4.4.3 · Pattern-directed matching

A frame records only consistent pattern bindings.

A pattern variable can extend an explicit frame when first encountered, then require the same value every time that variable appears again.

Guiding question

How can a matcher carry partial knowledge while it walks two data structures?

Represent pattern variables as explicit list data
Store variable bindings in an association-list frame
Match pair structure recursively from left to right
Reject a repeated variable when its value conflicts

The form (? who) represents a pattern variable rather than a literal list. On its first occurrence, extend-if-consistent adds who and the matching datum to the frame. Ordinary symbols and pair structure must match directly.

A later occurrence looks up the existing binding before extending anything. Equal data preserves the frame; conflicting data returns failed, which every remaining recursive step propagates. This is one-way matching with variables in the pattern, not full bidirectional unification or database search.

SICP code970 of 1,048,576 UTF-8 bytes

(begin
  (define (variable? pattern)
    (and (pair? pattern) (eq? (car pattern) '?)))
  (define (extend-if-consistent variable value frame)
    (let ((found (assoc (cadr variable) frame)))
      (cond (found
             (if (equal? value (cdr found)) frame 'failed))
            (else
             (cons (cons (cadr variable) value) frame)))))
  (define (pattern-match pattern datum frame)
    (cond ((eq? frame 'failed) 'failed)
          ((variable? pattern)
           (extend-if-consistent pattern datum frame))
          ((and (pair? pattern) (pair? datum))
           (pattern-match
             (cdr pattern)
             (cdr datum)
             (pattern-match (car pattern) (car datum) frame)))
          ((equal? pattern datum) frame)
          (else 'failed)))
  (define frame
    (pattern-match '(parent (? who) (? child))
                   '(parent bob alice)
                   '()))
  (list (cdr (assoc 'who frame))
        (cdr (assoc 'child frame))))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The first program returns (bob alice). The second returns (apple failed).

Trace focus

Follow recursive car matching before cdr matching, then locate each frame extension. In the second run, watch the second item lookup preserve the apple frame once and return failed for pear. The traces record one-way pattern matching and every frame extension.

Try it yourself

Change the program and compare the result.

Change the first pattern to (parent (? person) (? person)). Predict the result for (parent bob alice) before running.

Show hint

The second occurrence must equal the value stored by the first occurrence.

Complete this lesson

0 of 23 lessons complete in this chapter0%