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 algún punto fijo (un valor que está asignado a sí mismo) de su función de 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 funcionales y proporcionan un medio para permitir definiciones recursivas .

Combinador Y en 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 aplicada a sí misma. La yuxtaposición de expresiones denota aplicación de 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 β se 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 aplicando el combinador Y a funciones de dos o más variables. Las variables adicionales se pueden utilizar como contador o í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 recursividad simple . En el cálculo lambda no es posible referirse a la definición de una función dentro de su propio cuerpo por su nombre. Sin embargo, la recursividad se puede lograr obteniendo la misma función pasada como argumento y luego usando ese argumento para realizar la llamada recursiva, en lugar de usar el propio nombre de la función, como se hace en lenguajes que admiten la recursividad de forma nativa.

El combinador Y también se puede utilizar para implementar la paradoja de Curry . El corazón de la paradoja de Curry es que el cálculo lambda sin tipificar 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.

Implementaciones de ejemplo

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

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

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

Tenga en cuenta que ambos programas, aunque formalmente correctos, son inútiles en la práctica; Ambos se repiten indefinidamente hasta que terminan por desbordamiento de pila . De manera más general, como tanto Python como C++ usan una evaluación estricta , el combinador Y generalmente es 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 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 varios ámbitos diferentes:

• matemáticas generales
• Cálculo lambda sin tipo
• Cálculo lambda mecanografiado
• 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 a corregir hace referencia a su parámetro, se invoca otra llamada a la función, por lo que el cálculo nunca comienza. En cambio, el parámetro adicional se utiliza para activar el inicio del cálculo.

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

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

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

Estos diferentes enfoques afectan cómo 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 tanto, una solución.

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

Valores y dominios

Muchas funciones no tienen puntos fijos, por ejemplo con . Usando la codificación de 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 sólo 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 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 el mismo mapeo. El cálculo lambda y los lenguajes de programación consideran la identidad de la función 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 se pueden combinar para dirigir valores a sus lugares correctos en la expresión sin siquiera nombrarlos como variables.

Definiciones recursivas y combinadores de punto fijo

Los combinadores de punto fijo se pueden utilizar para implementar definiciones recursivas de funciones. Sin embargo, rara vez se utilizan en programación práctica. ^[4] Los sistemas de tipos fuertemente normalizados , como el cálculo lambda de tipo simple, 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 suelen ser ineficientes en comparación con otras estrategias para implementar la recursividad, ya que requieren más reducciones de funciones y construyen y desarman 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 número entero no negativo. Si queremos implementar esto en el cálculo lambda, donde los números enteros se representan usando la codificación Church , nos encontramos con el problema de que el cálculo lambda no permite que el nombre de una función ("hecho") se use en la definición de la función. Esto se puede evitar utilizando un combinador de punto fijo de la siguiente manera. ${\displaystyle {\textsf {fix}}}$

Defina 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; se evalúa como n -1.) ${\displaystyle (\operatorname {IsZero} \ n)}$ ${\displaystyle \operatorname {pred} \ n}$

Ahora define . 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 se desee.

Combinadores de punto fijo en 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 sin tipo, los combinadores de punto fijo no son especialmente raros. De hecho, hay infinitos de ellos. ^[5] En 2005, Mayer Goldberg demostró que el conjunto de combinadores de punto fijo del cálculo lambda sin tipo 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, desde 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, encontrado por John Tromp , es

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

aunque ojo que no está en su 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 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 es que beta se reduce a , ^{[nota 2]} mientras que y solo beta se 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 simple de llamada por valor:

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

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

Combinador estricto de punto fijo

En un lenguaje de programación estricto, el combinador Y se expandirá hasta que la pila se desborde , o nunca se detendrá en caso de optimización de la llamada final . ^[11] El combinador Z funcionará en lenguajes estrictos (también llamados lenguajes ansiosos, donde se aplica el orden de evaluación aplicativo). El combinador Z tiene el siguiente argumento definido explícitamente, evitando 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 eta-expansión 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 cálculo lambda sin tipo, 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 como combinador de punto fijo, es decir, que tienen la misma extensión infinita , se denominan combinadores de punto fijo no estándar . Cualquier combinador de punto fijo tampoco es 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 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 de forma recursiva . ^[6]

Implementación en otros idiomas

El combinador Y es una implementación particular de un combinador de punto fijo en 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 idiomas.

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

Implementación funcional perezosa

