マクロのマッチングを実装しよう - 2. On Lisp のマッチングコード

On Lispの「18.4 マッチング」に出てきたコードを理解し、Scheme で書き直す。
本丸の match は後回しにし、varsym? と binding を書く。

varsym?

varsym? は簡単。
x がパターン変数かどうかを返す。あらかじめテストを書いておいた。

(define (varsym? x)
  (and (symbol? x) (char=? (string-ref (symbol->string x) 0) #\?)))

(assert-check-true
 "varsym?"
 (varsym? '?x)
 (varsym? '?y)
 (varsym? '?abc))

(assert-check-false
 "varsym?"
 (varsym? 'x?)
 (varsym? 1)
 (varsym? 'a)
 (varsym? '(?a ?b))
 (varsym? "?x"))

binding

binding は bind のデータ構造さえ分かれば簡単。
「ある変数 ?x が 3 にマッチしている状態」を (?x . 3) というデータ構造で表現する。
その状態をリストで保持したものが binds 。
例↓。

((?x . 3) (?y . 4) (?z . 5))

binding は引数 x のマッチ情報が binds に存在すれば返す。
返されるデータは多値で

(values マッチした値 マッチ情報)

である。
binds にデータが見つからなければ

(values #f #f)

となる。
なぜ多値なのかは match に行くと分かるのだけど後回し。

あと面白いのは x が別の変数にマッチしていて binds に存在するならばそれをたどってくれる点。
テストケースの ?z はその一例。
コードは以下の通り。

(define (binding x binds)
  (define (recbind x binds)
    (let ((it (assoc x binds)))
      (if it
          (or (recbind (cdr it) binds) it)
          #f)))
  (let ((b (recbind x binds)))
    (if (pair? b)
        (values (cdr b) b)
        (values #f #f))))

(let ((binds '((?x . 3) (?y . 4) (?z . ?y))))
  (assert-check-true
   "binding"
   (= 3 (binding '?x binds))
   (= 4 (binding '?y binds))
   (= 4 (binding '?z binds))
   (not (binding '?w binds))
))

(let ((binds '((?x . (abc . def)) (?y . (gh ij (k))) (?z . ?y))))
  (assert-check-true
   "binding lists"
   (equal? (binding '?x binds) '(abc . def))
   (equal? (binding '?y binds) '(gh ij (k)))
   (equal? (binding '?z binds) '(gh ij (k)))
   (not (binding '?w binds))
))

続きはまた明日。
<前:マクロのマッチングを実装しよう1 | 次:マクロのマッチングを実装しよう3>