Church encodings, the U combinator and the Y combinator in JavaScript

Expression closures

Expression closures are available in Mozilla's implementation of JavaScript.

An expression closure allows you to write an anonymous function as:

 function (formals) exp

instead of:

 function (formals) { return exp ; }

Because it substantially simplifies the code, I'll use expression closures.

A universal subset of JavaScript

Reflected into JavaScript, the lambda calculus needs four forms:

 exp ::= variable                    [references]
      |  exp(exp)                    [function application]
      |  function (variable) exp     [anonymous functions]
      |  (exp)                       [precedence]

These four forms can simulate arbitrary computation.

To demonstrate this, we'll build well-known programming constructs out of these four.

Currying multi-argument functions

To create multi-argument functions, we can Curry.

A Curried function takes one argument and then returns a function that takes the next argument.

For example, to Curry the function:

 function f(x,y) {
   return x*x + y*y ;
 }

it becomes:

 function fC(x) {
   return function (y) {
     return x*x + y*y ;
   } ;
 }

so that:

 fC(a)(b) == f(a,b)

Currying is a broadly useful technique, and it's possible to curry and uncurry functions via combinators:

  function curry(f) {
    return function (x) function (y) f(x,y) ;
  }


  function uncurry(f) {
    return function (x,y) f(x)(y) ;
  }

so that curry(f) is fC and uncurry(fC) is f.

A void value

Sometimes, it's useful to have a well-defined void value, to be used in situations where the value will be ignored.

The identity function suffices:

 var VOID = function (x) x ;

The game: Encoding data as computation

To add data structures to the language, we need encode them as functions.

Thus, the key is to encode data according to how it will be used.

Booleans and conditionals

Booleans are used to effect branching.

Thus, Booleans should be encoding as branching.

A Boolean will consume two functions---one to execute if the value is true, and another to execute if the value is false.

Thus:

 var TRUE  = function (onTrue) function (onFalse) onTrue(VOID) ;
 var FALSE = function (onTrue) function (onFalse) onFalse(VOID) ;

which means that IF becomes:

 var IF = function (test)
            function (onTrue) 
              function (onFalse) 
                test(onTrue)(onFalse) ;

For instance:

 IF (TRUE) (function (_) true) (function (_) false)

yields true.

So, if we wanted to, we could convert Church Booleans back into JavaScript Booleans at the end of a computation:

 function boolify (churchBoolean) {
   return churchBoolean (function (_) true) (function (_) false) ;
 }

Numerals

There are several reasonable ways to encode numerals in the lambda calculus---because there are several ways to use numbers.

One of the most common uses for numbers is iteration---to peform a computation n times.

Church numerals take this iterative interpretation.

A Church numeral takes a function f and zero element z upon which to iterate the application of that function.

That is, the nth Church numeral computes fⁿ(z), where fⁿ is iterated function application:

f⁰(x) = x
fⁱ(x) = f(f^i-1(x))

If we allow ourselves to cheat, we can write a function that creates the nth Church numeral:

 function numeral(n) {
   return function (f) function (z) {
     for (var i = 0; i < n; i++) 
       z = f(z) ;
     return z ;
   } ;
 } ;

With that in mind, zero is easy to write:

 var ZERO = function (f) function (z) z ;

And, we can create SUCC, a function that adds one to a Church numeral, by adding one more round of iteration:

 var SUCC = function (n) function (f) function (z) f (n (f) (z)) ;

 var ONE = SUCC(ZERO) ;

 var TWO = SUCC(ONE) ;

To extract Church numerals at the end of a computation, we execute them:

 ZERO (function (x) x+1) (0) == 0

 (SUCC (SUCC (ZERO))) (function (x) x+1) (0) == 2

Or, to make things more convenient, we can write a function to do this:

 function numerify (n) {
   return n (function (x) x+1) (0) ;
 }

Remarkably, we can perform the standard arithmetic operations directly in Church numeral form:

var PLUS = function (n) 
            function (m)
             function (f) 
              function (z)
               (n(f) (m(f)(z))) ;

var MULT = function (n)
            function (m)
             function (f)
              function (z)
               (n (m(f)) (z)) ;

// Substract 1:
var PRED = function (n)
            function (f)
             function (z)
             ((n (function (g) (function (h) h(g(f)))))
              (function (u) z))(function (u) u) ;

var SUB = function (n) 
           function (m)
            (m(PRED))(n) ;

And, we can create a Church predicate that checks for 0:

 var ZEROP = function (n) n (function (_) FALSE) (TRUE);

Check out these numeral operations:

 var FOUR = numeral(4) ;

 var SIX = numeral(6) ;

 numerify(PLUS (FOUR) (SIX)) == 10 ;

 numerify(MULT (FOUR) (SIX)) == 24 ;

 numerify(SUB (SIX) (FOUR)) == 2 ;

Lists

As with numbers there are several ways to encode lists.

We'll encode lists as objects that destructure themselves:

// The empty list:
var NIL = function (onEmpty) 
           function (onPair)
            onEmpty(VOID) ;

// Construct a new list:
var CONS = function (hd) 
            function (tl)
             function (onEmpty) 
              function (onPair)
               onPair(hd)(tl) ;

