functional-programming computer-science theory definition combinators

functional programming - ¿Qué es un combinador en Y?



functional-programming computer-science (18)

Un combinador en Y es un concepto informático desde el lado "funcional" de las cosas. La mayoría de los programadores no saben mucho acerca de los combinadores, incluso si han oído hablar de ellos.

  • ¿Qué es un combinador en Y?
  • ¿Cómo funcionan los combinadores?
  • ¿Para qué son buenos?
  • ¿Son útiles en lenguajes procesales?

Recursion anonima

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

forall f. fix f = f (fix f)

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

x = f x

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

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

Usando fix , se pueden derivar pruebas constructivas arbitrarias sobre funciones recursivas generales / μ sin una autoreferencialidad no simétrica.

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

Usa metódicamente la equivalencia de combinador de punto fijo para reescrituras.

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

Calculo lambda

El formalismo del cálculo lambda no tipificado consiste en una gramática libre de contexto.

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

donde v extiende sobre las 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 apariciones libres de la variable x en la abstracción ("función") cuerpo B por la expresión ("argumento") E La reducción de etapa elimina la abstracción redundante. A veces se omite en el formalismo. Una expresión irreductible , a la que no se aplica ninguna regla de reducción, se encuentra en forma normal o canónica .

λ x y. E

es taquigrafía para

λ x. λ y. E

(abstracción multiarity),

E F G

es taquigrafía para

(E F) G

(asociatividad izquierda)

λ x. x

y

λ y. y

son alfa-equivalentes .

La abstracción y la aplicación son las dos únicas "primitivas del lenguaje" del cálculo lambda, pero permiten la codificación de datos y operaciones arbitrariamente complejos.

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

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 . . .

Una prueba formal de que

1 + 2 = 3

usando la regla de reescritura de reducción beta:

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

Combinadores

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

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

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

La reducción beta no está fuertemente normalizada ; no todas las expresiones reducibles, "redexes", convergen a la forma normal bajo la reducción beta. Un ejemplo simple es la aplicación divergente del combinador ω

λ x. x x

a sí mismo:

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

Se prioriza la reducción de las subexpresiones más a la izquierda ("cabezas"). El orden aplicativo 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. x x) (λ y. y y))

diverge bajo la ansiosa reducción beta de orden aplicativo

= (λ 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)) . . . = _|_

ya que en semántica estricta

forall f. f _|_ = _|_

pero converge bajo la perezosa reducción de orden normal

= (λ l. ((λ i. i) a)) ((λ x. x x) (λ y. y y)) = (λ l. a) ((λ x. x x) (λ y. y y)) = 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 (x x)) (λ x. f (x x))

es dado por

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

La equivalencia

Y g = g (Y g)

es isomorfo a

fix f = f (fix f)

El cálculo lambda no tipificado 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 infinidad recursivamente enumerable de combinadores de punto fijo además de 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)) . . .

La reducción beta de orden normal hace que el cálculo lambda sin tipo no extendido sea un sistema de reescritura Turing-complete.

En Haskell, el combinador de punto fijo se puede implementar elegantemente

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

La pereza de Haskell se normaliza a una finidad antes de que se hayan evaluado todas las subexpresiones.

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

Aquí están las respuestas a las preguntas originales , compiladas del artículo (que es TOTALY vale la pena leer) mencionado en la respuesta de Nicholas Mancuso , así como otras respuestas:

¿Qué es un combinador en Y?

Un combinador en Y es una "función" (o una función de orden superior, una función que opera en otras funciones) que toma un solo 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 acerca de esto es que el combinador es una expresión lambda, en la que puede reemplazar el nombre de un combinador con su definición donde sea que se encuentre y todo seguirá funcionando (entrará en un bucle infinito si el combinador lo haría). contienen 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 por 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 ejemplos a continuación suponen una tipificación dinámica + fuerte :

Combinador Y perezoso (de orden normal):
Esta definición se aplica a los idiomas 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(x x)) (λx.f(x x)) = λf.(λx.(x x)) (λx.f(x x))

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í misma.

