[PL] CH10. Implementing Subprograms (2)

1. Nested Subprogram; nonlocally하게 access할 수 있는 모든 변수들은 activation record instance에 있음 -> 스택 안에 있음

(1) nonlocal 변수에 대한 reference : two-step

변수가 할당된 스택에서 activation record의 instance를 찾음 → 변수(activation record instance) 의 local offset를 사용하여변수에 access

 

(2) Semantic rules of static-scoped languages

- 주어진 서브프로그램에서, static ancestor 영역에 선언된 변수들에만 nonlocally하게 access

- 모든 static ancestor의 activation record instance는 그 안에 있는 변수들이 nested procedure에 의해 reference될 때, 스택 안에 존재함을 보장

   -> procedure는 오직 모든 static ancestor program unit이 active할 때만 callable

 

- 올바른 선언은 enclosing scope에서 가장 먼저 발견되는 선언이며, 가장 가깝게 처음으로 nested

  -> nonlocal reference를 지원하기 위해, static ancestor에 상응하는 스택에서 activation record의 모든 instance를 찾는 것이 가능  --> static chain, display

 

 

 

(3) Static chains;

- 스택에서 특정 activation record에 연결하는 static link의 체인

 -> 기존 서브프로그램의 모든 static ancestor를, static parent의 순서대로 연결

 

- nonlocal 변수에 대한 reference가 만들어질 때, 변수를 포함하는 static ancestor activation instance를 찾을 때까지, static chain을 검색하여 변수를 포함하는 activation record instance를 찾을 수 있음

 

- scope의 nesting은 컴파일 타임 때 알 수 있기 때문에, 컴파일러는 reference가 nonlocal일 뿐만 아니라 nonlocal object를 포함하는 activation record instance에 도달할 때 필요한 static chain의 길이를 결정

 

- Static depth

 : 가장 바깥쪽 영역에서 얼마나 깊게 중첩돼있는지 표현하는 static scope과 연관된 정수

 

- reference의 Nesting_depth (chain offset)

 : nonlocal reference에 대한 올바른 activation record instance에 도달하는데 필요한 static chain의 길이

 : X에 대한 reference를 포함하는 procedure의 static_depth와 X에 대한 선언을 포함하는 procedure의 static_depth 사이의 차이점

 

 

- Actual reference : (chain_offset, local_offset)

 

MAIN_2 -> BIGSUB -> SUB2 -> SUB3 -> SUB1

 

 

 

- 자기를 호출한 것을 point -> dynamic link

- 자기를 선언한 것을 point -> static link

 

- 프로그램 실행동안 어떻게 static chain이 유지?

  : 서브프로그램이 리턴할 때 필요한 액션

      -> activation record가 스택에서 제거되기 때문에 아무것도 할 필요 없음

  : 서브루틴 호출시 필요한 액션

     -> parent 영역의 가장 최근 activation record instance는 호출 시 발견되어야 함

     1. 런타임 때 부모 영역의 가장 첫번째 영역을 찾을 때까지 다이나믹 페인의 activation record instance를 확인

     2.

컴파일 타임 때 : 컴파일러는 caller와 호출된 프로그램을 선언한 procedure 사이의 nesting_depth를 계산

호출 시 : 호출된 procedure의 activation record instance의 static link는 caller의 static chain 의 아래로 내려감으로써 결정됨

link의 수는 컴파일 시간에 계산된 nesting depth의 수와 동일

 

- static chain method의 문제점

 : static parent 넘어 영역의 변수에 대한 reference는 비쌈

  -> access에 달성하기 위해선, 선언에 대한 reference로부터의 영역을 둘러싼 범위당 하나의 링크를 따라야 함

 

 : 각 reference의 비용은 nesting의 깊이에 따르기 때문에, 프로그래머에게 nonlocal reference의 비용을 측정하라고 하는 것은 어려움

 

 

(4) Display

- static link는 activation record에 저장되기 보단 display라고 불리는 단일 배열에 수집

- display의 content는 접근 가능한 activation record instance의 주소의 리스트가 중첩된 순서

- nonlocal reference : (display_offset, local_offset)

 

- disply를 사용한 nonlocal 에 대한 access

  : display에 있는 특정한 activation record의 링크는 display_offset이라고 불리는 static하게 계산된 값을 사용

  : activation record instance 안의 local offset은 계산되며 static chain의 구현과 동일하게 사용됨

- display의 k 위치의 포인터는 k의 static depth의 procedure에 대한 activation record instancce를 가리킴

 

- 새로운 영역 상황을 반영하도록 어떻게 display를 수정?

  : k의 static depth를 갖는 procedure P에 대한 호출에 필요한 display 수정은 

       -> 디스플레이의 k 위치의 포인터 복사본을 새로운 activation record에 저장

       -> P 위치에 대한 activation record instance에 대한 링크를 디스플레이에 둠

  : 종료 시 디스플레이에 다시 배치할 종료 서브프로그램의 활성화 레코드 인스턴스에 저장된 포인터

 

 

ex) procedure Q에 의한 procedure P 호출 (Q->P)

*Psd : static_depth of P

*Qsd : static_depth of Q

 

Qsd = Psd

Qsd < Psd

Qsd > Psd

 

 

------------------------------