CTSS: Lisp

John McCarthy and colleagues developed the first version of Lisp at MIT. It originally targeted the IBM 704 and had its own batch operating system (called Overlord) and assembler. The first fully working version was called Lisp 1.5 and documented in the 1962 book LISP 1.5 Programmer's Manual. It was originally developed as an interpreter but a compiler, written in Lisp, was soon added.

At this point in history, the notation for list expressions was not the universal S-expression we know today. The book uses M-expressions, which has square brackets. There was also the 'doublet form' used to enter expressions at the top level. For example, take this CONS expression which takes as parameters the symbol A and the list (B C) to form (A B C):

Internally, Lisp stored two 15 bit cells in each 36 bit machine word, with the left hand cell taking up the space used by the address portion of the word when viewed as a IBM 7x machine code instruction, and the right hand cell in the decrement portion. This led to the primitive functions CAR and CDR used to access the address and decrement portions; these functions are still used today despite the link to the original hardware being long gone.

The version we have today derives from a port of this original code to CTSS in around 1965. Although the 1969 CTSS Programmer's Guide indicates that features specially for CTSS were added, such as a listen mode where commands could be typed interactively, the version we have seems to be an earlier one that does not have this.

The Lisp binary contains only definitions of fundamental functions like CONS, CAR etc; higher level standard functions such as REVERSE or even DEFINE were done in Lisp as an external library. This library can be loaded into the interpreter and then core saved to a new executable file, speeding up invocation of programs.

Below is an implementation of the TPK algorithm in Lisp 1.5, taking into account the limitations mentioned above.

• Library functions, namely DEFINE, APPEND, REVERSE, SQRT and ABS, are implemented separately in a library; I took DEFINE

from existing code and provided implementations for the others based on the Programmer's Manual.

• As there is no interactive input, the numbers acting as input to TPK

are hard coded into the function call.

DEFINE ((
    (F (LAMBDA (X) (PLUS (SQRT (ABS X)) (TIMES 5 (EXPT X 3))))
    )
    (LIMIT-F (LAMBDA (X) (PROG (RESULT)
         (SETQ RESULT (F (CAR X)))
         (RETURN (COND
                  ((GREATERP RESULT 400) (QUOTE TOO-LARGE))
                  (T RESULT)))))
    )
    (TPK (LAMBDA (NUMS)
                 (MAPLIST (REVERSE NUMS) (QUOTE LIMIT-F)))
    )
))

TPK ((10 -1 1 2 3 4 4.3 4.305 4.303 4.302 4.301))
STOP

This uses doublet form to invoke functions and the indentation is what was commonly used at the time.

The code should be read from bottom to top.

TPK reverses the list and calls MAPLIST on this, which will call LIMIT-F 11 times with lists formed by removing the first item in turn, ie (10 -1 1 2 ...), (-1 1 2 ...) (1 2 ...) etc. MAPCAR would be a better choice on more modern Lisps.

LIMIT-F uses a PROG and a local variable RESULT so the function F is only called once per number. The COND checks the result and returns the symbol TOO-LARGE if over 400, else the result.

The first step is to load the library file created for this project into the base Lisp interpreter, and save the resultant binary to a new excitable file.

lisp lib
W 1818.8
06978   
 VALUE
 NIL  
 VALUE
 DEFLIST
 VALUE  
 DEFINE
 VALUE 
 (APPEND REVERSE SQRT ABS)
R .016+.066               
           
save mylisp
W 1818.9
R .000+.066

This can then be run against the solution.

r mylisp tpk
W 1819.0
 VALUE  
 (F LIMIT-F TPK)
 VALUE          
 ( 0.39988629E3 TOO-BIG TOO-BIG TOO-BIG  0.39960863E3  0.322E3
  0.13673205E3  0.41414213E2  0.6E1 -0.4E1 TOO-BIG)           
R .016+.050

Full details on Github.

A great deal of information on the history of Lisp can be found at softwarepreservation.org.

I welcome any questions or comments, and also especially any corrections if I have got something wrong. Please email me at rupert@timereshared.com