Codificación de la iglesia

En matemáticas , la codificación de Church es una forma de representar varios tipos de datos en el cálculo lambda .

En el cálculo lambda sin tipos, el único tipo de dato primitivo son las funciones, representadas por términos de abstracción lambda. Los tipos que normalmente se consideran primitivos en otras notaciones (como enteros , booleanos , pares, listas y uniones etiquetadas ) no están presentes de forma nativa.

De ahí surge la necesidad de contar con formas de representar los datos de estos distintos tipos mediante términos lambda, es decir, mediante funciones que toman funciones como argumentos y devuelven funciones como resultados.

Los numerales de Church son una representación de los números naturales mediante la notación lambda. El método recibe su nombre de Alonzo Church , quien fue el primero en codificar datos en el cálculo lambda de esta manera. También puede extenderse para representar otros tipos de datos con un enfoque similar.

Este artículo utiliza ocasionalmente la sintaxis alternativa para los términos de abstracción lambda, donde λ x .λ y .λ z . N se abrevia como λ xyz . N , así como los dos combinadores estándar, $I\equiv \lambda xx$ y $K\equiv \lambda xy.x$ , según sea necesario.

Pares de iglesias

Los pares de Church son la codificación de Church del tipo par ( tupla de dos ). Tener dos cosas significa poder proporcionárselas a cualquier observador que espere dos cosas. El par se representa, por lo tanto, como una función que toma un argumento de función. El par en sí no decide qué hacer con los elementos de la tupla. Cuando se le da su argumento, lo aplica a los dos componentes del par. La definición del constructor de pares , las funciones de selección del primer elemento y de selección del segundo elemento en el cálculo lambda son:

{\begin{aligned}\operatorname {pair} &\equiv \lambda xy.\lambda zz\ x\ y\\\operatorname {first} &\equiv \lambda pp\ (\lambda xy.x)\\\operatorname {second} &\equiv \lambda pp\ (\lambda xy.y)\end{aligned}}

Por ejemplo,

{\begin{aligned}&\operatorname {primer} \ (\operatorname {par} \ a\ b)\\=&\ (\lambda pp\ (\lambda xy.x))\ ((\lambda xyz.z\ x\ y)\ a\ b)\\=&\ (\lambda pp\ (\lambda xy.x))\ (\lambda zz\ a\ b)\\=&\ (\lambda zz\ a\ b)\ (\lambda xy.x)\\=&\ (\lambda xy.x)\ a\ b\\=&\ a\end{aligned}}

Booleanos de la Iglesia

Las expresiones booleanas de Church codifican los valores booleanos verdadero y falso. Algunos lenguajes de programación las utilizan como modelo de implementación para la aritmética booleana; ejemplos de ello son Smalltalk y Pico.

La lógica booleana implica una elección entre dos alternativas. Por lo tanto, las codificaciones de Church para verdadero y falso son funciones de dos parámetros:

verdadero elige el primer parámetro ;
falso elige el segundo parámetro.

Las dos definiciones en cálculo lambda son:

{\begin{aligned}\operatorname {true} &\equiv \lambda a.\lambda ba\ \ \ \ \ =\lambda a.\lambda b.\operatorname {first} \,(\operatorname {pair} a\ b)\\\operatorname {false} &\equiv \lambda a.\lambda bb\ \ \ \ \ \,=\lambda a.\lambda b.\operatorname {second} \,(\operatorname {pair} a\ b)\end{aligned}}

Estas definiciones permiten que los predicados (es decir, funciones que devuelven valores lógicos ) actúen directamente como cláusulas condicionales , de modo que el operador `if` sea simplemente una función identidad y, por lo tanto, pueda omitirse. Cada valor lógico ya actúa como un `if` , realizando una elección entre sus dos argumentos. Un valor booleano aplicado a dos valores devuelve el primero o el segundo. La expresión

\operatorname {cláusula de prueba} \ \operatorname {cláusula entonces} \ \operatorname {cláusula sino}

Devuelve la cláusula then si la cláusula test es verdadera , y la cláusula else si la cláusula test es falsa .

Dado que los valores lógicos como verdadero y falso eligen su primer o segundo argumento, pueden combinarse para proporcionar operadores lógicos. Generalmente, son posibles varias implementaciones, ya sea manipulando directamente los parámetros o reduciéndolos a los valores lógicos más básicos. A continuación, se presentan las definiciones, utilizando la notación abreviada mencionada al inicio del artículo ( p y q son predicados; a y b son valores generales):

{\begin{aligned}\operatorname {if} &=\lambda pab.p\ a\ b&&\ \\\operatorname {and} &=\lambda pq.p\ q\ p&&=\lambda pqab.p\ (q\ a\ b)\ b\\\operatorname {or} &=\lambda pq.p\ p\ q&&=\lambda pqab.p\ a\ (q\ a\ b)\\\operatorname {not} &=\lambda p.p\operatorname {false} \operatorname {true} &&=\lambda pab\ \ .p\ b\ a\\\operatorname {xor} &=\lambda pq.p\ (\operatorname {not} \ q)\ q&&=\lambda pqab.p\ (q\ b\ a)\ (q\ a\ b)\\\operatorname {nand} &=\lambda pq.\operatorname {not} \ (\operatorname {and} p\ q)&&=\lambda pqab.p\ (q\ b\ a)\ a\\\operatorname {implies} &=\lambda pq.\operatorname {or} \ (\operatorname {not} p)\ q&&=\lambda pqab.p\ (q\ a\ b)\ a\\\end{aligned}}

Algunos ejemplos:

{\begin{aligned}\operatorname {and} \operatorname {true} \operatorname {false} &=(\lambda p.\lambda q.p\ q\ p)\ \operatorname {true} \ \operatorname {false} \\&=\operatorname {true} \operatorname {false} \operatorname {true} \\&=(\lambda a.\lambda b.a)\operatorname {false} \operatorname {true} \\&=\operatorname {false} \\\\\operatorname {or} \operatorname {true} \operatorname {false} &=(\lambda p.\lambda q.p\ p\ q)\ (\lambda a.\lambda b.a)\ (\lambda a.\lambda b.b)\\&=(\lambda a.\lambda b.a)\ (\lambda a.\lambda b.a)\ (\lambda a.\lambda b.b)\\&=(\lambda a.\lambda b.a)\\&=\operatorname {true} \\\\\operatorname {not} _{2}\ \operatorname {true} &=(\lambda p.\lambda a.\lambda b.p\ b\ a)(\lambda a.\lambda b.a)\\&=\lambda a.\lambda b.(\lambda a.\lambda b.a)\ b\ a\\&=\lambda a.\lambda b.(\lambda c.b)\ a\\&=\lambda a.\lambda b.b\\&=\operatorname {false} \\\\\operatorname {not} _{1}\ \operatorname {true} &=(\lambda p.\,p\ (\lambda a.\lambda b.\,b)\ (\lambda a.\lambda b.\,a))\ (\lambda a.\lambda b.\,a)\\&=(\lambda a.\lambda b.\,a)\ (\lambda a.\lambda b.\,b)\ (\lambda a.\lambda b.\,a)\\&=(\lambda b.\,(\lambda a.\lambda b.\,b))\ (\lambda a.\lambda b.\,a)\\&=\lambda a.\lambda b.\,b\\&=\operatorname {false} \end{aligned}}

Numerales de la iglesia

Los numerales de la Iglesia son las representaciones de los números naturales bajo la codificación de la Iglesia. La función de orden superior que representa el número natural n es una función que asigna cualquier función $f$ a su composición n -ésima . En términos más sencillos, un numeral representa el número aplicando cualquier función dada esa cantidad de veces en secuencia, comenzando desde cualquier valor inicial dado:

n:f\mapsto f^{\circ n}

f^{\circ n}(x)=(\underbrace {f\circ f\circ \ldots \circ f} _{n{\text{ times}}})\,(x)=\underbrace {f(f(\ldots (f} _{n{\text{ times}}}\,(x))\ldots ))

La codificación de Church es, por lo tanto, una codificación unaria de números naturales, ^{[ 1 ]} que corresponde al conteo simple . Cada numeral de Church logra esto por construcción.

Todos los numerales de Church son funciones que toman dos parámetros. Los numerales de Church 0 , 1 , 2 , ..., se definen de la siguiente manera en el cálculo lambda :

Comenzando con 0, sin aplicar la función en absoluto, proceda con 1 , aplicando la función una vez; 2 , aplicando la función dos veces seguidas; 3, aplicando la función tres veces seguidas, etc .:

