Cálculo combinador SKI

El cálculo combinatorio SKI es un sistema de lógica combinatoria y un sistema computacional . Puede considerarse un lenguaje de programación informática, aunque no es conveniente para escribir software. En cambio, es importante en la teoría matemática de algoritmos porque es un lenguaje completo de Turing extremadamente simple . Puede compararse con una versión reducida del cálculo lambda sin tipo . Fue introducido por Moses Schönfinkel ^[1] y Haskell Curry ^[2] .

Todas las operaciones del cálculo lambda se pueden codificar mediante eliminación de abstracción en el cálculo SKI como árboles binarios cuyas hojas son uno de los tres símbolos S , K e I (llamados combinadores ).

Notación

Aunque la representación más formal de los objetos en este sistema requiere árboles binarios, para una composición tipográfica más sencilla, a menudo se representan como expresiones entre paréntesis, como una abreviatura del árbol que representan. Cualquier subárbol puede estar entre paréntesis, pero a menudo solo se incluyen entre paréntesis los subárboles del lado derecho, con la asociatividad izquierda implícita para cualquier aplicación sin paréntesis. Por ejemplo, ISK significa (( IS ) K ). Usando esta notación, un árbol cuyo subárbol izquierdo es el árbol KS y cuyo subárbol derecho es el árbol SK se puede escribir como KS ( SK ). Si se desea más explicitud, también se pueden incluir los paréntesis implícitos: (( KS )( SK )).

Descripción informal

De manera informal, y utilizando la jerga de los lenguajes de programación, un árbol ( xy ) puede considerarse como una función x aplicada a un argumento y . Cuando se evalúa ( es decir , cuando la función se "aplica" al argumento), el árbol "devuelve un valor", es decir , se transforma en otro árbol. La "función", el "argumento" y el "valor" son combinadores o árboles binarios. Si son árboles binarios, también pueden considerarse funciones, si es necesario.

La operación de evaluación se define de la siguiente manera:

( x , y y z representan expresiones formadas a partir de las funciones S , K e I , y establecen valores):

Devuelvo su argumento:

Yo x = x

K , cuando se aplica a cualquier argumento x , produce una función constante de un argumento K x , que, cuando se aplica a cualquier argumento y , devuelve x :

Kxy = x

S es un operador de sustitución. Toma tres argumentos y luego devuelve el primer argumento aplicado al tercero, que luego se aplica al resultado del segundo argumento aplicado al tercero. Más claramente:

Sxyz = xz ( yz )

Ejemplo de cálculo: SKSK se evalúa como KK ( SK ) según la regla S. Luego, si evaluamos KK ( SK ), obtenemos K según la regla K. Como no se puede aplicar ninguna otra regla, el cálculo se detiene aquí.

Para todos los árboles x y todos los árboles y , SK xy siempre se evaluará como y en dos pasos, K y ( xy ) = y , por lo que el resultado final de evaluar SK xy siempre será igual al resultado de evaluar y . Decimos que SK x e I son "funcionalmente equivalentes" para cualquier x porque siempre arrojan el mismo resultado cuando se aplican a cualquier y .

A partir de estas definiciones se puede demostrar que el cálculo SKI no es el sistema mínimo que puede realizar completamente los cálculos del cálculo lambda, ya que todas las apariciones de I en cualquier expresión se pueden reemplazar por ( SKK ) o ( SKS ) o ( SK x ) para cualquier x , y la expresión resultante arrojará el mismo resultado. Por lo tanto, la " I " es simplemente azúcar sintáctico . Dado que I es opcional, el sistema también se conoce como cálculo SK o cálculo combinatorio SK .

Es posible definir un sistema completo utilizando un único combinador (impropio). Un ejemplo es el combinador iota de Chris Barker , que se puede expresar en términos de S y K de la siguiente manera:

ι x = x SK

Es posible reconstruir S , K e I a partir del combinador iota. Al aplicar ι a sí mismo se obtiene ιι = ι SK = SSKK = SK ( KK ) que es funcionalmente equivalente a I . K se puede construir al aplicar ι dos veces a I (lo que es equivalente a la aplicación de ι a sí mismo): ι(ι(ιι)) = ι(ιι SK ) = ι( ISK ) = ι( SK ) = SKSK = K . Al aplicar ι una vez más se obtiene ι(ι(ι(ιι))) = ι K = KSK = S .

