The Lambda Calculus for Absolute Dummies (like myself)
lambda-calculuscomputation-theoryfunctional-programmingformal-systems
Abstraction: Beginner tutorial on lambda calculus and computation theory
Key points:
- Lambda calculus invented mid-1930s by Alonzo Church; the only operation is beta reduction (cut and paste of bound variables into function bodies)
- Three constructs: variables (single letters), parentheses for grouping, and lambda abstractions (λvar.body)
- Church numerals encode natural numbers: 0 = λsz.z, 1 = λsz.s(z), 2 = λsz.s(s(z)); addition is automated successor application
- Boolean logic encoded as TRUE = λxy.x, FALSE = λxy.y; AND, OR, NOT, IS-ZERO, GREATER-OR-EQUAL all expressible
- Lambda calculus and Turing Machines are equally powerful (Church-Turing Thesis); every computable system maps to the other
- Lisp was built directly on lambda calculus ideas; the λ notation originated as a typesetter's accident from Alonzo Church's hat-notation
Connections: Alonzo Church · Lambda Calculus · Computability Theory · Functional Programming
Source: http://palmstroem.blogspot.com/2012/05/lambda-calculus-for-absolute-dummies.html