컴퓨터 프로그램에서의 메모리 영역은 코드 영역, 데이터 영역, 힙 영역, 그리고 스택 영역으로 분류된다. 이 중 스택은 프로그램 컴파일 타임에 결정되는 메모리 영역으로, 사실상 컴퓨터 프로그램에서 함수의 등장과 함께한 유서깊은 데이터 영역이다. 하지만, 스택이 우리 컴퓨터와 굉장히 오랜 시간 함께해온 것과는 별개로, 컴퓨터에서 스택이 다뤄지는 방식은 시대에 따라 계속 변해왔다. 이번 글에서는 CPU들이 스택을 다루는 방식이 어떻게 변해왔는지 알아보도록 하자.
우선, 스택이란 무엇인가? 스택은 LIFO (Last-In, Fist-Out) 방식으로 데이터를 관리하는 메모리 구조이다. 기본적으로 프로그램에서 함수가 호출될 때, 해당 함수는 어느만큼의 메모리를 사용하게 된다. (일반적으로 지역변수나 리턴값 등이 스택으로 관리된다) 사실 데이터를 저장할 때, 꼭 스택이라는 형식으로 저장할 필요는 없다. 하지만 함수 호출에 있어서 스택을 이용하는 것은 스택이라는 데이터 구조가 함수 호출이라는 동작을 가장 효율적으로 처리할 수 있기 때문이다.
만약 함수가 한번에 하나만 호출된다면, 사실 스택을 이용할 필요가 없을 것이다. 함수가 사용할 메모리 공간을 사전에 고정해두고, 해당 영역을 사용하도록 하면 된다. 하지만 우리는 함수 안에서 함수를 호출할 수 있다. C언어를 배울 때 사용하는 첫 예시인 Hello, World!에서 main() 안에서 printf("Hello, World\n")를 사용하는 것도 함수 안에서 함수를 사용하는 예시이다.
우리가 함수를 A > B > C 순으로 호출하면, 빠져나올 때는 C > B > A 순서로 빠져나온다. 이러한 마지막에 들어간 함수에서 가장 빨리 빠져나오는 특성이 스택의 LIFO 특성과 일치한다. 따라서 우리는 함수가 호출될 때, 함수가 사용하는 데이터를 스택에 차곡차곡 쌓고, 함수가 끝날 때 빼내는 방식으로 함수에게 메모리를 제공하게 된 것이다. 만약 이렇게 하지 않고, 각 함수가 데이터를 저장할 때 아무데나 저장하게 된다면, 함수가 호출될 때마다 메모리에서 어딘가 빈 공간을 찾아서 함수에게 제공해야 할 것이고, 함수 호출 속도는 굉장히 느려질 것이다.
프로그래밍에서 서브루틴, 함수라는 개념은 최초의 프로그래머인 에이다 러브레이스가 인류 최초의 컴퓨터 프로그램을 개발할 때부터 존재했다. 그는 반복 가능한 계산 단위를 천공카드 뭉치로 만들고, 카드 그룹으로 컴퓨터의 연산을 조직화하는 방법을 개발했다. 그러나 당시에는 스택과 같이 자동적으로 함수의 메모리 공간을 추적할 수 있는 방법은 없었다. 찰스 베비지가 설계한 해석기관의 데이터 저장 공간인 '스토어'는 단순히 번호가 붙은 거대한 톱니바퀴 뭉치였으며, 에이다는 톱니바퀴 기둥에서 프로그램이 사용할 데이터 공간을 직접 지정해야했다. 해석기관의 스토어는 현대 컴퓨터의 메모리보다는 전역적으로 접근 가능한 거대한 레지스터 세트에 더 가까운 형태였던 것이다. 따라서 베르누이 수를 계산하는 에이다의 프로그램은 함수 중첩 대신 루프를 주로 사용했다. 함수 중첩과 달리, 루프는 시작점과 끝점이 명확해서 카드 뭉치를 물리적으로 반복시키기가 쉬웠다.
컴퓨터 프로그램의 서브루틴이 스택을 사용한다는 개념은 1945년 콘라드 주세가 세계 최초의 상업용 컴퓨터인 Z4를 개발하면서 처음 등장했다.