7 ms·

My question would be, why is Lambda-calculus not a good programming language in practice?

pwm 8y ago
It is a mathematical model of computation and thus it does not concern itself with practicalities like space/time complexity or ease of implementation. On the other hand pretty much all practical functional language builds on top of LC, tackling these practical challenges.
- galaxyLogic 8y ago
  Understood there must be many practical issues, what I'm wondering is if there is an issue, and what is the main issue of using the syntax of Lambda calculus as the basis of a programming language, how is it worse than say Lisp or JavaScript?
  - OskarS 8y ago
    For the purpose it was intended (i.e. mathematical analysis of the notion of "computation") it's not worse. It is, in fact, far superior to almost any other system like that. The point of lambda calculus isn't to be able to program servers or whatever. The point is to be able to express ideas like beta-reduction and Y-combinators in a succint way, and a way that's easy to manipulate with a pencil (or chalk). "Notation as a tool of thought", and all that. Turing machines are similar: they're excellent for modeling computation, but you wouldn't want to use it for actual programming. It's not made for that. As someone else said: the fact that it is so remarkably close to several actual programming languages is pretty astonishing, and shows that there really is some deep brilliance to Church's original formulation. Turing is more famous for his machines, but it's interesting to note that while no programming language resembles a "raw" Turing machine, MANY languages resemble lambda calculus. EDIT: to answer your actual question: it's worse than Lisp or JavaScript in any number of ways. There's no state, there's no "I/O" as such, no loops, no function names (well, sortof), no strings, etc, etc. And oh, btw: no numbers. All numbers in lambda calculus is defined in terms of functions, htere's no such thing as a "numeric literal". As I said: it's not made for actual programming. Doing actual programming in lambda calculus is like trying to use the Peano axioms to calculate how much money you need to pay in the supermarket.
    - heavenlyblue 8y ago
      Everything you're saying here is true, but I think you're forgetting something incredibly important that isn't easily representable on a Turing machine at all: equivalences of the terms and their rewrite rules. Lambda calculus provides you with a set of ways in which you could rewrite your program and get an equivalent one (by the definition of lambda calculus), or how to execute the program itself. It means that most of the functionality for deciding when the code should be executed (by the compiler or at run time) is already in the compiler. It's something that imperative languages struggle with.
    - tromp 8y ago
      The lack of numbers is not too great a handicap, as one can design numbers to suits one's needs. For instance, the following is a program for computing the characteristic sequence of primes: \io.let zero = \x\y.x; one = \x\y.y; consz = \xs\p.p zero xs; oneS = \cont\x\xs\p.p x (xs cont); zeroS = \cont\x\xs.consz (xs cont); primes = \N\p.p one (let SN = \r.oneS (N r); F = SN F in (primes SN) F); main = consz (consz (primes zeroS)) in main Removing the minimal syntactic sugar results in \io.(\zero.(\one.(\consz.(\oneS.(\zeroS.(\primes.(\main.main) (consz (consz (primes zeroS)))) ((\f.(\x.x x) (\x.f (x x))) (\primes.\N.\p.p one ((\SN.(\F.primes SN F) ((\f.(\x.x x) (\x.f (x x))) (\F.SN F))) (\r.oneS (N r)))))) (\cont.\x.\xs.consz (xs cont))) (\cont.\x.\xs.\p.p x (xs cont))) (\xs.\p.p zero xs)) (\x.\y.y)) (\x.\y.x) which can be run, as a 167 bit executable, on a binary lambda calculus machine to produce the infinitely long 00110101000101000101000100000101000001000101000100... See http://www.ioccc.org/2012/tromp/hint.html http://www.ioccc.org/2012/tromp/hint.html for details
  - vertline3 8y ago
    "if there is an issue, and what is the main issue of using the syntax of Lambda calculus as the basis of a programming language" have you used scheme? From wikipedia "Scheme is a very simple language, much easier to implement than many other languages of comparable expressive power. This ease is attributable to the use of lambda calculus to derive much of the syntax of the language from more primitive forms."
    - mimixco 8y ago
      Scheme is a Lisp. And so is Clojure and probably 20 others. Wolfram Language is a Lisp with M-expressions (gag).
      - vertline3 8y ago
        Correct, scheme is like a minimal flavor lisp.
