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
