プログラミングを頑張る日記

プログラミングを勉強して、ハッカーになろう

Common Lispを頑張る(20)

嵐の前の静けさって感じの日曜日です。
それはともかく、久しぶりに「Land of Lisp」をやります。

久しぶりに読んだら次はリストの話でした。
ただのリストから一歩進み、特殊なリストを紹介してくれるそう。

普通のリスト

前にもありましたが、リストは全てコンスセルの連なりです。
リストの最後のコンスセルの右スロットはNILです。

CL-USER> (cons 1 (cons 2 (cons 3 nil)))
(1 2 3)
CL-USER>

consを使いまくってリストにするのも、(1 2 3)とするのも
読みやすさ以外は全く同じことです。

ドットリスト

最後のコンスセルの右スロットにNILを入れなかったら
どうなるのか、という話です。

CL-USER> (cons 1 (cons 2 3))
(1 2 . 3)
CL-USER>

見つかった最後の要素の前にドットを置いて、
「リストにしようと思ったらNILが来るべき場所に3が来た」と
Lispが教えてくれているようです。

NIL以外の値でリストが終端されているものはドットリストと
呼ばれるそうです。
ドットリストは異端児であり、そんなに使うことはないそうです。
でも出てきちゃうことはあるので慣れておこうとのこと。

実用的なドットリストの使い方としては、対を表現することだそう。

CL-USER> (cons 2 3)
(2 . 3)
CL-USER>

この対の表現方法はLispでは便利かつ効率的で、
二次元の点の座標、複雑なデータの中のキーと値などに
使われるそうです。

循環リスト

最後のコンスセルの右スロットの中に、NILを入れる代わりに
そのリストの最初のコンスセルを指定したらどうなるでしょう。

コンスセルはそれぞれメモリ上に独立したオブジェクトとして
存在しているため、自分が属するリストの前の方を指すことだって
できます。その様なリストは循環リストと呼ばれるそうです。

循環リストを試す前に下記を実行しておくようにとのこと。

CL-USER> (setf *print-circle* t)
T
CL-USER>

各コンスセルが既に表示されているものかどうか調べて
表示ルーチンが無限ループするのを避けるそうです。

さて、準備ができたので循環リストを作ってみます。

CL-USER> (defparameter *circle* (list 1 2 3))
*CIRCLE*
CL-USER> (setf (cdddr *circle*) *circle*)
#1=(1 2 3 . #1#)
CL-USER> 

これで(1 2 3 1 2 3 ...)という無限に続くリストが作れました。
しかしどう使ったものかよくわかりませんね。
*print-circle*をnilにして、次に行きます。

連想リスト

リストのたぐいの中でも特に便利なのは連想リスト(alist)だそう。
連想リストはキーと値が対になったリストですね。
テキストゲーム作成のときも使いました。

誰が何の勉強をしているかのalistを作ります。

CL-USER> (defparameter *study* '((neko . Lisp)
				 (inu . C++)
				 (nezumi . Ruby)))
*STUDY*
CL-USER> *study*
((NEKO . LISP) (INU . C++) (NEZUMI . RUBY))
CL-USER>

全部ドットリストです。
キーを使って検索するときはassocを使えば良いのでした。

CL-USER> (assoc 'neko *study*)
(NEKO . LISP)
CL-USER>

新しい要素を追加するときにはpushを使えばいいし、
既にあるキーと同じキーの要素を追加したら、
その値が最新の値になるのです。割りかし覚えています。

CL-USER> (push '(risu . Go) *study*)
((RISU . GO) (NEKO . LISP) (INU . C++) (NEZUMI . RUBY))
CL-USER> (push '(nezumi . python) *study*)
((NEZUMI . PYTHON) (RISU . GO) (NEKO . LISP) (INU . C++) (NEZUMI . RUBY))
CL-USER> (assoc 'nezumi *study*)
(NEZUMI . PYTHON)
CL-USER>

alistは変更があり得るような集まりを管理するのに便利です。
履歴が残ることも素敵ポイントですね。

ただし、10数項目程度のリストでもなければ、
データを取り出す時にあまり効率の良い方法ではないそうです。
Lisperはまずalistを使い、成長していくにつれ
他のデータ型を使うようになるそうです。

コンスセルと性能

コンスセルはリスト類似の構造を表現するのに便利なので
Lisperは特別に性能を求めることがなければ、コンスセルだけを
使って問題を解決しようとするそうです。
そして性能が必要だとしてもコンスセルを使うのは悪くない、
コンスセルの変更はアセンブリの1命令にまで最適化できるから、
だそうです。

木構造データ

Lispのデータは式の構文(S式)によって表現されます。
階層的で木構造からなるデータは自然にその形で表現できるそうです。
家の構成部品をLispで表現するというのが例です。

CL-USER> (defparameter *house* '(((モルタル (セメント)
				              ()
				              ())
				     (レンガ))
				 ((ガラス)
				     (窓枠)
				     (カーテン))
				 (屋根 (板葺き)
				       (煙突))))
*HOUSE*
CL-USER>

参考書のものを何となく日本語にしただけですが。
家を構成する部品の階層構造が、見て取れる感じになっています。

しかし、木構造より複雑なデータを使い始めると、
たとえコンスセルによるデータの表現自体ができても
S式を見てデータの構造を理解するのは難しくなるそうです。
例えばあるノードが任意のノードとエッジで接続しているような
グラフはプログラムで適切に可視化することは難しいそうで、
Lispのエレガントなシステムによってもそれは変わらないとのこと。
さてではどうするか…。

といいところですが、今日はここまでにします。