22 ms·

Modern lisps do realize the lambda calculus, but this was not immediate. In particular, in order to exactly match the lambda-calculus beta-reduction rule, you n

Modern lisps do realize the lambda calculus, but this was not immediate. In particular, in order to exactly match the lambda-calculus beta-reduction rule, you need to use lexical rather than dynamic scope, which did not really become popular until Scheme in the 1970s.

btilly 7y ago
Did not become popular, or did not become implemented? My understanding is that lexical scope was first implemented in Algol and Pascal, and then was first implemented with true garbage collection in Scheme. (Thereby leading to the restriction in Algol and Pascal that closures existed, but they could only be passed into functions, and never returned from them. That way the variables being closed over could live on the stack.) But I'd love to learn that I'm wrong and that these things came before that.
- vilhelm_s 7y ago
  Oh, I think you're right, Scheme was at least the first lexically scoped Lisp. Wikipedia says > The concept of closures was developed in the 1960s for the mechanical evaluation of expressions in the λ-calculus and was first fully implemented in 1970 as a language feature in the PAL programming language to support lexically scoped first-class functions. > PAL, the Pedagogic Algorithmic Language, is a programming language developed at the Massachusetts Institute of Technology in around 1967 to help teach programming language semantics and design. It is a "direct descendant" of ISWIM and owes much of its philosophy to Christopher Strachey.
- aap_ 7y ago
  LISP 1.5 as described in the manual implements lexical scope, at least in the interpreter. I haven't studied the compiler too closely, I think there dynamic scope is more prevalent, but as far as I know it has lexical scope as well.
  - vilhelm_s 7y ago
    Where do you see that? Looking at the "Universal LISP function" on page 13 in [0], the case for apply/LAMBDA just extends the current environment a with the arguments of the lambda, but it doesn't unpack a closure to get the environment the lambda function was defined in, so it implements the dynamic version. (Unlike, e.g., the interpreter in SICP [1].) [0] http://www.softwarepreservation.org/projects/LISP/book/LISP%201.5%20Programmers%20Manual.pdf http://www.softwarepreservation.org/projects/LISP/book/LISP%... [1] https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-26.html#%_sec_4.1.1 https://mitpress.mit.edu/sites/default/files/sicp/full-text/...
    - aap_ 7y ago
      The one on page 13 is not what LISP 1.5 does, that's more of an earlier purer idea. I meant the one on page 70 where FUNCTION packs a fucking together with its environment into a FUNARG closure, which when applied unpacks the environment it was created with.
      - vilhelm_s 7y ago
        Interesting! So yeah, the LISP 1.5. interpreter already seems to do this. Googling a bit, it seems that McCarthy mentions this in "History of Lisp" [0], as a change from LISP 1 to LISP 1.5: > In modern terminology, lexical scoping was wanted, and dynamic scoping was obtained. I must confess that I regarded this difficulty as just a bug and expressed confidence that Steve Russell would soon fix it. He did fix it but by inventing the so-called FUNARG device that took the lexical environment along with the functional argument. Similar difficulties later showed up in Algol 60, and Russell's turned out to be one of the more comprehensive solutions to the problem. While it worked well in the interpreter, comprehensiveness and speed seem to be opposed in compiled code, and this led to a succession of compromises. Unfortunately, time did not permit writing an appendix giving the history of the problem, and the interested reader is referred to (Moses 1970) as a place to start. (David Park tells me that Patrick Fischer also had a hand in developing the FUNARG device). So I guess closures had been invented at least by 1962 (when the LISP 1.5 manual was published), but were not widely used because of performance considerations? [0] http://www-formal.stanford.edu/jmc/history/lisp/node4.html http://www-formal.stanford.edu/jmc/history/lisp/node4.html
deleted 7y ago
[deleted]
paulddraper 7y ago
Now, all the Lisps (Racket, Clojure) are lexically scoped. Common LISP is lexically scoped, though it does still have opt-in dynamic scoping ("special variables").
- bathyspheric 7y ago
  Emacs Lisp is still dynamically scoped, no?
  - Impl0x 7y ago
    I believe so, yes.
  - Jtsummers 7y ago
    https://www.gnu.org/software/emacs/manual/html_node/elisp/Using-Lexical-Binding.html https://www.gnu.org/software/emacs/manual/html_node/elisp/Us... Since Emacs 24.1 (had to look up the version), it's been possible to enable lexical scope for a file or buffer. The default is still dynamic scope, and dynamic scope can be achieved even after enabling lexical scope with certain conditions.
jasonhansel 7y ago
Question: if lexical scopes are in the language's data structures, but can't be explicitly created or made visible in the language's syntax, is it still homoiconic?
- fourthark 7y ago
  Aren't lexical scopes visible in the language's syntax?
- seanhunter 7y ago
  If you look up a definition of lexical scope, you'll typically see something like this (from https://en.wikipedia.org/wiki/Scope_(computer_science)#Lexical_scoping https://en.wikipedia.org/wiki/Scope_(computer_science)#Lexic... but others are similar). "With lexical scope, a name always refers to its (more or less) local lexical environment. This is a property of the program text..." So as local lexical environment isa property of the program text, lexical scope is explicit in the language's syntax.

