¿Qué es un Y-combinator?

Un Y-combinator es un concepto de ciencias de la computación desde el lado “funcional” de las cosas. La mayoría de los progtwigdores no saben mucho acerca de los combinadores, si es que han oído hablar de ellos.

  • ¿Qué es un Y-combinator?
  • ¿Cómo funcionan los combinadores?
  • ¿Para qué son buenos?
  • ¿Son útiles en los lenguajes de procedimiento?

Si estás listo para una lectura larga, Mike Vanier tiene una gran explicación . Para resumir, le permite implementar recursiones en un idioma que no necesariamente lo admite de forma nativa.

Un Y-combinator es un “funcional” (una función que opera en otras funciones) que permite la recursión, cuando no se puede referir a la función desde sí mismo. En la teoría de la informática, generaliza la recursión , abstrae su implementación y, por lo tanto, la separa del trabajo real de la función en cuestión. El beneficio de no necesitar un nombre en tiempo de comstackción para la función recursiva es una especie de bonificación. =)

Esto es aplicable en idiomas que admiten funciones lambda . La naturaleza basada en la expresión de lambdas generalmente significa que no pueden referirse a sí mismos por su nombre. Y trabajando alrededor de esto para declarar la variable, referirnos a ella, luego asignarle la lambda, para completar el ciclo de autorreferencia, es frágil. La variable lambda se puede copiar y la variable original se puede reasignar, lo que rompe la autorreferencia.

Los Y-combinators son engorrosos de implementar, y a menudo usar, en lenguajes de tipo estático (que a menudo son los lenguajes de procedimiento ), porque las restricciones de tipeo usualmente requieren que el número de argumentos para la función en cuestión se conozca en tiempo de comstackción. Esto significa que se debe escribir un combinador y para cualquier conteo de argumentos que se necesite usar.

A continuación se muestra un ejemplo de cómo el uso y el funcionamiento de un Y-Combinator, en C #.

Usar un combinador en Y implica una forma “inusual” de construir una función recursiva. Primero debe escribir su función como un fragmento de código que llama a una función preexistente, en lugar de a sí misma:

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

Luego convierte eso en una función que toma una función para llamar, y devuelve una función que lo hace. Esto se denomina funcional porque requiere una función y realiza una operación que da como resultado otra función.

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

Ahora tiene una función que toma una función y devuelve otra función que se parece a un factorial, pero en lugar de llamarse a sí misma, llama al argumento pasado a la función externa. ¿Cómo haces de esto el factorial? Pase la función interna a sí mismo. El Y-Combinator lo hace, al ser una función con un nombre permanente, que puede introducir la recursión.

 // One-argument Y-Combinator. public static Func Y(Func, Func> 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. } 

En lugar de llamarse a sí mismo factorialmente, lo que sucede es que el factorial llama al generador factorial (devuelto por la llamada recursiva a Y-Combinator). Y dependiendo del valor actual de t, la función devuelta por el generador llamará nuevamente al generador, con t – 1, o simplemente devolverá 1, terminando la recursión.

Es complicado y críptico, pero todo se agita en el tiempo de ejecución, y la clave de su funcionamiento es la “ejecución diferida” y la ruptura de la recursión para abarcar dos funciones. La F interna se pasa como un argumento , para llamarla en la siguiente iteración, solo si es necesario .

Lo he levantado de http://www.mail-archive.com/boston-pm@mail.pm.org/msg02716.html, que es una explicación que escribí hace varios años.

Usaré JavaScript en este ejemplo, pero muchos otros idiomas también funcionarán.

Nuestro objective es poder escribir una función recursiva de 1 variable usando solo funciones de 1 variable y sin asignaciones, definiendo cosas por nombre, etc. (Por qué este es nuestro objective es otra pregunta, tomemos esto como el desafío que tenemos se dan.) Parece imposible, ¿eh? Como ejemplo, implementemos factorial.

Bueno, el paso 1 es decir que podríamos hacer esto fácilmente si hiciéramos trampa un poco. Usando funciones de 2 variables y asignación, al menos podemos evitar tener que usar la asignación para configurar la recursión.

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

