Lambda Calculus and Combinatory Logic


The lambda calculus is the calculus or logic of (anonymous) functions. Examples of very simple functions in mathematics include double[x] which takes 1 to 2, 2 to 4 etc and square[x] which takes 1 to 1, 2 to 4 etc. And there are functions in daily life, for example motherOf[x] takes one person to another. The example functions have explicit names, eg 'double'. Lambda calculus deals with functions, but typically without giving the functions names. The functions are anonymous functions.

Three of many academic areas that lambda calculus features prominently in are:

  • [Philosophy: Church's thesis to characterize the nature of computable functions] The lambda calculus is one means of capturing the pre-theoretical notion of computable function (all computable functions can be computed within the lambda calculus).
  • [Computer Science: Functional programming and programming languages and their semantics] Lambda calculus provides the theoretical underpinning for many areas within computer science.
  • [Philosophical and Linguistic Semantics: The logic and analysis of reasoning, speech, and grammars (especially, possible world semantics)] Often typed lambda calculus is put to work here.