[racket-dev] `letrec' and continuations

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Fri May 20 11:36:48 EDT 2011

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. 

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

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

Posted on the dev mailing list.