78

To all the people who know lambda calculus: What benefit has it bought you, regarding programming? Would you recommend that people learn it?

Gordon Gustafson
  • 40,133
  • 25
  • 115
  • 157
TraumaPony
  • 10,742
  • 12
  • 54
  • 74

11 Answers11

89

The benefit of lambda calculus is that it's an extremely simple model of computation that is equivalent to a Turing machine. But while a Turing machine is more like assembly language, lambda calculus is more a like a high-level language. And if you learn Church encodings that will help you learn the programming technique called continuation-passing style, which is quite useful for implementing backtracking search and other neat tricks.

The main use of lambda calculus in practice is that it is a great laboratory tool for studying new programming-language ideas. If you have an idea for a new language feature, you can add the new feature to the lambda calculus and you get something that is expressive enough to program while being simple enough to study very thoroughly. This use is really more for language designers and theorists than for programmers.

Lambda calculus is also just very cool in its own right: just like knowing assembly language, it will deepen your understanding of computation. It's especially fun to program a universal turing machine in the lambda calculus. But this is foundational mathematics, not practical programming.

Norman Ramsey
  • 198,648
  • 61
  • 360
  • 533
32

If you want to program in any functional programming language, it's essential. I mean, how useful is it to know about Turing machines? Well, if you write C, the language paradigm is quite close to Turing machines -- you have an instruction pointer and a current instruction, and the machine takes some action in the current state, and then ambles along to the next instruction.

In a functional language, you simply can't think like that -- that's not the language paradigm. You have to think back to lambda calculus, and how terms are evaluated there. It will be much harder for you to be effective in a functional language if you don't know lambda calculus.

EfForEffort
  • 55,816
  • 4
  • 36
  • 41
  • 79
    I sincerely doubt it is essential for functional programming (as I noted in my own answer). Also, Turing machines are practically never (if ever) used to understand imperative programming. – mweerden Sep 22 '08 at 13:41
  • 1
    I think this is a matter of "those who do not understand LISP are doomed to reinvent it", where even though I imagine vast majority of programmers come from heavy imperative backgrounds where the notion of loops for summation is common, and the idea of array reduction didn't exist. In turn we all kind of try to gain more control and discipline over our computations and the only reasonable direction to go is the direction of lambda calculus, in turn reinventing it, or digesting it from programming languages that don't teach you lambda calculus but you just "get" a lot of it. – Dmytro Sep 03 '16 at 07:48
  • @Dmitry I mean, the idea of lambda is so convenient that many of us tend to just "reinvent it", ESPECIALLY if you are a meta-programmer that writes preprocessors for their code to turn "for" loops into "for in" loops via simple transformations, or come to think of it, lambda calculus in general addresses many things you think about while writing preprocessors naturally, as all you think about is transformations and how to chain them as long as possible, preferably to the very end. Without lambdas, you simply get overwhelmed by complexity and everything falls apart, or is unmanagable. – Dmytro Sep 03 '16 at 07:53
24

To be honest, learning lambda calculus before functional programming has made me realize that the two are as unrelated as C is to any imperative programming.

Lambda calculus is a functional programming language, an esoteric one, a Turing tarpit if you like; accidentally it's also the first.

The majority of functional programming languages at all do not require you to 'learn' lambda calculus, whatever that would mean, lambda calculus is insanely minimal, you can 'learn' its axioms in an under an hour. To know the results from it, like the fixedpoint theorem, the Church-Rosser Theorem et cetera is just irrelevant to functional programming.

Also, lambda-abstractions are often held to be 'functions', I disagree with that, they are algorithms, not functions, a minor difference, most 'functional languages' treat their functions more in the way classical mathematics does.

However, to for instance effectively use Haskell you do need to understand certain type systems, that's irrespective of lambda calculus, the System F type system can be applied to all 'functions' and requires no lambda abstractions at all. Commonly in maths we say f : R^2 -> R : f (x) = x^2. We could've said: f (x) = x^2 :: R -> R -> R. In fact, Haskell comes pretty close to this notation.

Lambda calculus is a theoretical formalism, Haskell's functions are really no more 'lambda abstractions' than f : f(x) = x^2 really, what makes lambda abstractions interesting is that it enables us to define what are normally seen as 'constants' as 'functions', no functional language does that because of the huge computational overhead. Haskell and alike is just a restricted form of System F's type system applied to functions as used in everyday classical maths. Functions in Haskell are certainly not the anonymous formally symbolic reduction-applicants as they are in lambda-calculus. Most functional programming languages are not symbolic reduction-based re-writing systems. Lisps are to some degree but that's a paradigm on its own and its 'lambda keyword' really doesn't satisfy calling it lambda calculus.

Zorf
  • 6,334
  • 2
  • 29
  • 24
16

I think the use of lambda calculus with respect to programming in practice is that it is a quite minimal system that captures the essence of abstraction (or "anonymous functions" or closures, if you will). Other than that I don't think it is generally essential except when you need to implement abstraction yourself (as Tetha (114646) mentioned).

