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 statebased)
 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”
 invented by Haskell Curry
 a way to implement recursion in lambda calculus