Functional programming in JavaScript (9)

Please take a look at other posts about functional programming in JavaScript:

1. Part 1 - what Functional Programming is about
2. Part 2 - Functional Pipelines
3. Part 3 - the Y Combinator
4. Part 4 - Monads
5. Part 5 - Trampoline
6. Part 6 - Lenses
7. Part 7 - Church encoding (booleans)
8. Part 8 - Church encoding (arithmetics)
9. Part 9 - Church encoding (if, recursion)
10. Part 10 - Church encoding (lists)

We continue our Church encoding of numbers. In the last post we've defined ADD/MUL/POW.

How do we define SUB?

To have SUB, we have to have PRED, the predecessor function. How do we get this?

Turns out, this is tricky. SUCC was about applying a function. How do you un-apply a function?

The solution found by Stephen Klenee in 30s involves pairs and so called sliding window.

Start with a pair of (0,0). Then apply function (a,b) => (b, b+1) to it n times. Then take first element of the pair.

Got it? Let's try for 3. (0,0) -> (0,1) -> (1,2) -> (2,3). First element of the result pair is 2.

To have this in our encoding system, we define some helper functions and then, the PRED. With PRED, we can have SUB:

// --- pairs
const PAIR   = x => y => f => f(x)(y);
const FIRST  = p => p(TRUE);
const SECOND = p => p(FALSE);

// A helper that takes a pair (a,b) and returns (b, b+1)
const PHI = p => PAIR(SECOND(p))(SUCC(SECOND(p)));

// PRED starts at (0, 0), applies PHI 'n' times, then takes the FIRST element
const PRED = n => FIRST(n(PHI)(PAIR(ZERO)(ZERO)));

// SUBTRACT(m)(n) is just applying PRED to m, n times.
const SUB = m => n => n(PRED)(m);

console.log( toInt( PRED(FOUR) ) );
console.log( toInt( SUB(FOUR)(TWO) ) );

We are finally ready to have IF and recursion (using the Y discussed eariler). Note that IF forces an extra computation of its result with (). This is because of the eager evaluation of JavaScript that will force us to define both IF branches as functions (that have to be evaluated). We also define the IS_ZERO predicate and EQUALS (using IS_ZERO and SUB):

// --- IF, with additional ()
const IF = p => a => b => p(a)(b)();

// --- Y (recursion)
const Y = f => (x => x(x))(x => f(y => x(x)(y)));

const IS_ZERO = n => n(x => FALSE)(TRUE);

const EQUALS = m => n => 
  AND (IS_ZERO(SUB(m)(n))) 
      (IS_ZERO(SUB(n)(m)));

And here comes the big moment. We can now use all building blocks together to actually implement a high level recursive function:

// --- factorial!
const FAC = Y(self => n =>
  IF (EQUALS(n)(ONE))               // if n == 1
    (() => ONE)                     //    return 1
    (() => MUL(n)(self(PRED(n))))); //    else return n * fac(n-1)

console.log( toInt( FAC(FOUR) ) );

Wow, that was a long journey! We started from simple blocks, TRUE/FALSE, we added boolean operators, numbers, arithmetic, recursion and voila, we have built a system that's capable of expressing non-trivial computation of factorials!

If you just thought "it kind of looks like LISP" then you're on the right track. Conceptually, these two, Church encoding and LISP are similar. Technically, they differ much as LISP goes forward in optimizing how things are represented. For example, to represent 1000 in our encoding, we nest function application 1000 times. LISP supports numbers as values and performs arithmetics directly.

While at mathematical level, both are very close, you could say that LISP is a Church encoding optimized to make it a practical programming language.

Next time we'll discuss lists.