Tree data structure supporting functional manipulation
A system that allows walking and rewriting of parts of trees in a functional manner, along with translation of references to internal nodes that can be carried from one tree to its successors.
Implemented in a manner that is compatible with and depends upon FSet.
Design and Usage
To start, load this library (system name
:functional-trees) using Quicklisp:
This library defines one package,
:functional-trees, which we will refer to by
:ft. The main thing provided by
:ft is the
node class, an
object of which represents a node in a tree. Here are its slots:
(describe (make-instance 'ft:node))
#<FUNCTIONAL-TREES:NODE 0 NIL> [standard-object] Slots with :CLASS allocation: CHILD-SLOTS = NIL CHILD-SLOT-SPECIFIERS = #<unbound slot> Slots with :INSTANCE allocation: SERIAL-NUMBER = 0 ROOT-INFO = NIL SIZE = #<unbound slot> FINGER = NIL
child-slots slot holds a list of the slots that
actually hold children. Thus, since it holds the value
nil here, we see that
ft:node class can only really represent leaf nodes. Next we'll address
this by defining our own node class that can hold children. Afterward, we'll
discuss the other
In most cases it is likely that one would subclass the
provided by this package. Any subclass of
node can specify which of
its slots might hold subtrees by defining a
child-slots slot which
should be initialized to hold the names of these fields and should be
allocated on the class itself. See the following example.
(ft:define-node-class if-then-else-node (ft:node) ((ft:child-slots :initform '((then . 1) else) :allocation :class) (then :reader then :initarg :then :type ft:node) (else :reader else :initarg :else :type list)) (:documentation "An if-then-else subtree of a program AST."))
Note that we used
ft:define-node-class instead of just
defclass. The latter
would work, but the former also sets up some additional useful infrastructure
for our new
node subclass. This infrastructure is already defined generically
for all nodes, but the
ft:define-node-class macro defines it more efficiently
for a specific class of nodes.
Note also that the
:initarg keywords for
else are necessary, as
they are used by automatic tree-copying functions in this library. If they are
omitted, many functions (including the FSet generic sequence transformation
functions described below) will not work properly.
Each child slot should hold children nodes. Child slots may hold a
single node or multiple nodes. It is possible to specify the arity of
a child slot using the
child-slots class-level field. This changes
the behavior of relevant generic functions. E.g., the
then slot in
if-then-else-node above holds a single node child while the
slot may hold a list of any number of children.
In addition to customizing the functional-tree generic functions to
traverse your tree appropriately, defining
child-slots will cause
children function to be defined to return all children
of a newly defined node subclass--this is done by hooking the MOP
sub-class finalization process for sub-classes of
Thus if we create a node using our new class and give values to its
children function will return the list of those children
according to the order of the
(ft:children (make-instance 'if-then-else-node :else '(:foo :bar) :then :baz))
(:BAZ :FOO :BAR)
(In this particular example we eschewed the
:type annotations on the child
slots, for simplicity.)
"Functional" and "applicative"
The word "functional" usually means multiple things:
- Objects cannot be modified after they have been created (immutability).
- Functions always return the same results when given the same inputs (referential transparency).
(Note that the second condition implies the first.) This library satisfies the first condition but not the second, which is why we will sometimes use the word "applicative" instead of "functional". Also, we slightly relax our definition of immutability: because slots can be unbound, we do not consider an assignment to an unbound slot to be a mutation of the object. So rather than immutability meaning that the object never changes, it instead means that the object can only ever go upward in a lattice ordered by boundness of slots.
There is one exception to this definition of immutability: fingers. As shown by
node example, the
finger slot is initially set to
nil when a
node is created, and should only be set by the
(see below). Thus, a more accurate version of our definition of immutability
would replace "unbound" with "
nil" in the case of the
The reason we don't have referential transparency is that each newly created
node has a unique serial number:
(ft::serial-number (make-instance 'ft:node))
These serial numbers increase monotonically, and are used internally in the library for various algorithmic tasks. One important thing to note is that these serial numbers must be unique in any given tree in addition to being unique per node. That is, if you transform a tree by copying one of its subtrees to another location in the tree, you must clone that entire subtree to ensure that the new tree does not contain any duplicate serial numbers.
As the above examples show,
make-instance is fairly barebones: it sets the
serial-number but not much else. Because this library incorporates FSet,
though, we can extend the generic
convert function to provide an easier way to
construct our nodes (we will discuss
ft:populate-fingers in the next section):
(defmethod fset:convert ((to-type (eql 'if-then-else-node)) (sequence list) &key &allow-other-keys) (labels ((construct (form) (etypecase form (cons (make-instance 'if-then-else-node :then (construct (first form)) :else (mapcar #'construct (rest form)))) (atom (make-instance 'ft:node))))) (ft:populate-fingers (construct sequence))))
This method may be used to easily create a functional tree from a list.
(progn (defvar my-node (fset:convert 'if-then-else-node '((nil) nil))) (describe my-node))
#<IF-THEN-ELSE-NODE 7 (#<IF-THEN-ELSE-NODE 5 (#1=#<NODE 4 NIL>)> #1#.. [standard-object] Slots with :CLASS allocation: CHILD-SLOTS = ((THEN . 1) ELSE) CHILD-SLOT-SPECIFIERS = #<unbound slot> Slots with :INSTANCE allocation: SERIAL-NUMBER = 7 ROOT-INFO = NIL SIZE = #<unbound slot> FINGER = #<FUNCTIONAL-TREES:FINGER #<IF-THEN-ELSE-NODE 7 (#<IF-THEN-ELSE-NODE 5.. THEN = #<IF-THEN-ELSE-NODE 5 (#<NODE 4 NIL>)> ELSE = (#<FUNCTIONAL-TREES:NODE 6 NIL>)
Now we can round-trip from a
list to an
back, because this library already defines an
fset:convert method to
convert from nodes to lists, essentially a recursive version of
(ft::convert 'list my-node)
(#<IF-THEN-ELSE-NODE 7 (#<IF-THEN-ELSE-NODE 5 (#<NODE 4 NIL>)> #<NODE 4 NIL> #<NODE 6 NIL>)> #<IF-THEN-ELSE-NODE 5 (#<NODE 4 NIL>)> #<FUNCTIONAL-TREES:NODE 4 NIL> #<FUNCTIONAL-TREES:NODE 6 NIL>)
The convert functions to and from lists may be specialized for a particular subclass of node to achieve translation to and from functional trees which don't lose information. However, doing that in general is not possible without specific knowledge of the desired tree structure -- namely how the tree stores list values vs list strucure.
In the previous example, we constructed a small tree and then called
ft:populate-fingers on it. Let's take a look at one of these fingers:
(progn (defvar finger1 (ft:finger (then (then my-node)))) (describe finger1))
#<FUNCTIONAL-TREES:FINGER #<IF-THEN-ELSE-NODE 7 (#<IF-THEN-ELSE-NODE 5.. [standard-object] Slots with :INSTANCE allocation: NODE = #<IF-THEN-ELSE-NODE 7 (#<IF-THEN-ELSE-NODE 5 (#1=#<NODE 4 NIL>)> #1#.. PATH = (THEN THEN) RESIDUE = NIL CACHE = #<unbound slot>
From this we can see that a finger includes a pointer to the root of a tree (in
node) and a
path to another node in that tree. From these two pieces, it is
straightforward to follow
path, starting from the root
node, to find the
original node which held this
finger; once this lookup has been computed once,
finger can store the resulting
node in its
cache slot. The
to path transformations, which we will discuss in the next section.
Now let's look at one more finger:
(progn (defvar finger2 (ft:finger (first (else my-node)))) (describe finger2))
#<FUNCTIONAL-TREES:FINGER #<IF-THEN-ELSE-NODE 7 (#<IF-THEN-ELSE-NODE 5.. [standard-object] Slots with :INSTANCE allocation: NODE = #<IF-THEN-ELSE-NODE 7 (#<IF-THEN-ELSE-NODE 5 (#1=#<NODE 4 NIL>)> #1#.. PATH = ((ELSE . 0)) RESIDUE = NIL CACHE = #<unbound slot>
Because these two fingers were both created in the context of the same tree,
they both point to the same root
node. However, this one has a different
path to it: we took the first node in the
In general, a path in this library is a list where
- a symbol (e.g.
then) means to follow the child whose slot name is the given symbol, and
- a cons cell containing a symbol and a number means to follow the child with the given number as its index, in the slot whose name is the given symbol.
This library provides
ft:node implementations for the following generic
sequence functions from FSet:
It also provides a couple additional generic methods, also with implementations
mapctakes as arguments a function and a node, respectively. It calls the given function on every node in the tree of the given node, and then returns
mapcardoes the same thing as
mapc, except that it constructs a new tree from the results of all those function calls, and returns the newly constructed tree.
For example, we could expand an
if-then-else-nodeby adding an extra
(progn (defvar expanded (ft:mapcar (lambda (n) (if (typep n 'if-then-else-node) (make-instance 'if-then-else-node :then (then n) :else (list* (make-instance 'ft:node) (else n))) n)) my-node)) (describe expanded))
#<IF-THEN-ELSE-NODE 9 (#<IF-THEN-ELSE-NODE 11 (#1=#<NODE 4 NIL>.. [standard-object] Slots with :CLASS allocation: CHILD-SLOTS = ((THEN . 1) ELSE) CHILD-SLOT-SPECIFIERS = #<unbound slot> Slots with :INSTANCE allocation: SERIAL-NUMBER = 9 ROOT-INFO = #<FUNCTIONAL-TREES::ROOT-INFO #<IF-THEN-ELSE-NODE 7 (#<IF-THEN-ELSE-NO.. SIZE = #<unbound slot> FINGER = NIL THEN = #<IF-THEN-ELSE-NODE 11 (#<NODE 4 NIL> #<NODE 10 NIL>)> ELSE = (#<FUNCTIONAL-TREES:NODE 8 NIL> #<FUNCTIONAL-TREES:NODE 6 NIL>)
This library differs from a naive implementation of functional trees by efficiently handling the relationship between transformations on trees and transformations on paths.
When you transform a tree into another tree using this library, the latter
retains knowledge of the relationship to the former (its "predecessor") via its
(describe (ft:transform expanded))
#<FUNCTIONAL-TREES::PATH-TRANSFORM (((THEN THEN) (THEN THEN) LIVE).. [standard-object] Slots with :INSTANCE allocation: FROM = #<IF-THEN-ELSE-NODE 7 (#<IF-THEN-ELSE-NODE 5 (#1=#<NODE 4 NIL>)> #1#.. TRANSFORMS = (((THEN THEN) (THEN THEN) :LIVE) (((ELSE . 0)) ((ELSE . 1)) :LIVE))
Here we see that
expanded knows which tree it originally came
predecessor), and also stores some additional
transforms information. Since
expanded shares some structure with
transforms enable us to
take a path (that is, a finger) to a node in the
my-node tree and translate it
into a path (finger) to the same node in the
(defun show-expanded-finger (finger) (describe (ft:transform-finger-to finger (ft:transform expanded) expanded)))
Here's an example:
#<FUNCTIONAL-TREES:FINGER #<IF-THEN-ELSE-NODE 9 (#<IF-THEN-ELSE-NODE 1.. [standard-object] Slots with :INSTANCE allocation: NODE = #<IF-THEN-ELSE-NODE 9 (#<IF-THEN-ELSE-NODE 11 (#1=#<NODE 4 NIL>.. PATH = (THEN THEN) RESIDUE = NIL CACHE = #<unbound slot>
That example isn't particularly exciting, because the path to this node is the
same as it was before: it's still just the first child of the first child. We do
see that the root
node of the finger was changed to our new tree, though. But
we can also translate other paths:
#<FUNCTIONAL-TREES:FINGER #<IF-THEN-ELSE-NODE 9 (#<IF-THEN-ELSE-NODE 1.. [standard-object] Slots with :INSTANCE allocation: NODE = #<IF-THEN-ELSE-NODE 9 (#<IF-THEN-ELSE-NODE 11 (#1=#<NODE 4 NIL>.. PATH = ((ELSE . 1)) RESIDUE = NIL CACHE = #<unbound slot>
This path actually did change, because we added an extra
ft:node in the else
branch right before it.
This library is able to very efficiently compute these path transform objects: it only takes time O(n log n), where n is the number of newly allocated nodes in the transformed tree.
- Eliminate hard-coded children.
- Address all FIXMEs
- Address all #+broken
- Find should return the subtree.
- Define replacements for
- Integrate with FSet.
- Define a map-tree function.
- Ensure tests provide good coverage.
- Automatically define
convertmethods for subclasses of node.
- Consider hooking into the class definition mechanisms with the MOP to define copy-based setf setters for all fields on any child of a node.
- Eliminate 'data' as default key in trees.
- Make default equality test in tree methods be EQL, as on sequences.
- Add :START, :END for tree methods, where these are paths not integers.
- Back pointer to previous tree versions should be weak, if that is supported.
- Define copying setf expanders for non-class-allocated slots of node subclasses.
- Make trie maps switch to hash tables if the branching is too large (efficiency.)
- Cache PATH-TRANSFORM-OF.
- Enhance path transform compression so paths that differ only in the final index are compressed into "range" paths.
- Splice should report error on nodes of fixed arity.
- Make path transform algorithm more efficient with very long child lists.