; This is code also used in the CS 9D "Rule-based programming" assignment.

; Constructors/accessors for a rule.
(define make-pattern/action
  (lambda (pattern action)
    (cons pattern action) ) )

(define pattern car)
(define action cdr)

; Return true exactly when the pattern matches the question.
; The pattern and the question are both lists.
; Each element of the pattern is either 
;    the symbol _, which matches any single element;
;    the symbol ..., which must occur at the end of the pattern
;      and matches the remainder of the question;
;    a list, which matches any element of the list;
;    some other symbol, which matches itself.
; This is the version from Concrete Abstractions page 198, 
; augmented as in exercise 7.29.

(define (matches? pattern question)
  (cond 
    ((null? pattern)  
     (null? question) )
    ((null? question) 
     (equal? (car pattern) '...) )
    ((list? (car pattern))
     (if (member (car question) (car pattern))
         (matches? (cdr pattern) (cdr question))
         #f) )
    ((equal? (car pattern) '...) #t)
    ((equal? (car pattern) '_)
     (matches? (cdr pattern) (cdr question)) )
    ((equal? (car pattern) (car question))
     (matches? (cdr pattern) (cdr question)) )
    (else #f) ) )

; Return the elements in the question that correspond to wild card elements
; in the pattern.  If the pattern contains ..., its substitution is a list.
; If the pattern contains _, its substitution is the matched element.
; Example: (substitutions-in-to-match '(a _ b _ ...) '(a x b (1 2) g h))
; returns (x (1 2) (g h)).
; Nothing happens with list elements in the pattern.
; Precondition: (matches? pattern question).

(define (substitutions-in-to-match pattern question)
  (cond 
    ((null? pattern)  '( ))
    ((null? question) '(( )))  ; (car pattern) must be ...
    ((list? (car pattern))
     ; we know (member (car question) (car pattern))
     (substitutions-in-to-match (cdr pattern) (cdr question)) )
    ((equal? (car pattern) '...)
     (list question))
    ((equal? (car pattern) '_)
     (cons
       (car question)
       (substitutions-in-to-match (cdr pattern) (cdr question)) ) )
    ; we know (equal? (car pattern) (car question))
    (else
     (substitutions-in-to-match (cdr pattern) (cdr question)) ) ) )