一般的に言って,データ構造は何かを表現するために使われる. 配列は幾何学的変換を表現できる. ツリーは命令のヒエラルキーを表現できる. グラフは鉄道ネットワークを表現できる. Lispではクロージャが表現手段に使われることがある. クロージャ内では変数束縛は情報を蓄えることができるし, 複雑なデータ構造を構築するときのポインタの役目を果たすこともできる. 束縛を共有するかまたは互いを参照できるクロージャのグループを作ることで, データ構造とプログラムの長所を併せ持ったハイブリッド・オブジェクトを創れる.
その内部では共有された束縛がポインタになっている. クロージャにはポインタを高度に抽象化して扱う利点がある. 静的なデータ構造で表現する筈の物を表現するクロージャを使うことで, しばしば優雅さと効率が大きく向上するのを期待できる.
クロージャには3個の便利な性質がある. アクティブで,ローカルな状態を保持していて,複数のインスタンスを造れることだ. アクティブでローカルな状態を持ったオブジェクトの複数のコピーを使うべき所とはどこだろう? 何よりもネットワークに関わるアプリケーションが挙げられる. 多くの場合ネットワークの節点はクロージャとして表現できる. クロージャはそれ自身のローカルな状態を保持できるだけでなく,別のクロージャを参照できる. だからネットワーク内の節点を表現するクロージャは, 出力を送るべき幾つかの節点(クロージャ)の状態を理解できる. これはある種のネットワークならそのままコードに変換できるということだ.
この章と次章では,ネットワークを探索する方法を二つ検討する. まず,構造体として定義された節点と, ネットワークを探索する別のコードを使う伝統的な方法を追ってみる. そして次章で,同じプログラムを単一の抽象化手法で作る方法を示す.
例として,可能な中で最も単純な応用方法を使う. 「20の質問」を行う類のあれだ. ここで使うネットワークは二分ツリーで,葉でない節点は二択式の質問を保持し, 質問への答えに応じて右か左の部分ツリーへ下って探索して行く. 葉の節点は返り値を保持する. 探索が葉に到達すると,その値は探索結果として返される. このプログラムの実行結果は第\ref{fig:TwentyQuestions}図に示したようになる.
> (run-node 'people) Is the person a man? >> yes Is he living? >> no Was he American? >> yes Is he on a coin? >> yes Is the coin a penny? >> yes LINCOLN\caption{「20の質問」の実行例.} \label{fig:TwentyQuestions}
伝統的な方法は節点を表現するための何らかのデータ構造を定義することだろう.
節点は幾つかの情報を持たなければならない:それが葉であるかどうか.
そうなら返す値は何か.そうでないなら質問は何で,答えに応じてどちらへ進むか.
それを実現するのに十分なデータ構造を第\ref{fig:ReprDefNode}図に示した.
それは最小限の構造を持っている.
contents
欄は質問または返り値を保持する.
節点が葉でないなら,
yes
欄とno
欄で答えに応じてどの節点に進むかを指定する.
葉であるなら,それらが空でなのでそのことが分かる.
*nodes*
はグローバルなハッシュ表で,これに節点名の一覧を載せる.
最後にdefnode
は新しい節点(葉であってもそうでなくてもいい)を創り,
それを*nodes*
に蓄える.
これらの素材を使ってツリーの最初の節点が定義できる:
(defnode 'people "Is the person a man?" 'male 'female)
第\ref{fig:SampleNetwork}図には, 第\ref{fig:TwentyQuestions}図のやりとりを実現するのに必要なだけのネットワークを示した.
(defstruct node contents yes no) (defvar *nodes* (make-hash-table)) (defun defnode (name conts &optional yes no) (setf (gethash name *nodes*) (make-node :contents conts :yes yes :no no)))\caption{節点の表現と定義.} \label{fig:ReprDefNode}
(defnode 'people "Is the person a man?" 'male 'female) (defnode 'male "Is he living?" 'liveman 'deadman) (defnode 'deadman "Was he American?" 'us 'them) (defnode 'us "Is he on a coin?" 'coin 'cidence) (defnode 'coin "Is the coin a penny?" 'penny 'coins) (defnode 'penny 'lincoln)\caption{ネットワークの例.} \label{fig:SampleNetwork}
そうなれば必要なのはこのネットワークを探索し,
質問を表示し,示された経路を辿る関数を書くことだけだ.
その関数run-node
は第\ref{fig:TraverseNetwork}図に示した.
名前が与えられると,対応する節点を探す.
それが葉でないならcontents
欄の質問を行い,
答えに応じて二つの可能な行き先の中から選んで探索を続ける.
節点が葉であるなら,run-node
はcontents
欄の内容を返すだけだ.
この関数は第\ref{fig:SampleNetwork}図で定義されたネットワークを使い,
第\ref{fig:TwentyQuestions}図に示した出力を行う.
(defun run-node (name) (let ((n (gethash name *nodes*))) (cond ((node-yes n) (format t "~A~%>> " (node-contents n)) (case (read) (yes (run-node (node-yes n))) (t (run-node (node-no n))))) (t (node-contents n)))))\caption{ネットワーク探索のための関数.} \label{fig:TraverseNetwork}
前章で書いたネットワーク・プログラムは, どのプログラミング言語でも書けるようなものだった. あのプログラムは全く単純なもので,他の書き方があるなどとはなかなか思えない. しかしそれがあるのだ ---実際,遥かに単純に書き直せる.
(defvar *nodes* (make-hash-table)) (defun defnode (name conts &optional yes no) (setf (gethash name *nodes*) (if yes #'(lambda () (format t "~A~%>> " conts) (case (read) (yes (funcall (gethash yes *nodes*))) (t (funcall (gethash no *nodes*))))) #'(lambda () conts))))\caption{クロージャへとコンパイルされるネットワーク.} \label{fig:CompiledNetwork}
第\ref{fig:CompiledNetwork}図に示したコードはその点を説明している.
これがあのネットワークを機能させるのに必要な全てだ.
節点をデータ構造として表し,それを探索する別の関数を創る代わりに,
ここでは節点をクロージャとして表現した.
前の例では構造体の中に蓄えられていたデータはクロージャ内の変数束縛に蓄えられている.
節点自身の中にrun-node
の機能が組み込まれているので,もうそれは必要ない.
探索を始めるには,始めたい節点でfuncall
を呼ぶだけだ:
(funcall (gethash 'people *nodes*)) Is the person a man? >>
それから先の実行結果は前の実装法と全く変わりない.
節点をクロージャとして表現することで, 「20の質問」で使うネットワーク全体をコードに変換できた訳だ. 見た通り,上のコードでは実行時に名前によって節点のクロージャを探さなければならない. しかしネットワークが実行中に再定義されることがないと分かっているなら, 更に拡張を加えられる. 節点のクロージャがハッシュ表を介さず,子を直接呼ぶようにすることができる.
(defvar *nodes* nil) (defun defnode (&rest args) (push args *nodes*) args) (defun compile-net (root) (let ((node (assoc root *nodes*))) (if (null node) nil (let ((conts (second node)) (yes (third node)) (no (fourth node))) (if yes (let ((yes-fn (compile-net yes)) (no-fn (compile-net no))) #'(lambda () (format t "~A~%>> " conts) (funcall (if (eq (read) 'yes) yes-fn no-fn)))) #'(lambda () conts))))))\caption{静的参照によるコンパイル.} \label{fig:CompileWithStaticRef}
第\ref{fig:CompileWithStaticRef}図には新しい定義を示した.
ここでは*nodes*
はハッシュ表ではなく捨ててもいいリストだ.
節点は前と同じくdefnode
で定義するが,この時点ではクロージャは生成されない.
全ての節点の定義後,
compile-net
を呼んでネットワーク全体を一度にコンパイルする.
この関数は再帰的にツリーの葉まで下り,
戻りながら各節点で二つの部分ツリーそれぞれに対応する節点/クロージャを返す
\footnote{この実装法ではネットワークがツリーだと仮定している.
この章での実装法ではそうでなければならない.}.
だから全ての節点は二つの子の名前を把握しているだけなのではなく,
それらを直に制御できる.
compile-net
の元の呼び出しが返ると,
ネットワークのコンパイルした部分に対応する関数が得られる.
> (setq n (compile-net 'people)) #<Compiled-Function BF3C06> > (funcall n) Is the person a man? >>
compile-net
は二つの意味で「コンパイル」を行うことに注意しよう.
まずネットワークの抽象的表現をコードに変換するという一般的な意味のコンパイルを行う.
さらにcompile-net
自身が処理系にコンパイルされていれば,
返される関数もコンパイルされたものだ.
(wowowページを参照.)
ネットワークをコンパイルした後はdefnode
の作ったリストはもう要らないので,
捨ててしまって(例えば*nodes*
にnilを代入する)
ガーベジ・コレクタに任せればよい.
ネットワークに関わる多くのプログラムが, 節点をクロージャにコンパイルすることで実装できる. クロージャはデータ・オブジェクトであり,構造体が表現できるものを表現するのに使える. そうするには見かけたことのない思考法が幾らか要るが, 見返りには高速で優雅なプログラムが得られる.
マクロはクロージャをデータ表現に使うときに大きな助けになる. 「クロージャで表現する」と言うのは「コンパイルする」を言い直したに過ぎない. マクロはコンパイル時に仕事をこなすのだから,この技法にとって全く自然な手段なのだ. マクロの導入後,第23, 24章で, ここで使った戦略に基づいたずっと大規模なプログラムを提示する.