[프로그래밍 언어론] Subprogram Control (10)

 

[9] Subprogram Control

Introduction
- Subprogram Control : sequence control, data control
- Sequence Control : copy rules, static segment, dynamic segment
- Scope Rules : static scope rule, dynami scope rule

Data Control Problems
- 정적 변수를 제외한 나머지 변수는 모두 Activation Record에 있다.
- 정적 변수를 제외한 모든 변수의 l-value는 특정 AR에서 offset으로 계산 가능하다.

@Computing L-Value
- 1. 변수를 포함하는 AR을 찾음
- 2. AR의 특정위치에서 변수의 l-value를 구함

Scope
- The scope of a variable is the range of statments over which it is visible.
- The nonlocal variables of a program unit are those that are visible, but not declared there.
- The scope rules of a language determin how references to names are associated with variables.
- Scope and lifetime are somtimes closely related, but are different concepts.

Scope Rules
- Local variables
- Non-local variables : 참조 문장이 포함된 블록과 선언한 블록이 다른 경우
- Static scope rule : 프로그램 구문에 따른 선언의 위치에 따라 변수의 영역이 결정됨 (spatial relationship)
- Dynamic scope rule : 프로그램 수행에 따라 변수의 영역이 결정됨 (temporal relationship)

Static Scope
- Based on program text
- Enclosing static scopes are called its static ancestors
- The nearest static ancestor is called a static parent
- Variables can be hidden from a unit by having a closer variable with the same name. (Scope Hole)
- Often encourages many globals.

@Static Scope Search Process
- Search declarations locally first
- Then in increasingly larger enclosing scopes, until one is found for the given name.

Block
- A Method of creating static scopes inside program units

Dynamic Scoping
- Based on calling sequeces of program units, not their textual layout
- References to variables are connected to declarations by searching back through the chain of subprogram calls that forced execution to this point
- Convenient, but poor readability

Referencing Environment
- The referencing environment of a statment is the collection of all names that are visible to the statement.
- In static scoped language, it is the local variables plus all visible variables in all of enclosing scopes.
- In dynamic scoped language, it is the local variable plus all visible variables in all active subprograms. (Execution has begun but yet terminated)
- 변수에 접근하기 위해 offset과 SL을 따라가야 하는 회수는 컴파일 시각에 알 수 있다.

Acvitation Record Stack
- Stack top에서 부터 accumulates allocatation of subprogram invocation
- AR 스택을 관리하는 방법 : Two Pointers
- 각 AR에는 Dynimic Link와 Static Link를 가르키는 포인터들이 있다.
- Dynamic Link Pointer : caller의 AR을 가르킴 (dynamic parent)
- Static Link Pointer : static parent의 AR을 가르킴 (static parent)

Recursion
- 재귀함수, dynamic link pointer를 사용

Nested Subprograms
- JavaScript use stack-dynamic local variables and allow subprograms to be nested. (Non-C-based static-scoped language)
- All variables that can be nonlocally accessed reside in some activation record instance in the stack
- Static scope rule : static chains, display

@The Process of Locating a Nonlocal Referernce
- 1. Find the correct activation record instance
- 2. Determine the correct offset within that activation record instance
- Finding the offset is easy
- Finding the correct activation record instance is not
- Static semantic rules guarantee that all nonlocal variables that can be referenced have been allocated in some activation record instance that is on the stack when the reference is made.

Static Chains
- A static chain is a chain of static links that connects certain ARI.
- The static chain from an ARI connects it to all of its static ancestors.
- Chase the static chain until the ARI that has the variable is found, if variable names were stored in the ARI chain.

@static_depth
- An integer associated with a static scope whoes value is the depth of nesting of that scope.

@chain_offset / nesting_depth
- The difference between the static_depth of the reference and that of the scope where it is declared.
- Representation: (chain_offset, local_offset)
- Local_offset is the offset in the  AR of the variable being referenced.

Static Chain Maintenance
- Assuming there are no paremeters that are subprograms and no pass-by-name parameters,
- The ARI must be built
- The dynamic link is just the old stack top pointer (호출된 곳)
- The static link must point to th emost recent ARI of the static parent in most situations (정의된 곳)

Implementing Nested Subprograms Referencing Environment
- 1. Search the dynamic chain until the first AIR for the static parent is found. (easy, but slow)
- 2. Treat procedure calls and definitions like variable refereces and definitions
- Have the compiler compute the number of enclosing scopes between the caller and the procedure where callee was declared (nesting depth) and store this nesting depth and send it with the call.
- 호출 시, caller의 static chain에서 nesting depth와 동일한 수의 링크만큼 아래로 이동

Evaluation of the Static Chain Methods
- A nonlocal reference is slow if the number of scopes between the reference and the declaration of the referenced variable is large.
- Time-critical code is difficult, because the costs of nonlocal references are not equal.

Display
- Static scope rule을 구현하기 위한 다른 방법
- Static link를 별도의 스택에 관리
- Reference environment의 모든 변수는 해당 스택이 가르키는 활성 레코드 내에 존재
- The entries in the display are pointers to the ARI's that have the variables in the referencing environment.
- Representation : (display_offset, local_offset)
- Display_offset to get the pointer into the display to the ARI
- Local_offset to get to the variable within the ARI
- Display가 register에 있다면 속도↑
- With display, all nonlocal references cost the same amount of time

Display Maintenance
- Display_offset is exactly the same as static_depth of the procesure.
- K+1 entries in the display where K is the static depth of currently executing unit.

@For a call to procedure P with a static_depth of K:
- 1. Save, in the new ARI, a copy of the display pointer at position k
- 2. Put the link to the ARI for P at position K in the display.
- At an exit, move the saved display pointer from the ARI back into the display at position K.

