で、とりあえず単純なマッチと置き換えのコードを示しておくから
後は好きに拡張してくれ。シンボルは全てパターン変数として扱い、
シンボル以外のものは考慮してない。

(define (match template input)
(define (walk template input binding succ)
(cond
((null? template) (and (null? input) (succ binding)))
((symbol? template) (succ (acons template input binding)))
((pair? template)
(and (pair? input)
(walk (car template) (car input) binding
(cut walk (cdr template) (cdr input) <> succ))))))
(walk template input '() values))

(define (subst tree binding)
(cond
((pair? tree)
(cons (subst (car tree) binding) (subst (cdr tree) binding)))
((and (symbol? tree) (assq tree binding)) => (cut cdr <>))
(else tree)))

gosh> (subst '(d c b a) (match '((a b) (c . d)) '((1 2) (3 4 5))))
((4 5) 3 2 1)