El término más simple posible que forma una base es X = λf.f λxyz.xz (yz) λxyz.x, que satisface XX = K y X (XX) = S.

Definición formal

Los términos y derivaciones de este sistema también pueden definirse de manera más formal:

Términos : El conjunto T de términos se define recursivamente mediante las siguientes reglas.

S , K e I son términos.
Si τ ₁ y τ ₂ son términos, entonces (τ ₁ τ ₂ ) es un término.
Nada es un término si no está obligado a serlo según las dos primeras reglas.

Derivaciones : Una derivación es una secuencia finita de términos definidos recursivamente por las siguientes reglas (donde α e ι son palabras del alfabeto { S , K , I , (, )} mientras que β, γ y δ son términos):

Si Δ es una derivación que termina en una expresión de la forma α( I β)ι, entonces Δ seguido del término αβι es una derivación.
Si Δ es una derivación que termina en una expresión de la forma α(( K β)γ)ι, entonces Δ seguido del término αβι es una derivación.
Si Δ es una derivación que termina en una expresión de la forma α((( S β)γ)δ)ι, entonces Δ seguido del término α((βδ)(γδ))ι es una derivación.

Suponiendo que una secuencia es una derivación válida desde el principio, se puede extender utilizando estas reglas. Todas las derivaciones de longitud 1 son derivaciones válidas.

Expresiones de esquí

Autoaplicación y recursión

SII es una expresión que toma un argumento y aplica ese argumento a sí mismo:

SII α = I α( I α) = αα

También se lo conoce como combinador U , U x = xx . Una propiedad interesante de este es que su autoaplicación es irreducible:

SII ( SII ) = I ( SII )( I ( SII )) = SII ( I ( SII ) ) = SII ( SII )

O, utilizando la ecuación como su definición directamente, obtenemos inmediatamente U U = U U .

Otra cosa es que permite escribir una función que aplica una cosa a la autoaplicación de otra cosa:

( S ( K α)( SII ))β = K αβ( SII β) = α( I β( I β)) = α(ββ)

o puede verse como la definición directa de otro combinador, H xy = x ( yy ).

Esta función se puede utilizar para lograr la recursión . Si β es la función que aplica α a la autoaplicación de algo más,

β = H α = S ( K α)( SII )

entonces la autoaplicación de este β es el punto fijo de ese α:

SII β = ββ = α(ββ) = α(α(ββ)) =

\ldots

O, directamente de nuevo de la definición derivada, H α( H α) = α( H α( H α)).

Si α expresa un "paso computacional" calculado por αρν para algún ρ y ν, que supone que ρν' expresa "el resto del cálculo" (para algún ν' que α "calculará" a partir de ν), entonces su punto fijo ββ expresa todo el cálculo recursivo, ya que usar la misma función ββ para la llamada al "resto del cálculo" (con ββν = α(ββ)ν) es la definición misma de recursión: ρν' = ββν' = α(ββ)ν' = ... . α tendrá que emplear algún tipo de condicional para detenerse en algún "caso base" y no hacer la llamada recursiva entonces, para evitar la divergencia.

Esto se puede formalizar con

β = H α = S ( K α)( SII ) = S ( KS ) K α( SII ) = S ( S ( KS ) K )( K ( SII )) α

como

Y α = SII β = SII ( H α) = S ( K ( SII )) H α = S ( K ( SII ))( S ( S ( KS ) K )( K ( SII ))) α

lo que nos da una posible codificación del combinador Y. Una variación más corta reemplaza sus dos subtérminos principales solo con SSI , ya que H α( H α) = SHH α = SSIH α.

Esto se vuelve mucho más corto con el uso de los combinadores B, C, W , como equivalente

Y α = S ( KU )( SB ( KU ))α = U ( B α U ) = BU ( CBU )α = SSI ( CBU )α

Y con una sintaxis pseudo- Haskell se convierte en el excepcionalmente corto Y = U . (. U ).

Siguiendo este enfoque, son posibles otras definiciones de combinadores de puntos fijos, como

H gh = g ( hgh ); Y g = H g H

H hg = g ( hhg ); Y g = HH g

H algo = g ( halgo ); Y g = H _____ H __ g

