13 ms·

Lambda calculus is mathematically foundational in a way that Lisp of course isn't. The question is what does Lisp give us as an interpretation of those foundat

Lambda calculus is mathematically foundational in a way that Lisp of course isn't. The question is what does Lisp give us as an interpretation of those foundations? Or does it admit issues that might be unhelpful? (Are macros a good thing?)

lisper 4y ago
Let's not sell Lisp short here. LC might be mathematically foundational, but I think it's fair to say that Lisp is computationally foundational. Mathematics and computation are related, of course, but they are not identical. Computation is the study of mechanical processes for doing math. As such, Lisp's identification of CONS/CAR/CDR/COND as a sufficient set of primitives for a universal Turing machine is important because it's obvious (or at least it was obvious by 1958) how those primitives can be implemented as a mechanical process. Implementing LAMBDA in all its generality is far less obvious, which is why it took 20 years of further research to go from Lisp 1 to Scheme.
- somewhereoutth 4y ago
  I'd say that all foundations are mathematical (at least for 'concrete' stuff, and more besides). If lisp was foundationaly interesting presumably mathematicians would have given it more study? (perhaps they did?) I would disagree that computation is process for doing math - it is math in its own right, specifically that for operating over a discrete state space (urgh help needed to tighten this statement up) LC is basically a rewrite engine, so I'm not sure it would be so hard to implement? Probably some plastic bags, in two colours, paper scraps, and a marker pen would do it? (Edit - one colour bag would need 2 ordered compartments - or if you really have lots of spare time you could build it all with just plain bags and some set theory) However as you say perhaps Lisp is a better abstraction over the Turing tape (yuck).
  - lisper 4y ago
    > I would disagree that computation is process for doing math Sorry, but you are mistaken. This is not a matter of opinion, it is a matter of historical fact. There is a reason that the title of McCarthy's original Lisp paper ends with "and Their Computation by Machine." The opening paragraph of Turing's 1936 paper ends with the sentence, "According to my definition, a number is computable if its decimal can be written down by a machine." > specifically that for operating over a discrete state space. Sorry, but you are mistaken about that too. Analog computers and quantum computers are computers but they do not operate over discrete state spaces. They are, however, machines.
    - somewhereoutth 4y ago
      I think I meant computation in the mathematical sense. In other words that 'computation' is a mathematical object worthy of study in its own right. Per analog and quantum, indeed, and they are also mathematics. I think that is my point - (very nearly) everything proceeds from mathematics, there is no other foundation.
      - lisper 4y ago
        What can I say? You are mistaken. Computation is as much about physics as it is about math. It is the study of what can actually be done in this universe with real hardware (including human brains). If you doubt this, read the opening paragraph of this paper: https://www.scottaaronson.com/papers/pnp.pdf https://www.scottaaronson.com/papers/pnp.pdf The only reason that P=NP? matters at all (let alone why it is a foundational question) is because the theory of computation concerns itself with what can be done with actual physical hardware in actual physical time. > Per analog and quantum, indeed, and they are also mathematics. No, they aren't. Analog computers are machines. Quantum computers are machines (or at least they will be if we ever actually manage to build one). We can describe the behavior of these machines mathematically, but that is not why they matter. They matter because we can actually build them.
        somewhereoutth 4y ago
        I agree that much of the motivation comes from real world imperatives, but, for example, P=NP is of deep mathematical interest in its own right, and if/when mathematicians solve it, they will move on and let us sort out the details. We can actually build stuff (beyond some somewhat blessed prototypes) often only when we've understood the mathematics behind it - edit: or is that the other way around?? I'm not sure that any rigorous discipline can consider itself outside or unbound by mathematics.
        lisper 4y ago
        > P=NP is of deep mathematical interest in its own right Sure. Computation and math are closely related, but they are not identical. Physics is described almost exclusively by differential equations, but differential equations and physics are nonetheless two distinct fields of study.
  - openfuture 4y ago
    Lisp is called the dyck language or the catalan numbers depending on what kind of mathematician you are talking to.
