- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

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 Thu Jul 03 1997 - 17:07:00 CEST

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!

.

.

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!

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.

This is equally true for Escher.

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.

Sorry, but I still haven't seen the practical examples which demonstrate

this last point. Please show me the examples.

John

Received on Thu Jul 03 1997 - 17:07:00 CEST

*
This archive was generated by hypermail 2.3.0
: Fri Sep 20 2019 - 07:15:04 CEST
*