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
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.