[2021-1 프로그래밍언어론] Chapter 10: Implementing Subprograms

Subprogram Linkage

• 서브프로그램의 call과 return
• General sementics of calls:
  • 파라미터 전달 방법
  • 로컬 변수의 stack-dynamic 할당
  • 호출한 프로그램의 실행 상태 저장
  • 제어권 전달받기?
  • 서브프로그램 중첩이 가능한 경우에서의 nonlocal variable 접근 방식
• General sementics of returns:
  • out mode와 inout mode 파라미터는 무조건 그들의 값을 반환해야 함
  • 서브프로그램 안의 Stack-dynamic한 지역 변수들의 할당 해제
  • 저장해뒀던 실행 상태로 되돌아가기
  • caller에게 제어권 반납하기

• Implementing "Simple" Subprograms: 중첩 없이 모든 지역변수가 static인 경우
  • Stack-dynamic한 로컬 변수의 할당/할당 해제가 없음

Actual code를 저장하는 부분과 Non-code part를 저장하는 부분으로 나뉜다.

• Actual code: 실제 소스코드
• Non-code part: 상태정보, 데이터, 주소값 등
  • Activation record: non-code part에 정보를 저장하는 포맷, 레이아웃
  • 이 포맷대로 생성되는 인스턴스가 ARI(Activation record instance)

 

ARI

1. ARI for Program with "Simple" Subprograms
   • 각 서브프로그램 별 ARI에 Local variables / Parameters / Return address가 저장되어 있음
   • Non-code part는 실행 이전에 결정되며 변하지 않음
2. ARI for Subprograms with Stack-Dynamic Local Variables
   • 스택(런타임) 구조, 서브프로그램이 호출될 때마다 스택에 쌓이는 시스템
     • EP(Environment Pointer): 런타임 스택에서 현재 실행중인 서브프로그램의 ARI를 가리키고 있는 포인터
   • 재귀 가능
   • 컴파일러가 지역 변수의 묵시적 할당과 회수를 위해 코드를 생성해야 함
   • 서브프로그램 별 ARI에 Local variables / Parameters / Dynamic link / Return address가 저장되어 있음
     • Dynamic link는 나를 호출하는 caller를 가리킴
   • 포맷은 고정되어 있지만, 사이즈는 유동적임(지역 변수나 파라미터 개수에 따라..., 변수 하나 당 박스 하나라고 생각하면 됨. 리스트는 연속적인 박스 여러 개)
3. Revised Sementic Call/Return Actions
   • 서브프로그램이 호출되었을 때
     1. Stack에 새 서브프로그램의 ARI를 올린다.
        • 상태정보를 저장하고, 파라미터와 돌아올 주소, 제어권을 전달한다.
     2. 새 ARI의 Dynamic link가 EP가 현재 가리키고 있는 ARI를 가리키도록 한다.
     3. 이후 EP가 새 ARI를 가리키도록 한다.
     연결 리스트를 생각하면 된다.
   • 서브프로그램이 종료되었을 때
     • Pass-by-value-result나 out-mode 파라미터가 있다면 상응하는 actual parameter에 그 값을 넘겨준다.
     • 서브프로그램이 함수라면 반환값이 caller에게 전달한다.
     • stack의 EP를 EP - 1(현재 실행한 서브프로그램의 ARI의 dynamic link가 가리키고 있는 ARI)로 설정한다.
     • 제어권 반납, 실행 상태정보 복구

 

Dynamic Chain and Local Offset

• Dynamic Chain: Dynamic link들을 묶어둔 것. 호출관계에 대한 정보를 갖고 있음
• Local Offset: 로컬 변수들이 그들의 ARI 시작점으로부터 얼마나 떨어져 있는지에 대한 상대적인 정보. 컴파일 시간에 알 수 있음
• 강의 슬라이드의 예제 참고

 

Nested Subprograms

• 몇몇 C-based가 아닌 언어들은 stack-dynamic한 지역 변수를 사용하는 동시에 서브프로그램의 중첩을 허용한다. 따라서 ARI에 static link 항목이 추가된다.
• 서브프로그램의 ARI를 통해 non-local한 변수에 접근할 수 있음(포함관계 파악)
• Nested Subprogram은 Static Chain 사용
  • Static Chain: 나를 포함하고 있는 부모를 가리키고 있음
  • Static Depth: 내가 Main으로부터 얼마나 중첩되어 있는가?
  • Chain Offset: 해당 변수가 사용되는 곳의 depth - 해당 변수가 정의된 곳의 depth
  • 변수에 대한 참조값은 두 개의 값의 pair 형태(chain_offset, local_offset)로 표현된다.
    • Non-local 변수를 갖고 있는 subprogram의 ARI 시작 위치
    • 거기서부터 얼만큼 더 가야 원하는 non-local 변수가 위치해 있는지
  • local에 없는 변수를 호출할 시 static link를 따라가 변수를 찾는다. 거기에도 없으면 부모의 static link를 계속 따라가며 변수를 찾는다.

 

Static Chain Maintenance

• 서브프로그램 호출 시
  • ARI 생성
  • 생성된 ARI의 dynamic link는 직전 stack top pointer가 가리키는 ARI를 가리키게 함
  • 생성된 ARI의 static link는 가장 위쪽에 있는 static parent의 ARI를 가리키게 함
• 문제점
  • nesting depth가 커지면 nonlocal reference 시간이 길어짐
  • 시간 비용을 예측하기 어려움

 

Blocks

• 사용자 정의 지역 범위
• C에서는 { }로 감싸 블록을 만듦

1. 블록을 파라미터가 없는 서브프로그램으로 취급하는 경우
   • 모든 블록은 각각의 ARI를 가짐
2. 블록의 크기를 제한할 수 있는 경우
   • ARI의 local variables로 취급

 

Implementing Dynamic Scoping

1. Deep Access: non-local 변수 참조 시 dynamic chain을 통해 변수 검색
   • 모든 ARI가 변수 이름을 갖고 있어야 함
2. Shallow Access: 모든 지역 변수를 공용 공간에 몰아넣고 테이블로 관리
   • 각 변수 이름마다 하나의 스택을 갖음
   • 실행되는 서브프로그램 순서에 따라 사용되는 변수 스택에 서브프로그램 push
   • 변수의 값을 가져올 때 해당 변수 스택의 top에 위치한 서브프로그램의 값을 사용하면 됨