LISPy things you can do in 64K bytes of core

where "in 64K bytes" shall mean 64K bytes for the LISP system, the runtime stack, and the cons pool! This is the amount of space your LISP system would get on a basic DEC PDP-11 or in a tiny-model PCDOS program. It is probably a little less space than the first implementations of LISP could use.

The IBM 704 electronic data processing machine at M.I.T., on which LISP was first implemented in 1960, had 32K words of 36-bit core memory, [1] which in this case really means one tiny ferrite ring per bit. So there was a total of 36×32768 = 1,183,608 tiny little toroids housed in a not so tiny steel frame. The 704 required a rather spacious room with reinforced floors and industrial air conditioning. The total weight of a typical installation was around 10 metric tons.

The LISP system itself occupied 12K words of core and one word would hold a complete cons cell, [1] so the machine offered a little less than 20K cells of space to LISP. But then, the IBM 704 at the M.I.T. was quite a well-equipped machine. Many 704 installations included as little as 8K words or even 4K words of memory [2]  — too little to run a LISP system. Here is a LISP 1.0 sample program from [1]:

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))))))) ))
()

Note that programs were usually typed on as few lines as possible, because they had to be punched to punched cards or typed in at a teletype which echoed its input on paper. The operator (DEFINE), the arguments (in double parentheses in the case of DEFINE), and an environment had to be supplied to the LISP system in three separate expressions.

There were smaller computers running LISP, though. In 1964 there was PDP-1 LISP, which was an implementation for DEC's PDP-1 computer and it ran on systems with as little as 4096 words of 18-bit storage, where the system itself used around 2000 words. [3] Even on the PDP-1 a cons cell would fit in a single word, so some 2000 cells were available to the system. Here is a PDP-1 LISP sample program from [3] — yes, PDP-1 LISP used lower case:

(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)))))

The LISP system that will be used in the following is Kilo LISP, which is a portable implementation written in ANSI C (C89) that can compile to a tiny model PCDOS executable that runs in 64K bytes of memory. The LISP system itself occupies about 13K bytes, leaving enough space for 8192 cons cells, where each cell allocates 5 bytes (16 bits car, 16 bits cdr, and 3 bits tag, the latter rounded up to 8 bits). Here is a sample program:

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

The Kilo LISP system offers less than half as many cons cells as a big IBM 704 installation and about four times the space of a minimal PDP-1. Of course, ancient computers were slow: the IBM 704 had a clock speed of 40kHz (0.04 MIPS) and the PDP-1 operated at 150kHz (0.15 MIPS), but then the LISP systems on those machines were carefully hand-crafted assembly language programs and their hardware would typically execute one instruction per clock cycle.

Today you can probably emulate an IBM 704 and a PDP-1 on a cheap smartphone, both running at a multiple of the speed of the original hardware, while playing your favorite jump-and-run game. So while a 704 or a PDP-1 could probably run all of the following example programs, they would certainly take their time. The rest of this essay will concentrate on the memory aspect and ignore run times.

Here is a first impression of what ancient LISP feels like.

contact  |  privacy