The lambda calculus is Turing-complete, so the following language is sufficient to encode any computable function: exp ::= var | (lambda (var) exp) | (exp e

The lambda calculus is Turing-complete, so the following language is sufficient to encode any computable function: exp ::= var | (lambda (var) exp) | (exp exp) Check out http://matt.might.net/articles/church-encodings-demo-in-scheme/ http://matt.might.net/articles/church-encodings-demo-in-sche... To see how to build numbers, booleans, lists, conditionals and recursion out of pure lambdas. Even cooler is that these tricks work in languages like JavaScript too: http://matt.might.net/articles/implementation-of-recursive-fixed-point-y-combinator-in-javascript-for-memoization/ http://matt.might.net/articles/implementation-of-recursive-f...