- kazinator 4y ago
  LC is only computationally foundational; it describes recursive functions. It's just another universal turing machine. LC has a great disadvantage: it's difficult to write a LC interpreter in LC. This project shows exactly what that means. To write an LC interpreter, you need a data structure for representing expressions. You need a symbolic data type. LC does not know what a LC expression is. Papers about LC know what that is, but they are not executable. In Lisp we can say, okay, lambda calculus can be represented sort of like this: (lambda (x) x) and so on. That's a nested list. It contains symbols. We can use an assoc list to associate symbols with the terms that are their values. And so on ... Lisp has the programmatic vocabulary to talk about lambda calculus formally, in a way that is executable. I don't suspect there is a significantly easier way for LC to interpret LC than to use the 42 page expression to create a Lisp, and then write the interpreter in that lisp.
  - somewhereoutth 4y ago
    Perhaps LC is telling us that maybe macros weren't such a good idea after all??
  - anderskaseorg 4y ago
    There is. Using the Mogensen–Scott encoding, a self-interpreter can be written in lambda calculus as (λf.ff)(λf.λt.t(λx.x)(λm.λn.ffm(ffn))(λm.λv.ff(mv))), which is a direct translation of the equivalent Haskell code data Term t = Var t | App (Term t) (Term t) | Abs (t -> Term t) newtype Function = Function {apply :: Function -> Function} interpret :: Term Function -> Function interpret (Var x) = x interpret (App m n) = apply (interpret m) (interpret n) interpret (Abs m) = Function (\v -> interpret (m v)) https://en.wikipedia.org/wiki/Mogensen%E2%80%93Scott_encoding https://en.wikipedia.org/wiki/Mogensen%E2%80%93Scott_encodin...
    - kazinator 4y ago
      I don't see what in the interpreter converts the lambda calculus into the Morgensen-Scott encoding. The Wikipedia page describes a "mse" function that is in some meta-language which is not lambda calculus. So first wee need a Lambda Calculus based interpreter for the meta-language, which can run this "mse" function. It looks like mse[x] is supposed to match a variable term, and mse[M N] matches a function application and so on. There are no such concepts and representations in lambda calculus, not to mention shape matching on them. The meta language might as well just be a paragraph of English: instructions on how to hand-compile the lambda calculus into a bunch of thunks which the interpreter can just invoke in certain ways to bring about the evaluation.
- pmcjones 4y ago
  > which is why it took 20 years of further research to go from Lisp 1 to Scheme. Actually it only took Peter Landin a few years. For example see: P. J. Landin, The Mechanical Evaluation of Expressions, The Computer Journal, Volume 6, Issue 4, January 1964, Pages 308–320, https://doi.org/10.1093/comjnl/6.4.308 https://doi.org/10.1093/comjnl/6.4.308
  - lisper 4y ago
    Thanks for that link! TIL.
    - pmcjones 4y ago
      Also: MIT's PAL (1968 -- Art Evans, Martin Richards, and others) and John Reynolds' GEDANKEN (1969): https://www.softwarepreservation.org/projects/PAL/ https://www.softwarepreservation.org/projects/PAL/ https://www.softwarepreservation.org/projects/GEDANKEN/ https://www.softwarepreservation.org/projects/GEDANKEN/