o cualquier otra definición del combinador H intermediario (donde vale cualquier cosa en lugar de "_"), con su definición Y correspondiente para ponerlo en marcha correctamente.

La expresión de inversión

S ( K ( SI )) K invierte los dos términos que le siguen:

S ( K ( SI )) K αβ →

K ( SI )α( K α)β →

SI ( Kα )β →

Yo β( K αβ) →

Yo βα →

βα

Por lo tanto, es equivalente a CI . Y en general, S ( K ( S f )) K es equivalente a C f , para cualquier f .

Lógica booleana

El cálculo combinador SKI también puede implementar la lógica booleana en forma de una estructura if-then-else . Una estructura if-then-else consiste en una expresión booleana que es verdadera ( T ) o falsa ( F ) y dos argumentos, tales que:

Txy = x

Fxy = y

La clave está en definir las dos expresiones booleanas. La primera funciona como uno de nuestros combinadores básicos:

T = K

Kxy = x

El segundo también es bastante simple:

F = SK

SK xy = K y(xy) = y

Una vez definidos verdadero y falso, toda la lógica booleana se puede implementar en términos de estructuras if-then-else .

El NOT booleano (que devuelve el opuesto de un booleano dado) funciona de la misma manera que la estructura if-then-else , con F y T como segundo y tercer valor, por lo que se puede implementar como una operación de sufijo:

NO = λb.b ( F )( T ) = λb.b ( SK )( K )

Si esto se coloca en una estructura if-then-else , se puede demostrar que tiene el resultado esperado.

( T ) NO = T ( F )( T ) = F

( F ) NO = F ( F )( T ) = T

El OR booleano (que devuelve T si cualquiera de los dos valores booleanos que lo rodean es T ) funciona de la misma manera que una estructura if-then-else con T como segundo valor, por lo que se puede implementar como una operación infija:

O = T = K

Si esto se coloca en una estructura if-then-else , se puede demostrar que tiene el resultado esperado:

( T ) O ( T ) = T ( T )( T ) = T

( T ) O ( F ) = T ( T )( F ) = T

( F ) O ( T ) = F ( T )( T ) = T

( F ) O ( F ) = F ( T )( F ) = F

El operador booleano AND (que devuelve T si ambos valores booleanos que lo rodean son T ) funciona de la misma manera que una estructura if-then-else con F como tercer valor, por lo que se puede implementar como una operación de sufijo:

Y = F = SK

Si esto se coloca en una estructura if-then-else , se puede demostrar que tiene el resultado esperado:

( T )( T ) Y = T ( T )( F ) = T

( T )( F ) Y = T ( F )( F ) = F

( F )( T ) Y = F ( T )( F ) = F

( F )( F ) Y = F ( F )( F ) = F

Dado que esto define T , F , NOT (como un operador postfijo), OR (como un operador infijo) y AND (como un operador postfijo) en términos de notación SKI, esto demuestra que el sistema SKI puede expresar completamente la lógica booleana.

Como el cálculo SKI está completo , también es posible expresar NOT , OR y AND como operadores de prefijo:

NO = S ( SI ( KF ))( KT ) (como S ( SI ( KF ))( KT ) x = SI ( KF ) x ( KT x ) = I x ( KF x ) T = x FT )

OR = SI ( KT ) (como SI ( KT ) xy = I x ( KT x ) y = x T y )

Y = SS ( K ( KF )) (como SS ( K ( KF )) xy = S x ( K ( KF ) x ) y = xy ( KF y ) = xy F )

Conexión con la lógica intuicionista

Los combinadores K y S corresponden a dos axiomas bien conocidos de la lógica sentencial :

AK : A \to (B \to A)

COMO : (A \to (B \to C)) \to ((A \to B) \to (A \to C))

La aplicación de la función corresponde a la regla modus ponens :

MP

: deA

y

\to B,

inferir

B.

Los axiomas AK y AS y la regla MP son completos para el fragmento implicacional de la lógica intuicionista . Para que la lógica combinatoria tenga como modelo:

El fragmento implicacional de la lógica clásica , requeriría el análogo combinatorio de la ley del medio excluido , es decir , la ley de Peirce ;
La lógica clásica completa requeriría el análogo combinatorio del axioma sentencial $F \to A.$

