Combinador de punto fijo

Función de orden superior Y para la cual Y f = f (Y f)

En lógica combinatoria para informática , un combinador de punto fijo (o combinador de punto fijo ), ^{[1] : p.26} es una función de orden superior (es decir, una función que toma una función como argumento ) que devuelve un punto fijo (un valor que se asigna a sí mismo) de su función argumento, si existe.

Formalmente, si es un combinador de punto fijo y la función tiene uno o más puntos fijos, entonces es uno de estos puntos fijos, es decir ${\displaystyle {\textrm {fix}}}$ ${\displaystyle f}$ ${\displaystyle {\textrm {fix}}\ f}$

${\displaystyle f\ ({\textrm {fix}}\ f)={\textrm {fix}}\ f\ .}$

Los combinadores de punto fijo se pueden definir en el cálculo lambda y en lenguajes de programación funcional y proporcionan un medio para permitir definiciones recursivas .

Combinador Y en el cálculo lambda

En el cálculo lambda clásico sin tipo , cada función tiene un punto fijo. Una implementación particular de es el combinador paradójico Y de Haskell Curry , dado por ^{[2] : 131  [nota 1]} ${\displaystyle {\textrm {fix}}}$

${\displaystyle Y=\lambda f.\ (\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))}$

(Aquí utilizamos las notaciones y convenciones estándar del cálculo lambda: Y es una función que toma un argumento f y devuelve la expresión completa después del primer punto; la expresión denota una función que toma un argumento x , considerado como una función, y devuelve la expresión , donde denota x aplicado a sí mismo. La yuxtaposición de expresiones denota la aplicación de la función, es asociativa por la izquierda y tiene mayor precedencia que el punto). ${\displaystyle \lambda x.f\ (x\ x)}$ ${\displaystyle f\ (x\ x)}$ ${\displaystyle (x\ x)}$

Verificación

El siguiente cálculo verifica que efectivamente es un punto fijo de la función : ${\displaystyle Yg}$ ${\displaystyle g}$

En general, el término lambda no puede β-reducirse al término . Sin embargo, ambos términos β-reducen al mismo término, como se muestra. ${\displaystyle g\ (Y\ g)}$ ${\displaystyle Y\ g}$

Usos

Aplicado a una función con una variable, el combinador Y normalmente no termina. Se obtienen resultados más interesantes al aplicar el combinador Y a funciones de dos o más variables. Las variables adicionales se pueden utilizar como un contador o un índice. La función resultante se comporta como un bucle while o for en un lenguaje imperativo.

Utilizado de esta manera, el combinador Y implementa una recursión simple . El cálculo lambda no permite que una función aparezca como término en su propia definición como es posible en muchos lenguajes de programación, pero una función puede pasarse como argumento a una función de orden superior que la aplica de manera recursiva.

El combinador Y también se puede utilizar para implementar la paradoja de Curry . El núcleo de la paradoja de Curry es que el cálculo lambda sin tipo no es sólido como sistema deductivo, y el combinador Y lo demuestra al permitir que una expresión anónima represente cero, o incluso muchos valores. Esto es inconsistente en la lógica matemática.

Ejemplos de implementación

A continuación se presenta un ejemplo de implementación del combinador Y en dos lenguajes.

# Combinador Y en PythonY  =  lambda  f :  ( lambda  x :  f ( x ( x )))( lambda  x :  f ( x ( x )))Y ( Y )

// Combinador Y en C++, usando 14 extensiones de C++int principal () {   auto Y = []( auto f ) {      auto f1 = [ f ]( auto x ) -> decltype ( f ) {        devuelve f ( x ( x ));  }; devolver f1 ( f1 );  }; Y ( Y );}

Tenga en cuenta que ambos programas, aunque formalmente son correctos, son inútiles en la práctica; ambos se repiten indefinidamente hasta que terminan por desbordamiento de pila . En términos más generales, como Python y C++ utilizan evaluación estricta , el combinador Y es generalmente inútil en esos lenguajes; consulte a continuación el combinador Z, que se puede utilizar en lenguajes de programación estrictos .

Combinador de punto fijo

El combinador Y es una implementación de un combinador de punto fijo en el cálculo lambda. Los combinadores de punto fijo también se pueden definir fácilmente en otros lenguajes funcionales e imperativos. La implementación en el cálculo lambda es más difícil debido a las limitaciones del cálculo lambda. El combinador de punto fijo se puede utilizar en varias áreas diferentes:

• Matemáticas generales
• Cálculo lambda sin tipo
• Cálculo lambda tipificado
• Programación funcional
• Programación imperativa

Los combinadores de punto fijo se pueden aplicar a una variedad de funciones diferentes, pero normalmente no terminarán a menos que haya un parámetro adicional. Cuando la función que se va a fijar hace referencia a su parámetro, se invoca otra llamada a la función, por lo que el cálculo nunca comienza. En cambio, se utiliza el parámetro adicional para activar el inicio del cálculo.

El tipo del punto fijo es el tipo de retorno de la función que se está fijando. Puede ser un valor real, una función o cualquier otro tipo.

En el cálculo lambda sin tipo, la función a la que se aplicará el combinador de punto fijo se puede expresar mediante una codificación, como la codificación Church . En este caso, los términos lambda particulares (que definen funciones) se consideran valores. Al "ejecutar" (reducir beta) el combinador de punto fijo en la codificación, se obtiene un término lambda para el resultado que luego se puede interpretar como un valor de punto fijo.

Alternativamente, una función puede considerarse como un término lambda definido puramente en el cálculo lambda.

Estos diferentes enfoques afectan la forma en que un matemático y un programador pueden considerar un combinador de punto fijo. Un matemático puede ver el combinador Y aplicado a una función como una expresión que satisface la ecuación de punto fijo y, por lo tanto, una solución.

Por el contrario, una persona que solo quiera aplicar un combinador de punto fijo a alguna tarea de programación general puede verlo solo como un medio para implementar la recursión.

Valores y dominios

Muchas funciones no tienen puntos fijos, por ejemplo , con . Al utilizar la codificación Church , los números naturales se pueden representar en el cálculo lambda, y esta función f se puede definir en el cálculo lambda. Sin embargo, su dominio ahora contendrá todas las expresiones lambda, no solo aquellas que representan números naturales. El combinador Y, aplicado a f , producirá un punto fijo para f , pero este punto fijo no representará un número natural. Si se intenta calcular Y f en un lenguaje de programación real, se producirá un bucle infinito. ${\displaystyle f:\mathbb {N} \to \mathbb {N} }$ ${\displaystyle f(n)=n+1}$

Función versus implementación

El combinador de punto fijo puede definirse en matemáticas y luego implementarse en otros lenguajes. Las matemáticas generales definen una función en función de sus propiedades extensionales . ^[3] Es decir, dos funciones son iguales si realizan la misma función. El cálculo lambda y los lenguajes de programación consideran la identidad de funciones como una propiedad intensional . La identidad de una función se basa en su implementación.

Una función (o término) de cálculo lambda es una implementación de una función matemática. En el cálculo lambda hay varios combinadores (implementaciones) que satisfacen la definición matemática de un combinador de punto fijo.

Definición del término "combinador"

La lógica combinatoria es una teoría de funciones de orden superior . Un combinador es una expresión lambda cerrada , lo que significa que no tiene variables libres . Los combinadores pueden combinarse para dirigir los valores a sus lugares correctos en la expresión sin necesidad de nombrarlos como variables.

Definiciones recursivas y combinadores de punto fijo

Los combinadores de punto fijo se pueden utilizar para implementar la definición recursiva de funciones. Sin embargo, rara vez se utilizan en la programación práctica. ^[4] Los sistemas de tipos fuertemente normalizadores , como el cálculo lambda de tipos simples, no permiten la no terminación y, por lo tanto, a los combinadores de punto fijo a menudo no se les puede asignar un tipo o requieren características complejas del sistema de tipos. Además, los combinadores de punto fijo a menudo son ineficientes en comparación con otras estrategias para implementar la recursión, ya que requieren más reducciones de funciones y construyen y descomponen una tupla para cada grupo de definiciones mutuamente recursivas. ^{[1] : página 232}

La función factorial

La función factorial proporciona un buen ejemplo de cómo se puede utilizar un combinador de punto fijo para definir funciones recursivas. La definición recursiva estándar de la función factorial en matemáticas se puede escribir como

${\displaystyle \operatorname {fact} \ n={\begin{cases}1&{\text{if}}~n=0\\n\times \operatorname {fact} (n-1)&{\text{otherwise.}}\end{cases}}}$

