4 ms·

Lisp is not an implementation of "lambda calculus". > internal compiler is pretty capable Depends, when reading the documentation, one gets the impression tha

by lispm 2y ago

Lisp is not an implementation of "lambda calculus". > internal compiler is pretty capable Depends, when reading the documentation, one gets the impression that their compiler is very limited.

Y_Y 2y ago
> Lisp is not an implementation of "lambda calculus". Maybe you could explain that one for the benefit of myself and the other mortals.
- lispm 2y ago
  See the following excerpt of a longer paper. Generally the lambda calculus is a specific mathematical formalism, LISP is quite a bit more and an actual programming language (it has more than just functions) and implementations don't follow the rules of lambda calculus for evaluation. We also need to see differences between formal models for some of Lisp and actual implementations of a "real" Lisp with numbers, etc. We don't need to model numbers with functions, like with "church numerals". Here follows an excerpt from a paper "Some History of Functional Programming Languages" by D. A. Turner. It talks about LISP, as invent/discovered by John McCarthy: https://www.cs.kent.ac.uk/people/staff/dat/tfp12/tfp12.pdf https://www.cs.kent.ac.uk/people/staff/dat/tfp12/tfp12.pdf ----- Some Myths about LISP Something called “Pure LISP” never existed — McCarthy (1978) records that LISP had assignment and goto before it had conditional expressions and recursion — it started as a version of FORTRAN I to which these latter were added. LISP 1.5 programmers made frequent use of setq which updates a variable and rplaca, rplacd which update the fields of a CONS cell. LISP was not based on the lambda calculus, despite using the word “LAMBDA” to denote functions. At the time he invented LISP, McCarthy was aware of (Church 1941) but had not studied it. The theoretical model behind LISP was Kleene’s theory of first order recursive functions. The M-language was first order, as already noted, but you could pass a function as a parameter by quotation, i.e. as the S-expression which encodes it. Unfortunately, this gives the wrong binding rules for free variables (dynamic instead of lexicographic). If a function has a free variable, e.g y in f = λx.x + y y should be bound to the value in scope for y where f is defined, not where f is called. McCarthy (1978) reports that this problem (wrong binding for free variables) showed up very early in a program of James Slagle. At first McCarthy assumed it was a bug and expected it to be fixed, but it actually springs from something fundamental — that meta-programming is not the same as higher order programming. Various devices were invented to get round this FUNARG problem, as it became known. Not until SCHEME (Sussman 1975) did versions of LISP with default static binding appear. Today all versions of LISP are lambda calculus based. ----- A remark from me: "Today all versions of LISP are lambda calculus based.", except where they are not, like evaluation rules, dynamic binding, data types, etc. What we have now in most Lisps since the mid 80s is lexical binding and closures, but not exclusively. Scheme earlier called dynamic bound variables "fluids". CL has it, for example by default for global variables.
  - deleted 2y ago
    [deleted]
  - deleted 2y ago
    [deleted]
- trealira 2y ago
  I'm not who you replied to, however: - The original Lisp was based on mutable singly linked lists. Lambda calculus has no lists, except for Church-encoded ones (just like lambda calculus only has Church encoded booleans and numbers). It also doesn't have mutability. - Later, Common Lisp (which was a unification of the Lisp variants that had descended from Lisp 1.5) also grew an object system, and it was implemented using dynamic scoping and dynamic typing. That stuff definitely has nothing to do with lambda calculus. If you want an implementation of the lambda calculus, you could try Haskell 98 or Standard ML. Those are based on System F [0], a kind of typed lambda calculus. [0]: https://en.wikipedia.org/wiki/System_F https://en.wikipedia.org/wiki/System_F
  - kazinator 2y ago
    Though Lisp was originally implemented with lists that suported RPLACA and RPLACD functions for practical reasons, the interpretation of Lisp semantics in Lisp was specified (before Lisp was implemented) without using these functions.
  - tromp 2y ago
    > The original Lisp was based on mutable singly linked lists. Lambda calculus has no lists, except for Church-encoded ones (just like lambda calculus only has Church encoded booleans and numbers). While Lambda calculus only has 1 argument functions, you can use those to encode lists [1] and numbers in many ways, including unary, binary, and ternary [2]. [1] https://en.wikipedia.org/wiki/Church_encoding#List_encodings https://en.wikipedia.org/wiki/Church_encoding#List_encodings [2] https://bruijn.marvinborner.de/std/Number_Ternary.bruijn.html https://bruijn.marvinborner.de/std/Number_Ternary.bruijn.htm...
    - kazinator 2y ago
      Encodings built up within lambda calculus are not known to lambda calculus itself, and are ambiguous. There is no way to tell whether some encoding isn't just supposed to denote itself (the lambda calculus functional term that it is) rather than a number that it represents by convention.
