1.4 バインディング情報の表現

Next: 1.5 マッチング関数の定義 Up: 1 変数を含むパターンとデータのマッチング Previous: 1.3.2 任意のシンボルを変数に宣言する方法

1.4 バインディング情報の表現

バインディング情報は，変数の対応する値を検索するために利用される．バインディング情報を処理するために，以下のような基本関数を定義する．

(defun get-binding (var bindings)
  "バインディング情報bindings の中に
  変数varのバインディング情報が
  入っているかどうかを調べる"
  (assoc var bindings))
(defun binding-var (binding) (car binding))
(defun binding-val (binding) (cdr binding))
(defun make-binding (&key var val) (cons var val))
(defun lookup (var bindings)
  (binding-val (get-binding var bindings)))

(defun add-binding (var val bindings)
  (cons (make-binding :var var :val val)
        bindings))

連想リストではなく，構造体のリストを用いても実現することができる．構造体の場合には，binding-var, binding-val, make-bindingは自動的に生成される．

(defstruct binding var val)

(defun get-binding (var bindings)
  (find var bindings :key #'binding-var))

(defun lookup (var bindings)
  (let ((x (get-binding var bindings)))
    (if x (binding-val x))))

この場合，以下のように値が返る．

> (match '(?a ?a) '(x y))
FAIL 
> (match '(?a ?a) '(x x))
(#s(BINDING :VAR ?A :VAL X)) 
> (match '(?a ?a) '(y y))
(#s(BINDING :VAR ?A :VAL Y)) 
> (match '(x y z) '(x y z))
NIL

リストではなく，ハッシュ表を用いる方法では，

(defun get-binding (var bindings)
  (let ((v (gethash var bindings)))
    (if v (cons var v) nil)))

(defun lookup (var bindings)
  (gethash variable bindings))

(defun add-binding (var val bindings)
  (setf (gethash var bindings) val)
  bindings)

という具合に定義すればよさそうである．変数が多くなった場合には，ハッシュ表を用いる方法が有効であるが，数が少ない場合には連想リストで十分である．いずれにせよ，基本関数の定義内容を変えることで内部表現の変更がマッチング関数へ影響を及ぼさないように定義することは可能である．

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