by Michael Hanus, Kai-Oliver Prott, Finn Teegen
Proc. of the 24th International Symposium on Principles and Practice of Declarative Programming (PPDP 2022), ACM Press, pp. 1:1-1:15, 2022
© ACM Press
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.
Preprint (PDF) BibTeX-Entry Online