Hacker News Reader

Comment by Animats | Hacker News Reader

    ALTER SELECT-PATH TO PROCEED TO PATH-2.

That stores into the code.

In the early days of computing, programs did not have a call stack and code was not usually re-entrant. No recursion. So, finding a place to store state was tough. This is still seen in some embedded code.

It's all Von Neumann's fault. The program is stored in main memory, and he makes a big point that this means the program can modify itself. So early programming languages, operating systems, and CPUs tended to have support for that. Von Neumann didn't think of index registers. Array access involved code modification.

It took a while for index registers to become a standard computer feature. The first one was in the Manchester Mark I, but they were, for too long, a "high end" feature. The IBM 650, IBM 1401, and the Intel 8080 lacked them.[1] Building in an extra adder cost money.

[1] https://en.wikipedia.org/wiki/Index_register

View on HN

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?

> 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?

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/...

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.

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-...

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.

> 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.

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

To add to the history lesson, Herr Doktor Professor Djikstra's infamous "Go To Statement Considered Harmful" should perhaps have been titled "Call Stack Considered Very Useful".

It's worth reading with this understanding, and of course, it is a must to follow through with Dr. Knuth's equally seminal "Structured Programming with go to Statements", in which Djikstra is briefly quoted to qualify and clarify his position on the matter.

> To add to the history lesson, Herr Doktor Professor Djikstra

Dijkstra was Dutch, not Deutsch.

Well, yes.

But I'm able to construct the German form from memory, and have found myself unable to produce a Dutch equivalent even from reference.

When writing it, I imagined Meneer Djikstra rolling his eyes a bit. Which... fits.

It is actually not quite correct in German either, it should be Herr Professor Doktor not Doktor Professor.

Also worth noting that Dijkstra did not write the title for that letter, CACM editor Niklaus Wirth did.

Speaking of Wirth, he wrote a similar essay to the OP: https://people.inf.ethz.ch/wirth/Articles/GoodIdeas_origFig....

Reply on news.ycombinator.com