Notación imperativa para programación lógica = Imperative notation for logic programming

Resumen

Las variables de estado y los bucles, entre otras características, se asocian típicamente con los lenguajes de programación imperativos y no se encuentran de forma nativa en los paradigmas de programación declarativa. Por ejemplo, muchos lenguajes basados en lógica dependen exclusivamente de la recursión para expresar la iteración. Sin embargo, las características imperativas pueden simplificar la implementación de ciertos algoritmos que, de otro modo, serían más engorrosos de expresar mediante recursión. Como resultado, algunos sistemas de programación lógica han incorporado diversos constructos imperativos.

Prolog es uno de los principales representantes del paradigma de programación lógica. Puede soportar notación funcional mediante un enfoque sintáctico, FSyntax, que aprovecha la sintaxis del lenguaje y las capacidades de expansión de términos. Hiord es otro enfoque sintáctico que permite la programación de orden superior en Prolog. Basándose en call/n, introduce características adicionales como los predicados anónimos. Tanto FSyntax como Hiord se utilizan ampliamente en el sistema Ciao Prolog, el cual se basa en la familia de Prolog, aunque es también un sistema de programación multiparadigma. Ciao Prolog dispone de un avanzado sistema de módulos que permite implementar fácilmente extensiones sintácticas y semánticas potentes.

En este trabajo proponemos un conjunto de constructores de estilo imperativo que extienden FSyntax y Hiord. Estas extensiones están diseñadas para integrarse de forma natural con la notación funcional básica, las facilidades de orden superior y otras extensiones del lenguaje como las restricciones. A diferencia de propuestas anteriores, nuestro enfoque ofrece tanto un conjunto de primitivas como un mecanismo de alto nivel que, en conjunto, permite a los usuarios extender fácilmente el lenguaje con características como notación de arrays, variables de estado, bucles, etc.

Ofrecemos una descripción detallada de cómo la compilación de módulos procesa estos constructores: desde la definición de la sintaxis hasta su traducción completa en predicados planos de Prolog y llamadas estáticas. Además, describimos el concepto de unificación unidireccional, su representación equivalente en Prolog y su implementación en el sistema Ciao.

A partir de estas extensiones, desarrollamos un paquete adicional que proporciona notación de acceso indexado a arrays. Este paquete consta de una interfaz y cuatro implementaciones diferentes, y utiliza variables de estado para realizar la modificación del elemento n-ésimo de un array.

Evaluamos nuestro enfoque traduciendo problemas del Proyecto Euler de Picat a Ciao. Verificamos su corrección comprobando que todas las pruebas se superan, y medimos los tiempos de ejecución para evaluar el rendimiento. Estos resultados permiten comparaciones con implementaciones en otros lenguajes. Nuestros experimentos muestran que las extensiones propuestas ofrecen un rendimiento competitivo.

Finalmente, creemos que incorporar características sintácticas propias de la programación imperativa puede ayudar mucho al programador y, potencialmente, favorecer una adopción más amplia de los lenguajes declarativos. Además, dependiendo de su semántica, los constructores imperativos como los bucles pueden ayudar a los analizadores estáticos al proporcionar información implícita, como determinismo, no-fallo, modos, tipos y cotas del número de iteraciones de los bucles, lo cual resulta valioso para el análisis de coste y complejidad.

ABSTRACT

State variables and loops, among other features, are typically associated with imperative programming languages and are not natively found in declarative programming paradigms. For example, many logic-based languages rely solely on recursion to express iteration. However, imperative features can simplify the implementation of certain algorithms that would otherwise be more cumbersome to express recursively. As a result, some logic programming systems have incorporated various imperative constructs.

Prolog is one of the major representatives of the logic programming paradigm. It can support functional notation through a syntactic approach, FSyntax, which leverages the language’s syntax and term expansion capabilities. Hiord is another syntactic approach to supporting higher-order programming in Prolog. Building on call/n, it introduces additional features such as anonymous predicates. Both FSyntax and Hiord are extensively used in the Ciao Prolog system. Ciao Prolog is a multi-paradigm programming system based on the Prolog family. It features an advanced module system that enables easily implementing powerful syntactic and semantic extensions.

In this work, we propose a set of imperative-style constructs that extend FSyntax and Hiord. These extensions are designed to integrate smoothly with the basic functional notation, higher-order facilities, and other language extensions such as constraints. Unlike previous proposals, our approach offers both a collection of primitives and a high-level mechanism that together enable users to easily extend the language with features such as array notation, state variables, and loop constructs, etc.

We provide a detailed account of how the compilation module processes these constructs—from syntax definition to their full translation into flat Prolog predicates and static calls. Additionally, we describe the concept of one-sided unification, its equivalent representation in Prolog, and its implementation in the Ciao system.

Building on these extensions, we have developed an additional package that provides indexed array access notation. This package consists of an interface and four different implementations and uses state variables to support modification of the nth element of an array.

We evaluate our approach by translating Euler Project problems from Picat to Ciao. We verify correctness by checking that all tests pass, and we measure execution times to assess performance. These benchmarks allow comparison with implementations in other languages. Our experimental results show that the proposed extensions offer competitive performance.

Finally, we argue that incorporating syntactic features from imperative programming can improve programmer convenience and potentially support wider adoption of declarative languages. Moreover, depending on their semantics, imperative constructs like loops can assist static analyzers by providing implicit properties such as determinism, non-failure, modes, types, and bounds on loop iterations, information that is valuable for cost and complexity analyses.