[racket] Racket blog post: Fully Inlined Merge Sort

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.toronto at 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 ⊥
> 
>