15.4 Substitution of Expressions

A number of functions are provided for performing substitutions within a tree. All take a tree and a description of old subexpressions to be replaced by new ones. They come in non-destructive and destructive varieties and specify substitution either by two arguments or by an association list.

The naming conventions for these functions and for their keyword arguments generally follow the conventions for the generic sequence functions. See chapter 14.

[Function] subst new old tree &key :test :test-not :key
[Function] subst-if new test tree &key :key
[Function] subst-if-not new test tree &key :key

(subst new old tree) makes a copy of tree, substituting new for every subtree or leaf of tree (whether the subtree or leaf is a car or a cdr of its parent) such that old and the subtree or leaf satisfy the test. It returns the modified copy of tree. The original tree is unchanged, but the result tree may share with parts of the argument tree.

For example:

(subst ’tempest ’hurricane
       ’(shakespeare wrote (the hurricane)))
    ⇒ (shakespeare wrote (the tempest))

(subst ’foo ’nil ’(shakespeare wrote (twelfth night)))
    ⇒ (shakespeare wrote (twelfth night . foo) . foo)

(subst ’(a . cons) ’(old . pair)
       ’((old . spice) ((old . shoes) old . pair) (old . pair))
       :test #’equal)
    ⇒ ((old . spice) ((old . shoes) a . cons) (a . cons))

This function is not destructive; that is, it does not change the car or cdr of any already existing list structure. One possible definition of subst:

(defun subst (old new tree &rest x &key test test-not key)
  (cond ((satisfies-the-test old tree :test test
                             :test-not test-not :key key)
         new)
        ((atom tree) tree)
        (t (let ((a (apply #’subst old new (car tree) x))
                 (d (apply #’subst old new (cdr tree) x)))
             (if (and (eql a (car tree))
                      (eql d (cdr tree)))
                 tree
                 (cons a d))))))

See also substitute, which substitutes for top-level elements of a sequence.

X3J13 voted in January 1989 to restrict user side effects; see section 7.9.

[Function] nsubst new old tree &key :test :test-not :key
[Function] nsubst-if new test tree &key :key
[Function] nsubst-if-not new test tree &key :key

nsubst is a destructive version of subst. The list structure of tree is altered by destructively replacing with new each leaf or subtree of the tree such that old and the leaf or subtree satisfy the test.

X3J13 voted in January 1989 to restrict user side effects; see section 7.9.

[Function] sublis alist tree &key :test :test-not :key

sublis makes substitutions for objects in a tree (a structure of conses). The first argument to sublis is an association list. The second argument is the tree in which substitutions are to be made, as for subst. sublis looks at all subtrees and leaves of the tree; if a subtree or leaf appears as a key in the association list (that is, the key and the subtree or leaf satisfy the test), it is replaced by the object with which it is associated. This operation is non-destructive. In effect, sublis can perform several subst operations simultaneously. For example:

(sublis ’((x . 100) (z . zprime))
        ’(plus x (minus g z x p) 4 . x))
    ⇒ (plus 100 (minus g zprime 100 p) 4 . 100)

(sublis ’(((+ x y) . (- x y)) ((- x y) . (+ x y)))
        ’(* (/ (+ x y) (+ x p)) (- x y))
        :test #’equal)
    ⇒ (* (/ (- x y) (+ x p)) (+ x y))

X3J13 voted in January 1989 to restrict user side effects; see section 7.9.

[Function] nsublis alist tree &key :test :test-not :key

nsublis is like sublis but destructively modifies the relevant parts of the tree.

X3J13 voted in January 1989 to restrict user side effects; see section 7.9.