lambda application destroys sharing

From: Sebastian Fischer <>
Date: Wed, 25 Nov 2009 12:00:43 +0100


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
   More solutions? [Y(es)/n(o)/a(ll)]
   cyi> let twice f x = f (f x) in twice ((\x -> \y -> x+y) (1?2)) 10
   More solutions? [Y(es)/n(o)/a(ll)]
   cyi> let twice f x = f (f x) in twice (\y -> (1?2)+y) 10
   More solutions? [Y(es)/n(o)/a(ll)]
   More solutions? [Y(es)/n(o)/a(ll)]
   More solutions? [Y(es)/n(o)/a(ll)]

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



Underestimating the novelty of the future is a time-honored tradition.
curry mailing list
Received on Mi Nov 25 2009 - 12:02:14 CET

This archive was generated by hypermail 2.3.0 : Mi Sep 30 2020 - 07:15:04 CEST