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]
substnewoldtree&key :test :test-not :key
subst-ifnewtesttree&key :key
subst-if-notnewtesttree&key :key

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

change_begin
X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9.
change_end

[Function]
nsubstnewoldtree&key :test :test-not :key
nsubst-ifnewtesttree&key :key
nsubst-if-notnewtesttree&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.

change_begin
X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9.
change_end

[Function]
sublisalisttree&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))

change_begin
X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9.
change_end

[Function]
nsublisalisttree&key :test :test-not :key

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

change_begin
X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9.
change_end

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

AI.Repository@cs.cmu.edu