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

From: Wolfgang Lux <lux_at_wi.uni-muenster.de>

Date: Mon, 22 Oct 2001 17:04:54 +0200

Hello,

the semantics of purely functional programs in Curry is mostly similar

to that of Haskell (except for the handling of overlapping rules).

However, there is one major difference, which results in valid Haskell

programs to fail under Curry: The lifting algorithm given in appendix

D.8 of the report is too strict wrt local patterns. E.g. consider the

definition

foo xy = length [x,y]

where (x,y) = xy

In Haskell the expression "foo undefined" evaluates to 2, while in

Curry this expression fails. Another example is

bar n xy =

| n == 0 = success

| otherwise = x =:= y

where (x,y) xy

for which the expression "bar 0 undefined" is going to fail even though

the argument xy is not used at all.

The reason for these failures is the lifting algorithm of appendix D.8

which transforms local patterns declarations into additional arguments

of an auxiliary function. E.g., the definition of foo above is

translated into (after removing unused variables)

foo xy = foo' xy

foo' (x,y) = length [x,y]

This translation demands too much evaluation. A better solution is to

use accessor functions in order to extract the components of the

pattern:

foo xy = foo' (fst x) (snd y)

foo' x y = length [x,y]

With this definition the evaluation of "foo undefined" will no longer fail

but yield 2.

In order to get this behaviour, I propose to change the sub-paragraph

Eliminate patterns on pp. 71f into

Select a local pattern declaration which contains only argument

variables from the main function's left-hand side in the expression,

i.e., the rule has the form

l = C[let { decls_1; p = e'; decls_2 } in e]_p

with free(e') \subset free(l). Then transform this rule into the rules

l = C[f' x_1 ... x_k e']_p

f' x_1 ... x_k z = f'' x_1 ... x_k (f_1 z) ... (f_m z)

f'' x_1 ... x_k y_1 ... y_m = let { decls_1; decls_2 } in e

f_1, ..., f_m eval rigid

f_1 p = y_1

...

f_m p = y_m

where x_1 ... x_k are all the variables occurring in l, y_1 ... y_m

are all the variables occurring in p, z is a new variable symbol and

f', f'', f_1 ... f_m are new function symbols. Repeat this step until

all local pattern declarations are eliminated.

This translation can be optimized in a few special case. If p is just a

variable the function f' is not needed and the definition of l can be

simplified into

l = C[f'' x_1 ... x_k e']_p

Similarly, when e' is a variable the function f' is also not needed and

the definition of l can be replaced by

l = C[f'' x_1 ... x_k (f_1 e') ... (f_m e')]_p

The evaluation annotation for the f_i serves the purpose to avoid a

possible instantiation of the result of e' by any of the functions f_i,

which is IMHO not very useful and -- due to the lazy evaluation of the

applications -- in fact unpredictable.

Regards

Wolfgang

Date: Mon, 22 Oct 2001 17:04:54 +0200

Hello,

the semantics of purely functional programs in Curry is mostly similar

to that of Haskell (except for the handling of overlapping rules).

However, there is one major difference, which results in valid Haskell

programs to fail under Curry: The lifting algorithm given in appendix

D.8 of the report is too strict wrt local patterns. E.g. consider the

definition

foo xy = length [x,y]

where (x,y) = xy

In Haskell the expression "foo undefined" evaluates to 2, while in

Curry this expression fails. Another example is

bar n xy =

| n == 0 = success

| otherwise = x =:= y

where (x,y) xy

for which the expression "bar 0 undefined" is going to fail even though

the argument xy is not used at all.

The reason for these failures is the lifting algorithm of appendix D.8

which transforms local patterns declarations into additional arguments

of an auxiliary function. E.g., the definition of foo above is

translated into (after removing unused variables)

foo xy = foo' xy

foo' (x,y) = length [x,y]

This translation demands too much evaluation. A better solution is to

use accessor functions in order to extract the components of the

pattern:

foo xy = foo' (fst x) (snd y)

foo' x y = length [x,y]

With this definition the evaluation of "foo undefined" will no longer fail

but yield 2.

In order to get this behaviour, I propose to change the sub-paragraph

Eliminate patterns on pp. 71f into

Select a local pattern declaration which contains only argument

variables from the main function's left-hand side in the expression,

i.e., the rule has the form

l = C[let { decls_1; p = e'; decls_2 } in e]_p

with free(e') \subset free(l). Then transform this rule into the rules

l = C[f' x_1 ... x_k e']_p

f' x_1 ... x_k z = f'' x_1 ... x_k (f_1 z) ... (f_m z)

f'' x_1 ... x_k y_1 ... y_m = let { decls_1; decls_2 } in e

f_1, ..., f_m eval rigid

f_1 p = y_1

...

f_m p = y_m

where x_1 ... x_k are all the variables occurring in l, y_1 ... y_m

are all the variables occurring in p, z is a new variable symbol and

f', f'', f_1 ... f_m are new function symbols. Repeat this step until

all local pattern declarations are eliminated.

This translation can be optimized in a few special case. If p is just a

variable the function f' is not needed and the definition of l can be

simplified into

l = C[f'' x_1 ... x_k e']_p

Similarly, when e' is a variable the function f' is also not needed and

the definition of l can be replaced by

l = C[f'' x_1 ... x_k (f_1 e') ... (f_m e')]_p

The evaluation annotation for the f_i serves the purpose to avoid a

possible instantiation of the result of e' by any of the functions f_i,

which is IMHO not very useful and -- due to the lazy evaluation of the

applications -- in fact unpredictable.

Regards

Wolfgang

-- Wolfgang Lux Phone: +49-251-83-38263 Institut fuer Wirtschaftinformatik FAX: +49-251-83-38259 Universitaet Muenster Email: wlux_at_uni-muenster.de _______________________________________________ curry mailing list curry_at_lists.RWTH-Aachen.DE http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curryReceived on Di Okt 23 2001 - 08:51:12 CEST

*
This archive was generated by hypermail 2.3.0
: So Aug 01 2021 - 07:15:03 CEST
*