Narrowing vs. rewriting

From: Michael Hanus <hanus_at_I2.Informatik.RWTH-Aachen.DE>
Date: Thu, 3 Jul 1997 13:23:22 +0200

I often have the impression that there are some misunderstandings
about the nature of narrowing. Thus, I would like to discuss it
in this separate message.

It has been sometimes argued that narrowing is complicated (which
is indeed true for some older strategies) and resolution
or rewriting with explicit Boolean connectors is simpler.
I do not agree with this point since, from my understanding,
both methods lead to an identical operational behavior.
In order to make it clear, let's have a look at the following
simple example function:

f a = c
f b = d

(If you think this example is artificial, please replace "f"
by "father" or "mother" and the constants a,b,c,d by persons
of your own family.)

If you use this function to compute values, then there is
no difference between narrowing and rewriting (i.e., (f a)
is reduced to c and (f b) is reduced to d). Thus, the only
difference occurs if we want to use this function to solve
equations, like in the goal "f x = d", where "x" is a free
variable. If we use narrowing as possible in Curry,
this goal is evaluated by following steps (i.e., an instantiation
step followed by several reduction steps):

f x = d --> {x=a} f a = d | {x=b} f b = d
         --> {x=a} c = d | {x=b} f b = d
         --> {x=b} f b = d
         --> {x=b} d = d
         --> {x=b}

Now consider a rewriting model a la Escher. Since the equation
"f x = d" cannot be further evaluated, it is necessary to define
the function f as a predicate fp:

fp x y = (x==a && y==c) || (x==b && y==d)

Since it is a matter of taste whether this definition is more
readable than the first one, I do not want to discuss this point
but consider the operational behavior to solve the equivalent
goal "fp x d". Escher performs the following rewrite steps:

fp x d --> (x==a && d==c) || (x==b && d==d)
        --> (x==a && False) || (x==b && d==d)
        --> False || (x==b && d==d)
        --> (x==b && d==d)
        --> (x==b && True)
        --> (x==b)

If we compare the two derivations, we can see that they are
nearly identical except for some minor syntactic differences.
Thus, this clear indicates that narrowing is no more
complicated than rewriting with special rules for Booleans.
The only difference between the narrowing and the rewriting model
is that rewriting contains some explicit steps which are implicit
in the narrowing derivation.

So, the "simplicity" of rewriting cannot be a serious argument
to abandon the possibility to solve equations by narrowing.
On the other hand, the inclusion of narrowing has some advantages:

1. It costs nothing compared to resolution. Several implementations
of narrowing-based languages have shown that narrowing can be
implemented by pattern matching similar to functional or logic
languages, and there is no overhead if the logic features are
not used.

2. It is not necessary to define functions twice (like "concatenate"
and "split" in Escher) if they should be used for computing values
and solving equations.

3. Functions contain more information than predicates. This
information can be used for more efficient implementations
(see, e.g., Rita Loogen's dynamic cut technique described in
TCS 142 (1995) or our recent paper on parallel narrowing which
will appear in ICLP'97).

4. For narrowing there are results ensuring completeness and
optimality. No similar results are known for other computation
models for functional logic languages. For instance,
an Escher programmer does not know in advance
whether her goal can be solved or will flounder. Even without
logical variables and floundering, it is not ensured that a value
is computed or the system performs an infinite number of
possibly superfluous reduction steps.

Thus, if narrowing has the same behavior as rewriting and has
some additional advantages, what are the arguments to leave it out?
Of course, it is sometimes better to avoid the inversion of some
functions, thus Curry contains the rigid annotations. Actually,
rigid, i.e., rewriting, is the default and narrowing the exeception.
However, by excluding narrowing totally, some potential advantages
are lost.

I welcome further opinions on this important topic.

Best regards,

Michael
Received on Do Jul 03 1997 - 14:27:00 CEST