11

I am thinking about architectures like the 6502 (the stack is limited to 256 bytes -- hardly enough to evaluate any reasonably sized Lisp expression) or the PDP-7 and PDP-8, which stored the return address in the first word of the subroutine, so that subroutines could not call themselves.

It is a well-known property of Lisp that it makes heavy use of recursive routines. For example in typical Lisps that I've seen, eval calls apply, which calls eval again. It is easy to imagine how on a Z80 or x86 or something, a stack frame may contain all the pointers and other data you need. And each invocation of a function can have its own stack frame, as we all know.

My question how people used to implement Lisps on these old and unusual architectures.

Omar and Lorraine
  • 38,883
  • 14
  • 134
  • 274

2 Answers2

19

You are misinterpreting the nature of the Lisp stack. The 256 byte hardware stack of the 6502 processor was not used for the large stacks required by Threaded Interpreted Languages (TILs) like Lisp and Forth. As you say, 256 bytes is grossly inadequate for languages of this type.

The nature of Lisp is to act upon lists of data. A function is merely data and itself sits in a list. This Lisp stack lies within the main memory of the computer.

On the BBC Micro, where my experience of Lisp lies, each call to a function would result in a block of main memory being claimed. This block would hold the return information necessary. It could also hold variables (atoms and lists) declared within the function and could therefore vary in size. The hardware stack was used internally by the language interpreter and the way in which it was used was not made accessible to the Lisp programmer.

These blocks of memory were held in a linked list, which was interspersed with the definition of new functions, and of course, the lists of data upon which Lisp is based and which it is designed to manipulate.

Incidentally, on the BBC Micro you would still run out of memory very quickly. To have any sort of meaningful program you needed to have the optional second processor.

There is some further information in related questions on SO:
https://stackoverflow.com/q/28128620/2870922
https://stackoverflow.com/q/6758308/2870922
and further reading here

Community
  • 1
Chenmunka
  • 8,141
  • 3
  • 39
  • 65
8

For the PDP-1, a scanned and OCR'd (so you can cut & paste) listing of the LISP interpreter is available. This was actually the first LISP implementation, IIRC. The PDP-1 doesn't have any hardware stack; subroutine calls (jsp) store the return address in AC.

So the LISP call stack ("push down list") is implemented in software, using the pointer pdl and the routine pdw to "push down (a) word".

dirkt
  • 27,321
  • 3
  • 72
  • 113