왜 하위프로그램의 “구현”까지 알아야 하는가

14편에서 매개변수 전달 방식이 데이터의 흐름 방향을 정하는 규칙이라는 것을 배웠다. 이 문서는 한 단계 더 들어가 하위프로그램이 호출되고 반환될 때 컴퓨터 메모리 안에서 실제로 무슨 일이 일어나는가를 다룬다. 함수가 호출될 때마다 지역 변수는 어디에 저장되는가? 재귀 호출이 수천 번 일어나도 각 호출의 변수가 서로 섞이지 않는 이유는 무엇인가? 중첩된 함수 안에서 바깥 함수의 변수를 어떻게 찾아가는가? 이 질문들에 답하는 것이 활성화 레코드(activation record) 개념이다.

쉽게 말하면: 활성화 레코드는 “하위프로그램이 한 번 호출될 때마다 그 실행에 필요한 정보를 담아 만드는 메모리상의 작업 카드”다.

실행 스택과 활성화 레코드의 구조

왜 스택(stack)을 쓰는가

하위프로그램 호출은 가장 최근에 호출된 것이 가장 먼저 끝난다는 성질을 가진다. main이 f를 부르고, f가 g를 부르면, g가 끝나야 f로 돌아오고, f가 끝나야 main으로 돌아온다. 이 “나중에 들어온 것이 먼저 나간다(LIFO, Last In First Out)“는 성질은 스택(stack, 한쪽 끝에서만 넣고 빼는 자료구조) 자료구조의 동작 방식과 정확히 일치한다. 그래서 대부분의 언어 구현은 하위프로그램 호출 정보를 실행 스택(runtime stack, 호출 스택이라고도 함) 위에 쌓는다.

활성화 레코드에 담기는 것

활성화 레코드(활성 레코드, 활성화 기록이라고도 부른다. 하위프로그램이 한 번 호출되어 실행 중인 상태를 나타내는 단위이므로 “활성화(activation)“라는 이름이 붙었다)는 하위프로그램이 호출될 때마다 스택 위에 새로 만들어지는 메모리 블록이다. 언어와 구현에 따라 세부 구성은 다르지만, 전형적으로 다음 항목을 포함한다.

동적 링크와 정적 링크가 이 문서의 핵심 주제이며, 뒤에서 각각 자세히 다룬다.

재귀 호출과 실행 스택 — 단계별 추적

재귀 함수는 활성화 레코드가 왜 스택 방식으로 관리되어야 하는지를 가장 잘 보여준다. 팩토리얼(계승, factorial: n부터 1까지 모든 정수를 곱한 값)을 재귀로 계산하는 함수를 보자.

int factorial(int n) {
    if (n <= 1)
        return 1;
    else
        return n * factorial(n - 1);
}
 
int result = factorial(3);

한 줄씩 실행 추적 — 호출이 깊어지는 과정

각 호출은 자신만의 독립된 활성화 레코드를 가지므로 n=3인 호출의 n과 n=1인 호출의 n은 이름은 같아도 서로 다른 메모리 위치에 저장된 별개의 변수다. 스택의 맨 위(가장 최근에 쌓인 것)부터 하나씩 제거(pop)되며 반환되는 이 순서가 바로 LIFO다. 만약 활성화 레코드가 스택이 아니라 하나만 존재했다면, factorial(1)의 n=1이 factorial(3)의 n=3을 덮어써서 재귀가 아예 불가능했을 것이다.

자주 틀리는 점: “재귀 함수는 특별한 메모리 구조가 필요하다”고 생각하기 쉽지만, 사실 재귀 호출도 일반 함수 호출과 완전히 같은 방식으로 활성화 레코드를 스택에 쌓을 뿐이다. 재귀가 특별해 보이는 이유는 단지 같은 이름의 함수가 스스로를 호출해 여러 개의 활성화 레코드가 동시에 스택에 쌓인다는 점뿐이다.

동적 링크(dynamic link) — “누가 나를 불렀는가”

동적 링크는 현재 활성화 레코드가 호출자(caller)의 활성화 레코드를 가리키는 포인터다. 하위프로그램이 끝나 반환할 때, 실행 흐름과 반환 주소는 이 동적 링크를 따라 되돌아간다. 동적 링크가 만드는 연결의 사슬을 동적 체인(dynamic chain) 이라 부른다.

동적 체인은 프로그램이 실제로 호출된 순서를 나타낸다. 소스 코드에서 어디에 정의되어 있는지와 무관하게, “지금 이 순간 실행 중인 함수를 누가 불렀는가”만을 따라간다.

void c_func() { /* ... */ }
void b_func() { c_func(); }
void a_func() { b_func(); }
int main() { a_func(); return 0; }

main이 a_func을, a_func이 b_func을, b_func이 c_func을 호출한 순간의 동적 체인은 다음과 같다.

화살표는 “동적 링크가 가리키는 방향”이며, c_func의 활성화 레코드에 있는 동적 링크를 따라가면 b_func으로, 거기서 다시 따라가면 a_func으로, main까지 거슬러 올라갈 수 있다. c_func이 끝나면 이 동적 링크가 가리키는 b_func의 반환 주소로 돌아간다.

정적 링크(static link) — “나는 소스 코드에서 누구 안에 있는가”

정적 링크는 동적 링크와 전혀 다른 질문에 답한다: “이 하위프로그램은 소스 코드상 어떤 하위프로그램 안에 중첩 정의되어 있는가?” 이 질문은 Pascal, Ada처럼 중첩 하위프로그램(nested subprogram, 하위프로그램 안에 또 다른 하위프로그램을 정의할 수 있는 언어)을 지원하는 언어에서 특히 중요하다. C, Java는 중첩 하위프로그램(지역 함수)을 기본적으로 지원하지 않으므로 정적 링크 개념이 상대적으로 덜 중요하지만, 시험에서는 Pascal류 의사코드로 자주 출제된다.