{\begin{array}{r|l|l}{\text{Number}}&{\text{Function definition}}&{\text{Lambda expression}}\\\hline 0&0\ f\ x=x&0=\lambda f.\lambda x.x\\1&1\ f\ x=f\ x&1=\lambda f.\lambda x.f\ x\\2&2\ f\ x=f\ (f\ x)&2=\lambda f.\lambda x.f\ (f\ x)\\3&3\ f\ x=f\ (f\ (f\ x))&3=\lambda f.\lambda x.f\ (f\ (f\ x))\\\vdots &\vdots &\vdots \\n&n\ f\ x=f^{\circ n}\ x&n=\lambda f.\lambda x.f^{\circ n}\ x\end{array}}

El numeral 3 de Church es una cadena de tres aplicaciones de una función dada en secuencia, comenzando con un valor determinado. La función se aplica primero a un argumento dado y luego sucesivamente a su propio resultado. El resultado final no es el número 3 (a menos que el parámetro dado sea 0 y la función sea una función sucesora ). La función en sí, y no su resultado final, es el numeral 3 de Church . El numeral 3 de Church significa simplemente hacer algo tres veces. Es una demostración ostensiva de lo que se entiende por "tres veces".

Cálculo con numerales eclesiásticos

Las operaciones aritméticas con números producen números como resultado. En la codificación de Church, estas operaciones se representan mediante abstracciones lambda que, al aplicarse a los numerales de Church que representan los operandos, se reducen beta a los numerales de Church que representan los resultados.

Representación de la iglesia de la adición, $\operatorname {plus} (m,n)=m+n$ , utiliza la identidad $f^{\circ (m+n)}(x)=(f^{\circ m}\circ f^{\circ n})(x)=f^{\circ m}(f^{\circ n}(x))$ :

\operatorname {plus} \equiv \lambda mn.\lambda fx.m\ f\ (n\ f\ x)

La operación sucesora, $\operatorname {succ} (n)=n+1$ , se obtiene mediante la β-reducción de la expresión " $\operatorname {plus} \ 1$ ":

\operatorname {succ} \equiv \lambda n.\lambda fx.f\ (n\ f\ x)

Multiplicación, $\operatorname {mult} (m,n)=m*n$ , utiliza la identidad $f^{\circ (m*n)}(x)=(f^{\circ n})^{\circ m}(x)$ :

\operatorname {mult} \equiv \lambda mn.\lambda fx.m\ (n\ f)\ x

De este modo $b\ (b\ f)\equiv (\operatorname {mult} b\ b)\ f$ y $b\ (b\ (b\ f))\equiv (\operatorname {mult} b\ (\operatorname {mult} b\ b))\ f$ y así, en virtud de la codificación de Church que expresa la composición n -ésima, la operación de exponenciación $\operatorname {exp} (b,n)=b^{n}$ es dado por

\operatorname {exp} \equiv \lambda bn.n\ b\equiv \lambda bnfx.n\ b\ f\ x

La operación predecesora $\operatorname {pred} (n)$ es un poco más complicado. Necesitamos idear una operación que, cuando se repita $n+1$ los tiempos resultarán en $n$ aplicaciones de la función dada $f$ Esto se logra utilizando la función identidad en su lugar, solo una vez, y luego volviendo a cambiar a $f$ :

\operatorname {pred} \equiv \lambda nfx.n\ (\lambda ri.i\ (r\ f))\ (\lambda f.x)\ I

Como se mencionó anteriormente, $I$ es la función identidad, $\lambda x.x$ . El nombre de la variable $r$ Se elige como mnemotecnia para "resultado recursivo". Esta definición emplea un argumento adicional para usar el paradigma de paso de estado, ya que el cálculo lambda carece de mutación (por lo que nada se puede cambiar, solo reemplazar). Véase a continuación la explicación detallada.

Esto sugiere implementar, por ejemplo, funciones de división por la mitad y factoriales de manera similar al paso de estados.

{\begin{aligned}\operatorname {half} &\equiv \lambda nfx.n\ (\lambda rab.a\ (r\ b\ a))\ (\lambda ab.x)\ I\ f\\\operatorname {fact} &\equiv \lambda nf.n\ (\lambda ra.a\ (r\ (\operatorname {succ} a)))\ (\lambda a.f)\ 1\end{aligned}}

Por ejemplo, $\operatorname {pred} 4\ f\ x\,$ beta-reduce a $I(f\ (f\ (f\ x)))$ , $\operatorname {half} \ 5\ f\ x\,$ beta-reduce a $I\ (f\ (I\ (f\ (I\ x))))$ , y $\operatorname {fact} 4\,f\,$ beta-reduce a $1\ (2\ (3\ (4\ f)))$ .

Sustracción, $minus(m,n)=m-n$ , se expresa mediante la aplicación repetida de la operación predecesora un número determinado de veces, al igual que la suma se puede expresar mediante la aplicación repetida de la operación sucesora un número determinado de veces, etc.:

{\begin{aligned}(-)&\equiv \lambda mn.n\,\operatorname {pred} \,m\\(+)&\equiv \lambda mn.n\,\operatorname {succ} \,m\\(\times )&\equiv \lambda mn.n\ ((+)\ m)\ 0\\\operatorname {exp} &\equiv \lambda mn.n\ ((\times )\ m)\ 1\ \ \ \ \ \ \ \ \ \ \ \{-\ \ m^{n}\ -\}\\(\uparrow \uparrow )&\equiv \lambda mn.n\ (\operatorname {exp} \,m)\ 1\ \ \ \ \ \ \ \{-\ m\uparrow \uparrow n\ -\}\\\uparrow ^{k}&\equiv k\ (\lambda fmn.n\ (f\ m)\ 1)\ (\times )\\\end{aligned}}

$(\uparrow \uparrow )$ es la operación de tetración , $m\uparrow \uparrow 3=m^{(m^{(m^{1})})}$ , y $\uparrow ^{k}$ es de Knuth $k$ la flecha ^{[ 2 ]} en general.

De forma similar a la definición factorial anterior, la tetración también puede definirse utilizando las propiedades intrínsecas de la codificación de Church, creando la expresión de "código" para ella y dejando que los propios numerales de Church hagan el resto:

{\begin{aligned}\operatorname {tet} &\equiv \lambda mn.n\ (\lambda r.r\ m)\ 1\end{aligned}}

Aquí, de nuevo, $\operatorname {tet} \,m\ 3=1\ m\ m\ m=m^{(m^{(m^{1})})}$ .

Resta y división directas

Así como la suma como sucesión repetida tiene su contraparte en el estilo directo, la resta también puede expresarse de forma directa y más eficiente:

{\begin{aligned}\operatorname {minus} \equiv \lambda &mnfx.\\&m\ (\lambda rq.q\ r)\ (\lambda q.x)\\&(n\ (\lambda qr.r\ q)\ (\operatorname {Y} \ (\lambda qr.f\ (r\ q))))\end{aligned}}

Por ejemplo, $\operatorname {minus} \ 6\ 3\ f\ x$ se reduce a un equivalente de $f\ (2\ f\ x)$ .

Esto también proporciona otra versión predecesora, reductora de beta. $\lambda m.\operatorname {minus} \ m\ 1$ :

