5 ms·

> ALGOL 60 included a series of novel features, such as recursion, which was supported in a much more complex manner than logicians had ever envisaged...Recursi

> ALGOL 60 included a series of novel features, such as recursion, which was supported in a much more complex manner than logicians had ever envisaged...Recursive procedures in ALGOL 60 are much more complex than in Lisp. Can anyone explain how this "much more complex" recursion works?

deleted 6y ago
[deleted]
azhenley 6y ago
There is an interesting write-up about Algol 60's recursion [0] that was discussed here before [1]. [0] 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-... [1] https://news.ycombinator.com/item?id=10131664 https://news.ycombinator.com/item?id=10131664
niea_11 6y ago
I did a quick search and according to this article [1], dijkstra's implementation was not restricted compared to other implementations at the time : 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 . [1] : https://www.dijkstrascry.com/node/4 https://www.dijkstrascry.com/node/4
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 ago
  Do 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 ago
    Dijkstra'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 ago
  I'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.
throwaway_pdp09 6y ago
The answers to this question are extremely interesting and show how much work has been done to get where we are today, a position I took for granted and never really understood until now (even in name: 'yo-yo list', for heaven's sake!) 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.
todd8 6y ago
Early LISP implementations used dynamic scope. This means that non-local references in a function search for the variable's binding in the call chain: if A calls B then when B uses nonlocal variable x it refers to the x in A, not necessarily the x that belongs in the lexical parent of B as seen in the source code. (Unlike C, Algol/Pascal/LISP can all define functions inside of other functions. These nested function definitions introduce lexical non-local scopes.) 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.
- geophile 6y ago
  I may be fuzzy on this, it's been a long time. But isn't by-name a special case of passing a function? (And then referencing the parameter in the called procedure invokes the function.)
  - todd8 6y ago
    Yes, that's how "Jensen's Device" is used to implement call-by-name. However, note that the expression passed to an Algol 60 function by name causes the expression to be evaluated in the context of the function being called. Each time the formal parameter appears in the called function the expression passed to that parameter is re-evaluated.

deleted 6y ago

[deleted]

azhenley 6y ago

There is an interesting write-up about Algol 60's recursion [0] that was discussed here before [1]. [0] 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-... [1] https://news.ycombinator.com/item?id=10131664 https://news.ycombinator.com/item?id=10131664

niea_11 6y ago

I did a quick search and according to this article [1], dijkstra's implementation was not restricted compared to other implementations at the time : 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 . [1] : https://www.dijkstrascry.com/node/4 https://www.dijkstrascry.com/node/4

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 ago
Do 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 ago
  Dijkstra'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 ago
I'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.

throwaway_pdp09 6y ago

The answers to this question are extremely interesting and show how much work has been done to get where we are today, a position I took for granted and never really understood until now (even in name: 'yo-yo list', for heaven's sake!) 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.

todd8 6y ago

Early LISP implementations used dynamic scope. This means that non-local references in a function search for the variable's binding in the call chain: if A calls B then when B uses nonlocal variable x it refers to the x in A, not necessarily the x that belongs in the lexical parent of B as seen in the source code. (Unlike C, Algol/Pascal/LISP can all define functions inside of other functions. These nested function definitions introduce lexical non-local scopes.) 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.

geophile 6y ago
I may be fuzzy on this, it's been a long time. But isn't by-name a special case of passing a function? (And then referencing the parameter in the called procedure invokes the function.)
- todd8 6y ago
  Yes, that's how "Jensen's Device" is used to implement call-by-name. However, note that the expression passed to an Algol 60 function by name causes the expression to be evaluated in the context of the function being called. Each time the formal parameter appears in the called function the expression passed to that parameter is re-evaluated.