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”

  • invented by Haskell Curry
  • a way to implement recursion in lambda calculus