¿Lógica combinatoria simplemente escrita?

8

Como hay un cálculo lambda sin tipo y un cálculo lambda de tipo simple (como se describe, por ejemplo, en el libro Tipos y lenguajes de programación de Benjamin Pierce), ¿existe una lógica combinatoria de tipo simple?

Por ejemplo, parecería que los tipos naturales para los combinadores S, K y yo serían

S : (a -> b -> c) -> (a -> b) -> a -> c
K : a -> b -> a
I : a -> a

donde a, byc son variables de tipo que se extienden sobre un conjunto de tipos T. Ahora, quizás podríamos comenzar con un solo tipo base, Bool. Nuestro conjunto de tipos T es Bool junto con cualquier tipo que se pueda formar usando los tres patrones

(a -> b -> c) -> (a -> b) -> a -> c
a -> b -> a
a -> a

donde a, b, c en T.

Habría dos constantes nuevas en el idioma.

T : Bool
F : Bool

Entonces, este lenguaje consiste en los símbolos S, K, I, T y F, junto con paréntesis. Tiene un tipo base Bool, y los "tipos de función" que se pueden hacer a partir de los patrones de combinador S, K e I.

¿Se puede hacer que este sistema funcione? Por ejemplo, ¿hay una construcción de tipo si-entonces-otro bien tipada que se pueda formar solo con S, K, I, T, F?

Rodrigo de Azevedo
fuente
Búsqueda "álgebra combinatoria mecanografiada".
Andrej Bauer
Curiosamente, la lógica combinatoria mecanografiada es donde se notó por primera vez la correspondencia mal llamada "Curry-Howard", debido a la similitud con los axiomas lógicos de estilo Hilbert: en.wikipedia.org/wiki/Hilbert_system#Logical_axioms
cody

Respuestas:

11

Nota rápida, que permita que el polimorfismo paramétrico (Sistema F) en este sistema para que S, Ky Ipuede trabajar sobre todo tipo.

Tenga en cuenta que sin la coincidencia de patrones, no podemos escribir un ifno importa lo que hagamos. No tenemos absolutamente ninguna operación en booleanos. No hay forma de distinguir Truede False. En su lugar, intente

true : a -> a -> a
true = \t -> \f -> t

false : a -> a -> a
false = \t -> \f -> f

Dejemos la Bool = a -> a -> aclaridad.

 if : Bool -> a -> a -> a
 if = \bool -> \a -> \b -> bool a b

Ahora es solo cuestión de compilar algunas expresiones de cálculo lambda en combinadores, lo cual es bastante trivial.

if : Bool -> a -> a -> a -- Or just Bool -> Bool
if    = I

true : a -> a -> a
true  = K

false : a -> a -> a
false = K I
Daniel Gratzer
fuente