読者です 読者をやめる 読者になる 読者になる

レガシーコード生産ガイド

私に教えられることなら

PAIPメモ 4

PAIP(実用Common Lisp)を読んでて気になって調べた事などをメモします。

エクステント

レキシカル変数はレキシカルスコープと無限エクステント、 スペシャル変数は無限スコープと動的エクステントを持ちます。

他の組み合わせはあるのかというと、nilなどの定数は無限スコープと無限エクステント、 tagbodyの飛び先等はレキシカルスコープと動的エクステントを持つようです。

とりあえず、エクステントは参照できる期間のことで、動的エクステントは参照できる タイミングが実行時に動的に決まり、無限エクステントは参照がある限り参照できる(無限に伸びる) という意味だと理解しました。

extentは広さとか大きさという意味なので、コードブロックの広さが実行時の期間を表す、 というイメージを持てば良さそうです。

24.1 パッケージ

パッケージに関して未だに苦手意識があって(触ってないからですが)、それが原因でCommonLispをじっくり触ってない、という気がするので先にパケージの仕組みを勉強してみます。

参考にしたのは以下のページです

パッケージを作るおそらくもっともプリミティブな関数はmake-packageですが、in-packageと共に文字列をパッケージ名に指定できます。

CL-USER> (make-package "YO" :use '("COMMON-LISP"))
#<PACKAGE "YO">

CL-USER> (in-package "YO")
#<PACKAGE "YO">

YO> (make-package "Yo" :use '("COMMON-LISP"))
#<PACKAGE "Yo">

YO> (in-package "Yo")
#<PACKAGE "Yo">

|Yo|> (in-package :yo)
#<PACKAGE "YO">

YO>

文字列の場合は大文字小文字を区別しますが、キーワードやシンボルの場合は普通に大文字に変換されます。

(make-package パッケージ名 :use パッケージリスト)(in-package パッケージ名)のパッケージ名、パッケージリストでの指定ですが、in-packageのパッケージ名のみクォート無しでの指定になります。

キーワードはどこでも使えるので、とりあえずキーワードを指定しておけば迷わずに済みそうです。

ちなみに(in-package)は(SBCLでは)*package*へのsetqにマクロ展開されます。

importexportuse-packageの説明はPAIPのものでわかりました。

省略されているシャドウイングの方法ですが、DEFPACKAGE の shadowing-import-from についてのメモ - 幼年期のはじまりにわかりやすい例があります。これで勝つる。

shadowshadowing-importを使えば手でシャドウイングできます。(shaodwの最後の例が謎ですが……)

GPSバージョン1

説明読んでも、結局「何をどう計算したいのか」が理解できませんでした……

オペレータってGPSにおいて何?適合ってどういう操作?と混乱しました。。

なんとなく、

  • 現在の状態の集合
  • 目標の状態の集合
  • 状態の集合を受け取り、新たな状態の集合を返すオペレータ

の組み合わせから、「現在の状態の集合から目標の状態の集合に到達するために必要なオペレータの並び」を返すプログラムかな、と推測できます。

表4.1とコードから、GPSの流れを探ってみます。まずグローバル(スペシャル)変数は

  • *states* 現在の状態のリスト
  • *op* オペレータのリスト

の二つです。構造体として

  • op 動作を表すシンボルと、前提として必要な状態、生成する状態、消去する状態 の各集合を持つ

を定義します。次に、関数は

  • GPS 現在の状態の集合、目標の状態の集合、オペレータのリストを取り、現在の状態から目標に到達できる(SOLVED)かできない(NIL)かを返す
  • achieve 目標の状態を取り、現在の状態の集合に含まれているか、又は現在の状態の集合にオペレータを適用した新しい状態に含まれるかを判定する
  • appropriate-p 目標の状態とオペレータを取り、オペレータがその目標の状態を生み出すかを調べる
  • apply-op オペレータを取り、それが前提とする状態が現在の状態の集合にあるなら、実行したことをprintして、現在の状態を変更する

となっているようです。必要なオペレータの並びを返すのではなくprintしていたり、 achieveがachieve-pではない(動作も副作用も)などが気になりますが、 後に解決されているかもしれないのでとりあえず後に回します。

ここで少しメタな話になるのですが、GPSのコードに対してどう取り組むのが一番身になる/楽しいでしょうか。

  1. コードを読んで、動作を理解する
  2. コードをそのまま写して、他人のコードの書き方を学ぶ
  3. 動作の概要を把握して、概要から自分の手で再構築する

3の概要の把握で1は達成できそうです。3が一番楽しそうですが、 2によって他人のコードの書き方を学ぶのも大切そうです。 また、ただ見ながら写すよりも、少しの間覚えたり、頭を少し使ったほうが なんとなく身になる気がします。

ということで折衷案として

  1. コードの詳細をコメントに直して、それから再構築して答え合わせする
  2. 動作の概要・仕様をコメントにして、それから自分なりに書いて楽しむ

ということにします。

コード自体は本の内容そのものなので、上記のa,bとbから書いたGPSバージョン1を 残しておきます。

a

(defvar *states*) ; 現在の状態の集合
(defvar *ops*)    ; オペレータの集合

(defstruct op
  ;; 動作を表すシンボルと、
  ;; 前提条件、生成する状態、消去する状態 の各集合を持つ
  )

(defun GPS (*states* goals *ops*)
  ;; goalsが全てachieveを満たすなら'SOLVEDを、そうでなければNILを返す
  )

(defun achieve (goal)
  ;; すでに現在の状態にgoalが含まれているか
  ;; そうでなければ
  ;;   *ops*の中で、goalについてappropriate-pを満たすもののうち
  ;;   どれかがapply-opを満たすか
  )

(defun appropriate-p (goal op)
  ;; opの生成する状態に、goalが含まれているか
  )

(defun apply-op (op)
  ;; opの前提条件が全てachieveを満たす場合
  ;;   opの動作を表示する
  ;;   現在の状態にopが生成する新たな状態を追加する
  ;;   現在の状態からopが消去する状態を取り除く
  ;;   tを返す
  )

b

  • 現在の状態の集合、目標の状態の集合、オペレータの集合を使う
  • オペレータは状態の集合を取り、状態を追加・削除した新たな状態を返す
  • オペレータは前提の状態の集合を持ち、それが対象の状態に含まれている場合に適用される
  • 関数GPSの目的は、現在の状態の集合から目標の状態の集合へ到達できるかどうかを示すこと
  • GPSは到達できるなら動作のリストを、できないならばNILを返す
  • 集合にはリストを、オペレータには構造体を使う(学習用)
  • オペレータ構造体は、動作を表すシンボルと、前提として必要な状態、生成する状態、消去する状態 の各集合を持つ
  • 集合にはリスト用ではなく集合用の関数を使う(学習用)

bを元に書いたgps

Clojure->的なマクロと、3.19のfind-allとop、appropriate-pを使っています。

副作用を使わずに関数型のコードを意識して書きましたが、 見通し悪い気がします……デザインの試行錯誤した方が良さそうですね。

使用例は次のトピックにあります。

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defun insert-second (xs x)
    (cons (car xs) (cons x (cdr xs))))

  (defun thread-second (fst rests)
    (reduce
     (lambda (inner outer)
       (insert-second outer inner))
     rests :initial-value fst)))

