[PL] CH10. Implementing Subprograms (3)

1. display 구현

(1) 프로그램에서 서브프로그램의 최대 static depth인 display의 최대 사이즈는 컴파일러에 의해 결정됨

(2) 메모리에 run-time static array로 저장됨

      -> 메모리 위치를 통해 기계가 indirect addressing을 할 경우, nonlocal access는 1개 이상의 메모리 사이클을 돎

(3) 레이스터에 display 두기 위해 -> 추가 메모리 사이클이 필요하지 않음

 

 

2. Static chaining vs. display method ; non-local 처리 방법

(1) 레지스터에 display가 저장되지 않으면, display의 로컬 변수에 대한 참조는 static chain보다 느림 (indirection 레벨 추가)

(2) display의 static level이 1개 이상 있는 nonlocal 변수에 대한 reference는 static chain보다 바름

(3) display가 사용될 때, 모든 nonlocal reference에 대한 시간은 동일

(4) 호출된 프로그램이 몇몇의 static level 이상이 아니면, procedure에서의 유지는 stati chains 보다 빠름

(5) 비교

- deep static nesting, 먼 nonlocal 변수에 대한 reference가 많으면 -> display

- few nesting level, 먼 nonloal 변수에 대한 reference가 적으면 -> static chaining

(6) 일반적으로 nesting level 은 3 미만

 

 

3. Blocks

(1) Block = compound statement + data 선언

(2) Block의 구현

- 방법 1) parameter가 없는 procedure로서, 항상 프로그램의 같은 위치에서 호출

     -> 최대 nesting이 증가하면 -> display 사이즈 증가

- 방법 2) 블럭 변수에 필요한 공간의 양은 activation record에서 다음 로컬 변수에 대해 할당될 수 있음

    -> 모든 블럭 변수에 대한 offset은 static하게 계산될 수 있으므로, 블럭 변수는 그들이 로컬 변수인 것처럼 확실하게 address됨

 

a, b 와 f, g 는 같이 할당되어 (sharing), offset이 같음

 

 

4. Dynamic scoping 구현 ; 자기를 선언하고 호출한 것을 찾음

(1) Deep access

 - nonlocal reference는 최근에 액티브한 다른 서브프로그램에서 찾으므로써 해결될 수 있으며 가장 최근에 activated된 것을 시작으로 함

   : dynamic-chain을 따름

   : access하려면 스택에서 깊숙이 검색이 필요할 수 있음

 - 컴파일 타임 때 검색해야 할 체인의 길이를 결정할 수 없음

 - Activation record는 search process에 대한 변수의 이름을 반드시 저장해야 함

-  activation record : 파라미터, 로컬 변수, 로컬 변수의 이름에 대한 심볼, static link, return address, dynamic link

- ex) 호출 순서: MAIN_6 -> A -> A -> B-> C

C의 x := u + v에서 u는 c에서 선언하지 않았으므로 C 이전에 호출된 곳에서 선언되었는지 찾아야 함

MAIN_6에서 u가 선언되었으므로 여기서 참조함

v도 C에서 선언하지 않았으므로 C 이전에 호출된 곳에서 선언되었는지 찾아야 함

가장 최근에 선언된 곳이 A이므로 여기서 참조했음

 

(2) Shallow access; 이름이 다른 변수 별로 스택 생성 

 : 서브프로그램엣 선언된 변수들은 이 서브프로그램의 activation record 안에 저장되지 않음

 : activation record : 파라미터, return address, dynamic link

 

 (1) 구현

- 방법 1) 완성된 프로그램에서 각 변수 이름에 대한 분리된 스택을 가짐

   : 특정 이름에 대한 새로운 변수가 서브프로그램의 활성화 시작에서 선언될 때마다, 이 이름에 대한 스택에 셀이 넣어짐

   : 이름에 대한 모든 참조는 스택의 top의 변수에 대한 것

   : 변수에 대한 참조는 빠르지만, 서브프로그램의 시작과 끝에서 스택을 유지하는 것은 비쌈

수행이 끝나면 top을 pop