Joonsu Ryu

Researcher

10장의 주제는 부프로그램의 구현입니다. 이번 장을 한 문단으로 요약하면 다음과 같습니다.

“이 장의 목적은 주요 명령형 언어에서 부프로그램을 구현하는 방법을 알아보는 것입니다. 토론은 독자에게 그러한 언어가 어떻게 “작동”하는지에 대한 통찰력을 제공합니다. 부프로그램 구현의 어려움이 증가하는 이유는 재귀에 대한 지원과 비지역 변수 접근에 대한 지원을 포함해야 하기 때문입니다.”

부프로그램의 호출과 반환 연산을 합쳐서 부프로그램 연결(Subprogram Linkage)이라고 합니다. 부프로그램의 구현 방법은 부프로그램 연결의 의미를 기반으로 해야 합니다.

대부분의 언어에서 부프로그램 호출에는 많은 동작이 수행됩니다. 특히 중요한 부분은 바로 지난 장에서 다루었던 매개변수 전달 방법입니다. 만약 지역 변수가 정적 변수가 아니라면, 부프로그램을 호출할 때 부프로그램에서 선언된 지역 변수를 위한 기억 공간을 할당해야 하고, 그 기억 공간에 지역 변수를 바인딩 하고, 호출된 부프로그램의 실행 상태를 저장해야 합니다.

또한 부프로그램을 호출하는 과정에서 프로그램의 제어권을 부프로그램으로 전달해야 하고, 부프로그램의 수행이 종료되면 그 제어권을 다시 적당한 장소로 제어권을 반환하는 과정도 마련해야 합니다. 만약 해당 프로그래밍 언어가 중첩된 부프로그램을 지원한다면, 호출된 부프로그램에 비지역 변수에 접근할 수 있는 방안도 마련해야 합니다.

부프로그램 반환에 필요한 과정은 호출에 요구되는 과정보다는 덜 복잡합니다. 부프로그램이 out mode이거나 inout mode이고 Pass by Copy로 구현되는 매개변수를 가진다면, 반환 과정의 첫 번째는 관련된 형식 매개변수의 지역 값을 실 매개변수로 옮겨주는 것입니다. 다음으로는 부프로그램의 지역 변수에 사용된 기억 공간을 해제하고, 비지역 참조에 사용되는 메커니즘을 해제합니다. 마지막으로, 제어권을 호출한 프로그램에게 다시 반환합니다.

먼저 매우 간단한 부프로그램을 구현해봅시다. 여기서 간단하다는 뜻은 중첩 부프로그램이 없고, 모든 지역 변수가 정적이라는 것을 의미합니다. 초기 Fortran 버전이 바로 이런 부프로그램을 갖는 언어입니다. 초기 Fortran 언어에서는 부프로그램이 재귀적으로 사용될 수 없었고, Fortran 77에서 비지역 변수에 대한 모든 참조는 COMMON을 통해 이루어졌습니다. 또한 부프로그램에 선언된 변수는 정적으로 할당되었습니다.

Fortran 77에서 부프로그램 호출은 이러한 과정을 갖고 있었습니다.

  1. 현재 프로그램 단위의 실행 상태를 저장
  2. 매개변수 전달 과정을 수행
  3. 반환 주소를 호출된 프로그램에게 전달
  4. 제어권을 호출된 프로그램에 전달

Fortran 77에서 부프로그램 반환은 이러한 과정을 갖고 있었습니다.

  1. Pass by Value Result 매개변수나 out mode 매개변수가 사용된다면, 해당 매개변수의 현재 값을 실 매개변수로 전달
  2. 부프로그램이 함수인 경우, 함수 (반환)값을 호출자가 접근할 수 있는 위치로 이동
  3. 호출자의 실행 상태를 복구
  4. 제어권을 호출자에게 전달

이러한 호출 및 반환 과정에는 다음에 대한 저장 공간이 필요합니다.

  • 호출자의 상태 정보
  • 매개변수
  • 반환 주소
  • 함수의 반환값
  • (필요한 경우) 부프로그램에서 사용되는 임시 기억 장소

그런데 호출 과정과 반환 과정을 호출자와 호출된 부프로그램에게 분배하는 것이 문제입니다. 다행히 간단한 부프로그램의 경우, 이것을 분배하는 것이 쉬운 편입니다. 호출에서의 과정은 1을 제외하고 호출자에서 수행되어야 합니다. 실행 상태를 저장하는 것은 호출자에서 저장할 수도 있고, 호출된 부프로그램에서 저장할 수도 있습니다. 반환에서는 두 번째 과정을 제외하고는 호출된 부프로그램에서 수행해야 합니다. 두 번째 과정은 마찬가지로 호출자에서 수행할 수도 있고, 호출된 부프로그램에서 수행할 수도 있습니다.

Fortran 77과 같은 간단한 부프로그램은 각각 고정된 크기의 두 부분으로 구성됩니다. 하나는 부프로그램을 위한 정적인 실제 코드이고 나머지 하나는 지역 변수와 호출/반환 작업을 하기 위핸 데이터 영역입니다. 간단한 부프로그램의 경우 둘 다 고정된 크기를 갖습니다.

부프로그램에서 코드가 아닌 부분은 부프로그램의 활성화(즉, 실행)에 관련된 부분이기 때문에 활성화 레코드(Activation Record)라고 합니다. Fortran 77의 경우에는 재귀를 지원하지 않기 때문에, 한번에 하나의 활성 부프로그램만 있을 수 있습니다. 따라서 부프로그램의 활성화 레코드는 단지 하나만 존재합니다. 게다가 간단한 부프로그램에서 활성화 레코드는 고정 크기이기 때문에, 정적으로 할당할 수 있습니다.