- tromp 4y ago
  Lambda Calculus is computationally foundational. Lisp carries a lot of non-foundational baggage, some of which (like number primitives) makes it far more efficient for running on actual hardware. > As such, Lisp's identification of CONS/CAR/CDR/COND as a sufficient set of primitives for a universal Turing machine You don't need any of those for universality. They are trivially expressible in Lambda Calculus. LAMBDA is really the only necessary primitive.
  - lisper 4y ago
    Yes, that is why I said sufficient and not necessary. The reason CONS/CAR/CDR/COND matter is not because they are necessary. That they are not necessary was known long before 1958. The reason they matter is that they are a better impedance match to human cognition than LC. People can actually write useful programs in Lisp. Very few people can write useful code in LC. Lisp matters because it is a local maximum on the ratio of real-world utility to the size of the formalism. [UPDATE] One idea I've been kicking around for a long time but have not yet acted on is to explore using abstract associative maps as a primitive and see how far that gets you. I suspect this would be a significant win in terms of comprehensibility of code. The foundational axiom would be something like: ((amap k1 v2 k2 v2 ... kn vn ...) kn) == vn So IF, for example, can be written as (amap true [then] false [else]), CONS is (amap car [left] cdr [right]), etc. Or something like that. Oh, yeah, Lisp also introduced symbols as first-class entities. That's a big win.
    - tromp 4y ago
      > People can actually write useful programs in Lisp. I find programming in Haskell much more pleasant. Using car/cdr feels rather primitive compared to pattern matching. > Lisp matters because it is a local maximum on the ratio of real-world utility to the size of the formalism. I feel that role is better served by Haskell, which is basically typed lambda calculus with syntactic sugar on top. Ben Lynn's awesome work [1] shows how minimal a Haskell implementation can be... [1] https://crypto.stanford.edu/~blynn/compiler/ https://crypto.stanford.edu/~blynn/compiler/
      - 4y ago
armchairhacker 4y ago
Lisp is more expressive: I can write any program in LC but I'd much rather use Lisp. Similarly someone could write C or JavaScript or Swift or Haskell in LC. Although I'd argue Lisp is a bit better as it's one of the first languages, one of the first to involve functional concepts like code-as-data, and itself is based on really simple concepts like LC.
- somewhereoutth 4y ago
  Yes expressiveness is a crucial quality. I'd suggest that code-as-data is in fact not a functional concept, and indeed may not necessarily be as helpful as we might like to think. Lisp strayed from the path somewhat when it embarked on runtime enclosure (if my understanding is correct), and anyway it was never going to be as elegant as a true rewrite system.
- tromp 4y ago
  Haskell is more expressive. I can write any program in LISP but I'd much rather use Haskell. Btw, Haskell is much closer in spirit to LC than LISP is.
kazinator 4y ago
Lisp gives you a programming language in which you don't have to write a cryptic 42 page one-liner to have an implementation of lambda calculus. Lisp gives you a way to talk about lambda calculus, in a way that executes. For instance, papers about lambda calculus may talk about "beta reduction" and things of that nature. Those concepts are not in lambda calculus; they are about lambda calculus. In lambda calculus examples you have terms like \x x and whatnot. But lambda calculus doesn't explain what x is; x is an identifier and that is part of the description of lambda calculus, and not in lambda calculus. Lisp has the batteries included for describing languages, such as lambda calculus. It has an answer for what is x: it's a symbol, available as a data type. It has an answer for what is "beta reduction"; it's a function you can write, and execute on some piece of lambda calculus. Lisp closes the circle; the stuff you talk about in a paper can become code, and code which is not far from what the paper talks about.
- somewhereoutth 4y ago
  Beta reduction is in fact the essence of LC - without it all you'd have is a nice tree. The beauty and generality of LC is that x doesn't need an explanation, it is just a placeholder, yet that is enough to define interesting (perhaps all) things. Lisp is an abstraction, that per article can be built upon the deeper abstraction of LC - question is, what does it give us in terms of expressiveness and understanding?
- tromp 4y ago
  > Lisp gives you a programming language in which you don't have to write a cryptic 42 page one-liner to have an implementation of lambda calculus. You totally misunderstood what the 42 pages are. They are not an implementation of LC, but an implementation of LISP in LC. > Lisp gives you a way to talk about lambda calculus, in a way that executes. LC gives you that too; it allows you to encode lambda terms as bitstrings, which can be represented as lambda terms themselves. > But lambda calculus doesn't explain what x is In the binary encoding, x is a de-Bruijn index: a natural number indicating the nesting level of the binding lambda. > Lisp closes the circle So does Binary Lambda Calculus.
  - 4y ago

