[PL] CH10. Implementing Subprograms

1. The general semantics of Calls and returns

(1) Subprogram linkage

- subprogram call, return

- subprogram의 구현은 subprogram linkage의 의미를 기반으로 함

 

(2) The actions associated with subprogram call

- parameter passing 메카니즘을 포함

- 로컬 변수에 대해 저장공간을 할당하고, 이 변수들을 저장공간에 binding

- 호출하는 프로그램의 execution status 저장

- 서브프로그램의 코드로 제어권을 전송하고, 서브프로그램 수행이 완료되면 제어권은 적절한 위치로 다시 돌아감

- nonlocal 변수에 접근하기 위해 제공되는 메카니즘을 일으킴

 

(3) The actions associated with subprogram return

- 서브프로그램이 out mode이고 copy에 의해 수행되는 파라미터를 가질 때, return process의 첫번째 행동은 관련된 formal parameter의 local value를 actual parameter로 이동시킴.

- 로컬 변수에 대한 저장공간을 할당 해제

- nonlocal references에 사용된 메카니즘을 리턴

- 제어권은 호출하는 프로그램으로 리턴

 

 

2. Implementing "Simple" Subprograms

(1) Subprograms in early version of FORTRAN

- 서브프로그램은 recursion을 허용하지 않음

- nonolocal variables의 모든 referencing은 COMMON을 통해 이뤄짐

- 서브 프로그램에 선언된 변수들은 static하게 할당됨

 

(2) The semantics of a FORTRAN 77 subprogram call

- 현재 프로그램의 execution status를 저장

- parameter passing 프로세스를 수행

- callee에게 return address를 전달

- 제어권을 callee에게 전달

 

(3) The semantics of a FORTRAN 77 subprogram return

- pass-by-value-result 파라미터가 사용되면, 이 파라미터의 현재 value들은 상응하는 actual parameter로 이동

- 서브프로그램이 함수이면, 함수 값은 caller에 접근 가능한 위치로 이동

- caller의 execution status가 복원

- 제어권은 다시 caller에게 전달

 

(4) call, return 수행은 다음을 위한 저장공간이 필요함

- caller에 대한 status information

- parameters

- Return address

- 함수 서브 프로그램에 대한 함수 값

 

 

(5) A FORTRAN 77 서브프로그램은 사이즈가 고정된 2가지 파트로 구성됨

- static한 서브프로그램의 actual code

- call/return 수행에 위한 로컬 변수 및 데이터 영역

   -> 서브프로그램의 noncode 영역은 서브프로그램의 특정한 execution, activation과 관련됨 -> activation record

   -> FORTRAN 77은 recursion을 허용하지 않기 때문에, 주어진 서브프로그램에는 한 번에 서브 프로그램의 하나의 active version을 가짐

        => 서브 프로그램에 대한 activatio record의 단일 instance만 가지며, static하게 할당됨

 

FORTRAN 77 프로그램의 코드와 activation record

 

수행 전에 할당됨

 

 

 

3. Implementing subprograms with stack-dynamic local variables (with recursion)

(1) 더 복잡한 activation records

- ALGOL 언어의 서브프로그램 linkage는 더 복잡함

  : 파라미터는 2개의 method에 의해 전달됨

ex) modular-2 -> pass by value/reference

 

- 서브 프로그램에 선언된 변수들은 동적으로 할당됨

- Recursion은 서브프로그램의 다양한 동시적인 activation의 가능성을 가짐

   -> activation record의 다양한 instance가 필요함

   -> 각 activation은 return address와 함께, formal parameter 및 동적으로 할당된 로컬 변수에 대한 자체 copy본을 필요로 함

 

- ALGOL 언어는 nonlocal 변수에 접근하기 위해 static scoping을 사용

이러한 nonlocal accesses에 대한 지원은 linkage mechanism의 파트

 

(2) Creation of activation record

- procedure을 activating 하는 것은 procedure에 대한 activation record의 instance의 동적 생성이 필요함

- call과 return semantic은 마지막으로 호출된 서브프로그램이 가장 먼저 완료된 것으로 지정하기 때문에, 스택에서 activation record의 instance를 생성하는 것은 합리적

 

   -> 모든 procedure activation은 스택의 activation record의 새로운 instance를 만듦

 

(3) Activation record

- 주어진 서브프로그램에 대한 activation record의 format, size는 컴파일 타임 때 알 수 있음

- 로컬 변수는 activation record 내에서 저장 공간에 binding

- Static link (static scope pointer)

   : static parent의 activation의 activation record instance를 가리킴

   : nonlocal 변수에 대해 접근할 때 사용

 

- Dynamic link

   : caller (dynamic parent)의 activation record의 instance를 가리킴

   : static-scoped 언어에서, procedure가 수행을 완료하면, 현재 activation record instance의 destruction에서 사용됨

 

- Return address : code_segment, offset

- (Actual) Parameters : caller에 의해 제공되는 values/addresses

 

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

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

 

ex)

 

 

 

(4) Example without recursion and nonlocal references

 

MAIN_1 -> B(P) -> A(S) -> C(Y) 

 

 

 

- Dynamic Chain (call chain)

 : 주어진 시간에 스택에 존재하는 dynamic link의 집합

 : xecution이 현재 위치에 도달한 방법의 dynamic 기록을 나타냄

 

 

- Local_Offset

 : 로컬 변수에 대한 reference는 코드 영역에서 로컬 영역의 activation record의 시작으로 부터의 offset으로 나타낼 수 있음

 : activation record에서 변수의 local_offset은 컴파일 타임에서 결정되며, activation record와 관련된 procedure에서 선언된 변수의 order, type, size를 사용

 

 

(5) Recursion

ex. recursion을 이용한 factorial 계산