Can anyone explain how this "much more complex" recursion works?
Dynamic scoping is easier to implement than lexical scoping. With lexical scoping, the run-time must incorporate some mechanism to find the stack frame of a lexical parent (as seen in the program's source code) to access a nonlocal variable's value. In dynamic scoping the run-time can just follow the stack frame order (starting at the top) to find a nonlocal variable's binding.
Early LISP used dynamic scope. Scheme had lexical scope from the beginning. Common Lisp had both mechanisms and programs can use both.
The implementation of recursion also has to address proper access to nonlocal variables in functions that are values themselves and are passed as arguments to other functions. Do these functions access the nonlocal variables based on their call location or their lexical location in the source code? These problems with functions as arguments are known as the upward and downward funarg problems. Knuth wrote the man-boy program to test Algol 60 implementations in these areas.
Another complication for implementors of Algol 60 was parameter passing by-name, which is neither by-value nor by-reference. I don't recall any other well known language that has subsequently made that non-intuitive (to me) choice. I believe that Algol 68 abandoned call by-name, but it's been 25 years since I looked at the Algol 68 standard.
The closest analog of call by-name I can think of is Common Lisp macros.
If actually evaluating the expression is something expensive and its result might not be needed, it can be the right thing. But whoever designs the function interface has to anticipate that possibility.
They wanted performance on par with existing languages that didn’t allow recursion, and could simply assign fixed addresses to all function arguments and local variables.
Lisp didn’t have that. It allocated environments left and right. That meant that a function call allocated memory and potentially could trigger garbage collection.
The major improvement was to use a runtime stack. That was fairly novel. Earlier compilers used a stack at compile time to make it possible that those fixed addresses for arguments and locals could be shared between functions that didn’t call each other, directly or indirectly, but that stack didn’t exist at runtime.
And yes, the idea of a stack seems trivial nowadays, but it wasn’t at the time. Quite a few CPUs didn’t even have “jump to subroutine” or “return from subroutine” instructions.
Algol’s “call by name” feature also may have complicated this, but I don’t see how that’s more difficult than passing lambdas as arguments.
I guess they do escape analysis and where items are provably local, stack allocate them. If not, plonk them on the heap.
A call frame is an object like any other, so they go on the heap. This allows you to create closures.
“Dijkstra’s quest to generalize led him to use the well-known concept of a stack (i.e., a continuous portion of computer memory) as a run-time object, rather than a mere compile-time object as was the case in Samelson and Bauer’s ALCOR compiler.”
Digging deeper, I found https://www.illc.uva.nl/Research/Publications/Reports/MoL-20... (worth reading, IMHO) which indicates Samuelson and Baur used a stack to parse expressions and generate machine code for them, not for assigning memory locations.
So, I agree with you it can’t have been as simple als I implied.
I doubt they would have plonked anything on the heap, though, because languages of the time didn’t have a heap (FORTRAN certainly didn’t), and the language Samuelson and Baur wrote didn’t even allow functions to call other functions.
Moving to a stack costs, in that you can't do some things, per my original comment. You gain efficiency for what you can do though.
> used a stack to parse expressions and generate machine code for them
Prob this https://html.duckduckgo.com/html?q=dijkstra%20shunting%20yar... which I thought came from dijkstra but your digging suggests not, didn't know! (edit: it did https://en.wikipedia.org/wiki/Shunting-yard_algorithm) infix -> rpn which matches a stack very well (can evaluate as an interpreter, or emit code as a compiler. Not very efficient but it works).
Edit: much credit for digging and reading before posting, wish I could give you several upvotes for that.
I made lisp-interpreter and toyed with compiler.
It is Dijkstra's generalizing style which stands out when a comparison is made with the work of his contemporaries. Rutishauser, for example, had limited the order of his procedure activations in his run-time system [59], while Dijkstra had no such restriction. Floyd's work [60, p.42-43] relied on three specialized “yo-yo” lists (i.e., stacks) instead of one general stack. Likewise, the MAD translator [61, p.28] used several specialized tables. Also, and most importantly, the ALCOR compilers were severely restricted in that they could not handle several ALGOL60 language constructs, including the recursive procedure (cf. Section ). Finally, though the Irons-Feurzeig system [54] did implement recursive-procedure activations and by means of one general run-time stack, it was, in the interest of efficiency, sophisticated in its run-time capabilities and, hence, unlike the run-time system of Dijkstra and Zonneveld .
It's a bit like parsing, these days we either reach for a technique (eg. recursive descent) or an implementation of a tool (such as flex/bison) and never think there was a time before these where people had to struggle conceptually with these things.
[0] https://vanemden.wordpress.com/2014/06/18/how-recursion-got-...