¿Qué es un combinador en Y?[cerrado]

https://stackoverflow.com/questions/93526

01-07-2019
|

Pregunta

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 sobre combinadores, si es que 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?

Solución

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

Otros consejos

Un combinador Y es un "funcional" (una función que opera sobre otras funciones) que permite la recursividad, cuando no se puede hacer referencia a la función desde dentro de sí misma.En la teoría de la informática, generaliza la recursividad, abstrayendo su implementación y separándola así 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 ventaja.=)

Esto es aplicable en idiomas que soportan funciones lambda.El expresiónLa naturaleza basada en lambdas generalmente significa que no pueden referirse a sí mismas por su nombre.Y solucionar esto declarando la variable, haciendo referencia a ella y luego asignándole la lambda, para completar el ciclo de autorreferencia, es frágil.La variable lambda se puede copiar y reasignar la variable original, lo que rompe la autorreferencia.

Los combinadores en Y son complicados de implementar y, a menudo, de usar, en de tipo estático idiomas (que lenguajes procesales a menudo lo son), porque normalmente las restricciones de escritura requieren que se conozca el número de argumentos de la función en cuestión en el momento de la compilación.Esto significa que se debe escribir un combinador y para cualquier recuento de argumentos que sea necesario utilizar.

A continuación se muestra un ejemplo de cómo se usa y funciona un Y-Combinator en C#.

El uso de un combinador en Y implica una forma "inusual" de construir una función recursiva.Primero debes escribir tu función como un fragmento de código que llame a una función preexistente, en lugar de llamarla a sí misma:

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

Luego lo conviertes en una función que toma una función para llamar y devuelve una función que lo hace.Esto se llama funcional porque toma una función y realiza una operación con ella 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<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 se hace que esto sea el factorial?Pase 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 recursividad.

// 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 que el factorial se llame a sí mismo, 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á al generador nuevamente, con t - 1, o simplemente devolverá 1, terminando la recursividad.

Es complicado y críptico, pero todo se desmorona en tiempo de ejecución, y la clave para su funcionamiento es la "ejecución diferida" y la división de la recursividad para abarcar dos funciones.La F interior es pasado como argumento, que se llamará en la próxima iteración, solo si es necesario.

He levantado esto 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 lenguajes también funcionarán.

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

Bueno, el paso 1 es decir que podríamos hacer esto fácilmente si hacíamos 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 menos trampas.Bueno, en primer lugar, estamos usando la tarea, pero no necesitamos hacerlo.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 utilizando funciones de 2 variables para obtener una función de 1 variable.¿Podemos arreglar eso?Bueno, un tipo inteligente con el nombre de Haskell Curry tiene un buen truco, si tiene buenas funciones de orden superior, solo necesita funciones de 1 variable.La prueba es que puede obtener de las 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);

dónde ...sigue siendo exactamente el mismo.(Este truco se llama "currying" después de su inventor.El idioma Haskell también lleva el nombre de Haskell Curry.Archifique eso en trivia inútil.) Ahora solo aplique esta transformación en todas partes y obtenemos 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
);

No dudes en probarlo.alert() ese retorno, átelo a un botón, lo que sea.Ese código calcula los 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 entregarlo, sin la derivación, solo un ligeramente reformateado 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 tiene alguna utilidad intentar construir esto desde cero.Vamos a ver.Aquí hay una función factorial recursiva básica:

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

Refactoricemos y creemos una nueva función llamada fact que devuelve una función de cálculo factorial anónima 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();

Es un poco raro, pero no tiene nada de malo.Simplemente estamos generando una nueva función factorial en cada paso.

La recursividad en esta etapa sigue siendo bastante explícita.El fact La función debe ser consciente de su propio nombre.Parametricemos 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 recurser Todavía necesita saber su propio nombre.Parametricémoslo también:

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

var factorial = recurser(recurser);

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

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

var factorial = Y();

Ahora podemos deshacernos del recurser nombre en conjunto;es solo un argumento para la función interna de Y, que puede reemplazarse con 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 todavía se hace referencia es fact, pero ya debería quedar claro que eso 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 lo que el combinador Y es pero no lo que es para.

Combinadores de punto fijo se utilizan para demostrar que cálculo lambda es completo.Este es un resultado muy importante en la teoría de la computación y proporciona una base teórica para programación funcional.

Estudiar combinadores de punto fijo también me ha ayudado a comprender realmente la programación funcional.Sin embargo, nunca les encontré ningún uso en la programación real.

combinador y 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 aceptar sin algunos antecedentes; lo siento.Con algunos conocimientos generales presentados por otras respuestas, puede comenzar a analizar lo que está sucediendo.