// Get the head of a list:
var HEAD = function (list)
            list (VOID) (function (hd) function (tl) hd) ;

// Get the tail of a list:
var TAIL = function (list) 
            list (VOID) (function (hd) function (tl) tl) ;

// A predicate to test for the empty list:
var NILP = function (list) 
            list (function (_) TRUE) (function (_) function (_) FALSE);

The following now works:

 boolify(NILP (NIL)) == true ;

 boolify(NILP (CONS (VOID) (VOID))) == false ;

 var list = CONS (ZERO) (CONS (ONE) (NIL)) ;  // [0, 1]

 numerify(HEAD (list)) == 0 ;

 numerify(HEAD (TAIL (list))) == 1 ;

 boolify(NILP (TAIL (TAIL (list)))) == true ;

Let-binding

JavaScript lacks proper lexical scoping in its blocks.

But, it's not hard to add it by using the encoding for let-bindings.

In a language like Scheme, the let form introduces new lexical scope:

 (let ([x 10])
   (let ([x 3])
    (print x)) ; prints 3
   (prints x)) ; prints 10

In JavaScript, the equivalent with blocks does not work:

 { 
   var x = 10 ;
   {
      var x = 3 ;
      console.log(x) ; // prints 3
   }
   cosnole.log(x) ; // prints 3
 }

But, let forms desugar into immediately applied anonymous functions:

 (let ([var exp]) body)

  =>

 (function (var) body)(exp)

Using this transform, we could rewrite the earlier block example:

 (function (x) {
   (function (x) {
     console.log(x) ;
   })(3) ;
   console.log(x) ;
  })(10) ;

The U combinaitor

The Y combinator gets a lot of attention as the way to do recursion in the lambda calculus.

But, it's not the only way to do it.

The U combinator is much simpler, and it gets the job done too.

To get a sense of how it works, let's examine the smallest non-terminating program:

 (function (f) f(f)) (function (f) f(f))

This program, known as Ω, is applying the same function to itself, indefinitely.

If we factor out the function that applies its argument to itself as U, it's much easier to write Ω:

 var U = function (f) f(f) ;

 U(U) ; // Never terminates (or it stack overflows)

Self-application of a function to itself creates a way to get a handle on that function.

Once a function can get a handle on itself, recursion is easy.

For example, here's a self-contained non-recursive expression that computes factorial:

 U(function (h) function (n) (n <= 1) ? 1 : n*(h(h))(n-1))

When a function wrapped in self-application needs to generate another instance of itself, it uses self-application once more--hence the internal call to h(h) where you would expect to see fact.

Try it out:

 U(function (h) function (n) (n <= 1) ? 1 : n*(h(h))(n-1))(5) == 120

The Y combinator

The Y combinator is the more popular way to realize recursion in the lambda-calculus.

There's a much lengthier blog post on the Y combinator in JavaScript (plus an application to memoization), if you're interested in the details.

The short version is that the Y combinator computes the fixed point of a functional -- a function that consumes (and in this case, produces) another function.

The trick is to define recursive functions as the fixed points of non-recursive functions, and then to write a fixed-point finder -- the Y combinator -- without using recursion.

For a function f, x is a fixed point of f if x = f(x).

Now consider the function F:

 var F = function (f) function (n) (n <= 1) ? 1 : n*f(n-1) ;

The fixed point of F is factorial.

That is, if fact is a function that computes factorial, then F(fact) is also a function that computes factorial: fact = F(fact).

If we had a magic function, Y, that computed the fixed point of another function, we could use it to define factorial:

 var factorial = Y(F) ;

But, Y is not magical. It exists.

A fixed point finder, fix, given a function f, computes a fixed point:

f(fix(f)) = fix(f)

This is not just a property of fix; this is a recursive definition of fix.

Let's flip it around:

fix(f) = f(fix(f))

Now, let's call fix Y, and implement this as a recursive function in JavaScript:

 function Y(F) {
   return F(Y(F)) ;
 } 

Of course, if we tried to execute this function, it would immediately diverge -- it immediately recurs on itself.

But, let's continue.

We can pull out the implicit definition:

 var Y = function (F) F(Y(F)) ;

Now wrap (η-expand) the internal recursive call, so that the function does not immediately recur:

 var Y = function (F) F(function (x) Y(F)(x)) ;

At this point, it actually starts working; try this:

 var yfact = Y(function (f) function (n) (n <= 1) ? 1 : n*f(n-1)) ;

 yfact(5) == 120

Of course, we haven't eliminated recursion from the Y combinator.

But, that's easy enough to do with the U combinator:

 var Y = U(function (f) function (F) F(function (x) f(f)(F)(x))) ;

And, then we can expand the U combinator away:

 var Y = (function (f) function (F) F(function (x) f(f)(F)(x)))
          (function (f) function (F) F(function (x) f(f)(F)(x))) ;

Example

Putting it all together, we can define factorial using Church Booleans, Church numerals and the Y combinator:

 var CFACT = Y(function (fact)
                function (n)
                 (IF (ZEROP (n))
                   (function (_) ONE) 
                   (function (_) MULT (n) (fact(PRED(n)))))) ;

 
 numerify(CFACT(numeral(5))) == 120

Code

You can download all of the code in one file.

Related pages

---