## Uniform Lazy Narrowing

**María Alpuente, Moreno Falaschi, Pascual Julián,
and Germán Vidal**
© Oxford University
Press

*Journal of Logic and Computation,* 13(2), pp. 287-312, 2003

Needed narrowing is a complete and optimal operational principle
for modern declarative languages which integrate the best features of
lazy functional and logic programming.
We investigate the formal relation between needed
narrowing and another (not so lazy) demand-driven narrowing strategy
which is the basis for popular implementations of lazy
functional logic languages.
We demonstrate that needed narrowing and demand-driven narrowing are
computationally equivalent over the class of *uniform* programs.
We also introduce a complete refinement of demand-driven 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 demand-driven
narrowing, our results can be thought of as a formal basis for the
correctness of these implementations.

Available:
PDF (preliminary version)
BibTeX-Entry

Germán Vidal