64KB 메모리로 구현한 LISP의 역사와 예제를 소개한다

64KB 메모리 안에서 실행할 수 있는 LISP 시스템과 예제 프로그램을 소개한다. ANSI C(C89)로 작성된 Kilo LISP는 시스템에 약 13KB를 쓰고, 나머지 공간에 cons 셀 8192개를 담을 수 있다.

여기서 64KB는 LISP 시스템과 런타임 스택, cons 풀이 모두 차지하는 공간을 뜻한다. 이는 기본형 DEC PDP-11이나 tiny-model PCDOS 프로그램이 사용할 수 있는 메모리와 비슷한 규모다.

글은 1960년 LISP가 처음 구현된 IBM 704부터 살펴본다. 이 기계는 36비트 워드 32K개를 갖췄고, LISP 시스템이 12K 워드를 차지해 LISP에 조금 못 미치는 2만 개의 cons 셀이 남았다. 당시 IBM 704 설치 환경은 강철 프레임과 보강 바닥, 산업용 냉방 설비가 필요했고 무게는 약 10톤에 달했다. 한편 메모리가 8K 워드나 4K 워드에 불과한 IBM 704도 있어 LISP 시스템을 실행하기에는 부족했다.

1964년에는 DEC PDP-1에서 돌아가는 LISP 구현도 등장했다. 18비트 저장 공간 4096워드 가운데 시스템이 약 2000워드를 사용해, 약 2000개의 cons 셀이 남았다.

예제에 사용되는 Kilo LISP는 ANSI C(C89)로 작성된 이식 가능한 구현이다. tiny-model PCDOS 실행 파일로 컴파일하면 64KB 메모리에서 실행할 수 있다. 시스템 자체는 약 13KB를 차지하며, 각 셀이 5바이트인 cons 셀 8192개를 담을 수 있다. 글은 이 구현으로 메모리 제약 안에서 할 수 있는 작업을 살펴보며 실행 시간은 다루지 않는다.

과거 IBM 704의 클럭 속도는 40kHz(0.04 MIPS), PDP-1은 150kHz(0.15 MIPS)였다. 당시 LISP 시스템은 손으로 작성한 어셈블리어 프로그램이었고, 하드웨어는 일반적으로 클럭 주기마다 명령어 하나를 실행했다.

부록: 원문 예시

DEFINE
(( (SUBST (LAMBDA (X Y Z) (COND ((ATOM Z) (COND ((EQ Y Z) X)
(T Z))) (T (CONS (SUBST X Y (CAR Z)) (SUBST X Y (CDR Z))))))) ))
()

(rplacd (quote r1) (quote (expr (lambda (m l) (cond ((null l) m)
 (t (r1 (cons (car l) m) (cdr l))))))))
(rplacd (quote reverse) (quote (expr (lambda (l) (r1 nil l)))))

(setq assoc
 (lambda (x a)
 (cond ((null a) nil)
 ((eq x (caar a)) (car a))
 (else (assoc x (cdr a))))))