Combinatory Logic Tutorial

λ-reduction is a complicated syntactic transformation whose complete and explicit description is quite complex, and whose execution is full of subtle pitfalls that catch even experienced semanticists. You might think, therefore, that the popularity of the λ-calculus is due to there being no simpler alternative.

But you would be wrong. Combinatory Logic (CL), invented by Shoenfinkel and developed by Curry and others in the 1920's (note: before the λ-calculus!), is equivalent in expressive power to the lambda calculus, but much simpler. The language contains three special symbols ("S", "K", and "I"), along with parentheses and variables (restricted here to single characters, e.g., "x" or "y"). Any expression can be combined with any other expression:

(((SK)K)(yS))
By convention, combination is left-associative, so the above can be written equivalently as
SKK(yS)
Instead of alpha, beta, and nu reduction, there are two essential rules of inference:
KXY ==> X
SXYZ ==> XZ(YZ)
where "X", "Y", and "Z" are metavariables ranging over arbitrary expressions.

If it helps, the meaning of "K" can be thought of as "(λ x (λ y x))", the meaning of "S" can be thought of as "(λ x (λ y (λ z ((x z)(y z)))))". The other special symbol, "I", can be thought of as (λ x x), but can also be defined as SSK:

SKKX ==> KX(KX) ==> X
Since this derivation works for any expression X, SKK is the identity function.


Done.

Any expression in the lambda calculus can be converted.

Logic with just one paren symbol and just one operator.