lisper 4y ago

Let's not sell Lisp short here. LC might be mathematically foundational, but I think it's fair to say that Lisp is computationally foundational. Mathematics and computation are related, of course, but they are not identical. Computation is the study of mechanical processes for doing math. As such, Lisp's identification of CONS/CAR/CDR/COND as a sufficient set of primitives for a universal Turing machine is important because it's obvious (or at least it was obvious by 1958) how those primitives can be implemented as a mechanical process. Implementing LAMBDA in all its generality is far less obvious, which is why it took 20 years of further research to go from Lisp 1 to Scheme.

somewhereoutth 4y ago
I'd say that all foundations are mathematical (at least for 'concrete' stuff, and more besides). If lisp was foundationaly interesting presumably mathematicians would have given it more study? (perhaps they did?) I would disagree that computation is process for doing math - it is math in its own right, specifically that for operating over a discrete state space (urgh help needed to tighten this statement up) LC is basically a rewrite engine, so I'm not sure it would be so hard to implement? Probably some plastic bags, in two colours, paper scraps, and a marker pen would do it? (Edit - one colour bag would need 2 ordered compartments - or if you really have lots of spare time you could build it all with just plain bags and some set theory) However as you say perhaps Lisp is a better abstraction over the Turing tape (yuck).
- lisper 4y ago
  > I would disagree that computation is process for doing math Sorry, but you are mistaken. This is not a matter of opinion, it is a matter of historical fact. There is a reason that the title of McCarthy's original Lisp paper ends with "and Their Computation by Machine." The opening paragraph of Turing's 1936 paper ends with the sentence, "According to my definition, a number is computable if its decimal can be written down by a machine." > specifically that for operating over a discrete state space. Sorry, but you are mistaken about that too. Analog computers and quantum computers are computers but they do not operate over discrete state spaces. They are, however, machines.
  - somewhereoutth 4y ago
    I think I meant computation in the mathematical sense. In other words that 'computation' is a mathematical object worthy of study in its own right. Per analog and quantum, indeed, and they are also mathematics. I think that is my point - (very nearly) everything proceeds from mathematics, there is no other foundation.
    - lisper 4y ago
      What can I say? You are mistaken. Computation is as much about physics as it is about math. It is the study of what can actually be done in this universe with real hardware (including human brains). If you doubt this, read the opening paragraph of this paper: https://www.scottaaronson.com/papers/pnp.pdf https://www.scottaaronson.com/papers/pnp.pdf The only reason that P=NP? matters at all (let alone why it is a foundational question) is because the theory of computation concerns itself with what can be done with actual physical hardware in actual physical time. > Per analog and quantum, indeed, and they are also mathematics. No, they aren't. Analog computers are machines. Quantum computers are machines (or at least they will be if we ever actually manage to build one). We can describe the behavior of these machines mathematically, but that is not why they matter. They matter because we can actually build them.
      - somewhereoutth 4y ago
        I agree that much of the motivation comes from real world imperatives, but, for example, P=NP is of deep mathematical interest in its own right, and if/when mathematicians solve it, they will move on and let us sort out the details. We can actually build stuff (beyond some somewhat blessed prototypes) often only when we've understood the mathematics behind it - edit: or is that the other way around?? I'm not sure that any rigorous discipline can consider itself outside or unbound by mathematics.
        lisper 4y ago
        > P=NP is of deep mathematical interest in its own right Sure. Computation and math are closely related, but they are not identical. Physics is described almost exclusively by differential equations, but differential equations and physics are nonetheless two distinct fields of study.
- openfuture 4y ago
  Lisp is called the dyck language or the catalan numbers depending on what kind of mathematician you are talking to.
