3 ms·
I think this refers to making the implementation efficient. They wanted performance on par with existing languages that didn’t allow recursion, and could simpl
by Someone 6y ago
I think this refers to making the implementation efficient.
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.
- wilsonthewhale 6y agoDo you have any references or papers that developed the idea of having a stack at runtime? I love reading into the fundamentals of modern computing.
- mjn 6y agoDijkstra's paper "Recursive Programming" (1960) is where he lays out his proposal for implementing recursive Algol-60 subroutines with a stack: https://www.ics.uci.edu/~jajones/INF102-S18/readings/07_dijkstra.pdf https://www.ics.uci.edu/~jajones/INF102-S18/readings/07_dijk...
- throwaway_pdp09 6y agoI'm not sure that's fair. If you have objects that escape downwards (so X calls Y, y creates some item i, i gets returned to X) then you can't have a stack. i may be overwritten at the next call of anything else, as the stack grows over it. 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.
- Joker_vD 6y agoSee also: https://en.wikipedia.org/wiki/Man_or_boy_test https://en.wikipedia.org/wiki/Man_or_boy_test
- Someone 6y agoI got the stack reference from https://eprints.illc.uva.nl/383/1/PP-2010-04.text.pdf https://eprints.illc.uva.nl/383/1/PP-2010-04.text.pdf, which says: “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-2009-12.text.pdf 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.
- throwaway_pdp09 6y agoI was unclear I'm afraid, I was elaborating on your comment about lisp allocating madly, so lisp and not programs in general. 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%20yard%20algorithm 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 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.
- timonoko 6y agoIn 1972 the Nova 1200 Jump-to-Subroutine wrote the Program Counter contents above the subroutine address and thus Subroutine-Return was a short jump via that address. It was possible at compile-time to check if this mechanism was enough. Otherwise the subroutine call was three words, because it was possible to make one word Pushs and Pops in that advanced architecture. I made lisp-interpreter and toyed with compiler.