[racket-dev] `letrec' and continuations

On Fri, May 20, 2011 at 10:36 AM, Matthias Felleisen
<matthias at ccs.neu.edu> wrote:
>
> On May 20, 2011, at 10:28 AM, Matthew Flatt wrote:
>
>> The second printout is "ready" because locations for all of the
>> `letrec'-bound variables are allocated before the right-hand sides are
>> evaluated --- which means before the continuation is captured.
>
>> A programmer almost never needs the semantics of `letrec' that
>> `call/cc' exposes, and a programmer often wants `letrec' to be as
>> efficient as `let' or `let*'.
>
>
> What this code recalled for me is the (in)famous 1980s style
> puzzle (I believe due to Jinx) of retrieving reference cells
> (boxes) from letrec plus call/cc (see 1988 LFP paper on LC_v-CS).
>
> This issue has bugged the hell out of me since.
>
> 1. Are you sure Robby's idea -- which you modified to compile internal define differently -- works in all cases?
>
> 2. Some other ideas:
>
> -- We could request that RHS are syntactic values. That's Draconian. We would lose the pattern that you set up a common abstraction and then instantiate twice in the letrec w/o wrapping them in lambdas, e.g.,
>
> (let ()
>  (define (player-update! setter selector max-value)
>  (lambda (player delta)
>    (setter player (min (max 0 (+ (selector player) delta)) max-value))))
>
>  (define player-health+ (player-update! set-player-health! player-health MAX-HEALTH))
>
>  (define player-agl+  (player-update! set-player-agl! player-agl MAX-AGILITY))
>  ...)
>
> BUT.  ML and Haskell get away with this. Why don't we? (Partly due to typing lambda and currying.) PLUS, we could accommodate this change with a change to internal DEFINEs syntax. Don't make it a LETREC. Turn it into a mostly LET plus LETREC when you encounter a recursive function. This is ALGOL 60's semantics (as in the Burroughs dialect) and I have often told Eli that this is what I'd really like for DEFINE.

Just to note here: I believe that if the code happens to conform to
this restriction then the compiler will in fact be able to do a good
job with it already.

> -- We could use prompts on the right hand side of letrec. Bob H and I discussed this when he worked for Kent. At the time all of us were too much in love with another puzzle concerning letrec: define mutually recursive functions in a letrec from a common abstraction -- that uses call/cc. You set up coroutines that way. Honestly, I haven't designed a program since my 'control' days that uses this trick. It might be possible to formulate the puzzle with Jon and Eli's Icon-style generators but so what. This would eliminate the whole problem because you wouldn't get a second iteration.
>
> -- We could install code that re-inits the ref cells to UNDEFINED if a continuation from inside a RHS letrec is invoked. That would force the second solution. I don't think it would be too expensive to set up the logic and it might be possible to eliminate if you know there is no call to call/cc in any RHS.

Can we really change the semantics of letrec in such a fundamental way?

Would it make sense to have a new construct, say letrec-super-star,
that did one of those things and then use that as the core form in
Racket (that's also a big change, but probably smaller than changing
letrec itself).

> 3. We are Racket and we no longer need to live up to the Scheme standard.

:)

Just the big pile of Racket code that we have lying around.

Robby