2011/11/20

Two-argument reverse

Again I kept silence for over 4 months. I released 0.9.2 in August. Since then, quite a few changes are made into the development HEAD, and I'd like to start explaining them as I approach to release 0.9.3.

Some of the changes are small in the code, but can have great impact---meaning, it may change how you code in Gauche. However, they take a lot of words to explain; I need some more time.

For today, I pick a rather small topic to get up to the speed. It may even seem too trivial to mention, but somehow, it matters to me. Maybe because it is related to how I approach to a program.

★ ★ ★

A common pattern to transform a list is to tail-recurse the input with consing the results, and at the end reverse the result list to return:

  (let loop ([xs xs] [rs '()])
    (if (null? xs)
      (reverse rs)
      (loop (cdr xs) (cons (do-something (car xs)) rs))))

It is not necessarily a good style. Olin Shivers commented in his srfi-1 reference implementation that, this style is just trading execution stack for cons cells, and in stack-based system you should rather use a natural (non-tail) recursion:

  (let rec ([xs xs])
    (if (null? xs)
      '()
      (cons (do-something (car xs)) (rec (cdr xs)))))

In Gauche, the latter is just as fast as the former to a list up to about a thousand elements. However, if the input exceeds the limit and recursion gets too deep, Gauche starts moving the stack frames to the heap (a kind of stack GC), so it gets worse than using intermediate lists and reverse at the end. So I typically use cons-then-reverse idiom in Gauche.

Now, it is also common to write a function that adds the result to the existing pile of data. If we do non-tail recursive calls, it is trivial; I just replace () with the existing pile of data:

  (let rec ([xs xs])
    (if (null? xs)
      existing-pile-of-data
      (cons (do-something (car xs)) (rec (cdr xs)))))

If we use tail-recursive call and reverse, however, we need to reverse the accumulated results, then append the existing pile of data. Srfi-1 has a procedure specifically for this pattern, append-reverse:

  (let loop ([xs xs] [rs '()])
    (if (null? xs)
      (append-reverse rs previous-results)
      (loop (cdr xs) (cons (do-something (car xs)) rs))))

There's nothing wrong with this code; the append-reverse procedure is meant to avoid unnecessary copying. Except that I always feel something awkward in the name: I feel it somewhat miss the point by thinking the operation as "reverse, then append".

Look at this:

(reverse xs)             == (fold cons '() xs)
(append-reverse xs init) == (fold cons init xs)

It looks like reverse is really a special case of append-reverse with the init to be (). Thinking the operation as "reverse, then append" is actually upside-down. It may be more natural to think the operation represented by append-reverse as a fundamental one, and reverse is a shorthand for the special case.

Then, wouldn't it be reasonable to extend reverse this way?

(define (reverse xs :optional (tail '()))
  (fold cons tail xs))

If you stick to the idea that reverse is an operation to reverse the order of the given list, this extension seems contrived. However, how about thinking reverse as a list constructor, which happens to take initial content from xs but in the reverse order?

Actually, 0.9.2's reverse is already extended to take an optional tail argument, though it's not documented.

Tradition has great inertia, so I don't expect this extension gets widely accepted; after all, you can use srfi-1's append-reverse if you want this functionality. But I did get a little piece of mind with this extension.

Tags: reverse, srfi-1, append-reverse