{\begin{aligned}\operatorname {pred'} \equiv \lambda mfx.m\ &(\lambda rq.q\ r)\ (\lambda q.x)\\&(\lambda r.r\ (\operatorname {Y} \ (\lambda qr.f\ (r\ q))))\end{aligned}}

La definición directa de división se da de manera bastante similar a como

{\begin{aligned}\operatorname {div} \equiv \lambda &mnfx.\\&m\ (\lambda rq.q\ r)\ (\lambda q.x)\\&(\operatorname {Y} \ (\lambda q.n\ (\lambda qr.r\ q)\ (\lambda r.f\ (r\ q))\ (\lambda x.x)))\end{aligned}}

La solicitud para $(\lambda x.x)$ logra la resta mediante $1$ mientras crea un ciclo de acciones que emiten repetidamente un $f$ después $n-1$ pasos.

En lugar de $\operatorname {Y}$ , $(\lambda q.m\,q\,x)$ También puede utilizarse en cada una de las tres definiciones anteriores.

Tabla de funciones de los números de la Iglesia

Notas :

1 2
En la codificación de la Iglesia,
- $\operatorname {pred} (0)=0$
- $m\leq n\to m-n=0$

Función predecesora

La función predecesora se da como

\operatorname {pred} \equiv \lambda nfx.n\ (\lambda ri.i\ (r\ f))\ (\lambda f.x)\ (\lambda u.u)

Esta codificación utiliza esencialmente la identidad

first(\ (\langle i,j\rangle \mapsto \langle j,f\circ j\rangle )^{\circ n}\langle I,I\rangle \ )={\begin{cases}I&{\mbox{if }}n=0,\\f^{\circ (n-1)}&{\mbox{otherwise}}\end{cases}}

o

first(\ (\langle x,y\rangle \mapsto \langle y,f(y)\rangle )^{\circ n}\langle x,x\rangle \ )={\begin{cases}x&{\mbox{if }}n=0,\\f^{\circ (n-1)}(x)&{\mbox{otherwise}}\end{cases}}

Una explicación de pred

La idea es la siguiente. Lo único conocido por la Iglesia numeral $\operatorname {pred} n$ es el numeral $n$ mismo. Dados dos argumentos $f$ y $x$ , como de costumbre, lo único que puede hacer es aplicar ese numeral a los dos argumentos, modificado de alguna manera para que la cadena de aplicaciones de n de largo creada así tenga uno (específicamente, el de más a la izquierda) $f$ en la cadena reemplazada por la función identidad:

{\begin{aligned}f^{\circ (n-1)}(x)&=\underbrace {I\ (\underbrace {f(f(\ldots (f} _{{n-1}{\text{ times}}}} _{n{\text{ times}}}\,(x))\ldots )))=(Xf)^{\circ n}(Z\,x)\ A\\&=\underbrace {Xf\ (Xf\ (\ldots (Xf} _{{n}{\text{ times}}}\,(Z\,x))\ldots ))\ A\\&=X\ f\ r_{1}\ A_{1}\,\,\,\{-\ and\ it\ must\ be\ equal\ to:\ -\}\\&=I\ (X\ f\ r_{2}\ A_{2})\\&=I\ (f\ (X\ f\ r_{3}\ A_{3}))\\&=I\ (f\ (f\ (X\ f\ r_{4}\ A_{4})))\\&\ldots \\&=I\ (f\ (f\ \ldots (X\ f\ r_{n}\ A_{n})\ldots ))\\&=\underbrace {I\ (f\ (f\ \ldots (f} _{n{\text{ times}}}\ (Z\ x\ A_{n+1}))\ldots ))\\\end{aligned}}

Aquí $Xf$ es el modificado $f$ , y $Z\,x$ es el modificado $x$ . Desde $Xf$ en sí mismo no se puede cambiar, su comportamiento solo se puede modificar a través de un argumento adicional, $A$ .

El objetivo se logra, entonces, al pasar ese argumento adicional. $A$ desde afuera hacia adentro , modificándolo según sea necesario, con las definiciones

{\begin{aligned}A_{1}\,\,\,\,\,\,\,\,\,\,&=\,I\\A_{\,i>1}\,\,\,\,\,&=\,f\\Z\ x\ f\,\,\,\,&=x=K\ x\ f\\X\ f\ r\ A_{i}&=A_{i}\ (r\ A_{i+1})\,\,\,\,\,\,\{-\ i.e.,\ -\}\\X\ f\ r\ i\,\,\,\,\,&=i\ (r\ f)\end{aligned}}

Que es exactamente lo que tenemos en el $\operatorname {pred}$ expresión lambda de la definición.

Ahora es bastante fácil ver que

{\begin{aligned}\operatorname {pred} \ (\operatorname {succ} \ n)\ f\ x&=\operatorname {succ} \ n\ (Xf)\ (K\ x)\ I\\&=X\ f\ (n\ (X\ f)\ (K\ x))\ I\\&=I\ (n\ (Xf)\ (K\ x)\ \,\,f\,\,\,)\\&=\ \ldots \\&=I\ (f\ (f\ \ldots (f\ (K\ x\,\,f\,\,))\ldots ))\\&=I\ (n\ f\ x)\\&=n\ f\ x\ \end{aligned}}

{\begin{aligned}\operatorname {pred} \ 0\ f\ x&=\ 0\ (Xf)\ (K\ x)\ I\\&=\ K\ x\ I\\&=\ x\\&=\ 0\ f\ x\end{aligned}}

es decir, por contracción eta y luego por inducción, sostiene que

{\begin{aligned}&\operatorname {pred} \ (\operatorname {succ} \ n)&&=\ n\\&\operatorname {pred} \ 0&&=\ 0\\&\operatorname {pred} \ (\operatorname {pred} \ 0)&&=\ \operatorname {pred} \ 0\ =\ 0\\&\ldots \end{aligned}}

etcétera.

Definir el depredador mediante pares

La identidad anterior puede codificarse con el uso explícito de pares. Esto puede hacerse de varias maneras, por ejemplo:

{\begin{aligned}\operatorname {f} =&\ \lambda p.\ \operatorname {pair} \ (\operatorname {second} \ p)\ (\operatorname {succ} \ (\operatorname {second} \ p))\\\operatorname {pred} _{2}=&\ \lambda n.\ \operatorname {first} \ (n\ \operatorname {f} \ (\operatorname {pair} \ 0\ 0))\\\end{aligned}}

La expansión para $\operatorname {pred} _{2}3$ es:

{\begin{aligned}\operatorname {pred} _{2}3=&\ \operatorname {first} \ (\operatorname {f} \ (\operatorname {f} \ (\operatorname {f} \ (\operatorname {pair} \ 0\ 0))))\\=&\ \operatorname {first} \ (\operatorname {f} \ (\operatorname {f} \ (\operatorname {pair} \ 0\ 1)))\\=&\ \operatorname {first} \ (\operatorname {f} \ (\operatorname {pair} \ 1\ 2))\\=&\ \operatorname {first} \ (\operatorname {pair} \ 2\ 3)\\=&\ 2\end{aligned}}

Esta es una definición más sencilla de idear, pero conduce a una expresión lambda más compleja.

{\begin{aligned}\operatorname {pred} _{2}\equiv \lambda n.n\ &(\lambda p.p\ (\lambda abh.h\ b\ (\operatorname {succ} \ b)))\,\,(\lambda h.h\ 0\ 0)\,\,(\lambda ab.a)\end{aligned}}

En el cálculo lambda, los pares son esencialmente argumentos adicionales, ya sea pasándolos de adentro hacia afuera como aquí, o de afuera hacia adentro como en el original. $\operatorname {pred}$ definición. Otra codificación sigue directamente la segunda variante de la identidad del predecesor,

{\begin{aligned}\operatorname {pred} _{3}\equiv \lambda nfx.n\ &(\lambda p.p\ (\lambda abh.h\ b\ (f\ b)))\,\,(\lambda h.h\ x\ x)\,\,(\lambda ab.a)\end{aligned}}

De esta forma ya está bastante cerca del original, "de afuera hacia adentro". $\operatorname {pred}$ definición, creando también la cadena de $f$ es como lo hace, solo que de una manera un poco más derrochadora. Pero es mucho menos derrochador que el anterior, $\operatorname {pred} _{2}$ definición aquí. De hecho, si seguimos su ejecución llegamos a la nueva definición, aún más simplificada, pero totalmente equivalente.

{\begin{aligned}\operatorname {pred} _{4}\equiv \lambda nfx.n\ &(\lambda rab.r\ b\ (f\ b))\,K\ x\ x\end{aligned}}

lo que deja completamente claro y evidente que todo esto se trata simplemente de modificación y paso de argumentos. Su reducción procede como

{\begin{aligned}\operatorname {pred} _{4}3\ f\ x&=\ (..(..(..K)))\ x\ \,x\\&=\ (..(..K))\,\,\,\,\,\,\,x\ \,\,(f\ x)\\&=\ (..K)\,\,\,\,\,\,(f\ x)\ \,\,(f\ (f\ x))\\&=\ K\,\,\,\,(f\ (f\ x))\ \,\,(f\ (f\ (f\ x)))\\&=\ f\ (f\ x)\\\end{aligned}}

mostrando claramente lo que está sucediendo. Aun así, el original $\operatorname {pred}$ es mucho preferible ya que funciona de arriba hacia abajo y, por lo tanto, puede detenerse inmediatamente si la función proporcionada por el usuario $f$ es un cortocircuito. El enfoque de arriba hacia abajo también se utiliza con otras definiciones como

{\begin{aligned}\operatorname {pred} _{5}\equiv \lambda nfx.n\ &(\lambda rab.a\ (r\ b\ b))\,(\lambda ab.x)\ I\ f\\\operatorname {third} \equiv \lambda nfx.n\ &(\lambda rabc.a\ (r\ b\ c\ a))\,(\lambda abc.x)\ I\ I\ f\\\operatorname {thirdRounded} \equiv \lambda nfx.n\ &(\lambda rabc.a\ (r\ b\ c\ a))\,(\lambda abc.x)\ I\ f\ I\\\operatorname {twoThirds} \equiv \lambda nfx.n\ &(\lambda rabc.a\ (r\ b\ c\ a))\,(\lambda abc.x)\ I\ f\ f\\\operatorname {factorial} \equiv \lambda nfx.n\ &(\lambda ra.a\ (r\ (\operatorname {succ} a)))\,(\lambda a.f)\ 1\ x\\\end{aligned}}

División mediante recursión general

La división de números naturales puede implementarse mediante ^{[ 3 ].}

n/m=\operatorname {if} \ n\geq m\ \operatorname {then} \ 1+(n-m)/m\ \operatorname {else} \ 0

Calculador $n-m$ con $\lambda nm.m\,\operatorname {pred} \,n$ requiere muchas reducciones beta. A menos que se haga la reducción a mano, esto no importa demasiado, pero es preferible no tener que hacer este cálculo dos veces (a menos que se use la definición de resta directa, ver más arriba). El predicado más simple para probar números es IsZero, así que considere la condición.

\operatorname {IsZero} \ (\operatorname {minus} \ n\ m)

Pero esta condición es equivalente a $n\leq m$ , no $n<m$ . Si se utiliza esta expresión, entonces la definición matemática de división dada anteriormente se traduce en una función sobre los numerales de la Iglesia como,

\operatorname {divide1} \ n\ m\ f\ x=(\lambda d.\operatorname {IsZero} \ d\ (0\ f\ x)\ (f\ (\operatorname {divide1} \ d\ m\ f\ x)))\ (\operatorname {minus} \ n\ m)

Como se deseaba, esta definición tiene una sola llamada a $\operatorname {minus} \ n\ m$ Sin embargo, el resultado es que esta fórmula da el valor de $(n-1)/m$ .

Este problema puede corregirse sumando 1 a n antes de llamar a divide . La definición de divide es entonces:

\operatorname {divide} \ n=\operatorname {divide1} \ (\operatorname {succ} \ n)

divide1 es una definición recursiva. El combinador Y puede usarse para implementar la recursión. Crea una nueva función llamada div by;

En el lado izquierdo $\operatorname {divide1} \rightarrow \operatorname {div} \ c$
En el lado derecho $\operatorname {divide1} \rightarrow c$

Llegar,

\operatorname {div} =\lambda c.\lambda n.\lambda m.\lambda f.\lambda x.(\lambda d.\operatorname {IsZero} \ d\ (0\ f\ x)\ (f\ (c\ d\ m\ f\ x)))\ (\operatorname {minus} \ n\ m)

Entonces,

\operatorname {divide} =\lambda n.\operatorname {divide1} \ (\operatorname {succ} \ n)

dónde,

{\begin{aligned}\operatorname {divide1} &=Y\ \operatorname {div} \\\operatorname {succ} &=\lambda n.\lambda f.\lambda x.f\ (n\ f\ x)\\Y&=\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))\\0&=\lambda f.\lambda x.x\\\operatorname {IsZero} &=\lambda n.n\ (\lambda x.\operatorname {false} )\ \operatorname {true} \end{aligned}}