Ahora veamos si podemos hacer trampas menos. Bueno, en primer lugar estamos usando la asignación, pero no es necesario. Podemos simplemente escribir X e Y en línea.

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

Pero estamos usando funciones de 2 variables para obtener una función de 1 variable. ¿Podemos arreglar eso? Bueno, un chico inteligente llamado Haskell Curry tiene un buen truco, si tienes buenas funciones de orden superior, entonces solo necesitas funciones de 1 variable. La prueba es que puede obtener de funciones de 2 (o más en el caso general) variables a 1 variable con una transformación de texto puramente mecánica como esta:

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

donde … permanece exactamente igual. (Este truco se llama “currying” en honor a su inventor. El lenguaje Haskell también se llama así en honor a Haskell Curry. Anótelo bajo trivialidades inútiles). Ahora solo aplique esta transformación en todas partes y obtendremos nuestra versión final.

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

Siéntase libre de probarlo. alerta () que regresa, átela a un botón, lo que sea. Ese código calcula factoriales, recursivamente, sin usar asignación, declaraciones o funciones de 2 variables. (Pero intentar rastrear cómo funciona es probable que le dé vueltas a la cabeza. Y entregarlo, sin la derivación, con un ligero reformateo dará como resultado un código que seguramente desconcertará y confundirá).

Puede reemplazar las 4 líneas que definen recursivamente factorial con cualquier otra función recursiva que desee.

Me pregunto si hay algún uso al intentar construir esto desde cero. Veamos. Aquí hay una función factorial recursiva básica:

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

Reorganicemos y creemos una nueva función llamada fact que devuelve una función anónima de cálculo factorial en lugar de realizar el cálculo en sí:

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

Eso es un poco raro, pero no tiene nada de malo. Estamos generando una nueva función factorial en cada paso.

La recursión en esta etapa todavía es bastante explícita. La función de fact debe conocer su propio nombre. Vamos a parametrizar la llamada recursiva:

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

Eso es genial, pero el recurser aún necesita saber su propio nombre. Vamos a parametrizar eso también:

 function recurser(f) { return fact(function(x) { return f(f)(x); }); } var factorial = recurser(recurser); 

Ahora, en lugar de llamar al recurser(recurser) directamente, recurser(recurser) una función de envoltura que devuelva su resultado:

 function Y() { return (function(f) { return f(f); })(recurser); } var factorial = Y(); 

Ahora podemos deshacernos del nombre del recurser completo; es solo un argumento para la función interna de Y, que puede ser reemplazada por la función misma:

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

El único nombre externo al que se hace referencia sigue siendo fact , pero debería estar claro ahora que también se puede parametrizar fácilmente, creando la solución completa y genérica:

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

La mayoría de las respuestas anteriores describen qué es el Y-combinator pero no para qué sirve.

Los combinadores de puntos fijos se usan para mostrar que el cálculo lambda se está completando . Este es un resultado muy importante en la teoría de la computación y proporciona una base teórica para la progtwigción funcional .

El estudio de los combinadores de punto fijo también me ha ayudado a comprender realmente la progtwigción funcional. Sin embargo, nunca he encontrado ningún uso para ellos en la progtwigción real.

y-combinator en JavaScript :

 var Y = function(f) { return (function(g) { return g(g); })(function(h) { return function() { return f(h(h)).apply(null, arguments); }; }); }; var factorial = Y(function(recurse) { return function(x) { return x == 0 ? 1 : x * recurse(x-1); }; }); factorial(5) // -> 120 

Editar : Aprendo mucho mirando el código, pero este es un poco difícil de tragar sin un poco de fondo, lo siento. Con algunos conocimientos generales presentados por otras respuestas, puede comenzar a distinguir lo que está sucediendo.

La función Y es el “combinador y”. Ahora eche un vistazo a la línea var factorial donde se usa Y. Observe que le pasa una función que tiene un parámetro (en este ejemplo, recurse ) que también se usa más adelante en la función interna. El nombre del parámetro básicamente se convierte en el nombre de la función interna que le permite realizar una llamada recursiva (ya que usa recurse() en su definición). El combinador y realiza la magia de asociar la función interna anónima con el nombre del parámetro del función pasó a Y.

Para la explicación completa de cómo Y hace la magia, mira el artículo vinculado (no por mí, por cierto).

