I like the idea of adjusting the semantics of internal definitions and leaving `letrec' alone.
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 <mfl...@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