(defmacro -> (fst &rest rests)
  (thread-second fst rests))

(defun find-all (item sequence &rest keyword-args
                 &key (test #'eql) test-not &allow-other-keys)
  (if test-not
      (apply #'remove item sequence
             :test-not (complement test-not) keyword-args)
      (apply #'remove item sequence
             :test (complement test) keyword-args)))

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

(defun gps (starts goals ops)
  (let* ((result (achieve-all starts goals ops)))
    (when result
      (reverse (cons 'solved (actions result))))))

(defun achieve-all (starts goals ops)
  (reduce (achieve-all-fn goals ops)
          goals
          :initial-value starts))

(defun achieve-all-fn (goals ops)
  (lambda (before goal)
    (when before
      (achieve before goal goals ops))))

(defun success (after actions) (list t after actions))
(defun actions (result) (third result))
(defun states (result) (second result))

(defun push-action (state action)
  (success (states state) (cons action (actions state))))

(defun del-st (state op)
  (success (set-difference (states state) (op-del-list op)) (actions state)))

(defun add-st (state op)
  (success (union (states state) (op-add-list op)) (actions state)))

(defun affect-op (state op)
  (-> (push-action state (op-action op))
      (del-st op)
      (add-st op)))

(defun appropriate-p (goal op)
  (member goal (op-add-list op)))

(defun achieve (before goal goals ops)
  (if (member goal before)
      before
      (some (apply-op-fn before goal goals ops)
            (find-all goal ops :test #'appropriate-p))))

(defun apply-op-fn (before goal goals ops)
  (lambda (op)
    (let ((pre (achieve-all before (op-preconds op) ops)))
      (when pre (affect-op pre op)))))

遊ぶ

まずオペレータを定義します。

GPSの問題の定義とはズレた使い方ですが、2個目の例がやりたかったのでこうしました。

(defparameter *okeya-ops*)
(setf *okeya-ops*
      (list
       (make-op :action '風が吹く
                :add-list '(バタフライ・エフェクトが起きる))
       (make-op :action 'バタフライ・エフェクトが起きる
                :preconds '(バタフライ・エフェクトが起きる)
                :add-list '(地球の裏側の人が飛ばされてくる))
       (make-op :action '地球の裏側の人が飛ばされてくる
                :preconds '(地球の裏側の人が飛ばされてくる)
                :add-list '(人口が増える))
       (make-op :action '人口が増える
                :preconds '(人口が増える)
                :add-list '(桶屋の客が増える))
       (make-op :action '桶屋の客が増える
                :preconds '(桶屋の客が増える)
                :add-list '(桶屋が儲かる))))

自分で書いたバージョンです。

CL-USER> (gps (list nil) '(桶屋が儲かる) *okeya-ops* )

(風が吹く バタフライ・エフェクトが起きる 地球の裏側の人が飛ばされてくる 人口が増える 桶屋の客が増える SOLVED)

次にPAIP版です。表示を変えてみました。

CL-USER> (GPS nil '(桶屋が儲かる) *okeya-ops* )
風が吹くとバタフライ・エフェクトが起きる
バタフライ・エフェクトが起きると地球の裏側の人が飛ばされてくる
地球の裏側の人が飛ばされてくると人口が増える
人口が増えると桶屋の客が増える
桶屋の客が増えると桶屋が儲かる
SOLVED

楽しい。

広告を非表示にする