Oh, I see it now. Thanks for the detailed explanation; I had misinterpreted earlier.
On Fri, 24 Aug 2012 21:14:48 -0600, Neil Toronto <neil.toro...@gmail.com> wrote: > On 08/24/2012 06:23 PM, Michael Wilber wrote: > > This is interesting, but I don't understand how moving cons around keeps > > it from allocating? In particular, why are the cons calls "evaluated at > > expansion time" when we may not even know the length of the list during > > macro expansion time? > > If I write (inline-sort a b c), then the macro certainly knows the > length of the syntax list #'(a b c) when it expands. > > The difference between evaluating conses at expansion time and > evaluating them at runtime is that, at expansion time, they contain the > *syntax* that gets evaluated at runtime. At runtime, they contain the > runtime values. We might use cons to build a syntax list like this: > > (cons #'values (cons #'a (cons #'b (cons #'c empty)))) > > which evaluates at expansion time to something more or less equivalent > to #'(values a b c). At runtime, #'values is evaluated, then #'a, then > #'b, then #'c, and finally the value of #'values is applied to the others. > > > Near the top of the post, it says the code "would be slow because cons > > allocates." But how does this: > > > > (define (list-add1/acc vs [acc (list)]) > > (match vs > > [(list) (reverse acc)] > > [(list v vs ...) > > (list-add1/acc vs (cons (add1 v) acc))])) > > > > ...make the code *faster*? The only thing we've done is move the > > recursive step into tail position; we haven't changed the fact that we > > still need to apply cons to the arguments. This also comes at the cost > > of introducing an expensive (reverse) step. > > That's a good question. In general, the fact that the recursive call is > tail-call-optimized more than makes up for the list reversal, making > accumulator-passing style faster. > > But that's not what I was after at all. (Probably a communication > failure on my part.) In that section, I was concentrating only on moving > the `cons' inward. I wanted to take the small step from something like this: > > (if (< a b) > (cons a (if ... (cons b ...) (cons c ...))) > (cons b (if ... (cons a ...) (cons c ...)))) > > to something like this: > > (if (< a b) > (if ... (cons a (cons b ...)) (cons a (cons c ...))) > (if ... (cons b (cons a ...)) (cons b (cons c ...)))) > > to group all those conses together before moving parts of the code to > the expansion phase. With them grouped, it's possible to transform them > into a `values' expression at expansion time. > > APS is a typical way to move conses inward, but it doesn't work on the > merge sort. CPS is a more general way to move conses from the outside of > an expression to the inside. > > > Does this only work on literal values? > > Heck no. :) It'd be useless to me if it did. > > I've been considering the best ways to make it work on literal values, > though. It's not unusual to want to sort something like (list a b 2 c). > > Neil ⊥ > > ____________________ Racket Users list: http://lists.racket-lang.org/users