{\begin{aligned}\operatorname {true} &\equiv \lambda a.\lambda b.a\\\operatorname {false} &\equiv \lambda a.\lambda b.b\end{aligned}}

{\begin{aligned}\operatorname {minus} &=\lambda m.\lambda n.n\operatorname {pred} m\\\operatorname {pred} &=\lambda n.\lambda f.\lambda x.n\ (\lambda g.\lambda h.h\ (g\ f))\ (\lambda u.x)\ (\lambda u.u)\end{aligned}}

Da,

\scriptstyle \operatorname {divide} =\lambda n.((\lambda f.(\lambda x.x\ x)\ (\lambda x.f\ (x\ x)))\ (\lambda c.\lambda n.\lambda m.\lambda f.\lambda x.(\lambda d.(\lambda n.n\ (\lambda x.(\lambda a.\lambda b.b))\ (\lambda a.\lambda b.a))\ d\ ((\lambda f.\lambda x.x)\ f\ x)\ (f\ (c\ d\ m\ f\ x)))\ ((\lambda m.\lambda n.n(\lambda n.\lambda f.\lambda x.n\ (\lambda g.\lambda h.h\ (g\ f))\ (\lambda u.x)\ (\lambda u.u))m)\ n\ m)))\ ((\lambda n.\lambda f.\lambda x.f\ (n\ f\ x))\ n)

O como texto, usando \ para $λ$ ,

dividir = (\n.((\f.(\xx x) (\xf (xx))) (\c.\n.\m.\f.\x.(\d.(\nn (\x.(\a.\bb)) (\a.\ba)) d ((\f.\xx) fx) (f (cdmfx))) ((\m.\nn (\n.\f.\xn (\g.\hh (gf)) (\ux) (\uu)) m) nm))) ((\n.\f.\x. f (nfx)) n))

Por ejemplo, 9/3 está representado por

dividir (\f.\xf (f (f (f (f (f (f (f (fx))))))))) (\f.\xf (f (fx)))

Utilizando una calculadora de cálculo lambda, la expresión anterior se reduce a 3, utilizando el orden normal.

\f.\xf (f (f (x)))

Predicados

Un predicado es una función que devuelve un valor booleano. El predicado más fundamental sobre los numerales de la Iglesia es $\operatorname {IsZero}$ , que regresa $\operatorname {true}$ si su argumento es el numeral de la Iglesia $0$ , y $\operatorname {false}$ de lo contrario:

\operatorname {IsZero} =\lambda n.n\ (\lambda x.\operatorname {false} )\ \operatorname {true}

El siguiente predicado comprueba si el primer argumento es menor o igual que el segundo:

\operatorname {LEQ} =\lambda m.\lambda n.\operatorname {IsZero} \ (\operatorname {minus} \ m\ n)

Debido a la identidad

x=y\equiv (x\leq y\land y\leq x)

La prueba de igualdad se puede implementar como

\operatorname {EQ} =\lambda m.\lambda n.\operatorname {and} \ (\operatorname {LEQ} \ m\ n)\ (\operatorname {LEQ} \ n\ m)

En lenguajes de programación

La mayoría de los lenguajes de programación del mundo real admiten enteros nativos de máquina; las funciones ` church` y `unchurch` convierten entre enteros no negativos y sus numerales de Church correspondientes. Estas funciones se presentan aquí en Haskell , donde `<sup>c</sup>` \corresponde a la λ del cálculo lambda. Las implementaciones en otros lenguajes son similares.

tipo Iglesia a = ( a -> a ) -> a -> aiglesia :: Entero -> Iglesia Entero iglesia 0 = \ f -> \ x -> x iglesia n = \ f -> \ x -> f ( iglesia ( n - 1 ) f x )unchurch :: Iglesia Entero -> Entero unchurch cn = cn ( + 1 ) 0

Números firmados

Un método sencillo para extender los numerales de Church a números con signo consiste en utilizar un par de Church, que contiene numerales de Church que representan un valor positivo y uno negativo. ^{[ 4 ]} El valor entero es la diferencia entre los dos numerales de Church.

Un número natural se convierte en un número con signo mediante:

\operatorname {convert} _{s}=\lambda x.\operatorname {pair} \ x\ 0

La negación se realiza intercambiando los valores.

\operatorname {neg} _{s}=\lambda x.\operatorname {pair} \ (\operatorname {second} \ x)\ (\operatorname {first} \ x)

El valor entero se representa de forma más natural si uno de los elementos del par es cero. La función OneZero logra esta condición.

\operatorname {OneZero} =\lambda x.\operatorname {IsZero} \ (\operatorname {first} \ x)\ x\ (\operatorname {IsZero} \ (\operatorname {second} \ x)\ x\ (\operatorname {OneZero} \ (\operatorname {pair} \ (\operatorname {pred} \ (\operatorname {first} \ x))\ (\operatorname {pred} \ (\operatorname {second} \ x)))))

La recursión puede implementarse utilizando el combinador Y,

\operatorname {OneZ} =\lambda c.\lambda x.\operatorname {IsZero} \ (\operatorname {first} \ x)\ x\ (\operatorname {IsZero} \ (\operatorname {second} \ x)\ x\ (c\ (\operatorname {pair} \ (\operatorname {pred} \ (\operatorname {first} \ x))\ (\operatorname {pred} \ (\operatorname {second} \ x)))))

\operatorname {OneZero} =Y\operatorname {OneZ}

Más y menos

La suma se define matemáticamente en el par mediante:

x+y=[x_{p},x_{n}]+[y_{p},y_{n}]=x_{p}-x_{n}+y_{p}-y_{n}=(x_{p}+y_{p})-(x_{n}+y_{n})=[x_{p}+y_{p},x_{n}+y_{n}]

La última expresión se traduce al cálculo lambda como,

\operatorname {plus} _{s}=\lambda x.\lambda y.\operatorname {OneZero} \ (\operatorname {pair} \ (\operatorname {plus} \ (\operatorname {first} \ x)\ (\operatorname {first} \ y))\ (\operatorname {plus} \ (\operatorname {second} \ x)\ (\operatorname {second} \ y)))

