misc:software:Common Lisp:PAIP:4章

内容

章の冒頭で示されている以下の五つの手順を踏まえながら、GPS (General Problem Solver) の初歩的な開発を解説している。

1. 問題記述
2. 仕様記述
3. 実装
4. テスト
5. デバッグと分析

まず、Amazon.co.jp： Human Problem Solving: Allen Newell, Herbert A. Simon: 洋書 で挙げられている手段目標分析(mean-ends analysis)の例に対して実際に取り組んでいる。問題記述から分析まで一通り試し(GPS version 1)、その結果を踏まえ同様の手順を再度経て GPS version 2 を開発している。

以前の章より

(defun find-all (item sequence &rest keyword-args
                                 &key (test #'eql) test-not &allow-other-keys)
  "Find all those elements of sequence that match item,
according to the keywords. Doesn't alter sequence."
  (if test-not
      (apply #'remove item sequence
             :test-not (complement test-not) keyword-args)
      (apply #'remove item sequence
             :test (complement test) keyword-args)))

演習

演習4.1

「4.10 『中間情報の不足』問題」でdbg-indentはつぎのように定義されている。

(defun dbg-indent (id indent format-string &rest args)
  "Print indented debugging info if (DEBUG ID) has been specified."
  (when (member id *dbg-ids*)
    (fresh-line *debug-io*)
    (dotimes (i indent) (princ "  " *debug-io*))
    (apply #'format *debug-io* format-string args)))

• fresh-line関数はformat関数の~&で代用する
• インデント用の空白はformat関数の~Tで代用する
  • 空白の個数は~Tのパラメータとして設定する
• format関数の任意のフォーマット文字列を一つだけ取るには、~@?を使用する

これらを総合するとつぎのように記述できる。

(defun dbg-indent (id indent format-string &rest args)
  "Print indented debugging info if (DEBUG ID) has been specified."
  (when (member id *dbg-ids*)
    (format *debug-io* "~&~VT~@?" (* 2 indent) format-string args)))

演習4.2

Norvigの解答例は簡潔でわかりやすい。

(defun permutations (bag)
  "Return a list of all the permutations of the input."
  (if (null bag)
      '(())
      ;; mapcan によってリストの各要素を一つずつ処理し、その結果をリストとしてまとめる
      (mapcan #'(lambda (e)
                  (mapcar #'(lambda (p) (cons e p))
                          (permutations
                           ;; bag から e を取り除いたリストを返す
                           (remove e bag :count 1 :test #'eq))))
              bag)))

(permutations '(a b c))
; => ((A B C) (A C B) (B A C) (B C A) (C A B) (C B A))

(permutations '(a b c d))

演習4.3

(defparameter *dessert-ops*
  (list
    (make-op :action 'eat-dessert
         :preconds '(eat-cake eat-ice-cream)
         :add-list '(eat-dessert))
    (make-op :action 'eat-ice-cream
         :preconds '(have-ice-cream)
         :add-list '(eat-ice-cream))
    (make-op :action 'eat-cake
         :preconds '(have-cake)
         :add-list '(eat-cake))
    (make-op :action 'buy-cake
         :preconds '(have-money)
         :del-list '(have-money)
         :add-list '(have-cake))
    (make-op :action 'get-ice-cream
         :preconds '(have-cake)
         :add-list '(have-ice-cream))
    ))

(gps '(have-money)
     '(eat-dessert)
     *dessert-ops*)
; => 

演習4.4

演習4.5

演習4.6

演習4.7