현대 개발자에게 메모리는 사실상 무한에 가깝다. 수 기가바이트의 RAM을 당연하게 쓰는 환경에서 프로그램이 몇 킬로바이트 안에 들어가야 한다는 제약은 상상하기 어렵다. 2019년 t3x.org에 공개된 에세이 "LISPy things you can do in 64K bytes of core"는 바로 그 극단적 제약을 출발점으로 삼는다. 여기서 64K 바이트란 LISP 시스템 자체, 런타임 스택, 그리고 cons 셀을 담는 풀(pool)을 모두 합친 전체 공간을 뜻한다. 이는 기본형 DEC PDP-11이나 소형 모델로 컴파일한 PCDOS 프로그램이 쓸 수 있던 크기이며, 초기 LISP 구현들이 사용하던 공간보다도 오히려 조금 적다.
LISP이 태어난 하드웨어
LISP은 1960년 MIT의 IBM 704에서 처음 구현됐다. 이 기계는 36비트 워드 32K개 분량의 코어 메모리를 갖추고 있었는데, 당시 코어 메모리란 비트 하나마다 아주 작은 페라이트 링 하나가 대응되는 물리적 소자였다. 즉 36×32768, 약 118만 개의 작은 토로이드가 거대한 강철 프레임 안에 들어가 있었던 셈이다. 704는 보강된 바닥과 산업용 냉방을 갖춘 넓은 방을 요구했고, 일반적인 설치 구성의 총 무게는 약 10톤에 달했다.
이 거대한 기계에서조차 LISP이 쓸 수 있는 공간은 넉넉하지 않았다. LISP 시스템 자체가 12K 워드를 차지했고, 한 워드가 하나의 완전한 cons 셀을 담았으므로 실제로 LISP에 남은 공간은 2만 개에 조금 못 미치는 셀이었다. 그나마 MIT의 704는 상당히 잘 갖춰진 축에 속했다. 많은 704 설치 구성은 메모리가 8K 워드, 심지어 4K 워드에 불과했는데, 이 정도로는 LISP 시스템을 아예 돌릴 수가 없었다.
더 작은 기계, 그리고 입력의 불편함
작은 컴퓨터에서 LISP이 돌지 않은 것은 아니다. 1964년 DEC PDP-1을 위한 PDP-1 LISP은 18비트 저장 공간 4096 워드만 갖춘 시스템에서도 동작했다. 시스템 자체가 약 2000 워드를 썼고, PDP-1에서도 cons 셀 하나가 한 워드에 들어갔으므로 약 2000개의 셀이 남았다. 흥미롭게도 PDP-1 LISP은 당시로서는 드물게 소문자를 사용했다.
당시 프로그램이 대개 최소한의 줄 수로 빽빽하게 작성된 데에는 이유가 있다. 코드는 천공카드에 구멍을 뚫거나, 입력을 종이에 그대로 찍어내는 텔레타이프로 입력해야 했기 때문이다. 게다가 초기 LISP에서는 연산자인 DEFINE, 그 인자(DEFINE의 경우 이중 괄호로 감싼 형태), 그리고 환경(environment)을 각각 세 개의 분리된 식으로 시스템에 따로 넘겨야 했다. 오늘날의 대화형 REPL과 비교하면 한 번의 정의조차 번거로운 절차였다.
Kilo LISP이라는 현대의 재현
에세이가 실제 예제에 사용하는 시스템은 Kilo LISP이다. 이는 ANSI C(C89)로 작성된 이식성 높은 구현으로, 소형 모델 PCDOS 실행 파일로 컴파일하면 64K 바이트 메모리 안에서 동작한다. LISP 시스템이 약 13K 바이트를 차지하고 나면 8192개의 cons 셀을 담을 공간이 남는다. 각 셀은 5바이트를 쓰는데, car에 16비트, cdr에 16비트, 그리고 태그에 3비트를 할당하되 이 태그는 8비트로 올림 처리한 결과다.
이 수치를 역사적 기계와 나란히 놓으면 규모감이 선명해진다. Kilo LISP이 제공하는 cons 셀은 잘 갖춰진 IBM 704 설치 구성의 절반에도 못 미치지만, 최소 사양 PDP-1보다는 약 네 배 넓다. 다만 옛 기계들은 느렸다. IBM 704의 클럭은 40kHz(0.04 MIPS), PDP-1은 150kHz(0.15 MIPS) 수준이었다. 그럼에도 이들 LISP 시스템은 정교하게 손으로 짠 어셈블리 프로그램이었고, 당시 하드웨어는 보통 클럭 한 주기에 명령어 하나를 실행했다. 오늘날이라면 값싼 스마트폰으로 704와 PDP-1을 원래 하드웨어의 몇 배 속도로 에뮬레이션하면서 동시에 게임까지 돌릴 수 있을 것이다.
실무자에게 남기는 함의
이 글의 가치는 LISP 문법 소개가 아니라, 제약이 설계를 어떻게 규정했는지를 구체적 숫자로 보여주는 데 있다. cons 셀을 한 워드에 욱여넣는 결정, 태그 비트를 바이트 단위로 올림하는 트레이드오프, 프로그램을 몇 줄에 압축해 넣던 입력 관행은 모두 당시의 자원 한계에서 직접 파생된 것이다. 자원이 넘치는 환경에서 자란 코드는 이런 압력을 받지 않으므로 자료구조 하나가 차지하는 비용에 둔감해지기 쉽다. 반대로 임베디드, 웹어셈블리, 엣지 런타임처럼 메모리가 다시 희소해지는 영역에서는 60여 년 전의 고민이 그대로 되살아난다. 다만 이 에세이는 메모리 측면에만 집중하며 실행 시간은 의도적으로 다루지 않는다는 점은 염두에 둘 필요가 있다. 성능과 알고리즘 복잡도까지 고려하려면 별도의 분석이 요구되며, 여기서 제시된 셀 개수는 어디까지나 공간이라는 한 축의 이야기일 뿐이다.