5.1 データベースの実現

Next: 5.2 データベースへの登録 Up: 5 Prolog処理系の実現 Previous: 5 Prolog処理系の実現

5.1 データベースの実現

データベースは，ホーン節の集合です．ゴールの問い合わせに対して，同じパターンのゴールをもつホーン節を効率良く選ぶためには，ゴールの述語シンボルにより節集合を分類しておくことが有効です．このようにデータベースを分類して構成しておくことはIndexingと呼ばれます．ゴールの述語ごとに節を分類して保存するために利用できる方法としては，（１）述語シンボルの属性リストにすべての節を登録し，データベース全体を述語シンボルのリストで表現する方法，（２）キーを述語シンボルとして対応値を節集合にするハッシュ表を用いる方法，などが考えられます．これまでに何度も紹介してきたように，このような内部表現のデータ構造に依存しないようにアクセス関数を実現することが重要なプログラミング法です．以下では，ハッシュ表を用いた例を示しておきます．


(defun clause-head (clause) (first clause))
(defun clause-body (clause) (rest clause))

(defun get-clauses (pred)
    (gethash pred *prolog-database*))
(defun predicate (relation) (first relation))

(defvar *prolog-database* (make-hash-table))
(defun init-prolog ()
  (clrhash *prolog-database*))

(defun add-clause (clause)
  (let ((pred (predicate (clause-head clause))))
    (setf (gethash pred *prolog-database*)
          (nconc (get-clauses pred) (list clause)))
    pred))

add-clauseの中で注意するところとして，nconcを使っているところです． appendを使うとリスト構造がコピーされて無駄が多いのですが，nconcではその無駄がなくなります．nconcは副作用として破壊的な操作を行なってしまいますが，ここでは，(list clause)をnconcしているため，新たなコンスを nconcしていることになり他のデータを破壊する心配はありません．

Next: 5.2 データベースへの登録 Up: 5 Prolog処理系の実現 Previous: 5 Prolog処理系の実現

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