Что такое Y-комбинатор? [закрыто]

Другие ответы дают довольно краткий ответ на этот вопрос, без одного важного факта: вам не нужно реализовывать комбинатор с фиксированной запятой на любом практическом языке таким замысловатым образом, и это не имеет никакого практического смысла (кроме «посмотрите, я знаю, что Y-комбинатор есть "). Это важная теоретическая концепция, но мало практической ценности.

Я написал своего рода «руководство для идиотов» для Y-Combinator в Clojure и Scheme, чтобы помочь себе разобраться с ним. На них влияет материал в «Маленьком интриганке»

На схеме: https://gist.github.com/z5h/238891

или Clojure: https://gist.github.com/z5h/5102747

Оба руководства представляют собой код с добавлением комментариев и должны быть вырезаны и дополнены; вставляется в ваш любимый редактор.

Как новичок в комбинаторах, я нашел статью Майка Ваньера (спасибо Николасу Манкузо) очень полезной. Я хотел бы написать резюме, помимо документирования моего понимания, если бы оно могло помочь некоторым другим, я был бы очень рад.

От Crappy до Less Crappy

Используя факториал в качестве примера, мы используем следующую функцию almost-factorial для вычисления факториала числа x:

def almost-factorial f x = if iszero x
                           then 1
                           else * x (f (- x 1))

В приведенном выше псевдокоде almost-factorial принимает функцию f и число x (almost-factorial каррируется, поэтому его можно рассматривать как принимающее функцию f и возвращающее 1-арная функция).

Когда almost-factorial вычисляет факториал для x, он делегирует вычисление факториала для x - 1 функции f и накапливает этот результат с x (в этом случае он умножает результат на (x - 1) с х).

Это можно увидеть как almost-factorial принимает в дрянную версию факториальной функции (которая может рассчитывать только до числа x - 1) и возвращает менее дрянную версию факториал (который вычисляет до числа x). Как в следующем виде:

almost-factorial crappy-f = less-crappy-f

Если мы несколько раз передадим менее дрянную версию факториала в almost-factorial, мы в итоге получим желаемую факториальную функцию f. Где это можно рассматривать как:

almost-factorial f = f

Фиксированная точка

Тот факт, что almost-factorial f = f означает f, является фиксированной точкой функции almost-factorial.

Три функции

Для обобщения мы имеем нерекурсивную функцию fn (например, наше почти факториальное), у нас есть функция с фиксированной точкой fr (как и у нашего f), тогда что Y делает, когда вы даете Y fn, Y возвращает функция фиксированной точки из fn.

Итак, в итоге (упрощается, если предположить, что fr принимает только один параметр; x вырождается в x - 1, x - 2 ... в рекурсии):

• Определим вычисления ядра как fn : def fn fr x = ...accumulate x with result from (fr (- x 1)), это почти полезная функция - хотя мы не можем использовать fn напрямую на x, это будет полезно очень скоро. Этот нерекурсивный fn использует функцию fr для вычисления своего результата
• fn fr = fr, fr является точкой фиксации fn, fr является полезная функция , мы можем использовать fr в x, чтобы получить наш результат
• Y fn = fr, Y возвращает точка фиксации функции Y превращает нашу почти полезную функцию fn в полезную fr

Вывод Y (не включен)

Я пропущу вывод из Y и пойду к пониманию Y. В сообщении Майка Вайнера много деталей.

Форма Y

Y определяется как (в формате лямбда-исчисления ):

Y f = λs.(f (s s)) λs.(f (s s))

Если мы заменим переменную s слева от функций мы получаем

Y f = λs.(f (s s)) λs.(f (s s))
=> f (λs.(f (s s)) λs.(f (s s)))
=> f (Y f)

Так что действительно, результат (Y f) является точкой фиксации f.

Почему (Y f) работает?

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

def fn fr x = accumulate x (fr (- x 1))

начиная с fn fr = fr, мы продолжаем

=> accumulate x (fn fr (- x 1))
=> accumulate x (accumulate (- x 1) (fr (- x 2)))
=> accumulate x (accumulate (- x 1) (accumulate (- x 2) ... (fn fr 1)))

рекурсивное вычисление заканчивается, когда самый внутренний (fn fr 1) является базовым случаем, а fn не использует fr в расчет.

Снова глядя на Y:

fr = Y fn = λs.(fn (s s)) λs.(fn (s s))
=> fn (λs.(fn (s s)) λs.(fn (s s)))

Итак,

fr x = Y fn x = fn (λs.(fn (s s)) λs.(fn (s s))) x

Для меня магическими частями этой установки являются:

• fn и fr взаимозависимы друг от друга: fr «оборачивает» fn внутри, каждый раз, когда fr используется для вычисления x, он «порождает» («поднимает»?) An fn и делегирует вычисление этому fn (передавая само по себе fr и x); с другой стороны, fn зависит от fr и использует fr для вычисления результата меньшей задачи x-1.
• В то время, когда fr используется для определения fn (когда fn использует fr в своих операциях), реальное fr еще не определено.
• Именно fn определяет реальную бизнес-логику. Основываясь на fn, Y создает fr - вспомогательную функцию в определенной форме - для облегчения вычисления для fn рекурсивным способом .

Это помогло мне понять Y таким образом на данный момент, надеюсь, это поможет.

Кстати, я также нашел книгу Введение в функциональное программирование с помощью лямбда-исчисления очень хорошей, я только часть этого и тот факт, что я не мог разобраться Y в книга привела меня к этому посту.

Большинство приведенных выше ответов описывают, что такое Y-комбинатор , но не то, что он для .

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

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

Вот JavaScript-реализация Y-Combinator и факториальной функции (из статьи Дугласа Крокфорда, доступной по адресу: http://javascript.crockford.com/little.html ).

function Y(le) {
    return (function (f) {
        return f(f);
    }(function (f) {
        return le(function (x) {
            return f(f)(x);
        });
    }));
}

var factorial = Y(function (fac) {
    return function (n) {
        return n <= 2 ? n : n * fac(n - 1);
    };
});

var number120 = factorial(5);

Для программистов, которые не сталкивались с функциональным программированием в глубине и не хотят начинать сейчас, но немного любопытны:

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

Он работает, передавая функцию себе в качестве аргумента, чтобы он мог вызывать себя.

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

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

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

Y = λf. (Λx.f (xx)) (λx.f (xx))

Обычно вы можете заметить это из-за повторного (λx.f (x x)).

Символы λ - это греческая буква лямбда, которая дает название лямбда-исчислению, и существует множество терминов стиля (λx.t), потому что именно так выглядит лямбда-исчисление.

function factorial(n) {
    return n == 0 ? 1 : n * factorial(n - 1);
}

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

function fact() {
    return function(n) {
        return n == 0 ? 1 : n * fact()(n - 1);
    };
}

var factorial = fact();

Это немного странно, но в этом нет ничего плохого. Мы просто генерируем новую факториальную функцию на каждом шаге.

Рекурсия на этом этапе все еще довольно явно. Функция fact должна знать свое имя. Давайте параметризуем рекурсивный вызов:

function fact(recurse) {
    return function(n) {
        return n == 0 ? 1 : n * recurse(n - 1);
    };
}

function recurser(x) {
    return fact(recurser)(x);
}

var factorial = fact(recurser);

Это здорово, но recurser все еще нужно знать его собственное имя. Давайте также параметризуем это:

function recurser(f) {
    return fact(function(x) {
        return f(f)(x);
    });
}

var factorial = recurser(recurser);

Теперь, вместо непосредственного вызова recurser(recurser), давайте создадим функцию-обертку, которая возвращает ее результат:

function Y() {
    return (function(f) {
        return f(f);
    })(recurser);
}

var factorial = Y();

Теперь мы можем избавиться от recurser имя в целом; это просто аргумент внутренней функции Y, который можно заменить самой функцией:

function Y() {
    return (function(f) {
        return f(f);
    })(function(f) {
        return fact(function(x) {
            return f(f)(x);
        });
    });
}

var factorial = Y();

Единственное внешнее имя, на которое все еще ссылаются, это fact, но теперь должно быть ясно, что это легко параметризовать, также, создавая полное, общее решение:

function Y(le) {
    return (function(f) {
        return f(f);
    })(function(f) {
        return le(function(x) {
            return f(f)(x);
        });
    });
}

var factorial = Y(function(recurse) {
    return function(n) {
        return n == 0 ? 1 : n * recurse(n - 1);
    };
});

Я взял это из http://www.mail-archive.com/boston-pm@mail.pm.org/msg02716.html , которое является объяснением, которое я написал несколько лет назад.

Я буду использовать JavaScript в этом примере, но многие другие языки также будут работать.

Наша цель состоит в том, чтобы иметь возможность написать рекурсивную функцию из 1 переменной, используя только функции из 1 переменной и без присваиваний, определяя вещи по имени и т. Д. (Почему это наша цель - другой вопрос, давайте просто примем это как вызов, который нам дан.) Кажется невозможным, а? В качестве примера давайте реализуем факториал.

Ну, шаг 1 - сказать, что мы могли бы сделать это легко, если бы немного обманули. Используя функции 2 переменных и присваивания, мы можем по крайней мере избежать использования присваивания для настройки рекурсии.

// Here's the function that we want to recurse.
X = function (recurse, n) {
  if (0 == n)
    return 1;
  else
    return n * recurse(recurse, n - 1);
};

// This will get X to recurse.
Y = function (builder, n) {
  return builder(builder, n);
};

// Here it is in action.
Y(
  X,
  5
);

Теперь давайте посмотрим, сможем ли мы обмануть меньше. Ну, во-первых, мы используем назначение, но нам не нужно. Мы можем просто написать X и Y inline.

// No assignment this time.
function (builder, n) {
  return builder(builder, n);
}(
  function (recurse, n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse, n - 1);
  },
  5
);

Но мы используем функции от 2 переменных, чтобы получить функцию от 1 переменной. Можем ли мы это исправить? У умного парня по имени Haskell Curry есть хитрый трюк: если у вас есть хорошие функции более высокого порядка, вам нужны только функции с 1 переменной. Доказательством является то, что вы можете получить из функций от 2 (или более в общем случае) переменных до 1 переменной с помощью чисто механического преобразования текста, например:

// Original
F = function (i, j) {
  ...
};
F(i,j);

// Transformed
F = function (i) { return function (j) {
  ...
}};
F(i)(j);

где ... остается точно таким же. (Этот трюк назван «карри» по имени его изобретателя. Язык Haskell также назван по имени Haskell Curry. Файл, который находится под бесполезными мелочами.) Теперь просто примените это преобразование везде, и мы получим нашу окончательную версию.

// The dreaded Y-combinator in action!
function (builder) { return function (n) {
  return builder(builder)(n);
}}(
  function (recurse) { return function (n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse)(n - 1);
  }})(
  5
);

