The Lisp Implementafion for the PDP-1 Computer [pdf] | Hacker News Reader

The Lisp Implementafion for the PDP-1 Computer [pdf]

s3data.computerhistory.org

84 pointsabrax314116 comments

Peter Deutsch finished this when he was 17 years old.

https://en.wikipedia.org/wiki/L._Peter_Deutsch

Not sure which is more impressive, that, or the fact that this Lisp ran in under 4k of RAM.

No idea what the arch of a PDP would be like; but the manual mentions 4096 "registers". Would those register actually correspond to memory words in a more modern arch ? Was it possible in assembly to directly address each of those register (without the need for MOV-golfing ?)

A "register" is just a [core] memory word. ("The PDP-1 uses an 18-bit word size and has 4096 words as standard main memory", https://en.wikipedia.org/wiki/PDP-1). Terminology changed since then.

I like how the assembly source code is small enough to include at the end of the manual. A bit of slogging finds you the source code and a pdp-1 assembler, enough to run it on simh or MESS, but even though there's a online PDP-1 emulator running SpaceWar!, I wasn't able to find a way to run Lisp 1 online.

* http://www.softwarepreservation.org/projects/LISP/interlisp_...

* http://simh.trailing-edge.com/kits/lispswre.zip

Add: got it working with simh ("brew install simh; pdp1") using the instructions in the linked zip file. It is _really_ delicate, but I finally got fib working:

    (rplacd (quote sub) (quote (expr (lambda (a b) (plus a (minus b))))))

    (rplacd (quote fib) (quote (expr (lambda (l) (cond ((greaterp l 1) (plus (fib (sub l 2)) (fib (sub l 1)))) (t l))))))

    (fib 22) 
    5030

Why yes, it's all in octal fib(18) = 2584

> Was it possible in assembly to directly address each of those register (without the need for MOV-golfing ?

Kind of. 12-bit address field in the instruction. It was an accumulator machine; the CPU only had one main register (as we use the term today) and all operations were between that implicit register and the address specified in memory.

https://www.masswerk.at/spacewar/inside/pdp1-instructions.ht...

Dunno about the pdp-1, but the pdp-10 series machines allowed the registers to be addressed like memory, if I recall correctly- the registers were special and faster than the rest of memory, but one could put machine code in them and run it there. I guess using registers would have been tricky in that case though.

The pdp-1 has two architectural registers: AC and IO and they're not addressable as memory. The PDP-10 has a similar internal structure but fetches and stores the accumulator from/to memory* for instructions that use it.

* in the PDP-6 it really is external memory, in the later models (aka PDP-10) it was moved into the CPU

Dude that's cool for the time, for assembly, now it's way lower than that. Under 1000 bits. But that's only possible on the GA144 cores, MISC (minimal instruction set instead of RISC reduced instruction set). So so terse. I think the size of a program is grows asymptotically slower than for other architectures, just thought of that now.

Some more info about the PDP-1 asm here. https://www.masswerk.at/spacewar/inside/pdp1-instructions.ht...

Note that, cf. a recent discussion about REPLs, this may be the first known (at least published) REPL.

Pg. 4: “Doing CDR of an atom is permissible and will get the atom’s property list. Doing a CAR of an atom may very easily wreck the system.” :-)

Crazy how small the PDP-11 is. 4096 words, 18 bits per word. One register, but the memory locations are called "registers".

From the table on page 17 it looks like all cells are two words, but strangely they all start on an odd address, rather than an even address.

Regular pointers seem to be tagged with a high bit of 0, while pointers to atoms (strings) have a high bit of 1. There may be other tags, couldn't find an explanation of the tagging. Probably there is at least one for integers? No support for floating point.

The atom/string is just a chain of conses, where the car is 3 characters packed into one 18 bit word, and the cdr is the next part of the chain. Since there's no space for a tag in the car that explains why bad stuff happens if you take the car of an atom.

There's a garbage collector in the program listing. It is described as non-compacting, which makes sense if all objects have the same size - no fragmentation possible, and allocation is just unlinking from the freelist. No description of how the GC works.

On page 12 there is also a routine for manually unlinking things to reuse their storage, so perhaps GC can be postponed with manual memory management.

Update: It's been pointed out that the manual unlinking is just for canonicalized symbols which otherwise would live forever.

Someone is documenting their findings on Lisp-1: https://github.com/erikcorry/understanding-lisp-1

Reply on news.ycombinator.com