6.001 Recitation #7                                        Fall 1997
Prof. Albert R. Meyer

        5-minute-problem #10: Simple Matching with Nameless Variables
                      (posed in email Wed, 10/15/97)

Simple matching is over flat lists instead of trees:

Atom = Sch-Num + Boolean + Symbol-which-is-not-variable
Nameless-variable = {?, ~}  
   (We only consider nameless variables in this problem.)

Simple-datum = List(Atom)
Simple-pattern = List(Atom + Nameless-variable)

? matches exactly one Atom.
~ matches any sequence of Atom's (including none).


SIMPLE-MATCH: (Simple-pattern x Simple-datum) --> Boolean

In class, we worked on SIMPLE-MATCH, noting the

USEFUL FACT:

The pattern (atom0 atom-or-var1 ... atom-or-var_n) matches
the datum   (dat-atom0 dat-atom1 ... dat-atom_m) iff
atom0 = dat-atom0 and
(atom-or-var1 ... atom-or-var_n) matches (dat-atom1 ... dat-atom_m).

This leads to the definition:

(define (simple-match pat dat)
  (cond ((null? pat) (null? dat))
        ((is-atom? (car pat))
         (and (pair? dat)
              (eq-atom? (car pat) (car dat))
              (simple-match (cdr pat) (cdr dat))))
        (else
         (simple-match-initial-tilde (cdr pat) dat))))

(define (is-atom? dat)
  (or (number? dat)
      (boolean? dat)
      (and (symbol? dat)
           (not (eq? '? dat))
           (not (eq? '~ dat)))))

(define (eq-atom? a1 a2)            ; a1, a2 are atoms
  (or (and (number? a1)
           (number? a2)
           (= a1 a2))
      (and (boolean? a1)
           (boolean? a2)
           (or (and a1 a2)
               (not (or a1 a2))))
      (eq? a1 a2)))


The exercise is to DEFINE procedure SIMPLE-MATCH-INITIAL-TILDE, where
(simple-match-initial-tilde rest-pat dat) returns #t iff the pattern
starting with ~ and continuing with REST-PAT matches DAT.  Begin by
stating an appropriate USEFUL FACT about how

the pattern (~ atom-or-var1 ... atom-or-var_n) can match
the datum   (dat-atom0 dat-atom1 ... dat-atom_m).


SOLUTION:

Note that the SIMPLE-MATCH procedure given above neglected the
question-mark case.  Here's the revised code:


(define (simple-match pat dat)
  (cond ((null? pat) (null? dat))
        ((eq? (car pat) `~)
         (simple-match-initial-tilde (cdr pat) dat))
        (else
         (and (pair? dat)
              (or (eq? (car pat) '?)
                  (eq-atom? (car pat)   ;(car pat) is an atom
                            (car dat)))
              (simple-match (cdr pat) (cdr dat))))))


Useful facts for SIMPLE-MATCH-INITIAL-TILDE:

    (~ pat1 ... patn) matches (dat0 ... datm)
iff either
    (pat1 ... patn) matches (dat0 ... datm)   -- so ~ matches nothing,
    or
    (~ pat1 ... patn) matches (dat1 ... datm) -- so ~ is used to match a
                                                 sequence which starts
                                                 with dat0


(define (simple-match-initial-tilde rest-pat dat)
  (or (simple-match rest-pat dat)                 ; ~ not used in match
      ; ~ matches some positive length prefix of dat:
      (and (pair? dat)
           (simple-match-initial-tilde rest-pat (cdr dat)))))