¿Los términos de lógica combinatoria son siempre más grandes?

9

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?

Jake
fuente
el documento es de 1979. hay mucho más moderno / reciente pensamiento / tecnología sobre cómo traducir el código a la lógica, por ejemplo, con FPGA y GPU, y generalmente no se basaría en lenguajes funcionales ...
vzn
¿Puedes señalarme a ellos?
Jake
la investigación que cita es una "prueba de principio" más teórica ... sería mejor si citara el concepto / sección sobre "aumento de tamaño polinómico" que parece ser el foco de su pregunta ... ¿está interesado en el ¿teoría general de convertir código en lógica / circuitos, en el lado teórico o aplicado, o la teoría de hacerlo eficientemente, o ambos? la pregunta es muy transversal en sus diferentes aspectos ... tal vez pueda descubrir más en Computer Science Chat
vzn
1) ¿hay alguna manera de importar esto a un chat? Parece que no puedo entender eso. 2) No hay una sección sobre el aumento de tamaño polinómico y ese es mi problema. En realidad no dice nada sustancial (ni puedo encontrar ninguna de esas referencias) sobre cuánto es el aumento de tamaño.
Jake
los comentarios se pueden importar al chat después de un umbral de comentarios publicados por separado. eso no es necesario para iniciar un chat. Si se trata de un aumento polinómico, podría ser un concepto de "rumor" o "folklore" sobre esta línea de investigación, no estoy seguro. pero ¿dónde escuchaste cosas como "produce cosas que explotan en tamaño"; sería útil ser más específico, etc ...
vzn

Respuestas:

4

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 ...

vzn
fuente
1
¡Perfecto! Encontré este documento también después de buscar esos dos documentos. sciencedirect.com/science/article/pii/002001908790161X ¡Gracias!
Jake