+;; SUBLIS
+(test (equal (sublis '((x . 100) (z . zprime))
+ '(plus x (minus g z x p) 4 . x))
+ '(PLUS 100 (MINUS G ZPRIME 100 P) 4 . 100)))
+(test (equal (sublis '(((+ x y) . (- x y)) ((- x y) . (+ x y)))
+ '(* (/ (+ x y) (+ x p)) (- x y))
+ :test #'equal)
+ '(* (/ (- X Y) (+ X P)) (+ X Y))))
+(let ((tree1 '(1 (1 2) ((1 2 3)) (((1 2 3 4))))))
+ (test (equal (sublis '((3 . "three")) tree1)
+ '(1 (1 2) ((1 2 "three")) (((1 2 "three" 4))))))
+ (test (equal (sublis '((t . "string"))
+ (sublis '((1 . "") (4 . 44)) tree1)
+ :key #'stringp)
+ '("string" ("string" 2) (("string" 2 3)) ((("string" 2 3 44))))))
+ (test (equal tree1 '(1 (1 2) ((1 2 3)) (((1 2 3 4)))))))
+(let ((tree2 '("one" ("one" "two") (("one" "Two" "three")))))
+ (test (equal (sublis '(("two" . 2)) tree2)
+ '("one" ("one" "two") (("one" "Two" "three")))))
+ (test (equal tree2 '("one" ("one" "two") (("one" "Two" "three")))))
+ (test (equal (sublis '(("two" . 2)) tree2 :test 'equal)
+ '("one" ("one" 2) (("one" "Two" "three"))))))
+
+;; SUBST
+(let ((tree1 '(1 (1 2) (1 2 3) (1 2 3 4))))
+ (test (equal (subst "two" 2 tree1) '(1 (1 "two") (1 "two" 3) (1 "two" 3 4))))
+ (test (equal (subst "five" 5 tree1) '(1 (1 2) (1 2 3) (1 2 3 4))))
+ (test (eq tree1 (subst "five" 5 tree1))) ; Implementation dependent
+ (test (equal tree1 '(1 (1 2) (1 2 3) (1 2 3 4)))))
+(test (equal (subst 'tempest 'hurricane
+ '(shakespeare wrote (the hurricane)))
+ '(SHAKESPEARE WROTE (THE TEMPEST))))
+(test (equal (subst 'foo 'nil '(shakespeare wrote (twelfth night)))
+ '(SHAKESPEARE WROTE (TWELFTH NIGHT . FOO) . FOO)))
+(test (equal (subst '(a . cons) '(old . pair)
+ '((old . spice) ((old . shoes) old . pair) (old . pair))
+ :test #'equal)
+ '((OLD . SPICE) ((OLD . SHOES) A . CONS) (A . CONS))))
+