I'm starting an undergraduate computer science course next fall, but I can't really understand λ-calculus in the context of functional programming. I may be misinterpreting this completely, but based on this definition from the Stanford Encyclopedia of Philosophy, it's just another notation for functions.

If it is just that, why is it advantageous to use λ-calculus over regular function notations to calculate algorithm run time?

  • 5
    $\begingroup$ It's not "just another notation for functions" but "the first notation for functions". $\endgroup$ – Andrej Bauer Apr 20 '13 at 18:02
  • $\begingroup$ Thanks for the suggestion, @Kaveh. I'll keep it in mind for future posts, however mhelvens' answer is excellent, so no need for a crosspost. $\endgroup$ – Jules Mazur Apr 20 '13 at 23:14
  • $\begingroup$ It's a formally defined body of objects. I don't see what your exact problem is. $\endgroup$ – Raphael Apr 21 '13 at 15:07
  • $\begingroup$ I did not really understand the terminology or why things were done they are done in functional programming until I learned about lambda calculus. It makes software constructs seem far less arbitrary. $\endgroup$ – dansalmo Apr 26 '13 at 1:11

In computer science we want to analyze and understand source-code with mathematical rigour. That's the only way to prove interesting properties (such as termination) with absolute certainty. For that we need a language with a very well-defined meaning for every construct.

In theory this could be any language with a good formal semantics. But to make things less complicated and less prone to error, it's best to use a language that is as simple as possible but still able to express any program (i.e. is Turing complete). For reasoning about imperative code, there are Turing machines. But for reasoning about functional programming, there is the $\lambda$-calculus.

The basic $\lambda$-calculus is like a functional programming language, but with a lot of 'baggage' taken out. It's not important that this be a nice language to actually write programs in, nor that it be an efficient language. Just that it is simple and expressive. For example, we don't need loops, because we can simulate them with recursion. And we don't need functions with multiple parameters, since we can simulate them with Currying.

Now, at some point you may want to prove properties about constructs that are not part of the basic (untyped) $\lambda$-calculus. That's why computer scientists have extended it in different directions over the years. For example, to reason about type-systems there are a great many variations of typed $\lambda$-calculi.

  • 3
    $\begingroup$ imo, some computer science might be about understanding source code, but saying that's true in general sounds like saying physics is about understanding rockets with mathematical rigor. computer science is about computation. A related complaint is that the efficiency of the language does matter if you want to study efficiency and not well-formed source code. In that sense, it's probably better to think about TMs as a way to think about efficiency rather than a model of imperative languages (and for both purposes the word-RAM might be a better choice) $\endgroup$ – Sasho Nikolov Apr 20 '13 at 21:22
  • $\begingroup$ btw what I wrote above does not mean I do not like your answer :) $\endgroup$ – Sasho Nikolov Apr 20 '13 at 21:54
  • $\begingroup$ Agreed. ;-) Fixed. $\endgroup$ – mhelvens Apr 21 '13 at 7:54
  • 1
    $\begingroup$ Turing machines are atrocious at reasoning about imperative code, it's much easier to use a toy language like a simple while type language. stackoverflow.com/questions/507310/the-while-language. Turing machines remain very useful for insights in complexity theory. $\endgroup$ – cody Sep 17 '13 at 19:28

strangely a lot of books talk about $\lambda$ calculus without mentioning Lisp or Scheme, modern programming languages based on it, leaving students unfortunately with the idea that its old and abstract and mostly theoretical. studying Lisp or Scheme can be a great angle to immensely help understand $\lambda$ calculus.

If it is just that, why is it advantageous to use λ-calculus over regular function notations to calculate algorithm run time?

there are many advantages to using Lisp or functional programming and calculating algorithm run time is just one possibility (although it would be helpful if you cited a ref for that). since its already in functional notation sometimes determining the formulas for run time via induction or recurrence relations may have a stronger or more obvious relationship to the original code. other types of analysis of the algorithm are simplified also.

another main advantage is syntactical simplicity. parsers for other languages are very complex but the Lisp parsers are very simple. so Lisp is a great language to study the theory of parsing in.

another key aspect is analyzing software more from a logical or mathematical lens/view rather than a "computer-scientific" perspective.

as the other answer points out, Lisp is all about recursion instead of iteration and recursion is very much at the heart of CS.

more advocation for a "$\lambda$-view" and detail can be found in [1], a free online and semifamous ref.

[1] Structure & Interpretation of computer programs, by Abelson & Sussman


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.