Как Y-комбинатор вычисляет фиксированную точку программно?
Мне кажется, я математически понимаю идею Y-комбинатора: он возвращает фиксированную точку данного функционала Fтаким образом f = Y(F) где f удовлетворяет f == F(f),
Но я не понимаю, как это происходит с реальной программой вычислений?
Давайте возьмем приведенный здесь пример javascript (я также включил версию CoffeeScript в комментарий, которую легче читать):
var Y = function (F) {
return (function(x) {
return F(function(y) {
return x(x)(y);
});
})(function(x) {
return F(function(y) {
return x(x)(y);
});
});
};
var Factorial = function (factorial) {
return function (n) {
if (n === 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
};
/* Equivalent CoffeeScript:
Y = (F) ->
( (x) -> F((y) -> x(x)(y)) )( (x) -> F((y) -> x(x)(y)) )
Factorial = (factorial) ->
if n == 0 then 1 else n * factorial(n-1)
*/
Y(Factorial)(6) == 720 // => true
computed_factorial = Y(Factorial)
Часть, которую я не понимаю, это то, как computed_factorial функция (фиксированная точка) на самом деле вычисляется? Проследив определение Y, вы обнаружите, что он сталкивается с бесконечной рекурсией в x(x) часть, я не вижу никакого завершающего случая, подразумеваемого там. Тем не менее, это странно возвращается. Кто-нибудь может объяснить?
4 ответа
Я собираюсь использовать синтаксис функции стрелки ES6. Поскольку вы, кажется, знаете CoffeeScript, у вас не должно возникнуть проблем с его чтением.
Вот твой Y комбинатор
var Y = F=> (x=> F (y=> x (x) (y))) (x=> F (y=> x (x) (y)))
Я собираюсь использовать улучшенную версию вашего factorial функция tho. Вместо этого используется аккумулятор, который не позволит оценке превратиться в большую пирамиду. Процесс этой функции будет линейным итеративным, а ваш - рекурсивным. Когда ES6 наконец-то получит устранение хвостовых вызовов, это будет иметь еще большее значение.
Разница в синтаксисе является номинальной. В любом случае это не имеет значения, так как вы просто хотите увидеть, как Y оценивается.
var factorial = Y (fact=> acc=> n=>
n < 2 ? acc : fact (acc*n) (n-1)
) (1);
Ну, это уже заставит компьютер начать делать какую-то работу. Итак, давайте оценим это, прежде чем идти дальше...
Я надеюсь, у вас есть действительно хорошая подсветка скобок в вашем текстовом редакторе...
var factorial
= Y (f=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (1) // sub Y
= (F=> (x=> F (y=> x (x) (y))) (x=> F (y=> x (x) (y)))) (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (1) // apply F=> to fact=>
= (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (1) // apply x=> to x=>
= (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1) // apply fact=> to y=>
= (acc=> n=> n < 2 ? acc : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (acc*n) (n-1)) (1) // apply acc=> to 1
= n=> n < 2 ? 1 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*n) (n-1) // return value
= [Function] (n=> ...)
Итак, вы можете увидеть здесь, после того как мы позвоним:
var factorial = Y(fact=> acc=> n=> ...) (1);
//=> [Function] (n=> ...)
Мы получаем функцию обратно, которая ждет одного ввода, n, Давайте запустим факториал сейчас
Прежде чем мы продолжим, вы можете проверить (и вы должны), что каждая строка здесь верна, скопировав / вставив ее в javascript repl. Каждая строка вернется
24(который является правильным ответом дляfactorial(4), Извините, если я испортил это для вас). Это как когда вы упрощаете дроби, решаете алгебраические уравнения или балансируете химические формулы; каждый шаг должен быть правильным ответом.Обязательно прокрутите весь путь вправо для моих комментариев. Я говорю вам, какую операцию я выполнил в каждой строке. Результат выполненной операции находится на следующей строке.
И удостоверьтесь, что у вас есть удобный инструмент для подсветки скобок снова...
factorial (4) // sub factorial
= (n=> n < 2 ? 1 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*n) (n-1)) (4) // apply n=> to 4
= 4 < 2 ? 1 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*4) (4-1) // 4 < 2
= false ? 1 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*4) (4-1) // ?:
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*4) (4-1) // 1*4
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4) (4-1) // 4-1
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4) (3) // apply y=> to 4
= (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (4) (3) // apply x=> to x=>
= (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4) (3) // apply fact=> to y=>
= (acc=> n=> n < 2 ? acc : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (acc*n) (n-1)) (4) (3) // apply acc=> to 4
= (n=> n < 2 ? 4 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4*n) (n-1)) (3) // apply n=> to 3
= 3 < 2 ? 4 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4*3) (3-1) // 3 < 2
= false ? 4 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4*3) (3-1) // ?:
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4*3) (3-1) // 4*2
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12) (3-1) // 3-1
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12) (2) // apply y=> to 12
= (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (12) (2) // apply x=> to y=>
= (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12) (2) // apply fact=> to y=>
= (acc=> n=> n < 2 ? acc : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (acc*n) (n-1)) (12) (2) // apply acc=> 12
= (n=> n < 2 ? 12 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12*n) (n-1)) (2) // apply n=> 2
= 2 < 2 ? 12 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12*2) (2-1) // 2 < 2
= false ? 12 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12*2) (2-1) // ?:
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12*2) (2-1) // 12*2
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24) (2-1) // 2-1
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24) (1) // apply y=> to 24
= (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (24) (1) // apply x=> to x=>
= (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24) (1) // apply fact=> to y=>
= (acc=> n=> n < 2 ? acc : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (acc*n) (n-1)) (24) (1) // apply acc=> to 24
= (n=> n < 2 ? 24 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24*n) (n-1)) (1) // apply n=> to 1
= 1 < 2 ? 24 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24*1) (1-1) // 1 < 2
= true ? 24 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24*1) (1-1) // ?:
= 24
Я видел другие реализации Y также. Вот простой процесс создания другого (для использования в javascript) с нуля.
// text book
var Y = f=> f (Y (f))
// prevent immediate recursion (javascript is applicative order)
var Y = f=> f (x=> Y (f) (x))
// remove recursion using U combinator
var Y = U (h=> f=> f (x=> h (h) (f) (x)))
// given: U = f=> f (f)
var Y = (h=> f=> f (x=> h (h) (f) (x))) (h=> f=> f (x=> h (h) (f) (x)))
Y-комбинатор является одним из самых интересных явлений в лямбда-исчислении. Я сомневаюсь, что сразу увидев это, можно придумать интерпретацию его функциональности.
Y = f => (g => g(g))(g => n => f(g(g))(n));
Идея состоит в том, чтобы запустить лямбда (анонимную функцию) рекурсивно.
Эй, подожди минутку! Как именно вы можете это сделать, если у вас нет имени для ссылки на функцию и, в первую очередь, для ее вызова внутри себя...?
Давайте попробуем понять его происхождение шаг за шагом. Я буду использовать функции стрелок, поэтому, если вы не знакомы с ними, перейдите по этой ссылке. Они очень просты. x => x средства function(x){return x;}, JS this Ключевое слово имеет другое значение в стрелках, но это не по теме, согласно этой теме.
Поэтому, как всегда, мы будем использовать факториальную функцию, но получаемый нами Y-комбинатор будет действителен для всех рекурсивных функций.
Факториальная функция может быть просто выражена следующим образом
var fa = n => n === 0 ? 1 : n*fa(n-1);
fa(5) // <- 120
Но скажем, что мы не хотим ссылаться на fa функционировать рекурсивно; вместо этого мы хотели бы получить работающую факториальную функцию из гипотетической версии факториальной функции. Что такое гипотетическая факториальная функция? Гипотетическая факториальная функция принимает правильную факториальную функцию и возвращает нам работающую факториальную функцию. Как следующее
var fh = f => n => n === 0 ? 1 : n*f(n-1);
Так что, если я пройду fa функция к fh в качестве аргумента это должно работать. Подобно;
fh(fa)(5); // <- 120
Но мы не хотим ссылаться на другую факториальную функцию, такую как fa так как мы уже "вроде" определили факториальную логику в fh функция. Тогда мы думаем. fh держит f аргумент в закрытии и возвращает мне работающую факториальную функцию (n => n === 0 ? 1 : n*f(n-1)) если я передам ему надлежащую факториальную функцию, как fa, Так что, если я передам себя этому; Быстрая попытка fh(fh)(5) // <- NaN Мех..!
Итак, мы начинаем играть с внутренней функцией. Обычно я бы прошел этот шаг, но было бы полезно увидеть преобразования... так что давайте продолжим. Я могу определить fb функция, чтобы вернуть мне функцию, которая принимает два аргумента, себя и факторный счет n
fb = (f,n) => n === 0 ? 1 : n* f(f,n-1), // fb(fb,5) <- 120
Пока все хорошо, но факториальная функция с двумя аргументами совсем не похожа на то, что я ищу. Я могу отделить их, добавив еще один функциональный шаг, известный как частичное применение.
fc = f => n => n === 0 ? 1 : n* f(f)(n-1), // fc(fc)(5) <- 120
Теперь это очень близко к нашей гипотетической функции fh, Но внутренние шоу f(f)(n-1) Мы должны исправить это, чтобы показать f(n-1). Ну, может быть, мы можем использовать красоту JS IIFE, чтобы помочь нам...
fd = f => n => ((g,n) => n === 0 ? 1 : n * g(n-1))(f(f),n) // fd(fd)(5) <- 120
Вы можете увидеть IIFE..? ((g,n) => n === 0 ? 1 : n * g(n-1))(f(f),n) Тем не менее, пока это выглядит нормально, мне нужно избавиться от двойственного аргумента (g,n) IIFE для достижения желаемого результата. Это займет еще один уровень функциональности при частичном применении.
fe = f => n => (g => n => n === 0 ? 1 : n * g(n-1))(f(f))(n) // fe(fe)(5) <- 120
Теперь у нас внутри g => n => n === 0 ? 1 : n * g(n-1) который является основой нашей гипотетической функции fh, Что означает, что я могу заменить (я люблю эту часть.. точно так же, как замена исчисления; на самом деле это...) fh в приведенной выше функции читать как;
fe = f => n => fh(f(f))(n) // fe(fe)(5) <- 120
Хорошо, чтобы закончить. Что я хотел в первую очередь..? Я хочу кормить fh к функции (Y-комбинатор) и получить его фиксированную точку. Здесь я знаю, что fe(fe) использования fh и возвращает мне правильно работающую факториальную функцию. Итак, давайте определим функцию, которая примет нашу гипертетическую рекурсивную функцию в качестве аргумента и даст нам что-то работающее (исправлено). IIFE, чтобы помочь снова.
Y = f => (g => g(g))(g => n => f(g(g))(n));
Так что это должно работать на все. Давайте попробуем наш Y комбинатор с гипотетической функцией Фибоначчи.
var Y = f => (g => g(g))(g => n => f(g(g))(n)),
fibH = f => n => n === 0 ? 0
: n === 1 ? 1
: f(n-2) + f(n-1),
fibo = Y(fibH);
console.log(fibo(10));Я надеюсь, что все ясно...
В ленивом языке оценки Y-комбинатор может быть определен как:
Y = (f =>
(x => f( x(x) ))
(x => f( x(x) )))
Но так как Javascript - это язык оценки с нетерпением, определение Y таким образом приведет к тому, что часть x(x) будет бесконечно рекурсировать в то время, когда вы пытаетесь применить Y к функции.
Чтобы обойти эту проблему, можно ввести анонимную функцию-обертку, чтобы задержать выполнение x. Эта функция-обертка при вызове будет вести себя так же, как x(x), но сразу же вернется, поскольку это просто определение функции.
Зная, что x(x) будет связан с рекурсивной функцией, в случае примера:
Factorial = f => n => n==0 ? 1 : n*f(n-1)
Мы можем заранее сказать, что ему будет передан только один аргумент. Это позволяет нам использовать следующий шаблон для генерации анонимной функции, которая ведет себя так же, как любая заданная функция f (x):
f => x => f(x)
Когда мы применим этот шаблон к члену x(x), Y больше не будет повторяться бесконечно и становится:
Y = (f =>
(x => f( y => x(x)(y) ))
(x => f( y => x(x)(y) )))
Я хотел бы уточнить (это будет долгое чтение) ответ diwo о стремлении к бесконечной оценке x (x).
Прочитав ответ diwo, я очень быстро просмотрел и пропустил незаинтересованные части этого и ниже, как я понимаю это.
Наши собственные обозначения, определения
Обозначим оценку (выполнение программы) через x -> v, что означает "x оценивает значение v".
И в нетерпеливом, и в ленивом вычислении анонимная функция рассматривается как значение, т.е. она уже оценена, поэтому оценка функции немедленно останавливается.
Тогда энергичная оценка f (y) будет выглядеть следующим образом: f (y) -> (сначала вычислите y по v) -> f (v) -> (примените функцию f к аргументу v) -> f (v). (теперь (после второго шага) функция действительно применяется, увидим через секунду)
В то время как для контраста, ленивая оценка f (y) пропустит первый шаг: f (y) -> (применить функцию f к аргументу v) -> f (y) (теперь функция действительно применяется, но обратите внимание, что y остается неизменным).
Пусть теперь F будет Factorial, как в ответе diwo, и Y, как определено в первый раз:
Y = (f =>
(x => f( x(x) ))
(x => f( x(x) )))
а также
F = Factorial = f => n => n==0 ? 1 : n*f(n-1)
Давайте приступим к делу
Вся оценка (не работает) YF будет выглядеть так:
YF -> w (w): = (x => F (x (x))) (x => F (x (x))) -> F ((x => F (x (x)))) (x => F( x(x)))) = F( w(w)), где w обозначение для (x => F (x (x))). Теперь это то же самое, что и в усердной, и в ленивой оценке, но теперь мы получаем разницу.
Первое решение + ленивый
В ленивом вычислении, F будет "абстрактно" (без оценки) применяться к w (w) и, таким образом, оценивать
-> (n => n==0? 1: n*(w(w))(n-1))),
что затем остановит оценку, так как это анонимная функция, и мы уже знаем, что анонимные функции больше не оцениваются.
Первое (не рабочее) решение + нетерпеливый
В стремлении к контрасту F (w (w)) -> F (v), что означает, что аргумент w (w) должен быть оценен первым.
Теперь оцените w (w) = (x => F (x (x))) (x => F (x (x))) -> F ((x => F (x (x)))) (x = > F (x (x)))) = F (w (w)). Теперь это в нетерпеливой оценке оценивает дальнейшее использование правила, чтобы сначала оценить аргумент, то есть w (w). Который, как мы только что видели, снова оценивается как F (w (w)). Поэтому мы застряли в петле... YF -> W (W) -> F (W (W)) -> F (F (W (W))) -> F (F (F (W (W)))) ->... ошибка.
Второе (рабочее) решение + стремление
Если мы улучшим это с помощью определения
Y = (f =>
(x => f( y => x(x)(y) ))
(x => f( y => x(x)(y) )))
вместо этого оценка похожа на ленивую ситуацию:
YF -> z (z): = (x => F (y => x (x) (y))) (x => F (y => x (x) (y))) -> F (y => (x => F (y => x (x) (y))) ((x => F (y => x (x) (y)))) (y))) = F ( y => z(z)(y))).
Как правило, мы должны оценить аргумент (y => z(z)(y)). Поскольку это анонимная функция, ее оценка завершена, поэтому мы продолжаем применять F к (y => z (z) (y)) так же, как при ленивой оценке. Теперь мы получаем
F( y => z(z)(y))) -> (n => n==0? 1: n*(( y => z(z)(y))(n-1))), который теперь заканчивается оценка, так как это анонимная функция. Это похоже на первую ленивую оценку.
Так что да, почти через 3 года я отвечаю на свой вопрос. Одна из причин, по которой я это делаю, заключается в том, что ни один из ответов не помог с первоначальной технической проблемой, с которой я столкнулся. Это был комментарий @Bergi под вопросом, который сразу же помог мне.
Вопрос, который беспокоит меня в первоначальном вопросе, был довольно тривиальным. Я просто сделал глупую ошибку и не смог правильно отследить выполнение. Я спросил:
[...] вы обнаружите, что он сталкивается с бесконечной рекурсией в точке х (х)
Нет, на самом деле это не так.
var Y = (F) => ( x => F( y => x(x)(y) ) )( x => F( y => x(x)(y) ) )
var Factorial = (factorial) => (n => n == 0 ? 1 : n * factorial(n-1))
Когда ты бежишь Y(Factorial)ТОЛЬКО 1-я анонимная функция в Yопределение x => F( y => x(x)(y) ) выполняется, что в свою очередь делает F казнены.
F == Factorial в этом случае, но возвращение F это просто другая функция n => n == 0 ? 1 : n * factorial(n-1), где factorial = y => x(x)(y), Это n => ... вещь является окончательным возвращаемым значением, дальнейшее выполнение не происходит.
Таким образом, рассматриваемая часть, x(x) вещь, всегда "в ловушке" внутри factorial = y => x(x)(y)Таким образом, "бесконечная рекурсия" никогда не происходила.
Это должно завершить мой оригинальный вопрос.