McCarthy's samefringe

Richard Gabriel's article on random ideas vaguely related to parallelism includes McCarthy's clever samefringe, which runs in log space without coroutines. Am I the only person who didn't know about this?

(defun samefringe (tree1 tree2)
  (or (eq tree1 tree2)
      (and (not (atom tree1)) (not (atom tree2))
           (same (gopher tree1) (gopher tree2)))))

(defun same (x y)
  (and (eq (car x) (car y))
       (samefringe (cdr x) (cdr y))))

(defun gopher (tree)
  (cond ((atom (car tree)) tree)
        (t (gopher (cons (caar tree)
                         (cons (cdar tree) 
                               (cdr tree)))))))

Gabriel rightly says “this solution is difficult to understand”, but the problem is in the presentation, not the algorithm. Even McCarthy makes naming mistakes - gopher should be called skew-right. It rotates the tree all the way right, so the first element of the fringe is in the car, and the rest is easy.

No comments:

Post a Comment

It's OK to comment on old posts.