第7章 単純なリストの先へ
リストのお話を深めていくことにする。世の中のデータをリストで表現できるだろうか。
Lispの理解が進まないのは完全に(数学的)ロジックで組み上げられているから。
僕の頭の中にはコンピュータのハードが居て、どうしてもコンピュータからの視線で理解しようとしてしまう。此のギャップを超えられるか。
7.1 奇妙なリスト
リストはコンスセルで維持された構造を持っている。奇妙と言うよりよく使われるリスト構造だね。
リストの基本形はこれだった。
(cons 1 (cons 2 (cons 3 (nil)))) ;;今まで考えてたリスト こうやってどこまでも連なれる
(1 2 3)ドットリスト
(cons 1 (cons 2 3)) ;;ドットリスト つまり最後にnilがない
(1 2 . 3)
(cons 2 3) ;;対の表現 最後の要素がnilでないのでドットを表示して教えてる
(2 . 3)nil以外でリストが終端されている際には、最後の要素の前にドットが表示される。
次の対という概念で使われる。
対
実用的にドットリストを使う例しては、対がある。前記の例は2と3の対であった。
キーと値の対を表現できるので、とても役に立つ。
「(幅 . 34)(高 . 15)(奥 . 50)」とかの表現に役立つのだ。(日本語なんだが)
循環リスト
此の図のように、最後のコンスセルが先頭のコンスセルを指していると、ループを起こすような構造を持つリストである。
普通のリストを循環リストに変更するには、最後のコンスセルのnilを先頭へのポインタにすればよい。
[1]> (setf *print-circle* t) ;;所謂オマジナイ
T
[2]> (defparameter foo (list 1 2 3))
FOO
[3]> (setf (cddr foo) foo) ;;3個目の要素に先頭へのポインターを
#1=(1 2 . #1#) ;;#1#の記法に注意
[4]>3行目のsetfに注目。「(setf (cddr foo) foo)」このように第1引数に複雑な式を書けるのはsetfの利点だ。さらには9章にて。
連想リスト
特に便利と思うのが連想リストだ。最近は此のようなリストを色んな言語で扱えるようだ。
連想リスト、別名alist。
alistはキーと値の対のリストだ。考えやすいね。
習慣的に同じキーがある場合には最初の対が採用されることが多い。これはあるキーに対する更新値をリストの先頭に置いておけば、あるタイミングからは最新値を求めることができるのだ。1代前の値が欲しければ、2番目を取ればよい。履歴を辿ることもできるわけだ。assoc関数を使う。
[1]> (defparameter *drink-order* '((bill . double-espresso) ;;注文表
(lisa . small-drip-coffee)
(john . medium-latte)))
*DRINK-ORDER*
[2]> (assoc 'lisa *drink-order*) ;;lisaの注文を確認
(LISA . SMALL-DRIP-COFFEE)
[5]> (push '(lisa . large-mocha-with-whipped-cream) *drink-order*) ;;lisaの注文変更
((LISA . LARGE-MOCHA-WITH-WHIPPED-CREAM) (BILL . DOUBLE-ESPRESSO)
(LISA . SMALL-DRIP-COFFEE) (JOHN . MEDIUM-LATTE))
[6]>(assoc 'lisa *drink-order*) ;;lisaの注文確認
(LISA . LARGE-MOCHA-WITH-WHIPPED-CREAM)7.2 複雑なデータを扱うには
此の世の中、単純な1対1のリストでは表現しきれない。
Lispにおいて、コンパイラはコンスセルの変更をアセンブリ(言語)の1命令にまで最適化できるのだ。
遠慮しないでリスト構造を利用しよう。
木構造のデータの可視化
下記は家屋の構成部品をLispで表現したものだ。わかりやすく日本語を使った。
このように階層的で木構造を使ったデータはLispにとってごく自然にその構造を表現できる。
やっといつもの雰囲気になってきたね。RDBとかの構えでなければ此のような構造を自然に表現できるLispはアプリケーションとして完結するんじゃないだろうか。いやするね。
会計、台帳、顧客管理、小規模な在庫管理、ゲーム(^^)等々便利だ。バイナリーを意識してファイルへの読み書きするの言語システムに比べて、比較的御しやすいじゃないか。
(defparameter *家*
'((壁 (モルタル (セメント) (水) (砂)) (レンガ))
(窓 (ガラス) (窓枠) (カーテン))
(屋根 (屋根板) (煙突))))
グラフを可視化する
しかし木構造よりも複雑な構造を保つデータに関しては、ハードルが一気に上がるようだ。
ここで言うグラフとは何だろう。
最初のリーディングなので、ここは流す。
数学におけるグラフとは、エッジにより結合されたノードの集合体だそうだ。ノードやエッジには付加的なデータが結び付けられることもあるとか。
5章における魔法使いの館のマップは此の形式で作られており、此の形式を有向グラフと呼ぶ。
魔法使いの館では2つのalistを使った。1つはノードの情報を保持し、もう1つはエッジの情報を保持していた。これを改名して使おう。
(defparameter *wizard-nodes* '(
(living-room (you are in the living-room. ;;居間
a wizard is snoring loudly on the couch.)) ;;魔法使いはいびきを掻いて眠っている
(garden (you are in a beautiful garden. ;;庭
there is a well in front of you.)) ;;面前に井戸がある
(attic (you are in the attic. ;;屋根裏
there is a giant welding torch in the corner.)))) ;;大きな溶接トーチがある
(defparameter *wizard-edges* '((living-room (garden west door) ;;西へのドアで庭へ
(attic upstairs ladder)) ;;上への階段で二階へ
(garden (living-room east door)) ;;東へのドアで居間へ
(attic (living-room downstairs ladder)))) ;;下への階段で居間へ7.3 グラフを作る
グラフを描画するオープンソースの道具があるので、使ってみよう。
下記は以前見たであろうが、これがGraphvizの書いた図だ。
Graphvizを使ってゲーム世界のグラフを出力するライブラリを作って見よう。
ＤＯＴの情報を生成する
GraphvizへのDOTファイルを作ろう。プレーヤーが到達可能なノードの識別子と、それらをつなぐエッジをDOTフォーマットに変換し、各ノードとエッジに付加するラベルを付けてやる。
ノードの識別子を変換する
dot-name関数は無条件にアルファベット以外を_に変換してしまう。foo?とfoo*が存在していれば両方ともfoo_になるので衝突してしまう。
(defun dot-name (exp)
(substitute-if #\_ (complement #'alphanumericp) (prin1-to-string exp)))
> (dot-name 'living-room)
"LIVING_ROOM"
> (dot-name 'foo!)
"FOO_"
> (dot-name '24)
"24"
(substitute-if #\e #'digit-char-p "I'm a133t hack3r!"
"I'm a leet hacker!" ;;数字がeになっている
(substitute-if 0 #'oddp '(1 2 3 4 5 6 7 8))
'(0 2 0 4 0 6 0 8) ;;奇数が0になっている
(complement #'alphanumericp) ;;alphanumericpが真を返す文字の補集合を求める
;;complementは高階関数グラフのノードにラベルをつける
次にノードのそばに描かれるラベルの内容を生成する関数を作る。ラベルは簡潔にと言うのがコツだ。
また余計な文字(改行とか)が付いてこないようにしている。ラベルの長さは30文字まで。
(defparameter *max-label-length* 30)
(defun dot-label (exp)
(if exp
(let ((s (write-to-string exp :pretty nil)))
(if (> (length s) *max-label-length*)
(concatenate 'string (subseq s 0 (- *max-label-length* 3)) "...") s)) ""))ノードのＤＯＴ情報を生成する
さあ、DOTファイルを書き出そう。
(defun nodes->dot (nodes)
(mapc (lambda (node) ;;mapcarより早い
(fresh-line)
(princ (dot-name (car node)))
(princ "[label=\"")
(princ (dot-label node))
(princ "\"];"))
nodes))
> (nodes->dot *wizard-nodes*)
LIVING_ROOM[label="(LIVING_ROOM (YOU ARE IN TH..."];
GARDEN[label="(GARDEN (YOU ARE IN A BEAUT..."];
ATTIC[label="(ATTIC (YOU ARE IN THE ATTI..."]エッジをＤＯＴフォーマットに変換する
次はエッジの番だ。
(defun edges->dot (edges)
(mapc (lambda (node)
(mapc (lambda (edge)
(fresh-line)
(princ (dot-name (car node)))
(princ "->")
(princ "[label=\"")
(princ (dot-label (cdr edge)))
(princ "\"];"))
(cdr node)))
edges))
> (edges->dot *wizard-edges*)
LIVING_ROOM->GARDEN[label="(WEST DOOR)"];
LIVING_ROOM->ATTIC[label="(UPSTAIRS LADDER)"];
GARDEN->LIVING_ROOM[label="(EAST DOOR)"];
ATTIC->LIVING_ROOM[label="(DOWNSTAIRS LADDER)"]ＤＯＴデータを完成させる
(defun graph->dot (nodes edges)
(princ "digraph{")
(nodes->dot nodes)
(edges->dot edges)
(princ "}"))ＤＯＴファイルを画像にする
そしてDOTファイルを画像にする。
(defun dot->png (fname thunk)
(with-open-file (*standard-output* fname
:direction :output :if-exists :supersede)
(funcall thunk))
(ext:shell (concatenate 'string "dot -Tpng -0 " fname)))サンクを使うテクニック
“defun dot->png (fname thunk)”におけるthunkに注意。サンクと呼ばれる関数だ。これは引数を取らない零項(nullary)関数と呼ばれるもので、実行したくない計算を包んでいる。つまり、呼ばれても何もしないよ、と言う関数なんだ。サンク(thunk)またはサスペンション(suspension)とも呼ばれるそうだ。デバッグ時にはここになんかの関数名を書くことになるかもですね。
ファイルへの出力
with-open-fileによって情報をファイルへ書き出す。
(with-open-file (my-stream ;;これがストリームオブジェクトを受ける
"testfile.txt" ;;ファイル名
:direction :output
:if-exists :supersede)
(princ "Hello File!" my-stream)) ;;ストリームオブジェクトへ出力ストリームを作る
princなどの関数はストリーム引数を受け取ると、コンソールではなく、そのストリームオブジェクトへデータ出力する。with-open-fileは与えられた変数名を持つストリーム変数を生成するのだ。
ストリームオブジェクトの詳細は12章のお楽しみだ。
キーワード引数を理解する
ファイルへ出力するwith-open-file関数はタクサンの引数を必要とする。それだけ複雑な動きをするということなのだが、ここに:文字(コロン)を伴う引数が見えるね。これをキーワード引数と言う。キーワード引数は名前と値でセットだ。例えば:direction :outputのように、:direction(動作)に対して:output(出力)を指定している。:if-exists(同じファイルが存在している際の動作は)に対しては:supersede(以前の内容を捨てる)が指定されている。
他の言語とはちょっと違う並びだが、関数と引数と考えるときちんとした並びである。
下記のソースを見てみる。:(コロン)付きのシンボルはキーワードシンボルと呼ばれ、常に自分自信を指すシンボルである。下記のように:付きのキーワードシンボル:cigarの値は変更することが出来ない。そしてその値は常に自分だ。ファイル出力の際などにその動作を指定するのに使うという意味がわかっただろうか。
> (let ((cigar 5)) ;cigarに5を設定して返すコード
ciger)
> :cigar
:CIGAR
> (let ((:cigar 5))
:cigar)
** -LET: :CIGAR is a constant, may not be used as a variable
:cigarは定数ですので変数のようには使えません
> :cigar
:CIGAR ;;常に此の値コンソールへの出力を横取りする
*standard-output*について。これは標準のグローバル変数で、出力先を宣言しているものだ。ダイナミック変数とも呼ばれる。さっきのコードをもう一度。
(with-open-file (my-stream ;;これがストリームオブジェクトを受ける
"testfile.txt" ;;ファイル名
:direction :output
:if-exists :supersede)
(princ "Hello File!" my-stream)) ;;ストリームオブジェクトへ出力with-open-fileにて出力先としてtestfile.txtが指定されている。with-open-fileは一時的にダイナミック変数の*standard-output*を一時的にファイル出力に変更するのだ。(初期値はもちろんコンソールだ)従ってこのプログラムが動作している間の出力はファイルで、終了時に元に(コンソールとか)戻されるということになる。thunk内で出力があったら、それも同じファイルへ出力される。
使ってみないと実感できないよねえ。
グラフを画像にする
グラフの最後に全てのコードをまとめて。
(defun graph->png (fname nodes edges)
(dot->png fname (lambda () (graph->dot nodes edges))))
;;graph->dotはdot->pngの配下にいる(lambdaでサンクしている)ので出力はファイル(fname)へ出される。7.4 無向グラフを作る
あとから読むので、省略しておく。
7.5 本章で学んだこと
此の章では変わり者リストを覚え、グラフを描画するライブラリを教わった。
其の過程で次のことを学んだ。
- ドットリストとはnilで終わっていないリストである。REPLで表示されると、最後の要素の前にドットがおかれる。
- 対とは二つの要素しか無いドットリストである。2つの要素をコンスして得られる。
- 循環リストとはリストの最後のセルが其のリストの先頭を指しているものだ。
- 連想リスト(alist)とは対のリストである。キーと値の関係を保存するデータ構造を表現できる。
- Lispの式の構文は階層的なデータ構造を保存・表示するのに適しているが、より複雑なデータを可視化するには、外部のツールも役に立つ。
- データ構造が数学的なグラフ構造であるなら、Graphvizでグラフの図を生成してみるとわかりやすい。
- Lispプログラムからテキスト形式のデータを生成する際によく使われるテクニックは、デバッグの際にに便利なように、コンソールにテキストを出力するような関数にしておくことだ。実際のアプリケーションでは其の関数をサンクに包み、コンソール出力を横取りしてファイルなどの適切な出力先へと変更する関数に渡すだけでよい。
コメント