# Lambda calculus

• Lambda calculus was invented by Alonzo Church

• Lambda calculus concerns the nature of a function from a computational perspective

• “what is a function, from a computational perspective?”
• Analogous to Turing’s state machine, except functional (not state-based)

• any Turing machine program can be converted into a lambda calculus program
• A function is a small machine that takes an input, processes it, and produces an output

• Functions are “black boxes”, so we don’t know or care about what happens inside, just what goes in and comes out

• Functions are pure, so they have no internal state or side effects, simply producing an output from an input

## “Church” notation

overview:

$\lambda~input~.~output(s)$

an increment function:

$\lambda x.x+1$

a sum function (note that this takes two inputs):

$\lambda x.\lambda y.x+y$

demonstration of increment function:

$(\lambda x.x+1)~5\\ \rarr~~ \lambda 5.5+1\\ \rarr~~ 6$

encoding “true” and “false”:

$True ~\rarr~~ \lambda x.\lambda y.x\\ False ~\rarr~~ \lambda x.\lambda y.y$

“not” operator (note, FALSE and TRUE are outputs):

$\lambda b.b ~~FALSE~~TRUE$

applying the “not” operator to TRUE:

$(\lambda b.b ~~FALSE~~TRUE) ~~TRUE$

• expanded:

$\rarr ~~\lambda (\lambda x.\lambda y.x).\lambda x.\lambda y.x ~~FALSE~~TRUE$

• result:

$\rarr ~~FALSE$

• These definitions of true and false functions represent the concept of choosing between one thing and another

• They can be used to implement all of the logical operators, not just the “not” operator

• The most popular lambda calculus expression is the “Y combinator