Static Chain vs. Display
- 1. Reference to locals : both equal
- 2. Reference to nonlocals : one level away, they are equal, farther, display is faster
- 3. Procedure calls : for one or two levels of depth, static chain is faster
- 4. Procedure returns : both have fixed time, but static chain is slightly faster
- Nonlocal 변수 참조가 빈번하다면, display가 유리하다.
- 거의 없다면, static chain이 더 유리하다.

Dynamic Scope Rule
- 서브 프로그램의 호출 순서에 따라 비지역 변수를 탐색

Implementing Dynamic Scope
- 1. Deep Access
- 해당 변수를 찾을 때까지 동적 링크를 계속 거슬러 올라감
- 거슬러 올라갈  chain 길이가 정해져 있지 않다.
- 활성 레코드에 변수 이름을 기록해야 한다.
- 2. Shallow Access
- 참조할 변수를 공용 공간에 저장
- Variable Stack : 각 변수마다 스택을 관리
- Central Table : 모든 변수와 변수 값을 관리하는 표

Variable Stack
- 각 변수마다 별도의 stack을 사용해 관리
- 변수 이름이 같다면 호출 순으로 (active) 가려진다.

Central Table
- 모든 변수를 한 곳에 관리하며 별도의 stack을 유지 (active flag 사용)

Nested Subprogram Special
- 중첩된 procedure가 있을 때, nonlocal variable은 global variable이 아닐 수 있다. (static link를 이용)
- Nested Subprograms의 static link는 static parent의 가장 최근 ARI를 가르킨다.
- Subprograms as parameters : Shallow binding, Deep binding, Ad-hoc binding (callback function)
- 각 방식별 subprogram의 Referencing Environments :
- 1. Shallow binding : caller의 접근 환경 (dynamic scope과 비슷)
- 2. Deep binding : callee가 선언된 접근 환경 (static scope과 비슷)
- 3. Ad-hoc binding : The environment of subprogram that includes the call statement that passed the subprogram as an actual parameter
- Subprogram을 인수로 전달할 경우, 가장 최근 ARI을 가리키지 않을 수 있다.

Subprogram Control

Parameter and Argument
- Parameter : 다른 서브프로그램으로부터 전달된 데이터를 보관하기 위한 변수, 매개변수
- Argument : 서브프로그램을 호출할 때 실제로 전달되는 데이터, 실인수

Parameter Passing
- 인수 전달 : 실 인수를 형식 매개변수에 전달하는 것
- 위치로 구별하여 전달하는 것이 일반적
- 인수 정달 방법 : 실 인수와 형식 매개변수와의 관계를 설정
- Call by name
- Call by reference
- Call by value
- Call by result (value-result)

인수 전달 관련 주제
- 효율성
- 전달 의미에 따른 인수의 분류
- In parameter
- Out parameter
- In-out parameter

Call by Name
- 형식인수 대신 실인수 주어진 식을 그대로 치환
- Textual substitution과 유사하나 이름 충돌은 피하는 식으로 이루어짐
- 선언 procedure P(X, Y, Z) { int I = 7; X = I + (7 / Y) * Z; }
- 호출 P(A, B+2, 27+3)
- 변환 { int I=7; A = I + (7 / (B + 2)) * (27 + 3); }

Implementation of Call by Name
- Thunk : 인수를 받지 않는 함수
- 각 실인수에 대하여, 실인수로 주어진 수식의 L-value와 R-value를 계산하는 thunk를 만듦
- 인수를 사용할 경우 해당 thunk 호출
- 시그니처 void P(X,Y)
- 호출 P(A, B+2)
- Thunk1 to return L-value(A)
- Thunk2 to return R-value(A)
- Thunk3 to return L-value(B+2)
- Thunk 4 to return R-value(B+2)

Call by Name is Hard to Read
- 이름에 의한 인수 전달을 이용하면 프로그램을 이해하기 힘들다.
- 정의 swap(x, y) { t = x; x = y; y = t; }
- 호출 swap(I, A[I]); swap(A[I], I);
- 어떻게 구현해도 위 두 호출 중 하나는 해결되지 않음

Call By Reference
- 실인수의 l-value를 전달
- 호출 P(A, B+2, 27+3)
- Temp1 = B+2
- Temp2 = 27+3
- Jump to subroutine (function)
- L-value of A
- L-value of Temp1
- L-value of Temp2

Alias
- 같은 변수에 대한 다른 이름
- 종종 Call By Reference가 원인
- 형식인수와 전역변수 충돌
- 정의 int sqSum(int &a, int &b) { a = a * a; b = b * b; return a + b; }
- 호출 int c = sqSum(a, a);

Call By Value
- 실인수의 r-value를 전달
- 실인수의 값을 복사하는 것과 같은 의미
- 호출 P(A, B + 2, 27 + 3)
- Temp1 = B + 2
- Temp2 = 27 + 3
- Jump to subroutine (function)
- R-value of A, Temp1, and Temp2

Call By Value-Result
- 인수의 r-value를 매개변수로 전달
- 서브프로그램 복귀시, 매개변수의 r-value를 실인수로 복사
- In-out parameter로 aliasing이 발생하지 않는다.
- 시그니처 void P(X, Y, Z)
- 호출 P(A, B + 2, 27 + 3)
- Temp1 = B + 2
- Temp2 = 27 + 3
- Jump to subroutine (function)
R-value of A, Temp1, and Temp2
A = X, Temp1 = Y, Temp2 = Z
- 값 복사에 따른 시간 부담이 있다.
- 복사 순서에 따라 결과가 달라질 수 있다.
- 호출시 l-value를 결정하기 때문
- 선언 sub1(x, y) {x = 2; y = 3;}
- 호출 sub1(list[idx], idx);