Lambda Calculus

Introduction

It is also written as λ-Calculus.

It is a notation for expressing computation based on mathematical functions and programs.

λ-Calculus is a mathematical system for studying the interaction of functional abstraction and functional application.

It was introduced by Alonzo Church in the 1930s along with Church Encodings.

Because it directly supports abstraction, it is a universal model of computation that can be used to simulate any Turing machine.

λ-Calculus can encode any computations. It is a basis for functional programming languages.

A single input function can be represented in Lambda term as ‘λx’.

Syntax

A λ-calculus term is

• a variable x€Var, where Var is a countably infinite set of variables.
• An application, a function e0 applied to an argument e1, usually written e0 e1 or e0(e1); or
• a lambda abstraction, an expression λx.e representing a function with input parameter x and body e. Where a mathematician would write x → x2, in the λ-calculus we write λx.x2

Representation

Any function can be represented using ‘ λ’.

For a function f(x) = t,

λx.t

where x is a variable and t is the term.

For a function f(x) = x+1,

λx.x+1

where λx is a function with input x and x+1 is the output or result or function operation term.

For two input function f(x,y) = x+y,

λx.λy.x+y

where λx.λy is a function with two inputs x &y, and the term with x+y.

Example:

Qn. (λx.x+1) 5

Here, ( λx.x+1 ) is a function defined in terms of lambda(‘ λ’) and 5 is the passed value to the function. Let us calculate the output of the function.

(λx.x+1) 5

= 5 + 1

= 6