LOGICA COMBINATORIA

La lógica combinatoria es la lógica última y como tal puede ser un modelo simplificado del cómputo, usado en la teoría de computabilidad (el estudio de qué puede ser computado) y la teoría de la prueba (el estudio de qué se puede probar matemáticamente.)

La teoría, a causa de su simplicidad, captura las características esenciales de la naturaleza del cómputo. La lógica combinatoria (LC) es el fundamento del cálculo lambda, al eliminar el último tipo de variable de éste: la variable lambda. En LC las expresiones lambda (usadas para permitir la abstracción funcional) son substituidas por un sistema limitado de combinadores, las funciones primitivas que no contienen ninguna variable libre (ni ligada). Es fácil transformar expresiones lambda en expresiones combinatorias, y puesto que la reducción de un combinador es más simple que la reducción lambda, LC se ha utilizado como la base para la puesta en práctica de algunos lenguajes de programación funcionales no-estrictos en software y hardware.

Una de las propiedades fundamentales del !-c´alculus es la completitud combinatoria:
Teorema 3.1.1. Dado un !-t´ermino arbitrario conteniendo alguna variable libre, denotado como1
M("x), es posible construir un nuevo t´ermino F con la propiedad:
F"x = M("x)
Esta propiedad es denominada completitud combinatoria. Hay un candidato obvio para F, cual es:
!"x.M
No obstante, m´as notable a´un es que F pueda ser construido usando los dos combinadores S y K
y aplicaciones (es decir, no hay ninguna necesidad de la abstraci´on). La teor´ıa que desarrolla la
anterior aproximaci´on es la L´ogica Combinatoria.
La L´ogica Combinatoria fue inventada por Sch¨onfinkel en 1924 e independientemente por Curry
en 1930. La notaci´on que usamos en nuestra presentaci´on de la teor´ıa de combinadores se debe a
1Esta notaci´on deber´ıa ser le´ıda como “FV (M) es un subconjunto de !x ”.Curry. La teor´ıa de combinadores es m´as temprana que el m´as temprano trabajo sobre !-calculus
que fue introducido por Curry en 1932. Nuestro ´enfasis mostrado en el !-calculus est´a motivado por
el hecho de que la !-notaci´on es una notaci´on de “m´as alto nivel” que la de los combinadores; los
t´erminos combinatorios parecen programas de un lenguaje ensamblador. Esta ´ultima observaci´on
se refleja en el uso que las Ciencias de la Computaci´on han hecho de las dos teor´ıas: el !-calculus
es a veces descrito como el lenguaje de programaci´on funcional can´onico, mientras que ning´un
lenguaje de alto nivel emplea una notaci´on basada en los combinadores (de bajo nivel/grano fino)
de la L´ogica Combinatoria; alguna de las implementaciones pioneras estuvieron basadas en la reducci
´on de combinadores. Desde el punto de vista de la implementaci´on de un lenguaje, uno de los
atractivos de los t´erminos combinatorios es que no hay ninguna acotaci´on de variables y, consecuentemente,
el papel del entorno (cfr. Cap´ıtulo 8) disminuye: esto tiene importantes implicaciones
para las implementaciones distribuidas en las cuales el acceso a un entorno puede suponer un gran
embotellamiento. La clase de los t´erminos combinatorios es definida como sigue:
KPQ = P
SPQR = PR(QR)

P = P
P = Q
Q = P
P =Q Q= R
P = R
P = P!
PR = P!R
P = P!
RP = RP!