Next: 2 プロダクションシステム
Up: 1 変数を含むパターンとデータのマッチング
Previous: 1.6 ラムダ式の構造比較への応用例
マッチング関数が返すバインディング情報に基づいて，他のパターン
中に現れるその変数を置き換える手続きを考えます．
パターンの中に変数が現れていれば，その変数が
バインディング情報にあればその値を返し，なければ
そのデータをそのまま返すということをリストの
car,cdr部のそれぞれに再帰的に繰り返すだけでよい．
そこで，以下のような定義を行ないます．
(defun substitute-bindings (bindings pattern)
(cond
((null pattern) nil)
((variable-p pattern)
(let ((v (get-binding pattern bindings)))
(if v (binding-val v) pattern)))
((atom pattern) pattern)
(t (cons
(substitute-bindings bindings (car pattern))
(substitute-bindings bindings (cdr pattern))))))
この定義は，バインディング情報が連想リスト，あるいは，構造体のどちらで
あっても大丈夫な定義になっています．それは，バインディング情報への
アクセス関数を用いて定義してあるからです．
このように，あるデータタイプを決めた場合に，そのデータへのアクセス
関数を定義し，その関数のみを用いて上位の関数を定義するということを
行なうことで，データの内部表現を変更した場合に上位の関数の定義を
変更する必要はなくなります．
<cl> (substitute-bindings
(match '(?x ?y) '(a b))
'(x ?x y (?y (?x) ((?y)))))
(X A Y (B (A) ((B))))
<cl> (substitute-bindings
(match '(?x ?y) '(a b))
'(x ?x y (?y (?x) ((?y ?z)))))
(X A Y (B (A) ((B ?Z))))
ちなみに，バインディング情報が連想リストで表現している場合には，sublis
という組み込み関数を利用できます．sublisは連想リストとパターンを与えた
場合に，パターン中に現れる連想リストのキーデータを値データに置き換える
ということを行なうものです．
?で始まる変数でなくても連想リストのキーに
なっているデータを置き換える一般的なものです．
<cl> (sublis '((a . 1) (b . 2)) '(b (a c) a b))
(2 (1 C) 1 2)
<cl> (sublis '((?x . a) (?y . b))
'(x ?x y (?y (?x) ((?y ?z)))))
(X A Y (B (A) ((B ?Z))))
<cl> (match '(?x ?y) '(a b))
((?Y . B) (?X . A))
<cl> (sublis (match '(?x ?y) '(a b))
'(x ?x y (?y (?x) ((?y ?z)))))
(X A Y (B (A) ((B ?Z))))
<cl> (sublis '((x . 100) (z . zprime))
'(plus x (minus g z x p) 4 . x))
(PLUS 100 (MINUS G ZPRIME 100 P) 4 . 100)
<cl> (sublis '(((+ x y) . (- x y)) ((- x y) . (+ x y)))
'(* (/ (+ x y) (+ x p)) (- x y))
:test #'equal)
(* (/ (- X Y) (+ X P)) (+ X Y))
<cl> (setq tree1 '(1 (1 2) ((1 2 3)) (((1 2 3 4)))))
(1 (1 2) ((1 2 3)) (((1 2 3 4))))
<cl> (sublis '((3 . "three")) tree1)
(1 (1 2) ((1 2 "three")) (((1 2 "three" 4))))
<cl> tree1
(1 (1 2) ((1 2 3)) (((1 2 3 4))))
Next: 2 プロダクションシステム
Up: 1 変数を含むパターンとデータのマッチング
Previous: 1.6 ラムダ式の構造比較への応用例
generated through LaTeX2HTML. M.Inaba 平成18年5月21日