[racket-dev] `letrec' and continuations

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
>