Por lo tanto, existe un algoritmo para convertir los términos de cálculo lambda en lógica combinatoria utilizando los combinadores SK. Produce cosas que explotan en tamaño. Me gustaría saber más sobre esta explosión de tamaño. Sin embargo, no puedo pensar en un algoritmo mejor. He oído hablar de lenguajes funcionales que se compilan prácticamente para combinadores, por lo que parece que debe existir un mejor algoritmo. Busqué el artículo de David Turner sobre el tema y él básicamente dice que aplique algunas optimizaciones y que causen una "mejora considerable".
¿Significa "mejora considerable" que el tamaño se reduce a solo un aumento polinómico? ¿Hay alguna forma conocida de convertir los términos lambda a lógica combinatoria con solo un aumento de tamaño polinómico (o menor)? Si tal algoritmo existe, ¿es práctico?
Respuestas:
No soy un experto en esto, pero aquí hay dos documentos históricos que parecen ser muy relevantes para la pregunta y posiblemente es un área de investigación semi activa. Turner propuso un conjunto de combinadores que pueden reducirse a combinadores SK. El siguiente artículo argumenta que los combinadores de Turner, incluso sin reducirse a los combinadores de SK, conducen a una explosión exponencial (y que presumiblemente la reducción en términos de SK sería aún mayor). pero luego el segundo artículo dice que existe un algoritmo eficiente de espacio O (n log n) basado en los combinadores de Turner. (Parece que tal vez se han hecho afirmaciones sobre la eficiencia polinómica que se consideran no totalmente demostradas / no probadas y, por lo tanto, se consideran conjeturas ...
¿Qué es una implementación eficiente del cálculo λ? / Frandsen, Sturtivant (1991) (ver p.18)
Traducción de Turner Combinators en el espacio O (n log n) / Noshita (1985)
fuente