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.
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.
(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))))- Output
- —
- Value
- —
- Diagnostic
- —
The first program returns (bob alice). The second returns (apple failed).
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. These traces cover only one-way pattern matching.
Change the program before you read the hint.
Change the first pattern to (parent (? person) (? person)). Predict the result for (parent bob alice) before running.
Show one hint
The second occurrence must equal the value stored by the first occurrence.