kazinator 4y ago
LC is only computationally foundational; it describes recursive functions. It's just another universal turing machine. LC has a great disadvantage: it's difficult to write a LC interpreter in LC. This project shows exactly what that means. To write an LC interpreter, you need a data structure for representing expressions. You need a symbolic data type. LC does not know what a LC expression is. Papers about LC know what that is, but they are not executable. In Lisp we can say, okay, lambda calculus can be represented sort of like this: (lambda (x) x) and so on. That's a nested list. It contains symbols. We can use an assoc list to associate symbols with the terms that are their values. And so on ... Lisp has the programmatic vocabulary to talk about lambda calculus formally, in a way that is executable. I don't suspect there is a significantly easier way for LC to interpret LC than to use the 42 page expression to create a Lisp, and then write the interpreter in that lisp.
- somewhereoutth 4y ago
  Perhaps LC is telling us that maybe macros weren't such a good idea after all??
- anderskaseorg 4y ago
  There is. Using the Mogensen–Scott encoding, a self-interpreter can be written in lambda calculus as (λf.ff)(λf.λt.t(λx.x)(λm.λn.ffm(ffn))(λm.λv.ff(mv))), which is a direct translation of the equivalent Haskell code data Term t = Var t | App (Term t) (Term t) | Abs (t -> Term t) newtype Function = Function {apply :: Function -> Function} interpret :: Term Function -> Function interpret (Var x) = x interpret (App m n) = apply (interpret m) (interpret n) interpret (Abs m) = Function (\v -> interpret (m v)) https://en.wikipedia.org/wiki/Mogensen%E2%80%93Scott_encoding https://en.wikipedia.org/wiki/Mogensen%E2%80%93Scott_encodin...
  - kazinator 4y ago
    I don't see what in the interpreter converts the lambda calculus into the Morgensen-Scott encoding. The Wikipedia page describes a "mse" function that is in some meta-language which is not lambda calculus. So first wee need a Lambda Calculus based interpreter for the meta-language, which can run this "mse" function. It looks like mse[x] is supposed to match a variable term, and mse[M N] matches a function application and so on. There are no such concepts and representations in lambda calculus, not to mention shape matching on them. The meta language might as well just be a paragraph of English: instructions on how to hand-compile the lambda calculus into a bunch of thunks which the interpreter can just invoke in certain ways to bring about the evaluation.
pmcjones 4y ago
> which is why it took 20 years of further research to go from Lisp 1 to Scheme. Actually it only took Peter Landin a few years. For example see: P. J. Landin, The Mechanical Evaluation of Expressions, The Computer Journal, Volume 6, Issue 4, January 1964, Pages 308–320, https://doi.org/10.1093/comjnl/6.4.308 https://doi.org/10.1093/comjnl/6.4.308
- lisper 4y ago
  Thanks for that link! TIL.
  - pmcjones 4y ago
    Also: MIT's PAL (1968 -- Art Evans, Martin Richards, and others) and John Reynolds' GEDANKEN (1969): https://www.softwarepreservation.org/projects/PAL/ https://www.softwarepreservation.org/projects/PAL/ https://www.softwarepreservation.org/projects/GEDANKEN/ https://www.softwarepreservation.org/projects/GEDANKEN/