- kazinator 2y ago
  You and the other mortals picked up the idea somewhere that Lisp is an implementation of lambda calculus. It was almost totally incorrect. 1. Lambda calculus has only function terms. Lisp has many types: symbols, strings, conses, vectors, characters, integers, floating-point numbers, ... 2. Lambda calculus has no list processing. 3. Lambda calculus has no quote operator to operate on pieces of its own syntax as data. There is no straightforward way to write a meta-circular interpreter for lambda calculus in lambda calculus. (There are papers about it if you want to see how hard this is.) Lisp evaluation defined in Lisp before it was even implemented, in a small number of definitions. 4. Lambda calculus has no functions with optional arguments, or variadic functions. Only functions of one argument, which is required (using currying to simulate more arguments). 5. Lambda calculus has no dynamic control transfers: throw/catch, restarts; no object system; no interactivity. 6. Lambda calculus has no symbols and no named entities: no global function environment. No dynamic/global variables. No mutable variables. No "goto" analogous to Common Lisp tagbody/go.
  - Y_Y 2y ago
    Here is a nice article about lambda calculus self-interpreters: http://anthonylorenhart.com/2021-09-04-Extremely-Simple-Self-Interpretation/ http://anthonylorenhart.com/2021-09-04-Extremely-Simple-Self... tromp is the local expert around here and may have something more enlightening to say.

by lispm 2y ago

Lisp is not an implementation of "lambda calculus". > internal compiler is pretty capable Depends, when reading the documentation, one gets the impression that their compiler is very limited.

Y_Y 2y ago

> Lisp is not an implementation of "lambda calculus". Maybe you could explain that one for the benefit of myself and the other mortals.

lispm 2y ago
See the following excerpt of a longer paper. Generally the lambda calculus is a specific mathematical formalism, LISP is quite a bit more and an actual programming language (it has more than just functions) and implementations don't follow the rules of lambda calculus for evaluation. We also need to see differences between formal models for some of Lisp and actual implementations of a "real" Lisp with numbers, etc. We don't need to model numbers with functions, like with "church numerals". Here follows an excerpt from a paper "Some History of Functional Programming Languages" by D. A. Turner. It talks about LISP, as invent/discovered by John McCarthy: https://www.cs.kent.ac.uk/people/staff/dat/tfp12/tfp12.pdf https://www.cs.kent.ac.uk/people/staff/dat/tfp12/tfp12.pdf ----- Some Myths about LISP Something called “Pure LISP” never existed — McCarthy (1978) records that LISP had assignment and goto before it had conditional expressions and recursion — it started as a version of FORTRAN I to which these latter were added. LISP 1.5 programmers made frequent use of setq which updates a variable and rplaca, rplacd which update the fields of a CONS cell. LISP was not based on the lambda calculus, despite using the word “LAMBDA” to denote functions. At the time he invented LISP, McCarthy was aware of (Church 1941) but had not studied it. The theoretical model behind LISP was Kleene’s theory of first order recursive functions. The M-language was first order, as already noted, but you could pass a function as a parameter by quotation, i.e. as the S-expression which encodes it. Unfortunately, this gives the wrong binding rules for free variables (dynamic instead of lexicographic). If a function has a free variable, e.g y in f = λx.x + y y should be bound to the value in scope for y where f is defined, not where f is called. McCarthy (1978) reports that this problem (wrong binding for free variables) showed up very early in a program of James Slagle. At first McCarthy assumed it was a bug and expected it to be fixed, but it actually springs from something fundamental — that meta-programming is not the same as higher order programming. Various devices were invented to get round this FUNARG problem, as it became known. Not until SCHEME (Sussman 1975) did versions of LISP with default static binding appear. Today all versions of LISP are lambda calculus based. ----- A remark from me: "Today all versions of LISP are lambda calculus based.", except where they are not, like evaluation rules, dynamic binding, data types, etc. What we have now in most Lisps since the mid 80s is lexical binding and closures, but not exclusively. Scheme earlier called dynamic bound variables "fluids". CL has it, for example by default for global variables.
- deleted 2y ago
  [deleted]