donde n es un entero no negativo. Si queremos implementar esto en el cálculo lambda, donde los enteros se representan mediante la codificación Church , nos encontramos con el problema de que el cálculo lambda no permite que se use el nombre de una función ('fact') en la definición de la función. Esto se puede evitar utilizando un combinador de punto fijo como se indica a continuación. ${\displaystyle {\textsf {fix}}}$

Definir una función F de dos argumentos f y n :

${\displaystyle F\ f\ n=(\operatorname {IsZero} \ n)\ 1\ (\operatorname {multiply} \ n\ (f\ (\operatorname {pred} \ n)))}$

(Aquí hay una función que toma dos argumentos y devuelve su primer argumento si n = 0, y su segundo argumento en caso contrario; evalúa n -1). ${\displaystyle (\operatorname {IsZero} \ n)}$ ${\displaystyle \operatorname {pred} \ n}$

Ahora definamos . Entonces es un punto fijo de F , lo que da ${\displaystyle \operatorname {fact} ={\textsf {fix}}\ F}$ ${\displaystyle \operatorname {fact} }$

${\displaystyle {\begin{aligned}\operatorname {fact} n&=F\ \operatorname {fact} \ n\\&=(\operatorname {IsZero} \ n)\ 1\ (\operatorname {multiply} \ n\ (\operatorname {fact} \ (\operatorname {pred} \ n)))\ \end{aligned}}}$

como desees.

Combinadores de punto fijo en el cálculo lambda

El combinador Y, descubierto por Haskell B. Curry , se define como

${\displaystyle Y=\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))}$

Otros combinadores de punto fijo

En el cálculo lambda no tipificado, los combinadores de punto fijo no son especialmente raros. De hecho, hay un número infinito de ellos. ^[5] En 2005, Mayer Goldberg demostró que el conjunto de combinadores de punto fijo del cálculo lambda no tipificado es recursivamente enumerable . ^[6]

El combinador Y se puede expresar en el cálculo SKI como

${\displaystyle Y=S(K(SII))(S(S(KS)K)(K(SII)))}$

Los combinadores adicionales ( sistema B, C, K, W ) permiten una definición mucho más corta. Con el combinador de autoaplicación, dado que y , lo anterior se convierte en ${\displaystyle U=SII}$ ${\displaystyle S(Kx)yz=x(yz)=Bxyz}$ ${\displaystyle Sx(Ky)z=xzy=Cxyz}$

${\displaystyle Y=S(KU)(SB(KU))=BU(CBU)}$

El combinador de punto fijo más simple en el cálculo SK, descubierto por John Tromp , es

