[plt-scheme] about letrec and continuation : which behavior is correct ? and why ?

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Wed Aug 20 11:35:58 EDT 2008

The reason letrec has an "expansive" semantics (let + set!) is so  
that we can use abstractions even for the definition of mutually  
recursive functions:

  (letrec ((co1 (make-coroutine-for-game "Matthias"))
           (co2 (make-coroutine-for-game "Abdulaziz")))
    (coroutine-start co1 (pick-card)))

is the kind of "poem" that we used (at Indiana) to justify the  
EXPRESSION rhs for letrec.

Reality is, we do use this power on rare occasions but perhaps we  
should admit by now, these occasions are rare and the cost is high.

How about:

1. LETREC RHS must be syntactic values. (Note: ML got away with this  
for POLY LET after Andrew showed that there were like fewer than 10  
uses in 100 Kloc of SML code.)

2. LETREC RHS must be "provably equal" to values without effects.  
That is, we allow beta_value and nothing else.

1b. LETREC RHS must be "expansionably equal" (macro expansion) to  
values. That's probably the proper compromise.

Nice, easy spec and we won't miss much of the other opportunities. --  

P.S. ETA expansion doesn't work for the coroutine example because the  
result isn't necessarily a lambda function. So Andrew's trick is out.

On Aug 20, 2008, at 11:20 AM, Abdulaziz Ghuloum wrote:

> On Aug 19, 2008, at 2:48 PM, Joe Marshall wrote:
>> On Tue, Aug 19, 2008 at 7:44 AM, Abdulaziz Ghuloum
>> <aghuloum at cs.indiana.edu> wrote:
>>> On Aug 19, 2008, at 7:10 AM, Matthew Flatt wrote:
>>>> The R5RS/R6RS `letrec' is different, and the result with that
>>>> other `letrec' should be #f:
>> I've always thought this was a wart in the language.
> Fine, but how else would letrec be implements in order to provide
> the full generality of letrec (letrec is not fix) and at the same
> time obey the other rules of the imperative, strict, call-by-value
> language known as Scheme?  E.g., how would you evaluate
>   (letrec ([x (list (lambda () x))])
>     (eq? x ((car x)))) ; => #t
> without a side effect?
>>> An R6RS implementation may (or may not) raise an &assertion when
>>> the <init> continuation is invoked the second time, right?
>> Ugh.  That's worse than the SET! expansion.
> Returning to an <init> continuation may (1) rebind the variable
> as Matthias showed, (2) assign to an already existing binding as
> Matthew showed, or (3) raise an assertion as the report suggests.
> Rebinding is not always possible since there is no known general
> letrec transformation that eliminates side effects.  Options 2
> and 3 are always possible for all shapes of letrec, but they're
> ugly as you suggest.  Where does that leave us?
> Aziz,,,

Posted on the users mailing list.