Maths - λ Calculus

The usual way that we define a function on this site is something like:

s: x -> x*x

That is, the function (named s in this case) that takes x to x*x, that is the square function.

This particular example could be used like this

s(2) = 4

An alternative notation for function definition is lambda calculus. It is called lambda calculus because it is denoted by the Greek character lambda: λ. So the above example would be written:

s = λx.x*x

Where the character(s) between 'λ' and '.' is (are) the variable(s). So this function takes whatever the value of x may be and replaces it with x*x in this example. This is known as 'binding' the value of x and x is known as a bound variable.

One of the advantages of this notation is that, when used in a computer program, it can define the function in the place where it is being used rather than have it defined separately from where it is used. That we don't need to name the function, it is an 'anonymous' function.

So ( λx.x*x) 2 has the value 4. That is the square function applied to the value 2.

In some notations and computer languages (such a lisp) this would be written:

( λx.x*x 2 )

That is: the function and its arguments are all written inside the brackets. Perhaps the safest way to avoid any confusion is to write it like this:

( (λx.x*x) 2 )

An advantage of defining and using the function in the same place like this that we can nest lambda functions within other lambda functions to give us second order logic.

Functions of Multiple Variables and Currying

We can denote a function of multiple variables like this:

λxy.x*x + 3*y

which returns x squared plus 3 times y.

That is several bound variables (in this case x and y) can be placed between 'λ' and '.'.

However this is not strictly nessecary because a function of multiple variables can always be converted into a function of a single variable by Currying. So the function above is equivalent to:

λxy.x*x + 3*y
= λx.(λy.x*x + 3*y)

That is, a single variable function that returns a function that then gives the value required. In the general case we have:

λxy...z.M = λx.(λy. ... (λy.M) ...)

where M is some expression of xy...z.

Strictly I shouldn't use '=' but syntactic identity instead.

Nested Lambda Expressions

We can have multiple variables, not all variables need to be bound λ expressions, as a particular variable is bound by a λ expression then the dimension of the function is reduced. For example we might have a function of 3 variables x,y and z so we can think of this as a 3-dimensional function. If this is wrapped in an expression like λx.(...) then x will be bound. So we can think of this as taking a function of 3 variables and returning a function of 2 variables. We can then wrap thisin an expression like λy.(...) and then we will have a function of 1 variable.

Bound and Free Variables

 

Program Examples

Haskell

  example: lambda function for 'square'
(\x -> x*x)
Prelude> (\x -> x*x) 3
9
Prelude> 
  

In Haskell the character '\' represents λ

 


metadata block
see also:
Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

cover Modern Graph Theory (Graduate Texts in Mathematics, 184)

Terminology and Notation

Specific to this page here:

 

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2016 Martin John Baker - All rights reserved - privacy policy.