Improving the Efficiency of Non-Deterministic Computations

Sergio Antoy, Pascual Julian Iranzo, Bart Massey

In Proc. of the International Workshop on Functional and (Constraint) Logic Programming (WFLP 2001) , Report No. 2017, University of Kiel

Abstract

Non-deterministic computations greatly enhance the expressive power of functional logic programs, but are often computationally expensive. We propose two programming techniques that in some cases improve the efficiency of non-deterministic computations. These techniques rely on the introduction of a new symbol into the signature of a program. In one technique, this symbol is a polymorphic defined operation. In the other technique, this symbol is an overloaded constructor. In some situations, our programming techniques save either time by reducing the number of steps of a computation, or memory occupation by reducing the number of terms constructed by a computation, or both. We show how to apply our techniques using some examples and informally reason on their effects. We are working on quantifying these effects both theoretically and experimentally.