Eliminating Irrelevant Non-determinism in Functional Logic Programs

by Sergio Antoy, Michael Hanus

Long version of a paper appeared in Proc. of the 19th International Symposium on Practical Aspects of Declarative Languages (PADL 2017), Springer LNCS 10137, pp. 1-18, 2017

Functional logic programming languages support non-deterministic search and a flexible use of defined operations by applying them to unknown values. The use of these features has the risk that equal values might be computed several times or I/O computations could fail due to non-deterministic subcomputations. To detect such problems at compile time, we present a method to locate non-deterministic operations. If the non-determinism caused by some operation is semantically not relevant, the programmer can direct the compiler to produce only one result of a computation. If all the results of the computations are equal, this directive preserves the semantics and improves the operational behavior of programs. We define the declarative meaning of such annotations and propose both testing and verification techniques that respectively increase the confidence or formally prove that the non-determinism of an operation is irrelevant.

Preprint (PDF) BibTeX-Entry Online