요약
- 스택 이전에는 반환 주소를 전역 변수나 고정 위치에 저장해서 재귀/중첩 호출이 불가능했다
- LIFO 특성을 가진 호출/반환 패턴을 효율적으로 관리하기 위해 Call Stack이 등장했다
본문
스택 이전 시대의 문제
초기 컴퓨터(UNIVAC I, PDP-1, IBM 1130 등)에서는 서브루틴 호출 시 반환 주소를 전역 변수나 서브루틴의 첫 번째 메모리 위치에 저장했다.
A() → B() → A() 호출 시:
1. A가 B를 호출 → B의 반환 주소 = "A의 다음 명령"
2. B가 A를 호출 → A의 반환 주소 = "B의 다음 명령" (덮어씌워짐!)
3. A 종료 → B로 돌아가야 하는데, 원래 A의 반환 주소는 사라짐
같은 함수가 다시 호출되면 이전 반환 주소가 덮어씌워져서 원래 실행 흐름으로 복귀할 수 없었다.
Call Stack의 해결 방식
Call Stack은 호출마다 새로운 스택 프레임을 생성해서 각 호출의 실행 컨텍스트를 독립적으로 보존한다.
A() → B() → A() 호출 시:
┌─────────────────┐ ← Stack Top
│ A의 스택 프레임 │ (두 번째 A 호출)
├─────────────────┤
│ B의 스택 프레임 │
├─────────────────┤
│ A의 스택 프레임 │ (첫 번째 A 호출)
└─────────────────┘
LIFO 구조 덕분에 가장 최근 호출된 함수부터 차례로 반환하며, 각 프레임에 저장된 반환 주소로 정확히 복귀할 수 있다.
역사적 배경
| 연도 | 사건 |
|---|---|
| 1947 | Alan Turing이 "Reversion Storage" 개념 제안 |
| 1958 | John McCarthy가 LISP에서 빌트인 스택 구현 |
| 1961 | Burroughs B5000 - 하드웨어 스택을 지원한 최초의 컴퓨터 중 하나 |
재귀와 중첩 호출이 필수적인 고급 언어(Algol, LISP)의 등장이 하드웨어 스택 지원을 촉진했다.