A Semantics for Weakly Encapsulated Search in Functional Logic Programs

by Jan Christiansen, Michael Hanus, Fabian Reck, Daniel Seidel

Proc. of the 15th International Symposium on Principles and Practice of Declarative Programming (PPDP'13), ACM Press, pp. 49-60, 2013
© ACM Press

Encapsulated search is a key feature of (functional) logic languages. It allows the programmer to access and process different results of a non-deterministic computation within a program. Unfortunately, due to advanced operational features (lazy evaluation, partial values, infinite structures), there is no straightforward definition of the semantics of encapsulated search in functional logic languages. As a consequence, various proposals and implementations are available but a rigorous definition covering all semantical aspects does not exist. In this paper, we analyze the requirements of encapsulated search in a functional logic language like Curry and provide a comprehensive definition that covers weak encapsulation, a modular form of encapsulation, as well as nested applications of search operators. We set up a denotational semantics that distinguishes non-termination and different levels of failures in a computation. The semantics is also the basis of a practical implementation of search operators in the functional logic language Curry.

Preprint (PDF) BibTeX-Entry Online