[racket-dev] `letrec' and continuations

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 <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
> >