Para los progtwigdores que no han encontrado progtwigción funcional en profundidad, y no les importa comenzar ahora, pero son ligeramente curiosos:

El combinador Y es una fórmula que le permite implementar la recursión en una situación en la que las funciones no pueden tener nombres, pero se pueden pasar como argumentos, usarse como valores de retorno y definirse dentro de otras funciones.

Funciona pasando la función a sí mismo como un argumento, por lo que puede llamarse a sí mismo.

Es parte del cálculo lambda, que en realidad es matemática pero es efectivamente un lenguaje de progtwigción, y es bastante fundamental para la informática y especialmente para la progtwigción funcional.

El valor práctico diario del combinador en Y es limitado, ya que los lenguajes de progtwigción tienden a permitirle nombrar funciones.

En caso de que necesite identificarlo en una alineación policial, se verá así:

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

Generalmente puede detectarlo debido a lo repetido (λx.f (xx)) .

Los símbolos λ son la letra griega lambda, que le da su nombre al cálculo lambda, y hay muchos términos de estilo (λx.t) porque así es como se ve el cálculo lambda.

Otras respuestas brindan una respuesta bastante concisa a esto, sin un hecho importante: no es necesario implementar un combinador de punto fijo en ningún lenguaje práctico de esta forma enrevesada y hacerlo no tiene ningún propósito práctico (excepto “mira, sé qué Y-combinator”). es”). Es un concepto teórico importante, pero de poco valor práctico.

Un Y-Combinator es otro nombre para un condensador de flujo.

Aquí hay una implementación de JavaScript del Y-Combinator y la función Factorial (del artículo de Douglas Crockford, disponible en: 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); 

He escrito una especie de “guía de idiotas” para el Y-Combinator en Clojure y Scheme para ayudarme a enfrentarlo. Ellos están influenciados por el material en “The Little Schemer”

En Scheme: https://gist.github.com/z5h/238891

o Clojure: https://gist.github.com/z5h/5102747

Ambos tutoriales tienen un código intercalado con comentarios y deben cortarse y prepararse para su editor favorito.

El y-combinator implementa la recursión anónima. Entonces, en lugar de

 function fib( n ){ if( n< =1 ) return n; else return fib(n-1)+fib(n-2) } 

tu puedes hacer

 function ( fib, n ){ if( n< =1 ) return n; else return fib(n-1)+fib(n-2) } 

por supuesto, el combinador de y solo funciona en lenguajes de llamada por nombre. Si desea usar esto en cualquier lenguaje normal de call-by-value, necesitará el z-combinator relacionado (y-combinator diverge / infinite-loop).

Un combinador de punto fijo (u operador de punto fijo) es una función de orden superior que calcula un punto fijo de otras funciones. Esta operación es relevante en la teoría del lenguaje de progtwigción porque permite la implementación de la recursión en forma de una regla de reescritura, sin el respaldo explícito del motor de tiempo de ejecución del lenguaje. (src Wikipedia)

Este operador puede simplificar tu vida:

 var Y = function(f) { return (function(g) { return g(g); })(function(h) { return function() { return f.apply(h(h), arguments); }; }); }; 

Entonces evitas la función adicional:

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

Finalmente, llamas a fac(5) .

Recursión anónima

Un combinador de punto fijo es una fix función de orden superior que, por definición, cumple la equivalencia

 forall f. fix f = f (fix f) 

fix f representa una solución x a la ecuación de punto fijo

  x = fx 

El factorial de un número natural puede ser probado por

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