De manera similar se define la resta,

x-y=[x_{p},x_{n}]-[y_{p},y_{n}]=x_{p}-x_{n}-y_{p}+y_{n}=(x_{p}+y_{n})-(x_{n}+y_{p})=[x_{p}+y_{n},x_{n}+y_{p}]

donación,

\operatorname {minus} _{s}=\lambda x.\lambda y.\operatorname {OneZero} \ (\operatorname {pair} \ (\operatorname {plus} \ (\operatorname {first} \ x)\ (\operatorname {second} \ y))\ (\operatorname {plus} \ (\operatorname {second} \ x)\ (\operatorname {first} \ y)))

Multiplicar y dividir

La multiplicación puede definirse mediante:

x*y=[x_{p},x_{n}]*[y_{p},y_{n}]=(x_{p}-x_{n})*(y_{p}-y_{n})=(x_{p}*y_{p}+x_{n}*y_{n})-(x_{p}*y_{n}+x_{n}*y_{p})=[x_{p}*y_{p}+x_{n}*y_{n},x_{p}*y_{n}+x_{n}*y_{p}]

La última expresión se traduce al cálculo lambda como,

\operatorname {mult} _{s}=\lambda x.\lambda y.\operatorname {pair} \ (\operatorname {plus} \ (\operatorname {mult} \ (\operatorname {first} \ x)\ (\operatorname {first} \ y))\ (\operatorname {mult} \ (\operatorname {second} \ x)\ (\operatorname {second} \ y)))\ (\operatorname {plus} \ (\operatorname {mult} \ (\operatorname {first} \ x)\ (\operatorname {second} \ y))\ (\operatorname {mult} \ (\operatorname {second} \ x)\ (\operatorname {first} \ y)))

Aquí se ofrece una definición similar para la división, con la salvedad de que, en esta definición, uno de los valores de cada par debe ser cero (véase OneZero más arriba). La función divZ nos permite ignorar el valor que tiene un componente cero.

\operatorname {divZ} =\lambda x.\lambda y.\operatorname {IsZero} \ y\ 0\ (\operatorname {divide} \ x\ y)

Luego se usa divZ en la siguiente fórmula, que es la misma que para la multiplicación, pero con mult reemplazado por divZ .

\operatorname {divide} _{s}=\lambda x.\lambda y.\operatorname {pair} \ (\operatorname {plus} \ (\operatorname {divZ} \ (\operatorname {first} \ x)\ (\operatorname {first} \ y))\ (\operatorname {divZ} \ (\operatorname {second} \ x)\ (\operatorname {second} \ y)))\ (\operatorname {plus} \ (\operatorname {divZ} \ (\operatorname {first} \ x)\ (\operatorname {second} \ y))\ (\operatorname {divZ} \ (\operatorname {second} \ x)\ (\operatorname {first} \ y)))

Números racionales y reales

Los números reales racionales y computables también pueden codificarse en el cálculo lambda. Los números racionales pueden codificarse como un par de números con signo. Los números reales computables pueden codificarse mediante un proceso de limitación que garantiza que la diferencia con el valor real difiera en un número que puede hacerse tan pequeño como sea necesario. ^{[ 5 ]}^{[ 6 ]} Las referencias dadas describen software que, en teoría, podría traducirse al cálculo lambda. Una vez definidos los números reales, los números complejos se codifican naturalmente como un par de números reales.

Los tipos de datos y las funciones descritas anteriormente demuestran que cualquier tipo de dato o cálculo puede codificarse en el cálculo lambda. Esta es la tesis de Church-Turing .

Codificaciones de lista

Una lista contiene algunos elementos en orden. Las operaciones básicas sobre listas son:

Una representación de listas debería proporcionar formas de implementar estas operaciones.

La representación arquetípica de listas en el cálculo lambda es la codificación de listas de Church. Representa las listas como pliegues derechos , es decir, como funciones que devuelven el resultado de plegar la lista con argumentos proporcionados por el usuario.

Sigue el paradigma de que "una cosa es el resultado de su observación". Independientemente de la implementación concreta, al plegar una lista de valores se obtiene el mismo resultado. Esto proporciona una visión abstracta de lo que es una lista. La codificación de listas de Church es un ejemplo de este mecanismo.

Por otro lado, visto de forma más concreta, las listas pueden representarse como una secuencia de nodos de lista enlazados .

A continuación se presentan cuatro representaciones diferentes de listas:

Listas de iglesias: representación en el pliegue derecho .
Dos pares de iglesias por cada nodo de la lista.
Un par de iglesias por cada nodo de la lista.
Codificación de Scott.

Listas de iglesias: representación del pliegue derecho

Esta es la codificación original de Church para listas. Una lista se representa mediante una función binaria que, al recibir dos argumentos (una "función de combinación" y un "valor centinela"), realiza el pliegue derecho de la lista codificada utilizando dichos argumentos.

Para una lista vacía, el valor centinela se devuelve como resultado del plegado. El resultado de plegar una lista no vacía con cabeza h y cola t es el resultado de combinar, mediante la función proporcionada, la cabeza h con el resultado de plegar la cola t con los dos argumentos proporcionados. Por lo tanto, los dos argumentos de la función de combinación son, conceptualmente, el elemento actual y el resultado de plegar el resto de la lista.

Por ejemplo, una lista de tres elementos x, y y z está representada por un término que, al aplicarse a c y n, devuelve cx (cy (czn)). De forma equivalente, es una aplicación de la cadena de composiciones funcionales ( $\circ$ ) de aplicaciones parciales, ((cx) $\circ$ (cy) $\circ$ (cz)) n.

{\begin{aligned}\operatorname {nil} &\equiv \lambda \,c\,n.n\\\operatorname {isnil} &\equiv \lambda \,l.l\ (\lambda \,h\,r.\operatorname {false} )\ \operatorname {true} \\\operatorname {cons} &\equiv \lambda \,h\,t.\lambda \,c\,n.c\ h\ (t\ c\ n)\\\operatorname {singleton} &\equiv \lambda \,h.\lambda \,c\,n.c\ h\ n\\\operatorname {append} &\equiv \lambda \,l\,t.\lambda \,c\,n.l\ c\ (t\ c\ n)\\\operatorname {nonempty} &\equiv \lambda \,l.l\ (\lambda \,h\,r.\operatorname {true} )\ \operatorname {false} \\\operatorname {head} &\equiv \lambda \,l.l\ (\lambda \,h\,r.h)\ \operatorname {false} \\\operatorname {safeHead} &\equiv \lambda \,l\,e\,s.l\ (\lambda \,h\,r.s\ h)\ e\\\operatorname {fold} &\equiv \lambda \,c\,n\,l.l\ c\ n\\\operatorname {map} &\equiv \lambda f\,l.\lambda \,c\,n.l\ (\lambda \,h\,r.c\ (f\ h)\ r)\ n\equiv \lambda f\,l\,c.l\ (c\circ f)\\\operatorname {tail} &\equiv \lambda \,l.\lambda \,c\,n.l\ (\lambda \,h\,r\,g.g\ h\ (r\ c))\ (\lambda \,g.n)\ (\lambda \,h\,t.t)\end{aligned}}

Estas definiciones siguen la siguiente lógica: las ecuaciones

pliegue cn [ ] = n pliegue cn [x ] = cxn fold cn [x,y,z] = cx (cy (czn))

significa que

{\begin{aligned}&\{\ [\ \ \ \ ]\ \}&&\equiv \lambda \,c\,n.n\\&\{\ [\ x\ \ \ ]\ \}&&\equiv \lambda \,c\,n.c\ x\ n\\&\{\ [\ x,\,y,\,z\ ]\ \}&&\equiv \lambda \,c\,n.c\ x\ (c\ y\ (c\ z\ n))\end{aligned}}

dónde $\{\ l\ \}=\lambda \,c\,n.fold\ c\ n\ l$ denota la representación de la lista de la iglesia $l$ .

Dado que la lista codificada de Church es su propia función de plegado, plegarla simplemente significa aplicar esa función a los argumentos proporcionados.

Esta representación de lista se puede tipificar en System F.

La evidente correspondencia con los numerales de la Iglesia no es casual, ya que puede verse como una codificación unaria, con los números naturales representados por listas de valores unitarios (es decir, no importantes), por ejemplo [() () ()], donde la longitud de la lista sirve como representación del número natural. El plegado a la derecha sobre dichas listas utiliza funciones que necesariamente ignoran el valor del elemento, y es equivalente a la composición funcional encadenada, es decir ( (c ()) $\circ$ (c ()) $\circ$ (c ()) ) n = (f $\circ$ F $\circ$ f) n, como se usa en los numerales eclesiásticos.

