by Sergio Antoy, Michael Hanus
Proc. of the 11th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP'09), ACM Press, pp. 73-82, 2009
© ACM Press
We propose a novel approach to encapsulate non-deterministic computations in functional logic programs. Our approach is based on set functions that return the set of all the results of a corresponding ordinary operation. A characteristic feature of our approach is the complete separation between a usually-non-deterministic operation and its possibly-non-deterministic arguments. This separation leads to the first provably order-independent approach to computing the set of values of non-deterministic expressions. The proof is provided within the framework of graph rewriting in constructor-based systems. We propose an abstract implementation of our approach and prove its independence of the order of evaluation. Our approach solves easily and naturally problems mishandled by current implementations of functional logic languages.
Preprint (PDF) BibTeX-Entry Online