Re: Narrowing: yes or no? [was Re: Narrowing vs. rewriting]

From: Michael Hanus <hanus_at_I2.Informatik.RWTH-Aachen.DE>
Date: Fri, 4 Jul 1997 11:05:59 +0200

Manuel Chakravarty wrote:
> Apart from the discussion about concurrency, I think there are two
> good reasons why important parts of any realistic Curry program will
> exclusively use rewriting (not narrowing):

This is also the case for Prolog programs and it is exactly the
motivation why functions should be added to logic programs.
The questions is, however, how to deal with the remaining parts
where partial information and non-determinism are important.

> Sure, there are nice examples of programs that given the semantics of
> narrowing are short, elegant, and declarative. And I am sure, there
> are good applications for narrowing, but I am not sure whether
> narrowing is of much use in everyday programming. So, I agree very
> much with Phil: without characterizing target applications first, the
> whole discussion does not make too much sense.

Narrowing is a straightforward generalization of rewriting to cover
logic programming applications, and I think the motivation for this
FLP work is the integration of functional and logic programming in
a single language. Narrowing is just a method to deal with logical
variables and specifies how to instantiate them. The advantage
of narrowing is that is is well-understood (there are numerous
results characterizing its behavior) and it does not need the
extra-machinery of rewrite rules for Booleans as in Escher.

I agree that main parts of applications (like the one cited by
John Lloyd) do not use logical variables everywhere, but, if they occur,
we have to give an answer how to deal with them. Narrowing is
one possibility, explicit rewrite rules for Booleans another.
However, narrowing is better understood and easy to implement
(note that the rewrite rules of Escher are not function definitions
like in the Haskell). Moreover, the non-determinism in narrowing
is equally present in the rewrite rules for Booleans, as I showed
in my initial "narrowing vs. rewriting" email. Thus, narrowing
is not more complicated than rewriting.

> So, what is the purpose of Curry? Initially, I remember, it was meant
> to provide a common language for the people working on integration: to
> compare implementations, avoid long introduction of syntax in talks,
> support cross-fertilization, share code etc. Do we still agree that
> this is the purpose of the language?

I still agree on this motivation. I would like to add that
Curry should be also a common basis to teach FP and LP
in a single course. Thus, if we abandon narrowing at this stage
(even if some people will not use it in their applications),
we loose this goal since people working on narrowing will
still work on their own languages.

Best regards,

Michael
Received on Fr Jul 04 1997 - 12:10:00 CEST