Common Lisp the Language, 2nd Edition

Next: Using Lists as Up: Lists Previous: Alteration of List

# 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
``subst-if new test tree &key :key
``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.

Compatibility note: In MacLisp, `subst` is guaranteed not to share with the tree argument, and the idiom `(subst `nil nil` x)` was used to copy a tree `x`. In Common Lisp, the function `copy-tree` should be used to copy a tree, as the `subst` idiom will not work.

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 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9.

[Function]
`nsubst new old tree &key :test :test-not :key
``nsubst-if new test tree &key :key
``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 (MAPPING-DESTRUCTIVE-INTERACTION) 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 (MAPPING-DESTRUCTIVE-INTERACTION) 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 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9.

Next: Using Lists as Up: Lists Previous: Alteration of List