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

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

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

    Для того, чтоб жизнь мёдом не казалась, ограничим себя небольшим подмножеством языка 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
    


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

    Осторожно, очень много функций
    var fact = function (x) {
      return x(x);
    }(function (x) {
      return function (y) {
        return function (f) {
          return function (n) {
            return function (p) { 
              return function (t) {
                return function (e) {
                  return p(t)(e);
                }
              };
            }(function (n) {
              return n(function (x) { 
                return function (x) { 
                  return function (y) {
                    return y;
                  }; 
                };
              })(function (x) { 
                return function (y) {
                  return x;
                }; 
              });
            }(n))(function (n) {
              return function (f) {
                return function (x) {
                  return f(n(f)(x));
                };
              };
            }(function (f) {
              return function (x) {
                return x;
              };
            }))(function (x) {
              return function (n) {
                return function (m) {
                  return function (f) {
                    return n(m(f));
                  };
                };
              }(n)(f(function (n) {
                return function (s) {
                  return function (z) {
                    return function (p) {
                      return p(function (x) { 
                        return function (y) {
                          return y;
                        }; 
                      });
                    }(n(function (p) {
                      return function (a) {
                        return function (b) {
                          return function (t) {
                            return t(a)(b);
                          };
                        };
                      }(s(function (p) {
                        return p(function (x) { 
                          return function (y) {
                            return x;
                          }; 
                        });
                      }(p)))(function (p) {
                        return p(function (x) { 
                          return function (y) {
                            return x;
                          }; 
                        });
                      }(p)); 
                    })(function (a) {
                      return function (b) {
                        return function (t) {
                          return t(a)(b);
                        };
                      };
                    }(z)(z)));
                  };
                };
              }(n)))(x);
            });
          };
        }(x(x))(y);
      };
    });
    



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

    Comments 47

      +6
      выносим мозг со вкусом!
      спасибо за статью
        +2
        Интересно, сколько памяти жрёт вычисление факториала 10, например.
          –3
          Насколько я понимаю, это иллюстрирует красоту общей алгебры.
            +3
            Причем тут общая алгебра? Это иллюстрирует красоту лямбда-исчисления.
              +1
              А вот если еще и через arrow function написать, то вообще красотища то какая будет =)
          +1
          Вопроса «зачем так делать?» нет. Есть вопрос «зачем так делать на языке, который для этого вообще не предназначен?», на haskell'е те же функции выглядели бы сильно проще.
            +7
            Вопрос «зачем так делать на языке, который для этого вообще не предназначен?» в хабе «Ненормальное программирование» задавать неприлично.

            PS если на Хаскеле, как и в этой статье, не использовать никаких имен — то получившийся однострочник едва ли будет понятнее приведенного тут кода
              +1
              Ну, если сравнивать такой код
              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);
              };
              


              с вот таким:
              natToChurch 0 = \f -> id
              natToChurch n = \f -> f . (natToChurch (n - 1))
              
              churchToNat f = f (+1) 0
              


              то выбор очевиден, несмотря на какие-либо наличия имён
                0
                Я думаю, что люди знающие haskell и так в курсе всего этого безобразия, интереснее разбудить интерес к ФП у людей пишущих на более мейнстримовых языках.
                • UFO just landed and posted this here
                    0
                    К ответу на этот вопрос можно подойти с разных сторон.

                    Во-первых, у ФП есть очевидное преимущество в области параллельных вычислений (отсутствие защищаемого состояния и безразличие к порядку вычисления), а т.к. сейчас даже в телефонах по 4 ядра, это становится все более и более актуальным.

                    Что касается понятности, эффективности и выразительности, то делать выводы о ФП по достаточно извращенному примеру, использующему только лямбда исчисление — не правильно. Естественно есть более выразительные функциональные языки предоставляющие синтаксис для простых и красивых абстракций. В реальной жизни программист для вычисления факториал напишет например такой код на haskell:
                    fact n = product [1..n]
                    

                    Или без использования стандартной библиотеки:
                    fact 0 = 1
                    fact n = n * fact (n - 1)
                    

                    Ничего страшного и непонятного в таком коде нет, какие-то подходы могут быть непривычны, но это далеко не rocket science. Подтверждением этому факту служит то, что многие подходы ФП (map, reduce, лябмды, замыкания и т.д.) благополучно переползли в императивные языки и не вызывают проблем у среднестатистического программиста.

                    Теперь о том, зачем понимать лямбды, комбинаторы и прочее. Я думаю, что мало кто возьмется спорить с тем, что программисту на любом императивном языке полезно понимать семантику указателей, немножко знать Си и иметь хотя бы поверхностное понимание того как работает регистровая машина.

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

                    И еще, я просто получаю удовольствие от красивых математических концепции. Мне нравится видеть, как простые вещи (семантика л-исчисления чрезвычайно проста) комбинируясь дают неограниченно сложные структуры. Так что эстетическое восприятие программирования играет для меня не последнюю роль.
                    • UFO just landed and posted this here
                        0
                        Правда, я ни разу пока не встречал задачи, которую было бы сильно сложнее написать императивным/объектным стилем.

                        Ну обычно тут приводят в пример быструю сортировку (не очень корректный пример, т.к. она не in-place, но оценить выразительность дает):

                        qsort [] = []
                        qsort (x:xs) = qsort [a | a <- xs, a <= x] ++ [x] ++ qsort [a | a <- xs, a > x]
                        

                        Императивный код с циклами и индексами выглядит намного ужаснее.

                        Еще мне нравится такой пример, вполне себе практический, представим себе электронную таблице типа экселевской, пусть это будет список с ячейками в которых лежат значения и функции зависящие от этих значений, попробуем написать код вычисляющий значения для всех ячеек:

                        solve x = go where go = fmap ($ go) x          
                                  
                        main = print $ solve [const 42      -- константа 42
                                            , succ . (!! 0) -- нулевая ячейча + 1
                                            , sum . take 2] -- сумма первых двух ячеек
                        

                        Это валидная программа на haskell, а теперь попробуйте написать то же самое в императивном стиле.

                        Что касается GUI, тут я соглашусь, задачи программирования GUI очень хорошо мапятся на ООП.
                        А на том же C++ можно по всякому — и так, и эдак, и с подвывертом.

                        Можно. Ценой кошмарных синтаксических конструкций.
                        • UFO just landed and posted this here
                            0
                            Быстрая сортировка ведь есть в стандартной библиотеке C++?

                            Ну а что вы хотели? Чтобы я привел пример задачи, которую никто еще раньше не решал?

                            Что касается программы с ячейками — во-первых, я не очень понял задачу.

                            Реализовать табличный процессор, на входе имеем список констант и функций от этих констант, на выходе тот же самый список, в котором все функции вычислены.

                            Могу еще пример привести, некогда один хабраюзер решал задачу генерации JSON на C++ http://habrahabr.ru/post/230079/ и даже написал статью на эту тему. Я в комментариях привел пример того, как ту же самую задачу решить на haskell http://habrahabr.ru/post/230079/#comment_7786101. Сравните объем и понятность кода из комментария и код из статьи.

                            Но ни разу почему-то не пришлось решать задачи, которые я посчитал бы удобным решать на чисто функциональных языках

                            Может быть дело не в задачах, а в вашем субъективном мнении на счет удобства тех или иных языков? На самом деле, в этом нет ничего плохого, я тоже предпочитаю использовать те инструменты, которые знаю лучше всего, и это к сожалению не haskell. Только это еще не повод отказывать себе в изучении чего-то нового.
                            • UFO just landed and posted this here
                                0
                                Вы не поняли задачу. Функции могут зависеть не только от констант, но и друг от друга.
                                • UFO just landed and posted this here
                                    0
                                    Еще мне нравится такой пример, вполне себе практический, представим себе электронную таблице типа экселевской, пусть это будет список с ячейками в которых лежат значения и функции зависящие от этих значений, попробуем написать код вычисляющий значения для всех ячеек:
                                    • UFO just landed and posted this here
                                        0
                                        Вы действительно не поняли задачу, ну предположим, что синтаксис вам не понятен, но комментарии на русском прочесть же можно?

                                        $ cat q.hs
                                        solve x = go where go = fmap ($ go) x
                                        
                                        main = print $ solve [const 42      -- константа 42
                                                            , succ . (!! 0) -- нулевая ячейча + 1
                                                            , sum . take 2] -- сумма первых двух ячеек
                                        $ runhaskell q.hs
                                        [42,43,85]
                                        

                                        Получится элегантно решить в императивном стиле?
                                        • UFO just landed and posted this here
                                            +1
                                            Всё равно не понял.

                                            Есть такая проблема. У меня, если честно, закончилось желание что либо вам объяснять. Не поняли, ну и ладно, видимо не сильно хотелось.
                                            • UFO just landed and posted this here
                                  • UFO just landed and posted this here
                                      0
                                      Тем который получил пиво, вместо заказа на пару месяцев?
                                      • UFO just landed and posted this here
                                        +1
                                        Наверное, тут уместен случай из жизни.

                                        Не понимаю, каким образом он тут уместен?
                                        • UFO just landed and posted this here
                                      0
                                      Я же вижу, что не всё в этом мире функция.

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

                                      Бывают же константы, бывают процедуры, бывают контейнеры (объекты, структуры и т.п.)

                                      Константы — это функции возвращающие одинаковый результат при любых входных данных
                                      Процедуры — монады
                                      Контейнеры — функторы
                                      Никто не мешает писать в императивном или ООП стиле на функциональном языке, все эти концепции на месте, только называются и выглядят непривычно.
                                        0
                                        зачем нужен подход «всё — функция»

                                        Функциональщина этого и не утверждает. Любая функция есть значение, но не любое значение — функция (и не любая конструкция языка — значение).
                          +2
                          Только потому что первый код был написан неоптимально. Вот этот код
                          function NatToChurch (n) {
                            return n == 0 ? Zero : Succ(NatToChurch(n-1));
                          }
                          

                          никак не сложнее своего эквивалента на Хаскеле.

                          PS только вот почему мы вдруг начали сравнивать удобочитаемость двух исключительно отладочных функций?
                            0
                            Можно и не отладочный, а более уместные:
                            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);
                                }
                              };
                            };
                            


                            опять же выглядит сильно страшнее, чем

                            true = \x -> \y -> x
                            false = \x -> y -> y
                            
                            if = \cond -> \yes -> \no -> cond yes no
                            
                              0
                              Для таких маленьких функций — согласен. Но перепишите определение fact на Хаскель, пожалуйста, тогда и сравним.

                              PS
                              var If = function (p) { return p; }
                              
                              if = \cond -> cond
                              
                                0
                                if = \cond -> cond
                                

                                тогда уж:
                                if = id
                                

                                Хороший язык, спору нет :)
                                  0
                                  id — это уже стандартная библиотека, ей нельзя пользоваться в этой задаче
                                    0
                                    Если уж на то пошло, на хаскеле задача с такой формулировкой вообще не решается (или я не знаю как ее решить), т.к. придется объявить рекурсивный тип.
                                  0
                                  Да, конечно, даже
                                  if' = id
                                  

                                  (UPD: да, не обновил перед отправкой)

                                  fact получается явно не сложнее:
                                  fact n = isZero (n) (id) (n . (fact $ dec $ n))
                                  
                                    0
                                    Автор поста не пользовался именованными функциями. Почему вы считаете, что можете написать одну строку на Хаскеле с их использованием, а потом сравнивать языки?
                                      0
                                      Как это не пользовался? А все эти succ, pred, isZero и т. д. — не именованные функции?
                                        +1
                                        А спойлер в конце статьи вы смотрели?
                          0
                          На хаскеле не получится тривиально реализовать рекурсию комбинатором, т.к. он типизирован.

                      Only users with full accounts can post comments. Log in, please.