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);

Then it will call the f function 3 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. If we unrolled this it 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 I is a function that when given f and x will call f I 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 which is not instantly obvious to decipher in lambda calculus is the predecessor. This function will take a CN representing the integer I and will return a CN representing I - 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 complicated manner. This is true for all of Lambda Calculus, the behaviour defines the value not the structure. Meaning there are an infinite number of ways to represent a CN for an given integer.

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 in accomplishing this it can be broken up into its different components.

const createMapBox = v => f => f(v);
const createConstBox = v => f => v;
const useFunctionWithBoxes = f => bx => createMapBox(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 take a step back and create a function which just 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 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 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 out makeCopy into the predecessor. We split our implementation of createBox into two different types of box. One which will act like our original box, using the given function to map the value. And one which will completely ignore the given function and return the original value untouched. We will put the initial seed value to the CN in the box that ignores the function. The wrapped call to f will return the original box implementation that will apply the function it is given.

const createMapBox = v => f => f(v);
const createConstBox = v => f => v;
const useFunctionWithBoxes = f => bx => createMapBox(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 Lambda Calculus is slightly odd as all values have the same type 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 {
  (_: V): V;
}

/**
 * Given two types F and G, will represent a function from F to G
 * F => G
 */
interface Fn<F, G> {
  (_: F): G;
}

/**
 * ChurchNumerals represent positive intergers.
 * 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 T.
 * when given a function it can use it to return the value
 * transformed by the function.
 * Exactly how the function is used depends on the implementation of the box.
 */
interface Box<T extends V> {
  <T2 extends V>(f: Fn<T, T2>): T | T2;
}

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

/**
 * Creates a no-op Box.
 * When called will always just return the Box's value,
 * regardless of the argument passed to it.
 * v => f => v;
 */
function createConstBox<T extends V>(value: T): Box<T> {
  return _ => 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>) => createMapBox(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.