[racket-dev] `letrec' and continuations

From: Robby Findler (robby at eecs.northwestern.edu)
Date: Fri May 20 11:55:36 EDT 2011

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.


Posted on the dev mailing list.