[racket] Racket blog post: Fully Inlined Merge Sort

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 ⊥