Search papers, labs, and topics across Lattice.
This paper presents a monadic implementation of functional logic programs that supports memoization of non-deterministic choices, addressing the challenge of duplicated computational efforts in demand-driven evaluation. The approach transforms functional logic programs into a monadic representation and implements a monadic interface with memoization. Experiments show that this implementation achieves promising performance, outperforming existing Curry compilers.
Functional logic programs can be efficiently implemented in purely functional languages like Haskell, achieving performance gains over existing Curry compilers by using a novel monadic interface with memoization.
Functional logic languages are a high-level approach to programming by combining the most important declarative features. They abstract from small-step operational details so that programmers can concentrate on the logical aspects of an application. This is supported by appropriate evaluation strategies. Demand-driven evaluation from functional programming is amalgamated with non-determinism from logic programming so that solutions or values are computed whenever they exist. This frees the programmer from considering the influence of an operational strategy to the success of a computation but it is a challenge to the language implementer. A non-deterministic demand-driven strategy might duplicate unevaluated choices of an expression which could duplicate the computational efforts. In recent implementations, this problem has been tackled by adding a kind of memoization of non-deterministic choices to the expression under evaluation. Since this has been implemented in imperative target languages, it was unclear whether this could also be supported in a functional programming environment, like Haskell. This paper presents a solution to this challenge by transforming functional logic programs into a monadic representation. Although this transformation is not new, we present an implementation of the monadic interface which supports memoization in non-deterministic branches. We demonstrate that our approach yields a promising performance that outperforms current compilers for Curry.
