lambda application destroys sharing

From: Sebastian Fischer <sebf_at_informatik.uni-kiel.de>
Date: Wed, 25 Nov 2009 12:00:43 +0100

Hello,

it is well known that eta-expansion is not valid in functional-logic
programs [1]. To my surprise, this has the consequence that the same
is true for applications of lambda abstractions (due to the way they
are eliminated using lambda lifting). Here is an example session using
the Münster Curry Compiler, but PACKS behaves similarly (but does not
allow lambda abstractions in its prompt):

   cyi> let twice f x = f (f x) in twice ((1?2)+) 10
   12
   More solutions? [Y(es)/n(o)/a(ll)]
   14
   cyi> let twice f x = f (f x) in twice ((\x -> \y -> x+y) (1?2)) 10
   12
   More solutions? [Y(es)/n(o)/a(ll)]
   14
   cyi> let twice f x = f (f x) in twice (\y -> (1?2)+y) 10
   12
   More solutions? [Y(es)/n(o)/a(ll)]
   13
   More solutions? [Y(es)/n(o)/a(ll)]
   13
   More solutions? [Y(es)/n(o)/a(ll)]
   14

The second call is a (semantically valid, I think) translation of the
first partial application into lambda abstractions, the third call
results from the second by application which is - for me, surprisingly
- an invalid transformation.

I don't propose to change anything, just wanted to share this
observation.

Cheers,
Sebastian

[1]: http://www.informatik.uni-kiel.de/~curry/listarchive/0497.html


-- 
Underestimating the novelty of the future is a time-honored tradition.
(D.G.)
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Wed Nov 25 2009 - 12:02:14 CET

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