Comparative Implementation of Narrowing Strategies
Daniela Genius, Department of Program Structures and Data Organization, Vincenz-Priessnitz-Str. 3, 76128 Karlsruhe, Germany
Abstract
We have implemented several narrowing strategies by translation
into Prolog, exploiting determinism on the one hand, expression
parallelism on the other. For the latter strategies a translation
scheme is given. As efficiency of the parallel
strategies is unsatisfactory at least in a Prolog
implementation, we suggest a combination of both approaches, improving
run time behaviour of the parallel strategy significantly.
We try to establish a taxonomy among the strategies we considered.
A testing environment is provided, which also contains some heuristics
for the creation of definitional trees out of left hand sides of
rules. Extending parallel narrowing strategies by conditional rules
is still an open question, demanding for further research.
Introduction
Informally speaking, a narrowing step is an instantiation of goal variables
followed by a reduction step on the instantiated goal.
Lazy narrowing strategies generally apply steps at outermost positions, and
consider inner positions only if they are demanded.
For the class of inductively sequential rewrite systems,
needed narrowing is optimal w.r.t. the number of
solutions as well as the length of derivations.
Our goal is to extend needed narrowing to a more general class of weakly orthogonal systems which allow overlapping left hand sides of rules.
The Implementations
A conservative extension is weakly needed narrowing which can be implemented in Prolog by using the backtracking mechanism.
Loogen and Winkler
propose a dynamic cut, i.e. cutting off alternative solutions at run time
if no variables in the goal have been bound.
Lazy narrowing with
simplification by Hanus exploits determinism by
performing reduction steps between narrowing steps.
We focus on the application of
steps at multiple disjoint positions at once, so called narrowing multisteps.
A narrowing multistep consists of a first part, in which possible substitutions
are explicitly collected. This breadth-first approach is necessary, as
try to eliminate some of the substitutions afterwards.
In the second part, we simply perform a rewrite multistep.
A detailed translation scheme is described in the MPLP paper.
Parallel Narrowing with Simplification
In analogy to lazy narrowing with simplification, we generate separate pieces of code for a terminating subset of the rules.
Simplification steps should be applied as long as no goal variable needs to be bound.
Simplification rules are generated with the help of the definitional tree for the terminating rules.
The new strategy avoids the overhead of collecting substitutions breadth-first in many cases, resulting in a gain in efficiency (factor 3-4).
Experimental Results
In my thesis, the influence of programming techniques, behaviour on
purely functional programs, and the elimination of useless computations
have been considered in some detail.
Lazy narrowing with simplification has significant advantages on
generate-and-test programs, such as permutation sort.
The implementation overhead of multistep and dynamic cut strategies in a
Prolog implementation is very high, as we have to consider the entire term
in a breadth-first manner in the first case, and bypass Prolog's backtracking mechanism in both cases.
Conditional Narrowing
We suggest a method to extend multistep strategies by conditional equations.
Thus, a nonambiguity condition like in BABEL becomes necessary.
Generation of Definitional Trees
For convenience, we provide algorithms that extend Antoy's definitional tree creation algorithms to overlapping lhs of rules (so-called parallel definitional trees).
Conclusions
The concrete implementation also comprises the definition of a
small language CUT (CUrry Translation) and a frontend,
in order to support the development of Curry.
We have presented the first implementation of a narrowing strategy
with parallel steps. Furthermore we suggest,
from the implementational point of view, a parallel strategy with
simplification steps, which is the most powerful though not the fastest
among the strategies we examined.
Related Web pages
Thesis was accomplished at the RWTH Aachen, Department of Computer Science II (Prof. Hanus)