Church encoding in Scheme: Desugaring numbers, lists, booleans, conditionals and recursion into lambda

A compiler will often desugar complex language constructs into simpler yet equivalent language constructs.

For example, a C compiler might translate for loops into while loops.

Desugaring simplifies compilation by eliminating cases in functions that operate on syntax.

In languages which contain the λ-calculus as their core, the desugaring process, if taken to its limit, will desguar every program into a language with only three expression types: variable references, single-argument anonymous functions and function calls.

In other words, the following subset of Scheme is Turing-complete:

 <exp> ::= <var>
        |  (lambda (<var>) <exp>)
        |  (<exp> <exp>)

Unbeknownst to many, JavaScript also contains the lambda calculus, which means the following subset of JavaScript is also Turing-complete:

 <exp> ::= <var>
        |  function (<var>) { return <exp> ; }
        |  (<exp>)(<exp>)

Encodings of high-level constructs in the λ-calculus are Church encodings.

To see how Church encodings work, read and play around with the commented code below.