[Programming Language] 7. 부프로그램 구현 (2)

직전글
2023.08.02 - [Language] - [Programming Language] 7. 부프로그램 구현 (1)
 

- 재귀 부프로그램 예제

int factorial(int n) {
   // 지점 1
   if (n <= 1) return 1;
   else return ( n * factorial(n-1) );
   // 지점 2
}

void main() {
   int value;
   value = factorial(3);
   // 지점 3
}

함수 factorial의 활성화 레코드 형식

지점1에 도착할 때마다의 스택 내용 (지점1을 총 세 번 지나감)

각각은 함수 값이 정의되지 않은 ARI를 가지고 있음. 첫 번째 ARI는 호출자 main의 복귀 주소를 가지고 있음. 다른 ARI는 함수 factorial에 대한 복귀 주소를 가지고 있음.

지점2에 도착할 때마다의 스택 내용 (지점2를 총 세 번 지나감)

지점 2는 return이 수행되었지만, ARI가 스택에서 제거되기 이전임. 함수 코드에서 매개변수 n과 함수의 재귀 호출에서 반환된 값을 곱하고 있음. 함수 값은 순서대로 1, 2, 6임.
 

● 중첩 부프로그램

정적 영역 언어이고 스택 동적 지역 변수를 사용하면서, 부프로그램의 중첩을 허용하는 언어. (Python, JavaScript, Ruby, Lua, Ada 등. C는 해당안됨.)
중첩 부프로그램을 갖는 정적 영역 언어에서 비지역 변수의 참조는 두 단계 접근 과정을 요구함.
비지역으로 접근될 수 있는 모든 비정적 변수는 스택에 생성된 활성화 레코드 인스턴스 중의 하나에 존재하기 때문에,
(1) 스택에서 그 변수가 할당된 활성화 레코드 인스턴스를 찾고,
(2) 발견한 활성화 레코드 인스턴스에서 변수의 지역 오프셋을 사용하여 변수에 접근
해야 함.
 

- 변수가 할당된 활성화 레코드 인스턴스 찾기

ㄴ 정적 조상 영역의 변수 접근에 관한 규칙들

• 부프로그램에서는 자신의 정적 조상 영역에서 선언된 변수만이 가시적으로 접근될 수 있음
• 모든 정적 조상의 활성화 레코드 인스턴스는, 그 인스턴스에 있는 변수가 어떤 중첩 부프로그램에 의해서 참조될 때, 스택에 항상 존재해야 함. 즉, 모든 정적 조상 부프로그램이 활성화되어 있을 때만, 부프로그램을 호출할 수 있음.
  만약, 어떤 특정한 정적 조상이 활성화 상태가 아니라면, 그 지역 변수는 기억 장소가 바인드되지 않았을 것이고, 따라서 그들에 접근을 허용하는 것은 무의미함. (이전에 나왔던 클로저는 이 규칙을 위반함!)

ㄴ 비지역 참조의 의미에 따르면,
"정확한 선언"은 둘러싸고 있는 영역에서 찾을 때, 첫 번째 발견된 선언(가장 가깝게 중첩된 첫 번째 선언)임. 따라서, 비지역 참조를 지원하기 위해, 정적 조상에 대응되는 모든 활성화 레코드 인스턴스를 스택에서 찾는 것이 가능해야 함.
 
위 내용들에 따라, 정적 체인을 이용하여 활성화 레코드 인스턴스를 찾는 방법이 존재함을 알 수 있음.
 

- 정적 체인

중첩 부프로그램을 허용하는 언어에서 정적 영역을 구현하는 가장 일반적인 방법.
이 방법에서는, 정적 링크(a.k.a 정적 영역 포인터)라고 불리는 새로운 포인터가 활성화 레코드에 추가됨. 정적 링크는 정적 부모의 활성화 레코드 인스턴스의 시작 주소를 가리킴. 정적 링크는 비지역 변수를 접근하기 위하여 사용됨.
정적 링크가 추가됨에 따라, 지역 변수를 위한 지역 오프셋 계산이 달라질 수 있음에 주의해야 함.
※ 참고 ※ 동적 링크: 호출한 함수의 시작 주소를 가르킴. / 정적 링크: 정적 부모의 시작 주소를 가르킴.
 
정적 체인은 스택에서 어떤 활성화 레코드 인스턴스들을 연결하는 정적 링크의 체인임
부프로그램 p가 수행되는 동안, p의 활성화 레코드 인스턴스의 정적 링크는 p의 정적 부모 프로그램 단위의 활성화 레코드 인스턴스를 가리킴.
또한, 정적 부모 프로그램 활성화 레코드 인스턴스의 정적 링크는 p의 조부모 프로그램 단위의 활성화 레코드 사례를 가리킴 (조부모 프로그램 단위가 존재한다면)
결론적으로, 정적 체인은 정적 부모를 시작으로 실행 중인 부프로그램의 모든 정적 조상을 연결함.

