[racket-dev] `letrec' and continuations

Let me make my proposals (2 and 3) more precise because your response suggests they were too short. 

1. We could make internal define the primary vehicle for definitions, i.e., not compile thru letrec. As far as I am concerned, your change to the language to allow defines in many more places has made letrec superfluous. 

2. The semantics for internal defines would be more Algol like, meaning your example would immediately behave like let and thus be fast. 

3. As far as letrec is concerned, we can make it 'expensive' if it is no longer the intermediate target instruction from the macro compiler's perspective. 

-- I think my preferred solution would be to wrap letrec so that continuations grabbed during the setup set up a continuation mark that labels them as 'dangerous'. When you reinvoke them, the existence of the mark tells you that the reference cells should be reinitialized (probably only the ones on the control flow from the continuation point). 

-- An alternative could be to stick a lexical identifier into letrec declarations that gets removed from the scope once the letrec is established. It would reappear when you invoke a continuation from the RHS and thus you'd know to reini the ref cells. BUT, this requires a mechanism that is not expressible at the surface of Racket. And it's odd. 

-- Matthias





On May 20, 2011, at 12:37 PM, Matthew Flatt wrote:

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