Dos pares como nodo de lista

Una lista no vacía puede representarse mediante un par de Church, donde

primero contiene el encabezado de la lista
El segundo contiene la cola de la lista.

Sin embargo, esto no proporciona una representación de la lista vacía, ya que no existe un puntero "nulo". Para representar el valor nulo, el par se puede envolver en otro par, lo que da como resultado tres valores:

Primero , el indicador de lista nula (un valor booleano).
primero de segundo contiene la cabeza ( coche ).
segundo de segundo contiene la cola ( cdr ).

Utilizando esta idea, las operaciones básicas de lista se pueden definir de esta manera: ^{[ 7 ]}

En un nodo nulo , nunca se accede al segundo elemento , siempre que head y tail solo se apliquen a listas no vacías.

Un par como nodo de lista

Alternativamente, defina ^{[ 8 ]}

{\begin{aligned}\operatorname {cons} &\equiv \operatorname {pair} \\\operatorname {nil} &\equiv \operatorname {false} \\\operatorname {isnil} &\equiv \lambda l.\ l\ (\lambda htd.\operatorname {false} )\ \operatorname {true} \\\operatorname {head} &\equiv \lambda l.\ l\ (\lambda htd.\ h)\ \operatorname {nil} \\\operatorname {tail} &\equiv \lambda l.\ l\ (\lambda htd.\ t)\ \operatorname {nil} \\\end{aligned}}

donde las definiciones como la última siguen todas el mismo patrón general para el uso seguro de una lista, con $h$ y $t$ refiriéndose al principio y al final de la lista, y $d$ siendo desechado, como un dispositivo artificial:

{\begin{aligned}\lambda l.l\ (\lambda htd.\langle \operatorname {head-and-tail-clause} \rangle )\ \langle \operatorname {nil-clause} \rangle \\\end{aligned}}

Otras operaciones en esta codificación son:

{\begin{aligned}\operatorname {lfold} &\equiv \lambda g.\ \operatorname {Y} \ (\lambda r.\lambda al.\ l\ (\lambda htd.\ r\ (g\ a\ h)\ t)\ a)\\\operatorname {rfold} &\equiv \lambda gz.\ \operatorname {Y} \ (\lambda r.\lambda l.\ l\ (\lambda htd.\ g\ h\ (r\ t))\ z)\\\operatorname {length} &\equiv \operatorname {rfold} \ (\lambda hr.\ \operatorname {succ} \ r)\ \operatorname {zero} \\&\equiv \lambda lfx.\ \operatorname {rfold} \ (\lambda h.\ f)\ x\ l\\\end{aligned}}

{\begin{aligned}\operatorname {map} &\equiv \lambda f.\ \operatorname {rfold} \ (\lambda hr.\operatorname {cons} \ (f\ h)\ r)\ \operatorname {nil} \\\operatorname {filter} &\equiv \lambda p.\ \operatorname {rfold} \ (\lambda hr.\ p\ h\ (\operatorname {cons} \ h\ r)\ r)\ \operatorname {nil} \\\operatorname {reverse} &\equiv \operatorname {lfold} \ (\lambda ah.\ \operatorname {cons} \ h\ a)\ \operatorname {nil} \\\operatorname {append} &\equiv \lambda lm.\ \operatorname {rfold} \ \operatorname {cons} \ m\ \ l\\\operatorname {conj} &\equiv \lambda lv.\ \operatorname {append} \ l\ \ (\operatorname {cons} \ v\ \operatorname {nil} )\end{aligned}}

{\begin{aligned}\operatorname {drop} \equiv \ &\lambda n.\ n\ \operatorname {tail} \\\equiv \ &\operatorname {Y} \ (\lambda r.\lambda nl.\ l\ (\lambda htd.\\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \operatorname {IsZero} \ n\ l\ (r\ (\operatorname {pred} \ n)\ t))\ \operatorname {nil} )\\\equiv \ &\lambda n.\ n\ (\lambda rl.l\ (\lambda htd.r\ t)\ \operatorname {nil} )\ (\lambda l.l)\\\operatorname {drop-while} \equiv \ &\lambda p.\ \operatorname {Y} \ (\lambda rl.\ l\ (\lambda htd.\ p\ h\ (r\ t)\ l)\ \operatorname {nil} )\\\operatorname {drop-last} \equiv \ &\lambda nl.\ \operatorname {IsZero} \ n\ \,l\ \,(\operatorname {second} \ (\\&\ \ \ \ \ \ \ \ \ \ \ \ \operatorname {Y} \ (\lambda rl_{r}.\ l_{r}\ (\lambda htd.\\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ r\ t\ (\lambda n_{a}l_{a}.\ \operatorname {IsZero} \ n_{a}\\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (\operatorname {pair} \ \operatorname {zero} \ (\operatorname {cons} \ h\ l_{a}))\\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (\operatorname {pair} \ (\operatorname {pred} \ n_{a})\ \operatorname {nil} )\ ))\\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (\operatorname {pair} \ n\ \operatorname {nil} )\ )\\&\ \ \ \ \ \ \ \ \ \ \ \ \ l\ ))\\\equiv \ &\lambda nl.\ \operatorname {map} \ \operatorname {first} \ (\operatorname {zip} \ l\ \,(\operatorname {drop} \ n\ l))\\\operatorname {take} \equiv \ &\operatorname {Y} \ (\lambda rnl.\ l\ (\lambda htd.\ \operatorname {IsZero} \ n\ \operatorname {nil} \ \\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ (\operatorname {cons} \ h\ (r\ (\operatorname {pred} \ n)\ t)))\ \operatorname {nil} )\\\equiv \ &\lambda nl.\ \operatorname {map} \ \operatorname {first} \ (\operatorname {zip} \ l\ \,(\operatorname {replicate} \ n\ \,\operatorname {nil} ))\\\equiv \ &\lambda n.\ n\ (\lambda rl.\ l\ (\lambda htd.\ \operatorname {cons} \ h\ (r\ t))\ \operatorname {nil} )\ (\lambda l.\operatorname {nil} )\\\operatorname {take-while} \equiv \ &\lambda p.\ \operatorname {Y} \ (\lambda rl.\ l\ (\lambda htd.\ p\ h\ (\operatorname {cons} \ h\ (r\ t))\ \operatorname {nil} )\ \operatorname {nil} )\\\equiv \ &\lambda p.\ \operatorname {rfold} \ (\lambda hr.\ p\ h\ (\operatorname {cons} \ h\ r)\ \operatorname {nil} )\ \operatorname {nil} \\\operatorname {take-last} \equiv \ &\lambda nl.\ \operatorname {IsZero} \ n\ \operatorname {nil} \ (\operatorname {second} \ (\\&\ \ \ \ \ \ \ \ \ \ \ \ \operatorname {Y} \ (\lambda rl_{r}.\ l_{r}\ (\lambda htd.\\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ r\ t\ (\lambda n_{a}l_{a}.\ \operatorname {IsZero} \ n_{a}\\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (\operatorname {pair} \ \operatorname {zero} \ l_{a})\\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (\operatorname {pair} \ (\operatorname {pred} \ n_{a})\ l_{r})\ ))\\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (\operatorname {pair} \ n\ \operatorname {nil} )\ )\\&\ \ \ \ \ \ \ \ \ \ \ \ \ l\ ))\\\equiv \ &\lambda nl.\ \operatorname {drop} \ (\operatorname {length} \ (\operatorname {drop} \ n\ \,l))\ l\end{aligned}}