La función Y es el "combinador y".Ahora eche un vistazo a var factorial línea donde se utiliza 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 de la función pasada a Y.

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

Para programadores que no han experimentado la programación funcional en profundidad y no les interesa comenzar ahora, pero tienen un poco de curiosidad:

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

Funciona pasándose la función a sí mismo como argumento, para que pueda llamarse a sí mismo.

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

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

En caso de que necesites identificarlo en una rueda de policía, se ve así:

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

Generalmente puedes detectarlo debido a las repetidas (λx.f (x x)).

El λ Los símbolos son la letra griega lambda, que da nombre al cálculo lambda, y hay muchos (λx.t) términos de estilo 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 complicada y hacerlo no tiene ningún propósito práctico (excepto "mira, sé qué es el combinador Y").Es un concepto teórico importante, pero de poco valor práctico.

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

Un combinador en Y es otro nombre para un condensador de flujo.

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

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

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

Ambos tutoriales contienen código intercalado con comentarios y deben cortarse y pegarse en su editor favorito.

recursividad anónima

Un combinador de punto fijo es una función de orden superior fix 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 se puede demostrar mediante

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

Usando fix, se pueden derivar pruebas constructivas arbitrarias sobre funciones generales/μ-recursivas 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 reescribe

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

cálculo lambda

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

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

dónde v abarca variables, junto con la beta y reducción de eta normas

(λ 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 el cuerpo de abstracción (“función”) B por la expresión (“argumento”) E.La reducción de eta elimina la abstracción redundante.A veces se omite en el formalismo.Un irreducible expresión, a la que no se aplica ninguna regla de reducción, está en normal o forma canónica.

λ x y. E

es una abreviatura de

λ x. λ y. E

(abstracción multiaridad),

E F G

es una abreviatura de

(E F) G

(aplicación asociatividad de izquierda),

λ x. x

λ y. y

son equivalente alfa.

La abstracción y la aplicación son los dos únicos “lenguaje primitivo” del cálculo lambda, pero permiten codificación de datos y operaciones arbitrariamente complejas.

Los números de Church son una codificación de los números naturales similar a los naturales axiomáticos de 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
    . . .

Una prueba formal de que

1 + 2  =  3

usando la regla de reescritura de la 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, combinadores son abstracciones que no contienen variables libres.Más simplemente: I, el combinador de identidad

λ x. x

isomorfa a la función identidad

id x = x

Estos combinadores son los operadores primitivos de cálculos 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 es fuertemente normalizante;No todas las expresiones reducibles, "redexes", convergen a su forma normal bajo reducción beta.Un ejemplo sencillo es la aplicación divergente del omega. ω 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”). Orden aplicativo normaliza los argumentos antes de la sustitución, orden normal no es.Las dos estrategias son análogas a la evaluación entusiasta, p.C, y evaluación diferida, p.Haskel.

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

diverge bajo una 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))
. . .
=  _|_

desde en estricto semántica

forall f.  f _|_  =  _|_

pero converge bajo reducción beta perezosa 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 de la Y combinador de punto fijo

λ 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 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 sin tipo de Churchian, se ha demostrado que existe una infinidad recursivamente enumerable de combinadores de punto fijo además 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 convierte al cálculo lambda no extendido y sin tipo en un sistema de reescritura completo de Turing.

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 hasta el infinito 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])

David Turner: Tesis de Church y programación funcional
Iglesia de Alonso: Un problema irresoluble de la teoría de números elemental
cálculo lambda
Teorema de Church-Rosser

El combinador y implementa la recursividad 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 sólo funciona en idiomas de llamada por nombre.Si desea utilizar esto en cualquier lenguaje normal de llamada por valor, necesitará el combinador z relacionado (el combinador y divergirá/bucle infinito).

Como novato en combinadores, encontré El artículo de Mike Vanier. (gracias Nicholas Mancuso) por ser de gran ayuda.Me gustaría escribir un resumen, además de documentar lo que he entendido, si pudiera ser de ayuda para otros, estaría muy contento.

De De mierda a menos cutre

Usando factorial como ejemplo, usamos lo siguiente almost-factorial función para calcular el factorial de un 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 toma en función f y numero x (almost-factorial es curry, por lo que se puede considerar que actúa en función f y devolver una función de 1 aridad).

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

Puede verse como almost-factorial toma en un de mierda versión de la función factorial (que solo puede calcular hasta el número x - 1) y devuelve un menos cutre versión de factorial (que calcula hasta el número x).Como en esta forma:

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

Si pasamos repetidamente el menos cutre versión de factorial para 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 medio 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 de ajá para mí.(lea la publicación de Mike sobre el punto de reparación si aún no lo ha hecho)

Tres funciones

