4 ms·
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 call
by 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 agoI 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 agoYes, 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.
- lkuty 6y agoWhich reminds me of The Funarg Problem Explained by Joseph Weizenbaum https://www.computerhistory.org/collections/catalog/102720700 https://www.computerhistory.org/collections/catalog/10272070.... I used its "diagrams" to understand the closure mechanism (definition vs invocation environments) during the course of a Scheme class in 1996.
- samatman 6y agoA link to the actual paper, for the curious http://www.softwarepreservation.org/projects/LISP/MIT/Weizenbaum-FUNARG_Problem_Explained-1968.pdf http://www.softwarepreservation.org/projects/LISP/MIT/Weizen...
- mcguire 6y agoHaskell's call-by-need is a close relative of by-name (the resulting thunk is only evaluated once).
- User23 6y agoAlgol 60 is a marvel and I feel like it's a language every programmer should learn at least to the point of coding a few basic algorithms. The closest analog of call by-name I can think of is Common Lisp macros.
- ncmncm 6y agoIn C++ you can pass a no-arguments lambda with local bindings that approximates pass-by-name. 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.