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

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

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

*
This archive was generated by hypermail 2.3.0
: Sa Apr 01 2023 - 07:15:05 CEST
*