슬라이드에 나온 그림은 주프로그램(Main)과 두 개의 부프로그램 A, B로 이루어진 프로그램을 나타냅니다. 이러한 프로그램 구성은 컴파일러에 의해 전부 만들어지는 것은 아닙니다. 만약 독립적으로 컴파일이 수행되었다면 3개의 프로그램 단위는 각각 다른 날에 컴파일 되었을 수도 있습니다. 각각의 프로그램 단위가 컴파일 될 때, 외부 부프로그램의 참조 리스트와 더불어 기계어 코드가 파일에 작성됩니다. 따라서 슬라이드에 나온 그림은 운영체제의 일부인 링커(Linker)에 의해 통합됩니다. 링커가 주프로그램을 위해 호출되었을 때, 링커는 주프로그램에 참조된 부프로그램을 포함한 파일을 찾고, 그 파일들을 메모리에 적재합니다. 그 후, 링커는 주프로그램에 있는 부프로그램 호출의 목적지 주소를 부프로그램의 진입 주소로 설정합니다. 이러한 과정을 모든 부프로그램에 대해서 동일한 작업을 실시합니다.

이 과정을 슬라이드에 나온 구조에 빗대서 설명하면, 링커는 Main을 위해 호출된 후 부프로그램 A, B의 기계어 코드 프로그램과 활성화 레코드를 찾아 Main의 코드와 함께 메모리에 적재합니다. 그런 다음 A, B에 대한 호출과 A, B, Main에서 라이브러리 부프로그램에 대한 호출의 목적지 주소를 패치(Patch)합니다.

이제 스택 동적 지역 변수를 갖는 언어의 부프로그램을 구현하는 방법을 알아보겠습니다. 스택 동적 지역 변수의 가장 중요한 장점 중 하나는 재귀적 부프로그램을 지원한다는 것입니다. ALGOL과 그로부터 영향을 받은 언어들에서의 부프로그램 연결은 다음과 같은 이유로 간단한 부프로그램의 연결보다 훨씬 복잡합니다.

  • 매개변수를 전달하는 방법이 두 가지 이상입니다. 예를 들어, Modula-2에서는 Pass by Value와 Pass by Reference를 지원합니다.

  • 부프로그램에 선언된 변수가 동적으로 할당되는 경우가 있습니다.

  • 재귀는 여러 개의 부프로그램이 동시에 활성화될 수 있는 가능성을 추가합니다. 그렇기 때문에 활성화 레코드에는 여러 개의 인스턴스가 필요합니다. 각각의 활성화에는 반환 주소와 함께 형식 매개변수와 동적으로 할당된 지역 변수의 복사본이 필요합니다.

  • ALGOL과 그와 유사한 언어들에서는 정적 범위를 사용하여 비지역 변수에 대한 접근을 제공합니다. 이러한 비지역 변수에 대한 지원은 연결 과정의 일부로 들어가야만 합니다.

프로시저를 활성화하기 위해서는 프로시저에 대한 활성화 레코드 인스턴스를 동적으로 생성해야 합니다. 호출 및 반환 체계에서 마지막으로 호출된 부프로그램이 첫 번째로 종료되기 때문에 활성화 레코드 인스턴스는 스택으로 구현하는 것이 합리적입니다. 이 스택은 실행 시간(Run-time) 시스템의 일부이기 때문에 실행 시간 스택(Run-time Stack)이라고 부릅니다. 부프로그램이 재귀적이든, 그렇지 않든 모든 프로시저의 활성화는 스택에 활성화 레코드 인스턴스를 생성합니다.

다행히 대부분의 언어에서 주어진 부프로그램의 활성화 레코드 형식은 컴파일 시간에 알려집니다. 게다가, 대부분의 지역 데이터는 고정 크기이므로 활성화 레코드의 크기 또한 컴파일 시간에 알 수 있습니다. 그러나, Ada와 같이 지역 배역의 크기가 실 매개변수의 값에 영향을 받는 언어는 크기가 동적으로 정해질 수 있습니다. 그렇기 때문에 스택 동적 변수를 갖는 언어에서는 활성화 레코드가 동적으로 생성됩니다. 활성화 레코드의 형식은 활성화 레코드 인스턴스의 템플릿입니다. (지역 변수, 매개변수, 동적 링크, 반환 주소)

지역 변수는 활성화 레코드 내의 저장소로 바인딩됩니다. 정적 링크(=정적 범위 포인터)는 비지역 변수에 대한 접근에 사용되는 링크로써, 정적으로 상위에 있는 활성화 레코드 인스턴스를 가리킵니다. 동적 링크는 당연히 동적으로 상위에 있는 활성화 레코드 인스턴스를 가리킵니다. 그렇다면 동적 링크는 정적 영역을 갖는 언어에서 필요하지 않나 싶겠지만, 정적 영역을 갖는 경우 이 링크는 프로시저의 실행이 완료될 때 현재 활성화 레코드 인스턴스를 제거하는데 사용되고, 또 실행 시간 오류가 발생할 때 추적(Traceback) 정보를 제공하기 위해 사용됩니다. 동적 영역 언어라면 당연히 동적으로 비지역 변수에 접근하기 위해 사용됩니다.

반환 주소는 코드 세그먼트와 오프셋으로 이루어져 있으며, 실 매개변수는 호출자가 제공하는 값이나 주소를 통해 접근합니다.

다음 예제를 통해 스택 동적 변수를 갖는 부프로그램이 어떤 활성화 레코드를 갖는지 알아보겠습니다. 왼쪽의 코드는 Pascal 언어로 만들어진 프로시저입니다. 가장 먼저 프로시저의 매개변수를 확인해 보면, total은 var로 선언되었기 때문에 Pass by Reference 매개변수이고, part라는 변수는 그렇지 않기 때문에 Pass by Value 입니다. 따라서 두 개의 매개변수가 스택에 쌓일 때, part는 그 값이, total은 그 주소가 저장된 것을 확인할 수 있습니다.

