[PL] 09. Implementing Subprograms

Subprogram Linkage

Subprogram이 call하고 return하는 것을 함께 부르는 것

 

Subprogram이 call한다는 것의 일반적 의미

• Parameter의 전달 방법 (Actual parameter가 formal parameter로 전달)
• Local 변수를 Stack-dynamic으로 할당해준다.
• 호출하는 프로그램(calling program)이 실행 상태를 저장한다.
• Transfer of control and arrange for the return (return을 위해 제어와 arrange를 전환)
• 중첩을 지원하면, non-local 변수에 대한 접근이 지원(arrange)되어야 한다.

 Subprogram이 return한다는 것의 일반적 의미

• out mode / inout mode의 parameter들은 반드시 그들의 값을 return해야한다.
• stack-dynamic local 변수들을 해제(Deallocation)
• 실행 상태를 복원
• control을 caller에게 반환

---

Simple Subprogram

모든 함수의 호출은 Main 함수에서 한다.

 

Call Semantics

• caller(main 함수)의 실행 상태를 저장한다.
• parameter를 전달한다.
• called된 곳으로 return address를 전달한다.
• called된 곳으로 control을 전송한다.

Return Semantics

• pass-by-value-result이거나 out mode parameter가 쓰이면 그 parameter의 현재 값을 대응되는 actual parameter로 옮긴다.
• function이면 function value를 caller가 얻을 수 있는 곳으로 옮긴다.
• caller의 실행 상태를 복원한다.
• caller로 control을 다시 전송한다

Required storage

• 상태 정보
• parameters
• return address
• return value for function
• temporary(임시 값)
• => 다 Stack에 저장

actual code / non-code part로 구분된다.

실행 중인 subprogram의 non-code part를 위한 format, 혹은 layout을 activation record라고 한다.

activation record instance(ARI)는 activation record의 구체적인 예시이다. (메모리에 들어가면 인스턴스다.)

내 프로세스가 돌아가는 메모리의 Stack 공간에 호출되어있는 함수의 개수만큼 activation record instance가 생성

---

Subprogram with Stack-Dynamic Local Variables

컴파일러는 local 변수의 암묵적인 할당/해제 코드를 생성해야 한다.

Recursion이 지원되어야 한다.

 

Dynamic link : 나를 호출하는 애를 가리킬 포인터

activation record의 형식은 static, size는 dynamic하다.

dynamic link는 caller의 activation record의 base를 가리킨다. 

base는 ARI의 맨 밑. 맨 위는 Stack top

activation record instance는 subprogram이 호출될 때 동적으로 생성된다.

activation record instance는 run-time stack에 상주한다.

 

Environment Pointer(EP)는 run-time system에 의해 유지.

현재 실행 중인 프로그램 유닛의 ARI의 base를 가리킨다.

한 함수가 return될 때, dynamic link가 가리키는 곳을 새 EP로 정한다.

---

Call Actions

• activation record instance를 생성한다.
• 현재 프로그램 유닛의 실행 상태를 저장한다.
• parameter를 계산하고 전달한다.
• 호출된 프로그램에게 return address를 전달한다.
• 호출된 프로그램에게 control을 전달한다. 

Prologue action of the called (호출된 프로그램)

• 이전 EP를 스택의 dynamic link에 저장하고 새 값을 생성한다.
• local 변수를 할당한다.

Epilogue action of the called (호출된 프로그램)

• pass-by-value-result이거나 out mode parameter가 쓰이면 그 parameter의 현재 값을 대응되는 actual parameter로 옮긴다.
• function이면 function value를 caller가 접근가능한 위치로 옮긴다.
• “current EP - 1”이 Stack top이 된다. 그리고 EP를 old dynamic link로 설정해준다.
• caller의 실행 상태를 복원해준다.
• caller로 control을 돌려준다. (return address로 PC(Program Counter)값을 바꿔준다.)

Dynamic Chain

• stack의 dynamic link들의 집합. (call chain이라고도 부름) (base pointer를 모아 놓은 것)
• local 변수는 EP에 주소가 있는 activation record의 시작으로부터 그들의 offset(= local_offset)을 통해 접근할 수 있다. 
• local 변수의 local_offset은 compile time에 컴파일러에 의해 결정된다. 
• 즉, base pointer + local_offset으로 local 변수의 주소를 계산할 수 있다.

---

Nested Subprograms

C 기반이 아닌 static-scoped 언어는 stack-dynamic local 변수를 사용한다. 

그리고 중첩된 subprogram을 허용한다.

non-locally 접근할 수 있는 모든 변수는 stack의 어떤 activation record instance에 상주한다.

 

non-local reference의 locating 과정

1. 올바른 activation record instance를 찾는다.
2. activation record instance 내에서 올바른 offset을 결정한다.

Locating a non-local reference

• offset을 찾는 것은 쉽다.
• 올바른 activation record instance을 찾는 것
  Static semantic rule은 참조될 수 있는 모든 non-local 변수가 참조가 이루어질 때는 stack에 어떤 activation record instance에 할당되었음을 보장

---

Static Scoping

Static chain

• 특정 activation record instance를 연결하는 static link의 체인

Static link

• Subprogram A의 activation record instance의 static link는 A의 static 부모의 ARI중 하나를 가리킨다.
• 즉, 나를 포함하고 있는 함수의 base point를 가리킨다.

Static chain을 따라가면 나를 포함하는 함수를 쭉 따라간다. 
모든 static ancestor과 연결되어 있다.

Static_depth는 static scope과 관련된 정수 값이다. 
nesting depth라고도 볼 수 있다.

nonlocal reference의 chain_offset 혹은 nesting_depth는 reference의 static_depth와 선언된 범위 사이의 차이다.

변수에 대한 참조는 (chain_offset, local_offset)의 쌍으로 표현 가능. 

여기서 local_offset은 참조되는 변수의 activation record 안에서의 offset이다.

sub3 코드 안에서 x = c + e; 
c랑 e는 나의 베이스로부터 계산 가능
x는 static link를 타고 3번 이동해서 위치를 계산해야 한다. 

 

Static Chain의 문제점

1. nonlocal 변수 참조는 nesting depth가 클수록 느리다.
2. 시간이 중요한 코드에서는 어렵다. 
    - nonlocal 참조의 cost를 결정하기 어렵다. / 코드 변경으로 nesting depth가 변경되면 cost도 변경된다.

---

Blocks

Blocks : 변수의 user-specified local scope

 

---

Implementing Blocks

1. Block을 parameter가 없는 subprogram으로 취급, 항상 같은 위치에서 호출한다. 모든 블록은 activation record를 가지고 instance는 매번 블록이 실행될 때마다 생성된다.
2. 블록에 필요한 최대 저장 공간을 정적으로 결정할 수 있으므로, 그만큼의 공간을 activation record 안의 local variables 이후에 할당할 수 있다.

---

Implementing Dynamic Scoping

Dynamic Scope 언어에서 non-local 변수를 찾아가는 방법

 

Deep Access

• non-local reference는 dynamic chain의 activation record instance를 검색해서 찾는다.
• chain의 길이는 정적으로 결정될 수 없다.
• 모든 activation record instance는 변수 이름(variable name)을 가져야 한다.

Shallow Access

• local 변수들을 central place에 위치시킨다.
• 각 변수 이름(variable name)마다 1개의 스택을 사용
• Central table에는 각 변수 이름(variable name)마다 entry가 있다.