Prev Up Next

A more involved example of continuation usage is the problem of determining if two trees (arbitrarily nested dotted pairs) have the same fringe, ie, the same elements (or leaves) in the same sequence. Eg,

(same-fringe? '(1 (2 3)) '((1 2) 3))
=> #t

(same-fringe? '(1 2 3) '(1 (3 2)))
=> #f

The purely functional approach is to flatten both trees and check if the results match.

(define same-fringe?
  (lambda (tree1 tree2)
    (let loop ((ftree1 (flatten tree1))
               (ftree2 (flatten tree2)))
      (cond ((and (null? ftree1) (null? ftree2)) #t)
            ((or (null? ftree1) (null? ftree2)) #f)
            ((eqv? (car ftree1) (car ftree2))
             (loop (cdr ftree1) (cdr ftree2)))
            (else #f)))))

(define flatten
  (lambda (tree)
    (cond ((null? tree) '())
          ((pair? (car tree))
           (append (flatten (car tree))
                   (flatten (cdr tree))))
          (else
           (cons (car tree)
                 (flatten (cdr tree)))))))

However, this traverses the trees completely to flatten them, and then again till it finds non-matching elements. Furthermore, even the best flattening algorithms will require conses equal to the total number of leaves. (Destructively modifying the input trees is not an option.)

We can use call/cc to solve the problem without needless traversal and without any consing. Each tree is mapped to a generator, a procedure with internal state that successively produces the leaves of the tree in the left-to-right order that they occur in the tree.

(define tree->generator
  (lambda (tree)
    (let ((caller '*))
      (letrec
          ((generate-leaves
            (lambda ()
              (let loop ((tree tree))
                (cond ((null? tree) 'skip)
                      ((pair? tree)
                       (loop (car tree))
                       (loop (cdr tree)))
                      (else
                       (call/cc
                        (lambda (rest-of-tree)
                          (set! generate-leaves
                            (lambda ()
                              (rest-of-tree 'resume)))
                          (caller tree))))))
              (caller '()))))
        (lambda ()
          (call/cc
           (lambda (k)
             (set! caller k)
             (generate-leaves))))))))

When a generator created by tree->generator is called, it will store the continuation of its call in caller, so that it can know who to send the leaf to when it finds it. It then calls an internal procedure called generate-leaves which runs a loop traversing the tree from left to right. When the loop encounters a leaf, it will use caller to return the leaf as the generator's result, but it will remember to store the rest of the loop (captured as a call/cc continuation) in the generate-leaves variable. The next time the generator is called, the loop is resumed where it left off so it can hunt for the next leaf.

Note that the last thing generate-leaves does, after the loop is done, is to return the empty list to the caller. Since the empty list is not a valid leaf value, we can use it to tell that the generator has no more leaves to generate.

The procedure same-fringe? maps each of its tree arguments to a generator, and then calls these two generators alternately. It announces failure as soon as two non-matching leaves are found:

(define same-fringe?
  (lambda (tree1 tree2)
    (let ((gen1 (tree->generator tree1))
          (gen2 (tree->generator tree2)))
      (let loop ()
        (let ((leaf1 (gen1))
              (leaf2 (gen2)))
          (if (eqv? leaf1 leaf2)
              (if (null? leaf1) #t (loop))
              #f))))))

It is easy to see that the trees are traversed at most once, and in case of mismatch, the traversals extend only upto the leftmost mismatch. cons is not used.

Prev Up Next

Log in or registerto write something here or to contact authors.