Calculating factorial on Church numbers

Good day friends!

The topic of functional programming is quite well disclosed on Habré, there are a whole bunch of articles devoted to λ-calculus , Church numbers and similar topics, so I won’t open anything new, but we will write one useless and extremely inefficient program.

In order for life to not seem like honey, we will limit ourselves to a small subset of the JavaScript language, namely, we will use only anonymous functions of one argument. We don’t need anything else (almost).

Let's start by defining the factorial, and see what we need in the process of solving the problem:

var fact = function (n) {
  if (n === 0) return 1;
  return n * fact(n - 1);
};

So, we need functions, logical values ​​(for the result of a comparison operation with zero), a conditional operator, operations of multiplying and subtracting units, in addition, we will need to implement a recursive function call.

Ready?

Let's start with a simple one, with the logical values True , False and the If function . True and False are represented by the curried functions of two arguments that select the first or second argument. True selects the first argument, and False selects the second. If takes three arguments, a boolean, then branch, and else branch.

var True = function (x) { 
  return function (y) {
    return x;
  }; 
};
var False = function (x) { 
  return function (y) {
    return y;
  }; 
};
var If = function (p) { 
  return function (t) {
    return function (e) {
      return p(t)(e);
    }
  };
};

You can indulge in the console by running code like:

console.log(If(True)('foo')('bar'));
console.log(If(False)('foo')('bar'));

Next we need numbers. A set of natural numbers can be obtained by defining the value of the number ZERO and the operation PLUS_ ONE. Church numbers, roughly speaking, are functions of two arguments, applying the first argument to the second n times, where n is the corresponding positive integer.

var Zero = function (f) {
  return function (x) {
    return x;
  };
};
var Succ = function (n) {
  return function (f) {
    return function (x) {
      return f(n(f)(x));
    };
  };
};

Additionally, we define a predicate that checks whether the number is zero, and factorial implementation will require such a check. The predicate returns False if the first argument of the number is executed at least once.

var IsZero = function (n) {
  return n(function (x) { 
    return False;
  })(True);
};

Check how the numbers work:

Succ(Succ(Succ(Zero)))(function (x) { return x + 1; })(0);
console.log(If(IsZero(Zero))('zero')('not zero'));
console.log(If(IsZero(Succ(Zero)))('zero')('not zero'));

As you can see, the unit has been added to zero three times, and the predicate correctly recognizes the transmitted number.

Now that we have all the natural numbers, we define a function that multiplies two numbers, the result of the multiplication is a function that uses its argument n times m times.

var Mul = function (n) {
  return function (m) {
    return function (f) {
      return n(m(f));
    };
  };
};

It remains to learn how to subtract one from the number. Everything is a bit more complicated here. The idea of ​​subtraction is that a pair of numbers (n, n - 1) is built and the second element of the pair is taken. Thus, we need to get the constructor of the pair, as well as the function of getting the first and second element. Then we can determine the function of obtaining the previous number.

var Pair = function (a) {
  return function (b) {
    return function (t) {
      return t(a)(b);
    };
  };
};
var Fst = function (p) {
  return p(True);
};
var Snd = function (p) {
  return p(False);
};
var Pred = function (n) {
  return function (s) {
    return function (z) {
      return Snd(n(function (p) {
        return Pair(s(Fst(p)))(Fst(p)); 
      })(Pair(z)(z)));
    };
  };
};

Let's play with pairs and subtraction:

Fst(Pair('foo')('bar')); // => "foo"
Snd(Pair('foo')('bar')); // => "bar"
Pred(Succ(Succ(Zero)))(function (x) { return x + 1; })(0); // => 1

It would seem that everything is ready and you can implement the factorial:

var fact = function (n) {
  return If(IsZero(n))(Succ(Zero))(Mul(n)(fact(Pred(n))));
};

But there are two problems, the first is that JavaScript is a language with an applicative order of calculations and our factorial will just hang, because will make a recursive call regardless of the value of the argument. This problem can easily be solved by wrapping a recursive call into an anonymous function and thereby delaying execution.

var fact = function (n) {
  return If(IsZero(n))(Succ(Zero))(function (x) {
    return Mul(n)(fact(Pred(n)))(x);
  });
};

Now the function works correctly:

fact(Succ(Succ(Succ(Zero))))(function (x) { return x + 1; })(0); // => 6

The last problem remains. At first, I promised to use only anonymous functions, but here we see a recursive call called fact . We need to get rid of it and the Y-combinator will help us with this . I will not explain the principle of its work; there are articles on this subject both on Habr and outside Habr. I recommend for example this blog post . The Y-combinator in the applicative language looks like this:

var Y = function (f) {
  return function (x) {
    return x(x);
  }(function (x) {
    return function (y) {
      return f(x(x))(y);
    };
  });
};

You can check the correctness of its operation as follows:

Y(function (f) {
  return function (n) {
    return If(IsZero(n))(Succ(Zero))(function (x) {
      return Mul(n)(f(Pred(n)))(x);
    });
  };
})(Succ(Succ(Succ(Zero))))(function (x) { return x + 1; })(0); // => 6

Now we substitute the factorial into the Y-combinator and get the final version:

var fact = function (x) {
  return x(x);
}(function (x) {
  return function (y) {
    return function (f) {
      return function (n) {
        return If(IsZero(n))(Succ(Zero))(function (x) {
          return Mul(n)(f(Pred(n)))(x);
        });
      };
    }(x(x))(y);
  };
});

For convenience, we define the NatToChurch and ChurchToNat functions :

var NatToChurch = function (n) {
  return n == 0 ? Zero : function (f) {
    return function (x) {
      return f(NatToChurch(n - ChurchToNat(Succ(Zero)))(f)(x));
    };
  };
};
var ChurchToNat = function (n) {
  return n(function (x) {
    return x + 1;
  })(0);
};

Now you can put experiments in the console:

ChurchToNat(fact(NatToChurch(5))); // => 120

The last step, do all the permutations and get the final function:



It remains to answer the question "Why do this?" Frankly, I have no answer to this question. Good to all!