${\displaystyle Y'=SSK(S(K(SS(S(SSK))))K)}$

Aunque tenga en cuenta que no está en forma normal, que es más larga. Este combinador corresponde a la expresión lambda

${\displaystyle Y'=(\lambda xy.xyx)(\lambda yx.y(xyx))}$

El siguiente combinador de punto fijo es más simple que el combinador Y, y se reduce β al combinador Y; a veces se lo cita como el propio combinador Y:

${\displaystyle X=\lambda f.(\lambda x.xx)(\lambda x.f(xx))}$

Otro combinador de punto fijo común es el combinador de punto fijo de Turing (llamado así por su descubridor, Alan Turing ): ^{[7] [2] : 132}

${\displaystyle \Theta =(\lambda xy.y(xxy))\ (\lambda xy.y(xxy))}$

Su ventaja sobre es que beta-reduce a , ^{[nota 2]} mientras que y solo beta-reduce a un término común. ${\displaystyle Y}$ ${\displaystyle \Theta \ f}$ ${\displaystyle f\ (\Theta f)}$ ${\displaystyle Y\ f}$ ${\displaystyle f\ (Yf)}$

${\displaystyle \Theta }$También tiene una forma sencilla de llamada por valor:

${\displaystyle \Theta _{v}=(\lambda xy.y(\lambda z.xxyz))\ (\lambda xy.y(\lambda z.xxyz))}$

El análogo de la recursión mutua es un combinador de punto fijo polivariádico , ^{[8] [9] [10]} que puede denotarse Y*.

Combinador estricto de punto fijo

En un lenguaje de programación estricto, el combinador Y se expandirá hasta el desbordamiento de pila , o nunca se detendrá en caso de optimización de llamada de cola . ^[11] El combinador Z funcionará en lenguajes estrictos (también llamados lenguajes ansiosos, donde se aplica el orden de evaluación aplicativa). El combinador Z tiene el siguiente argumento definido explícitamente, lo que evita la expansión de en el lado derecho de la definición: ^[12] ${\displaystyle Zg}$

${\displaystyle Zgv=g(Zg)v\ .}$

y en cálculo lambda es una expansión eta del combinador Y :

${\displaystyle Z=\lambda f.(\lambda x.f(\lambda v.xxv))\ (\lambda x.f(\lambda v.xxv))\ .}$

Combinadores de punto fijo no estándar

Si F es un combinador de punto fijo en el cálculo lambda no tipado, entonces tenemos

${\displaystyle F=\lambda x.Fx=\lambda x.x(Fx)=\lambda x.x(x(Fx))=\cdots }$

Los términos que tienen el mismo árbol de Böhm que un combinador de punto fijo, es decir, tienen la misma extensión infinita , se denominan combinadores de punto fijo no estándar . Cualquier combinador de punto fijo también es no estándar, pero no todos los combinadores de punto fijo no estándar son combinadores de punto fijo porque algunos de ellos no satisfacen la ecuación de punto fijo que define a los "estándar". Estos combinadores se denominan combinadores de punto fijo estrictamente no estándar ; un ejemplo es el siguiente combinador: ${\displaystyle \lambda x.x(x(x\cdots ))}$

${\displaystyle N=BM(B(BM)B)}$

dónde

${\displaystyle B=\lambda xyz.x(yz)}$

${\displaystyle M=\lambda x.xx\ .}$

El conjunto de combinadores de punto fijo no estándar no es enumerable recursivamente . ^[6]

Implementación en otros idiomas

El combinador Y es una implementación particular de un combinador de punto fijo en el cálculo lambda. Su estructura está determinada por las limitaciones del cálculo lambda. No es necesario ni útil utilizar esta estructura para implementar el combinador de punto fijo en otros lenguajes.

A continuación se dan ejemplos simples de combinadores de punto fijo implementados en algunos paradigmas de programación .

Implementación funcional perezosa

En un lenguaje que admita la evaluación diferida , como Haskell , es posible definir un combinador de punto fijo utilizando la ecuación de definición del combinador de punto fijo, que se denomina convencionalmente fix. Dado que Haskell tiene tipos de datos diferidos, este combinador también se puede utilizar para definir puntos fijos de constructores de datos (y no solo para implementar funciones recursivas). La definición se proporciona aquí, seguida de algunos ejemplos de uso. En Hackage, el ejemplo original es: ^[13]

fix , fix' :: ( a -> a ) -> a fix f = let x = f x in x -- Lambda eliminada. Uso compartido. -- Definición original en Data.Function. -- alternativa: fix' f = f ( fix' f ) -- Lambda eliminada. No uso compartido.                        fix ( \ x -> 9 ) -- esto evalúa a 9    fix ( \ x -> 3 : x ) – evalúa a la lista infinita perezosa [3,3,3,...]    fact = fix fac -- evalúa a la función factorial donde fac f 0 = 1 fac f x = x * f ( x - 1 )                  hecho 5 -- se evalúa como 120  

Implementación funcional estricta

En un lenguaje funcional estricto, como se ilustra a continuación con OCaml , el argumento de f se expande de antemano, lo que produce una secuencia de llamadas infinita,

${\displaystyle f\ (f...(f\ ({\mathsf {fix}}\ f))...)\ x}$.

Esto se puede resolver definiendo fix con un parámetro adicional.

deje que  rec  fije  f  x  =  f  ( fije  f )  x  (* note la x adicional; aquí fije f = \x-> f (fije f) x *)deje que  factabs  fact  =  function  (* factabs tiene un nivel adicional de abstracción lambda *)  0  ->  1  |  x  ->  x  *  fact  ( x - 1 )sea  ​​_  =  ( corregir  factabs )  5  (*evalúa a "120" *)

En un lenguaje funcional multiparadigma (uno decorado con características imperativas), como Lisp , Peter Landin sugirió el uso de una asignación de variable para crear un combinador de punto fijo, ^[14] como en el siguiente ejemplo usando Scheme :

( define Y! ( lambda ( f ) (( lambda ( i ) ( set! i ( f ( lambda ( x ) ( i x )))) ;; (set! i expr) asigna a i el valor de expr i ) ;; reemplazándolo en el ámbito léxico actual #f )))                 

Utilizando un cálculo lambda con axiomas para declaraciones de asignación, se puede demostrar que Y!satisface la misma ley de punto fijo que el combinador Y de llamada por valor: ^{[15] [16]}

${\displaystyle (Y_{!}\ \lambda x.e)e'=(\lambda x.e)\ (Y_{!}\ \lambda x.e)e'}$

En un uso más idiomático y moderno de Lisp, esto normalmente se manejaría a través de una etiqueta con alcance léxico (una letexpresión), ya que el alcance léxico no se introdujo en Lisp hasta la década de 1970:

( define Y* ( lambda ( f ) (( lambda ( i ) ( sea (( i ( f ( lambda ( x ) ( i x ))))) ;; (sea ((i expr)) i) define localmente a i como expr i )) ;; no recursivamente: por lo tanto, i en expr no es expr #f )))                

O sin la etiqueta interna:

( define Y ( lambda ( f ) (( lambda ( i ) ( i i )) ( lambda ( i ) ( f ( lambda ( x ) ( aplica ( i i ) x ))))))))                

Implementación del lenguaje imperativo

Este ejemplo es una implementación ligeramente interpretativa de un combinador de punto fijo. Se utiliza una clase para contener la función fix , llamada fixer . La función que se va a corregir está contenida en una clase que hereda de fixer . La función fix accede a la función que se va a corregir como una función virtual. En cuanto a la definición funcional estricta, a fix se le asigna explícitamente un parámetro adicional x , lo que significa que no se necesita una evaluación diferida.

plantilla < typename R , typename D > clase fixer { público : R fix ( D x ) { devolver f ( x ); } privado : virtual R f ( D ) = 0 ; };                 hecho de clase : public fixer < long , long > { virtual long f ( long x ) { if ( x == 0 ) { return 1 ; } return x * fix ( x -1 ); } };                       resultado largo = hecho (). fix ( 5 );   

Mecanografía

En el Sistema F (cálculo lambda polimórfico) un combinador de punto fijo polimórfico tiene tipo ^[17]

∀a.(a → a) → a

donde a es una variable de tipo . Es decir, fix toma una función que asigna a → a y la utiliza para devolver un valor de tipo a.

En el cálculo lambda de tipos simples extendido con tipos de datos recursivos , se pueden escribir operadores de punto fijo, pero el tipo de un operador de punto fijo "útil" (uno cuya aplicación siempre retorna) puede estar restringido.

En el cálculo lambda de tipos simples , no se le puede asignar un tipo al combinador de punto fijo Y ^[18] porque en algún punto trataría con el subtérmino de autoaplicación mediante la regla de aplicación: ${\displaystyle x~x}$

${\displaystyle {\Gamma \vdash x\!:\!t_{1}\to t_{2}\quad \Gamma \vdash x\!:\!t_{1}} \over {\Gamma \vdash x~x\!:\!t_{2}}}$

donde tiene el tipo infinito . De hecho, no se puede tipificar ningún combinador de punto fijo; en esos sistemas, cualquier soporte para recursión debe agregarse explícitamente al lenguaje. ${\displaystyle x}$ ${\displaystyle t_{1}=t_{1}\to t_{2}}$

Tipo para el combinador Y

En los lenguajes de programación que admiten tipos de datos recursivos , es posible tipificar el combinador Y teniendo en cuenta adecuadamente la recursión a nivel de tipo. La necesidad de autoaplicar la variable x se puede gestionar utilizando un tipo ( Rec a), que se define de modo que sea isomorfo a ( Rec a -> a).

Por ejemplo, en el siguiente código Haskell, tenemos Iny outsiendo los nombres de las dos direcciones del isomorfismo, con tipos: ^{[19] [20]}

En :: ( Rec a -> a ) -> Rec a fuera :: Rec a -> ( Rec a -> a )                

lo que nos permite escribir:

nuevo tipo Rec a = In { out :: Rec a -> a }            y :: ( a -> a ) -> a y = \ f - > ( \ x -> f ( salida x x )) ( En ( \ x -> f ( salida x x )))                      

O equivalentemente en OCaml:

tipo  ' a  recc  =  In  de  ( ' a  recc  ->  ' a ) dejar  salir  ( In  x )  =  xsea  ​​y  f  =  ( fun  x  a  ->  f  ( out  x  x )  a )  ( In  ( fun  x  a  ->  f  ( out  x  x )  a ))

Alternativamente:

sea  ​​y  f  =  ( fun  x  ->  f  ( fun  z  ->  out  x  x  z ))  ( En  ( fun  x  ->  f  ( fun  z  ->  out  x  x  z )))

información general

Debido a que los combinadores de punto fijo se pueden utilizar para implementar la recursión, es posible utilizarlos para describir tipos específicos de cálculos recursivos, como aquellos en iteración de punto fijo , métodos iterativos , unión recursiva en bases de datos relacionales , análisis de flujo de datos , conjuntos FIRST y FOLLOW de no terminales en una gramática libre de contexto , cierre transitivo y otros tipos de operaciones de cierre .

Una función para la cual cada entrada es un punto fijo se denomina función identidad . Formalmente:

${\displaystyle \forall x(f\ x=x)}$

A diferencia de la cuantificación universal sobre todo , un combinador de punto fijo construye un valor que es un punto fijo de . La propiedad notable de un combinador de punto fijo es que construye un punto fijo para una función dada arbitraria . ${\displaystyle x}$ ${\displaystyle f}$ ${\displaystyle f}$

Otras funciones tienen la propiedad especial de que, después de ser aplicadas una vez, las aplicaciones posteriores no tienen ningún efecto. Más formalmente:

${\displaystyle \forall x(f\ (f\ x)=f\ x)}$

Estas funciones se denominan idempotentes (véase también Proyección (matemáticas) ). Un ejemplo de este tipo de función es la función que devuelve 0 para todos los números enteros pares y 1 para todos los números enteros impares.

En el cálculo lambda , desde un punto de vista computacional, la aplicación de un combinador de punto fijo a una función identidad o una función idempotente generalmente da como resultado un cálculo no terminal. Por ejemplo, obtenemos

${\displaystyle (Y\ \lambda x.x)=(\lambda x.(xx)\ \lambda x.(xx))}$

donde el término resultante sólo puede reducirse a sí mismo y representa un bucle infinito.

Los combinadores de punto fijo no necesariamente existen en modelos de computación más restrictivos. Por ejemplo, no existen en el cálculo lambda de tipos simples .

El combinador Y permite definir la recursión como un conjunto de reglas de reescritura , ^[21] sin requerir soporte de recursión nativo en el lenguaje. ^[22]

En los lenguajes de programación que admiten funciones anónimas , los combinadores de punto fijo permiten la definición y el uso de funciones recursivas anónimas , es decir, sin tener que vincular dichas funciones a identificadores . En este contexto, el uso de combinadores de punto fijo a veces se denomina recursión anónima . ^{[nota 3] [23]}

Véase también

• Función anónima
• Iteración de punto fijo
• Cálculo lambda#Recursión y puntos fijos
• Elevación de lambda
• Sea expresión

Notas

1. A lo largo de este artículo, se utilizan las reglas de sintaxis dadas en el cálculo Lambda#Notación para guardar paréntesis.
2. ${\displaystyle \Theta \ f}$ ${\displaystyle \equiv }$ ${\displaystyle (\lambda xy.y(xxy))\ (\lambda xy.y(xxy))\ f}$ ${\displaystyle \to }$ ${\displaystyle (\lambda y.y\ ((\lambda xy.y(xxy))\ (\lambda xy.y(xxy))\ y))\ f}$ ${\displaystyle \to }$ ${\displaystyle f\ ((\lambda xy.y(xxy))\ (\lambda xy.y(xxy))\ f)}$ ${\displaystyle \equiv }$ ${\displaystyle f\ (\Theta \ f)}$
3. Esta terminología parece ser en gran parte folclore , pero aparece en lo siguiente:
   • Trey Nash, Accelerated C# 2008 , Apress, 2007, ISBN  1-59059-873-3 , pág. 462—463. Basado en gran medida en el blog de Wes Dyer (véase el siguiente artículo).
   • Wes Dyer Anonymous Recursion in C#, 2 de febrero de 2007, contiene un ejemplo sustancialmente similar al que se encuentra en el libro mencionado anteriormente, pero acompañado de más discusión.

Referencias

1. Peyton Jones, Simon L. (1987). La implementación de la programación funcional (PDF) . Prentice Hall International.
2. Henk Barendregt (1985). El cálculo lambda: su sintaxis y semántica . Estudios de lógica y fundamentos de las matemáticas. Vol. 103. Ámsterdam: Holanda Septentrional. ISBN 0444867481.
3. Selinger, Peter. "Apuntes sobre cálculo lambda (PDF)". pág. 6.
4. "Para aquellos de nosotros que no sabemos qué es un Y-Combinator o por qué es útil, ..." Hacker News . Consultado el 2 de agosto de 2020 .
5. Bimbó, Katalin (27 de julio de 2011). Lógica combinatoria: pura, aplicada y tipificada. CRC Press. p. 48. ISBN 9781439800010.
6. Goldberg, 2005
7. Alan Mathison Turing (diciembre de 1937). "La función -en la - -conversión". Journal of Symbolic Logic . 2 (4): 164. JSTOR  2268281. ${\displaystyle p}$ ${\displaystyle \lambda }$ ${\displaystyle K}$
8. "Muchas caras del combinador de punto fijo". okmij.org .
9. Y polivariádica en Haskell98 puro Archivado el 4 de marzo de 2016 en Wayback Machine , lang.haskell.cafe, 28 de octubre de 2003
10. "recursión - ¿Combinador de punto fijo para funciones recursivas mutuas?". Desbordamiento de pila .
11. Bene, Adam (17 de agosto de 2017). "Combinadores de punto fijo en JavaScript". Bene Studio . Medium . Consultado el 2 de agosto de 2020 .
12. "CS 6110 S17 Clase 5. Recursión y combinadores de punto fijo" (PDF) . Universidad de Cornell . 4.1 Un combinador de punto fijo CBV.
13. La definición original en Data.Function.
14. Landin, PJ (enero de 1964). "La evaluación mecánica de expresiones". The Computer Journal . 6 (4): 308–320. doi :10.1093/comjnl/6.4.308.
15. Felleisen, Matías (1987). El cálculo Lambda-v-CS. Universidad de Indiana.
16. Talcott, Carolyn (1985). La esencia del ron: una teoría de los aspectos intensionales y extensionales de la computación de tipo Lisp (tesis doctoral). Universidad de Stanford.
17. Girard, Jean-Yves (1986). "El sistema F de tipos de variables, quince años después". Theoretical Computer Science . 45 (2): 159–192. doi :10.1016/0304-3975(86)90044-7. MR  0867281.Véase en particular la página 180.
18. Introducción al cálculo lambda Archivado el 8 de abril de 2014 en Wayback Machine.
19. Hilo de la lista de correo de Haskell sobre Cómo definir el combinador Y en Haskell, 15 de septiembre de 2006
20. Geuvers, Herman; Verkoelen, Joep. Sobre combinadores de punto fijo y bucles en teoría de tipos . CiteSeerX 10.1.1.158.1478 . 
21. Daniel P. Friedman , Matthias Felleisen (1986). "Capítulo 9 - Lambda The Ultimate". The Little Lisper . Science Research Associates . pág. 179."En el capítulo hemos derivado un combinador Y que nos permite escribir funciones recursivas de un argumento sin utilizar define".
22. Mike Vanier. "El Combinador Y (ligero retorno) o cómo tener éxito en la recursión sin recurrir realmente". Archivado desde el original el 22 de agosto de 2011."De manera más general, Y nos brinda una forma de obtener recursión en un lenguaje de programación que admite funciones de primera clase pero que no tiene recursión incorporada".
23. El método If Works: derivación del combinador Y, 10 de enero de 2008

• Werner Kluge, Máquinas de computación abstractas: una perspectiva de cálculo lambda , Springer, 2005, ISBN 3-540-21146-2 , pp. 73–77 
• Mayer Goldberg, (2005) Sobre la enumerabilidad recursiva de combinadores de punto fijo , Informe BRICS RS-05-1, Universidad de Aarhus
• Matthias Felleisen , Una conferencia sobre el por qué de Y.

Enlaces externos

• Teoría de la recursión y la alegría, Manfred von Thun, (2002 o anterior)
• El cálculo lambda: notas de Don Blaheta, 12 de octubre de 2000
• Y Combinator Archivado el 23 de marzo de 2009 en Wayback Machine.
• "Un uso del Combinador Y en Ruby"
• "Programación funcional en Ada"
• Código Rosetta - Combinador Y