¿Son iguales el cálculo lambda y la lógica combinatoria?

Actualmente estoy leyendo " Cálculo Lambda y Combinadores " de Hindley y Seldin. No soy un experto, pero siempre me ha interesado el cálculo lambda debido a su participación en la programación funcional (comenzando con Lisp y SICP, y ahora con R y Haskell).

En " Cálculo binario lambda y lógica combinatoria" , John Tromp afirma:

CL puede verse como un subconjunto de cálculo lambda ... las teorías son en gran medida las mismas, llegando a ser equivalentes en presencia de la regla de la extensionalidad.

¿Bajo qué condiciones se usaría la lógica combinatoria en lugar del cálculo lambda ?

Cualquier referencia sería apreciada.

combinatory-logic functional-programming lambda-calculus Shane
fuente

Echa un vistazo a "Cálculo Lambda: su sintaxis y semántica" por HP Barendregt.

Kaveh

Respuestas:

Lo que distingue la lógica combinatoria es que es libre de variables. Esto a veces es útil en metamatemáticas y lógica filosófica, donde el estado de las variables es complicado.

También puede ser útil en implementaciones, ya que administrar variables puede ser un dolor de cabeza. Cf., por ejemplo, Hughes, 1982, Supercombinadores: un nuevo método de implementación para lenguajes aplicativos

Charles Stewart
fuente

La lógica combinatoria ya no se considera útil en las implementaciones, y nunca se usó porque "administrar variables puede ser un dolor de cabeza". Se usaron combinadores y variantes para implementar la reducción de gráficos para lenguajes perezosos, pero hoy en día Haskell (el lenguaje perezoso más destacado) utiliza técnicas mucho más razonables para implementar la reducción de gráficos.

Blaisorblade

Véase, por ejemplo, S. Peyton Jones, 1992, "Implementación de lenguajes funcionales perezosos en hardware estándar: la máquina G sin etiqueta sin espinas" - research.microsoft.com/copyright/accept.asp?path=/users/simonpj/…

Blaisorblade

@Blaisorblade: se usaron combinadores y variantes para implementar la reducción de gráficos para lenguajes perezosos . Tenga cuidado: Haskell y ghc no son lo mismo, y la literatura contiene varios Haskells basados en supercombinator. Pero es cierto, lo último en programación funcional ha encontrado las ventajas de eficiencia de manejar entornos que superan su complejidad. Todavía se ven supercombinadores utilizados, por ejemplo, en la programación lógica de orden superior, donde esto no es cierto. Los supercombinatores siguen siendo parte del inventario de técnicas utilizadas en la implementación de la programación de orden superior.

Charles Stewart

Los supercombinatores evitan solo las variables libres, no las unidas, por lo que en mi humilde opinión, no pueden considerarse usos de la lógica combinatoria per se. En su mayoría son términos lambda especiales. Hay diferencias mucho más pequeñas entre los supercombinatores, los programas lambda-lifted (si hay alguno, no estoy seguro) y la implementación de GHC (donde los punteros de un cierre a sus variables libres se pueden copiar de la función host, gracias a la pureza). Dicho esto, también estaba pensando en el reciente compilador de Utrecht Haskell, que es muy similar a GHC, pero el IIRC utiliza levantamiento de lambda; Aún así, eso no es CL.

Blaisorblade

No conocía la programación lógica de orden superior: encontré este documento: springerlink.com/content/t68777w270713p5n . Desafortunadamente, es poco probable que tenga tiempo de leerlo.

Blaisorblade

En referencia al comentario de John Tromp, quiero comentar que la lógica combinatoria se siente muy diferente del cálculo lambda. Dado que su interés proviene de la programación funcional, realmente no desea saber mucho sobre lógica combinatoria.

Mi tutorial favorito sobre lógica combinatoria se encuentra en estas notas de la Universidad de Cambridge.

Sin embargo, se presentan para explicar la implementación de los llamados lenguajes perezosos (o aplicativos); Como se mencionó en mi comentario anterior, tales técnicas ahora están desactualizadas.

Blaisorblade
fuente

Dado que los lenguajes combinatorios ya no se usan para implementar lenguajes perezosos / aplicativos, ¿cuáles son las técnicas más modernas ahora? ¿Y hay un nombre / categoría para clasificar estas técnicas?

CMCDragonkai

@CMCDragonkai Vea los comentarios a cstheory.stackexchange.com/a/306/989 para su discusión. La respuesta práctica breve es "ver documentos sobre lo que hace GHC": hay una variedad de técnicas diferentes (que incluyen tanto la máquina STG como optimizaciones como el análisis de rigor) que se combinan para hacer que los programas perezosos sean rápidos.

Blaisorblade