tathougies 8y ago
Actually the question should be... why is the lambda calculus such a great programming language in practice? The lambda calculus is unique among other theoretical models of computation (automata, turing machines, etc) in that it is the syntactic and computational basis of several popular languages (lisp, Haskell, ML, etc). In all these languages, you can essentially write lambda calculus terms in a way that you cannot write turing machines in imperative languages.
jakeinspace 8y ago
The same reason a Turing machine (even a finite one) is a silly programming 'language'. It's an abstract model of computation. It just happens that real-world languages based on The Lambda Calculus like Lisp are only a stone's throw away syntactically, whereas the gulf between even assembly and a Turing machine program is quite large. I suppose that's because The Lambda Calculus doesn't aim to describe a pseudo-physical machine, and therefore leaves implementation much more open to interpretation.
dreamcompiler 8y ago
Same reason Turing machines are impractical; it's too low-level. But IMHO starting with "functional composition without side effects" (LC model) and adding the practical stuff gets you a lot farther than adding practical stuff to "everything is a side effect and functions don't exist" (the TM model). Back in the days before parallel programming, large-scale software engineering, networks, cloud computation, etc it wasn't always clear that anything was wrong with the TM model. But given how computing works today it's clear (to me at least) that LC is a much, much better substrate for designing computation.
- dreamcompiler 8y ago
  As an aside, 1958 was definitely back in those days. But that's when John McCarthy decided the TM model was lacking and said "Hey let's build a programming language on Lambda Calculus instead" and Lisp was born. And that's how John McCarthy was smarter than the rest of us.
kazinator 8y ago
It doesn't have features like global definitions, numbers, strings, I/O, arrays, lists, data structures, ...
mimixco 8y ago
It is. We call it Lisp.

pwm 8y ago

It is a mathematical model of computation and thus it does not concern itself with practicalities like space/time complexity or ease of implementation. On the other hand pretty much all practical functional language builds on top of LC, tackling these practical challenges.

galaxyLogic 8y ago
Understood there must be many practical issues, what I'm wondering is if there is an issue, and what is the main issue of using the syntax of Lambda calculus as the basis of a programming language, how is it worse than say Lisp or JavaScript?
- OskarS 8y ago
  For the purpose it was intended (i.e. mathematical analysis of the notion of "computation") it's not worse. It is, in fact, far superior to almost any other system like that. The point of lambda calculus isn't to be able to program servers or whatever. The point is to be able to express ideas like beta-reduction and Y-combinators in a succint way, and a way that's easy to manipulate with a pencil (or chalk). "Notation as a tool of thought", and all that. Turing machines are similar: they're excellent for modeling computation, but you wouldn't want to use it for actual programming. It's not made for that. As someone else said: the fact that it is so remarkably close to several actual programming languages is pretty astonishing, and shows that there really is some deep brilliance to Church's original formulation. Turing is more famous for his machines, but it's interesting to note that while no programming language resembles a "raw" Turing machine, MANY languages resemble lambda calculus. EDIT: to answer your actual question: it's worse than Lisp or JavaScript in any number of ways. There's no state, there's no "I/O" as such, no loops, no function names (well, sortof), no strings, etc, etc. And oh, btw: no numbers. All numbers in lambda calculus is defined in terms of functions, htere's no such thing as a "numeric literal". As I said: it's not made for actual programming. Doing actual programming in lambda calculus is like trying to use the Peano axioms to calculate how much money you need to pay in the supermarket.
  - heavenlyblue 8y ago
    Everything you're saying here is true, but I think you're forgetting something incredibly important that isn't easily representable on a Turing machine at all: equivalences of the terms and their rewrite rules. Lambda calculus provides you with a set of ways in which you could rewrite your program and get an equivalent one (by the definition of lambda calculus), or how to execute the program itself. It means that most of the functionality for deciding when the code should be executed (by the compiler or at run time) is already in the compiler. It's something that imperative languages struggle with.
  - tromp 8y ago
    The lack of numbers is not too great a handicap, as one can design numbers to suits one's needs. For instance, the following is a program for computing the characteristic sequence of primes: \io.let zero = \x\y.x; one = \x\y.y; consz = \xs\p.p zero xs; oneS = \cont\x\xs\p.p x (xs cont); zeroS = \cont\x\xs.consz (xs cont); primes = \N\p.p one (let SN = \r.oneS (N r); F = SN F in (primes SN) F); main = consz (consz (primes zeroS)) in main Removing the minimal syntactic sugar results in \io.(\zero.(\one.(\consz.(\oneS.(\zeroS.(\primes.(\main.main) (consz (consz (primes zeroS)))) ((\f.(\x.x x) (\x.f (x x))) (\primes.\N.\p.p one ((\SN.(\F.primes SN F) ((\f.(\x.x x) (\x.f (x x))) (\F.SN F))) (\r.oneS (N r)))))) (\cont.\x.\xs.consz (xs cont))) (\cont.\x.\xs.\p.p x (xs cont))) (\xs.\p.p zero xs)) (\x.\y.y)) (\x.\y.x) which can be run, as a 167 bit executable, on a binary lambda calculus machine to produce the infinitely long 00110101000101000101000100000101000001000101000100... See http://www.ioccc.org/2012/tromp/hint.html http://www.ioccc.org/2012/tromp/hint.html for details
