The functional-trees Reference Manual

This is the functional-trees Reference Manual, version 0.0.0, generated automatically by Declt version 3.0 "Montgomery Scott" on Mon Apr 19 16:07:35 2021 GMT+0.

1 Introduction

Functional Trees

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:

(ql:quickload :functional-trees)

This library defines one package, :functional-trees, which we will refer to by its nickname :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

The :class-allocated child-slots slot holds a list of the slots that actually hold children. Thus, since it holds the value nil here, we see that the raw 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 ft:node slots.

Sub-classing the `node` class

In most cases it is likely that one would subclass the node class 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 then and 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 else 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 the generic 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 node.

Thus if we create a node using our new class and give values to its child-slots, the children function will return the list of those children according to the order of the child-slots list:

(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 our first node example, the finger slot is initially set to nil when a node is created, and should only be set by the ft:populate-fingers function (see below). Thus, a more accurate version of our definition of immutability would replace "unbound" with "nil" in the case of the finger slot.

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.

Constructing trees

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 if-then-else-node and back, because this library already defines an fset:convert method to convert from nodes to lists, essentially a recursive version of ft:children.

(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.

Fingers

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 residue relates 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 else branch.

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.

Transformations

This library provides ft:node implementations for the following generic sequence functions from FSet:

reduce
find-if
find-if-not
find
count-if
count-if-not
count
position-if
position-if-not
position
remove-if
remove-if-not
remove
substitute-if
substitute-if-not
substitute

It also provides a couple additional generic methods, also with implementations for ft:node:

mapc takes 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 nil.

mapcar does 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-node by adding an extra ft:node to every else branch:

(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>)

Path transforms

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 transform slot:

(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 from (the predecessor), and also stores some additional transforms information. Since expanded shares some structure with my-node, these 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 expanded tree:

(defun show-expanded-finger (finger)
  (describe (ft:transform-finger-to finger
                                    (ft:transform expanded)
                                    expanded)))

Here's an example:

(show-expanded-finger finger1)

#<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:

(show-expanded-finger finger2)

#<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.

Tasks

[X] Eliminate hard-coded children.
[X] Address all FIXMEs
[X] Address all #+broken
[X] Find should return the subtree.
[X] Define replacements for cl:subst and friends.
[X] Integrate with FSet.
[X] Define a map-tree function.
[X] Replace update-tree with map-tree
[X] Ensure tests provide good coverage.
[ ] Automatically define convert methods for subclasses of node.
[X] 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.
[X] Eliminate 'data' as default key in trees.
[X] 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.

2 Systems

The main system appears first, followed by any subsystem dependency.

2.1 `functional-trees`

Author: GrammaTech
License: MIT
Description: Tree data structure supporting functional manipulation
Long Description: Tree data structure supporting functional (or
applicative) manipulation. This system allows the 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.
Version: 0.0.0
Defsystem Dependency: asdf-package-system
Dependency: functional-trees/functional-trees (system)
Source: functional-trees.asd (file)

2.2 `functional-trees/functional-trees`

Author

GrammaTech

License

MIT

Dependencies

alexandria
iterate
cl-store
fset
closer-mop

Source

functional-trees.asd (file)

Component

file-type.lisp (file)

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.

3.1 Lisp

3.1.1 `functional-trees.asd`

Location

functional-trees.asd

Systems

functional-trees (system)
functional-trees/functional-trees (system)

3.1.2 `functional-trees/functional-trees/file-type.lisp`

Parent

functional-trees/functional-trees (system)

Location

functional-trees.lisp

Packages

• Introduction		What functional-trees is all about
• Systems		The systems documentation
• Files		The files documentation
• Packages		The packages documentation
• Definitions		The symbols documentation
• Indexes		Concepts, functions, variables and data types

• The functional-trees system
• The functional-trees/functional-trees system

• The functional-trees.asd file
• The functional-trees/functional-trees/file-type.lisp file

• Exported special variables
• Exported macros
• Exported generic functions
• Exported classes
• Exported types

• Internal special variables
• Internal macros
• Internal functions
• Internal generic functions
• Internal conditions
• Internal structures
• Internal classes
• Internal types

• Concept index
• Function index
• Variable index
• Data type index

	Index Entry	Section

F
	File, Lisp, `functional-trees.asd`:	The functional-trees․asd file
	File, Lisp, `functional-trees/functional-trees/file-type.lisp`:	The functional-trees/functional-trees/file-type․lisp file
	`functional-trees.asd`:	The functional-trees․asd file
	`functional-trees/functional-trees/file-type.lisp`:	The functional-trees/functional-trees/file-type․lisp file

L
	Lisp File, `functional-trees.asd`:	The functional-trees․asd file
	Lisp File, `functional-trees/functional-trees/file-type.lisp`:	The functional-trees/functional-trees/file-type․lisp file

	Index Entry	Section

*
	`cache-path-transforms?`:	Exported special variables
	`node-obj-code`:	Internal special variables
	`path-transform-cache`:	Internal special variables

A
	`arity`:	Internal classes

C
	`cache`:	Exported classes
	`child-slot-specifiers`:	Exported classes
	`child-slots`:	Exported classes
	`class`:	Internal classes
	`count`:	Internal classes

D
	`data`:	Internal classes

F
	`finger`:	Exported classes
	`from`:	Internal classes

H
	`heap`:	Internal classes

M
	`map`:	Internal classes

N
	`node`:	Exported classes
	`node`:	Internal structures
	`nodes`:	Internal conditions

P
	`path`:	Exported classes
	`path`:	Internal structures

R
	`repeated-node`:	Internal conditions
	`residue`:	Exported classes
	`root`:	Internal classes
	`root-info`:	Exported classes

S
	`size`:	Exported classes
	`size`:	Internal structures
	`slot`:	Internal classes
	`Slot, arity`:	Internal classes
	`Slot, cache`:	Exported classes
	`Slot, child-slot-specifiers`:	Exported classes
	`Slot, child-slots`:	Exported classes
	`Slot, class`:	Internal classes
	`Slot, count`:	Internal classes
	`Slot, data`:	Internal classes
	`Slot, finger`:	Exported classes
	`Slot, from`:	Internal classes
	`Slot, heap`:	Internal classes
	`Slot, map`:	Internal classes
	`Slot, node`:	Exported classes
	`Slot, node`:	Internal structures
	`Slot, nodes`:	Internal conditions
	`Slot, path`:	Exported classes
	`Slot, path`:	Internal structures
	`Slot, repeated-node`:	Internal conditions
	`Slot, residue`:	Exported classes
	`Slot, root`:	Internal classes
	`Slot, root-info`:	Exported classes
	`Slot, size`:	Exported classes
	`Slot, size`:	Internal structures
	`Slot, slot`:	Internal classes
	`Slot, sn`:	Internal structures
	`Slot, transform`:	Internal classes
	`Slot, transforms`:	Internal classes
	`sn`:	Internal structures
	`Special Variable, cache-path-transforms?`:	Exported special variables
	`Special Variable, node-obj-code`:	Internal special variables
	`Special Variable, path-transform-cache`:	Internal special variables

T
	`transform`:	Internal classes
	`transforms`:	Internal classes

	Index Entry	Section

C
	`Class, finger`:	Exported classes
	`Class, node`:	Exported classes
	`Class, node-heap`:	Internal classes
	`Class, path-transform`:	Internal classes
	`Class, root-info`:	Internal classes
	`Class, slot-specifier`:	Internal classes
	`Class, trie`:	Internal classes
	`Class, trie-node`:	Internal classes
	`Condition, transform-finger-loop-error`:	Internal conditions

F
	`finger`:	Exported classes
	`functional-trees`:	The functional-trees system
	`functional-trees`:	The functional-trees package
	`functional-trees/functional-trees`:	The functional-trees/functional-trees system

N
	`node`:	Exported classes
	`node-heap`:	Internal classes
	`node-heap-data`:	Internal structures
	`node-heap-index`:	Internal types

P
	`Package, functional-trees`:	The functional-trees package
	`path`:	Exported types
	`path-transform`:	Internal classes

R
	`root-info`:	Internal classes

S
	`slot-specifier`:	Internal classes
	`Structure, node-heap-data`:	Internal structures
	`System, functional-trees`:	The functional-trees system
	`System, functional-trees/functional-trees`:	The functional-trees/functional-trees system

T
	`transform-finger-loop-error`:	Internal conditions
	`trie`:	Internal classes
	`trie-node`:	Internal classes
	`Type, node-heap-index`:	Internal types
	`Type, path`:	Exported types

The functional-trees Reference Manual

Table of Contents

The functional-trees Reference Manual

1 Introduction

Functional Trees

Design and Usage

Sub-classing the node class

"Functional" and "applicative"

Constructing trees

Fingers

Transformations

Path transforms

Tasks

2 Systems

2.1 functional-trees

2.2 functional-trees/functional-trees

3 Files

3.1 Lisp

3.1.1 functional-trees.asd

3.1.2 functional-trees/functional-trees/file-type.lisp

4 Packages

4.1 functional-trees

5 Definitions

5.1 Exported definitions

5.1.1 Special variables

5.1.2 Macros

5.1.3 Generic functions

5.1.4 Classes

5.1.5 Types

5.2 Internal definitions

5.2.1 Special variables

5.2.2 Macros

5.2.3 Functions

5.2.4 Generic functions

5.2.5 Conditions

5.2.6 Structures

5.2.7 Classes

5.2.8 Types

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types

Sub-classing the `node` class

2.1 `functional-trees`

2.2 `functional-trees/functional-trees`

3.1.1 `functional-trees.asd`

3.1.2 `functional-trees/functional-trees/file-type.lisp`

4.1 `functional-trees`