What is Lambda Calculus

Lambda Calculus is a simple and very sparse notation for representing and applying functions.

The format is:

λx.x

Where

  • λ signifies it is a Lambda function
  • The x before the period represents the input to the function
  • The function body follows the period

So λx.x is the equivalent of:

function(x) {
  return x
}

or

x => x

(To type a λ on OSX hit cmd ctrl space and search for lamda with no ‘b’)

Lambda Calculus consists of:

  • variables (which can only contain lambdas)
  • lambdas (anonymous functions)
  • application of functions to variables and other functions

So no data types, no numbers or strings directly but we can represent numbers and strings with pure functions.

  • lambdas have an arrity of one (meaning they can only take one parameter)
  • working with more than one parameter is done by currying: λx.λy. x(y) The first lambda takes x and returns a function that takes y, applies x to y and returns the result.

Suprisingly with this sparse notation we can represent anything that can be computed although, in my mind at least, it may not be the most maintainable representation.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.