그 이후에는 프로시저 내에서 발생하는 지역 변수가 스택에 쌓입니다. 교재와는 순서가 좀 다른데, 교재에서는 list[1]부터 list[5]까지 쌓인 후 sum의 변수가 스택에 저장되었지만, 여기서는 그 반대로 저장이 되었습니다. 다만 그 순서는 크게 중요하지 않은 것 같습니다. 다음으로 반환 주소와 정적 링크, 동적 링크가 차례로 저장되는 것을 확인할 수 있습니다.

지난 장에서, 부프로그램이 호출될 때부터 실행이 끝날 때 활성 상태라는 것을 배웠습니다. 따라서 부프로그램의 실행이 끝난 이후에는 활성화 레코드가 더 이상 의미가 없습니다. 따라서 그 이후에는 활성화 레코드가 해제됩니다.

또한 예제와 같이 매개변수 항상 스택에 전달되는 것은 아닙니다. RISC에서 동작하는 컴파일러 중 일부분은 매개변수를 레지스터에 전달하기도 합니다. 왜냐하면 RISC는 CISC보다 더 많은 레지스터를 갖고 있기 때문입니다. 그러나 여기에서 그것까지는 고려하지 않고, 매개변수는 항상 스택에 저장된다고 가정하겠습니다.

다음은 본격적으로 재귀가 없고, 비지역 변수에 대한 참조가 없는 예제에서 활성화 레코드를 만들어보겠습니다.

역시 코드는 왼쪽과 같이 주어졌습니다. 간단하게 보시면, MAIN_1 주프로그램에서 부프로그램 B를 호출하고, 부프로그램 B에서는 부프로그램 A를 호출합니다. 그리고 부프로그램 A에서는 C를 호출합니다. 구조상으로 부프로그램 C는 부프로그램 A 안에 있네요. 이 상황에서, 슬라이드와 같이 지점 1, 2, 3에서 각각 활성화 레코드를 그려보겠습니다.

지점 1에서는 프로시저 MAIN_1과 B가 활성화되어있는 상태입니다. 따라서 활성화 레코드에는 MAIN_1과 B만 있어야 합니다. 따라서 가장 아래에는 MAIN_1에서 선언된 지역 변수인 P가 스택 가장 아래에 위치합니다. 그 다음에 스택에 쌓이는 것은 프로시저 B의 매개변수 R입니다. 다음으로는 프로시저 B의 지역 변수인 S, T가 스택에 쌓입니다. 그 후, 반환 주소, 정적 링크, 동적 링크가 차례대로 스택에 쌓이게 됩니다.

다음은 지점 2에서의 스택 상황을 확인해보겠습니다. 지점 2에서는 프로시저 B가 프로시저 A를 호출한 상황입니다. 이 때 활성화된 프로시저는 MAIN_1, B, A 입니다. 따라서, 활성화 레코드에는 이전에 쌓였던 MAIN_1와 B의 데이터가 그대로 남아있습니다. 여기에 프로시저 A의 활성화 레코드가 그 위에 쌓이게 됩니다. 가장 먼저 프로시저 A의 매개변수인 X가 쌓이고, 그 위로 프로시저 A의 지역 변수인 Y, 그 위에는 반환 주소와 정적 링크, 동적 링크 순서대로 스택에 쌓이게 됩니다.

마지막으로 지점 3에서의 스택 상황을 확인하겠습니다. 이 때 활성화된 프로시저는 MAIN_1, B, A, C입니다. 따라서 활성화 레코드에는 이전에 쌓였던 MAIN_1, B, A의 데이터가 그대로 남아있습니다. 여기에 프로시저 C의 활성화 레코드가 그 위에 쌓이게 됩니다. 가장 먼저 프로시저 C의 매개변수인 Q가 쌓입니다. 그러나 프로시저 C의 지역 변수는 없기 때문에 그 다음에는 바로 반환 주소와 정적 링크, 동적 링크 순서대로 스택에 쌓이게 됩니다.

이 예제에서 지점 1 -> 2 -> 3의 스택이 계속 쌓이기만 하는 것을 보고 “활성화 레코드는 스택에 계속 쌓이기만 하는구나”라고 착각을 하실 수도 있는데, 이것은 그러한 이유 때문이 아닙니다. 이 예제에서 지점 3에 도달할 때까지 비활성화되는 프로시저가 없기 때문에 스택에 계속 쌓이기만 하는 것입니다. 만약 지점 2에서 3으로 갈 때 프로시저 A가 비활성화된다면, 지점 3에서 A의 활성화 레코드는 스택에서 해제되고, 그 자리에 프로시저 C의 활성화 레코드가 위치하게 됩니다.

이러한 활성화 레코드에서 특정 시간에 스택에 존재하는 동적 링크의 모음을 동적 체인(Dynamic Chain), 또는 호출 체인(Call Chain)이라고 합니다. 동적 체인은 실행이 현재 위치(활성화 레코드 스택의 꼭대기에 있는 부프로그램의 위치)에 어떻게 도달했는지에 대한 동적 기록을 나타냅니다.

지역 변수에 대한 참조는 코드에서 활성화 레코드의 시작 지점으로부터 오프셋으로 나타내는데, 이것을 지역 오프셋(Local Offset)이라고 합니다. 활성화 레코드에 있는 변수의 지역 오프셋은 활성화 레코드와 관련된 부프로그램에서 선언된 변수의 순서, 타입, 크기를 사용하여 컴파일 시간에 결정됩니다.

다음은 재귀를 사용하여 팩토리얼(Factorial)을 계산하는 프로그램에 대해 활성화 레코드 스택을 구해보겠습니다. 먼저, 코드의 구조를 살펴보면 TEST라는 주프로그램에서 FACTORIAL 이라는 함수를 호출합니다. FACTORIAL 함수에서는 특정 조건에 다다를 때까지 계속 자기 자신을 호출하는 구조입니다. 이 예제는 이전과 달리 하나의 함수를 계속 호출하는 구조이기 때문에 활성화 레코드의 포멧은 동일합니다. (슬라이드의 오른쪽 그림) FACTORIAL 함수는 지역 변수가 없지만, 반환 값이 있기 때문에 함수 값이 활성화 레코드에 추가됩니다. 이러한 구조에서, 지점 1, 2, 3에서의 활성화 레코드 스택이 어떻게 나오는지 알아보겠습니다.