Не стесняйтесь попробовать. alert (), которые возвращают, привязывают к кнопке, что угодно. Этот код вычисляет факториалы рекурсивно, без использования присваивания, объявлений или функций двух переменных. (Но попытка проследить, как это работает, вероятно, заставит вашу голову кружиться. А передача его без деривации, только слегка переформатированный, приведет к коду, который наверняка сбьет с толку и запутает.)

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

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

Это применимо к языкам, которые поддерживают лямбда-функции . Характер лямбд на основе выражений обычно означает, что они не могут ссылаться на себя по имени. И обходить это путем объявления переменной, обращения к ней, а затем присвоения ей лямбды, чтобы завершить цикл самоссылки, является хрупким. Лямбда-переменная может быть скопирована, а исходная переменная переназначена, что нарушает самоссылку.

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

Ниже приведен пример того, как используется и работает Y-Combinator, в C #.

Использование Y-комбинатора предполагает «необычный» способ построения рекурсивной функции. Сначала вы должны написать свою функцию в виде фрагмента кода, который вызывает ранее существующую функцию, а не себя:

// Factorial, if func does the same thing as this bit of code...
x == 0 ? 1: x * func(x - 1);

Затем вы превращаете это в функцию, которая принимает функцию для вызова и возвращает функцию это делает так. Это называется функционалом, потому что он берет одну функцию и выполняет с ней операцию, которая приводит к другой функции.