I also completely disagree with Denis Bueno (114701) who says that it is essential for functional programming. It is perfectly well possible to define, use or understand a functional language without any lambda calculus at all. In order to understand the evaluation of terms in functional languages (which, in my opinion, somewhat contradicts the use of a functional language) you will most likely be better of learning about term rewrite systems.

Community
  • 1
  • 1
mweerden
  • 13,619
  • 5
  • 32
  • 32
14

I agree with those that say it is theoretically possible to learn functional programming without learning the lambda calculus—but what's the advantage of not learning the lambda calculus? It's not as if it takes a big investment of time.

Most likely, it will help you understand functional programming better. But even if it doesn't, it's still a cool thing worth learning. The Y-combinator is a thing of beauty.

Keith Pinson
  • 7,835
  • 7
  • 61
  • 104
Michael Dorfman
  • 4,060
  • 1
  • 22
  • 29
  • 3
    The lambda calculus is without any doubt a wonderful thing well worth learning. However, it truly surprises me to read these claims that it is helpful (or even essential) in understanding functional programming. I have a hard time figuring out how it would help. Am I missing something here? – mweerden Sep 26 '08 at 11:50
  • 10
    +1 for being the only answer to mention the word "beauty." The practicality debate aside, it is possibly the most beautiful field of mathematics I have yet studied. – Keith Pinson Oct 25 '11 at 03:19
12

If you only want to be a technician and write programs to do things, then you don't really need to know lambda-calculus, finite-state machines, pushdown automata, regular expressions, context-free grammar, discrete mathematics, etc.

But if you have curiosity about the deeper mysteries underlying this stuff, you can start to wonder how these questions might be answered. The concepts are beautiful and will expand your imagination. I also think they, incidentally, make one a better practicioner.

What got me hooked was Minsky's book Computation: Finite and Infinite Machines.

Mike Dunlavey
  • 40,059
  • 14
  • 91
  • 135
  • 2
    You do not **have** to know "finite-state machines, regular expressions, context-free grammar", but these are very useful in many programing tasks. I would be 1/100 effective without these. E.g. don't you use GREP? – TFuto Aug 04 '14 at 12:39
  • @TFuto: I'm on windows. I *used* to have grep, but with these infernal upgrades, stuff that used to work doesn't any longer :) Also, those formal concepts are more on the inventive side of C.S., as opposed to the conformist side. They get me in trouble, [*like here*](http://stackoverflow.com/a/24875909/23771). – Mike Dunlavey Aug 04 '14 at 13:01
  • 1
    I suggest you revisiting REGEXPs, e.g. in Java. That is a very expressive thing and if used wisely, a big timesaver. By the way, you can use GREP on Windows with Cygwin or compile it with MinGW. And if you have a bit more time, understanding e.g. ANTLR is a huge jump in development power. You can generate parsers for a large set of languages... So you can replace manual input parsing and validation. – TFuto Aug 05 '14 at 13:14
5

The lambda calculus is a computational model, just like the turing machine. Thus, it is useful if you need to implement a certain evaluator for a language based on this model, however, in practice, you just need the basic idea (uh. place argument semantically correct in the body of a function?) and that's about it.

Tetha
  • 4,826
  • 1
  • 16
  • 17
4

One posible way to learn lambda calculus is

http://en.wikipedia.org/wiki/Lambda_Calculus

Or, if you want more, here is my blog dedicated to lambda calculus and stuff like that

http://weblogs.manas.com.ar/lziliani/

As every abstraction of computations, with lambda calculus you can model stuff used in most programming languages, like subtyping. For more about this, one of the best books with practical uses of lambda calculus in this sense is

http://www.amazon.com/Types-Programming-Languages-Benjamin-Pierce/dp/0262162091/ref=sr_1_1?ie=UTF8&s=books&qid=1222088714&sr=8-1

  • 3
    For me the book [Introduction to Functional Programming through Lambda Calculus](http://www.amazon.com/Introduction-Functional-Programming-Calculus-Mathematics/dp/0486478831/ref=pd_sim_b_1) is the best starting place. – Edwin Dalorzo Oct 15 '12 at 12:45
4

I found that the Lambda calculus was useful for understand how functional programming worked on a deeper level. Especially how to implement functional languages.

It has made it easier for me to understand advanced concepts like type-systems and evaluations strategies (e.g. call by name versus call by value).

I don't think one needs to know anything about the Lambda calculus to use basic functional programming techniques. However understanding the lambda calculus makes it easier to learn advanced programming theory.

cdiggins
  • 17,602
  • 7
  • 105
  • 102
3

I'd also like to mention that if you're doing anything in the area of NLP, lambda calculus is at the foundation of a massive body of work in compositional semantics.

Robert Elwell
  • 6,598
  • 1
  • 28
  • 32
0

The benefits for me is a more compact synergistic programming. Stuff tends to flow horizontally more than vertically. Plus it is very useful for prototyping simple algorithms. Don't know if I am using it to its full potential but I find it very useful.

Nick Berardi
  • 54,393
  • 15
  • 113
  • 135