Set Functions for Functional Logic Programming

The authors propose a novel approach to encapsulate non-deterministic computations in functional logic programs. Their approach is based on set functions that return the set of all the results of a corresponding ordinary operation. A characteristic feature of their 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.