데이터 구조 수업의 흔한 과제 중 하나는 산술식을 이진 트리로 바꾸는 것이다. 1 + 1 + 1을 평가해 3을 얻으려면 연산자를 루트에, 두 피연산자를 자식 노드에 놓고 트리를 아래에서 위로 접어 올리면 된다. 한 개발자는 이 단순한 문제에서 출발해 며칠 만에 클로저, 가비지 컬렉터, 커스텀 메모리 할당자, REPL, FFI까지 갖춘 C 기반의 작은 함수형 언어를 만들어냈다. 그 과정에는 언어 런타임을 직접 구현할 때 마주치는 핵심 설계 결정들이 압축적으로 담겨 있다.
연산자를 값으로 일반화하기
출발점은 평가기가 '무엇을 알아야 하는가'라는 질문이었다. 처음에는 덧셈, 뺄셈, 곱셈, 나눗셈을 각각 별도의 표현식 종류(sum type)로 두는 방식을 떠올렸다. 그러나 이 네 연산은 구조적으로 완전히 동일하다. 모두 두 개의 표현식을 받아 하나의 표현식을 내놓는다. 그렇다면 평가기가 굳이 Add와 Sub를 구분할 이유가 없다. 평가기는 함수가 무엇을 하는지 알 필요가 없고, 단지 함수를 어떻게 적용하는지만 알면 된다. 이 통찰이 전체 프로젝트의 방향을 바꿨다. 연산은 특별한 문법이 아니라 그냥 값이 되고, (+ 1 1) 같은 표현이 자연스럽게 따라온다.
변수를 도입하자 곧바로 현실적인 벽에 부딪혔다. 변수는 이름을 표현식에 매핑하는 해시 테이블 조회에 불과하지만, C에는 내장 해시 테이블이 없다. 결국 해시 테이블부터 직접 구현해야 했다. 이런 식으로 '작은 변경'이 계속 새로운 하부 구조를 요구하는 것이 저수준 언어로 런타임을 짤 때의 전형적인 경험이다.
노드 하나에 48바이트, 그리고 할당자 문제
표현식을 태그드 유니언 노드로 정의하자 64비트 시스템에서 노드 하나가 32바이트를 차지했다. 문제는 여기서 끝이 아니었다. malloc()으로 노드를 할당할 때마다 시스템이 16바이트의 메타데이터 헤더를 붙였다. 결국 노드 하나가 실질적으로 48바이트를 소비했고, 1+1을 계산하는 데 필요한 3개 노드만 해도 144바이트가 들었다. 게다가 이런 작은 할당이 수없이 반복된다. 개별 malloc 호출의 오버헤드가 누적되는 구조인 것이다.
해법은 아레나 할당자였다. 시작할 때 큰 메모리 덩어리를 하나 잡아두고, 노드를 요청받으면 현재 위치(top)를 옮기며 직접 잘라 쓰고, 끝나면 블록 전체를 한 번에 해제하는 방식이다. 하지만 재귀 피보나치 fib(5)를 돌리자 노드가 1만 3천 개나 생성되면서 1024개짜리 블록을 금세 넘어섰다. 단순히 realloc으로 블록을 키우면 될 것 같지만, 여기에 함정이 있다. 노드들이 블록 내부에서 서로를 포인터로 가리키고 있어서, realloc이 블록을 새 주소로 옮기는 순간 모든 포인터가 깨지며 세그폴트가 난다.
그래서 하나의 블록을 키우는 대신 여러 블록을 연결 리스트로 이어 붙이는 청크 할당자를 택했다. 한 청크가 가득 차면 새 청크를 할당해 next 포인터로 연결할 뿐, 기존 데이터는 전혀 이동시키지 않는다. 첫 청크와 현재 할당 중인 청크만 추적하면 된다. 데이터를 옮기지 않으니 포인터 무결성이 유지된다.
함수를 노드로 만들다
함수 구현에서 근본적인 갈림길이 나왔다. 처음에는 함수를 C 함수 포인터로 두려 했다. 하지만 그러면 사용자가 자기 함수를 정의할 방법이 없다. 사용자가 코드를 입력하면 그것은 C 함수 포인터가 아니라 노드 트리(AST)로 만들어질 뿐이기 때문이다. 함수가 C 포인터라면 그것은 평가기가 들여다볼 수 없는 불투명한 값이 되고, 함수가 또 다른 함수를 반환하는 상황을 그래프에 다시 넣어 나중에 평가할 수 없게 된다.
그래서 '나는 함수지만 내 코드는 C 포인터가 아니라 바로 이 트리다'라고 평가기에게 알려주는 노드 타입이 필요했다. 이것이 클로저 표현이다. 클로저는 블랙박스가 아니라 그래프 안의 실제 노드로, 한쪽에는 매개변수를, 다른 쪽에는 본문에 해당하는 연산 트리를 담는다. 함수가 노드가 되면서 이제 함수를 값으로 주고받고, 반환하고, 필요할 때마다 단계별로 평가할 수 있게 됐다. 결과적으로 환경 테이블은 이름을 노드에 매핑하며, 변수와 C 네이티브 함수, 사용자 정의 클로저를 한곳에 담는다. 네이티브 함수는 불투명한 C 구현이고 클로저는 언어 차원의 그래프 표현이라는 역할 분담이 명확해진다.
가비지 컬렉터 없이는 안 된다
환경 테이블과 재귀 평가기를 갖춘 뒤 피보나치를 돌리자 메모리 문제가 폭발했다. fib(5)가 1.32MB, fib(10)이 40MB를 먹더니, fib(40)은 약 13억 개의 노드를 생성하며 12기가바이트를 넘긴 뒤 OOM으로 죽었다. 48바이트 곱하기 13억이면 이론상 62GB에 달하는 할당량이다. 원인은 명확했다. 노드를 평가하며 리터럴로 축약하고 나면 쓸모가 없어진 옛 자식 노드들이 그대로 할당자에 남아, 프로그램이 끝날 때까지 해제되지 않았다.
해법은 마크 앤 스위프 가비지 컬렉터였다. 루트에서 출발해 여전히 도달 가능한 모든 노드를 표시하는 마크 단계를 거친다. 여기서 중요한 최적화가 있다. 노드를 리터럴로 축약하는 순간 양쪽 자식 포인터를 null로 만들면, GC는 그 지점에서 옛 노드에 절대 도달할 수 없게 된다. 마크가 끝나면 청크를 훑어 표시되지 않은 노드를 freeList라는 연결 리스트에 모으고, 이후 새 노드가 필요할 때 freeList가 비어 있지 않으면 그 머리를 꺼내 재사용한다. 이 재활용 덕분에 fib(40)의 메모리 사용량은 12GB에서 1.7MB로 떨어졌다.
다만 저자 스스로 밝히듯 이 GC는 실행을 잠시 멈추고 수거하는 stop-the-world 방식이고, 재귀 피보나치 알고리즘 자체가 지수적이라는 한계는 그대로 남는다. 즉 메모리는 극적으로 줄었어도 연산량은 여전하다. 그럼에도 이 프로젝트가 실무자에게 주는 교훈은 분명하다. 언어 런타임이란 결국 표현의 일반화, 포인터 안정성을 지키는 메모리 배치, 그리고 도달 불가능한 상태를 회수하는 규율이 맞물려 돌아가는 그래프 축약 엔진이라는 점이다. 1+1을 2로 계산하는 작은 목표가 이 모든 조각을 순서대로 요구했다는 사실이야말로, 우리가 매일 쓰는 언어 처리기 안에서 벌어지는 일을 압축해 보여준다.