- deleted 2y ago
  [deleted]
trealira 2y ago
I'm not who you replied to, however: - The original Lisp was based on mutable singly linked lists. Lambda calculus has no lists, except for Church-encoded ones (just like lambda calculus only has Church encoded booleans and numbers). It also doesn't have mutability. - Later, Common Lisp (which was a unification of the Lisp variants that had descended from Lisp 1.5) also grew an object system, and it was implemented using dynamic scoping and dynamic typing. That stuff definitely has nothing to do with lambda calculus. If you want an implementation of the lambda calculus, you could try Haskell 98 or Standard ML. Those are based on System F [0], a kind of typed lambda calculus. [0]: https://en.wikipedia.org/wiki/System_F https://en.wikipedia.org/wiki/System_F
- kazinator 2y ago
  Though Lisp was originally implemented with lists that suported RPLACA and RPLACD functions for practical reasons, the interpretation of Lisp semantics in Lisp was specified (before Lisp was implemented) without using these functions.
- tromp 2y ago
  > The original Lisp was based on mutable singly linked lists. Lambda calculus has no lists, except for Church-encoded ones (just like lambda calculus only has Church encoded booleans and numbers). While Lambda calculus only has 1 argument functions, you can use those to encode lists [1] and numbers in many ways, including unary, binary, and ternary [2]. [1] https://en.wikipedia.org/wiki/Church_encoding#List_encodings https://en.wikipedia.org/wiki/Church_encoding#List_encodings [2] https://bruijn.marvinborner.de/std/Number_Ternary.bruijn.html https://bruijn.marvinborner.de/std/Number_Ternary.bruijn.htm...
  - kazinator 2y ago
    Encodings built up within lambda calculus are not known to lambda calculus itself, and are ambiguous. There is no way to tell whether some encoding isn't just supposed to denote itself (the lambda calculus functional term that it is) rather than a number that it represents by convention.
kazinator 2y ago
You and the other mortals picked up the idea somewhere that Lisp is an implementation of lambda calculus. It was almost totally incorrect. 1. Lambda calculus has only function terms. Lisp has many types: symbols, strings, conses, vectors, characters, integers, floating-point numbers, ... 2. Lambda calculus has no list processing. 3. Lambda calculus has no quote operator to operate on pieces of its own syntax as data. There is no straightforward way to write a meta-circular interpreter for lambda calculus in lambda calculus. (There are papers about it if you want to see how hard this is.) Lisp evaluation defined in Lisp before it was even implemented, in a small number of definitions. 4. Lambda calculus has no functions with optional arguments, or variadic functions. Only functions of one argument, which is required (using currying to simulate more arguments). 5. Lambda calculus has no dynamic control transfers: throw/catch, restarts; no object system; no interactivity. 6. Lambda calculus has no symbols and no named entities: no global function environment. No dynamic/global variables. No mutable variables. No "goto" analogous to Common Lisp tagbody/go.
- Y_Y 2y ago
  Here is a nice article about lambda calculus self-interpreters: http://anthonylorenhart.com/2021-09-04-Extremely-Simple-Self-Interpretation/ http://anthonylorenhart.com/2021-09-04-Extremely-Simple-Self... tromp is the local expert around here and may have something more enlightening to say.