Получение Y-комбинатора в 7 простых шагов

http://igstan.ro/posts/2010-12-01-deriving-the-y-combinator-in-7-easy-steps.html
  • Перевод
Y-комбинатор это метод реализации механизма рекурсии в языке программирования который не поддерживает его изначально (на самом деле, он используется больше для осуществления программирования мозгов). Однако требуется, чтобы язык поддерживал анонимные функции.

Я выбрал JavaScript для получения Y-комбинатора, начиная с определения рекурсивной функции факториала, используя пошаговые преобразования над исходной функцией.

Шаг 1


На начальном этапе используем встроенный механизм рекурсии JavaScript.
var fact = function (n) {
    if (n < 2) return 1;
    return n * fact(n - 1);
};


Шаг 2


Чтобы было простейшей вещью для получения базовой рекурсии? Мы могли бы определить функцию которая получает себя в качестве аргументы и вызывает этот аргумент с тем же аргументом. Конечно, это бесконечный цикл, и это вызовет переполнение стека.
(function (f) {
    f(f);
})(function (f) {
    f(f);
});

Давайте используем образец выше для нашей функции факториала. Существует однако небольшая разница. Функция факториала получает аргумент который пока неизвестен, так что мы хотим вернуть функцию которая принимает этот аргумент. Эта функция может быть использована для вычисления факториалов. Также, это то, что делает нашу реализацию не результатом бесконечного цикла.
var fact = (function (f) {
    return function (n) {
        // termination condition
        if (n < 2) return 1;

        // because f returns a function, we have a double function call.
        return n * f(f)(n - 1);
    };
})(function (f) {
    return function (n) {
        // termination condition
        if (n < 2) return 1;

        // because f returns a function, we have a double function call.
        return n * f(f)(n - 1);
    };
});

Шаг 3


На данный момент у нас есть некоторое уродливое дублирование. Давайте спрячем его в некоторой вспомогательной функции recur
var recur = function (f) {
    return f(f);
};

var fact = recur(function (f) {
    return function (n) {
        if (n < 2) return 1;

        // because f returns a function, we have a double function call.
        return n * f(f)(n - 1);
    };
});


Шаг 4


Проблемой версии выше является двойной вызов функции. Мы хотим его ликвидировать, так чтобы реализовать факториал аналогично с рекурсивной версией. Как мы можем это сделать?

Мы можем использовать вспомогательную функцию которая принимает числовой аргумент и выполняет двойной вызов. Фокус в том чтобы оставить эту вспомогательную функцию в некоторой среде где f видна, так чтобы g могла вызвать f.
var recur = function (f) {
    return f(f);
};

var fact = recur(function (f) {
    var g = function (n) {
        return f(f)(n);
    };

    return function (n) {
        if (n < 2) return 1;

        // no more double call, g is a function which takes a numeric arg
        return n * g(n - 1);
    };
});


Шаг 5


Работа выше хороша но определение содержит так много беспорядочного кода. Мы может скрыть его подальше внутри еще одной вспомогательной функции, оставляя почти только определение факториала.
var recur = function (f) {
    return f(f);
};

var wrap = function (h) {
    return recur(function (f) {
        var g = function (n) {
            return f(f)(n);
        };

        return h(g);
    });
};

var fact = wrap(function (g) {
    return function (n) {
        if (n < 2) return 1;
        return n * g(n - 1);
    };
});


Шаг 6


Давайте встроим определение g внутри wrap так как мы вызываем это только однажды.
var recur = function (f) {
    return f(f);
};

var wrap = function (h) {
    return recur(function (f) {
        return h(function (n) {
            return f(f)(n);
        });
    });
};

var fact = wrap(function (g) {
    return function (n) {
        if (n < 2) return 1;
        return n * g(n - 1);
    };
});


Шаг 7


Теперь если мы также встроим определение функции recur внутри wrap то мы закончим вместе с известным Y-комбинатором.
var Y = function (h) {
    return (function (f) {
        return f(f);
    })(function (f) {
        return h(function (n) {
            return f(f)(n);
        });
    });
};

var fact = Y(function (g) {
    return function (n) {
        if (n < 2) return 1;
        return n * g(n - 1);
    };
});


Конец


Я надеюсь, что вам понравилось.
Поделиться публикацией