먼저 이 그림들은 각각 첫 번째, 두 번째, 세 번째 호출이 되었을 때 지점 1에서의 활성화 레코드 스택을 나타낸 이미지입니다. 왜 동일한 지점의 활성화 레코드 스택이 3개 나오냐면, 주프로그램 TEST에서 FACTORIAL(3)으로 호출했기 때문에 이 함수가 3번 호출되기 때문입니다. 따라서 FACTORIAL 함수가 3번 호출될 동안 스택에서는 아무것도 해제되지 않고 계속 쌓이기만 합니다.

스택 맨 아래에는 당연히 주프로그램 TEST의 지역 변수인 VALUE가 저장되어 있고, 그 위에는 FACTORIAL 함수의 활성화 레코드가 쌓입니다. 이 때, 반환 주소는 첫 번째, 두 번째, 세 번째가 모두 달라집니다. 첫 번째 FACTORIAL 함수의 반환 주소는 주프로그램인 TEST가 되지만, 두 번째 FACTORIAL 함수의 반환 주소는 첫 번째 호출한 FACTORIAL 함수가 됩니다. 마찬가지로 세 번째 FACTORIAL 함수의 반환 주소는 두 번째 FACTORIAL 함수가 됩니다. 이미지 상으로 두 번째와 세 번째의 반환 주소가 동일해보이지만, 의미상으로는 다르다는 것을 주의해주세요.

이 그림의 4~6은 첫 번째, 두 번째, 세 번째 호출이 되었을 때 지점 2에서의 활성화 레코드 스택을 나타낸 이미지입니다. 지점 2는 특이하게 마지막에 호출된 FACTORIAL 함수에서 가장 먼저 도달합니다. 그렇기 때문에 첫 번째로 지점 2에 도착할 때 활성화 레코드 스택은 3개의 FACTORIAL 함수의 활성화 레코드가 쌓인 상태입니다. 지점 1에서는 세 번째 호출까지 함수 값을 알 수 없었지만, 지점 2는 END 시점이기 때문에 이 지점에서 함수 값 또한 1로 계산이 끝난 상황입니다.

두 번째 도착하는 지점 2에서는 세 번째 호출된 FACTORIAL이 종료된 상황이기 때문에 활성화 레코드 스택에서 제거되었습니다. 이 때도 FACTORIAL의 함수 값이 계산된 상황이므로 함수 값에 2가 저장됩니다. 마찬가지로 세 번째 도착하는 지점 2에서는 두 번째 호출된 FACTORIAL이 종료된 상황이기 때문에 활성화 레코드 스택에서 제거되었습니다. 물론 FACTORIAL의 함수 값이 계산 가능한 지점이므로 함수 값에 6이 저장됩니다.

마지막으로 VALUE의 값을 출력하는 지점 3에서는 모든 FACTORIAL 함수가 종료된 시점이므로 TEST의 지역 변수인 VALUE만 남아있게 되는 것입니다.

C 언어 기반이 아닌 정적 영역 언어는 스택 동적 지역 변수를 사용할 때 부프로그램이 중첩되는 것을 허용하기도 합니다. 이러한 언어의 대표적인 예시는 Ada, Python, JavaScript 등이 있습니다.

그런데 이전 슬라이드에서 보았듯이, 비지역으로 접근할 수 있는 모든 변수는 활성화 레코드 스택에 존재합니다. 여기서 중첩된 부프로그램을 갖는 정적 영역 언어에서 비지역 변수를 참조하기 위해서는 두 단계의 과정이 필요합니다. 첫 번째 단계는 스택에서 그 변수가 할당된 활성화 레코드를 찾는 것입니다. 두 번째 단계는 변수의 지역 오프셋을 사용하여 변수에 접근하는 것입니다.

하지만 원하는 변수를 갖고 있는 정확한 활성화 레코드를 찾는 것은 어렵습니다. 지정된 부프로그램에서는 정적으로 상위 범위에 선언된 변수만 비지역으로 접근할 수 있습니다. 그런데 모든 정적 상위에 있는 활성화 레코드는 중첩된 프로시저에 의해 해당 인스턴스의 변수가 참조될 때 스택에 항상 존재합니다. 즉, 모든 정적 상위 부프로그램이 활성화일 때만 프로시저를 호출할 수 있습니다. 만약 어떤 특정한 정적 상위 프로그램이 활성화 상태가 아니라면, 그 지역 변수는 기억 공간에 바인딩되지 않았을 것이기 때문에 접근을 허용하는 것의 무의미합니다.

비지역 참조에서 올바른 선언은 영역을 살펴볼 때 가장 먼저 발견되는 것입니다. (즉, 가장 가깝게 중첩된 첫 번째 선언) 따라서 비지역 참조를 지원하기 위해서는 스택에서 해당 정적 상위에 해당하는 모든 활성화 레코드를 찾을 수 있어야 합니다. 이것을 구현하는 방법은 정적 체인(Static Chain)과 디스플레이(Display)라는 것이 있습니다. 이제부터 이 두 가지 방법에 대해 알아보겠습니다.

