Another try at SUBST

[STEELE at CMU-20C]

How about this one?

(defun subst (old new tree @key test test-not key)
  (cond ((atom tree)
	 (if (satisfies-the-test old tree :test test :test-not test-not :key key)
	     new tree))
	(t (let ((a (subst old new (car tree) :test test :key key))
		 (d (subst old new (cdr tree) :test test :key key)))
	     (if (and (eq a (car tree)) (eq d (cdr tree)))
		 tree
		 (cons a d))))))

(defun satisfies-the-test (x y @key test test-not key)
  (if key
      (if test
	  (if test-not
	      <signal-error>
	      (funcall test x (funcall key y)))
	  (if test-not
	      (not (funcall test x (funcall key y)))
	      (eql x (funcall key y))))
      (if test
	  (if test-not
	      <signal-error>
	      (funcall test x y))
	  (if test-not
	      (not (funcall test x y))
	      (eql x y)))))

Actually, SATISFIES-THE-TEST might be useful to define for user use?
--Guy
-------