[racket-dev] `letrec' and continuations

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?