A mathematical model where the only terms are functions ("lambdas"), variables, and function calls ("applications"). Somehow this can compute anything that can be computed. -- Syntax -- Lambda: `(λV.E)` (backslash works too) Variable: `V` (single characters only) Application: `A B` 1. It's a good idea to surround a lambda with parentheses `()` when you're applying it. 2. The `V[123]` syntax in the output represents variables renamed to avoid name collisions, and does not currently work as input. -- Examples -- Infinite loop = (λx.x x) (λx.x x) True = λx.λy.x False = λx.λy.y NOT = λb.((b λx.λy.y) λx.λy.x) OR = λa.λb.((a λx.λy.x) b) AND = λa.λb.((a b) λx.λy.y) Zero = False = λf.λx.x Successor (+1) = λn.λf.λx.f ((n f) x) Add = λa.λb.λf.λx.(b f) ((a f) x) Multiply = λa.λb.λf.λx.(b (a f)) x Power = λm.λn.n m
My initial attempt involved a data structure similar to cons pairs, containing a type, var-name and two pointers. But it seems putting it all in one list is significantly simpler. May has bugz (had bug)
