I have been playing with LISP (xlispstat) for a while and have been trying
to implement a genetic programming algorythm in it. I am using binary tree
representations of functions (that is an evolved program should consist
entiraly of lists of length 3 whos fist member is a member of the function
set and whos other members are either similar lists or members of the
terminal set.) however at some point though the gp run cons cells start
appearing, oftain containing atoms which dont apear in any of the
functions used in the program or as arguments to the program (the atom
TREE is particularly common)

The most likely function to be causing this is crossover - which performs
most of the work for crossover and mutation (ie. replaces a random subtree
in a tree with some specifies structure.)

(defun crossover (tree &optional (subst nil) (prob-no-recursion .75))
  "args: tree &optional (subst nil) (prob-no-recursion .75)

finds a random subtree (not including the entire tree) of tree and returns
it, possibly
after replacing it with subst if subst is non nil.."
  (if (< (random 1.0) (expt prob-no-recursion (1- (max-depth tree))))
      ;; swap with a sub tree
      (let ((args (cdr tree))
            (rnd (random 2))
            (tmp nil))
        (if (null subst)
            (cond ((= rnd 0) (car args))
                  (t (second args)))
          (cond ((= rnd 0) (setf tmp (car args))
                           (rplaca args subst)
                           tmp)
                (t (setf tmp (second args))
                   (rplacd args (list subst))
                   tmp))))
    ;; swap with another sub-tree
    (let* ((dl (max-depth (second tree)))
           (dr (max-depth (third tree)))
           (rnd (random (+ dl dr))))
      (if (< rnd dl)
          (crossover (second tree) subst)
        (crossover (third tree) subst)))))