- vertline3 8y ago
  "if there is an issue, and what is the main issue of using the syntax of Lambda calculus as the basis of a programming language" have you used scheme? From wikipedia "Scheme is a very simple language, much easier to implement than many other languages of comparable expressive power. This ease is attributable to the use of lambda calculus to derive much of the syntax of the language from more primitive forms."
  - mimixco 8y ago
    Scheme is a Lisp. And so is Clojure and probably 20 others. Wolfram Language is a Lisp with M-expressions (gag).
    - vertline3 8y ago
      Correct, scheme is like a minimal flavor lisp.

tathougies 8y ago

Actually the question should be... why is the lambda calculus such a great programming language in practice? The lambda calculus is unique among other theoretical models of computation (automata, turing machines, etc) in that it is the syntactic and computational basis of several popular languages (lisp, Haskell, ML, etc). In all these languages, you can essentially write lambda calculus terms in a way that you cannot write turing machines in imperative languages.

jakeinspace 8y ago

The same reason a Turing machine (even a finite one) is a silly programming 'language'. It's an abstract model of computation. It just happens that real-world languages based on The Lambda Calculus like Lisp are only a stone's throw away syntactically, whereas the gulf between even assembly and a Turing machine program is quite large. I suppose that's because The Lambda Calculus doesn't aim to describe a pseudo-physical machine, and therefore leaves implementation much more open to interpretation.

dreamcompiler 8y ago

Same reason Turing machines are impractical; it's too low-level. But IMHO starting with "functional composition without side effects" (LC model) and adding the practical stuff gets you a lot farther than adding practical stuff to "everything is a side effect and functions don't exist" (the TM model). Back in the days before parallel programming, large-scale software engineering, networks, cloud computation, etc it wasn't always clear that anything was wrong with the TM model. But given how computing works today it's clear (to me at least) that LC is a much, much better substrate for designing computation.

dreamcompiler 8y ago
As an aside, 1958 was definitely back in those days. But that's when John McCarthy decided the TM model was lacking and said "Hey let's build a programming language on Lambda Calculus instead" and Lisp was born. And that's how John McCarthy was smarter than the rest of us.

kazinator 8y ago

It doesn't have features like global definitions, numbers, strings, I/O, arrays, lists, data structures, ...

mimixco 8y ago

It is. We call it Lisp.