Incremental Needed Narrowing
Authors
M. Alpuente, S. Escobar, S. Lucas
Abstract
Needed narrowing is currently the best complete strategy for
executing inductively sequential functional logic
programs. Its optimality properties
and the fact that inductively sequential programs are a subclass of strongly
sequential programs support the claim that needed narrowing must be
considered the functional logic couterpart of
Huet and Lévy's strongly needed reduction.
In this paper, we show how a
pre-eminent property of reduction in (a distinguished subclass of)
strongly sequential programs,
namely the incrementality of the evaluation,
can be inherited by needed narrowing. We give an incremental definition of
needed narrowing and show that the original optimality properties are kept.
Moreover, we experimentally demonstrate that the
incremental refinement can lead to substantial improvements in the overall
evaluation process.
Keywords
Functional logic languages, Implementation, Incrementality, Needed Narrowing.