Stage 3: Implementation

仕様が完全であるのならCommonLispに十分実装できます。図4.1にGPSをCommonLispを使って実装するための値、データ型、関数をまとめておきます。

GPS	Top level関数。operatorのlistをつかって、状態をゴールまで解決する
*state*	特殊変数：現在の状態
*ops*	特殊変数：利用可能なoperatorのlist
op	データタイプ：add-listとdel-listの前提条件つきoperation
achieve	関数：単一のゴールを達成する
appropriate-p	operatorがgoalに対して適切かを決定する
apply-op	現在の状態にoperatorを適用する
member	CommonLisp関数：listにmemberが含まれているかをテストする
set-difference	setの中のそれ自身を含まないlistを返す
union	2つのlistを連結する
every	elementごとにlistからテストにパスしたを返す
some	listからテストにパスしてlistを返す
find-all	elementにマッチしたすべてのlistを返す(p101)

そして、これが完全なコードです

(defvar *state* nil "現在の状態：条件のリスト")
(defvar *ops* nil "利用可能なoperatorのリスト")
(defstruct op "Operation"
  (action nil) (preconds nil) (add-list nil) (del-list nil))
(defun GPS (*state* goals *ops*)
  "General Problem Solver: *ops*をつかって、すべてのgoalを達成する"
  (if (every #'achieve goals) 'solved))
(defun achieve (goal)
  "もしすでに到達してるならgoalを達成する。そうでないなら適切なopがあれば、それを適用する"
 (or (member goal *state)
     (some #'apply-op
           (find-all goal *ops* :test #'appropriate-p))))
(defun appropriate-p (goal op)
  "もしadd-listにあるなら、opがgoalに適切であるかを判定する"
  (member goal (op-add-list op)))
(defun apply-op (op)
  "opが適用されたときに、メッセージを表示し、更新を行う"
  (when (every #'achieve (op-preconds op))
        (print (list 'executing (op-action op)))
        (setf *state* (set-difference *state* (op-del-list op)))
	 (setf *state* (union *state* (op-add-list op)))
 t))

見たところ、プログラムは7つの定義でできています。7つのアイテムの仕様は上のとおりです。一般的にいって、仕様と実装は対応になるものではありません。通常は、仕様と実装の間における対応は完全ではありません。二つのdefvar、1つのdefstruct、4つのdefunがあります。これらは変数、構造体、関数のCommon Lispによる定義です。これらは、ほとんどのLispにおいてはtop levelにありますが、それらは魔法ではなく、Lispの環境にたいして、新しい定義を追加するという副作用のspecial formなのです。
下に再掲した二つのdefvarでは、*state*と*ops*という名前の特殊変数を宣言していて、プログラム中からのどこからでもアクセス可能です。

(defvar *state* nil "現在の状態：条件のリスト")
(defvar *ops* nil "利用可能なoperatorのリスト")

defstructはaction, preconds, add-list, del-listといったslotのあるopという構造体を定義します。CommonLispにおける構造体はCやPASCALのものと同じです。defstructは自動的にmake-opというconstructor関数とop-action, op-preconds, op-add-list, op-del-listというアクセス関数を生成します。defstructはさらに、copy-opというcopy関数、op-pという述語とsetf定義によって各slotを変更できるようにします。GPSプログラムではそれらは使われていません。おおまかに言うと、defstructは

(defstruct op "Operation"
  (action nil) (preconds nil) (add-list nil) (del-list nil))

であり、下記の定義はdefstructによって拡張されたものです。

(defun make-op (&key action preconds add-list del-list)
  (vector 'op action preconds add-list del-list))
(defun op-action (op) (elt op 1))
(defun op-preconds (op) (elt op 2))
(defun op-add-list (op) (elt op 3))
(defun op-del-list (op) (elt op 4))
(defun copy-op (op) (copy-seq op))
(defun op-p (op)
  (and (vectorp op) (eq (elt op 0) 'op)))
(setf (documentation 'op 'structure) "An operation")

次に、GPSプログラムの4つの関数定義です。main関数はGPSで、3つの引数をとります。最初は世界の現在の状態、次がGoalの状態、3つめが使用できるOperatorです。関数の中身は簡単に言えば、もしGoalに到達可能であればそれを実行し、問題を解決します。そうでない場合には問題は解決できません。
achieve関数は引数にgoalをとります。関数は現在の状態がすでにgoal(実際にはなにもしない)か、適切なoperatorを適用したならば、関数は成功します。適切なoperatorのlistのうちのうち、何か適用できるまでこの操作は続きます。achieveが101pageで定義したfind-allを呼びだします。これを使って、find-allが現在のgoalにappropriate-p述語によってマッチしたoperatorのlistを返します。
appropriate-pはoperatorが適切なゴールになるかどうかをテストする関数です(Lispではこのような述語においては利便性のために末尾に-pをつけます)
最後にapply-opではすべての適切な前提条件をachieveし、operatorを適用できます。これにはメッセージを表示しdelete-listから削除し、add-listに追加するoperatorによって、作用させ、世界の状態を変更します。さらにapply-opは適用したoperatorを返します。