{\begin{aligned}\operatorname {all} &\equiv \operatorname {Y} \ (\lambda rpl.\ l\ (\lambda htd.\ p\ h\ (r\ p\ t)\ \operatorname {false} )\ \operatorname {true} )\\\operatorname {any} &\equiv \operatorname {Y} \ (\lambda rpl.\ l\ (\lambda htd.\ p\ h\ \operatorname {true} \ (r\ p\ t))\ \operatorname {false} )\\\operatorname {element-at} &\equiv \lambda nl.\ \operatorname {head} \ (\operatorname {drop} \ n\ l)\\\operatorname {insert-at} &\equiv \lambda nvl.\ \operatorname {append} \ (\operatorname {take} \ n\ l)\ (\operatorname {cons} \ v\ (\operatorname {drop} \ n\ l))\\\operatorname {remove-at} &\equiv \lambda nl.\ \operatorname {append} \ (\operatorname {take} \ n\ l)\ (\operatorname {drop} \ (\operatorname {succ} \ n)\ l)\\\operatorname {replace-at} &\equiv \lambda nvl.\ \operatorname {append} \ (\operatorname {take} \ n\ l)\ (\operatorname {cons} \ v\ (\operatorname {drop} \ (\operatorname {succ} \ n)\ l))\\\operatorname {index-of} &\equiv \lambda p.\ \operatorname {Y} \ (\lambda rnl.\ l\ (\lambda htd.\ p\ h\ n\ (r\ (\operatorname {succ} \ n)\ t))\ \operatorname {zero} )\ \operatorname {one} \\\operatorname {last-index-of} &\equiv \lambda p.\ \operatorname {Y} \ (\lambda rnl.\ l\ (\lambda htd.\ (\lambda i.\ \operatorname {IsZero} \ i\ (p\ h\ n\ \operatorname {zero} )\ i)\\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (r\ (\operatorname {succ} \ n)\ t))\ \operatorname {zero} )\ \operatorname {one} \\\operatorname {range} &\equiv \lambda fz.\ \operatorname {Y} \ (\lambda rsn.\ \operatorname {IsZero} \ n\ \operatorname {nil} \ (\operatorname {cons} \ (s\ f\ z)\\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (r\ (\operatorname {succ} \ s)\ (\operatorname {pred} \ n))))\ \operatorname {zero} \\\operatorname {repeat} &\equiv \lambda v.\ \operatorname {Y} \ (\lambda r.\ \operatorname {cons} \ v\ r)\\\operatorname {replicate} &\equiv \lambda nv.\ n\ (\operatorname {cons} \ v)\ \operatorname {nil} \\\operatorname {zip} &\equiv Y\ (\lambda rlm.\ l\ (\lambda htd.\ m\ (\lambda esz.\\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \operatorname {cons} \ (\operatorname {pair} \ h\ e)\ (r\ t\ s))\ \operatorname {nil} )\ \operatorname {nil} )\\\end{aligned}}

Scott enumera

La codificación Scott para tipos de datos sigue su sintaxis superficial sin tener en cuenta la recursión en el tipo de dato. En el estilo de definición de tipos de datos algebraicos de disyunción de conjunciones o suma de productos, representa un dato dado como una función que espera tantos argumentos como alternativas haya en su definición de tipo de dato, donde se espera que cada uno de dichos argumentos sea una función "manejadora" que debe ser capaz de manejar la cantidad dada de argumentos de datos que corresponderán a los campos de datos para esa alternativa.

Dados todos los manejadores como argumentos, la función de representación de datos llamará al manejador apropiado con los datos internos correspondientes. Por lo tanto, se puede decir que los valores codificados en Scott incorporan el manejo de casos de coincidencia de patrones para su tipo de datos.

Para las listas, significa la definición del tipo de datos.

$\qquad List:=\operatorname {NIL} \ |\,\operatorname {Cons} \,\langle val\rangle \,List$

y listas representadas como

$\quad {\begin{aligned}\operatorname {NIL} &=\lambda nc.n\\\operatorname {Cons} &=\lambda ad.\lambda nc.c\ a\ d\\\operatorname {IsEmpty} &=\lambda l.l\,\operatorname {true} \,(\lambda ad.\operatorname {false} )\\\operatorname {Head} &=\lambda l.l\,\operatorname {NIL} \,(\lambda ad.a)\\\operatorname {Tail} &=\lambda l.l\,\operatorname {NIL} \,(\lambda ad.d)\\\operatorname {Foldr} &=\lambda gz.\operatorname {Y} \lambda rl.l\ z\ (\lambda ad.g\,a\ (r\ d))\\\operatorname {Foldr2} &=\lambda gzpq.\operatorname {Foldr} \ (\lambda ark.k\ a\ r)\ (\lambda k.z)\ p\\&\ \ \ \ \ \ \ \ (\operatorname {Foldr} \ (\lambda bsar.g\ a\ b\ (r\ s))\ (\lambda ar.z)\ q)\\&=\lambda gzpq.\operatorname {Foldr} \ (\lambda t.t\ g)\ z\ (\operatorname {Zip} \ p\ q)\\&=\lambda gz.\operatorname {Y} \lambda rpq.p\,z\,(\lambda ad.\\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ q\,z\,(\lambda be.g\ a\ b\ (r\ d\ e)))\\\operatorname {Appd} &=\operatorname {Foldr} \,\operatorname {Cons} \\\operatorname {Map} &=\lambda f.\operatorname {Foldr} \ (\lambda a.\operatorname {Cons} \ (f\ a))\,\operatorname {NIL} \\\operatorname {Map2} &=\lambda f.\operatorname {Foldr2} \ (\lambda ab.\operatorname {Cons} \ (f\ a\ b))\,\operatorname {NIL} \\&=\lambda f.\operatorname {Y} \lambda rpq.p\,\operatorname {NIL} \,(\lambda ad.\\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ q\,\operatorname {NIL} \,(\lambda be.\operatorname {Cons} \,(f\ a\ b)\ (r\ d\ e)))\\\operatorname {Zip} &=\operatorname {Map2} \,\operatorname {pair} \\\end{aligned}}$

Las operaciones recursivas en listas de Scott normalmente requieren el uso explícito de recursión, por ejemplo, utilizando $\operatorname {Y}$ Combinador o definiciones de autoaplicación explícitas. Un ejemplo de ello es foldr , a diferencia de la operación nula que representa bajo la codificación Church. Sin embargo, tail está disponible de inmediato, por lo que su definición es mucho más sencilla en este caso. Consulte la codificación Scott para obtener más información.

La codificación Scott puede considerarse como el uso de la idea de continuaciones , lo que puede conducir a un código más simple ^{[ 9 ]} . En este enfoque, utilizamos el hecho de que las listas pueden observarse mediante expresiones de coincidencia de patrones . Por ejemplo, utilizando la notación de Scala , si listdenota un valor de tipo Listcon una lista vacía Nily un constructor, Cons(h, t)podemos inspeccionar la lista y calcular nilCodeen caso de que la lista esté vacía y consCode(h, t)cuando la lista no esté vacía:

lista coincidencia { caso Nil => nilCode caso Cons ( h , t ) => consCode ( h , t ) }

El listvalor viene dado por cómo actúa sobre nilCodey consCode. Por lo tanto, definimos una lista como una función que acepta tales nilCodey consCodecomo argumentos, de modo que en lugar de la coincidencia de patrones anterior podemos simplemente escribir:

\operatorname {list} \ \operatorname {nilCode} \ \operatorname {consCode}

Denotemos por nel parámetro correspondiente a nilCodey por cel parámetro correspondiente a consCode. La lista vacía es entonces la que devuelve el argumento nulo:

\operatorname {nil} \equiv \lambda n.\lambda c.\ n

La lista no vacía con cabeza hy cola tviene dada por

\operatorname {cons} \ h\ t\ \equiv \ \lambda n.\lambda c.c\ h\ t

De forma más general, un tipo de datos algebraicos con $m$ Las alternativas se convierten en una función con $m$ parámetros, cada uno de los cuales es una función observadora/manejadora para su alternativa correspondiente. Cuando el $i$ El constructor de la alternativa tiene $n_{i}$ argumentos, la función controladora correspondiente toma $n_{i}$ argumentos también.

La codificación de Scott se puede realizar en el cálculo lambda sin tipos, mientras que su uso con tipos requiere un sistema de tipos con recursión y polimorfismo de tipos. Una lista con tipo de elemento E en esta representación que se utiliza para calcular valores de tipo C tendría la siguiente definición de tipo recursiva, donde '=>' denota el tipo de función :

tipo Lista = C => // argumento nulo ( E => Lista => C ) => // argumento cons C // resultado de la coincidencia de patrones

Una lista que se puede usar para calcular tipos arbitrarios tendría un tipo que cuantifica sobre C. Una lista genérica en Etambién tomaría Ecomo argumento de tipo.

Observaciones generales

Una implementación sencilla de la codificación de Church ralentiza algunas operaciones de acceso. $O(1)$ a $O(n)$ , dónde $n$ es el tamaño de la estructura de datos , lo que hace que la codificación de Church sea impracticable. ^{[ 10 ]} La investigación ha demostrado que esto puede abordarse mediante optimizaciones dirigidas, pero la mayoría de los lenguajes de programación funcional en su lugar expanden sus representaciones intermedias para contener tipos de datos algebraicos . ^{[ 11 ]} No obstante, la codificación de Church se usa a menudo en argumentos teóricos, ya que es una representación natural para la evaluación parcial y la demostración de teoremas. ^{[ 10 ]} Las operaciones pueden tipificarse usando tipos de rango superior , ^{[ 12 ]} y la recursión primitiva es fácilmente accesible. ^{[ 10 ]} La suposición de que las funciones son los únicos tipos de datos primitivos simplifica muchas demostraciones.