// A function that creates a factorial, but only if you pass in
// a function that does what the inner function is doing.
Func<Func<Double, Double>, Func<Double, Double>> fact =
  (recurs) =>
    (x) =>
      x == 0 ? 1 : x * recurs(x - 1);

Теперь у вас есть функция, которая принимает функцию и возвращает другую функцию, которая выглядит как факториал, но вместо вызова самой себя она вызывает аргумент, передаваемый во внешнюю функцию. Как вы делаете это факториалом? Передайте внутреннюю функцию себе. Y-Combinator делает это, будучи функцией с постоянным именем, которая может вводить рекурсию.

// One-argument Y-Combinator.
public static Func<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> F)
{
  return
    t =>  // A function that...
      F(  // Calls the factorial creator, passing in...
        Y(F)  // The result of this same Y-combinator function call...
              // (Here is where the recursion is introduced.)
        )
      (t); // And passes the argument into the work function.
}

Вместо того, чтобы сам факториал вызывать, происходит то, что факториал вызывает генератор факториала (возвращаемый рекурсивным вызовом Y-Combinator). И в зависимости от текущего значения t функция, возвращаемая из генератора, либо снова вызовет генератор, с t - 1, либо просто вернет 1, завершая рекурсию.

Это сложно и загадочно, но все встряхивается во время выполнения, и ключом к его работе является «отложенное выполнение» и разбиение рекурсии на две функции. Внутренний F передается в качестве аргумента , который будет вызываться на следующей итерации, только при необходимости .