Combinador en Y estricto (orden aplicativo):
Esta definición se aplica a los idiomas con una estrategia de evaluación - evaluación estricta (también: ávida, codiciosa) en la que una expresión se evalúa tan pronto como está vinculada a una variable.

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

Es igual a uno perezoso en su naturaleza, solo tiene un envoltorio de λ extra para retrasar la evaluación del cuerpo del lambda. He hecho otra pregunta , algo relacionada con este tema.

¿Para qué son buenos?

Robado de la respuesta por Chris Ammerman : el combinador en Y generaliza la recursión, abstrae su implementación y, por lo tanto, la separa del trabajo real de la función en cuestión.

Aunque el Y-combinator tiene algunas aplicaciones prácticas, es principalmente un concepto teórico, cuya comprensión expandirá su visión general y, probablemente, aumentará sus habilidades analíticas y de desarrollador.

¿Son útiles en lenguajes procesales?

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

Y como lo mencionó Chris Ammerman : la mayoría de los lenguajes de procedimiento tienen tipificación estática.

Así que responde a esta - no realmente.

Aquí hay una implementación de JavaScript de 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);

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

De Crappy a Less Crappy

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

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

En el pseudocódigo anterior, almost-factorial tomas almost-factorial en la función f y el número x (el almost-factorial está en curry, por lo que se puede ver como tomar la función f y devolver una función de 1 aridad).

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

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

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

Si repetidamente pasamos la versión menos pesada de factorial a almost-factorial , eventualmente obtendremos nuestra función factorial deseada f . Donde pueda ser considerado como:

almost-factorial f = f

Punto fijo

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

Esta fue una manera realmente interesante de ver las relaciones de las funciones anteriores y fue un momento aha para mí. (por favor lea la publicación de Mike en el punto de corrección si no lo ha hecho)

Tres funciones

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

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

  • Definimos los cálculos del núcleo 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)

Me saltearé la derivación de Y e iré 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 (s s)) λs.(f (s s))

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

Y f = λs.(f (s s)) λs.(f (s s)) => f (λs.(f (s s)) λs.(f (s s))) => 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))

ya que 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 termina cuando el más interno (fn fr 1) es el caso base y fn no usa fr en el cálculo.

Mirando a Y nuevo:

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

Asi que

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

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

  • fn y fr interdependen entre sí: fr ''envuelve'' fn adentro, cada vez que se usa fr para calcular x , ''genera'' (''¿levanta''?) un fn y delega el cálculo a ese 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 en que se usa fr para definir fn (cuando fn usa fr en sus operaciones), el fr real aún no está definido.
  • Es fn que define la lógica de negocio real. Basado en fn , Y crea fr (una función auxiliar en una forma específica) para facilitar el cálculo de fn de manera recursiva .

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

Por cierto, también encontré el libro Una Introducción a la Programación Funcional a través de Lambda Cálculo muy bueno, solo una parte de él y el hecho de que no pude entender a Y en el libro me llevó a esta publicación.

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

Ahora, vuelva a escribirlo para que no use el nombre de la función dentro de la función, pero aún así lo llame recursivamente.

El único lugar donde se factorialdebe ver el nombre de la función es en el sitio de la llamada.

Sugerencia: no puede usar nombres de funciones, pero puede usar nombres de parámetros.

Trabaja el problema. No lo busques. Una vez que lo resuelvas, entenderás qué problema resuelve el combinador y.

El combinador y implementa la recursión anónima. Así que 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 y solo funciona en los idiomas de llamada por nombre. Si desea usar esto en cualquier lenguaje normal de llamada por valor, entonces necesitará el combinador z relacionado (el combinador y se desviará / bucle infinito).

El operador-este 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 extra:

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

Finalmente, llamas fac(5) .

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

En el esquema: https://gist.github.com/z5h/238891

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

Ambos tutoriales tienen códigos entremezclados con comentarios y se deben cortar y pegar en su editor favorito.

He sacado esto de http://www.mail-archive.com/[email protected]/msg02716.html que es una explicación que escribí hace varios años.

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

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

