프로그램은 서브루틴을 단위로 하는 계층 구조로 볼 수 있다. 서브루틴 호출의 제어 메커니즘은 '복사' 규칙으로 설명할 수 있는데, 즉, 서브루틴 호출 문장의 효과는 서브루틴 본문의 복사본으로 호출 문장을 대체하고 (적절하게 매개변수와 충돌하는 식별자를 대체함으로써) 같은 결과를 얻을 수 있다.
이 관점에서 서브루틴 호출은 프로그램의 여러 위치에서 동일하거나 거의 동일한 문장을 복사할 필요가 없는 제어 구조로 볼 수 있다. 그러나 복사 규칙에 따르면, 프로그램 실행 중 어느 시점에서도 한 서브루틴을 동시에 여러 번 호출할 수 없다.
완전한 프로그램 실행 모델을 먼저 설정해야 한다.
일반적으로 특정 서브루틴 문장이 실행된다기보다는 서브루틴의 활성화 레코드 내에서 특정 문장이 실행된다고 말한다.
프로그램 실행 지점을 추적하기 위해 두 가지 데이터, 즉 두 시스템 정의 포인터 변수에 대한 저장 공간이 필요하다.
현재 명령어 포인터 CIP는 현재 하드웨어나 소프트웨어 인터프리터가 실행 중인 명령어를 가리킨다.
현재 환경 포인터 CEP는, 동일한 서브루틴의 모든 활성화가 동일한 코드 세그먼트를 사용하기 때문에 현재 명령어만으로는 충분하지 않으며, 서브루틴의 참조 환경을 나타내는 활성화 레코드를 가리키는 포인터(따라서 환경 포인터라고 함)가 필요하기에 존재한다.
일반적으로 호출 시 CIP와 CEP를 호출된 서브루틴의 활성화 레코드에 저장하고, 활성화 레코드에는 시스템 정의 데이터 객체인 반환 지점(두 포인터 값을 저장하는 곳)이 포함된다.
서브루틴 B가 시작될때의 상태다.
call 호출을 만날 때마다, 이전의 (ip, ep)를 활성화 레코드의 반환 지점에 저장하고, 새로운 (ip, ep)를 CIP, CEP에 할당하여 제어를 전환한다.
반환 문장을 만나면, 이전의 (ip, ep)를 가져와 CIP, CEP를 재설정하고 제어권을 반환한다.
프로그램을 작성할 때, 실행해야 할 연산과 그 순서는 일반적으로 알고 있지만, 이러한 연산의 피연산자에 대해서는 덜 알고 있다. 예를 들어: X := Y + 2 * Z
에는 세개의 연산이 있는데, 연산자는 무엇일까?
2는 명백히 곱셈의 操作数지만, X, Y, Z는 단지 식별자일 뿐이며, 연산자가 아니라 연산자를 지정하는 방식이다. Y는 실수, 정수 또는 매개변수가 없는 서브루틴의 이름일 수도 있고, 프로그래머의 오류로 인해 Y는 실제로 불리언 값, 문자열 또는 문장 레이블일 수도 있다.
그렇다면 현재 Y는 무엇이며, 어디에서 왔는지(또는 어디에서 정의되었는지)는 어케 알까?
서브루틴의 데이터는 활성화 레코드에 저장된다. X의 L-값은 활성화 레코드의 특정 오프셋이다.
서브루틴 데이터 제어의 목표는 데이터가 있는 서브루틴의 활성화 레코드를 찾는 것이다. 주어진 표현식이 X = Y + Z라면, Y를 포함하는 활성화 레코드를 찾고 활성화 레코드의 고정된 위치에서 Y의 L-값을 얻은 후, Z와 X에 대해서도 동일한 과정을 반복한다.
데이터 제어의 핵심 문제는 Y가 이러한 할당 문의 각 실행에서 무엇을 의미하는가이다. Y는 지역 또는 비지역 변수일 수 있으며, 이 문제는 선언의 범위 규칙을 알아야한다. (식별자의 사용 범위 및 참조 환경)
데이터 객체를 연산의 피연산자로 사용하는 두 가지 방법은 아래와 같다.
데이터 제어는 식별자(단순 변수)를 특정 데이터 객체와 서브루틴에 바인딩하는 것과 관련이 있고, 이러한 바인딩을 关联이라고 하며, (식별자, 데이터/서브루틴)의 쌍으로 표시된다.
대부분의 프로그래밍 언어에서 프로그램 실행 중에 关联의 "생성-사용-제거" 과정이 진행된다.
참조 환경은 실행 중에 참조를 위한 식별자 关联의 집합이다. 서브루틴의 참조 환경은 일반적으로 실행 중에 변경되지 않는다. 참조 환경의 구성 요소는 아래와 같다:
식별자의 스코프는, 프로그램 내에서 해당 식별자를 접근(또는 명명)할 수 있는 명령문의 집합을 의미한다.
정적 스코프는 문법에 의해 결정되고, 동적 스코프는 실행에 의해 결정된다.
식별자 연관의 동적 스코프는 실행 중 关联이 가시적인 서브루틴 활성화의 집합이다.
동적 범위는 반드시 关联이 생성된 서브루틴 활성화를 포함하며, 이는 해당 关联이 그 서브루틴의 지역 환경의 일부이기 때문이다. 또한 다른 프로그램 활성화에서 비지역 연관으로서 가시적일 수도 있다.
동적 스코프의 규칙으로, 프로그램의 실행을 기반으로 각 关联의 동적 스코프를 정의한다. 예를 들어, 특정 동적 스코프 규칙은 서브루틴 P의 활성화에서 생성된 어떤 연관의 범위는 그 활성화를 포함하고, P가 호출하거나 전달 호출한 서브루틴의 활성화도 포함한다고 명시할 수 있다.
모든 선언이나 식별자의 정의는 일정한 범위가 있으며, 이를 정적 스코프라고 한다. 선언의 정적 스코프는 프로그램 텍스트의 일부로서, 식별자의 사용이 해당 식별자의 특정 선언에 대한 참조로 간주되는 영역이다.
규칙의 예시를 보자.
Q와 T는 P 내부에 선언된 프로시저이므로, Q와 T의 스코프는 a의 스코프와 같다.
R과 S는 Q 내부에 선언된 프로시저다.
U는 T 내부에 선언된 프로시저다.
프로시저가 호출되면, 활성 레코드가 레코드 스택 안에 들어간다.
위 그림으로 예시를 보자.
예시2:
컴파일러는 프로그램의 정적 구조를 알고 있기 때문에, 지정된 데이터 객체를 포함하는 활성 레코드에 올바르게 접근하기 위해 방문해야 하는 정적 링크의 개수를 생성할 수 있다.
정적 체인의 문제점으로, 만약 중첩의 깊이가 많다면, 링크를 여러 번 검색해야 한다. 디스플레이를 사용하면 접근 횟수를 두개의 명령으로 줄일 수 있다.
위는 활성 레코드의 구조다.
데이터 접근은 항상 두 단계로 나누어진다.
P가 Q를 호출했을 때 생성 과정을 보자. P의 활성 레코드를 가리키는 포인터가 있다고 가정한다.
I번째 레벨에서 J번째 레벨로 호출할 때, 호출 활성 레코드에서 Display[1..J-1]를 복사하고 새로운 활성 레코드 포인터를 Display[J]로 추가하여 새로운 디스플레이를 생성한다.
리턴 시엔 현재 활성 레코드의 링크를 사용하여 이전 활성 레코드를 얻고, 내부 저장소의 리턴 주소를 사용하여 이전 활성 레코드로 점프한다.
C 언어에서의 예시다. J와 K는 동시 존재가 불가능하니, 같은 저장공간을 사용해도 된다.
디스플레이 대신 M 레지스터만을 사용하는 경우, M1, M2, M3, M4만 사용할대 프로시저가 5레벨 충첩되면 어떻게 될까? 비합법적일까?
C언어는 효율적인 실행을 위해, 중첩 프로시저가 없고, 디스플레이나 정적 링크도 필요없지만 동적 링크는 필요하다.
class A {
public: int x;
virtual void p() {...};
void q() {...p()...};
protected: int y;
private: int z;
...}
class B : A {
public: int w;
virtual void p() {...};
void r() {...p()...};
private: int v;
virtual void s() {...};
...}
위의 예시를 보자.
스코프 규칙은 일관성을 유지해야 한다.
예를 들어, Pascal의 정적 규칙은 C:=C+B에서 변수 B의 참조를 주 프로그램의 B 선언과 연결한다. 그러니 동적 규칙도 B의 인용을 주 프로그램에서 B로 선언된 객체와 연결해야 한다.
코드에서 B의 여러 선언이 있을 수 있고, 실행 중인 서브프로그램 활성에서도 여러 명명된 B 데이터 객체가 있을 수 있다. 따라서 정적과 동적 규칙 간의 일관성을 유지하는 것이 중요하다.
정적 스코프 규칙이 없다고 가정하고 서브프로그램 내의 문장 X:=X+Max를 생각해 보자. 정적 스코프 규칙이 없으면, 번역 시 X와 Max에 대해 확신할 수 없다. 실행 시에, 참조 연산은 먼저 X와 Max와 관련된 연관을 찾아야 하고, 그 후에 타입과 기타 속성을 결정해야 한다.
Max가 서브프로그램 이름인지, 변수 이름인지, 문장 레이블인지, 타입 이름인지, 형식 매개변수 이름인지도 모르고, X가 변수 이름이라면, Max와 더할 수 있는 타입인지도 모른다. 게다가, 해당 문장이 두 번 실행될 때마다, X와 Max의 연관이 변경될 수 있기 때문에, 전체 프로세스를 매번 반복해야 한다.
정적 스코프 규칙은 이 프로세스의 대부분을 프로그램 번역 시 한 번만 수행하도록 허용하고, 반복할 필요가 없도록 한다. 예를 들어, X:=X+Max에서 Max는 상수 const Max=30이다. 따라서 컴파일러는 Max의 값이 항상 30이라는 것을 알 수 있으며, 문장은 X에 30을 더하는 것으로 번역되므로 Max에 대한 참조 연산이 필요 없다.
X에 대해, 선언이 X: real이라면, 컴파일러는 정적 검사를 수행하여 문장이 실행될 때:
확인 가능하다.
로컬 참조 환경은 가장 단순한 데이터 제어 구조를 형성한다.
서브프로그램 Q의 로컬 환경은 Q의 헤더에 선언된 식별자, 변수 이름, 형식 매개변수 이름, 서브프로그램(서브프로그램 내에 선언된 서브프로그램) 이름 등을 포함한다.
지역 환경에 대해, 정적과 동적 규칙은 일치하기 쉽다. 정적 규칙을 구현하기 위해, 컴파일러는 식별자와 지역 선언 테이블을 유지한다. Q의 본문을 컴파일할 때 식별자의 선언이 필요할 때마다 이 테이블을 조회하면 된다.
서브프로그램 P, Q, R과 지역 변수 X가 Q에 선언되었다고 가정한다.
X 실행 순서:
제어가 서브프로그램 Q에서 P로 반환될 때, Q의 지역 변수 X에 대한 연관은 다시 숨겨지지만, 이 연관에 대해 두 가지 다른 의미를 부여할 수 있다.
참조 환경을 구현하는 편리한 방법은 서브프로그램의 지역 변수를 지역 환경 테이블로 나타내는 것이다. 지역 환경 테이블을 사용하면 유지(보존)와 삭제 방법의 구현이 간단한다.