Church encodings in Javascript. Natural numbers and arithmetic, booleans, conditionals, recursion, and a demonstration using the factorial function.

church.js

#!/usr/bin/env node
'use strict'

let churchToInt = c => c(x => x + 1)(0)

let ZERO = f => x => x
let ONE = f => x => f(x)
let TWO = f => x => f(f(x))
let increment = n => f => x => f(n(f)(x))
let THREE = increment(TWO)
let FOUR = increment(THREE)
let multiply = n => m => f => x => m(n(f))(x)
let addInc = n => m => m(increment)(n)
let add = n => m => f => x => n(f)(m(f)(x))
let exp = n => m => m(n)

// BOOLEANS
let churchToBool = c => c(true)(false)
let TRUE = x => y => x
let FALSE = ZERO

// Church encodings of pairs
let cons = x => y => s => s(x)(y)
// first element
let car = p => p(TRUE)
// second element
let cdr = p => p(FALSE)

// given x, returns (x, x + 1)
let selfAndInc = x => cons(x)(increment(x))

// given (x, y), returns (y, y + 1)
let shift = p => selfAndInc(cdr(p))

// given n > 0, returns n - 1.
// applies n to shift and (0, 0), and takes the first element of the pair
let decrement = n => car(n(shift)(cons(ZERO)(ZERO)))

// is this church numeral zero? returns a church boolean
let isZero = n => n(_ => FALSE)(TRUE)

// the eager Y Combinator, in ES6
let yComb = f => (x => y => f(x(x))(y))(x => y => f(x(x))(y))

// if then else - the then and else must be thunks to allow lazy execution
// otherwise, factorial would recurse infinitely
let ifte = c => t => e => c(t)(e)()

let fact = yComb(f => n => ifte(isZero(n))(_ => ONE)(_ => multiply(n)(f(decrement(n)))))


console.log("1! = " + churchToInt(fact(ONE)))
console.log("2! = " + churchToInt(fact(TWO)))
console.log("3! = " + churchToInt(fact(THREE)))
console.log("4! = " + churchToInt(fact(FOUR)))