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

On Wed, Aug 20, 2008 at 8:20 AM, Abdulaziz Ghuloum
<aghuloum at cs.indiana.edu> 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?


The thing that I thought was a wart was that letrec was
*required* to expand as if it were a let followed by a set
even in cases where it could have been accomplished by
a fixed-point computation.  You are forced to be inelegant
even when you don't need to be.


>>> 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?

Option 4:  An implementation *may* implement letrec as a binding
followed by an assignment, or it *may* implement letrec as a
fixed point, or it *may* mix the two.  Returning to an <init> continuation
may cause re-assignment or rebinding at the discretion of the
implementation.

Alternatively, the right hand side of the letrec could be restricted.

I rarely use letrec (or internal define) for arbitrary values.  I almost
always use letrec (or internal define) for procedures only.  If this
were the case, then you'd have to explicitly have a side effect in
the code above:

(let ((x (list #f)))
  (set-car! x (lambda () x))
  (eq? x ((car x))))

Which, frankly, is a better way of writing this than the letrec
because it is obvious that some side-effecting is going on in
order to create magic circular structure such that
(eq? x ((car x))) could evaluate to #t.


-- 
~jrm