LISP

The LISP interpreter was written by Jurjen. It was one of the more complex programs written for the ORDINATOR.

History

The interpreter started as a program on the JEC 2 (Jurjen's Eigen Computer 2; now deceased because its parts were needed for the JEC 3 which unfortunately was never finished). The machine had 2K of memory, but that wasn't enough for LISP, thus 4K of memory were added using an external breadboard. The wires were quite loose; sneezing was not recommended during programming.

With the extra memory, Jurjen managed to get a working LISP interpreter, based on the execution model that was originally used by MIT. The first source was handwritten and hand-assembled (since the JEC had no assembler).

When the EXIDY came at DJOE, with its enormous 56K memory, the LISP interpreter was moved to it by retyping everything from the (paper) source. From then on, the interpreter grew; a reasonable library of useful routines saw the light. This was the famous "rabbit version" that showed a picture of a rabbit during startup, using the EXIDY's programmable character set.

At this time, the input routine was still directly connected to the parser, so that there was no backspacing: once a key was typed, it was processed, and there was no way back!

When the ORDINATOR had grown up enough that is could be used for user-level programming, the LISP interpreter was moved to CP/M (at the cost of the rabbit, unfortunately) and got real disk I/O and a line input routine that didn't start processing user input until you typed RETURN.

Technical details

Originally, the empty list ( ) and NIL were different values: evaluating NIL gave ( ), of course. Jurjen found out the hard way that many programs in LISP assumed that NIL and ( ) were identical, so a lot of code had to be changed (this was before macro assemblers), at the cost of some performance.

The input parser of the interpreter was a pure recursive descent parser: Jurjen didn't know about proper parsers until much later. Since the existing parser worked fine, however, it was never rewritten to the style of modern parsers.

Programs

Among many other LISP programs, two are worth mentioning here: the Sequence pattern recognizer and the SASL compiler.

Sequence pattern recognizer

The sequence pattern recognizer figured out what the pattern was in a sequence of numbers, and predicted the next element. It was inspired by the MIT program. It was intelligent enough to recognize for example the pattern in the sequence:

1, 3, 7, 12, 18, 26, 35, 45, 56, 69

(the differences are equal to the list of number not in the sequence).

This program actually uncovered a bug in the LISP interpreter when Jurjen demonstrated it on an "open house" day with the sequence:

1, -2, 6, -24

The program erroneously predicted -120 (the proper answer being 120)! With many people watching, some digging uncovered that there was a bug in the sign handling of the multiplication routine (an OR instruction instead of a XOR). Jurjen promptly fixed the bug and reassembled the interpreter so that the recognizer gave the correct answer a few minutes later. This was yet another example of our "live performance" way of working.

On the ORDINATOR, LISP used about 60% of the processor cycles on an average day.

SASL compiler

The SASL compiler formed one half of the SASL compiler/interpreter combination described elsewhere. It was written in LISP and hence its input was a SASL program written as a LISP data structure. Its output was another LISP data structure, describing the combinator graph that was to be loaded by the SASL interpreter. To emphasize the unreadability of that output, it was given the equally unreadable file extension ".(,)".

For example, the following is a SASL program for computing factorial numbers, followed by its invocation to compute the factorial of 100:

fac 0 = 1
fac n = n*fac(n-1)

fac 100

The input for the SASL compiler would have been something like this:

fac n (if (= n 0) 1 (* n (fac (- n 1))))

(fac 100)

The corresponding output of the compiler would be something like:

fac (((if B ((= B L) C 0)) C 1) S ((* (fac B ((- B L) C 1))) S L))

(fac 100)

This would then be fed to the SASL interpreter which would print the answer. In order to avoid having to load the SASL compiler for each compilation run, a special version of the LISP interpreter with the SASL compiler already preloaded was created; this version was appropriately called SC (SASL Compiler).

References

The LISP interpreter is also described on pages 40-42 of the book "THE ORDINATOR PROJECT".