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
