Scheme equal-tree procedure

Question

Given a new implementation of tree in Scheme using list:

(define make-tree list)
(define add-subtree cons)
(define make-leaf (lambda (x) x))
(define empty-tree? empty?)
(define first-subtree car)
(define rest-tree cdr)
(define composite-tree? list?)
(define leaf? (lambda (x) (not (composite-tree? x))))

Implement the CPS procedure equal-tree$ which receives a pair of leaf-valued trees, t1 and t2, and two continuations: succ and fail and determines their structure identity as follows:

• if t1 and t2 have the same structure, equal-tree$ returns a tree with the same structure, but where each leaf contains a pair with the leaves of the original two trees at this position(no matter whether their values agree or not).

• Otherwise, equal-tree$ returns a pair with the first conflicting sub-trees in depth-first traversal of the trees.

for example:

(define id (lambda (x) x))
(equal-trees$ '(1 (2) (3 9)) '(7 (2) (3 5)) id id) ---> '((1 . 7) ((2 . 2)) ((3 . 3) (9 . 5)))

I tried my best to solve this question but I encountered a bug and hopefully some can help me fixing it.

This is my try:

(define equal-tree$
  (lambda (tree1 tree2 succ fail)
    (if (and (empty? tree1) (empty? tree2))
      '()
      (if (or (empty? tree1) (empty? tree2))
        (fail '())
        (if (and (leaf? tree1) (leaf? tree2))
          (succ (cons tree1 tree2))
          (if (or (leaf? tree1) (leaf? tree2))
            (fail (cons (car tree1) (car tree2)))
            (equal-tree$ (car tree1) (car tree2) 
               (lambda (X) cons(cons (car tree1) (car tree2)) x) fail)))))
   )
)

And here is the output for the example above (I just don't know why it prints '(1 . 7) ... :

'(1 . 7)

Answer 1

You have a reasonable-looking sequence of if tests (though using cond instead would be more idiomatic Scheme). But the values you return do not generally look correct.

The first problem I see is in your first if clause. If both trees are empty, you return '(). But according to the spec, you should be calling the succ function with that result. This may look unimportant if you use id as your continuation, but note that each recursive step builds up a more detailed succ continuation, so in general succ may be a quite impactful function.

The second if is also a problem. Again you return '(), when you are supposed to return the first conflicting subtrees. It's not clear to me what that means, but it would be reasonable to pass a pair of tree1 and tree2 to fail.

The third and fourth clause look fine. You call succ with a pair of the two leaves, as expected.

The recursive call is clearly wrong: you have mis-parenthesized calls to cons, and your lambda variable is named X but you refer to it as x. The series of cons calls doesn't really look right either, but you can experiment with that once your more pressing syntactic issues are resolved and your base cases work properly.

Lastly, you are doing a lot of low-level work with cons, car, '(), and so on. You should be using the abstract functions provided to you, such as add-subtree and (make-tree), instead of using the low-level primitives they are built on.