2 ms·

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 sys

by 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

by OskarS 7y ago

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