The factorial function implemented in the lambda calculus

factorial.js

// In the lambda calculus, an expression must be one of the following:
// 1) function(x) { return expression; }
// 2) expression(expression)
// 3) x

// Pairs

const pair = function(x) {
  return function(y) {
    return function(f) {
      return f(x)(y);
    };
  };
};

const first = function(p) {
  return p(
    function(x) {
      return function(y) {
        return x;
      };
    }
  );
};

const second = function(p) {
  return p(
    function(x) {
      return function(y) {
        return y;
      };
    }
  );
};

// Arithmetic on natural numbers

const zero = function(f) { return function(x) { return x; } };
const one = function(f) { return function(x) { return f(x); } };

const increment = function(x) {
  return function(f) {
    return function(y) {
      return f(x(f)(y));
    };
  };
};

const decrement = function(x) {
  return first(
    x(
      function(p) {
        return pair(second(p))(increment(second(p)));
      }
    )(pair(zero)(zero))
  );
};

const add = function(x) {
  return function(y) {
    return x(increment)(y);
  };
};

const multiply = function(x) {
  return function(y) {
    return x(add(y))(zero);
  }
};

// The "Z" combinator for looping

const z = function(f) {
  return (
    function(x) {
      return function(z) {
        return f(x(x));
      };
    }
  )(
    function(x) {
      return function(z) {
        return f(x(x));
      };
    }
  );
};

// The identity function

const id = function(x) {
  return x;
};

// And finally: the factorial function!

const factorial = z(
  function(f) {
    return function(x) {
      return x(
        function(y) {
          return function(q) {
            return multiply(x)(f(id)(decrement(x)));
          };
        }
      )(
        function(q) { return one; }
      )(id);
    };
  }
)(id);

// Debugging

function print(y) {
  console.log(y(function(x) { return x + 1; })(0));
}

const two = increment(one);
const four = add(two)(two);
const five = increment(four);

print(factorial(five)); // Prints 120