Here you go!<p>A TXR Lisp macro <i>for-tree</i> for traversing a tree, given a variable, an expression for the root node, and expressions for how to to left and right relative to the variable.<p>A node structure that <i>for-tree</i> knows nothing about. No iterator abstraction or API, nothing.<p><pre><code> (defstruct node ()
value
left
right)
</code></pre>
Example tree (a balanced binary tree whose numeric values happen to be sorted):<p><pre><code> (defvar example-tree #S(node value 5
left #S(node value 3
left #S(node value 1)
right #S(node value 4))
right #S(node value 7
left #S(node value 6)
right #S(node value 9)))
</code></pre>
Walk it:<p><pre><code> (for-tree nod example-tree nod.left nod.right
(prinl nod.value))
1
3
4
5
6
7
9
</code></pre>
Code:<p><pre><code> (defmacro go-leftmost (var root left-expr stack)
^(for ((,var ,root)) (,var) ((set ,var ,left-expr))
(push ,var ,stack)))
(defmacro for-tree (var root left-expr right-expr . body)
(with-gensyms (stack node left right)
^(let (,stack)
(go-leftmost ,var ,root ,left-expr ,stack)
(for ((,var (pop ,stack)))
(,var)
((iflet ((,right ,right-expr))
(go-leftmost ,var ,right ,left-expr ,stack))
(set ,var (pop ,stack)))
,*body))))
</code></pre>
The <i>left-expr</i> and <i>right-expr</i> must be expressions that involve the <i>var</i> variable; the construct evaluates these to find the left or right child. When the value is <i>nil</i> it means there is no child.<p>This is almost exactly what the blog is asking for, transliterated to Lisp syntax.<p>Original concept in fantasy C syntax:<p><pre><code> for_tree(Node* N = mytreeroot; N != NULL; N : {N->left, N->right}
{
print(N->value);
}
</code></pre>
Lispified:<p><pre><code> (for-tree nod example-tree nod.left nod.right
(prinl nod.value))
</code></pre>
As required, the construct specifies the node variable to be the loop dummy, the root expression giving its initial value and the two accessor expressions for left and right traversal.<p>The termination test N != NULL is made implicit in the Lisp version, so early termination requires a break out of the loop. It could be arranged.<p>The fantasy C syntax specifies a variable name in the navigation declarator: N : { N->left, N->right }. Presumably, the variable here can be renamed to anything you want; it just arbitrarily happens to have the same name as the loop dummy.<p>I didn't replicate this feature exactly because it just adds verbosity for nothing. It's okay if the navigation declarator just refers to the loop's one and only dummy variable.<p>Anyway, programming languages should definitely not have a tree traversal primitive. Rather, languages should be Lisp.