[프로그래밍 언어론] 서브프로그램 구현

서브프로그램 구현 개요

서브프로그램 연결

• 서브프로그램 호출(call) 작업과 복귀(return) 작업
• 서브프로그램 호출 시 해야 할 작업
  • 호출하는 서브프로그램의 상태 저장
  • 인수 전달
  • 복귀할 주소 저장
  • 호출되는 프로그램으로 분기
• 서브프로그램 복귀 시 해야 할 작업
  • 필요에 따라 형식인수 값 복사(out parameter)
  • 함수의 경우, 반환값 전달
  • 호출한 서브프로그램의 상태 복귀
  • 호출한 서브프로그램으로 분기

활성 레코드

• 서브프로그램 호출에 필요한 공간
  • 호출자의 상태 정보를 보관할 공간
  • 인수를 저장할 공간
  • 함수의 경우 반환값을 저장할 공간
  • 복귀할 주소를 저장할 공간
• 활성 레코드(activation record)
  • 수행 중인 서브프로그램에서 코드를 제외한 데이터 부분이 저장되는 형태
  • 활성 레코드 틀 자체는 정적으로 결정 가능
• 활성 레코드 인스턴스(activation record instance)
  • 활성 레코드의 구체적인 예
  • 활성 레코드 틀 형태로 저장된 데이터
  • 활성 레코드 인스턴스는 실행 시 필요에 따라 생성, 소멸됨

서브프로그램 관련 용어 정리

• 동적 체인(dynamic chain, call chain)
  • 활성 레코드 스택 상에서 인접한 동적 링크들을 차례로 연결한 것
  • 리스트 형태임
• 정적 체인(static chain)
  • 활성 레코드 스택 상에서 정적 링크들로 연결된 체인
  • 트리 형태임
• 지역 변위(local offset)
  • 활성 레코드 시작 부분에서 스택 동적 변수 위치까지의 변위
  • 컴파일 시간에 계산 가능

정적 체인과 동적 체인

정적 체인

• 정적 깊이
  • 정적 영역의 중첩 깊이
  • 자신을 감싸고 있는 정적 영역의 개수
• 체인 변위
  • 비지역변수가 참조되는 지점의 정적 깊이와 해당 비지역변수가 선언된 지점의 정적 깊이의 차
  • 체인 변위만큼 정적 체인을 거슬로 올라가면 비지역변수를 찾을 수 있음
• 변수 참조
  • 임의의 변수 주소는 (체인 변위, 지역 변위) 순서쌍으로 표현 가능
  • 지역변수와 비지역변수 모두 가능
  • 체인을 거슬러 올라가는 비용은 체인 변위가 클수록 높아짐
• 정적 체인 관리
  • 서브 프로그램 호출 시
    • 활성 레코드 인스턴스 구축
    • 동적 링크는 이전 프레임을 가리키도록 설정
    • 정적 링크는 정적 부모의 가장 최근 활성 레코드를 가리키도록 설정
  • 정적 부모의 최근 활성 레코드 탐색 방법
    • 동적 링크를 계속 거슬러 올라감
    • 호출자와 피호출자의 정적 깊이 차이를 이용
• 정적 체인 방법의 평가
  • 장점
    • 구현이 쉬움
    • 각 활성 레코드에 하나의 링크만 유지하면 되므로 공간 낭비가 적음
  • 단점
    • 참조되는 비지역변수가 선언된 블록의 중첩 깊이와 참조 문장을 포함한 중첩 깊이의 차이가 크다면 비지역변수 참조 시간 부담이 커짐
    • 비지역변수 참조 시간이 변수에 따라 다르기 때문에, 응답 시간이 빨라야 하는 프로그램을 작성할 때는 불리함

동적 체인

• 동적 영역 규칙을 구현하기 위한 방법
• 비지역변수를 자신의 호출자에서 찾아야 함
• 깊은 참조(deep access)
  • 해당 변수를 찾을 때까지 동적 링크를 계속 거슬러 올라감
  • 거슬러 올라갈 체인 길이가 정해져 있지 않음
  • 활성 레코드에 변수 이름을 저장해야 함
