The functional-trees Reference Manual

Table of Contents

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 Tue Dec 22 13:31:33 2020 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
  TRANSFORM                      = 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:

1. Objects cannot be modified after they have been created (immutability).
2. 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))

3

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)
             (if (consp form)
                 (make-instance 'if-then-else-node
                                :then (construct (first form))
                                :else (mapcar #'construct (rest form)))
                 (make-instance 'ft:node))))
    (ft:populate-fingers (construct sequence))))

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:

(progn
  (defvar my-node (fset:convert 'if-then-else-node '((nil) nil)))
  (describe my-node)
  (fset:convert 'list my-node))

#<IF-THEN-ELSE-NODE 7 ((NIL) NIL)>
  [standard-object]

Slots with :CLASS allocation:
  CHILD-SLOTS                    = ((THEN . 1) ELSE)
  CHILD-SLOT-SPECIFIERS          = #<unbound slot>
Slots with :INSTANCE allocation:
  SERIAL-NUMBER                  = 7
  TRANSFORM                      = NIL
  SIZE                           = #<unbound slot>
  FINGER                         = #<FUNCTIONAL-TREES:FINGER #<IF-THEN-ELSE-NODE 7 ((NIL) NIL)> NIL>
  THEN                           = #<IF-THEN-ELSE-NODE 5 (NIL)>
  ELSE                           = (#<FUNCTIONAL-TREES:NODE 6 NIL>)
((NIL) NIL)

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 ((NIL) NIL)> (THEN THE..
  [standard-object]

Slots with :INSTANCE allocation:
  NODE                           = #<IF-THEN-ELSE-NODE 7 ((NIL) NIL)>
  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 ((NIL) NIL)> ((ELSE..
  [standard-object]

Slots with :INSTANCE allocation:
  NODE                           = #<IF-THEN-ELSE-NODE 7 ((NIL) NIL)>
  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 ((NIL NIL) NIL NIL)>
    [standard-object]
  
  Slots with :CLASS allocation:
    CHILD-SLOTS                    = ((THEN . 1) ELSE)
    CHILD-SLOT-SPECIFIERS          = #<unbound slot>
  Slots with :INSTANCE allocation:
    SERIAL-NUMBER                  = 9
    TRANSFORM                      = #<IF-THEN-ELSE-NODE 7 ((NIL) NIL)>
    SIZE                           = #<unbound slot>
    FINGER                         = NIL
    THEN                           = #<IF-THEN-ELSE-NODE 11 (NIL 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 ((NIL) NIL)>
  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 ((NIL NIL) NIL NIL)> (..
  [standard-object]

Slots with :INSTANCE allocation:
  NODE                           = #<IF-THEN-ELSE-NODE 9 ((NIL NIL) NIL 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 ((NIL NIL) NIL NIL)> (..
  [standard-object]

Slots with :INSTANCE allocation:
  NODE                           = #<IF-THEN-ELSE-NODE 9 ((NIL NIL) NIL 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

lisp.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/lisp.lisp

Parent

functional-trees/functional-trees (system)

Location

functional-trees.lisp

Packages

functional-trees

Exported Definitions

• child-slot-specifiers (method)
• child-slots (method)
• children (generic function)
• children (method)
• children-alist (generic function)
• children-alist (method)
• children-slot-specifier-alist (generic function)
• children-slot-specifier-alist (method)
• copy (generic function)
• copy (method)
• copy (method)
• copy (method)
• copy (method)
• copy (method)
• copy (method)
• copy (method)
• copy-with-children-alist (generic function)
• copy-with-children-alist (method)
• define-methods-for-node-class (macro)
• define-node-class (macro)
• do-tree (macro)
• finger (method)
• finger (class)
• mapc (generic function)
• mapc (method)
• mapc (method)
• mapc (method)
• mapc (method)
• mapcar (generic function)
• mapcar (method)
• mapcar (method)
• mapcar (method)
• mapcar (method)
• mapcar (method)
• mapcar (method)
• node (method)
• node (class)
• path (method)
• path (type)
• path-equalp (generic function)
• path-equalp (method)
• path-equalp-butlast (generic function)
• path-equalp-butlast (method)
• path-later-p (generic function)
• path-later-p (method)
• path-later-p (method)
• path-later-p (method)
• path-later-p (method)
• path-later-p (method)
• path-later-p (method)
• path-later-p (method)
• populate-fingers (generic function)
• populate-fingers (method)
• populate-fingers (method)
• residue (method)
• swap (generic function)
• swap (method)
• swap (method)
• swap (method)
• swap (method)
• transform (method)
• transform (method)
• transform-finger-to (generic function)
• transform-finger-to (method)
• transform-finger-to (method)
• tree-copy (generic function)
• tree-copy (method)
• tree-copy (method)
• tree-copy (method)

Internal Definitions

• *node-obj-code* (special variable)
• assert (macro)
• cache (method)
• (setf cache) (method)
• check-transforms-for-cycle (function)
• child-list (function)
• cons-0-de (macro)
• copy-node-heap-data (function)
• data (method)
• (setf data) (method)
• descend (macro)
• dump (macro)
• encapsulate (function)
• equal? (generic function)
• equal? (method)
• equal? (method)
• expand-children-defmethod (function)
• expand-copying-setf-writers (function)
• expand-lookup-specialization (function)
• from (method)
• from (method)
• lexicographic-< (function)
• make-node-heap (function)
• make-node-heap-data (function)
• make-slot-specifier (function)
• make-trie (function)
• map-children (method)
• map-children (method)
• map-children/i (generic function)
• map-children/i (method)
• mapcar-children (generic function)
• mapcar-children (method)
• mapcar-children (method)
• node-can-implant (generic function)
• node-can-implant (method)
• node-heap (class)
• node-heap-add-children (generic function)
• node-heap-add-children (method)
• node-heap-data (structure)
• node-heap-data-< (function)
• node-heap-data-node (function)
• (setf node-heap-data-node) (function)
• node-heap-data-p (function)
• node-heap-data-path (function)
• (setf node-heap-data-path) (function)
• node-heap-data-size (function)
• (setf node-heap-data-size) (function)
• node-heap-data-sn (function)
• (setf node-heap-data-sn) (function)
• node-heap-index (type)
• node-heap-insert (function)
• node-heap-pop (function)
• node-heap-sift-down (function)
• node-heap-sift-up (function)
• node-heap/count (method)
• (setf node-heap/count) (method)
• node-heap/heap (method)
• (setf node-heap/heap) (method)
• node-valid (generic function)
• node-valid (method)
• node-values (generic function)
• node-values (method)
• nodes-disjoint (generic function)
• nodes-disjoint (method)
• parse-specialized-lambda-list (function)
• path-element-= (generic function)
• path-element-= (method)
• path-element-= (method)
• path-element-= (method)
• path-element-= (method)
• path-element-= (method)
• path-element-= (method)
• path-element-= (method)
• path-element-> (generic function)
• path-element-> (method)
• path-element-> (method)
• path-element-> (method)
• path-element-> (method)
• path-element-> (method)
• path-element-> (method)
• path-element-> (method)
• path-of-node (function)
• path-p (function)
• path-transform (class)
• path-transform-compress-mapping (function)
• path-transform-of (generic function)
• path-transform-of (method)
• predecessor-chain (generic function)
• predecessor-chain (method)
• prefix? (function)
• pure-traverse-tree (generic function)
• pure-traverse-tree (method)
• pure-traverse-tree (method)
• pure-traverse-tree/i (generic function)
• pure-traverse-tree/i (method)
• pure-traverse-tree/i (method)
• root (method)
• (setf root) (method)
• slot-position-in-node (generic function)
• slot-position-in-node (method)
• slot-spec-arity (function)
• slot-spec-of-slot (generic function)
• slot-spec-of-slot (method)
• slot-spec-slot (function)
• slot-specifier (class)
• slot-specifier-arity (method)
• slot-specifier-class (method)
• slot-specifier-for-slot (generic function)
• slot-specifier-for-slot (method)
• slot-specifier-for-slot (method)
• slot-specifier-slot (method)
• store-nodes (function)
• subst (generic function)
• subst (method)
• subst (method)
• subst-if (generic function)
• subst-if (method)
• subst-if (method)
• subst-if-not (generic function)
• subst-if-not (method)
• test-handler (macro)
• transform-finger (generic function)
• transform-finger (method)
• transform-finger-loop-error (condition)
• transform-finger-loop-error-nodes (method)
• transform-finger-loop-error-repeated-node (method)
• transform-path (generic function)
• transform-path (method)
• transform-path (method)
• transforms (method)
• transforms-to-trie (function)
• traverse-tree (generic function)
• traverse-tree (method)
• traverse-tree (method)
• trie (class)
• trie-insert (generic function)
• trie-insert (method)
• trie-map (method)
• (setf trie-map) (method)
• trie-node (class)
• update-predecessor-tree (generic function)
• update-predecessor-tree (method)
• update-predecessor-tree (method)
• vars-of-specialized-lambda-list (function)
• with-encapsulation (macro)

4 Packages

Packages are listed by definition order.

4.1 functional-trees

Prototype implementation of functional trees w. finger objects

Source

lisp.lisp (file)

Nicknames

• functional-trees/functional-trees
• ft

Use List

• cl-store
• iterate
• alexandria
• common-lisp

Exported Definitions

• child-slot-specifiers (generic function)
• child-slot-specifiers (method)
• child-slots (generic function)
• child-slots (method)
• children (generic function)
• children (method)
• children-alist (generic function)
• children-alist (method)
• children-slot-specifier-alist (generic function)
• children-slot-specifier-alist (method)
• copy (generic function)
• copy (method)
• copy (method)
• copy (method)
• copy (method)
• copy (method)
• copy (method)
• copy (method)
• copy-with-children-alist (generic function)
• copy-with-children-alist (method)
• define-methods-for-node-class (macro)
• define-node-class (macro)
• do-tree (macro)
• finger (generic function)
• finger (method)
• finger (class)
• mapc (generic function)
• mapc (method)
• mapc (method)
• mapc (method)
• mapc (method)
• mapcar (generic function)
• mapcar (method)
• mapcar (method)
• mapcar (method)
• mapcar (method)
• mapcar (method)
• mapcar (method)
• node (generic function)
• node (method)
• node (class)
• path (generic function)
• path (method)
• path (type)
• path-equalp (generic function)
• path-equalp (method)
• path-equalp-butlast (generic function)
• path-equalp-butlast (method)
• path-later-p (generic function)
• path-later-p (method)
• path-later-p (method)
• path-later-p (method)
• path-later-p (method)
• path-later-p (method)
• path-later-p (method)
• path-later-p (method)
• populate-fingers (generic function)
• populate-fingers (method)
• populate-fingers (method)
• residue (generic function)
• residue (method)
• swap (generic function)
• swap (method)
• swap (method)
• swap (method)
• swap (method)
• transform (generic function)
• transform (method)
• transform (method)
• transform-finger-to (generic function)
• transform-finger-to (method)
• transform-finger-to (method)
• tree-copy (generic function)
• tree-copy (method)
• tree-copy (method)
• tree-copy (method)

Internal Definitions

• *node-obj-code* (special variable)
• assert (macro)
• cache (generic function)
• cache (method)
• (setf cache) (method)
• (setf cache) (generic function)
• check-transforms-for-cycle (function)
• child-list (function)
• cons-0-de (macro)
• copy-node-heap-data (function)
• data (generic function)
• data (method)
• (setf data) (method)
• (setf data) (generic function)
• descend (macro)
• dump (macro)
• encapsulate (function)
• equal? (generic function)
• equal? (method)
• equal? (method)
• expand-children-defmethod (function)
• expand-copying-setf-writers (function)
• expand-lookup-specialization (function)
• from (generic function)
• from (method)
• from (method)
• lexicographic-< (function)
• make-node-heap (function)
• make-node-heap-data (function)
• make-slot-specifier (function)
• make-trie (function)
• map-children (generic function)
• map-children (method)
• map-children (method)
• map-children/i (generic function)
• map-children/i (method)
• mapcar-children (generic function)
• mapcar-children (method)
• mapcar-children (method)
• node-can-implant (generic function)
• node-can-implant (method)
• node-heap (class)
• node-heap-add-children (generic function)
• node-heap-add-children (method)
• node-heap-data (structure)
• node-heap-data-< (function)
• node-heap-data-node (function)
• (setf node-heap-data-node) (function)
• node-heap-data-p (function)
• node-heap-data-path (function)
• (setf node-heap-data-path) (function)
• node-heap-data-size (function)
• (setf node-heap-data-size) (function)
• node-heap-data-sn (function)
• (setf node-heap-data-sn) (function)
• node-heap-index (type)
• node-heap-insert (function)
• node-heap-pop (function)
• node-heap-sift-down (function)
• node-heap-sift-up (function)
• node-heap/count (generic function)
• node-heap/count (method)
• (setf node-heap/count) (method)
• (setf node-heap/count) (generic function)
• node-heap/heap (generic function)
• node-heap/heap (method)
• (setf node-heap/heap) (method)
• (setf node-heap/heap) (generic function)
• node-valid (generic function)
• node-valid (method)
• node-values (generic function)
• node-values (method)
• nodes-disjoint (generic function)
• nodes-disjoint (method)
• parse-specialized-lambda-list (function)
• path-element-= (generic function)
• path-element-= (method)
• path-element-= (method)
• path-element-= (method)
• path-element-= (method)
• path-element-= (method)
• path-element-= (method)
• path-element-= (method)
• path-element-> (generic function)
• path-element-> (method)
• path-element-> (method)
• path-element-> (method)
• path-element-> (method)
• path-element-> (method)
• path-element-> (method)
• path-element-> (method)
• path-of-node (function)
• path-p (function)
• path-transform (class)
• path-transform-compress-mapping (function)
• path-transform-of (generic function)
• path-transform-of (method)
• predecessor-chain (generic function)
• predecessor-chain (method)
• prefix? (function)
• pure-traverse-tree (generic function)
• pure-traverse-tree (method)
• pure-traverse-tree (method)
• pure-traverse-tree/i (generic function)
• pure-traverse-tree/i (method)
• pure-traverse-tree/i (method)
• root (generic function)
• root (method)
• (setf root) (method)
• (setf root) (generic function)
• slot-position-in-node (generic function)
• slot-position-in-node (method)
• slot-spec-arity (function)
• slot-spec-of-slot (generic function)
• slot-spec-of-slot (method)
• slot-spec-slot (function)
• slot-specifier (class)
• slot-specifier-arity (generic function)
• slot-specifier-arity (method)
• slot-specifier-class (generic function)
• slot-specifier-class (method)
• slot-specifier-for-slot (generic function)
• slot-specifier-for-slot (method)
• slot-specifier-for-slot (method)
• slot-specifier-slot (generic function)
• slot-specifier-slot (method)
• store-nodes (function)
• subst (generic function)
• subst (method)
• subst (method)
• subst-if (generic function)
• subst-if (method)
• subst-if (method)
• subst-if-not (generic function)
• subst-if-not (method)
• test-handler (macro)
• transform-finger (generic function)
• transform-finger (method)
• transform-finger-loop-error (condition)
• transform-finger-loop-error-nodes (generic function)
• transform-finger-loop-error-nodes (method)
• transform-finger-loop-error-repeated-node (generic function)
• transform-finger-loop-error-repeated-node (method)
• transform-path (generic function)
• transform-path (method)
• transform-path (method)
• transforms (generic function)
• transforms (method)
• transforms-to-trie (function)
• traverse-tree (generic function)
• traverse-tree (method)
• traverse-tree (method)
• trie (class)
• trie-insert (generic function)
• trie-insert (method)
• trie-map (generic function)
• trie-map (method)
• (setf trie-map) (method)
• (setf trie-map) (generic function)
• trie-node (class)
• update-predecessor-tree (generic function)
• update-predecessor-tree (method)
• update-predecessor-tree (method)
• vars-of-specialized-lambda-list (function)
• with-encapsulation (macro)

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

5.1 Exported definitions

5.1.1 Macros

Macro: define-methods-for-node-class CLASS-NAME

Package

functional-trees

Source

lisp.lisp (file)

Macro: define-node-class NAME SUPERCLASSES SLOTS &rest REST

Package

functional-trees

Source

lisp.lisp (file)

Macro: do-tree (VAR TREE &key INDEX REBUILD VALUE) &body BODY

Generalized tree traversal used to implement common lisp sequence functions. VALUE is the value to return upon completion. INDEX may hold a
variable bound in BODY to the *reversed* path leading to the current node. If REBUILD then the body should return the new node that will replace NODE, NODE itself if it is not to be replaced, and NIL if NODE is to be deleted (from a variable arity list of children in its parent.

Package

functional-trees

Source

lisp.lisp (file)

5.1.2 Generic functions

Generic Function: child-slot-specifiers OBJECT

Package

functional-trees

Methods

Method: child-slot-specifiers (NODE node)

The list CHILD-SLOTS
converted to a list of slot-specifier objects

Source

lisp.lisp (file)

Generic Function: child-slots OBJECT

Package

functional-trees

Methods

Method: child-slots (NODE node)

List of child slots with optional arity.
This field should be specified as :allocation :class if defined by a subclass of ‘node’. List of either symbols specifying a slot holding a list of children or a cons of (symbol . number) where number specifies a specific number of children held in the slot.

Source

lisp.lisp (file)

Generic Function: children NODE

Return all children of NODE.

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: children (NODE node)

Generic Function: children-alist NODE

Return an alist mapping child slots of NODE to their members.

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: children-alist (NODE node)

Generic Function: children-slot-specifier-alist NODE

Return an alist mapping child slot specifiers of NODE to their members

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: children-slot-specifier-alist (NODE node)

Generic Function: copy OBJ &key &allow-other-keys

Generic COPY method.

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: copy (NODE node) &rest KEYS

Method: copy OBJ &key &allow-other-keys

Method: copy (OBJ array) &key &allow-other-keys

Method: copy (OBJ hash-table) &key &allow-other-keys

Method: copy (OBJ list) &key &allow-other-keys

Method: copy (OBJ sequence) &key &allow-other-keys

Method: copy (OBJ symbol) &key &allow-other-keys

Generic Function: copy-with-children-alist OBJ CHILDREN-ALIST &rest ARGS

Perform a copy of node OBJ, with children-alist being used to initialize some children

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: copy-with-children-alist (OBJ node) (CHILDREN-ALIST list) &rest ARGS

Generic Function: finger OBJECT

Package

functional-trees

Methods

Method: finger (NODE node)

A finger back to the root of the (a?) tree.

Source

lisp.lisp (file)

Generic Function: mapc FUNCTION CONTAINER &rest MORE

Map FUNCTION over CONTAINER.

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: mapc FUNCTION (TREE node) &rest MORE

Method: mapc FUNCTION (NOTHING null) &rest MORE

Method: mapc FUNCTION ANYTHING &rest MORE

Method: mapc FUNCTION (SEQUENCE sequence) &rest MORE

Generic Function: mapcar FUNCTION CONTAINER &rest MORE

Map FUNCTION over CONTAINER.

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: mapcar FUNCTION (TREE node) &rest MORE

Method: mapcar FUNCTION (NOTHING null) &rest MORE

Method: mapcar FUNCTION ANYTHING &rest MORE

Method: mapcar FUNCTION (SEQUENCE sequence) &rest MORE

Method: mapcar PREDICATE (SEQ seq) &rest MORE &aux RESULT

Method: mapcar FUNCTION (SEQUENCE list) &rest MORE

Generic Function: node OBJECT

Package

functional-trees

Methods

Method: node (FINGER finger)

The node to which this finger pertains, considered as the root of a tree.

Source

lisp.lisp (file)

Generic Function: path OBJECT

Package

functional-trees

Methods

Method: path (FINGER finger)

A list of nonnegative integer values giving a path from node down to another node.

Source

lisp.lisp (file)

Generic Function: path-equalp PATH-A PATH-B

Are path-a and path-b the same path?

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: path-equalp PATH-A PATH-B

Generic Function: path-equalp-butlast PATH-A PATH-B

Are path-a and path-b the same, except possibly for their last entries?

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: path-equalp-butlast PATH-A PATH-B

Generic Function: path-later-p NODE PATH-A PATH-B

Does PATH-A from NODE represent an AST path after
PATH-B from NODE? Use this to sort AST asts for mutations that perform multiple operations.

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: path-later-p NODE (PATH-A null) (PATH-B null)

Method: path-later-p (NODE node) (PATH-A null) (PATH-B null)

Method: path-later-p NODE (PATH-A null) (PATH-B cons)

Method: path-later-p (NODE node) (PATH-A null) (PATH-B cons)

Method: path-later-p NODE (PATH-A cons) (PATH-B null)

Method: path-later-p (NODE node) (PATH-A cons) (PATH-B null)

Method: path-later-p NODE (PATH-A list) (PATH-B list)

Generic Function: populate-fingers ROOT &optional INITIAL-RPATH

Walk tree, creating fingers back to root. RPATH
is a reversed list of nodes to be prepended to each path.

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: populate-fingers (ROOT node) &optional INITIAL-RPATH

Method: populate-fingers (ROOT null) &optional INITIAL-RPATH

Generic Function: residue OBJECT

Package

functional-trees

Methods

Method: residue (FINGER finger)

If this finger was created from another
finger by a path-transform, some part of the path may not have been translated. If so, this field is the part that could not be handled. Otherwise, it is NIL.

Source

lisp.lisp (file)

Generic Function: swap TREE LOCATION-1 LOCATION-2

Swap the contents of LOCATION-1 and LOCATION-2 in TREE.

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: swap (TREE node) (LOCATION-1 list) (LOCATION-2 list)

Method: swap (TREE node) (LOCATION-1 node) LOCATION-2

Method: swap (TREE node) LOCATION-1 (LOCATION-2 node)

Method: swap (TREE node) LOCATION-1 LOCATION-2 around

Generic Function: transform OBJECT

Package

functional-trees

Methods

Method: transform (N node) around

Source

lisp.lisp (file)

Method: transform (NODE node)

If non-nil, is either a PATH-TRANSFORM object to this node, or the node that led to this node.

Source

lisp.lisp (file)

Generic Function: transform-finger-to F P TO

Converts a finger from one tree to another.

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: transform-finger-to (F finger) (P path-transform) (TO node)

Method: transform-finger-to (F finger) (P path-transform) (TO node) around

Generic Function: tree-copy OBJ

Copy method that descends into a tree and copies all its nodes.

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: tree-copy (NODE node)

Method: tree-copy OBJ

Method: tree-copy (OBJ list)

5.1.3 Classes

Class: finger ()

A wrapper for a path to get to a node

Package

functional-trees

Source

lisp.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• convert (method)
• print-object (method)
• lookup (method)
• transform-finger (method)
• transform-finger-to (method)
• transform-finger-to (method)
• slot-unbound (method)
• cache (method)
• cache (method)
• residue (method)
• path (method)
• node (method)

Direct slots

Slot: node

The node to which this finger pertains, considered as the root of a tree.

Type

functional-trees:node

Initargs

:node

Initform

(alexandria:required-argument :node)

Readers

node (generic function)

Slot: path

A list of nonnegative integer values giving a path from node down to another node.

Type

functional-trees:path

Initargs

:path

Initform

(alexandria:required-argument :path)

Readers

path (generic function)

Slot: residue

If this finger was created from another
finger by a path-transform, some part of the path may not have been translated. If so, this field is the part that could not be handled. Otherwise, it is NIL.

Type

list

Initargs

:residue

Readers

residue (generic function)

Slot: cache

Internal slot used to cache the lookup of a node.

Readers

cache (generic function)

Writers

(setf cache) (generic function)

Class: node ()

A node in a tree.

Package

functional-trees

Source

lisp.lisp (file)

Direct superclasses

identity-ordering-mixin (class)

Direct methods

• subst-if (method)
• subst (method)
• substitute (method)
• substitute-if-not (method)
• substitute-if (method)
• remove (method)
• remove-if-not (method)
• remove-if (method)
• remove-if (method)
• position (method)
• position-if-not (method)
• position-if (method)
• count (method)
• count-if-not (method)
• count-if (method)
• find (method)
• find-if-not (method)
• find-if (method)
• reduce (method)
• mapcar (method)
• mapc (method)
• convert (method)
• convert (method)
• node-values (method)
• print-object (method)
• swap (method)
• swap (method)
• swap (method)
• swap (method)
• insert (method)
• insert (method)
• insert (method)
• insert (method)
• insert (method)
• insert (method)
• splice (method)
• splice (method)
• splice (method)
• splice (method)
• splice (method)
• splice (method)
• less (method)
• less (method)
• less (method)
• less (method)
• less (method)
• less (method)
• with (method)
• with (method)
• with (method)
• with (method)
• with (method)
• with (method)
• lookup (method)
• lookup (method)
• lookup (method)
• lookup (method)
• lookup (method)
• lookup (method)
• equal? (method)
• path-transform-of (method)
• node-heap-add-children (method)
• node-can-implant (method)
• nodes-disjoint (method)
• node-valid (method)
• populate-fingers (method)
• transform-finger (method)
• transform-finger-to (method)
• transform-finger-to (method)
• predecessor-chain (method)
• mapcar-children (method)
• map-children (method)
• map-children/i (method)
• traverse-tree (method)
• update-predecessor-tree (method)
• pure-traverse-tree (method)
• pure-traverse-tree/i (method)
• tree-copy (method)
• copy (method)
• slot-unbound (method)
• transform (method)
• initialize-instance (method)
• children-slot-specifier-alist (method)
• children-alist (method)
• children (method)
• internal-store-object (method)
• copy-with-children-alist (method)
• path-later-p (method)
• path-later-p (method)
• path-later-p (method)
• path-element-> (method)
• slot-position-in-node (method)
• slot-spec-of-slot (method)
• slot-specifier-for-slot (method)
• slot-specifier-for-slot (method)
• slot-unbound (method)
• finger (method)
• child-slot-specifiers (method)
• child-slots (method)
• size (method)
• transform (method)

Direct slots

Slot: transform

If non-nil, is either a PATH-TRANSFORM object to this node, or the node that led to this node.

Type

(or null functional-trees:node functional-trees::path-transform weak-pointer)

Initargs

:transform

Readers

transform (generic function)

Slot: size

Number of nodes in tree rooted here.

Type

(integer 1)

Readers

size (generic function)

Slot: child-slots

List of child slots with optional arity.
This field should be specified as :allocation :class if defined by a subclass of ‘node’. List of either symbols specifying a slot holding a list of children or a cons of (symbol . number) where number specifies a specific number of children held in the slot.

Type

list

Allocation

:class

Readers

child-slots (generic function)

Slot: child-slot-specifiers

The list CHILD-SLOTS
converted to a list of slot-specifier objects

Type

list

Allocation

:class

Readers

child-slot-specifiers (generic function)

Slot: finger

A finger back to the root of the (a?) tree.

Type

(or null functional-trees:node functional-trees:finger)

Readers

finger (generic function)

5.1.4 Types

Type: path ()

Package

functional-trees

Source

lisp.lisp (file)

5.2 Internal definitions

5.2.1 Special variables

Special Variable: *node-obj-code*

Package

functional-trees

Source

lisp.lisp (file)

5.2.2 Macros

Macro: assert &body BODY

Package

functional-trees

Source

lisp.lisp (file)

Macro: cons-0-de (&rest SYMS) &body BODY

Package

functional-trees

Source

lisp.lisp (file)

Macro: descend (NAME &key OTHER-ARGS EXTRA-ARGS REPLACE SPLICE CHECKS) &body NEW

Define generic functions which descend (and return) through functional trees. This is useful to define standard FSet functions such as ‘with’,
‘less’, etc... Keyword arguments control specifics of how the
recursion works and how the generic functions are defined. OTHER-ARGS specifies additional arguments that are used. EXTRA-ARGS defines additional arguments that are not used. REPLACE is a boolean flagging
if NEW replaces the target or is added alongside the target. SPLICE
is a boolean flagging if NEW is inserted or spliced. CHECKS allows
for the specification of checks to run at the beginning of the
functions.

Package

functional-trees

Source

lisp.lisp (file)

Macro: dump &body FORMS

Package

functional-trees

Source

lisp.lisp (file)

Macro: test-handler FN

This macro is an idiom that occurs in many methods. It handles checking and normalization of :TEST and :TEST-NOT arguments.

Package

functional-trees

Source

lisp.lisp (file)

Macro: with-encapsulation TREE &body BODY

Package

functional-trees

Source

lisp.lisp (file)

5.2.3 Functions

Function: check-transforms-for-cycle START-NODE STOP-NODE

Check if the transform path from START-NODE has a cycle. The path stops at STOP-NODE, or at NIL

Package

functional-trees

Source

lisp.lisp (file)

Function: child-list NODE SLOT-SPEC

Package

functional-trees

Source

lisp.lisp (file)

Function: copy-node-heap-data INSTANCE

Package

functional-trees

Source

lisp.lisp (file)

Function: encapsulate TREE REWRITE-FN

Apply REWRITE-FN to TREE, producing a new tree. The new tree has its predecessor set to TREE.

Package

functional-trees

Source

lisp.lisp (file)

Function: expand-children-defmethod CLASS CHILD-SLOTS

Package

functional-trees

Source

lisp.lisp (file)

Function: expand-copying-setf-writers CLASS CHILD-SLOTS

Package

functional-trees

Source

lisp.lisp (file)

Function: expand-lookup-specialization CLASS CHILD-SLOTS

Package

functional-trees

Source

lisp.lisp (file)

Function: lexicographic-< LIST1 LIST2

Lexicographic comparison of lists of reals, symbols, or pairs. Symbols are considered to be less than reals, and symbols are compared with each other using fset:compare

Package

functional-trees

Source

lisp.lisp (file)

Function: make-node-heap ()

Package

functional-trees

Source

lisp.lisp (file)

Function: make-node-heap-data &key (NODE NODE) (SIZE SIZE) (PATH PATH) (SN SN)

Package

functional-trees

Source

lisp.lisp (file)

Function: make-slot-specifier &rest ARGS

Package

functional-trees

Source

lisp.lisp (file)

Function: make-trie ()

Package

functional-trees

Source

lisp.lisp (file)

Function: node-heap-data-< ND1 ND2

Package

functional-trees

Source

lisp.lisp (file)

Function: node-heap-data-node INSTANCE

Function: (setf node-heap-data-node) VALUE INSTANCE

Package

functional-trees

Source

lisp.lisp (file)

Function: node-heap-data-p OBJECT

Package

functional-trees

Source

lisp.lisp (file)

Function: node-heap-data-path INSTANCE

Function: (setf node-heap-data-path) VALUE INSTANCE

Package

functional-trees

Source

lisp.lisp (file)

Function: node-heap-data-size INSTANCE

Function: (setf node-heap-data-size) VALUE INSTANCE

Package

functional-trees

Source

lisp.lisp (file)

Function: node-heap-data-sn INSTANCE

Function: (setf node-heap-data-sn) VALUE INSTANCE

Package

functional-trees

Source

lisp.lisp (file)

Function: node-heap-insert NH NODE PATH

Package

functional-trees

Source

lisp.lisp (file)

Function: node-heap-pop NH

Package

functional-trees

Source

lisp.lisp (file)

Function: node-heap-sift-down HEAP COUNT

Package

functional-trees

Source

lisp.lisp (file)

Function: node-heap-sift-up HEAP I

Package

functional-trees

Source

lisp.lisp (file)

Function: parse-specialized-lambda-list LAMBDA-LIST

Similar to Alexandria’s PARSE-ORDINARY-LAMBDA-LIST, but can handle lambda lists for method argments.

Package

functional-trees

Source

lisp.lisp (file)

Function: path-of-node ROOT NODE

Package

functional-trees

Source

lisp.lisp (file)

Function: path-p LIST

Package

functional-trees

Source

lisp.lisp (file)

Function: path-transform-compress-mapping MAPPING

Internal function used to remove redundancy from a set of path mappings.

Package

functional-trees

Source

lisp.lisp (file)

Function: prefix? P1 P2

True if list P1 is a prefix of P2

Package

functional-trees

Source

lisp.lisp (file)

Function: slot-spec-arity SLOT-SPEC

Package

functional-trees

Source

lisp.lisp (file)

Function: slot-spec-slot SLOT-SPEC

Package

functional-trees

Source

lisp.lisp (file)

Function: store-nodes NODE TABLE

Package

functional-trees

Source

lisp.lisp (file)

Function: transforms-to-trie TRANSFORMS

Construct a trie for TRANSFORMS, which is a list as described in the transforms slot of PATH-TRANSFORMS objects.

Package

functional-trees

Source

lisp.lisp (file)

Function: vars-of-specialized-lambda-list LAMBDA-LIST

List of the variables bound by a lambda list

Package

functional-trees

Source

lisp.lisp (file)

5.2.4 Generic functions

Generic Function: cache OBJECT

Generic Function: (setf cache) NEW-VALUE OBJECT

Package

functional-trees

Methods

Method: cache (FINGER finger)

Method: (setf cache) NEW-VALUE (FINGER finger)

Internal slot used to cache the lookup of a node.

Source

lisp.lisp (file)

Generic Function: data OBJECT

Generic Function: (setf data) NEW-VALUE OBJECT

Package

functional-trees

Methods

Method: data (TRIE-NODE trie-node)

Method: (setf data) NEW-VALUE (TRIE-NODE trie-node)

Data for segments that end at this trie node, or NIL if no such segments end here.

Source

lisp.lisp (file)

Generic Function: equal? A B

Test equality of A and B.

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: equal? A B

Method: equal? (NODE1 node) (NODE2 node)

Generic Function: from OBJECT

Package

functional-trees

Methods

Method: from (X null)

Source

lisp.lisp (file)

Method: from (PATH-TRANSFORM path-transform)

automatically generated reader method

Source

lisp.lisp (file)

Generic Function: map-children NODE FN

Package

functional-trees

Methods

Method: map-children (NODE node) (FN function)

Source

lisp.lisp (file)

Method: map-children NODE (FN function)

Source

lisp.lisp (file)

Generic Function: map-children/i NODE INDEX FN

Call FN on each child of NODE, along with the INDEX augmented by the label of that child.

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: map-children/i (NODE node) (INDEX list) (FN function)

Generic Function: mapcar-children NODE FN

Apply traverse-children recursively to children of NODE, returning a plist suitable for passing to COPY

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: mapcar-children (NODE node) (FN function)

Method: mapcar-children NODE (FN function)

Generic Function: node-can-implant ROOT AT-NODE NEW-NODE

Check if new-node can the subtree rooted at at-node below ROOT and produce a valid tree.

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: node-can-implant (ROOT node) (AT-NODE node) (NEW-NODE node)

Generic Function: node-heap-add-children NH NODE PATH

Add the children of NODE to the node heap NH. PATH is the path to NODE.

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: node-heap-add-children NH (NODE node) (PATH list)

Generic Function: node-heap/count OBJECT

Generic Function: (setf node-heap/count) NEW-VALUE OBJECT

Package

functional-trees

Methods

Method: node-heap/count (NODE-HEAP node-heap)

automatically generated reader method

Source

lisp.lisp (file)

Method: (setf node-heap/count) NEW-VALUE (NODE-HEAP node-heap)

automatically generated writer method

Source

lisp.lisp (file)

Generic Function: node-heap/heap OBJECT

Generic Function: (setf node-heap/heap) NEW-VALUE OBJECT

Package

functional-trees

Methods

Method: node-heap/heap (NODE-HEAP node-heap)

automatically generated reader method

Source

lisp.lisp (file)

Method: (setf node-heap/heap) NEW-VALUE (NODE-HEAP node-heap)

automatically generated writer method

Source

lisp.lisp (file)

Generic Function: node-valid NODE

True if the tree rooted at NODE have EQL unique
serial-numbers, and no node occurs on two different paths in the tree

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: node-valid (NODE node)

Generic Function: node-values NODE

Returns multiple values that are used by
CONVERT ’LIST to append to the beginning of the list representation of a node.

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: node-values (NODE node)

Generic Function: nodes-disjoint NODE1 NODE2

Return true if NODE1 and NODE2 do not share any serial-number

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: nodes-disjoint (NODE1 node) (NODE2 node)

Generic Function: path-element-= A B

Equality function for elements of a path, taking into account the representation of named children

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: path-element-= (A real) (B real)

Method: path-element-= (A cons) (B real)

Method: path-element-= (A real) (B cons)

Method: path-element-= (A symbol) (B symbol)

Method: path-element-= (A symbol) B

Method: path-element-= A (B symbol)

Method: path-element-= (A cons) (B cons)

Generic Function: path-element-> NODE A B

Ordering function for elements of paths

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: path-element-> NODE (A real) (B real)

Method: path-element-> (NODE node) (A cons) (B cons)

Method: path-element-> NODE (A symbol) (B symbol)

Method: path-element-> NODE (A symbol) B

Method: path-element-> NODE A (B symbol)

Method: path-element-> NODE (A cons) (B real)

Method: path-element-> NODE (A real) (B cons)

Generic Function: path-transform-of FROM-NODE TO-NODE

Produce a path transform that maps FROM-NODE to TO-NODE

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: path-transform-of (ORIG-FROM node) (TO node)

Generic Function: predecessor-chain N

REturns the list of predecessor trees of N

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: predecessor-chain (N node)

Generic Function: pure-traverse-tree NODE FN

Traverse tree at and below NODE in preorder, calling FN on each node.

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: pure-traverse-tree (NODE node) (FN function)

Method: pure-traverse-tree NODE (FN function)

Generic Function: pure-traverse-tree/i NODE INDEX FN

Traverse tree below NODE in preorder, calling
FN on each node (and with the reversed path INDEX to that node).

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: pure-traverse-tree/i (NODE node) (INDEX list) (FN function)

Method: pure-traverse-tree/i NODE (INDEX list) (FN function)

Generic Function: root OBJECT

Generic Function: (setf root) NEW-VALUE OBJECT

Package

functional-trees

Methods

Method: root (TRIE trie)

automatically generated reader method

Source

lisp.lisp (file)

Method: (setf root) NEW-VALUE (TRIE trie)

automatically generated writer method

Source

lisp.lisp (file)

Generic Function: slot-position-in-node NODE SLOT

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: slot-position-in-node (NODE node) (SLOT symbol)

Generic Function: slot-spec-of-slot OBJ SLOT &optional ERROR?

Returns the slot spec pair of a slot in OBJ. If ERROR? is
true (the default) signal an error if SLOT is not a child slot of OBJ. Otherwise, in that case return NIL.

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: slot-spec-of-slot (OBJ node) (SLOT symbol) &optional ERROR?

Generic Function: slot-specifier-arity OBJECT

Package

functional-trees

Methods

Method: slot-specifier-arity (SLOT-SPECIFIER slot-specifier)

The arity of the slot

Source

lisp.lisp (file)

Generic Function: slot-specifier-class OBJECT

Package

functional-trees

Methods

Method: slot-specifier-class (SLOT-SPECIFIER slot-specifier)

The class to which the slot belongs

Source

lisp.lisp (file)

Generic Function: slot-specifier-for-slot OBJ SLOT &optional ERROR?

Returns the child slot SLOT in node OBJ. If it is not
the name of a child slot, return NIL if error? is NIL and error if error? is true (the default.)

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: slot-specifier-for-slot (OBJ node) (SLOT slot-specifier) &optional ERROR?

Method: slot-specifier-for-slot (OBJ node) (SLOT symbol) &optional ERROR?

Generic Function: slot-specifier-slot OBJECT

Package

functional-trees

Methods

Method: slot-specifier-slot (SLOT-SPECIFIER slot-specifier)

The name of the slot

Source

lisp.lisp (file)

Generic Function: subst NEW OLD TREE &key KEY TEST TEST-NOT &allow-other-keys

If TREE is a cons, this simply calls ‘cl:subst’. Also works on a functional tree node.

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: subst NEW OLD (TREE cons) &key KEY TEST TEST-NOT

Method: subst NEW OLD (TREE node) &rest REST &key &allow-other-keys

Generic Function: subst-if NEW TEST TREE &key KEY &allow-other-keys

If TREE is a cons, this simply calls ‘cl:subst-if’. Also works on a functional tree node.

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: subst-if NEW TEST (TREE cons) &key KEY

Method: subst-if NEW TEST (TREE node) &rest REST &key &allow-other-keys

Generic Function: subst-if-not NEW TEST TREE &key KEY

If TREE is a cons, this simply calls ‘cl:subst-if’. Also works on a functional tree node.

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: subst-if-not NEW TEST TREE &key KEY

Generic Function: transform-finger FINGER NODE &key ERROR-P

Transforms FINGER, producing a new finger that
points through the root NODE. NODE must be derived from the tree that FINGER is pointed through.

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: transform-finger (F finger) (NODE node) &key ERROR-P

Generic Function: transform-finger-loop-error-nodes CONDITION

Package

functional-trees

Methods

Method: transform-finger-loop-error-nodes (CONDITION transform-finger-loop-error)

Source

lisp.lisp (file)

Generic Function: transform-finger-loop-error-repeated-node CONDITION

Package

functional-trees

Methods

Method: transform-finger-loop-error-repeated-node (CONDITION transform-finger-loop-error)

Source

lisp.lisp (file)

Generic Function: transform-path PATH TRANSFORMS

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: transform-path (PATH list) (TRANSFORMS list)

Method: transform-path (ORIG-PATH list) (TRIE trie)

Generic Function: transforms OBJECT

Package

functional-trees

Methods

Method: transforms (PATH-TRANSFORM path-transform)

A list of (<path-set> <path> <status>) triples
where <path-set> is a path set, <path> is the mapping of the initial path in that <path-set>, and <status> is one of :live :dead. These should be sorted into non-increasing order of length of <path>. If missing, compute from the source/target node pair, if possible.

Source

lisp.lisp (file)

Generic Function: traverse-tree NODE FN

Traverse tree rooted at NODE in preorder.
At each node, call FN. If the first value returned is true, replaced node by the second returned value and continued the traversal. If any child is replaced also replace the parent node (as the trees are applicative.)

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: traverse-tree (NODE node) (FN function)

Method: traverse-tree NODE (FN function)

Generic Function: trie-insert TRIE SEGMENT DATA

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: trie-insert (TRIE trie) (SEGMENT list) DATA

Generic Function: trie-map OBJECT

Generic Function: (setf trie-map) NEW-VALUE OBJECT

Package

functional-trees

Methods

Method: trie-map (TRIE-NODE trie-node)

Method: (setf trie-map) NEW-VALUE (TRIE-NODE trie-node)

Alist mapping indices to trie nodes

Source

lisp.lisp (file)

Generic Function: update-predecessor-tree OLD-TREE NEW-TREE

Sets the back pointer of NEW-TREE to be OLD-TREE, if NEW-TREE lacks a back pointer. Returns NEW-TREE.

Package

functional-trees

Source

lisp.lisp (file)

Methods

Method: update-predecessor-tree (OLD-TREE node) (NEW-TREE node)

Method: update-predecessor-tree OLD-TREE NEW-TREE

5.2.5 Conditions

Condition: transform-finger-loop-error ()

Error thrown when TRANSFORM-FINGER finds a cycle in the FROM links

Package

functional-trees

Source

lisp.lisp (file)

Direct superclasses

error (condition)

Direct methods

• transform-finger-loop-error-repeated-node (method)
• transform-finger-loop-error-nodes (method)

Direct slots

Slot: nodes

Initargs

:nodes

Initform

(quote nil)

Readers

transform-finger-loop-error-nodes (generic function)

Slot: repeated-node

Initargs

:repeated-node

Initform

(quote nil)

Readers

transform-finger-loop-error-repeated-node (generic function)

5.2.6 Structures

Structure: node-heap-data ()

Package

functional-trees

Source

lisp.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots

Slot: node

Readers

node-heap-data-node (function)

Writers

(setf node-heap-data-node) (function)

Slot: size

Initform

0

Readers

node-heap-data-size (function)

Writers

(setf node-heap-data-size) (function)

Slot: path

Readers

node-heap-data-path (function)

Writers

(setf node-heap-data-path) (function)

Slot: sn

Initform

0

Readers

node-heap-data-sn (function)

Writers

(setf node-heap-data-sn) (function)

5.2.7 Classes

Class: node-heap ()

Max heaps for path-transform computation

Package

functional-trees

Source

lisp.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• node-heap/count (method)
• node-heap/count (method)
• node-heap/heap (method)
• node-heap/heap (method)

Direct slots

Slot: heap

Type

simple-vector

Initform

(make-array (quote (10)))

Readers

node-heap/heap (generic function)

Writers

(setf node-heap/heap) (generic function)

Slot: count

Type

(integer 0)

Initform

0

Readers

node-heap/count (generic function)

Writers

(setf node-heap/count) (generic function)

Class: path-transform ()

An object used to rewrite fingers from one tree to another.

Package

functional-trees

Source

lisp.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• print-object (method)
• transform-finger-to (method)
• transform-finger-to (method)
• transforms (method)
• from (method)

Direct slots

Slot: from

Type

functional-trees:node

Initargs

:from

Initform

(alexandria:required-argument :from)

Readers

from (generic function)

Slot: transforms

A list of (<path-set> <path> <status>) triples
where <path-set> is a path set, <path> is the mapping of the initial path in that <path-set>, and <status> is one of :live :dead. These should be sorted into non-increasing order of length of <path>. If missing, compute from the source/target node pair, if possible.

Type

list

Initargs

:transforms

Readers

transforms (generic function)

Class: slot-specifier ()

Object that represents the slots of a class

Package

functional-trees

Source

lisp.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• print-object (method)
• slot-specifier-for-slot (method)
• slot-specifier-arity (method)
• slot-specifier-slot (method)
• slot-specifier-class (method)

Direct slots

Slot: class

The class to which the slot belongs

Initargs

:class

Readers

slot-specifier-class (generic function)

Slot: slot

The name of the slot

Type

symbol

Initargs

:slot

Readers

slot-specifier-slot (generic function)

Slot: arity

The arity of the slot

Type

(integer 0)

Initargs

:arity

Readers

slot-specifier-arity (generic function)

Class: trie ()

Package

functional-trees

Source

lisp.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• transform-path (method)
• trie-insert (method)
• root (method)
• root (method)

Direct slots

Slot: root

Type

functional-trees::trie-node

Initargs

:root

Readers

root (generic function)

Writers

(setf root) (generic function)

Class: trie-node ()

Package

functional-trees

Source

lisp.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• trie-map (method)
• trie-map (method)
• data (method)
• data (method)

Direct slots

Slot: data

Data for segments that end at this trie node, or NIL if no such segments end here.

Initargs

:data

Readers

data (generic function)

Writers

(setf data) (generic function)

Slot: map

Alist mapping indices to trie nodes

Type

list

Initargs

:map

Readers

trie-map (generic function)

Writers

(setf trie-map) (generic function)

5.2.8 Types

Type: node-heap-index ()

Package

functional-trees

Source

lisp.lisp (file)

Appendix A Indexes

A.1 Concepts

A.2 Functions