Deriving an Efficient Tree Traversal, Part I

In an attempt to live up to this blog's name, I'm going to spend the next few posts describing a series of transformations that derive an efficient implementation of a tree traversal suitable for imperative languages, starting from a natural, structural recursion in a language that isn't purposefully broken. This is mostly based on material from Mitch's Principles of Programming Languages course that all first-year Northeastern PhD students take--especially data abstraction, contexts, and continuations. This is great stuff, and it's worth learning.

The Problem

The problem we'll solve is to write a traversal of the DHTML DOM tree in a web page. The problem is useful and ubiquitous, but it's hard to solve in a language that doesn't like recursion. It's pretty well-known that you need to maintain an explicit stack to drive the traversal, but it's not obvious how to get it right. I could point out popular libraries that get it wrong, but I'll be polite.

For the sake of example, I'll simplify the problem somewhat: we'll represent DOM nodes as a simple structure:

;; tree = symbol × (listof tree)
(define-struct tree (tag children))

Leaf nodes are represented as trees with empty lists of children. We'll traverse the DOM in the style of CSS selectors, which are represented as an ancestry path of tags:

;; path = (listof selector)
;; selector = symbol

For example, the path '(foo bar) represents the set of all bar nodes that are descendants of foo nodes.

Natural Solution

The clearest implementation of the problem is a structural induction on the DOM tree and selector path (technically, the ordering is lexicographic over both inputs):

;; select : tree × path → (listof tree)
(define (select tree path)
  (cond
    [(null? path) (list tree)]
    [(matches? tree (car path))   ; does node's tag match first tag in path?
     (append (select tree (cdr path))
             (select* (children tree) path))]
    [else (select* (children tree) path)]))

;; select* : (listof tree) × path → (listof tree)
(define (select* trees path)
  (cond
    [(null? trees) null]
    [else (append (select (car trees) path)
                  (select* (cdr trees) path))]))

We have two distinct datatypes to recur on: tree and (listof tree), which leads to two separate functions. When we find a node that matches, we need to test it against the rest of the path as well; otherwise we just search its descendants. We only produce a match when we find a node that has matched the entire selector path.¹

CPS

The recursive solution uses the implicit control stack of Scheme to drive the traversal, but we want an explicit implementation. The easiest way to represent control is to CPS a program, so let's try that:

;; select/k : tree × path × ((listof tree) → (listof tree)) → (listof tree)
(define (select/k tree path k)
  (cond
    [(null? path) (k (list tree))]
    [(matches? tree (car path))
     (select/k tree (cdr path)
       (lambda (ts1)
         (select*/k (children tree) path
           (lambda (ts2)
             (k (append ts1 ts2))))))]
    [else (select*/k (children tree) path k)]))

;; select*/k : (listof tree) × path × ((listof tree) → (listof tree)) → (listof tree)
(define (select*/k trees path k)
  (cond
    [(null? trees) (k null)]
    [else (select/k (car trees) path
            (lambda (ts1)
              (select*/k (cdr trees) path
                (lambda (ts2)
                  (k (append ts1 ts2))))))]))

This no longer relies on the control stack of Scheme, because every function call is in tail position. However, it isn't a satisfying solution for an iterative language--even one with higher-order functions--because without proper tail calls, it will still use unbounded control space.

To be continued...

---

¹ For the sake of simplicity, I'm not going to worry about duplicate elements in the result list.