En un lenguaje que admite evaluación diferida , como Haskell , es posible definir un combinador de punto fijo utilizando la ecuación definitoria 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 sólo para implementar funciones recursivas). La definición se proporciona aquí, seguida de algunos ejemplos de uso. En Hackage, la muestra original es: ^[13]

arreglar , arreglar' :: ( a -> a ) -> a arreglar f = let x = f x in x - Lambda eliminado. Intercambio. -- Definición original en Data.Function. -- alternativa: fix' f = f ( fix' f ) -- Lambda levantada. No compartir.                        arreglar ( \ x -> 9 ) - esto se evalúa como 9    fix ( \ x -> 3 : x ) - evalúa la lista infinita diferida [3,3,3,...]    fact = fix fac - se evalúa como 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  corrija  f  x  =  f  ( fix  f )  x  (* tenga en cuenta la x adicional; aquí corrija f = \x-> f (fix f) x *)let  factabs  fact  =  function  (* factabs tiene un nivel extra de abstracción lambda *)  0  ->  1  |  x  ->  x  *  hecho  ( x - 1 )let  _  =  ( arreglar  factabs )  5  (* se evalúa como "120" *)

En un lenguaje funcional de múltiples paradigmas (uno decorado con características imperativas), como Lisp , Landin (1963) ^{[ cita completa necesaria ]} sugiere el uso de una asignación de variable para crear un combinador de punto fijo, como en el siguiente ejemplo usando Scheme :

( define Y! ( lambda ( f ) (( lambda ( i ) ( set! i ( f ( lambda ( x ) ( i x )))) ;; (set! i expr) asigna i el valor de expr i ) ; ; reemplazándolo en el alcance léxico presente #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: ^{[14] [15]}

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

En el uso más idiomático de Lisp moderno, esto normalmente se manejaría a través de una etiqueta de 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 ) ( let (( i ( f ( lambda ( x ) ( i x ))))) ;; (let ((i expr)) i) define localmente i como expr i )) ;; no recursivamente: por lo tanto i en expr no es expr #f )))                

O sin la etiqueta interna:

( definir Y ( lambda ( f ) (( lambda ( i ) ( i i )) ( lambda ( i ) ( f ( lambda ( x ) ( aplicar ( 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 de reparación , llamada fixer . La función a arreglar está contenida en una clase que hereda de fixer. La función de reparación accede a la función a reparar 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 es necesaria una evaluación diferida.

plantilla < nombre de tipo R , nombre de tipo D > clase reparador { público : R arreglar ( D x ) { retorno f ( x ); } privado : virtual R f ( D ) = 0 ; };                 hecho de clase : fijador público < largo , largo > { virtual largo f ( largo x ) { if ( x == 0 ) { return 1 ; } devolver x * arreglar ( x -1 ); } };                       resultado largo = hecho (). arreglar ( 5 );   

Mecanografía

En el Sistema F (cálculo lambda polimórfico), un combinador polimórfico de punto fijo tiene tipo ^{[ cita necesaria ]} ;

∀a.(a → a) → a

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

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

En el cálculo lambda de tipo simple , al combinador de punto fijo Y no se le puede asignar un tipo ^[16] porque en algún momento 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 escribir ningún combinador de punto fijo; en esos sistemas, cualquier soporte para la recursividad 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 escribir el combinador Y teniendo en cuenta adecuadamente la recursividad a nivel de tipo. La necesidad de autoaplicar la variable x se puede gestionar utilizando un tipo ( Rec a), que se define de manera 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: ^{[17] [18]}

Entrada :: ( Rec a -> a ) -> Rec a salida :: Rec a -> ( Rec a -> a )                

lo que nos deja escribir:

nuevo tipo Rec a = Entrada { salida :: Rec a -> a }            y :: ( a -> a ) -> a y = \ f -> ( \ x -> f ( fuera x x )) ( Entra ( \ x -> f ( fuera x x )))                      

O equivalentemente en OCaml:

escriba  ' a  recc  =  In  of  ( ' a  recc  ->  ' a ) deje  salir  ( In  x )  =  xsea  ​​y  f  =  ( diversión  x  a  ->  f  ( fuera  x  x )  a )  ( Entra  ( diversión  x  a  ->  f  ( fuera  x  x )  a ))

Alternativamente:

let  y  f  =  ( fun  x  ->  f  ( fun  z  ->  out  x  x  z ))  ( In  ( fun  x  ->  f  ( fun  z  ->  out  x  x  z )))

información general

Debido a que los combinadores de punto fijo se pueden usar para implementar la recursividad, es posible usarlos para describir tipos específicos de cálculos recursivos, como los de iteración de punto fijo , métodos iterativos , unión recursiva en bases de datos relacionales , análisis de flujo de datos , FIRST. y SEGUIR conjuntos 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 llama función identidad . Formalmente:

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

En contraste con 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, una vez aplicadas, las aplicaciones posteriores no tienen ningún efecto. Más formalmente:

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

Estas funciones se denominan idempotentes (ver también Proyección (matemáticas) ). Un ejemplo de dicha 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 de identidad o una función idempotente generalmente da como resultado un cálculo no final. 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 existen necesariamente en modelos de cálculo más restrictivos. Por ejemplo, no existen en el cálculo lambda de tipo simple .

El combinador Y permite definir la recursividad como un conjunto de reglas de reescritura , ^[19] sin requerir soporte nativo de recursividad en el lenguaje. ^[20]

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 recursividad anónima . ^{[nota 3] [21]}

Ver también

• Función anónima
• iteración de punto fijo
• Cálculo lambda#Recursión y puntos fijos
• elevación lambda
• dejar expresión

Notas

1. A lo largo de este artículo, se utilizan las reglas de sintaxis proporcionadas en 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 folklore , pero aparece a continuación:
   • Trey Nash, C# acelerado 2008 , Apress, 2007, ISBN  1-59059-873-3 , pág. 462—463. Derivado sustancialmente del blog de Wes Dyer (ver el siguiente artículo).
   • Wes Dyer Anonymous Recursion en C#, 2 de febrero de 2007, contiene un ejemplo sustancialmente similar al que se encuentra en el libro anterior, 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 Internacional.
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. "Notas de la conferencia sobre cálculo Lambda (PDF)". pag. 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. Prensa CRC. pag. 48.ISBN​ 9781439800010.
6. Goldberg, 2005
7. Alan Mathison Turing (diciembre de 1937). "La función en -conversión ". Revista de Lógica Simbólica . 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 mutuamente recursivas?". Desbordamiento de pila .
11. Bene, Adam (17 de agosto de 2017). "Combinadores de punto fijo en JavaScript". Estudio Bene . Medio . Consultado el 2 de agosto de 2020 .
12. "CS 6110 S17 Conferencia 5. Combinadores de recursividad y punto fijo" (PDF) . Universidad de Cornell . 4.1 Un combinador de punto fijo CBV.
13. La definición original en Data.Function.
14. Felleisen, Matías (1987). El cálculo Lambda-v-CS. Universidad de Indiana.
15. Talcott, Carolyn (1985). La esencia del ron: una teoría de los aspectos intensionales y extensionales de la computación tipo Lisp (tesis doctoral). Universidad Stanford.
16. Introducción al cálculo Lambda Archivado el 8 de abril de 2014 en la Wayback Machine.
17. Hilo de la lista de correo de Haskell sobre Cómo definir el combinador Y en Haskell, 15 de septiembre de 2006
18. Geuvers, Herman; Verkoelen, Joep. Sobre combinadores de punto fijo y bucles en teoría de tipos . CiteSeerX 10.1.1.158.1478 . 
19. Daniel P. Friedman , Matthias Felleisen (1986). "Capítulo 9: Lambda The Ultimate". El pequeño Lisper . Asociados de investigación científica . pag. 179."En el capítulo hemos derivado un combinador Y que nos permite escribir funciones recursivas de un argumento sin usar define".
20. Mike Vanier. "El combinador Y (ligero retorno) o: cómo tener éxito en la recursividad sin recurrir realmente". Archivado desde el original el 22 de agosto de 2011."En términos más generales, Y nos brinda una forma de obtener recursividad en un lenguaje de programación que admite funciones de primera clase pero que no tiene recursividad incorporada".
21. The If Works Deriving the Y combinador, 10 de enero de 2008

• Werner Kluge, Máquinas informáticas abstractas: una perspectiva del cálculo lambda , Springer, 2005, ISBN 3-540-21146-2 , págs. 
• Mayer Goldberg, (2005) Sobre la enumerabilidad recursiva de los 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 alegría, Manfred von Thun, (2002 o antes)
• The Lambda Calculus - notas de Don Blaheta, 12 de octubre de 2000
• Combinador Y
• "Un uso del combinador Y en Ruby"
• "Programación funcional en Ada"
• Código Rosetta - Combinador Y