Usando el fix , las pruebas constructivas arbitrarias sobre las funciones generales / μ-recursivas pueden derivarse sin autorreferencialidad anónima.

 fact n = (fix fact') n 

dónde

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

tal que

  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 

Esta prueba formal de que

 fact 3 = 6 

utiliza metódicamente la equivalencia del combinador de punto fijo para reescribir

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

Cálculo Lambda

El formalismo de cálculo lambda sin tipo consiste en una gramática libre de contexto

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

donde v abarca variables, junto con las reglas de reducción beta y eta

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

La reducción beta sustituye todas las ocurrencias libres de la variable x en la abstracción (“función”) del cuerpo B por la expresión (“argumento”) E La reducción de Eta elimina la abstracción redundante. A veces se omite del formalismo. Una expresión irreductible , a la que no se aplica ninguna regla de reducción, es en forma normal o canónica .

 λ x y. E 

es una abreviatura de

 λ x. λ y. E 

(abstracción multiarity),

 EFG 

es una abreviatura de

 (EF) G 

(aplicación de asociatividad a la izquierda),

 λ x. x 

y

 λ y. y 

son equivalentes alfa

La abstracción y la aplicación son las dos únicas “primitivas del lenguaje” del cálculo lambda, pero permiten la encoding de datos y operaciones arbitrariamente complejas.

Los numerales de la Iglesia son una encoding de los números naturales similares a los naturales Peano-axiomáticos.

  0 = λ f x. x No application 1 = λ f x. fx One application 2 = λ f x. f (fx) Twofold 3 = λ f x. f (f (fx)) Threefold . . . SUCC = λ nf x. f (nfx) Successor ADD = λ nmf x. nf (mfx) Addition MULT = λ nmf x. n (mf) x Multiplication . . . 

Una prueba formal de que

 1 + 2 = 3 

usando la regla de reescritura de la reducción beta:

  ADD 1 2 = (λ nmf x. nf (mfx)) (λ g y. gy) (λ h z. h (hz)) = (λ mf x. (λ g y. gy) f (mfx)) (λ h z. h (hz)) = (λ mf x. (λ y. fy) (mfx)) (λ h z. h (hz)) = (λ mf x. f (mfx)) (λ h z. h (hz)) = λ f x. f ((λ h z. h (hz)) fx) = λ f x. f ((λ z. f (fz)) x) = λ f x. f (f (fx)) Normal form = 3 

Combinators

En el cálculo lambda, los combinadores son abstracciones que no contienen variables libres. Más simple: I , el combinador de identidad

 λ x. x 

isomorfo a la función de identidad

 id x = x 

Dichos combinators son los operadores primitivos de cálculos combinadores como el sistema SKI.

 S = λ xy z. xz (yz) K = λ x y. x I = λ x. x 

La reducción beta no se normaliza mucho ; no todas las expresiones reducibles, “redexes”, convergen a la forma normal en la reducción beta. Un ejemplo simple es la aplicación divergente del combinador omega ω

 λ x. xx 

a sí mismo:

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

La reducción de las subexpresiones más a la izquierda (“cabezas”) tiene prioridad. La orden de aplicación normaliza los argumentos antes de la sustitución, el orden normal no. Las dos estrategias son análogas a la evaluación entusiasta, por ejemplo, C, y la evaluación perezosa, por ejemplo, Haskell.

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

diverge bajo la ansiosa reducción beta de orden aplicativa

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

ya que en estricta semántica

 forall f. f _|_ = _|_ 

pero converge bajo la pereza de la reducción beta de orden normal

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

Si una expresión tiene una forma normal, la reducción beta de orden normal la encontrará.

Y

La propiedad esencial del combinador de punto fijo Y

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

es dado por

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

La equivalencia

 Y g = g (Y g) 

es isomorfo a

 fix f = f (fix f) 

El cálculo lambda sin tipo puede codificar pruebas constructivas arbitrarias sobre funciones generales / μ-recursivas.

  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 

(Multiplicación retrasada, confluencia)

Para el cálculo lambda no tipificado de Churchian, se ha demostrado que existe una infinita enumeración recursiva de combinadores de punto fijo además de Y

  X = λ f. (λ x. xx) (λ x. f (xx)) Y' = (λ x y. xyx) (λ y x. y (xyx)) Z = λ f. (λ x. f (λ v. xxv)) (λ x. f (λ v. xxv)) Θ = (λ x y. y (xxy)) (λ x y. y (xxy)) . . . 

La reducción beta de orden normal hace que el cálculo lambda no tipificado no extendido sea un sistema de reescritura completo de Turing.

En Haskell, el combinador de punto fijo se puede implementar con elegancia

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

La pereza de Haskell se normaliza a una finitud antes de que todas las subexpresiones hayan sido evaluadas.

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

  • David Turner: Tesis de la Iglesia y Progtwigción Funcional
  • Iglesia de Alonzo: un problema insoluble de la teoría numérica elemental
  • Cálculo Lambda
  • Teorema de iglesia-Rosser

Como novato en combinadores, encontré el artículo de Mike Vanier (gracias a Nicholas Mancuso) de gran ayuda. Me gustaría escribir un resumen, además de documentar mi comprensión, si pudiera ser de ayuda para otros, estaría muy contento.

De Crappy a Less Crappy

Usando factorial como ejemplo, usamos la siguiente función almost-factorial para calcular factorial del número x :

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

En el pseudocódigo anterior, almost-factorial toma la función f número x ( almost-factorial está cursado, por lo que puede verse como tomar la función f y devolver una función de 1 aria).

Cuando almost-factorial calcula factorial para x , delega el cálculo de factorial para x - 1 a la función f y acumula ese resultado con x (en este caso, multiplica el resultado de (x – 1) con x).

Se puede ver como almost-factorial toma almost-factorial en una versión repugnante de la función factorial (que solo puede calcular hasta el número x - 1 ) y devuelve una versión menos cruda de factorial (que calcula hasta el número x ). Como en esta forma:

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

Si repetidamente pasamos la versión menos funcional de factorial a almost-factorial , eventualmente obtendremos nuestra función factorial deseada f . Donde se puede considerar como:

 almost-factorial f = f 

Punto fijo

El hecho de que almost-factorial f = f significa f es el punto fijo de función almost-factorial .

Esta fue una forma realmente interesante de ver las relaciones de las funciones anteriores y fue un momento increíble para mí. (Por favor, lea la publicación de Mike sobre el punto fijo si no lo ha hecho)

Tres funciones

Para generalizar, tenemos una función no recursiva fn (como nuestra casi factorial), tenemos su función de punto fijo fr (como nuestra f), entonces lo que Y hace es cuando le das a Y fn , Y devuelve el punto fijo función de fn .

Entonces en resumen (simplificado asumiendo que fr toma solo un parámetro; x degenera a x - 1 , x - 2 … en recursión):

  • Definimos los cálculos centrales como fn : def fn fr x = ...accumulate x with result from (fr (- x 1)) , esta es la función casi útil , aunque no podemos usar fn directamente en x , será útil muy pronto Este fn no recursivo usa una función fr para calcular su resultado
  • fn fr = fr , fr es el punto fijo de fn , fr es la función útil , podemos usar fr en x para obtener nuestro resultado
  • Y fn = fr , Y devuelve el punto fijo de una función, Y convierte nuestra función casi útil fn en fr útil

Derivando Y (no incluido)

Voy a omitir la derivación de Y y voy a entender Y La publicación de Mike Vainer tiene muchos detalles.

La forma de Y

Y se define como (en formato de cálculo lambda ):

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

Si reemplazamos la variable s a la izquierda de las funciones, obtenemos

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

Entonces, de hecho, el resultado de (Y f) es el punto fijo de f .

¿Por qué funciona (Y f) ?

Dependiendo de la firma de f , (Y f) puede ser una función de cualquier aridad, para simplificar, supongamos que (Y f) solo toma un parámetro, como nuestra función factorial.

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

desde fn fr = fr , continuamos

 => 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))) 