btilly 7y ago

Did not become popular, or did not become implemented? My understanding is that lexical scope was first implemented in Algol and Pascal, and then was first implemented with true garbage collection in Scheme. (Thereby leading to the restriction in Algol and Pascal that closures existed, but they could only be passed into functions, and never returned from them. That way the variables being closed over could live on the stack.) But I'd love to learn that I'm wrong and that these things came before that.

vilhelm_s 7y ago
Oh, I think you're right, Scheme was at least the first lexically scoped Lisp. Wikipedia says > The concept of closures was developed in the 1960s for the mechanical evaluation of expressions in the λ-calculus and was first fully implemented in 1970 as a language feature in the PAL programming language to support lexically scoped first-class functions. > PAL, the Pedagogic Algorithmic Language, is a programming language developed at the Massachusetts Institute of Technology in around 1967 to help teach programming language semantics and design. It is a "direct descendant" of ISWIM and owes much of its philosophy to Christopher Strachey.
aap_ 7y ago
LISP 1.5 as described in the manual implements lexical scope, at least in the interpreter. I haven't studied the compiler too closely, I think there dynamic scope is more prevalent, but as far as I know it has lexical scope as well.
- vilhelm_s 7y ago
  Where do you see that? Looking at the "Universal LISP function" on page 13 in [0], the case for apply/LAMBDA just extends the current environment a with the arguments of the lambda, but it doesn't unpack a closure to get the environment the lambda function was defined in, so it implements the dynamic version. (Unlike, e.g., the interpreter in SICP [1].) [0] http://www.softwarepreservation.org/projects/LISP/book/LISP%201.5%20Programmers%20Manual.pdf http://www.softwarepreservation.org/projects/LISP/book/LISP%... [1] https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-26.html#%_sec_4.1.1 https://mitpress.mit.edu/sites/default/files/sicp/full-text/...
  - aap_ 7y ago
    The one on page 13 is not what LISP 1.5 does, that's more of an earlier purer idea. I meant the one on page 70 where FUNCTION packs a fucking together with its environment into a FUNARG closure, which when applied unpacks the environment it was created with.
    - vilhelm_s 7y ago
      Interesting! So yeah, the LISP 1.5. interpreter already seems to do this. Googling a bit, it seems that McCarthy mentions this in "History of Lisp" [0], as a change from LISP 1 to LISP 1.5: > In modern terminology, lexical scoping was wanted, and dynamic scoping was obtained. I must confess that I regarded this difficulty as just a bug and expressed confidence that Steve Russell would soon fix it. He did fix it but by inventing the so-called FUNARG device that took the lexical environment along with the functional argument. Similar difficulties later showed up in Algol 60, and Russell's turned out to be one of the more comprehensive solutions to the problem. While it worked well in the interpreter, comprehensiveness and speed seem to be opposed in compiled code, and this led to a succession of compromises. Unfortunately, time did not permit writing an appendix giving the history of the problem, and the interested reader is referred to (Moses 1970) as a place to start. (David Park tells me that Patrick Fischer also had a hand in developing the FUNARG device). So I guess closures had been invented at least by 1962 (when the LISP 1.5 manual was published), but were not widely used because of performance considerations? [0] http://www-formal.stanford.edu/jmc/history/lisp/node4.html http://www-formal.stanford.edu/jmc/history/lisp/node4.html

deleted 7y ago

[deleted]

paulddraper 7y ago

Now, all the Lisps (Racket, Clojure) are lexically scoped. Common LISP is lexically scoped, though it does still have opt-in dynamic scoping ("special variables").

bathyspheric 7y ago
Emacs Lisp is still dynamically scoped, no?
- Impl0x 7y ago
  I believe so, yes.
- Jtsummers 7y ago
  https://www.gnu.org/software/emacs/manual/html_node/elisp/Using-Lexical-Binding.html https://www.gnu.org/software/emacs/manual/html_node/elisp/Us... Since Emacs 24.1 (had to look up the version), it's been possible to enable lexical scope for a file or buffer. The default is still dynamic scope, and dynamic scope can be achieved even after enabling lexical scope with certain conditions.

jasonhansel 7y ago

Question: if lexical scopes are in the language's data structures, but can't be explicitly created or made visible in the language's syntax, is it still homoiconic?

fourthark 7y ago
Aren't lexical scopes visible in the language's syntax?
seanhunter 7y ago
If you look up a definition of lexical scope, you'll typically see something like this (from https://en.wikipedia.org/wiki/Scope_(computer_science)#Lexical_scoping https://en.wikipedia.org/wiki/Scope_(computer_science)#Lexic... but others are similar). "With lexical scope, a name always refers to its (more or less) local lexical environment. This is a property of the program text..." So as local lexical environment isa property of the program text, lexical scope is explicit in the language's syntax.