La codificación de Church es completa, pero solo representacionalmente. Se necesitan funciones adicionales para traducir la representación a tipos de datos comunes, para su visualización. En general, no es posible determinar si dos funciones son extensionalmente iguales debido a la indecidibilidad de la equivalencia según el teorema de Church . La traducción puede aplicar la función de alguna manera para recuperar el valor que representa, o buscar su valor como un término lambda literal. El cálculo lambda se suele interpretar como el uso de la igualdad intensional . Existen posibles problemas con la interpretación de los resultados debido a la diferencia entre la definición intensional y la extensional de igualdad.

Véase también

Cálculo lambda
Sistema F para numerales de Church en un cálculo mecanografiado
Codificación de Mogensen-Scott
Definición de ordinales de Von Neumann : otra forma de codificar los números naturales: como conjuntos.

Referencias

↑ Jansen, Jan Martin (2013), "Programación en el cálculo λ: de Church a Scott y viceversa", The Beauty of Functional Code , Lecture Notes in Computer Science, vol. 8106, Springer-Verlag, pp. 168–180 , doi : 10.1007/978-3-642-40355-2_12 , ISBN 978-3-642-40354-5.
↑ Dan Doel ( https://math.stackexchange.com/users/590896/dan-doel ), ¿ Tetración de los numerales de Church? , URL (versión: 2026-02-27): https://math.stackexchange.com/q/4601054
↑ Allison, Lloyd. "Cálculo Lambda de Enteros" .
↑ Bauer, Andrej. "Respuesta de Andrej a una pregunta: "Representación de números negativos y complejos mediante el cálculo lambda"" .
↑ "Aritmética real exacta" . Haskell . Archivado del original el 26 de marzo de 2015.
↑ Bauer, Andrej (26 de septiembre de 2022). "Software de cálculo de números reales" . GitHub .
↑ Pierce, Benjamin C. (2002). Tipos y lenguajes de programación . MIT Press . pág. 500. ISBN 978-0-262-16209-8.
↑ Tromp, John (2007). "14. Cálculo lambda binario y lógica combinatoria" . En Calude, Cristian S (ed.). Aleatoriedad y complejidad, de Leibniz a Chaitin . World Scientific. pp. 237–262 . ISBN 978-981-4474-39-9.Como PDF: Tromp, John (14 de mayo de 2014). "Cálculo lambda binario y lógica combinatoria" (PDF) . Recuperado el 24 de noviembre de 2017 .
↑ Jansen, Jan Martin (2013). "Programación en el cálculo lambda: De Church a Scott y viceversa". En Achten, Peter; Koopman, Pieter WM (eds.). La belleza del código funcional: ensayos dedicados a Rinus Plasmeijer con motivo de su 61.º cumpleaños . Lecture Notes in Computer Science. Vol. 8106. Springer. pp. 168–180 . doi : 10.1007/978-3-642-40355-2_12 . ISBN 978-3-642-40354-5.
1 2 3 Trancón y Widemann, Baltasar; Parnas, David Lorge (2008). "Expresiones tabulares y programación funcional total". En Olaf Chitil; Zoltán Horváth; Viktória Zsók (eds.). Implementación y aplicación de lenguajes funcionales . 19.º Taller Internacional, IFL 2007, Friburgo, Alemania, 27-29 de septiembre de 2007. Artículos seleccionados revisados. Lecture Notes in Computer Science. Vol. 5083. pp. 228-229 . doi : 10.1007/978-3-540-85373-2_13 . ISBN 978-3-540-85372-5.
↑ Jansen, Jan Martin; Koopman, Pieter WM; Plasmeijer, Marinus J. (2006). "Interpretación eficiente mediante la transformación de tipos de datos y patrones en funciones". En Nilsson, Henrik (ed.). Tendencias en programación funcional. Volumen 7. Bristol: Intellect. pp. 73–90 . CiteSeerX 10.1.1.73.9841 . ISBN 978-1-84150-188-8.
↑ "Los predecesores y las listas no son representables en el cálculo lambda simplemente tipado" . Cálculo lambda y calculadoras lambda . okmij.org.

Stump, A. (2009). "Metaprogramación directamente reflexiva" (PDF) . High-Order Symb Comput . 22 (2): 115– 144. CiteSeerX 10.1.1.489.5018 . doi : 10.1007/s10990-007-9022-0 . S2CID 16124152 .
Cartwright, Robert. "Números eclesiásticos y booleanos explicados" (PDF) . Comp 311 — Revisión 2. Universidad Rice .
Kemp, Colin (2007). "§2.4.1 Church Naturals, §2.4.2 Church Booleans, Cap. 5 Técnicas de derivación para TFP" . Fundamentos teóricos para la 'programación totalmente funcional' práctica.(PhD). Escuela de Tecnología de la Información e Ingeniería Eléctrica, Universidad de Queensland. pp. 14–17 , 93–145 . CiteSeerX 10.1.1.149.3505 . Todo sobre la Iglesia y otras codificaciones similares, incluyendo cómo derivarlas y las operaciones que se realizan sobre ellas, desde los primeros principios.
Algunos ejemplos interactivos de numerales eclesiásticos
Tutorial en vivo de cálculo lambda: álgebra booleana

[ce-3] 1 2 En la codificación de la Iglesia,
$\operatorname {pred} (0)=0$
$m\leq n\to m-n=0$

[mwAWA] $\operatorname {pred} (0)=0$

[mwAXA] $m\leq n\to m-n=0$

[1] Jansen, Jan Martin (2013), "Programación en el cálculo λ: de Church a Scott y viceversa", The Beauty of Functional Code , Lecture Notes in Computer Science, vol. 8106, Springer-Verlag, pp. 168–180 , doi : 10.1007/978-3-642-40355-2_12 , ISBN 978-3-642-40354-5.

[2] Dan Doel ( https://math.stackexchange.com/users/590896/dan-doel ), ¿ Tetración de los numerales de Church? , URL (versión: 2026-02-27): https://math.stackexchange.com/q/4601054

[4] Allison, Lloyd. "Cálculo Lambda de Enteros" .

[5] Bauer, Andrej. "Respuesta de Andrej a una pregunta: "Representación de números negativos y complejos mediante el cálculo lambda"" .

[6] "Aritmética real exacta" . Haskell . Archivado del original el 26 de marzo de 2015.

[7] Bauer, Andrej (26 de septiembre de 2022). "Software de cálculo de números reales" . GitHub .

[8] Pierce, Benjamin C. (2002). Tipos y lenguajes de programación . MIT Press . pág. 500. ISBN 978-0-262-16209-8.

[9] Tromp, John (2007). "14. Cálculo lambda binario y lógica combinatoria" . En Calude, Cristian S (ed.). Aleatoriedad y complejidad, de Leibniz a Chaitin . World Scientific. pp. 237–262 . ISBN 978-981-4474-39-9.Como PDF: Tromp, John (14 de mayo de 2014). "Cálculo lambda binario y lógica combinatoria" (PDF) . Recuperado el 24 de noviembre de 2017 .

[10] Jansen, Jan Martin (2013). "Programación en el cálculo lambda: De Church a Scott y viceversa". En Achten, Peter; Koopman, Pieter WM (eds.). La belleza del código funcional: ensayos dedicados a Rinus Plasmeijer con motivo de su 61.º cumpleaños . Lecture Notes in Computer Science. Vol. 8106. Springer. pp. 168–180 . doi : 10.1007/978-3-642-40355-2_12 . ISBN 978-3-642-40354-5.

[Widemann-11] 1 2 3 Trancón y Widemann, Baltasar; Parnas, David Lorge (2008). "Expresiones tabulares y programación funcional total". En Olaf Chitil; Zoltán Horváth; Viktória Zsók (eds.). Implementación y aplicación de lenguajes funcionales . 19.º Taller Internacional, IFL 2007, Friburgo, Alemania, 27-29 de septiembre de 2007. Artículos seleccionados revisados. Lecture Notes in Computer Science. Vol. 5083. pp. 228-229 . doi : 10.1007/978-3-540-85373-2_13 . ISBN 978-3-540-85372-5.

[12] Jansen, Jan Martin; Koopman, Pieter WM; Plasmeijer, Marinus J. (2006). "Interpretación eficiente mediante la transformación de tipos de datos y patrones en funciones". En Nilsson, Henrik (ed.). Tendencias en programación funcional. Volumen 7. Bristol: Intellect. pp. 73–90 . CiteSeerX 10.1.1.73.9841 . ISBN 978-1-84150-188-8.

[13] "Los predecesores y las listas no son representables en el cálculo lambda simplemente tipado" . Cálculo lambda y calculadoras lambda . okmij.org.

[ 1 ]

[ 2 ]

[ 3 ].

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]