el cálculo recursivo finaliza cuando el más interno (fn fr 1) es el caso base y fn no utiliza fr en el cálculo.

Mirando a Y otra vez

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

Asi que

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

Para mí, las partes mágicas de esta configuración son:

  • fn y fr interdependen entre sí: fr ‘wraps’ fn inside, cada vez que fr se usa para calcular x , ‘engendra’ (‘lifts’?) an fn y delega el cálculo a esa fn (pasando en sí mismo fr y x ); por otro lado, fn depende de fr y usa fr para calcular el resultado de un problema menor x-1 .
  • En el momento fr se usa para definir fn (cuando fn usa fr en sus operaciones), el real fr aún no está definido.
  • Es fn que define la lógica comercial real. En función de fn , Y crea fr – una función auxiliar en una forma específica – para facilitar el cálculo de fn de forma recursiva .

Me ayudó a entender Y esta manera en este momento, espero que ayude.

Por cierto, también encontré muy bueno el libro Introducción a la progtwigción funcional a través del cálculo de Lambda , solo soy parte de él y el hecho de que no pude entender Y en el libro me llevó a esta publicación.

Aquí hay respuestas a las preguntas originales , comstackdas a partir del artículo (que TOTALMENTE merece la pena leer) mencionadas en la respuesta de Nicholas Mancuso , así como otras respuestas:

¿Qué es un Y-combinator?

Un Y-combinator es una función “funcional” (o una función de orden superior, una función que opera en otras funciones) que toma un único argumento, que es una función que no es recursiva, y devuelve una versión de la función que es recursivo


Algo recursivo =), pero una definición más profunda:

Un combinador: es solo una expresión lambda sin variables libres.
Variable libre: es una variable que no es una variable vinculada.
Variable enlazada – variable que está contenida dentro del cuerpo de una expresión lambda que tiene ese nombre de variable como uno de sus argumentos.

Otra forma de pensar sobre esto es que el combinador es una expresión lambda, en la que puedes reemplazar el nombre de un combinador por su definición donde sea que se encuentre y hacer que todo funcione (entrarás en un ciclo infinito si el combinador lo hiciera contiene referencia a sí mismo, dentro del cuerpo lambda).

Y-combinator es un combinador de punto fijo.

El punto fijo de una función es un elemento del dominio de la función que se asigna a sí mismo mediante la función.
Es decir, c es un punto fijo de la función f(x) si f(c) = c
Esto significa f(f(...f(c)...)) = fn(c) = c

¿Cómo funcionan los combinadores?

Los siguientes ejemplos suponen una tipificación fuerte + dinámica :

Lazy (orden normal) Y-combinator:
Esta definición se aplica a los lenguajes con evaluación perezosa (también: diferida, llamada por necesidad): estrategia de evaluación que retrasa la evaluación de una expresión hasta que se necesita su valor.

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

Lo que esto significa es que, para una función dada f (que es una función no recursiva), la función recursiva correspondiente se puede obtener primero calculando λx.f(xx) , y luego aplicando esta expresión lambda a sí mismo.

Estricto combinador en Y (orden aplicativa):
Esta definición se aplica a los lenguajes con evaluación estricta (también: ávida, ávida): estrategia de evaluación en la que una expresión se evalúa tan pronto como está vinculada a una variable.

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

Es lo mismo que perezoso en su naturaleza, solo tiene un envoltorio adicional de λ para retrasar la evaluación del cuerpo de la lambda. He hecho otra pregunta , algo relacionada con este tema.

¿Para qué son buenos?

Robín tomado prestado de la respuesta de Chris Ammerman : Y-combinator generaliza la recursión, abstrae su implementación y, por lo tanto, la separa del trabajo real de la función en cuestión.

A pesar de que Y-combinator tiene algunas aplicaciones prácticas, es principalmente un concepto teórico, cuya comprensión ampliará su visión general y, probablemente, boostá sus habilidades analíticas y de desarrollo.

¿Son útiles en los lenguajes de procedimiento?

Como dijo Mike Vanier : es posible definir un combinador Y en muchos lenguajes estáticos, pero (al menos en los ejemplos que he visto), tales definiciones generalmente requieren algún hacker de tipo no obvio, porque el combinador en sí no lo hace t tiene un tipo estático directo. Eso está más allá del scope de este artículo, así que no lo mencionaré más

Y como lo menciona Chris Ammerman : la mayoría de los lenguajes de procedimiento tienen tipado estático.

Así que responde a esto, no realmente.

Creo que la mejor manera de responder esto es elegir un idioma, como JavaScript:

 function factorial(num) { // If the number is less than 0, reject it. if (num < 0) { return -1; } // If the number is 0, its factorial is 1. else if (num == 0) { return 1; } // Otherwise, call this recursive procedure again. else { return (num * factorial(num - 1)); } } 

Now rewrite it so that it doesn't use the name of the function inside the function, but still calls it recursively.

The only place the function name factorial should be seen is at the call site.

Hint: you can't use names of functions, but you can use names of parameters.

Work the problem. Don't look it up. Once you solve it, you will understand what problem the y-combinator solves.