Improving the Efficiency of Non-Deterministic Computations1 1Supported in part by NSF grants INT-9981317 and CCR-0110496 and by the Spanish Knowledge Society Foundation, the Spanish Research Funding Agency (CICYT) TIC 2001-2705-C03-01, by Acción Integrade Hispano-Italiana HI2000-0161, and the Valencian Research Council under grant GV01-424.

AbstractNon-deterministic computations greatly enhance the expressive power of functional logic programs, but are often computationally expensive. We analyze a programming technique that improves the time and memory efficiency of some non-deterministic 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 polymorphic defined 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, address its soundness and completeness, and informally reason about its impact on the efficiency of computations