tromp 4y ago
Lambda Calculus is computationally foundational. Lisp carries a lot of non-foundational baggage, some of which (like number primitives) makes it far more efficient for running on actual hardware. > As such, Lisp's identification of CONS/CAR/CDR/COND as a sufficient set of primitives for a universal Turing machine You don't need any of those for universality. They are trivially expressible in Lambda Calculus. LAMBDA is really the only necessary primitive.
- lisper 4y ago
  Yes, that is why I said sufficient and not necessary. The reason CONS/CAR/CDR/COND matter is not because they are necessary. That they are not necessary was known long before 1958. The reason they matter is that they are a better impedance match to human cognition than LC. People can actually write useful programs in Lisp. Very few people can write useful code in LC. Lisp matters because it is a local maximum on the ratio of real-world utility to the size of the formalism. [UPDATE] One idea I've been kicking around for a long time but have not yet acted on is to explore using abstract associative maps as a primitive and see how far that gets you. I suspect this would be a significant win in terms of comprehensibility of code. The foundational axiom would be something like: ((amap k1 v2 k2 v2 ... kn vn ...) kn) == vn So IF, for example, can be written as (amap true [then] false [else]), CONS is (amap car [left] cdr [right]), etc. Or something like that. Oh, yeah, Lisp also introduced symbols as first-class entities. That's a big win.
  - tromp 4y ago
    > People can actually write useful programs in Lisp. I find programming in Haskell much more pleasant. Using car/cdr feels rather primitive compared to pattern matching. > Lisp matters because it is a local maximum on the ratio of real-world utility to the size of the formalism. I feel that role is better served by Haskell, which is basically typed lambda calculus with syntactic sugar on top. Ben Lynn's awesome work [1] shows how minimal a Haskell implementation can be... [1] https://crypto.stanford.edu/~blynn/compiler/ https://crypto.stanford.edu/~blynn/compiler/
    - 4y ago

armchairhacker 4y ago

Lisp is more expressive: I can write any program in LC but I'd much rather use Lisp. Similarly someone could write C or JavaScript or Swift or Haskell in LC. Although I'd argue Lisp is a bit better as it's one of the first languages, one of the first to involve functional concepts like code-as-data, and itself is based on really simple concepts like LC.

somewhereoutth 4y ago
Yes expressiveness is a crucial quality. I'd suggest that code-as-data is in fact not a functional concept, and indeed may not necessarily be as helpful as we might like to think. Lisp strayed from the path somewhat when it embarked on runtime enclosure (if my understanding is correct), and anyway it was never going to be as elegant as a true rewrite system.
tromp 4y ago
Haskell is more expressive. I can write any program in LISP but I'd much rather use Haskell. Btw, Haskell is much closer in spirit to LC than LISP is.

kazinator 4y ago

Lisp gives you a programming language in which you don't have to write a cryptic 42 page one-liner to have an implementation of lambda calculus. Lisp gives you a way to talk about lambda calculus, in a way that executes. For instance, papers about lambda calculus may talk about "beta reduction" and things of that nature. Those concepts are not in lambda calculus; they are about lambda calculus. In lambda calculus examples you have terms like \x x and whatnot. But lambda calculus doesn't explain what x is; x is an identifier and that is part of the description of lambda calculus, and not in lambda calculus. Lisp has the batteries included for describing languages, such as lambda calculus. It has an answer for what is x: it's a symbol, available as a data type. It has an answer for what is "beta reduction"; it's a function you can write, and execute on some piece of lambda calculus. Lisp closes the circle; the stuff you talk about in a paper can become code, and code which is not far from what the paper talks about.

somewhereoutth 4y ago
Beta reduction is in fact the essence of LC - without it all you'd have is a nice tree. The beauty and generality of LC is that x doesn't need an explanation, it is just a placeholder, yet that is enough to define interesting (perhaps all) things. Lisp is an abstraction, that per article can be built upon the deeper abstraction of LC - question is, what does it give us in terms of expressiveness and understanding?
tromp 4y ago
> Lisp gives you a programming language in which you don't have to write a cryptic 42 page one-liner to have an implementation of lambda calculus. You totally misunderstood what the 42 pages are. They are not an implementation of LC, but an implementation of LISP in LC. > Lisp gives you a way to talk about lambda calculus, in a way that executes. LC gives you that too; it allows you to encode lambda terms as bitstrings, which can be represented as lambda terms themselves. > But lambda calculus doesn't explain what x is In the binary encoding, x is a de-Bruijn index: a natural number indicating the nesting level of the binding lambda. > Lisp closes the circle So does Binary Lambda Calculus.
- 4y ago