정적 체인 시각화

- 정적 링크를 이용한 비지역 변수의 활성화 레코드 인스턴스 검색

ㄴ 단순한 방법
그 변수를 포함하는 정적 조상 활성화 레코드를 찾을 때까지 정적 체인을 따라가는 것
 
ㄴ 더 쉬운 방법
영역의 중첩은 컴파일 시간에 알려지므로, 컴파일러는 참조가 비지역 참조라는 것 뿐만 아니라, 비지역 객체를 포함하는 활성화 레코드 인스턴스에 도착하는데 필요한 정적 체인의 길이도 알고 있음.
 
+ 정적 깊이
정적 영역이 최외곽 영역으로부터 얼마나 깊게 중첩되었는가를 나타내는 정수.
다른 프로그램 단위에 중첩되지 않은 프로그램 단위의 정적 깊이는 0임.
부프로그램 A가 정적 깊이가 0인 부프로그램 내에 중첩되었다면, A의 정적 깊이는 1이고, 부프로그램 A가 중첩 부프로그램 B의 정의를 포함하면, B의 정적 깊이는 2임.
 
+ 중첩 깊이 (또는 체인 오프셋)
변수 X의 비지역 참조를 위한 정확한 활성화 레코드 인스턴스에 도착하는데 필요한 체인의 길이는 정확히 X의 참조를 포함하는 부프로그램(A)의 정적 깊이 (Da)와 X의 선언을 포함하는 부프로그램(B)의 정적 깊이 (Db) 의 차이임. 즉, Da – Db 임.
 
+ 실제 참조
정수의 순서쌍 (체인 오프셋, 지역 오프셋)으로 표시함.

// Python
def f1() :
  def f2() :
    def f3() :
      ...
    ...
  ...
# end of f1
...

f1, f2, f3의 정적 깊이는 각각 0, 1, 2임. f3이 f1에서 선언된 변수를 참조한다면, 그 참조의 체인 오프셋은 2임 (f3의 정적 깊이 – f1의 정적 깊이). f3이 f2에서 선언된 변수를 참조한다면, 그 참조의 체인 오프셋은 1임.
 

- 비지역 접근의 전체 과정을 이해하기 위한 Ada 프로그램 예제

프로시저 호출 순서: Main_2는 Bigsub를 호출함 → Bigsub은 Sub2를 호출함 → Sub2는 Sub3를 호출함 → Sub3는 Sub1을 호출함

지점 1 에서의 스택 상황

프로시저 Sub1의 지점 1에서 변수 A의 참조는 Bigsub의 비지역 변수 A가 아니라 지역 변수 A임.
지점 1에서 A의 이 참조는 (체인 오프셋, 지역 오프셋) 쌍으로 (0, 3)을 가짐.
지점 1에서 B의 참조는 Bigsub의 비지역 변수임.
지점 1에서 B의 참조는 (1, 4)로 표현 가능함.
지점 1에서 Sub2의 B는 이 지점에서 참조 환경에 있지 않고, 접근 가능하지 않음.
지점 1에서 C의 참조는 Bigsub에서 선언된 C이고 (1, 5)로 표현됨.
 
지점 1, 지점 2, 지점 3에서 변수 A의 참조는 다음과 같음.
(0, 3) = 지역 변수
(2, 3) = 비지역 변수 (Bigsub의 변수 A)
(1, 3) = 비지역 변수 (Bigsub의 변수 A)
 

● 블록

여러 언어들은 (C, C++, Java 등) 변수를 위한 사용자 지정 지역 영역을 제공함. (이전 게시물 참고)

- 블록을 활성화 레코드에 구현하는 방법

정적 체인 방법을 사용하여 구현 가능함. 즉, 블록은 프로그램의 같은 장소에서 항상 호출되는 (즉, 블록이 시작되는 위치에서 항상 호출되는) 매개변수가 없는 부프로그램으로 처리하면 됨. 따라서, 모든 블록은 활성화 레코드를 가짐. 해당 활성화 레코드 인스턴스는 블록이 시작될 때 생성됨.
 

- 더 단순하고 효율적인 방법

모든 블록 변수의 오프셋을 정적으로 계산하면서, 블록 변수를 마치 지역 변수인 것 처럼 처리면 됨.

// C
void main() {
  int x, y, z;
  while (...) {
    int a, b, c;
    ...
    while (...) {
       int d, e;
       ...
    }
  }
  while (...) {
    int f, g;
    ...
  }
  ...
}

f, g가 정의되었을 때, a, b, c, d, e는 스택에서 이미 제거된 상태이기 때문에, f, g가 a, b의 위치에 할당될 수 있음을 표시한 것임.
 

● 동적 영역 규칙의 구현

