[racket-dev] `letrec' and continuations

On Fri, May 20, 2011 at 10:53 AM, Matthew Flatt <mflatt at cs.utah.edu> wrote:
> I like the idea of adjusting the semantics of internal definitions and
> leaving `letrec' alone.

While this seems like a nice change, how does it interact with
internal syntax definitions?  If there are internal syntax
definitions, do we fall back to `letrec-syntaxes+values'?  Do we want
`letrec-syntaxes+let*-values' (I hope not)?

>
> At Fri, 20 May 2011 09:39:06 -0500, Robby Findler wrote:
>> How about making letrec (or letrec*?) be syntactically illegal if
>> there are no forward references and make the internal definition
>> expander avoid it in that case? (Or maybe just the second half of
>> that.)
>>
>> Robby
>>
>> On Fri, May 20, 2011 at 9:28 AM, Matthew Flatt <mflatt at cs.utah.edu> wrote:
>> > If you run this program in Racket,
>> >
>> >  (let ([restart void])
>> >   (letrec ([forward-reference (lambda () maybe-ready)] ; affects compiler
>> >            [dummy1 (let/cc k (set! restart k))]
>> >            [dummy2 (displayln maybe-ready)]
>> >            [maybe-ready 'ready])
>> >     (let ([rs restart])
>> >       (set! restart void)
>> >       (rs #f))))
>> >
>> > then the output is
>> >
>> >  #<undefined>
>> >  ready
>> >
>> > 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.
>> >
>> >
>> > If you comment out the `forward-reference' binding, however, then the
>> > printout is
>> >
>> >  #<undefined>
>> >  #<undefined>
>> >
>> > That's because the optimizer, seeing no forward references, incorrectly
>> > converts the `letrec' to a `let*'.
>> >
>> > There's some logic in the optimizer to avoid a transformation from
>> > `letrec' to `let*' when a continuation might be captured, but it's
>> > obviously broken. I could fix it, but before I fix the optimizer for
>> > the current semantics, I wonder whether there's some way to specify the
>> > semantics of `letrec' so that a conversion to `let*' would be legal.
>> >
>> >
>> > 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*'. This is particularly true now that
>> > Racket's syntax lets you use internal definitions in so many places.
>> > For example, a quicksort core
>> >
>> >  (define (quicksort! vec n m)
>> >   (when (> (- m n) 1)
>> >     (let* ([around-val (vector-ref vec n)]
>> >            [pos (pivot around-val vec n m)])
>> >       (vector-set! vec pos pivot)
>> >       (quicksort! vec n pos)
>> >       (quicksort! vec (add1 pos) m))))
>> >
>> > is 15% faster (on a vector of 1000000 random numbers) than
>> >
>> >  (define (quicksort! vec n m)
>> >   (when (> (- m n) 1)
>> >     (define around-val (vector-ref vec n))
>> >     (define pos (pivot around-val vec n m))
>> >     (vector-set! vec pos around-val)
>> >     (quicksort! vec n pos)
>> >     (quicksort! vec (add1 pos) m)))
>> >
>> > With internal definitions, the compiler can't see enough of `pivot' to
>> > be sure that it won't capture a continuation, and so it heap-allocates
>> > a location for `pos'.
>> >
>> > R6RS addresses the problem by saying that an expression on the
>> > right-hand side of `letrec*' cannot return multiple times. In practice,
>> > I expect that means a compiler would convert `letrec*' to `let*'
>> > without checking the multiple-return constraint --- exploiting the
>> > usual "unspecified" trap door. Obviously, I'm not in favor of
>> > unspecified behavior. I also don't see how to make a single-return
>> > check efficient; it seems to require heap allocation.
>> >
>> >
>> > Any ideas?
>> >
>> > _________________________________________________
>> >  For list-related administrative tasks:
>> >  http://lists.racket-lang.org/listinfo/dev
>> >
>
> _________________________________________________
>  For list-related administrative tasks:
>  http://lists.racket-lang.org/listinfo/dev



-- 
sam th
samth at ccs.neu.edu