Next: 1.1 マッチング関数の仕様 Up: ソフトウェア第三　講義資料パターンマッチ，前向き推論，ユニフィケーション，後向き推論 Previous: 前向き推論

1 変数を含むパターンとデータのマッチング

データの等号比較は，TかNILを返す関数であるが，ここでは，等号を調べるパターンの中に変数があるならば，その変数が比較するデータの中に対応するものがあるかどうかを調べるという手続きmatchを考える． matchは，equalと同様に，データが同じであればTを返すが，何とでも対応できる変数を導入することでequalを拡張した形になる．たとえば，?で始まるシンボルが変数を表すと決めると，

> (equal '(a b c)  '(a b c))
T
> (match '(a b c)  '(a b c))
T
> (match '(?x b c) '(a b c))
T
> (equal '(?x b c)  '(a b c))
NIL
> (match '(?x b a) '(a b c))
NIL
> (match '(?x b a) '(b a))
NIL

というように対応するかどうかを調べることが可能である．しかし，実際の応用では，パターンに用いた変数が何とマッチングすれば二つのデータが照合可能かということを知りたいことが多く，変数のバインディング情報を参照できるようにしなければならない．また，

> (match '(lambda (?x) (list ?x))
            '(lambda (a) (list b)))
NIL
> (match '(lambda (?x) (list ?x))
            '(lambda (a) (list a)))
T

という具合に同じ変数がパターンの中に複数回現れる場合には， 2度目に現れた?xがbと対応するかどうか比較する際に，すでに，?xがaと対応していなければならないという条件を考慮してマッチングの比較がなされなければならない．つまり，変数を含むパターンとデータのマッチング処理は，equal関数と似た形とするが，変数が出てきたところで，その変数がすでにあるデータとマッチングされているかどうか，そして，何にマッチングされているかという変数のバインディング情報を保存した形でマッチングがなされる必要がある．

generated through LaTeX2HTML. M.Inaba 平成18年5月7日