프레임은 일관된 패턴 바인딩만 기록한다.
패턴 변수는 처음에는 프레임을 확장하고 다시 나타날 때는 같은 값인지 확인합니다.
매처는 두 데이터 구조를 걸으며 부분 지식을 어떻게 전달할까요?
- 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))))- 출력
- —
- 값
- —
- 진단
- —
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 first pattern to (parent (? person) (? person)). Predict the result for (parent bob alice) before running.
힌트 하나 보기
The second occurrence must equal the value stored by the first occurrence.