\( \newcommand\D{\mathrm{d}} \newcommand\E{\mathrm{e}} \newcommand\I{\mathrm{i}} \newcommand\bigOh{\mathcal{O}} \newcommand{\cat}[1]{\mathbf{#1}} \newcommand\curl{\vec{\nabla}\times} \newcommand{\CC}{\mathbb{C}} \newcommand{\NN}{\mathbb{N}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\RR}{\mathbb{R}} \newcommand{\ZZ}{\mathbb{Z}} \)
UP | HOME

Lisp Machines

Table of Contents

Giving up on assembly language was the apple in our Garden of Eden: Languages whose use squanders machine cycles are sinful. The LISP machine now permits LISP programmers to abandon bra and fig-leaf.

– Alan Perlis, Epigrams in Programming, ACM SIGPLAN Sept. 1982

1. Overview

It's still unclear to me the exact origins, but this is how I understand Lisp machines: basically a RISC processor with some microcoded "Lisp virtual machine" target. This is morally right, but quite wrong historically. Correcting the errors, I think, will illuminate and enlighten.

For more in-depth discussion on specific topics, I have relegated the discussion to their own articles.

1.1. Open Questions

How is a Lisp Machine (if we picture it as a virtual machine) different from, say, an SECD machine? Presumably more features are needed, but what features are necessary?

2. History of Lisp Machines

2.1. Origins (1973–1979)

Started at MIT's AI lab around 1973. Originally motivated by the limitations of the PDP-10 when doing AI with Lisp (Macsyma and Woods's LUNAR program are explicitly cited in AIM 444), the hope was to make some high-level hardware designed for Lisp. It's unclear to me if the hope was to manufacture Lisp-oriented hardware like how Burroughs large systems did for Algol 60, or if something else was the goal.

The first Lisp Machine was called the "Cons Machine", or informally referred to as the "Knight machine" (named after Tom Knight who designed it), and its prototype first appeared in 1975 (pg 27 of AI Memo 444). It appears to be a microcoded CPU — i.e., a "vanilla CPU" with microcode specifically for Lisp — according to MIT AI Memo 444. Knight's "CONS" (Working paper 80) explicitly suggests an amalgam of:

  1. Xerox Parc ALTO microprocessor
  2. the DEC PDP-11/40
  3. CMU extensions to the PDP-11/40

Which is interesing. (See also the hisory of microprogramming.) But this ended the experimental phase, and gave way to the marketing period where a number of different companies started producing and selling Lisp machines.

  • Richard Greenblatt, "The LISP Machine". MIT Working Paper 79, November 1974, Eprint.
  • Thomas F Knight, "CONS". MIT Working Paper 80, November 1974, Eprint.
  • Alan Bawden, Richard Greenblatt, Jack Holloway, Thomas Knight, David Moon, Daniel Weinreb, "LISP Machine Progress Report". AI Memo 4444, August 1977.
  • Thomas F Knight, "Implementation of a list processing machine". PhD Thesis, MIT, January 1979.
  • Thomas F. Knight, Jr., David A. Moon, Jack Holloway, Guy L. Steele, Jr., "CADR". AI Memo 528, May 1979.
  • A. Bawden, R. Greenblatt, Jack Holloway, Thomas Knight, David Moon, Daniel Weinreb, "LISP Machine Progress Report". AI Memo 444, August 1979.
  • https://tumbleweed.nu/lm-3/

2.2. Commercialization (1980–????)

Greenblatt founded Lisp Machines, Inc., some time in 1979 — according to Levy's Hackers: Heroes of the Computer Revolution.

Russell Nofsker founded Symbolics, Inc., in April 1980 to build and sell Lisp machines. Most of the MIT AI Lab hackers (and financial backers) sided with Nofsker's Symbolics over Greenblatt's LMI.

Symbolics's initial product was called the LM-2, released in 1981. It was a MIT Cadr machine repackaged.

A couple years later, Symbolics released the 3600 in 1983. Like the Cadr machine, it uses a microcoded setup atop a Motorola 68k CPU (this CPU referred to as the "Front-End Processor" or FEP). The operating system was named a year later, dubbed "Genera". (Yeah, it's odd the OS had no name for a while, until 1984, but there it is.)

Texas Instruments acquired the rights to produce the MIT-derived Lisp Machine from LMI in 1983 (unlambda). That year, TI also bought NuMachine and NuBus from Western Digital. As I understand it, the entire notion of a "computer bus" as we understand emerged from the NuBus. Around 1985, released its TI Explorer Lisp Machine. A 1987 press release noted the development of "the Explorer LISP microprocessor" and referred to its earlier 1985 CPU as the "MegaChip" processor.

3. Architecture

3.1. CPU

I can't quite understand the CPU the CONS machines used, nor which ones the CADR machines used.

The Symbolics 3600 apparenly used a Motorola 68k CPU. David Moon cites a number of benchmarks showing, given the choices at the time, the 68k CPU performed best with Lisp code. Later with the introduction of the Ivory and Genera system they moved to the 64-bit Alpha architecture.

Xerox Daybreak used the MESA CPU. Apparently this is an esoteric CPU.

Interlisp used a MOS 6502 CPU variant, dubbed "INTER-LISP/65".

3.2. Instruction Set

As I understand it, the insruction set for Lisp machines are referred to as "macro instructions". In fact, according to the manual for Genera, the disassemble command produces the "macro instructions" for the compiled function.

At some level, we could think of a Lisp machine as an abstract machine operating on these "macro instructions" as its instruction set. At this level, a Lisp machine is a stack machine with some shortcuts and warts (Paul Fuqua).

3.2.1. Example Disassembles

For the Ivory microprocessor 

(defun example-count (predicate list)
  (let ((count 0))
    (dolist (i list count)
      (when (funcall predicate i)
        (incf count)))))

Would disassemble as (reddit): 

Command: (disassemble (compile #'example-count))

  0  ENTRY: 2 REQUIRED, 0 OPTIONAL      ;Creating PREDICATE and LIST
  2  PUSH 0                             ;Creating COUNT
  3  PUSH FP|3                          ;LIST 
  4  PUSH NIL                           ;Creating I
  5  BRANCH 15
  6  SET-TO-CDR-PUSH-CAR FP|5
  7  SET-SP-TO-ADDRESS-SAVE-TOS SP|-1
 10  START-CALL FP|2                    ;PREDICATE 
 11  PUSH FP|6                          ;I 
 12  FINISH-CALL-1-VALUE
 13  BRANCH-FALSE 15
 14  INCREMENT FP|4                     ;COUNT 
 15  ENDP FP|5
 16  BRANCH-FALSE 6
 17  SET-SP-TO-ADDRESS SP|-2
 20  RETURN-SINGLE-STACK

In the Genera 8 manual, 

(defun foo (array-1 array-2 n-elements)
  (let ((a array-1)
        (b array-2))
    (declare (sys:array-register a b))
    (dotimes (i n-elements)
      (setf (aref b i) (aref a i)))))

Disassembles as: 

(disassemble 'foo)

0 ENTRY: 3 REQUIRED, 0 OPTIONAL
1 PUSH-LOCAL FP|0               ; ARRAY-1
2 BUILTIN SETUP-1D-ARRAY TO 4   ; creating A(FP|3)
3 PUSH-LOCAL FP|1               ; ARRAY-2
4 BUILTIN SETUP-1D-ARRAY TO 4   ; creating B(FP|7)
5 PUSH-LOCAL FP|2               ; N-ELEMENTS creating FP|11 (unnamed)
6 PUSH-IMMED 0                  ; creating I(FP|12)
7 BRANCH 15
10 PUSH-LOCAL FP|12             ; I
11 FAST-AREF FP|4               ; A
12 PUSH-LOCAL FP|12             ; I
13 FAST-ASET FP|8               ; B
14 BUILTIN 1+LOCAL IGNORE FP|12 ; I
15 PUSH-LOCAL FP|12             ; I
16 PUSH-LOCAL FP|11
17 BUILTIN INTERNAL-< STACK
20 BRANCH-TRUE 10
21 RETURN-NIL
FOO

Another example from the manual, if we inline square in the following: 

(defun square-sum (a b)(square (+ a b)))
(defun square (x) (* x x))

Then square-sum disassembles like: 

0 ENTRY: 2 REQUIRED, 0 OPTIONAL
1 PUSH-LOCAL FP|0               ;A
2 BUILTIN +-INTERNAL STACK FP|1 ;B creating X(FP|2)
3 PUSH-LOCAL FP|2               ;X
4 PUSH-LOCAL FP|2               ;X
5 BUILTIN *-INTERNAL STACK
6 RETURN-STACK

For the MIT Cadr machine (reference), 

(defun fact (x)
  (cond ((zerop x) 1)
        (t (* x (fact (1- x))))))

This compiles and disassembles to: 

(disassemble #'fact)

22 NOVE D-PDL ARG|0 ;X
23 MISC D-IGNORE ZEROP
24 BR-NIL 26

25 MOVE D-RETURN 'I
26 MOVE D-PDL ARG|0  ;X
27 CALL D-PDL FEF|10 ;@FUNCTION-CELL FACT
30 MOVE D-PDL ARG|0  ;X
31 MISC D-LAST 1-
32 * PDL-POP
33 MOVE D-RETURN PDL-POP

The explanation:

The first thing (line 22) is to push argument 0 (x) onto the stack, and (line 23) check if it is equal to zero. Line 23 uses the ZEROP miscellaneous function, which sets the "indicators" to NIL if the quantity was not ZERO. Line 24 is a branch instruction which tests the "indicators"; if NIL is set, it will branch to 26. If NIL was not set (the number was zero), it falls through to line 25, which returns the value 1.

If the number was not zero (the second clause of the COND in the source), then control passes to line 26, which pushes X on the PDL (first argument to the multiply on line 32). Next line 27 opens a call to FACT. Line 30 subtracts 1 from X (with the 1- miscellaneous function), and moves the result to "destination LAST". This result is thus the first and only argument to the recursive invocation of FACT, the result of which is left on the PDL because of the destination field of the CALL instruction on line 27.

Now (FACT (1- x)) and X are on the PDL, and they are multiplied by the multiply instruction on line 32. It leaves its result on the PDL, to be found by line 33, which returns the result.

3.3. Space Cadet Keyboard

One relic which remains fabled among programmers today, the keyboard used for Lisp machines back at MIT's AI lab, the CONS/CADR machines used Space Cadet keyboards.

4. References

Last Updated 2023-08-22 Tue 12:51.