동적 영역 언어에서 지역 변수와 변수에 대한 비지역 참조가 구현되는 두 가지 방법에는 (1) 심층 접근 (Deep Access) 과 (2) 피상 접근 (Shallow Access)이 있음.
 

- 심층 접근

동적 영역 언어에서 지역 변수가 스택 동적 변수이고, 활성화 레코드의 일부라면, 비지역 변수의 참조는 가장 최근에 활성화된 부프로그램부터 시작해서 다른 부프로그램의 활성화 레코드 인스턴스를 탐색하면 해결됨.
이 개념은 정적 체인 대신에 동적 체인을 사용하는 것만 제외하고는 중첩 부프로그램을 갖는 정적 영역 언어의 비지역 변수를 접근하는 것과 유사함.
동적 체인은 활성화된 역순으로 모든 부프로그램 활성화 레코드 인스턴스를 연결하므로, 동적 영역 언어의 비지역 변수를 참조하는데 필요함.
이런 접근은 스택 심층부에 대한 탐색을 요구하기 때문에 심층 접근라고 부름.

심층 접근의 간단한 시각화

ㄴ 코드 예시

// 실제로 존재하는 언어 아님
void sub3() {
  int x, z;
  x = u + v;
  ...
}

void sub2() {
  int w, x;
  ...
}

void sub1() {
  int v, w;
  ...
}

void main() {
  int v, u;
  ...
}

함수 호출 순서 가정: main은 sub1을 호출 → sub1은 sub1을 호출 → sub1는 sub2를 호출 → sub2는 sub3을 호출

위의 활성화 레코드 인스턴스에는 정적 링크가 없음.(필요가 없음)
함수 sub3의 변수 x, u, v의 참조에서, u라는 이름을 갖는 유일한 변수는 main에만 존재하므로, 변수 u를 참조하기 위하여 스택에 있는 모든 활성화 레코드 인스턴스를 탐색한 후에 발견할 수 있음.
이 탐색은 4개의 동적 링크를 따라 움직이면서 10개의 변수 이름을 조사함.
( 순서대로  (1) sub3에서 x, (2) sub3에서 z, (3) sub2에서 w, (4) sub2에서 x, (5) sub1에서 v, (6) sub1에서 w, (7) sub1에서 v, (8) sub1에서 w, (9) main에서 v, (10) main에서 u 발견)
함수 sub1의 변수 v의 참조는 함수 sub1의 가장 최근 활성화 레코드 인스턴스에서 발견됨.
이 탐색은 2개의 동적 링크를 따라 움직이면서 5개의 변수 이름을 조사함.
( 순서대로 (1) sub3에서 x, (2) sub3에서 z, (3) sub2에서 w, (4) sub2에서 x, (5) sub1에서 v 발견)
 
ㄴ 동적 영역 언어의 심층 접근 방법과 정적 영역 언어의 정적 체인과의 차이점
 
(1) 동적 영역 언어에서는 컴파일 시간에 탐색할 체인의 길이를 결정하는 방법이 없음
체인에 있는 모든 활성화 레코드 인스턴스는 변수를 포함하는 첫 번째 인스턴스가 발견될 때까지 탐색됨.
이것이 동적 영역 언어가 정적 영역 언어보다 전형적으로 느린 실행 속도를 갖는 이유임.

(2) 동적 영역 언어 구현에서 활성화 레코드는 탐색 과정을 위해서 변수의 이름을 저장해야 함.
정적 영역 언어 구현에서는 단지 값만이 요구됨. (예: (체인 오프셋, 지역 오프셋) 쌍으로 표시)
 

- 피상 접근

피상 접근은 심층 접근과 같은 목적을 달성하기 위한 다른 구현임.
피상 접근 방법에서 부프로그램에서 선언된 변수는 그 부프로그램의 활성화 레코드에 저장되지 않음.
동적 영역에서는 주어진 시점에 특정 이름의 가시적인 변수가 기껏해야 하나이므로, 매우 다른 접근 방법이 취해짐.
 
ㄴ 방법
 
전체 프로그램에 있는 각 변수에 대해 별도의 스택을 만듦.
특정 이름을 갖는 새로운 변수가 호출된 부프로그램의 선언에 의해서 생성될 때마다 변수는 그 이름을 위한 스택의 최상위에 한 개의 셀을 할당 받음.
이름의 참조는 그 이름과 관련된 스택의 꼭대기에 있는 변수임. 왜냐하면, 꼭대기에 있는 변수가 가장 최근에 생성된 변수이기 때문.
부프로그램이 종료될 때, 지역 변수의 존속시간이 끝나고, 그 변수 이름에 대한 스택에서 한 항목이 제거됨.

ㄴ 장점
변수의 빠른 참조를 허용함.

ㄴ 단점
부프로그램의 진입 시와 종료 시에 스택의 유지보수 비용이 높아짐.