Wikisource

Page:Scheme - An interpreter for extended lambda calculus.djvu/10

This page has been proofread, but needs to be validated.
Sussman and Steele December 22, 1975 9 SCHEME Programming Examples 

(DEFINE SAMEFRINGE
   (LAMBDA (TREE1 TREE2)
       (LABELS ((SAME
                 (LAMBDA (S1 S2)
                     (S1 (LAMBDA (X1 R1)
                             (S2 (LAMBDA (X2 R2)
                                     (IF (EQUAL X1 X2)
                                         (IF (EQUAL X1 '(EXHAUSTED))
                                             T
                                             (SAME R1 R2))
                                         NIL))))))))
               (SAME (FRINGE TREE1)
                     (FRINGE TREE2)))))

Now let us consider an alternative solution to the samefringe problem. We believe that this solution is clearer for two reasons:

  1. the implementation of SAMEFRINGE is more clearly iterative;
  2. rather than returning an object which will return both the first and the rest of a fringe to a given continuation, FRINGE returns an object which will deliver up a component in response to a request for that component.
(DEFINE FRINGE
   (LAMBDA (TREE)
       (LABELS ((FRINGE1
                 (LAMBDA (NODE ALT)
                    (IF (ATOM NODE)
                        (LAMBDA (MSG)
                            (IF (EQ MSG 'FIRST) NODE
                                (IF (EQ MSG 'NEXT) (ALT) (ERROR))))
                        (FRINGE1 (CAR NODE)
                                 (LAMBDA () (FRINGE1 (CDR NODE) ALT)))))))
               (FRINGE1 TREE
                        (LAMBDA ()
                            (LAMBDA (MSG) (IF (EQ MSG 'FIRST) '*EOF* (ERROR))))))))

(DEFINE SAMEFRINGE
    (LAMBDA (T1 T2)
        (DO ((C1 (FRINGE T1) (C1 'NEXT))
             (C2 (FRINGE T2) (C2 'NEXT)))
            ((OR (NOT (EQ (C1 'FIRST) (C2 'FIRST)))
                 (EQ (C1 'FIRST) '*EOF*)
                 (EQ (C2 'FIRST) '*EOF*))
             (EQ (C1 'FIRST) (C2 'FIRST))))))

A much simpler and more probable problem is that of building a pattern matcher with backtracking for segment matches. The matcher presented below is intended for matching single-level list structure patterns against lists of atoms. A pattern is a list containing three types of elements:

Retrieved from "https://en.wikisource.org/w/index.php?title=Page:Scheme_-_An_interpreter_for_extended_lambda_calculus.djvu/10&oldid=10955884"