## A Needed Narrowing Strategy

**Sergio Antoy and Rachid Echahed and Michael Hanus**
*Technical Report MPI-I-93-243, Max-Planck-Institut fuer Informatik*

*Short version in Proc. of the 21st ACM Symposium on
Principles of Programming Languages*

Narrowing is the operational principle of languages that
integrate functional and logic programming. We propose
a notion of a needed narrowing step that, for inductively
sequential rewrite systems, extends the Huet and Levy notion
of a needed reduction step. We define a strategy, based
on this notion, that computes only needed narrowing steps.
Our strategy is sound and complete for a large class of
rewrite systems, is optimal w.r.t. the cost measure that
counts the number of distinct steps of a derivation, computes
only independent unifiers, and is efficiently implemented
by pattern matching.

Available:
DVI
BibTeX-Entry