Комментарии 47

    +1
    Ну что, прикольно. Можно людям предлагать как альтернативу arguments.callee.

    Но, с другой стороны, слишком много магии. Проще дать имя функции и вызывать родителя по имени, как в вашем первом примере.
      +3
      Думаю это чисто учебный пример — применение одного из шаблонов проектирования функционального программирования (Y-комбинатор) в javaScript.
      Очень полезная статья как для изучения функционального программирования так и javaScript. Побольше бы таких.
        +1
        Полностью согласен, что статья хороша как учебная. Нужно осваивать новые техники и подходы, особенно принципиально отличающиеся от тех, что мы повсеместно используем, пусть даже на таких, казалось бы, простых примерах. И язык выбран подходящим образом: поддерживает анонимные функции, но в месте с тем не мыслится нами, как правило, как функциональный, будучи таковым.

        Тем не менее, чем огранничиться парадоксальным комбинатором Карри Y, можно было б упомянуть о комбинаторе Θ, предложенным Тьюрингом (1937). Он с точки зрания лямбда-исчисления лучше в том смысле, что Θ(F) редуцируется до F(Θ(F)), в то время как Y таковым свойством не обладает, ограничивая себя лишь равенством Y(F)=F(Y(F)).
          +1
          По мотивам этой статьи, творчески переработав, записал скринкаст о реализации Y-комбинатора на JavaScript: youtu.be/clYMNxScsFQ
      +7
      Сначала подумал, что речь о бизнес-инкубаторе y-combinator и как туда попасть ))
      Вот уж эти стартапы, скоро снится начнут.
        0
        Двусмысленный заголовок =)
          –5
          Господи, а зачем тут JS? Типа, чтобы даже последние дебилы веб-обезьяны типичный посетитель Хабра понял? На традиционной схеме это на порядок понятнее и красивее.
          Лямбда-счисление:
          Y = λf.(λx.f (x x)) (λx.f (x x))

          Схема:
          (define Y (λ (f) ((λ (rec) (f (λ arg (apply (rec rec) arg)))) (λ (rec) (f (λ arg (apply (rec rec) arg)))))))
          • НЛО прилетело и опубликовало эту надпись здесь
              0
              Хаскель как раз не очень подходит для демонстрации Y-комбинатора.
              • НЛО прилетело и опубликовало эту надпись здесь
                  +1
                  imho, цель статьи — показать, откуда и как получается Y-комбинатор. Думаю, хаскелисты это и так знают, а остальных этот дополнительный тип только зря запутает.
                  • НЛО прилетело и опубликовало эту надпись здесь
              +2
              Об этом вы лучше автора оригинала спросите.
              на порядок понятнее и красивее
              Я с лиспом не знаком, и пока искал пару 3-й скобке в вашем втором выражении окончательно запутался. В статье же все предельно доступно, на простом и понятном многим языке.
              • НЛО прилетело и опубликовало эту надпись здесь
                  0
                  Для упрощения поиска закрывающих тегов можно сделать что-то типа HAML для лисперов.
                  (a href=«foo» (strong bar (em baz)))
                  • НЛО прилетело и опубликовало эту надпись здесь
                –1
                Что за дурацкая привычка псевдолисперов выкладывать чанки кода в одну строку? Лисп — ни разу не язык однострочников, это самый вертикальный язык из всех мне известных, и в этом его большое преимущество.

                (defn Y [r]
                (letfn [(rec[f] (f f))]
                (rec (fn[g]
                (r (fn[x] ((rec g) x)))))))

                Вышло все равно не мгновенно очевидно, но это изза сложности понимая самого комбинатора.
                Не создавайте, пожалуйста, языку дурную славу, ее у него и так достаточно.
              –2
              Интересный у вас fact(-2) получается.

              Вместо того, чтобы «маскировать уродство» не лучше ли было взять подходящий инструмент? Хаскель для того и придумали.
                –1
                Нет, давайте уже поговорим о динамической и статической типизации и пригодности языков подмножества ECMA для функционального программирования.
                  +1
                  Давайте поговорим. Что Вас беспокоит?
                    –1
                    Сегодня меня беспокоят цены на редкоземельные металлы. А обсудить мы можем то, о чем я писал в первом комментарии в ветке.
                      +1
                      Неплохо было бы привести аргументы, чтобы было что обсуждать.
                        –1
                        Так и приводите. Мои — у вас перед глазами.
                        Если желаете — могу дать их подробнее.
                        1. В языках с динамической типизацией требуется внимательно следить за аргументами. Это не только идеологически неправильно, но и не удобно.
                        2. Также скриптовые языки, мягко говоря, не выразительны, когда дело доходит до функционального программирования.

                        Теперь я написал это три раза. Ваши аргументы?
                          +1
                          Ааа. Так это вы называете аргументами.
                          Ну холивар динамическая vs статическая типизация вообще к теме не имеет ни малейшего отношения

                          А второе — это спорный вопрос. На новой версии языка, которой можно будет пользоваться на сервере уже где-то через полгода-год получается вполне изящно:
                          var fact = Y(#(callee) {
                          	#(num) { num > 1 ? num * callee(num - 1) : 1 }
                          });
                          
                            –1
                            Новая версия, которая будет когда-то — это очень хорошо. Пока можно было взять старую версию лиспа хаскеля или *мл и сделать красиво.

                            Это не спорный вопрос и не холивар. Я просто хотел отметить, что не следует забивать гвозди селедкой.
                              +1
                              Пока кроме старой версии Javascript нельзя взять ни новую версию ни Лисп или Хаскель.

                              А на сервере можно взять и Лисп с Хаскелем и новую версию JavaScript.

                              Хотя вру. На новой версии уже можно писать даже для клиента.

                              Еще аргументы есть?
                                –1
                                Полно!
                                Блог называется «программирование», а не яваскрипт, а это значит, что выбор языка для иллюстрации У комбинатора был осознанным и ошибочным.

                                Все ваши размышления о сервере и клиенте тут совершенно не при чём, потому что язык был взят для иллюстрации, а не для решения конкретной задачи на клиенте.

                                Если бы вы взяли новую редакцию яваскрипта и, используя её написали статью о У комбинаторе — я бы снял шляпу и поставил большой плюс, а пока — все ещё селёдка.
                                  +1
                                  А какая разница, какой язык? Javascript знает очень много людей, синтаксис у него очень простой и понятный. Если вам интересно, вот код на последней версии языка:

                                  var Y = # (h) {
                                  	# (# (f) {
                                  		f(f)
                                  	})(# (f) {
                                  		h(# (n) { # f(f)(n) })
                                  	})
                                  };
                                  
                                  var fact = Y(# (callee) {
                                      #(num) { num > 1 ? num * callee(num - 1) : 1 }
                                  });
                                  
                                    –1
                                    Разница очевидна, если сравнить код приведенный вами, код приведенный в седьмом шаге и код из коммента, который кстати тоже заминустовали: habrahabr.ru/blogs/programming/118927/#comment_3880779

                                    В функциональном программировании самое главное понять принцип. Второе главное — реализовать с помощью _удобного_ инструмента.

                                    И ещё одно. Человек, который может в этот код — может в ФП -)
                    0
                    Наверно вы в танке и не заметили что статья о Y-комбинаторе а не о JavaScript. А динамическая типизация это не то что +'123' + 1 = 124 это то что функции можно делать полиморфными
                      –1
                      Вы наверное не очень в программирование.

                      «123» + 1 = 124 это dynamic cast
                      Полиморфизм отлично работает и со статической типизацией.
                      То что я имел в виду пишется так: «Dynamic typing may result in runtime type errors—that is, at runtime, a value may have an unexpected type, and an operation nonsensical for that type is applied.»

                      Матчасть, матчасть и еще раз матчасть.
                  0
                  > язык не поддерживает механизм рекурсии, но поддерживает анонимные функции

                  а можно пример?
                    0
                      +3
                      я лямбда-исчисление изучал ещё в университете по курсу мат. логики.
                      я говорю о языках программирования.
                    0
                    Вообще подобная статья была в блоге питона, я тогда чуть моск не сломал, но мне понравилось :) Но как там же и пояснили практического смысла в этом нет (выходит затратнее), но мозги развивает.
                      –1
                      Не думал, что на JS для этого нужно столько кода…
                      На VB.Net и C# намного компактнее:

                      C#

                      VB.Net
                      Delegate Function SelfApplicable(Of TReturn)(ByVal self As SelfApplicable(Of TReturn)) As TReturn
                      Dim YC As SelfApplicable(Of Func(Of Func(Of Func(Of Integer, Integer), Func(Of Integer, Integer)), Func(Of Integer, Integer))) = _
                      Function(y) Function(f) Function(x) f(y(y)(f))(x)
                      Dim factorial = YC(YC)(Function(fac) Function(x) If(x = 0, 1, x * fac(x — 1)))

                      P.S. <code> не пашет =(
                        –1
                        Самоотправилось…

                        C#
                        delegate TReturn SelfApplicable<TReturn>(SelfApplicable<TReturn> self);

                        SelfApplicable<Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>>>
                        YC = y => f => x => f(y(y)(f))(x);
                        var factorial = YC(YC)(fac => x => x = 0? 1: x * fac(x — 1));
                          0
                          Черт, зачем столько строк? Ведь можно было в одну всё записать!
                            0
                            Разве
                            var factorial = YC(YC)(fac => x => x = 0? 1: x * fac(x — 1));
                            не одна строка?
                            0
                            JavaScript.NEXT:
                            var fact = Y(#(callee) {
                            	#(num) { num > 1 ? num * callee(n - 1) : 1 }
                            });
                            
                          +1
                          Может я олдфаг, но зачем для обычной рекурсии такие непонятные коды городить?
                            +1
                            А тут рекурсия необычная, тут она анонимная.
                              –1
                              var fact= function (n) {
                              var g= arguments.callee
                              if (n < 2) return 1;
                              return n * g(n — 1);
                              }
                                +1
                                arguments.callee — deprecated
                                  –1
                                  и чо?
                                    +2
                                    чо и чо?

                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                          Самое читаемое