## Lazy Narrowing and Needed Narrowing: A Comparison

**María Alpuente, Moreno Falaschi, Pascual Julián,
and Germán Vidal**

*Proc. of the 11th International Workshop on Functional and
(Constraint) Logic Programming (WFLP 2002).*

Needed narrowing is a complete and optimal operational principle
for modern declarative languages which integrate the best features of
(lazy) functional and logic programming.
This paper investigates the formal relation between needed
narrowing and another (not so lazy) demand-driven narrowing strategy
which is the basis for popular implementations of
non-strict functional logic languages.
We demonstrate that needed narrowing and demand-driven lazy narrowing are
computationally equivalent over the class of *uniform* programs,
i.e., both strategies compute the same *answers* and *values*
over this class of programs.
We also introduce a complete refinement of demand-driven lazy narrowing,
called *uniform lazy narrowing*, which is
still equivalent to needed narrowing over the aforementioned class.
Since actual implementations of functional logic languages
are based on the transformation of the original program into a
uniform one, which is then executed using the (demand-driven) lazy
narrowing strategy, our results can be thought of as a formal basis
for the correctness of these implementations.

Available:
PS
BibTeX-Entry

Germán Vidal