Анонимная рекурсия

Комбинатор с фиксированной точкой - это функция высшего порядка fix, которая по определению удовлетворяет эквивалентности

forall f.  fix f  =  f (fix f)

fix f представляет собой решение x для уравнение с фиксированной точкой

               x  =  f x

Факториал натурального числа может быть доказан с помощью

fact 0 = 1
fact n = n * fact (n - 1)

Используя fix, произвольные конструктивные доказательства над общими / µ-рекурсивными функциями могут быть получены без одноименной самоссылки.

fact n = (fix fact') n

где

fact' rec n = if n == 0
                then 1
                else n * rec (n - 1)

так, что

   fact 3
=  (fix fact') 3
=  fact' (fix fact') 3
=  if 3 == 0 then 1 else 3 * (fix fact') (3 - 1)
=  3 * (fix fact') 2
=  3 * fact' (fix fact') 2
=  3 * if 2 == 0 then 1 else 2 * (fix fact') (2 - 1)
=  3 * 2 * (fix fact') 1
=  3 * 2 * fact' (fix fact') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (fix fact') (1 - 1)
=  3 * 2 * 1 * (fix fact') 0
=  3 * 2 * 1 * fact' (fix fact') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (fix fact') (0 - 1)
=  3 * 2 * 1 * 1
=  6

Это формальное доказательство того, что

fact 3  =  6

методично использует эквивалентность комбинатора с фиксированной запятой для переписывает

fix fact'  ->  fact' (fix fact')

Лямбда-исчисление

Формализм нетипизированного лямбда-исчисления состоит из контекстной грамматики

E ::= v        Variable
   |  λ v. E   Abstraction
   |  E E      Application

где v распространяется на переменные, вместе с правилами бета и сокращения

(λ x. B) E  ->  B[x := E]                                 Beta
  λ x. E x  ->  E          if x doesn’t occur free in E   Eta

Восстановление бета заменяет все свободные вхождения переменной x в тело абстракции («функция») B по выражению («аргумент») E. Эта сокращение уменьшает избыточную абстракцию. Иногда это исключается из формализма. неприводимое выражение , к которому не применяется правило редукции, имеет нормальную или каноническую форму .

λ x y. E

- сокращение для

λ x. λ y. E

(абстракция, мультиарность),

E F G

- сокращение для

(E F) G

(приложение левой ассоциативности)

λ x. x

и

λ y. y

являются альфа-эквивалентами .

Абстракция и приложение являются двумя единственными «языковыми примитивами» лямбда-исчисления, но они позволяют кодировать произвольно сложных данных и операций.

Церковные цифры представляют собой кодировку натуральных чисел, сходных с Peano-аксиоматическими натуралами.

   0  =  λ f x. x                 No application
   1  =  λ f x. f x               One application
   2  =  λ f x. f (f x)           Twofold
   3  =  λ f x. f (f (f x))       Threefold
    . . .

SUCC  =  λ n f x. f (n f x)       Successor
 ADD  =  λ n m f x. n f (m f x)   Addition
MULT  =  λ n m f x. n (m f) x     Multiplication
    . . .

Формальное доказательство того, что

1 + 2  =  3

использует правило переписывания бета-сокращения:

   ADD                      1            2
=  (λ n m f x. n f (m f x)) (λ g y. g y) (λ h z. h (h z))
=  (λ m f x. (λ g y. g y) f (m f x)) (λ h z. h (h z))
=  (λ m f x. (λ y. f y) (m f x)) (λ h z. h (h z))
=  (λ m f x. f (m f x)) (λ h z. h (h z))
=  λ f x. f ((λ h z. h (h z)) f x)
=  λ f x. f ((λ z. f (f z)) x)
=  λ f x. f (f (f x))                                       Normal form
=  3

Комбинаторы

В лямбда-исчислении, комбинаторы - это абстракции, которые не содержат свободных переменных. Проще говоря: I, тождественный комбинатор

λ x. x

изоморфен тождественной функции

id x = x

Такие комбинаторы являются примитивными операторами исчислений комбинаторов подобно Лыжная система.

S  =  λ x y z. x z (y z)
K  =  λ x y. x
I  =  λ x. x

Уменьшение бета не сильно нормализует ; не все приводимые выражения, «redexes», сходятся к нормальной форме при бета-редукции. Простым примером является расходящееся применение комбинатора omega ω

λ x. x x

к себе:

   (λ x. x x) (λ y. y y)
=  (λ y. y y) (λ y. y y)
. . .
=  _|_                     Bottom

Приоритет является уменьшение крайних левых подвыражений («голов»). Аппликативный порядок нормализует аргументы перед заменой, нормальный порядок - нет. Эти две стратегии аналогичны стремлению к оценке, например, С и ленивая оценка, например, Haskell.

   K          (I a)        (ω ω)
=  (λ k l. k) ((λ i. i) a) ((λ x. x x) (λ y. y y))

расходится при энергичном сокращении бета-аппликативного порядка

=  (λ k l. k) a ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ y. y y) (λ y. y y))
. . .
=  _|_

, поскольку в строгая семантика

forall f.  f _|_  =  _|_

, но сходится при ленивой бете нормального порядка сокращение

=  (λ l. ((λ i. i) a)) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  a

Если выражение имеет нормальную форму, бета-редукция нормального порядка найдет его.

Y

Существенное свойство Y комбинатора с фиксированной точкой

λ f. (λ x. f (x x)) (λ x. f (x x))

задается в

   Y g
=  (λ f. (λ x. f (x x)) (λ x. f (x x))) g
=  (λ x. g (x x)) (λ x. g (x x))           =  Y g
=  g ((λ x. g (x x)) (λ x. g (x x)))       =  g (Y g)
=  g (g ((λ x. g (x x)) (λ x. g (x x))))   =  g (g (Y g))
. . .                                      . . .

. эквивалентность

Y g  =  g (Y g)

изоморфна

fix f  =  f (fix f)

Нетипизированное лямбда-исчисление может кодировать произвольные конструктивные доказательства над общими / µ-рекурсивными функциями.

 FACT  =  λ n. Y FACT' n
FACT'  =  λ rec n. if n == 0 then 1 else n * rec (n - 1)

   FACT 3
=  (λ n. Y FACT' n) 3
=  Y FACT' 3
=  FACT' (Y FACT') 3
=  if 3 == 0 then 1 else 3 * (Y FACT') (3 - 1)
=  3 * (Y FACT') (3 - 1)
=  3 * FACT' (Y FACT') 2
=  3 * if 2 == 0 then 1 else 2 * (Y FACT') (2 - 1)
=  3 * 2 * (Y FACT') 1
=  3 * 2 * FACT' (Y FACT') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (Y FACT') (1 - 1)
=  3 * 2 * 1 * (Y FACT') 0
=  3 * 2 * 1 * FACT' (Y FACT') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (Y FACT') (0 - 1)
=  3 * 2 * 1 * 1
=  6

(Задержка умножения, слияние)

Для нетипизированного лямбда-исчисления Черча, как было показано, существует рекурсивно перечислимая бесконечность комбинаторов с фиксированной точкой, кроме Y.

 X  =  λ f. (λ x. x x) (λ x. f (x x))
Y'  =  (λ x y. x y x) (λ y x. y (x y x))
 Z  =  λ f. (λ x. f (λ v. x x v)) (λ x. f (λ v. x x v))
 Θ  =  (λ x y. y (x x y)) (λ x y. y (x x y))
  . . .

Бета-редукция нормального порядка превращает неинтенсивное нетипизированное лямбда-исчисление в систему полного переписывания по Тьюрингу.

В Хаскеле комбинатор с фиксированной точкой может быть элегантно реализован

fix :: forall t. (t -> t) -> t
fix f = f (fix f)

Лень Хаскелла нормализуется до конечности до того, как все подвыражения будут оценены.

primes :: Integral t => [t]
primes = sieve [2 ..]
   where
      sieve = fix (\ rec (p : ns) ->
                     p : rec [n | n <- ns
                                , n `rem` p /= 0])

• Дэвид Тернер: Тезис Черча и функциональное программирование
• Алонзо Черч: Неразрешимая проблема теории элементарных чисел
• Лямбда-исчисление
• Теорема Черча – Россера