정적 링크가 만드는 연결의 사슬을 정적 체인(static chain) 이라 하며, 이는 소스 코드에 적힌 렉시컬(lexical, 어휘적) 중첩 구조를 그대로 반영한다. 정적 스코프(static scope, 소스 코드의 중첩 위치로 변수의 유효 범위가 정해지는 규칙 — 9편 참고)를 쓰는 언어에서, 하위프로그램이 자신을 둘러싼 바깥 하위프로그램의 비지역 변수(non-local variable, 지역 변수도 전역 변수도 아닌, 자신을 둘러싼 중간 단계 하위프로그램에 속한 변수)를 찾아갈 때 이 정적 체인을 따라간다.

procedure A
    x : integer

    procedure B
        y : integer

        procedure C
            z : integer
        begin
            z := x + y     { x는 A의 지역변수, y는 B의 지역변수 — 둘 다 C 입장에서 비지역 변수 }
        end C

    begin
        C()
    end B

begin
    B()
end A

이 의사코드에서 C는 소스 코드상 B 안에 중첩되어 있고, B는 A 안에 중첩되어 있다. C가 실행되어 z := x + y를 계산할 때, x와 y는 C의 지역 변수가 아니므로 정적 체인을 따라 바깥으로 찾아 나가야 한다.

비지역 변수 접근 절차: C가 y를 찾을 때는 정적 링크를 한 칸 따라가 B의 활성화 레코드에서 찾고, x를 찾을 때는 정적 링크를 두 칸 따라가 A의 활성화 레코드에서 찾는다. 몇 칸을 따라가야 하는지(중첩 깊이의 차이)는 컴파일 시점에 이미 정해져 있으므로, 이 정보는 컴파일러가 계산해 코드에 미리 심어 둔다.

쉽게 말하면: 정적 링크는 “내가 태어난 곳(정의된 위치)“을 가리키고, 동적 링크는 “누가 나를 불렀는가(호출한 곳)“를 가리킨다. 이 둘은 대부분 다른 곳을 가리킨다.

정적 체인과 동적 체인이 달라지는 상황 — 핵심 함정

정적 체인과 동적 체인이 항상 일치한다면 굳이 두 개로 나눌 이유가 없다. 이 둘이 달라지는 상황이 독학사 시험의 핵심 함정이다. 다음 의사코드를 보자.

procedure A
    x : integer

    procedure B
    begin
        write(x)     { B는 A 안에 정의되어 있으므로 A의 x에 접근 }
    end B

    procedure D
        x : integer
    begin
        x := 100
        B()          { D가 B를 호출 }
    end D

begin
    x := 1
    D()
end A

B는 소스 코드상 A 바로 안에 정의되어 있다. 그런데 B를 실제로 호출한 것은 D다. D도 A 안에 정의되어 있지만(형제 관계), D가 B를 호출했다고 해서 B가 D의 지역 변수 x(값 100)에 접근하게 되는 것은 아니다.

한 줄씩 실행 추적

1

B의 동적 링크는 방금 자신을 호출한 D를 가리키지만, B의 정적 링크는 D가 아니라 A를 가리킨다. 왜냐하면 B는 소스 코드에서 D 안이 아니라 A 안에 정의되었기 때문이다. 그래서 write(x)는 D의 x(값 100)가 아니라 A의 x(값 1)를 출력한다.

자주 틀리는 점: “방금 누가 이 함수를 호출했으니 그 함수의 지역 변수에 접근할 것”이라고 생각하면 틀린다. 비지역 변수 접근은 언제나 정적 체인(소스 코드의 중첩 구조)을 따르지, 동적 체인(실제 호출 순서)을 따르지 않는다. 이것이 정적 스코프 언어의 정의이기도 하다(9편에서 정적 스코프 vs 동적 스코프를 다룬 것과 정확히 연결된다). 만약 언어가 동적 스코프를 쓴다면 정반대로, 이 예시에서 B는 실제로 자신을 호출한 D의 x(값 100)를 찾게 되어 출력이 100으로 바뀐다.

정적 체인과 동적 체인 비교 정리

핵심 정리

• 하위프로그램 호출은 LIFO 성질을 가지므로 실행 스택 위에 호출마다 활성화 레코드를 쌓아 관리하며, 반환 주소·매개변수·지역 변수·동적 링크·정적 링크를 담는다.
• 재귀 호출도 특별한 구조가 필요한 게 아니라, 같은 함수가 스스로를 부를 때마다 독립적인 활성화 레코드가 스택에 새로 쌓이는 것일 뿐이다.
• 동적 링크는 “누가 나를 호출했는가”(실행 순서), 정적 링크는 “나는 소스 코드에서 누구 안에 정의되었는가”(중첩 구조)를 가리키며 이 둘은 자주 일치하지 않는다.
• 정적 스코프 언어에서 비지역 변수 접근은 언제나 정적 체인을 따르며, 실제로 누가 호출했는지(동적 체인)와는 무관하다.
• 정적 체인과 동적 체인이 달라지는 전형적 상황은 어떤 하위프로그램을 그 하위프로그램의 형제 하위프로그램이 호출하는 경우다.

마무리 복습

참고 자료

• Pearson - Sebesta, Concepts of Programming Languages (Global Edition) 소개 페이지 
• 국가평생교육진흥원 독학학위제