중첩 부프로그램이 가능한 언어에서 정적 영역을 구현하는 가장 일반적인 방법은 정적 체인입니다. 이 방법에서는 정적 링크라고 불리는 새로운 포인터가 활성화 레코드에 추가됩니다. 정적 링크는 비지역 변수에 접근하기 위해 사용되며, 정적 체인은 활성화 레코드를 연결하는 정적 링크의 체인입니다. 예를 들어, 어떤 프로시저 P가 실행되는 중에, P로 인해 생성된 활성화 레코드의 정적 링크는 P의 정적 상위 프로그램의 활성화 레코드를 가리킵니다. 따라서 정적 체인은 정적인 부모 프로그램을 시작으로, 실행 중인 부프로그램의 모든 정적 상위 프로그램을 연결합니다.

만약 비지역 변수에 대한 참조가 발생한다면, 그 변수를 포함하는 정적 상위 프로그램의 활성화 레코드를 찾을 때까지 정적 체인을 탐색함으로써 찾을 수 있습니다.

그런데 이렇게 영역이 중첩되는 것은 컴파일 시간에 알려지기 때문에 컴파일러는 이러한 참조가 지역이 아니라는 것 뿐만 아니라, 실제로 비지역 개체를 포함하는 활성화 레코드에 도달하는 데 필요한 정적 체인의 길이도 알 수 있습니다. 그러한 길이를 정적 깊이(Static Depth)라고 합니다. 정적 깊이는 정적 영역이 가장 바깥쪽 영역으로부터 얼마나 깊게 중첩되어 있는지를 나타내는 정수값입니다.

변수 X의 비지역 참조를 위한 정확한 활성화 레코드에 도착하는데 필요한 체인의 길이를 중첩 깊이(Nesting Depth)라고 합니다. 중첩 깊이는 X를 참조하는 부프로그램의 정적 깊이와 X가 선언된 부프로그램의 정적 깊이의 차이입니다. 중첩 깊이를 체인 오프셋(Chain Offset)이라고도 부릅니다. 실제로 참조할 때는 정수 순서쌍 (체인 오프셋, 지역 오프셋)으로 표시됩니다.

예를 들어, 슬라이드에 나온 코드에서는 A - B - C 순서로 중첩이 되어 있습니다. 먼저 각 프로시저의 정적 깊이를 계산해보면, 가장 바깥에 있는 A는 0, B는 1, C는 2로 계산할 수 있습니다. 만약 프로시저 C에서 프로시저 A에 있는 비지역 변수를 참조하고 싶다면 중첩 깊이를 계산해야 하는데, 이 때의 중첩 깊이는 C의 정적 깊이(2) - A의 정적 깊이(0) = 2가 됩니다.

이제 좀더 복잡한 프로그램을 가지고 참조를 위한 깊이를 계산해 보겠습니다. 이 프로그램은 MAIN_2라는 주프로그램에서 부프로그램 BIGSUB를 호출하고, BIGSUB는 SUB2 부프로그램을 호출합니다. SUB2는 SUB3 부프로그램을 호출하고, SUB3은 SUB1 부프로그램을 호출합니다. 그러나 프로그램의 구조는 호출과 일치하지 않음을 주의해주시기 바랍니다.

먼저 SUB1의 A := B + C; 지점에서 A, B, C를 접근하기 위한 중첩 깊이를 계산해보겠습니다. A는 SUB1 내에서 정의되어 있기 때문에 당연히 0이 됩니다. B와 C는 바로 위의 BIGSUB에서 정의되어 있기 때문에 1이 됨을 쉽게 계산할 수 있습니다. 그리고 이들의 지역 오프셋을 계산하기 위해서는 활성화 레코드를 먼저 계산해야 합니다. 활성화 레코드를 계산하는 방법은 이전에 설명했기 때문에 생략하겠습니다. 활성화 레코드의 0, 1, 2는 각각 동적 링크, 정적 링크, 반환 주소를 저장하기 때문에 지역 변수는 그 다음부터 저장됩니다. BIGSUB는 A, B, C 순서대로 저장되었기 때문에 각각 3, 4, 5에 저장됨을 알 수 있습니다. 따라서 A의 참조쌍은 (0, 3), B의 참조쌍은 (1, 4), C의 참조쌍은 (1, 5)가 됨을 알 수 있습니다.

마찬가지로 SUB3의 E := B + A; 지점에서 E, B, A의 참조쌍을 계산해보겠습니다. E는 SUB3의 지역 변수이기 때문에 중첩 깊이가 0이 됩니다. B는 SUB2의 B를 참조하기 때문에 중첩 깊이가 1이 됩니다. A는 BIGSUB의 A를 참조하기 때문에 중첩 깊이가 2가 됩니다. 이제 지역 오프셋을 계산해보면, SUB3은 지역 변수로 C, E를 갖고 있습니다. 따라서 C의 지역 오프셋이 3, E의 지역 오프셋이 4가 됩니다. SUB2는 지역 변수로 B, E를 가지고 있으므로 B의 지역 오프셋은 3, BIGSUB는 지역 변수로 A, B, C를 가지고 있기 때문에 지역 오프셋은 3이 됩니다. 따라서 E의 참조쌍은 (0, 4), B는 (1, 3), A는 (2, 3)이 됩니다.

마지막으로 SUB2의 A := D + E; 지점에서 A, D, E의 참조쌍을 계산해보겠습니다. A는 BIGSUB의 A를 참조하므로 참조쌍이 (1, 3)이 됩니다. 그런데 D는 SUB2의 상위 프로시저인 BIGSUB에 선언되어 있지 않고, 그보다 상위 프로시저인 MAIN_2에도 선언되어 있지 않습니다. 따라서 D는 선언되어 있지 않은 변수이므로 Error가 발생합니다. E는 SUB2의 지역 변수이므로 (0, 4)가 됨을 쉽게 계산할 수 있습니다.

이전 슬라이드에 제시된 프로그램의 구조를 토대로 활성화 레코드를 나타낸 모습입니다. 이 그림의 핵심은 정적 링크과 동적 링크가 어떻게 연결되어 있는지 입니다. 정적 링크는 프로그램 구조상으로 자신의 상위 프로시저를 가리킵니다. 예를 들어, BIGSUB의 정적 링크는 MAIN_2를 가리키고, SUB2의 정적 링크는 BIGSUB를 가리키는 것을 확인할 수 있습니다.

