Re: New PAKCS release (Version 1.8.0)

From: Francisco Javier López Fraguas <fraguas_at_sip.ucm.es>
Date: Thu, 29 Mar 2007 20:23:29 +0200

Michael Hanus wrote:

>However, an implementation is free to do some optimizations,
>e.g., inlining, constant propagation, partial evaluation,
>or omitting eta-expansion so that reductions can be done earlier.

Removing eta expansion is not merely an optimization,
but has subtle semantic consequences in presence of non-determinism.

The following is a well-known example for the CRWL (Toy) community:

Consider the program

g x = 0
h x = 1

fcoin = g
fcoin = h % fcoin is a 'functional coin'

fadd f g x = (f x) + (g x)
fdouble f = fadd f f

Now consider the evaluation of (fdouble fcoin 0)
 * Without eta expansion in the definition of fcoin
   (fdouble fcoin 0) returns 0 and 2
 * With eta expansion in the definition of fcoin, it returns 0,1 y 2

Thus, performing eta expansion allows to 'escape from sharing'.
I used to exploit this kind of properties in my postdoc lectures to illustrate
how to simulate runtime choice in Toy.

So, I strongly recommend to eliminate in the Curry report the paragraph
mentioned by Wolfgang. Otherwise the report will not correspond to the behavior
of the system.

Wrt HO patterns, I will be glad if the FLP community adopt
more widely the CRWL approach for HO.

Best,

Paco

PS: Sorry, but I cannot react to new messages until April 10

----- Mensaje original -----
De: Michael Hanus <mh_at_informatik.uni-kiel.de>
Fecha: Jueves, Marzo 29, 2007 4:58 pm
Asunto: Re: New PAKCS release (Version 1.8.0)
A: Wolfgang Lux <wlux_at_uni-muenster.de>
CC: curry_at_informatik.rwth-aachen.de

> Wolfgang Lux wrote:
> > Do you consider removing the sentence
> > For convenience, a defining equation f = g
> between functions
> > is allowed but will be interpreted in Curry
> as syntactic sugar
> > for the corresponding defining equation f x
> = g x on base types.
> > on the bottom of p.6 from the report, which IMO suggests
> > eta-expansion?
>
> I don't think that removing this sentence is a necessary requirement.
> The original motivation for this sentence was to base the kernel
> of Curry (i.e., without syntactic sugar) on a firm foundation,
> i.e., needed narrowing or CRWL which were originally defined
> only for first-order rewrite systems.
>
> However, an implementation is free to do some optimizations,
> e.g., inlining, constant propagation, partial evaluation,
> or omitting eta-expansion so that reductions can be done earlier.
>
> Since time has changed and there are extensions of CRWL
> for higher-order rewrite systems (i.e., rules where the
> left- and right-hand side are not of base type and
> partial applications as patterns), I don't see a problem to
> drop this sentence (i.e., the first-order interpretation of
> higher-order rules). Moreover, we could also allow
> partial applications as patterns (as in TOY).
>
> What do you think?
>
> Best regards,
>
> Michael
>
> _______________________________________________
> curry mailing list
> curry_at_lists.RWTH-Aachen.DE
> http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
>
>

********************************
Francisco J. Lopez Fraguas
Dep. Sistemas Informaticos y Computacion
Fac. Informatica U. Complutense Madrid
Prof. Jose Garcia Santesmases s/n
28040 Madrid
Spain

fraguas_at_sip.ucm.es
Tel: +34 91 3947630
Fax: +34 91 3947529
********************************




_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Fri Mar 30 2007 - 07:51:22 CEST

This archive was generated by hypermail 2.3.0 : Mon Nov 11 2019 - 07:15:07 CET