[racket] Racket blog post: Fully Inlined Merge Sort

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?

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.

Does this only work on literal values?

On Fri, 24 Aug 2012 15:08:37 -0600, Neil Toronto <neil.toronto at gmail.com> wrote:
> I've posted to the Racket blog:
>
>    http://blog.racket-lang.org/2012/08/fully-inlined-merge-sort.html
>
> It shows how to use continuation-passing style in expansion-phase
> functions to fully inline a merge sort. The expanded code doesn't create
> any intermediate lists. Or a result list, for that matter.
>
> Neil ⊥
> ____________________
>   Racket Users list:
>   http://lists.racket-lang.org/users