Improving the Eciency of Non-Deterministic Computations

Non-deterministic computations greatly enhance the expressive power of functional logic programs, but are often computationally expensive. We analyze a program-ming technique that improves the time and memory e±ciency of some non-deter-ministic computations. This technique relies on the introduction of a new symbol into the signature of a program. This symbol may be treated either as a polymor-phic de¯ned operation or as an overloaded constructor. Our programming technique may save execution time, by reducing the number of steps of a computation. The technique may also save memory, by reducing the number of terms constructed by a computation. We give some examples of the application of our technique, ad-dress its soundness and completeness, and informally reason about its impact on the e±ciency of computations.