Вычисление факториала на числах Чёрча

Доброго дня, друзья!

Тема функционального программирования раскрыта на Хабре весьма неплохо, есть целая куча статей посвященных λ-исчислению, числам Чёрча и подобным темам, так что ничего нового я не открою, зато мы напишем одну бесполезную и крайне неэффективную программу.

Для того, чтоб жизнь мёдом не казалась, ограничим себя небольшим подмножеством языка JavaScript, а именно, будем использовать только анонимные функции от одного аргумента. Больше нам ничего не потребуется (ну почти).

Начнем с определения факториала, и посмотрим, что нам понадобится в процессе решения задачи:

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

Итак, нам потребуются функции, логические значения (для результата операции сравнения с нулем), условный оператор, операции умножения и вычитания единицы, кроме того нужно будет реализовать рекурсивный вызов функции.

Готовы?

Начнем с простого, с логических значений True, False и функции If. True и False представлены каррированными функциями двух аргументов осуществляющими выбор первого либо второго аргумента. True выбирает первый аргумент, а False — второй. If принимает три аргумента, логическое значение, ветку then и ветку else.

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

Можно побаловаться в консоли выполняя код типа:

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

Дальше нам потребуются числа. Множество натуральных чисел можно получить определив значение числа НОЛЬ и операцию ПЛЮС_ОДИН. Числа Чёрча, грубо говоря, представляют собой функции двух аргументов, применяющие первый аргумент ко второму n раз, где n — это соответствующее натуральное число.

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

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

Дополнительно определим предикат проверяющий, является ли число нулем, реализация факториала потребует такую проверку. Предикат возвращает False если первый аргумент числа выполнился хотя бы раз.

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

Проверьте как работают числа:

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

Как видите, к нулю трижды прибавилась единица, а предикат корректно распознает переданное число.

Теперь, когда у нас есть все натуральные числа определим функцию умножающую два числа, результат умножения — это функция, которая n раз по m раз применяет свой аргумент.

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

Осталось научиться отнимать единицу от числа. Тут все немного сложнее. Идея вычитания состоит в том, что строится пара чисел (n, n — 1) и берется второй элемент пары. Таким образом нам нужно получить конструктор пары, а так же функции получения первого и второго элемента. После чего мы сможем определить функцию получения предыдущего числа.

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

Поиграемся с парами и вычитанием:

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

Казалось бы, все уже готово и можно реализовать факториал:

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

Но есть две проблемы, первая заключается в том, что JavaScript — язык с аппликативным порядком вычислений и наш факториал просто повиснет, т.к. будет выполнять рекурсивный вызов вне зависимости от значения аргумента. Эту проблему легко решить обернув рекурсивный вызов в анонимную функцию и тем самым отложив выполнение.

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

Теперь функция работает корректно:

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

Осталась последняя проблема. Вначале я обещал использовать только анонимные функции, а тут мы видим рекурсивный вызов по имени fact. Нужно от него избавиться и в этом нам поможет Y-комбинатор. Объяснять принцип его работы я не буду, на эту тему есть статьи и на Хабре и вне пределов Хабра. Рекомендую например вот эту блогозапись. Y-комбинатор в аппликативном языке выглядит так:

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

Проверить корректность его работы можно так:

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

Теперь подставим факториал в Y-комбинатор и получим конечный вариант:

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

Для большего удобства определим функции NatToChurch и ChurchToNat:

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

Теперь можно ставить эксперименты в консоли:

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

Последний шаг, сделать все подстановки и получить финальную функцию:



Осталось ответить на вопрос «Зачем так делать?». Признаюсь честно, на этот вопрос у меня ответа нет. Всем добра!