Positive Analogue

Understanding the Church Numeral Predecessor

August 08, 2018

Church Numerals(CN) are a way of representing positive integers in Lambda Calculus. They follow a very similar pattern to Array.prototype.reduce. If we take the following call to reduce:

["", "", ""].reduce(f, x);

f will be called three times. First starting with the x value as a seed to the first call of f and then all subsequent calls to f will be given the last returned value. Unrolling this would look like f(f(f(x))).

[].reduce(n => n + 1, 0); // 0
[""].reduce(n => n + 1, 0); // 1
["", ""].reduce(n => n + 1, 0); // 2
["", "", ""].reduce(n => n + 1, 0); // 3

A CN representing the integer n is a function that when given f and x will call f n times. Here is zero to three in CNs.

const zero = f => x => x;
const one = f => x => f(x);
const two = f => x => f(f(x));
const three = f => x => f(f(f(x)));

const toJsNumber = cn => cn(n => n + 1)(0);
toJsNumber(zero); // 0
toJsNumber(one); // 1
toJsNumber(two); // 2
toJsNumber(three); // 3

One function that is not clear to decipher is the predecessor function. It takes a CN representing the integer n and produces a CN representing n - 1.

For javascript numbers this function would just look like this

function predecessor(n) {
  return n - 1;
}

Where as in Lambda Calculus it is:

const predecessor = n => f => x => n(b => g => g(b(f)))(_ => x)(h => h);

toJsNumber(predecessor(zero)); // 0
toJsNumber(predecessor(one)); // 0
toJsNumber(predecessor(two)); // 1
toJsNumber(predecessor(three)); // 2

One key aspect to the predecessor function is that the CN it has created is not a clean implementation of the number it represents. Instead the returned CN just behaves the correct way, albeit in a more convoluted manner. This is true for all of Lambda Calculus, the behaviour defines the value, not the structure. A way to see this is that for an given integer there are an infinite number of ways to structure it yet still behave as a CN.

const I = v => v;
toJsNumber(f => x => f(x)); // 1
toJsNumber(f => x => I(f(x))); // 1
toJsNumber(f => x => I(I)(f(x))); // 1
toJsNumber(f => x => I(I)(I)(f(x))); // 1

With this in mind, when building the predecessor function, we are trying to create a function that doesn’t necessarily look like a CN but one which behaves as a CN. For the predecessor, this means creating a function that will call its f parameter one fewer times that the original CN would do.

To try and make the predecessor function reveal its trick we will break it up into a few different components.

const predecessor = n => f => x => n(b => g => g(b(f)))(_ => x)(h => h);

// becomes...

const createBox = v => f => f(v);
const createConstBox = v => f => v;
const useFunctionWithBoxes = f => bx => createBox(bx(f));
const predecessor = n => f => x =>
  n(useFunctionWithBoxes(f))(createConstBox(x))(h => h);

We can now try and build up and motivate these different components.

Let’s first create a function which only creates a copy of a CN, instead of creating CN - 1.

const makeCopy = n => f => x => n(f)(x);
toJsNumber(makeCopy(two)); // 2

Now we have created a new CN which will use the original CN to invoke f the correct number of times. Now we need a way to ensure f is applied fewer times. We need a way to intercept calls to f. One way to do this is to use something we will just call a Box. A Box is a function that is holding on to a value to be used as an argument to a function later.

const createBox = v => f => {
  console.log(`before 'f(${v})'`);
  const result = f(v);
  console.log(`after 'f(${v})'`);
  return result;
};

const f = x => x + 1;
const aBox = createBox(4);
console.log(aBox(f));
// > before 'f(4)'
// > after 'f(4)'
// > 5

We can now take our makeCopy function and adapt it so that it uses boxes so we can intercept the calls to f. We need to add (h => h) to the end so that we return the value inside the final box and not the box itself.

const makeCopy = n => f => x => n(f)(x);

// becomes...

const createBox = v => f => f(v);
const useFunctionWithBoxes = f => bx => createBox(bx(f));
const makeCopy = n => f => x =>
  n(useFunctionWithBoxes(f))(createBox(x))(h => h);

toJsNumber(makeCopy(two)); // 2

Now comes the hook which converts our makeCopy into the predecessor. We add a new, additional, implementation of createBox called createConstBox. This will completely ignore the function it is given and instead return the original value untouched. We will put the initial seed value to the CN in a const box so it will ignore the first call to f. After that the value will be back in a normal box and f will take affect again.

const createBox = v => f => f(v);
const createConstBox = v => f => v;const useFunctionWithBoxes = f => bx => createBox(bx(f));
const predecessor = n => f => x =>
  n(useFunctionWithBoxes(f))(createConstBox(x))(h => h);
toJsNumber(predecessor(two)); // 1

And finally here is a completely deconstructed implementation of the predecessor function in typescript. Adding types to pure Lambda Calculus may seem slightly odd as all values have the same type (At runtime LC won’t complain that a string was used where it was expecting a number) but it can help express how a function is intended to be used.

/**
 * Every value in lambda calculus is a function
 * which takes one value and returns one value.
 */
interface V {
  <V1 extends V>(v: V1): V;
}

/**
 * A function from F to G
 * F => G
 */
interface Fn<F extends V, G extends V> {
  (f: F): G;
}

/**
 * A ChurchNumeral representing positive interger N.
 * The first argument is the accumulator which will be applied N times
 * the second argument is the starting value given to the accumulator.
 */
interface ChurchNumeral {
  <T extends V>(acc: Fn<T, T>): (init: T) => T;
}

/**
 * A box holds a value of type T.
 * when given a function 'f' the value will be applied to that function
 * and the result returned
 */
interface Box<T extends V> extends V {
  (f: Fn<T, T>): T;
}

/**
 * Given a value will return a box
 * that will update the value using the given function
 * v => f => f(v);
 */
function createBox<T extends V>(value: T): Box<T> {
  return function(f: Fn<T, T>) {
    return f(value);
  };
}

/**
 * Creates a no-op Box.
 * When called will always just return the Box's original value,
 * ignoring the function passed to it.
 * v => f => v;
 */
function createConstBox<T extends V>(value: T): Box<T> {
  return (_: Fn<T, T>) => value;
}

/**
 * Given a function of type (a => a) will return a function raised to work
 * with values of type Box<a>.
 * (a => a) => (Box<a> => Box<a>)
 */
function useFunctionWithBoxes<T extends V>(f: Fn<T, T>): Fn<Box<T>, Box<T>> {
  return (box: Box<T>) => createBox(box(f));
}

function predecessor(n: ChurchNumeral): ChurchNumeral {
  // Return a function with the ChurchNumeral signature
  // (a => a) => a => a
  return function<T extends V>(f: Fn<T, T>) {
    return function(x: T) {
      // Now we will call the original numeral 'n'
      // but in a way so that it only applies the function n - 1 times
      const accumulator: Fn<Box<T>, Box<T>> = useFunctionWithBoxes(f);
      const initialValue: Box<T> = createConstBox(x);
      const boxedResult: Box<T> = n(accumulator)(initialValue);
      const result: T = boxedResult(x => x);
      return result;
    };
  };
}

Ashley Claymore

Hi! I'm Ashley Claymore. Like many others, pulling things apart to learn how they work brings me a lot of joy. This site serves as an outlet for these little projects.