• 실시간 탐색이 필요

기타 서브프로그램 구현 방법

디스플레이

• 정적 체인 방법을 대체할 수 있는 방법
• 수행 중 참조할 수 있는 모든 정적 링크를 별도의 스택(디스플레이)에 관리
  • 디스플레이(display): 현재 수행 중인 블록과 이 블록의 정적 조상에 대한 활성 레코드를 가리키는 포인터로 이루어진 스택
• 참조 환경의 모든 변수는 이 스택이 가리키는 활성 레코드 내에 존재함
• 변수 참조 표기법
  • 순서쌍: (디스플레이 변위, 지역 변위)
  • 디스플레이 변위(display offset)는 해당 변수가 선언된 서브프로그램의 정적 깊이와 동일
• 변수 참조 방법
  • 디스플레이 변위를 이용하여 참조할 변수를 포함하는 활성 레코드 선택
  • 지역 변위(local offset)를 이용하여 해당 활성 레코드 내의 변수 위치 선책
• 디스플레이 관리
  • 정적 깊이와 디스플레이 크기
    • 디스플레이 변위는 정적 깊이와 동일
    • 현재 수행 중인 서브프로그램의 정적 깊이가 p라면 디스플레이 내에는 p+1개의 항목이 존재
  • 서브프로그램 호출 시
    • 호출되는 서브프로그램의 정적 깊이가 q라면
    • 디스플레이의 q번째 항목(D[q])를 새로 생성된 활성 레코드 인스턴스의 특정 위치에 백업하고
    • 새로 생성된 활성 레코드 인스턴스 주소를 D[q]에 저장
  • 서브 프로그램 복귀 시 현재 활성 레코드 내에 백업되었던 D[q] 항목을 다시 복구함
• 정적 체인과 디스플레이 비교정적 체인 디스플레이

  지역변수 참조	두 방법 모두 비슷한 비용	두 방법 모두 비슷한 비용
  비지역변수 참조	한 단계 떨어진 경우, 디스플레이와 같은 비용	멀리 떨어져 있는 경우에 유리함
  서브프로그램 호출	정적 깊이 차가 적으면 유리	정적 깊이 차가 크면 유리
  서브프로그램 복귀	상수 시간(약간 빠름)	상수 시간(백업 복구 필요)

변수 스택과 중앙 테이블

• 동적 영역 규칙 구현의 또 다른 방법
• 얕은 참조
  • 비지역변수와 지역변수를 구별하지 않음
  • 참조되는 모든 변수의 정보는 한 군데 존재해야 함
  • 변수 스택: 변수 이름마다 스택이 존재함
  • 중앙 테이블: 모든 변수의 값을 한 곳에서 관리함

과거 민감(history-sensitive) 서브 프로그램

• 이전 호출 내용을 기억하는 서브프로그램: 서브프로그램이 종료되어도 서브프로그램의 상태 정보 일부가 기억됨
• 과거 민감 서브프로그램 구현
  • 전역변수 이용: 전역변수를 이용하여 서브프로그램 상태 정보를 기억함. 정보 은닉이 보장되지 않음
  • 정적 지역변수 이용: 서브프로그램 종료 후에도 할당이 해제되지 않는 정적 지역변수 이용. 정보 은닉이 보장됨

코루틴(coroutine)

• 여러 개의 진입 위치를 스스로 관리하는 서브프로그램
• 코루틴은 ‘호출된다’고 하지 않고 ‘재개된다(resumed, 계속된다)’고 함
• 서브프로그램 호출이 종속적이 아닌 대칭적임(대칭적 제어 모델)
• 프로그램 수행이 번갈아 이루어짐(유사 병렬성)
• 코루틴의 흐름제어
  • 메인 유닛이 첫 번째 코루틴을 재개함
  • 코루틴이 서로를 재개함(무한 재개되는 경우가 많음)
• 코루틴의 활용: 생산자-소비자 시뮬레이션, 카드 게임 시뮬레이션 등