동적 링크는 자신을 호출한 프로시저를 가리킵니다. 예를 들어, SUB1의 동적 링크는 SUB3을 가리키고, SUB3의 동적 링크는 SUB2를 가리킵니다.

그렇다면, 프로그램 실행 중에 정적 체인이 어떻게 유지되는 것일까요? 정적 체인은 부프로그램이 호출되거나 반환될 때마다 변경되므로, 그 때마다 수정되어야 합니다. 부프로그램이 종료될 때는 해당 부프로그램의 활성화 레코드가 스택에서 제거되는데, 그 활성화 레코드가 가리키는 포인터는, 활성화 레코드가 제거될 때 같이 해제되므로 신경을 쓸 필요가 없습니다.

그러나 새로운 부프로그램이 호출될 때는 문제가 복잡해집니다. 정확한 자신의 상위 프로시저를 컴파일 시간에 알 수 있다고 하더라도, 호출 시에는 그 상위 프로시저의 활성화 레코드가 스택 어디에 있을지는 모르기 때문입니다. 이 문제를 해결하는데는 두 가지 방법이 있습니다.

  1. 첫 번째 방법은 실행 시간에 상위 영역의 첫 번째 항목을 찾을 때까지 동적 체인의 활성화 레코드를 탐색하는 것입니다.

  2. 두 번째 방법은 컴파일 시간에 호출자와 호출된 프로그램을 선언한 프로시저 사이의 중첩 깊이를 계산하고, 호출이 발생할 때, 호출된 프로시저의 활성화 레코드의 정적 링크를 호출자의 정적 체인에서 컴파일러 시간에 계산된 중첩 깊이와 동일한 링크 수 만큼 이동하여 결정하는 것입니다.

두 번째 방법에 대해 좀 더 자세히 설명하자면, 이전 슬라이드의 스택 상황에서 SUB3이 SUB1을 호출하는 때를 생각해봅시다. 컴파일러는 SUB3의 중첩 깊이가 SUB1을 선언한 프로시저인 BIGSUB의 2단계 안쪽이라는 것을 알 수 있습니다. 따라서 SUB3이 SUB1을 호출할 때, 활성화 레코드에서 정적 체인의 두 번째 링크가 가리키는 활성화 레코드를 가리키도록 설정하는 것입니다. (SUB3 -> SUB2 -> BIGSUB) 따라서 SUB1의 활성화 레코드에서 정적 링크는 BIGSUB를 가리키도록 설정되는 것입니다.

정적 체인의 단점은 비지역 변수에 참조하는 비용이 지역 변수의 참조보다 크다는 것입니다. 비지역 변수를 참조할 때마다 해당 변수가 선언이 된 영역을 찾기 위해서 정적 체인의 링크를 따라가야합니다. 해당 비지역 변수가 현재 위치에서 멀면 멀 수록 그 링크를 많이 따라가야 합니다. 다행히 실제 그렇게까지 먼 비지역 변수를 참조하는 경우는 드물지만, 정적 체인의 진짜 단점은 시간이 중요한 프로그램(Time Critical Program)을 작업하는 경우 프로그래머가 비지역 변수를 참조할 때 그 비용을 추정하는 것이 어렵다는 것입니다. 왜냐하면 각각의 참조의 비용은 중첩 깊이에 따라 달라지기 때문입니다. 코드가 수정될 때마다 중첩의 깊이가 변화할 수 있고, 그로 인해 코드를 변경하기 전과 변경한 후의 시간이 얼마나 차이가 날지 계산하기 어려워지는 문제가 있습니다.

정적 체인의 대안 중 하나는 디스플레이(Display)입니다. 이 방법은 정적 링크를 활성화 레코드에 저장하지 않고, 디스플레이라는 단일 배열에 저장합니다. 특정 시간에서 디스플레이의 내용은 접근 가능한 활성화 레코드 인스턴스의 주소 목록입니다. 이것은 각각의 활성 범위에 대해 하나씩 나타나며, 중첩된 순서대로 표시됩니다.

비지역 변수의 참조 쌍은 (디스플레이 오프셋, 지역 오프셋)으로 표현합니다.

디스플레이에 저장된 활성화 레코드에 대한 링크는 디스플레이 오프셋이라는 정적으로 계산된 값을 사용하여 찾습니다. 활성화 레코드 내의 지역 오프셋은 정적 체인에서와 동일한 용도로 사용됩니다. 일반적으로 디스플레이에서 $k$라는 위치에 있는 포인터는 정적 깊이가 $k$인 프로시저에 대한 활성화 레코드를 가리킵니다.

만약 새로운 프로시저가 호출되거나 기존의 프로시저가 종료될 때 디스플레이를 수정해야 한다면 다음과 같은 과정이 발생합니다. 정적 길이가 $k$인 프로시저 P의 호출이 발생할 때, 새 활성화 레코드에 디스플레이 $k$ 위치에 있는 포인터 복사본을 저장합니다. 그리고 디스플레이에서 $k$ 위치에 P의 활성화 레코드에 대한 링크를 배치합니다. 프로시저 종료 시, 종료된 부프로그램의 활성화 레코드에 저장된 포인터가 디스플레이에 다시 배치됩니다.

디스플레이를 이해하기 위해 예제를 하나 풀어보겠습니다. 프로시저 Q가 프로시저 P를 호출하는 상황이라고 가정해봅시다. Psd를 P의 정적 깊이, Qsd를 Q의 정적 깊이라고 정의하겠습니다. 그렇다면 가능한 경우는 1) Qsd = Psd, 2) Qsd < Psd, 3) Qsd > Psd 이렇게 3가지가 나오게 됩니다.

