マクロのマッチングを実装しよう - 5. match

scheme

下準備が長かったけどいよいよ On Lispの match を実装する。

match は引数 x, y を比較しマッチしているか確認する。

  • x と y が等しい場合はマッチする
  • _ は何とでもマッチする（何もないとはマッチしない）
  • x や y が既に束縛されているなら値を展開してから再度 match を呼ぶ
  • x と y が pair だったら car と cdr の順に match を呼び出す。（結果的にリストの要素を比較していく）
(define match
  (lambda (x y . binds)
    (let ((bn (if (pair? binds) (car binds) binds)))
      (acond2
       ((or (eqv? x y) (eqv? x '_) (eqv? y '_)) (values bn #t))
       ((binding x bn) (match it y bn))
       ((binding y bn) (match x it bn))
       ((varsym? x) (values (cons (cons x y) bn) #t))
       ((varsym? y) (values (cons (cons y x) bn) #t))
       ((and (pair? x) (pair? y) (match (car x) (car y) bn))
        (match (cdr x) (cdr y) it))
       (#t (values #f #f))))))

テストコード

match のテスト。
どのように match するか分かると思う。

(assert-check-equal equal?
                     ('((?x . 3))                                              (match '?x 3))
                     ('((?y . 3) (?x . 2))                                     (match '(?x . ?y) '(2 . 3)))
                     ('((?y . 3) (?x . 2))                                     (match '(?x ?y _) '(2 3 4)))
                     ('((?z . (hoge (c))) (?y . (display b)) (?x . (pair? a))) (match  '(if ?x ?y ?z) '(if (pair? a) (display b) (hoge (c)))))
                     ('((?z . (display a)) (?y . 3) (?x . a)) (match '(let ((?x ?y)) (_ ?z)) '(let ((a 3)) (begin (display a)))))
                     ('((?z . (display a)) (?y . 3) (?x . a)) (match '(let ((?x ?y)) (_ ?z)) '(let ((a 3)) (print (display a)))))
)