Next: 1.1 マッチング関数の仕様 Up: ソフトウェア特論講義資料前向き推論，後ろ向き推論 Previous: 前向き推論

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

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

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

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


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

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

Next: 1.1 マッチング関数の仕様 Up: ソフトウェア特論講義資料前向き推論，後ろ向き推論 Previous: 前向き推論

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