[racket-dev] `letrec' and continuations

At Fri, 20 May 2011 11:36:48 -0400, Matthias Felleisen 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). 

Yes.

> 1. Are you sure Robby's idea -- which you modified to compile internal define 
> differently -- works in all cases? 

I don't think we've pinned down exactly the definition, yet, but I'm
pretty sure we can define something that works and that is useful.

> 2. Some other ideas: 
> 
> -- We could request that RHS are syntactic values. That's Draconian.

Yes, that's out.

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

I think we can define internal definitions that way without a
requirement such as values on the the RHS.

> -- We could use prompts on the right hand side of letrec. 

I've considered that possibility. I like how it would be more like
`define' at the top level. Much like a check for multiple returns,
however, I don't see how to make it cheap enough.

> -- We could install code that re-inits the ref cells to UNDEFINED if a 
> continuation from inside a RHS letrec is invoked.

Same as multiple-return checking --- sounds expensive to me.

Of course, those possibilities be cheap enough through some
implementation that I haven't thought of.

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

I mention standards only as an illustration of how the issue has been
addressed before.