2 ms·

The PDP-8 has a fun method of returning from subroutines: every subroutine has a spare word allocated at the beginning of it, and it gets the return address wri

The PDP-8 has a fun method of returning from subroutines: every subroutine has a spare word allocated at the beginning of it, and it gets the return address written to it when the subroutine is called. Returning from the subroutine is therefore a matter of jumping to the written address. This lets you call a chain of subroutines without a stack, but of course recursion is impossible. This is maybe common in similar machines?

bear8642 5y ago
> of course recursion is impossible. Thought PDP-8 was used extensively for lisp at various locations. Was recursion made possible by allocating memory elsewhere and using spare word as pointer?
- Animats 5y ago
  There was LISP for the PDP-8! [1] That must have been a cram job, with 4K of 12-bit words. [1] https://collections.museumsvictoria.com.au/content/media/38/420088-small.jpg https://collections.museumsvictoria.com.au/content/media/38/...
Animats 5y ago
UNIVAC 1100 series machines had a Store Location Jump instruction which did that. The return point was stored into the first word of the subroutine. Fortunately, you didn't have to use that. Stacks were, for a long time, controversial. What if you ran out of memory? Some rare compilers, such as Modula 1 for the PDP-11, computed the stack size for each task. If you wanted to recurse, you had to give a recursion limit. Async, the early years. Stacks work well now because we now have lots of memory and address space. Early machines lacked that luxury.
kmill 5y ago
There was an interesting controversy surrounding the Algol-60 report. It seems many members of the committee wanted to be able to create implementations of the language that used only static allocations for activation records, but in the "Amsterdam plot," they sneaked into the report the possibility for recursive procedure definitions which require dynamically allocated activation records (not all machines had efficient stacks!). I don't remember where I first learned about this, it might have been this https://vanemden.wordpress.com/2014/06/18/how-recursion-got-into-programming-a-comedy-of-errors-3/ https://vanemden.wordpress.com/2014/06/18/how-recursion-got-...
Gibbon1 5y ago
I used a compiler 30 years ago for an embedded target that didn't support recursion. There was a tradeoff. By nixing recursion the compiler could perform variable folding optimizations that would be impossible with recursion. That's because without recursion the call tree is an acyclic graph. The result is variables are held in registers and a tiny scratchpad instead of being pushed on a stack.
- zozbot234 5y ago
  > There was a tradeoff. By nixing recursion the compiler could perform variable folding optimizations that would be impossible with recursion. I don't think this is a real tradeoff. Your optimization clearly depends on whole-program compilation anyway, so programs that do not involve non-tail recursion can still be optimized as such.
fpoling 5y ago
Early Fortran required such implementation. In it everything was statically allocated by the compiler including the function return address.

bear8642 5y ago

> of course recursion is impossible. Thought PDP-8 was used extensively for lisp at various locations. Was recursion made possible by allocating memory elsewhere and using spare word as pointer?

Animats 5y ago
There was LISP for the PDP-8! [1] That must have been a cram job, with 4K of 12-bit words. [1] https://collections.museumsvictoria.com.au/content/media/38/420088-small.jpg https://collections.museumsvictoria.com.au/content/media/38/...

Animats 5y ago

UNIVAC 1100 series machines had a Store Location Jump instruction which did that. The return point was stored into the first word of the subroutine. Fortunately, you didn't have to use that. Stacks were, for a long time, controversial. What if you ran out of memory? Some rare compilers, such as Modula 1 for the PDP-11, computed the stack size for each task. If you wanted to recurse, you had to give a recursion limit. Async, the early years. Stacks work well now because we now have lots of memory and address space. Early machines lacked that luxury.

kmill 5y ago

There was an interesting controversy surrounding the Algol-60 report. It seems many members of the committee wanted to be able to create implementations of the language that used only static allocations for activation records, but in the "Amsterdam plot," they sneaked into the report the possibility for recursive procedure definitions which require dynamically allocated activation records (not all machines had efficient stacks!). I don't remember where I first learned about this, it might have been this https://vanemden.wordpress.com/2014/06/18/how-recursion-got-into-programming-a-comedy-of-errors-3/ https://vanemden.wordpress.com/2014/06/18/how-recursion-got-...

Gibbon1 5y ago

I used a compiler 30 years ago for an embedded target that didn't support recursion. There was a tradeoff. By nixing recursion the compiler could perform variable folding optimizations that would be impossible with recursion. That's because without recursion the call tree is an acyclic graph. The result is variables are held in registers and a tiny scratchpad instead of being pushed on a stack.

zozbot234 5y ago
> There was a tradeoff. By nixing recursion the compiler could perform variable folding optimizations that would be impossible with recursion. I don't think this is a real tradeoff. Your optimization clearly depends on whole-program compilation anyway, so programs that do not involve non-tail recursion can still be optimized as such.

fpoling 5y ago

Early Fortran required such implementation. In it everything was statically allocated by the compiler including the function return address.