El no determinismo es una característica fundamental de la programación lógica que permite a los programas producir cero, uno o más resultados ante un único objetivo. Si bien actualmente muchos patrones de programación propios del paradigma funcional –como el orden superior, la currificación o las mónadas– han sido ampliamente adoptados en la mayoría de lenguajes de programación modernos, no ocurre lo mismo con la programación lógica. En parte, esto es debido a que estos mecanismos inherentes del paradigma lógico no se materializan de forma tan clara o tangible en otros lenguajes. Sin embargo, una computación no determinista puede ser fácilmente modelada en cualquier lenguaje como un programa que produce una lista de resultados. Además, estas computaciones no deterministas pueden enlazarse de forma sencilla. El propósito de este artículo es tratar de mostrar cómo aprovechar una de las principales características de la programación lógica, el no determinismo, fuera de este marco de programación para simplificar la implementación de funciones que pueden producir múltiples resultados.
Un analizador sintáctico es un programa que analiza cadenas de símbolos y las transforma en algún tipo de representación más estructurada. Por otra parte, en programación funcional una mónada es una estructura que representa una forma de computación. Las mónadas favorecen la programación con efectos de forma genérica, y el análisis sintáctico es uno de los muchos problemas que ayudan a simplificar.
En este artículo se proporciona una descripción general de los conceptos fundamentales sobre el análisis sintáctico basado en las interfaces de funtor, funtor aplicativo y mónada.
Toda cláusula Prolog es un término Prolog válido, lo cual implica que podemos analizar y procesar código Prolog utilizando predicados y características incorporadas del propio lenguaje. Esto es especialmente conveniente a la hora de definir transformaciones automáticas de programas. Aunque el estándar ISO Prolog no define ningún mecanismo de transformación de programas tales como la expansión de macros o la compilación condicional, todos los sistemas Prolog ampliamente utilizados proporcionan predicados que permiten reescribir código en tiempo de compilación.
Normalmente, en Prolog, estos mecanismos se proveen mediante la expansión de términos y la expansión de objetivos, en forma de predicados dinámicos: term_expansion/2 y goal_expansion/2, respectivamente.
Las estructuras de datos incompletas proporcionan una técnica de programación propia de Prolog que permite incrementar la eficiencia de los programas lógicos y simplificar su diseño. Estas estructuras se apoyan en el uso de variables lógicas para representar huecos, los cuales simbolizan partes de las estructuras que todavía no han sido computadas. La estructura incompleta más utilizada es la lista diferencia.