6 ms·

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 o

by pwm 7y 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 7y 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 7y 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 7y 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 7y 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 7y 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 7y ago
    Scheme is a Lisp. And so is Clojure and probably 20 others. Wolfram Language is a Lisp with M-expressions (gag).
    - vertline3 7y ago
      Correct, scheme is like a minimal flavor lisp.

by pwm 7y ago

galaxyLogic 7y 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 7y 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 7y 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 7y 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 7y 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 7y ago
  Scheme is a Lisp. And so is Clojure and probably 20 others. Wolfram Language is a Lisp with M-expressions (gag).
  - vertline3 7y ago
    Correct, scheme is like a minimal flavor lisp.