Esta conexión entre los tipos de combinadores y los axiomas lógicos correspondientes es un ejemplo del isomorfismo de Curry-Howard .

Ejemplos de reducción

Puede haber varias formas de hacer una reducción. Todas son equivalentes, siempre que no se altere el orden de las operaciones.

${\textrm {ESQUÍ(KIS)}}$
- ${\textrm {ESQUÍ(ESC)}}\Rightarrow {\textrm {K(ESC)(I(ESC))}}\Rightarrow {\textrm {ESC}}\Rightarrow {\textrm {I}}$
- ${\textrm {ESQUÍ(KI)}}\Flecha derecha {\textrm {ESQUÍII}}\Flecha derecha {\textrm {KI(II)}}\Flecha derecha {\textrm {KII}}\Flecha derecha {\textrm {I}}$
${\textrm {KS(I(SKSI))}}$
- ${\textrm {KS(I(SKSI))}}\Flecha derecha {\textrm {KS(I(KI(SI)))}}\Flecha derecha {\textrm {KS(I(I))}}\Flecha derecha {\textrm {KS(II)}}\Flecha derecha {\textrm {KSI}}\Flecha derecha {\textrm {S}}$
- ${\textrm {KS(I(SKSI))}}\Rightarrow {\textrm {S}}$
${\textrm {SKIK}}\Rightarrow {\textrm {KK(IK)}}\Rightarrow {\textrm {KKK}}\Rightarrow {\textrm {K}}$

Véase también

Lógica combinatoria
Sistema B, C, K, W
Combinador de punto fijo
Cálculo lambda
Programación funcional
Lenguaje de programación Unlambda
Los lenguajes de programación Iota y Jot , diseñados para ser incluso más simples que SKI.
Burlarse de un ruiseñor

Referencias

^ Schönfinkel, M. (1924). "Über die Bausteine der mathematischen Logik". Annalen Matemáticas . 92 (3–4): 305–316. doi :10.1007/BF01448013. S2CID 118507515.Traducido por Stefan Bauer-Mengelberg como van Heijenoort, Jean , ed. (2002) [1967]. "Sobre los elementos básicos de la lógica matemática". Un libro de consulta sobre lógica matemática 1879-1931 . Harvard University Press. págs. 355-366. ISBN 9780674324497.
^ Curry, Haskell Brooks (1930). "Grundlagen der Kombinatorischen Logik" [Fundamentos de la lógica combinatoria]. American Journal of Mathematics (en alemán). 52 (3). Johns Hopkins University Press: 509–536. doi :10.2307/2370619. JSTOR 2370619.

Smullyan, Raymond (1985). Burlarse de un ruiseñor . Knopf. ISBN 0-394-53491-3.Una introducción suave a la lógica combinatoria, presentada como una serie de rompecabezas recreativos que utilizan metáforas de observación de aves.
— (1994). "Cap. 17-20". Diagonalización y autorreferencia . Oxford University Press. ISBN 9780198534501.OCLC 473553893 .Son una introducción más formal a la lógica combinatoria, con un énfasis especial en los resultados de punto fijo.

Enlaces externos

O'Donnell, Mike "El cálculo combinatorio SKI como sistema universal".
Keenan, David C. (2001) "Diseccionar un ruiseñor".
Rathman, Chris, "Aves combinadoras".
"Combinadores de arrastrar y soltar (subprograma Java)"
Un cálculo de procesos móviles, parte I (PostScript) (por Milner, Parrow y Walker) muestra un esquema para la reducción de gráficos combinadores para el cálculo SKI en las páginas 25-28.
El lenguaje de programación Nock puede considerarse un lenguaje ensamblador basado en el cálculo combinador SK, de la misma manera que el lenguaje ensamblador tradicional se basa en las máquinas de Turing. La instrucción Nock 2 (el "operador Nock") es el combinador S y la instrucción Nock 1 es el combinador K. Las otras instrucciones primitivas de Nock (las instrucciones 0, 3, 4, 5 y la pseudoinstrucción "cons implícito") no son necesarias para el cálculo universal, pero hacen que la programación sea más conveniente al proporcionar facilidades para tratar con estructuras de datos de árboles binarios y aritmética; Nock también proporciona 5 instrucciones más (6, 7, 8, 9, 10) que podrían haberse construido a partir de estas primitivas.