; 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) #f)
    ((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 list of elements in the question that match ... and _ 
; in the pattern. 
; What matches ... is always a list.
; Example: (substitutions-in-to-match '(a _ b _ ...) '(a x b (1 2) g h))
; returns (x (1 2) (g h)).
; 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)) ) ) )