프로그램 구조는 슬라이드 왼쪽에 나와있는 것으로 가정하겠습니다. 먼저 SUB2에서 SUB1을 호출할 때, 이 두 프로시저는 같은 정적 깊이를 갖는 경우입니다. 그렇다면 디스플레이 0번째 인덱스는 정적 깊이가 0인 MAIN_3을 가리키게 되고, 1번째 인덱스는 정적 깊이가 1인 BIGSUB를 가리키게 됩니다. SUB1을 호출하기 전에는 2번째 인덱스는 정적 깊이가 2인 SUB2를 가리키고 있습니다. 그런데 이 상황에서 SUB1을 호출한다면, SUB1은 SUB2와 마찬가지로 정적 깊이가 2이므로, 디스플레이의 2번째 인덱스가 SUB1을 가리키도록 수정됩니다.

두 번째는 SUB2가 SUB3을 호출하는 상황을 확인해보겠습니다. 이 경우에는 SUB3의 정적 깊이가 SUB2보다 깊은 경우입니다. 이 경우는 너무 간단합니다. 그냥 디스플레이의 다음 인덱스가 새로 호출된 SUB3을 가리키도록 설정하면 끝나기 때문입니다.

이번에는 프로그램 구조를 조금 바꾸었습니다. 호출 순서는 MAIN_4 -> BIGSUB -> SUB2 -> SUB3 -> SUB1 -> SUB4 입니다. SUB3이 호출될 때 까지는 이전의 상황과 마찬가지이므로 전혀 문제가 없습니다. 문제는 SUB1이 호출될 때부터 시작됩니다. SUB1은 SUB3보다 정적 깊이가 낮은 프로시저입니다. 따라서 디스플레이의 2번째 인덱스는 SUB1을 가리키게 됩니다. 문제는 2번째 인덱스가 스택의 가장 윗부분을 가리키게 된다는 것입니다. 따라서 디스플레이의 3번째 인덱스가 SUB3을 가리키고 있을 지라도, 컴파일러는 이것을 비활성된 것으로 인식합니다.

이후에 SUB4가 호출될 때는 이전과 동일합니다. SUB4는 SUB1보다 정적 깊이가 깊은 곳에 위치해있기 때문에, 디스플레이의 3번째 인덱스가 SUB4를 가리키게 설정하면 됩니다.

이번에는 SUB1만 호출되고 끝나는 상황이라고 가정해봅시다. 이전 슬라이드에서는 SUB1이 호출될 때 문제가 생겼었지만, 결국 SUB4로 인해 최종 디스플레이 배열은 문제가 없이 생성되었습니다. 그러나 이제는 SUB1이 선언되고 끝났기 때문에, 디스플레이의 3번째 인덱스가 SUB3을 가리키고 있음에도 이것이 활성화되지 않는 문제가 발생합니다. 하지만 정적 영역 언어를 기준으로 보았을 때, SUB1에서 SUB3의 지역 변수를 참조할 수 없으니 이것은 옮게 된 비활성화입니다.

그럼 디스플레이를 구현하는 방법이 어떻게 되는지 알아보겠습니다. 먼저 디스플레이 배열의 크기를 정하는 것은 간단합니다. 컴파일러가 부프로그램에 대한 최대 정적 깊이를 알 수 있기 때문입니다. 따라서 디스플레이 배열은 실행 시간에 정적 배열로 메모리에 저장됩니다. 만약 컴퓨터가 메모리 위치에 따른 간접 주소 지정을 하는 경우, 비지역 접근은 지역 접근보다 메모리 사이클이 한 단계 증가합니다. 만약 디스플레이 배열을 레지스터에 위치시킨다면 추가적인 메모리 사이클이 필요하지 않습니다.

정적 체인과 디스플레이를 비교해보겠습니다. 속도 면에서 보자면, 정적 수준이 한 단계 차이가 나는 경우 정적 체인이 디스플레이보다 빠릅니다. 왜냐하면 디스플레이가 레지스터에 저장되는 경우가 아니라면 간접 주소 지정을 통해 접근을 하게 되는데, 이 경우 비지역 변수에 대한 참조 과정이 한 단계 증가하기 때문입니다.

그러나 두 단계 이상의 정적 수준에 있는 비지역 변수에 대한 참조는 정적 체인보다 빠릅니다. 정적 체인은 정적 수준의 깊이가 증가할수록 속도가 느려지지만, 디스플레이는 모든 단계의 비지역 변수 참조 속도가 동일하기 때문입니다.

전체적으로 비교하자면, 정적 수준이 깊은 비지역 변수에 대한 참조가 많은 경우에는 디스플레이가 더 좋고, 그렇지 않은 경우에는 정적 체인이 더 좋습니다. 그리고 사실 일반적으로 정적 수준이 깊은 비지역 변수를 참조하는 일은 생각보다 많지 않기 때문에, 정적 체인이 더 좋다고 말할 수 있습니다. 사실 일반적인 정적 중첩은 3보다 작습니다.

5장에서 C 기반 언어들은 블록(Block)라는 지역 영역을 선언할 수 있다고 배웠습니다. 블록은 복합문(Compound Statement)과 데이터 정의(Data Declaration)이 결합된 구조입니다. 여기에서는 블록의 구현 방법에 대해서만 논의하도록 하겠습니다.

첫 번째 구현 방법은 블록을 매개변수가 없는 부프로그램으로 취급을 하는 것입니다. 이 경우 직전에 배운 정적 체인이나 디스플레이를 이용하여 간단하게 구현할 수 있습니다. 물론 블록을 부프로그램으로 취급을 하게 되면 그 만큼 정적 중첩이 더 많이 쌓이고, 그로 인해 디스플레이의 경우에는 배열의 사이즈가 커지는 단점이 있습니다.