Para generalizar, tenemos un no recursivo función fn (como nuestro casi factorial), tenemos su punto fijo función fr (como nuestra f), entonces ¿qué? Y lo que hace es cuando das Y fn, Y devuelve la función de punto fijo de fn.

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

Definimos el cálculos básicos como fn: def fn fr x = ...accumulate x with result from (fr (- x 1)), este es el casi útil función - aunque no podemos usar fn directamente en x, será útil muy pronto.Este no recursivo fn utiliza una función fr para calcular su resultado
fn fr = fr, fr es el punto fijo de fn, fr es el útil función, podemos usar fr en x para obtener nuestro resultado
Y fn = fr, Y devuelve el punto fijo de una función, Y se vuelve agrio casi útil función fn en útil fr

derivando `Y` (no incluido)

Me saltaré la derivación de Y y ve al entendimiento Y.La publicación de Mike Vainer tiene muchos detalles.

La forma de `Y`

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

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)

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

Por que `(Y f)` ¿trabajar?

Dependiendo de la firma de f, (Y f) puede ser una función de cualquier aridad, para simplificar, supongamos (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 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 de nuevo:

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

Entonces

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 interdependientes unos de otros: fr 'envolturas' fn dentro, cada vez fr se utiliza para calcular x, 'genera' (¿'levanta'?) una fn y delega el cálculo a ese fn (pasando en sí mismo fr y x);por otro lado, fn depende de fr y usos fr para calcular el resultado de un problema más pequeño x-1.
En el momento fr se utiliza para definir fn (cuando fn usos fr en sus operaciones), el verdadero fr aún no está definido.
Es fn que define la verdadera lógica empresarial.Residencia en fn, Y crea fr - una función auxiliar en una forma específica - para facilitar el cálculo de fn en un recursivo manera.

Me ayudó a entender Y De esta manera por el momento, espero que ayude.

Por cierto, también encontré el libro. Introducción a la programación funcional mediante cálculo Lambda muy bien, solo estoy a medio camino y el hecho de que no podía entenderlo Y en el libro me llevó a esta publicación.

Aquí hay respuestas a las preguntas originales, compilado de el artículo (que vale la pena leer TOTALMENTE) mencionado en el respuesta de Nicolás Mancuso, así como otras respuestas:

¿Qué es un combinador en Y?

Un combinador Y es una función "funcional" (o una función de orden superior, una función que opera sobre 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 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 vinculada: variable contenida dentro del cuerpo de una expresión lambda que tiene ese nombre de variable como uno de sus argumentos.

Otra forma de pensar en esto es que el combinador es una expresión lambda en la que puedes reemplazar el nombre de un combinador con su definición en todos los lugares donde se encuentra y hacer que todo siga funcionando (entrarás en un bucle infinito si el combinador no funciona). contiene referencia a sí mismo, dentro del cuerpo lambda).

El combinador Y es un combinador de punto fijo.

El punto fijo de una función es un elemento del dominio de la función que la función asigna a sí mismo.
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 siguientes suponen fuerte + dinámico mecanografía:

Combinador en Y perezoso (orden normal):
Esta definición se aplica a idiomas con perezoso (también:evaluació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(x x), y luego aplicar esta expresión lambda a sí mismo.

Combinador en Y estricto (orden aplicativo):
Esta definición se aplica a idiomas con estricto (también:impaciente, codicioso) evaluación: estrategia de evaluación en la que una expresión se evalúa tan pronto como se vincula 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 lo mismo que el perezoso por naturaleza, solo que tiene un extra. λ envoltorios para retrasar la evaluación del cuerpo de la lambda.he preguntado otra pregunta, algo relacionado con este tema.

¿Para qué son buenos?

~~Robado~~ tomado de respuesta de Chris Ammerman:Y-combinator generaliza la recursividad, abstrayendo su implementación y separándola así del trabajo real de la función en cuestión.

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

¿Son útiles en lenguajes procesales?

Como declarado por Mike Vanier: Es posible definir un combinador 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 obvia, porque el combinador Y en sí no tiene un tipo estático sencillo. .Eso está más allá del alcance de este artículo, por lo que no lo mencionaré más.

Y como mencionado por Chris Ammerman:la mayoría de los lenguajes procesales tienen escritura estática.

Así que responda a esta: en realidad no.

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 la recursividad en forma de regla de reescritura, sin el apoyo explícito del motor de ejecución del lenguaje.(fuente Wikipedia)

El operador this puede simplificarle la 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).

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 reescríbalo para que no use el nombre de la función dentro de la función, pero aún así la llame de forma recursiva.

El único lugar donde se encuentra el nombre de la función. factorial debe verse está en el lugar de la llamada.

Pista:No puedes usar nombres de funciones, pero puedes usar nombres de parámetros.

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

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow