Christiansen, J., Hanus, M., Reck, F., & Seidel, D. (2013). A Semantics for Weakly Encapsulated Search in Functional Logic Programs. In Proceedings of the 15th Symposium on Principles and Practice of Declarative Programming - PPDP 13 (S. 49-60). ACM Press. http://doi.org/10.1145/2505879.2505896
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.