On Fri, May 20, 2011 at 10:53 AM, Matthew Flatt <mfl...@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 <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 -- sam th sa...@ccs.neu.edu _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
