Re: Narrowing vs. rewriting

From: John Lloyd <jwl_at_cs.bris.ac.uk>
Date: Thu, 3 Jul 1997 15:21:39 +0100 (BST)

I have some comments on Michael's message about narrowing vs. rewriting,
but first can I suggest some other people take up this and some of
the other issues. Can some people please take the time to read the Escher paper
carefully and see whether there is something in there which can usefully be
incorporated into the Curry design? Whatever we eventually decide for Curry,
we need to be convinced it is as simple as possible and at the same time is
rich enough to attract programmers!


> f a = c
> f b = d
>
.
.
>
> 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)

First a minor point. It's better to write the last statement as

fp = {(a,c), (b,d)}

The points Michael makes on this example are entirely accurate. In fact,
it's not surprising - narrowing should behave similarly to rewriting plus use
of some of the rewrites in Booleans. The intuition is that when Escher
matches it does only half the narrowing step. The rest is taken care of
by explicit equalities in the body.

However, put yourself in the position of having to explain the computational
model of Escher or Curry to an (inexperienced, say) programmer. Here is the
Escher story - I'll leave others to fill in the Curry story for comparison:

In Escher you always write equations. The basic idea is that, having set
up the intended interpretation (i.e. application) and the program, you want
to find out the meaning (denotation) of certain expressions. So you give
Escher an expression which is "too complicated" for the programmer
to be easily able to give its intended meaning. Escher computes for a while
and then returns an expression which is guaranteed to have the same meaning
as the original one and is sufficiently simple that the programmer can see
at a glance what it's meaning is.

The computation is a simple sequence of expressions, the first being
the original expression and the last being Escher's answer. The function
call mechanism is very simple indeed. Compared to Prolog (this is being
unfair to Curry of course, but it makes the point!) I have gotten rid of
all kinds of "crud" - backtracking, unification, search trees, cuts, ... -
that programmers are much better off not having to worry about.

In fact, this is just the Haskell story except Escher allows variables
in expressions. Having taught Haskell to our big first class here, I feel
very confident that I can explain this story and pretty soon have students
writing conventional Haskell programs as well as LP-like ones.

In summary, the rewriting story of Haskell does work well - I'm generalising
it somewhat but the the essence is the same. This is definitely a good story!



> 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.

Actually, this is a feature of Escher, not a bug! I don't like
multi-directional functions or predicates. It's generally clearer to write
separately the two (different!) functions you need.


>
> 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).

This is equally true for Escher.



> 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.

This I have discussed earlier. But note one additional point. It isn't
always disastrous for a computation to not compute far enough (i.e flounder).
Whatever happens the first and last expressions are equal.


> However, by excluding narrowing totally, some potential advantages
> are lost.

Sorry, but I still haven't seen the practical examples which demonstrate
this last point. Please show me the examples.

John
Received on Do Jul 03 1997 - 17:07:00 CEST