두 번째 방법은 블록 변수에 필요한 공간을 활성화 레코드에 같이 할당하는 것입니다. 이것은 블록 변수를 위해 요구되는 기억 장소가 정적으로 계산될 수 있기 때문에 사용할 수 있는 방법입니다. 이 방법을 사용할 경우, 일반적으로 블록 변수를 지역 변수 다음 위치에 배치합니다.

슬라이드에 나온 코드에서는 b, g가 차지하는 영역과 a, f가 차지하는 영역이 서로 중복되어 있습니다. 이것은 a, b, c를 가지고 있는 블록은 f, g가 있는 블록 시점에서는 이미 종료되었기 때문입니다.

마지막으로는 동적 영역을 구현하는 방법에 대해 알아보겠습니다. 동적 영역을 구현하는 방법은 크게 깊은 접근(Deep Access)과 얕은 접근(Shallow Access)이 있습니다. 주의할 점은 이것들이 이전에 배웠던 깊은 바인딩과 얕은 바인딩과는 전혀 다른 이야기라는 것입니다.

동적 영역에서 지역 변수가 스택 동적 변수이고 활성화 레코드에 포함되어 있다면, 비지역 변수의 참조는 가장 최근에 활성화된 부프로그램부터 시작해서 현재 활성화 중인 다른 부프로그램의 활성화 레코드를 탐색하면서 해결할 수 있습니다. 이 개념은 정적 체인 대신 동적 체인을 사용한다는 것만 제외하면 정적 영역에서 비지역 변수에 접근하는 것과 유사합니다. 동적 체인은 활성화된 역순으로 스택을 탐험하는데, 스택의 가장 위부터 아래로 탐색해나가기 때문에 이 방법을 깊은 접근이라고 부릅니다.

정적 영역과는 달리, 동적 영역 언어에서는 접근에 필요한 체인의 길이를 컴파일 타임에 결정할 수 있는 방법이 없습니다. 그렇기 때문에 동적 영역 언어는 정적 영역 언어보다 속도가 느립니다. 게다가 정적 영역 언어에서는 변수의 이름을 저장하지 않고 값만 저장해도 상관이 없었지만, 동적 영역 언어를 구현할 때는 활성화 레코드에 검색을 위해 변수 이름을 저장해두어야 합니다.

슬라이드에 나온 코드 예제는 가장 최근에 활성화된 부프로그램인 C에서 x := u + v; 명령어를 수행하려고 합니다. 이 때, 변수 x는 C의 지역 변수이기 때문에 탐색이 필요 없습니다. 그러나 u와 v는 C의 지역 변수가 아니기 때문에 활성화 레코드를 탐색해야 합니다. 활성화 레코드 스택을 보면 C 이전에 활성화된 부프로그램은 B입니다. B에 u와 v가 저장되어 있는지 확인해야 하는데, 이것을 위해서는 변수 이름을 비교해보아야 합니다. B에도 u와 v가 없으니 계속 링크를 타고 올라가야 하고, 변수의 이름을 비교해보면서 u와 v를 찾는 과정을 반복합니다.

다음은 동적 영역을 구현하는 두 번째 방법인 얕은 접근입니다. 얕은 접근 방법에서는 부프로그램의 지역 변수가 활성화 레코드에 포함되어 있지 않습니다. 이 방법은 전체 프로그램에서 각각의 변수에 따라 개별적인 스택을 갖습니다. 만약 부프로그램이 활성화될 때 새로운 이름의 변수가 선언된다면, 그 이름으로 새로운 스택이 생성됩니다. 만약 기존에 있는 변수라면, 부프로그램의 이름에 해당하는 셀이 그 값과 함께 스택에 추가됩니다. 동적 영역 언어에서 비지역 변수에 접근할 때는 가장 최근에 활성화된 부프로그램의 변수를 가지게 되는데, 얕은 접근의 구조상 각 변수의 스택에 가장 위에 있는 셀은 가장 최근에 활성화된 부프로그램의 변수입니다. 즉, 비지역 변수에 접근할 때는 항상 스택의 맨 위에 있는 셀을 참조하면 됩니다.

얕은 접근 방법은 그 구조에서 예상할 수 있다시피 비지역 변수에 대한 참조는 매우 빠릅니다. 그러나 부프로그램에 진입하거나 종료할 때마다 변수에 대한 스택이 변동되므로, 스택을 유지하는 비용이 크다는 단점이 있습니다. 슬라이드에 나온 스택 그림은 이전 슬라이드에서의 깊은 접근에서 다루었던 예제 코드와 동일한 코드를 사용했을 때를 나타낸 모습입니다.

슬라이드에 나와있지 않지만 얕은 접근이 구현 방법은 이것 말고도 있습니다. 예를 들어, SNOBOL 언어는 변수에 이름에 하나의 장소를 할당하는 중앙 테이블을 사용하고 있습니다. 각각의 항목은 변수가 현재 어느 부프로그램에 바인딩이 되어 있는지 활성(Active) 비트를 가지고 있습니다. 변수에 접근할 때는 중앙 테이블의 오프셋을 이용합니다. 이 오프셋은 정적이기 때문에 접근이 빠르다는 장점이 있습니다.

또한 각 변수의 최신 값만 저장하는 단일 셀을 가지는 테이블을 구현하는 방법도 있습니다. 이 방법은 최소한의 오버헤드만 가진다는 장점이 있습니다.

동적 영역 언어를 구현할 때 깊은 접근과 얕은 접근 중 어느 방법을 사용할 지는 부프로그램 호출과 비지역 변수를 참조를 어느 정도로 하는 지에 따라 달려 있습니다. 깊은 접근 방법은 부프로그램이 호출되거나 해제될 때 속도가 빠르지만, 참조에 대한 비용이 크고, 얕은 접근 방법은 그 반대로 참조는 효율적이지만, 부프로그램이 호출되거나 해제될 때 비효율적입니다.

10장의 내용은 여기까지입니다. 읽어주셔서 감사합니다!

Leave a comment