Bueno, el primer paso 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 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 engañar menos. Bueno, en primer lugar estamos usando la asignación, pero no necesitamos. Podemos 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 con el nombre de Haskell Curry tiene un buen truco. Si tienes buenas funciones de orden superior, solo necesitas funciones de 1 variable. La prueba es que puede obtener desde 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 ... sigue siendo exactamente el mismo. (Este truco se llama "curry" en honor a su inventor. El lenguaje Haskell también recibe su nombre de Haskell Curry. Archivo que en trivia inútil). 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éntete libre de probarlo. alerta () que regrese, atarlo a un botón, lo que sea. Ese código calcula factoriales, recursivamente, sin usar asignación, declaraciones o funciones de 2 variables. (Pero tratar de rastrear cómo funciona es probable que haga girar la cabeza. Y al entregarlo, sin la derivación, solo reformatearlo ligeramente resultará en 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.

La mayoría de las respuestas anteriores describen qué es el combinador en Y, pero no para qué sirve.

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

Estudiar combinadores de punto fijo también me ha ayudado a entender realmente la programación funcional. Sin embargo, nunca he encontrado ningún uso para ellos en la programación real.

Me pregunto si hay algún uso en 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); }

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

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

Eso es un poco raro, pero no hay nada de malo en ello. Solo estamos generando una nueva función factorial en cada paso.

La recursión en esta etapa es todavía bastante explícita. La función de fact necesita ser consciente de 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 todavía 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, creamos una función de envoltura que devuelve su resultado:

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

Ahora podemos deshacernos recurser nombre del recurser ; es solo un argumento de la función interna de Y, que se puede reemplazar con la función en sí:

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 todavía se hace referencia es un fact , pero ya debería estar claro 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); }; });

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

Si estás listo para una larga lectura, Mike Vanier tiene una gran explicación . En pocas palabras, le permite implementar la recursión en un lenguaje que no necesariamente lo admite de forma nativa.

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

Un Y-combinator es un "funcional" (una función que opera en otras funciones) que permite la recursión, cuando no puede referirse a la función desde dentro de sí misma. 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 compilación para la función recursiva es una especie de bonificación. =)

Esto es aplicable en lenguajes que soportan funciones lambda . La naturaleza basada en la expression de las lambdas generalmente significa que no pueden referirse a sí mismas por su nombre. Y resolver esto mediante la declaración de la variable, referirse a ella y asignarle la lambda para completar el bucle de auto-referencia es frágil. La variable lambda se puede copiar, y la variable original se puede reasignar, lo que rompe la auto-referencia.

Los combinadores en Y son complicados de implementar y, a menudo, de usar en lenguajes de static-typed (que suelen ser los lenguajes de procedimiento ), porque generalmente las restricciones de escritura requieren que se conozca el número de argumentos para que la función en cuestión se conozca en el momento de la compilación. Esto significa que se debe escribir un combinador de y para cada cuenta de argumento que uno necesita usar.

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

El uso de 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 conviertes 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 toma una función y realiza una operación con ella que resulta en 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<Double, Double>, Func<Double, Double>> 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 parece 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? Pasar la función interna a sí mismo. El Y-Combinator hace eso, al ser una función con un nombre permanente, que puede introducir la recursión.

// 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. }

En lugar de la llamada factorial en sí misma, lo que sucede es que la llamada factorial es el 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á al generador nuevamente, 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 para 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 , que se llamará en la siguiente iteración, solo si es necesario .

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 programación porque permite la implementación de recursión en forma de una regla de reescritura, sin el apoyo explícito del motor de tiempo de ejecución del lenguaje. (src Wikipedia)

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

Edit : Aprendo mucho mirando el código, pero este es un poco difícil de tragar sin un poco de historia, 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 Y se utiliza. 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 La función pasó a Y.

Para una explicación completa de cómo Y hace la magia, revise el JavaScript (no por mí por cierto).

Para los programadores que no han encontrado la programación funcional en profundidad, y no les importa comenzar ahora, pero son algo curiosos:

El combinador de 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, se pueden usar como valores de retorno y se pueden definir dentro de otras funciones.

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

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

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

En caso de que necesite identificarlo en una alineación de la policía, se ve así:

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

Por lo general, se puede detectar debido a la repetición (λx.f (xx)) .

Los símbolos λ son la letra griega lambda, que 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.