Demandness in Rewriting and Narrowing
Authors
Sergio Antoy and Salvador Lucas
Abstract
The traditional investigation of rewriting and
narrowing strategies aims at establishing fundamental properties,
such as soundness, completeness and/or optimality,
of a strategy.
In this work, we analyze and compare rewriting and
narrowing strategies from the point of view of
the information taken into account by a strategy
to compute a step. The notion of demandness provides a suitable
framework for presenting and comparing well-known strategies.
We find the existence of an almost linear sequence of strategies that
take into account more and more information.
We show on examples that, as we progress on this sequence,
a strategy becomes more focused and avoid some useless steps
computed by strategies preceding it in this sequence.
Our work, which is still in progress, clarifies the behavior of
similar or related strategies and it promises to simplify the transfer of
some results from one strategy to another. It also suggest that the
notion of demandness is both atomic and fundamental to the
study of strategies.
Keywords
Declarative programming, narrowing, rewriting, strategies.