14

I am starting my first year (in college) in Computer Science next year and I write mostly in C (if that is to matter). I have tried searching but most of what I find assumes knowledge of lambda calculus. Why is lambda calculus considered so much more useful than single variable calculus in prograrmming? Is there a relationship between lambda expressions and functional programs? Was it Alonzo Church's work on lambda calculus that influenced the development of programming languages?

Everyone outside school keeps buzzing about it and I have no clue what they will be talking about even though I am eager to learn it and see how it directly relates to my programming and understanding of programming languages.

Tom Au
  • 893
  • 7
  • 17
RonaldMunodawafa
  • 661
  • 1
  • 6
  • 12
  • 2
    This question will be better answered at https://cs.stackexchange.com/. –  Oct 18 '14 at 22:14
  • @ChrisF. Maybe this question is a better fit for one of the computer science sites. If not, I tried to narrow it, and wonder if it can be re-opened in its current form. – Tom Au Oct 20 '14 at 00:07
  • Mathematica has lambda calculus baked in noticed nobody mentioned it. – William Feb 03 '17 at 01:26

2 Answers2

26

The Lambda Calculus is interesting, elegant, and makes it much easier to understand functional programming languages. However, you won't encounter the LC in a typical CS Bachelor course, so you don't have to learn it right now – I would recommend to experiment with functional languages first before revisiting the Lambda Calculus. I believe OCaml is a good starting point into functional programming for a C programmer, and that Scheme is a good starting point to dive into the Lambda Calculus.

The Lambda Calculus is not associated with Calculus (which ought to be called Analysis instead). In general, a calculus is a “formal system”, i.e. a set of rules to do something. While Differential Calculus provides rules regarding the change of values, the rules of the Lambda Calculus describe computation itself. From this set of very basic rules, we can build arbitrary computations, data representations such as booleans, integers, or lists, and even control flow constructs such as conditionals or loops. The LC is equivalent to Turing Machines, but either model has different strengths.

Lambda Calculus had an immense impact on programming languages. The second high-level language to be implemented was Lisp, which can be understood as a direct encoding of the LC into a programming language. This “functional programming” has immense effect on the evolution of programming languages. Features such as anonymous functions, function pointers, closures (nested functions), garbage collection, variable scope, metaprogramming, advances in type systems, type inference, interpreted languages, dynamically-typed languages, object-oriented programming are all owed to a large part to the functional programming branch of programming languages. There's a joke that any new (non-academic) programming language only adds features that Lisp has already had for decades.

Beyond that, the Lambda Calculus and other related calculi are indispensable tools in programming language theory and in certain compiler construction techniques.

Any language that has anonymous functions which behave as closures and can be passed around freely immediately contains an encoding of the lambda calculus. Anonymous functions correspond a lambda expressions, except that in the LC functions always have exactly one argument. However, any Turing-complete language is equivalent to the LC, so the LC can always be implemented on top of such languages. This tends to happen in rule-matching systems or overly intelligent configuration formats, giving rise to “Greenspun's tenth rule” (in jest – mostly): “Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.”

amon
  • 132,749
  • 27
  • 279
  • 375
  • This is a better answer than the one I had selected before. Your answer really hits home. This is exactly what I was looking for! – RonaldMunodawafa Oct 18 '14 at 22:29
  • "... except that in the LC functions always have exactly one argument": Is this feature called **currying** or is it at least related to it? – Giorgio Oct 19 '14 at 10:31
  • @Giorgio Currying is different, but related. LC doesn't have multi-argument functions, but those can simply be encoded as nested functions that take one argument each. Example using ML notation: `x = fn (a, b, c) => a + b + c` (type `int * int * int -> int`, invocation `fn (1, 2, 3)`) can be transformed into `x = fn a => fn b => fn c => a + b + c` (type `int -> int -> int -> int`, invocation `((x 1) 2) 3` – parens optional in ML). Now instead of supplying all three arguments, we can also only provide two: `plus3 = x 1 2` which has type `int -> int`. This is partial application/currying. – amon Oct 19 '14 at 11:36
  • I thought currying meant having all functions take only one argument (as in LC). – Giorgio Oct 19 '14 at 14:50
8

Lambda calculus has nothing to do with differential/integral calculus. Calculus in the most generic sense of the word just means a system of calculation.

At a very high level lambda calculus is a model of computation the same way a turing machine is a model of computation. The reason programming language researchers study lambda calculus is because as a model it has strong connections to formal methods in mathematics like logic and category theory. So methods from those domains can be applied to studying various aspects and extensions of lambda calculus which in turn helps design better programming languages with certain properties.

The most direct influence of lambda calculus in programming languages usually appears in the form of first class functions and closures. C does not have support for closures and so you'll need to explore the concept in a more high-level language like Lisp, Python, Ruby, JavaScript, etc. Historically Lisp is considered the first concrete implementation of lambda calculus as a programming language.

  • 1
    You might want to mention specific languages that are quite close to lambda calculus, e.g. Lisp. – Giorgio Oct 18 '14 at 22:09
  • 1
    I am still learning Scheme using SICP and hope I will learn more about this area. Thanks for your elaborate answer and suggestion. – RonaldMunodawafa Oct 18 '14 at 22:18