next up previous
Next: 2 プロダクションシステム Up: 1 変数を含むパターンとデータのマッチング Previous: 1.6 ラムダ式の構造比較への応用例

1.7 バインディング情報に基づく置換

マッチング関数が返すバインディング情報に基づいて,他のパターン 中に現れるその変数を置き換える手続きを考えます. パターンの中に変数が現れていれば,その変数が バインディング情報にあればその値を返し,なければ そのデータをそのまま返すということをリストの 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 up previous
Next: 2 プロダクションシステム Up: 1 変数を含むパターンとデータのマッチング Previous: 1.6 ラムダ式の構造比較への応用例
generated through LaTeX2HTML. M.Inaba 平成18年5月21日