2014-07-27

"ガベージコレクションのアルゴリズムと実装" 中村成洋/相川光 著 竹内郁雄 監修

プログラムが深刻な問題を抱える時、動的メモリの管理に関するものが多い。メモリ系のバグが厄介なのは、バグが埋め込まれる箇所と、それが顕在化するタイミングが大きくズレていることにある。かつて、必要なデータ領域の確保と解放の問題は、プログラマの責任とされた。今でも、そうなんだろうけど...
整数型や文字型などプリミティブなデータ型を扱う分には、それほど目くじらを立てることもあるまい。だが、大量のデータ領域、あるいは、クラス型や構造体といった抽象化データを扱う場合には注意がいる。メモリ空間を相対アドレスで管理すれば、複雑なデータ構造にもアクセスしやすい。物理的には、参照という形で間接アドレッシングの構造を持つことになる。あの忌み嫌われるポインタってやつだ。こいつの危険性は、参照値をちょいと間違えたり改竄するだけで不正領域を指すことができることで、セキュリティ上の問題となる。あるいは、malloc/free, new/delete といった御呪いを疎かにするだけで、ヒープ領域には文字通りゴミが山積みされる。メモリ資源が豊富になればなるほどコードは複雑化し、バグの頻度が高まるは必定。不要になったゴミは長い間メモリ空間に居座り、メモリリークやらで他のプログラムと衝突したり、コールスタックに矛盾が紛れ込んでシステムを不安定にさせたり、最悪の場合メモリを喰い潰してシステムをダウンさせる。
そこで登場するのがゴミ収集係、そう、ガベージコレクションだ。人間社会においても、ゴミ清掃システムが破綻すると都市は崩壊する。地味な存在こそが、真の意味でシステムを支えている。本来、論理性だけに傾注したいプログラマとって、低水準な構造を意識させられることは思考の足かせとなる。動的空間を意識せずに済むというだけで、情報のゴミに翻弄される酔っ払いは幸せよ...

しかしながら、自動化という言葉は、心地よい響きがするだけに迷信となりやすい。厄介な機能を隠してくれるということは、その危険性までも隠蔽することになる。
近年、ポインタの概念を排除した多くの高水準言語を見かける。だが、むろんポインタがなくなったわけではなく、隠しているに過ぎない。トリッキーなキャストを要求するようなデータ定義が危険なことに変わりはない。ゴミ収集の仕掛けや癖を知っておくだけでも、危険なデータ構造を定義するリスクを避けることができよう。
ちなみに、おいらはプログラマではないが、メモリ管理やデータ構造の考え方はハードウェア設計でも参考になる。FIFO構造やスタック構造など物理構造の制限に因われなければ、思考も広がるだろう。おまけに、アルゴリズムを読むのが好きときた。コンパクトでエレガントに書かれる分野だけに、数学的で無味乾燥的なものと思われがちだが、そこには作者の思考物語が埋め込まれている。それが読み取れた時、感動を禁じ得ない...

本書に共感を覚えるのは、実装の解説をデータ型から始めてくれることである。おいらは、データ型やクラス型や構造体などの定義が、コンパクトな仕様書のようなものだと考えている。静的なデータ型を一通り定義するだけで、大方のプログラムイメージが出来上がっている。型の適切な定義は、そのプログラムが何をするものかについて、かなりの事を物語ってくれるはずだ。
実装編では、Python, DalvikVM(Android), Rubinius(Ruby), V8(JavaScript)におけるものが紹介され、言語システムを違った視点から眺められるのも興味深い。ただ、アルゴリズムではやや意外な印象を与える。それは、この技術分野が思ったより推論的で、確率論的であること。人間社会的とも言えようか。自分で明示的にやった方がマシかもしれない、と思わせるところもある。もう少しきちんと管理してくれると思ったのだが、保険の機能ぐらいに思った方がよさそうである。
ガベージコレクションは、大まかに「保守的GC」「正確なGC」の二つに分類される。保守的GCとは、「ポインタと非ポインタとを識別できないGC」のことだという。正確なGCとは、言うまでもなく確実にポインタを識別すること。それがポインタなのかも正確に判断できないとなれば、データ領域を勝手に移動すると本来の参照関係が崩れることになる。よって、フラグメーテーションの問題がつきまとう。
しかしながら、ポインタの識別は構文解析と関わり、言語処理系の支援なしで完璧な判別は困難となる。処理も重そうだし、本筋のプログラムが遅くなったり停止するのでは本末転倒。保守的GCを選択する方が、実用的なようである。
さらに、アルゴリズムが言語処理系に対して独立して設計できるかどうかも、実用性の指標となろう。結局、現実味のある実装は、互いのアルゴリズムの欠点を補い合うような複合的な用い方になる。いまや実用的の代名詞となった、妥協、適当、微妙... ってのが、この世にマッチしているのかもしれん。どうせ世界は不完全だし。現代社会は、何事も面倒なことを覆い隠し、利便性や自動化に邁進していくが、自動化に頼り過ぎる感は否めない。本書は、これを問うているようにも映る。プログラミングが庶民化すると、低品質のソフトウェアが大量に出回る。少なくとも、システムプログラムとアプリケーションプログラムでは、プログラマの意識にも雲泥の差が生じるだろう。高水準という基準も曖昧になっていく。かつて、C言語も高水準言語と呼ばれた。そりゃ、アセンブラ言語に比べれば、見た目からして高級だ。アセンブラ言語だって機械語に比べれば、はるかに抽象度が高い。所詮、相対的な価値観の問題か。今日、高水準と呼ばれるプログラミング言語の一つの指標として、言語システムが動的メモリを自動で管理してくれるかどうか、という見方はできそうである...

1. ガベージコレクションの世界と三つの基本アルゴリズム
1995年、Javaの発表以来、ガベージコレクション技術の有り難さが広く認知されるようになった。しかし、その歴史は古く、1959年、Lispの設計で、D.Edwards が実装したという。
本書は、基本的なアルゴリズムに、「マークスイープGC」「参照カウント」「コピーGC」の三つを挙げ、他は派生型や組合せとしている。マークスイープGCは1960年、John McCarthy が発表... 参照カウントは1960年、George E. Collins が発表... コピーGCは1963年、Marvin L. Minsky が発表... と、この分野の基礎技術は半世紀前にほぼ確立しているようである。いずれにせよ、完璧なガベージコレクションの方法はない。マシン、言語、アプリケーションなどの設計思想に応じて、アルゴリズムの組合せや用い方も変わる。
全般的な印象として気になるのが、GCの起動タイミングが先送りなところである。具体的には、メモリアロケーションに失敗した時。おいらは、ゴミが発生したら即掃除しないと気が済まないタチだ。もちろん、先駆けてメモリ状態を健全に保とうとするアルゴリズムもあるが...
また、同じソフトウェア業界でありながら、用語のニュアンスもだいぶ違うようである。
例えば...
「オブジェクト」とは、オブジェクト指向で言うところの属性や振る舞いを持ったサービス群という意味合いでなく、データの塊を意味するという。ガベージコレクションは、この塊を基本単位とし、メモリ上での移動や破棄といった操作を行う。
「ミューテータ(mutator)」という用語も紹介してくれる。Dijkstra によって考案された用語だそうで、「変化させるもの」という意味。オブジェクト指向的なオブジェクトへのアクセスメソッドは、基本的に set/get 系で済むと思っているが、ガベージコレクションでは参照関係を重視するため、ゴミ収集ではミューテータのタイミングが鍵となりそうだ。つまり、参照関係は時間とともに変化するが、その監視の手がかりになるというわけである。
「チャンク(chunk)」という用語も聞き慣れない。「かたまり」という意味で、将来的にオブジェクトを利用するための空き領域のこと。ガベージコレクションは、死んだオブジェクトを回収して、チャンクとして次に備える。
... こうした用語がデータ構造にだけ着目している点に、いかにもゴミ収集の世界という印象を与える。要するに、問題は死んだオブジェクトをいかに判別するかということ。過去の実績や栄光などに構っちゃいない。そして、ガベージコレクションの役割は、死んだオブジェクトを本当の意味で葬り去ることにある。

2. マークスイープGC(Mark Sweep GC)
保守的GCの代表的な存在のようで、その名のとおり、マークフェーズとスイープフェーズからなる。マークフェーズは、生きているオブジェクトにマークをつけるステップ。スイープフェーズは、マークのついていないオブジェクトを回収するステップ。その機構は極めて単純で、ルートから階層的に参照関係を再帰的に辿ってマークすれば、すべてのオブジェクトがマークできるという発想。
オブジェクト探索には、その階層から「深さ優先探索」と、その広がりから「幅優先探索」とが考えられる。GCはすべてを探索する必要があるので、どちらを優先しても探索するステップ数はあまり変わらない。だが、メモリ消費量を比較すると、深さ優先探索の方が少なく抑えられる傾向にあるという。アロケーションのタイミングは、ミューテータからチャンクが要求されると、その適切なサイズのチャンクを返す。
チャンクには、「First-fit, Best-fit, Worst-fit」の三つの戦略があるという。First-fit は要求されたサイズを返す。Best-fit は要求サイズ以上で最小のチャンクを返す。Worst-fit は最大のチャンクを見つけ、要求されたサイズとその残りに分割する。戦略によっては、細かなチャンクが多くなってしまう問題がある。そこで、連続したチャンクをつないでおいて、フリーリストとして持っておく手もある。
また、マークスイープGCは、Copy-On-Write との相性が悪いという。Copy-On-Write とは、unix系の仮想記憶で使用されている高速化手法で、プロセスのコピー(fork)を行う時など、大半のメモリ領域でコピーしたふりをして、実際にはメモリを共有するといった仕掛けである。だが、書き込みが発生した場合、他のプロセスとの不整合が生じるため、共有メモリを勝手に書き換えるわけにはいかない。書き込む場合は私有領域にコピーしておき、その領域上でデータ操作を行えばいいのだけど。マークスイープGCは、生きている可能性のあるオブジェクトすべてにマークビットを立ててしまうため、本来発生しないコピーが頻発してメモリを圧迫するという。確かに、マークビットを立てるだけで、オブジェクトに書き換えが生じたと勘違いされては困る。この問題に対処する方法が、「ビットマップマーキング」だという。ガベージコレクション用のヘッダをビットマップテーブルとして別管理するわけか...

3. 参照カウント
すべてのオブジェクトに参照の数を記憶させるという考え方で、各オブジェクトは自分の人気度を知っていて、人気がなければ自然消滅させる。マークスイープGCでは、チャンクがなくなった時にミューテータがGCに空き領域を要求するが、参照カウントでは、ミューテータが明示的にGCを起動することはなく、ミューテータの処理とともにカウンタの増減を行う。カウンタの増減のタイミングは、ミューテータが新たなオブジェクトを生成する時やポインタの参照状態を更新した時で、カウンタ値がゼロになると破棄される。参照カウントは、メモリ管理をミューテータと並行して行うという特徴がある。しかしながら、カウンタ値のビット幅が大きくなり、処理が重たそう。
また、循環参照が回収できないという大きな欠点を抱えているという。カウンタのビット幅を減らす方法では、「Sticky参照カウント法」を紹介してくれる。その極端な例では、1bitしか割り当てない「1ビット参照カウント」という方法もあるという。すぐにオーバーフローするわけで、簡易的な判別ぐらいにしか使えないような...
カウンタの増減処理を軽減する方法では、「遅延参照カウント法」という改良版が紹介される。
さらに、循環参照が回収できるように、マークスイープGCと組み合わせた「部分マークスイープ法」を紹介してくれる。循環参照が回収できないのは、参照カウントの特有の問題とすれば、通常は参照カウントをやっておき、必要な時にマークスイープGCを呼び出すという戦略である。しかし、効率が悪いようだ。一般的に、循環参照をもつゴミは滅多に生じないのだとか。循環参照を持つかもしれないオブジェクト群に対してのみ、マークスイープGCを適用するとなると、循環参照であるかもしれないという推定が必要になる。再帰的にアロケーションを試すといった機構が必要か。これはこれで、オーバーヘッドが大きそうである。滅多に生じないのであれば、最初のキューが空かどうかだけでも、かなりの判別ができそうな気もする。

4. コピーGC(Copying GC)
生きているオブジェクトだけを集めて別の領域にコピーし、連続した領域を確保するという考え方。むかーし、メインフレームでコンデンスによる最適化といった処理を明示的にやっていたような... おっと、年齡がバレそう!ユーザが明示的にデフラグをやる某OSの思想もどうか?と思うが...
それはさおき、コピーGCはフラグメンテーションの抑止に非常に良く、メモリ状態を常に健全に保てるという特徴がある。全領域をコピーするので、保守的GCと相反する。参照関係にあるオブジェクト同士が隣り合わせにあるので、キャッシュメモリの恩恵を受けやすい。しかし、ヒープ領域を常に二等分して、片方をバックアップ用に開けておく必要があるため、メモリの使用効率が悪い。
また、再帰的関数の呼び出しでは、子オブジェクトが再帰的にコピーを行うため、オーバーヘッドが大きいという。再帰的コピーの対処では、固有の反復コピー関数で置き換える「CheneyのコピーGC」を紹介してくれる。キャッシュとの相性を犠牲にするが...
あるいは、全体を二等分するのではなく、細かく空間を分けて、マークスイープGCなどの他のアルゴリズムに割り当てる「複数空間コピー法」も紹介してくれる。フラグメンテーションの問題が再浮上するけど...

5. 世代別GC(Generational GC)
三つのアルゴリズムとは、ちと違う視点だが、考え方としては興味深い。注意したいのは、このアルゴリズムは単独なものではなく、他のGCと組み合わせることである。
ほとんどのオブジェクトは生成されてすぐゴミになり、長く生き残るのは稀、という研究報告があるそうな。そこで、オブジェクトに年齡の概念を導入する。GCを一回経て、生き残ったオブジェクトは、1歳となる。そして、オブジェクトを世代別に分類し、一定の年齡を超えると旧世代オブジェクトとし、新世代オブジェクトを重点的にGCの対象とすることで時間を短縮する。
とはいえ、旧世代から新世代への参照を考慮する必要がある。その対処では、記憶集合(Remembered set)を使って、新世代への参照を効率よく見つけることができるという。そして、「ライトバリア」という旧世代から新世代への参照を記録するための機構を紹介してくれる。ヒープ領域が圧迫された時の非常手段として、旧世代オブジェクトから排除するというのはありかもしれん。楢山節考やなぁ...

6. Python
Python のメモリ確保は、単純に malloc/free を使うだけでなく、その上に3階層の独自レイヤを重ねて、効率的なアロケーションを行う戦略をとっているという。

  レイヤ3: PyList_New(), PyTuplet_New(), PyDict_New(),...
  レイヤ2: PyObject_GC_New(), PyObject_Malloc(), ...
  レイヤ1: new_arena()
  レイヤ0: malloc()

しかも、オブジェクトの生成時に、割り当てるメモリのサイズによって、アロケーション方法を変えている。要求サイズが 256byte を超えると素直に malloc を呼び、それ以下だとレイヤ順に登っていく。オブジェクトのほとんどが、256byte 以下で、しかも、すぐに捨てられる傾向にある。例えば、forループ文では一時的な文字列や数値列を大量に使い捨てるので、malloc/free 構造を使うのはあまりにも酷。
その構造は、細かい方からブロック、プール、アリーナの3階層になっているという。アリーナオブジェクトはプールで分割され、プールサイズは 4Kbyte 固定。このサイズは、大抵のOSの仮想メモリのページサイズ 4K と合う。OSがプール単位でメモリ管理してくれることを期待してのことか。それで、OSとの相性が良くなるかは知らんが...
また、アルゴリズムは参照カウントをベースとし、「参照の所有権」という構造を紹介してくれる。所有権はオブジェクトに対するものではなく、参照に対してのもの。尚、オブジェクト自体には所有権はない。参照の所有権は、関数の戻り値と引数に大きな意味を持つという。関数側は、呼び出し側に戻り値と一緒に参照の所有権を渡す。参照の所有権を持つものが、同時に破棄する権利を持つという考え方か。他から参照ができるのは、参照の所有権を借りている状態とするわけだが、借り手が勝手に破棄するわけにはいかない。ただ、カウンタをデクリメントする権利はある。貸出時にインクリメントして、返却時にデクリメントするという仕掛けか。まるで図書館の仕組み。しかし、すべてのデータのやりとりにおいて、参照の所有権がつきまとうとなれば、言語処理系に仕様変更や機能追加をする度に、GCの構造に振り回されそう。
また、参照カウントの欠点である循環参照の問題は、マークスイープGCの改良版との組合せで対処しているという。循環参照は、すべてのオブジェクトで起こるのではなく、コンテナオブジェクトによって引き起こされるという。コンテナオブジェクトとは、他のオブジェクトへの参照を保持することが可能なオブジェクトのこと。尚、Pythonのオブジェクト構造には、リスト型、タプル型、辞書型といったコンテナオブジェクトが用意されている。
なんと!コンテナオブジェクトは三世代あって、世代別コンテナオブジェクト構造だという。言語設計者は、こんなデータ構造までも考慮しながら設計しなければならんのかぁ... 足を向けて寝られん!

7. DalvikVM
DalvikVM は、Androidプラットフォームに搭載される仮想マシン。Android のアーキテクチャは、Linuxカーネルやそのライブラリ(libc, SQlite, ...)で構成されるが、その上位階層に位置づけられる。尚、Dalvik(谷間の入江) という名は、開発者Dan Bornstein の祖先が住んだアイスランドのフィヨルドにある漁村に因んでいるそうな。
Androidを起動すると、最初に Zygote というプロセスが立ち上がるという。Zygote はすべての親プロセスとなる。アプリケーションを立ち上げる際は、Zygote から fork してプロセスを作る。Zygote は多くのライブラリを抱えるために起動は遅いが、その後の子プロセスは起動が高速に行える。また、子プロセスは親プロセスの共有メモリ領域を使用するため、メモリ消費量も軽減できるという。
ちなみに、Android には、bionic という独自のCライブラリが搭載されているという。bionic は、glibc malloc から派生した独自の dlmalloc を持っているとか。glibc が大きすぎるということか。BSD libc を改良したものらしい...
共有メモリ用のデバイスには、ashmem(Anonymous Shared Memory Subsystem) というものが組み込まれているという。こいつが、mmap の機構を持っているらしい。mmap とは unix系のシステムコールで、ファイルのランダムアクセスなどを可能にするライブラリ。通常のアロケーションには、brk というシステムコールを使うという。これは、Cのヒープ領域を拡張するシステムコールだとか。だが、Cのヒープ領域はプロセスによってサイズの上限が決まっていて、mmap は、brk より制限が少なく、大きなメモリサイズを取得できる。ただし、mmap はページサイズ 4KByte 単位でしか割り当てない。
dlmalloc のアロケーションは、小さなサイズには brk を、大きなサイズには mmap を使うという。mmap 機構からして、Copy-On-Write との相性が良さそうだが、DalvikVMでは、これを苦手とするマークスイープGCを採用しているという。もっとも、この問題に対処したビットマップマーキングのようだが...
ところで、仮想マシンの世界は、大まかにレジスタマシンとスタックマシンの二つに分類される。スタックマシンは、レジスタを使わずにスタックを使って計算し、結果をスタックに積み上げる。一方、レジスタマシンは、数値を固有のレジスタにロードして、計算結果をレジスタに格納する。CPUの設計経験を持つおいらには、後者の方がイメージしやすい。それも古代人の感覚かもしれん。実際、固有レジスタで機能を差別化するよりも、スタックだけで抽象化した方がすっきりしている。スタックマシンのメリットは、オブジェクトコードのコンパクト化、コンパイルの単純さなどが挙げられるが、なによりもプロセッサの状態数が少なくて済む。ただ、メモリ参照をスタックで管理すればアクセスがそこに集中するわけだし、GCにとっては辛そうな気もするけど...
多くの JVM(Java Virtual Machine )でスタックマシンが採用される。しかし、DalvikVM はレジスタマシンを採用しているという。それも、Android 特有の事情があるようだ。Android端末のプロセッサが、レジスタマシンアーキテクチャだからであろう。ハードウェア思想をそのまま受け継いで、最大限の高速化を狙っているのだろう。これを仮想マシンと言うのか?は知らん。実際、ARMに特化したアセンブラコードもたくさん置かれているらしい。Androidマシンには、ARMが採用され、Android-x86 も進行中という事情もある。

8. Rubinius
Rubyの処理系で有名なのは、C言語で記述される CRuby の方だが、本書はあえて Rubinius を扱っている。Rubiniusは、Evan Phoenix を中心に進められ、その象徴的なポリシーに「Ruby で Ruby を実装」というのがあるそうな。思想では、Rubinius の方がエレガントに映るが、実用性では、CRuby の方であろうか。Rubinius が興味深いのは、本書で扱われる数少ない「正確なGC」の事例だということ。尚、CRuby の方は「保守的GC」だという。
Rubinius は世代別GCを採用し、マイナーGCとメジャーGCの二段階で構成されるという。マイナーGCでは、コピーGC(CheneyのコピーGC)を、メジャーGCでは、マークスイープGCとマークコンパクトGC(ImmixGC)を。メモリ空間も、それぞれ三つの領域に割り当てられる。シーケンスは、閾値を超える大きなサイズの場合はマークスイープGCアロケータを呼び出し、閾値を越えない場合は、コピーGC空間用に割り当て可能な場合はコピーGCアロケータを呼び出し、それ以外はマークコンパクトGC用アロケータを呼び出すといった具合。コピーGCでは、ライトバリアが実装されているようだ。
やはり、Rubiniusも、CRuby用に書かれたC拡張ライブラリをサポートしているようだ。では、Cのコールスタックやレジスタをどうやって走査するのか?保守的GCであれば、オブジェクトへのポインタがC拡張ライブラリのコールスタックやレジスタに漏れたとしても、とりあえず生きているオブジェクトとみなす。しかし、正確なGCではそうはいかない。その対処として、C拡張ライブラリに渡すすべてのオブジェクトへのポインタをハンドラに格納し、ルートで扱うという。そして、参照カウントに似た形でハンドラの生死を管理するとか。こりゃ、いくらなんでも Ruby じゃ書けんやろ。どうやら、C++ で書いてギャップを埋めているようだ。あれ、ポリシーに反しないのか?
保守的GCのメリットは、ミューテータでGCを意識する必要がない。デメリットは、使用できるGCアルゴリズムが制限される。対して、正確なGCのメリットは、GCアルゴリズムが制限されない。デメリットは、ミューテータを意識する必要がある。保守的なGCを採用している CRuby は、驚くほど簡単にC拡張ライブラリを記述することができるという。対して、正確なGCを採用している Rubinius は、アルゴリズムの制限がないために、比較的簡単にGCを改良することができるという。GCの作りやすさを優先しているという見方もできそうか...

9. V8
Google Chrome の特徴は、Google社が独自に開発した高速な JavaScript エンジンを搭載していること。そう、V8 JavaScript Enjine ってやつだ。名前の由来は、V型8気筒エンジンからきているらしい。高速なパワフルエンジンの代名詞だとか。コードは、80%以上が C++でグルグルしそうだけど...
V8 は正確なGCが採用され、世代別GCが使用されるという。構成は、Rubinius のGCに似ていて、これも正確なGCの事例。マイナーGCでは、コピーGC(CheneyのコピーGC)を、メジャーGCでは、マークスイープGCとマークコンパクトGCを採用している。ハンドラでリストを持つという考え方も、Rubinius と同じか。もっとも、こちらは最初から C++ で書こうとしているので、なんでもありだけど...
そもそも、GCをどう位置づけるか?システムプログラムなのだから、わざわざスクリプト言語で書く必要があるのか?あるいは、言語システムはアプリケーションプログラムなのか?OSの境界も曖昧になっている。ユーザの立場では、ポインタから解放してくれることはありがたい。だからといって、ポインタの概念を知らなくて、本当にいいのか?将来はガベージコレクションも独り一人歩きを始めるのかもしれん...
ところで、むかーしから、ファイナライザってやつの意義がよく分かっていない。ソフト屋さんに、いろいろ説明してもらうのだけど、いまいちしっくりこない。ファイナライズとは、オブジェクトの解放処理にフックをかけて、何らかの処理をする機能である。何らかの処理というのが微妙で、メッセージを発行するぐらいしか思いつかない。デバッグの手がかりにはなりそうだが、パフォーマンスを落とすだけのような気もする。GCを装備していない言語システムでは、直接デストラクタをやればいいだろう。だが、自動化システムではファイナライザにオブジェクトの解放まで期待していいのか?
案の定、V8 にはファイナライザがないという。ファイナライザに関する問題は、GCの実装において厄介なものらしい。もしかして、いらねぇってかぁ?変に操作をやると怖いから、触らぬ神に祟りなし!

2014-07-20

"Emacs Lisp テクニックバイブル" るびきち 著

本書は、Lisp を手軽に学ぶために手にしたのだが、仕事仲間に話題を振ると、エディタ談義で盛り上がってしまった。プログラミング言語とエディタには相関関係があるという説もあるが、無理に法則性を見出すこともあるまい。開発環境は開発者の思考の場であり、テキストエディタは思考プロセスを書きとめる上で最も単純で根幹的な道具となる。それだけに使い手の思い入れは強く、プログラミング言語同様、宗教的ですらある。むかーし、出張先で困らないように、最低でも vi ぐらいは使えないといけないよ!と指摘されたことがある。もうそんな時代でもあるまいが、どんな環境でも対応できるような身体にはしておきたい。
本格的にエディタの選択に迫られたのは、20年前になろうか。Emacs に近寄り難いと感じたのは、当時のデフォルトのキーバインドが酷かったこと。vi の方がましだと思ったぐらい。現在でも、Emacs のキーバインドにうろたえる人は少なくあるまい。ネット社会ともなれば、カスタマイズした設定ファイルを公開してくれる方々がいて、非常に助かる。shell環境もそうだが、この手の設定環境は伝承される傾向があり、情報不足に陥ることはなさそうだ。
とはいえ、デフォルトで使いづらいというだけで、ヤル気が失せる。編集作業において、キーワードの補完や色分けといった機能は必須だ。コーディング中に、変数名の綴りを間違うだけで大きなストレスとなる。ちなみに、Emacs では、テキストの色分け機能がデフォルトで無効になっているという。(require 'generic-x)ってやれば済む話だが。著者は、これだけで Emacs ユーザの損失だと嘆いている。そうだろう!そうだろう!てなわけで、おいらは秀丸エディタ派となった。なんにせよ、テキストエディタってやつは、料理人でいうところの包丁一本... の存在だ!

しかしながら、プラットフォームに依存しない作業環境という観点から、Emacs も捨てがたい。たまには、Emacs + Mew を使うし、TRAMP というリモートアクセス用のパッケージにも興味がある。Windows版や Mac版もあるにはあるが、一昔前はバージョンや OS の違いで互換性が保たれないという印象があった。現在ではそうでもないらしい。
Emacs のマクロ機能は、秀丸エディタのそれとは比べ物にならないのも確か。一つのエディタの中に作業環境を押し込むのもどうか?という疑問もあるが、Emacs はエディタの概念をも超越している。実際、エディタの外に、gcc, Ruby, HTML & JavaScript などの環境を並行して構築しているが、プラットフォームを Emacs で吸収するという考え方もあるだろう。それを実現させるものが、バッファの概念だ。初めて触れた時、そのエレガントな思想に感動したものである。ファイルから独立したバッファの抽象度は高く、作業領域やアプリケーション領域に割り当てることができる。
ざっと眺めるだけでも... コマンドや関数の補完では、Completions バッファが自動で開いて候補が表示される。Help を開けば、そこに表示用バッファが生成される。ファイルを探す時(find-file)、カーソルでディレクトリ階層を辿ることができる。shell との相性がよく、端末として使える。本書は、eshellってやつを紹介してくれるが、病みつきになるらしい。なによりも驚くべきは、一時的な作業領域の scratch バッファが、lisp式を評価する機構を具えていることだ。あるいは、Lisp用対話型インタプリタも用意されている。本書では、これらよりもっといいやり方を教えてくれるけど...
それにしても、秀丸エディタのタブモードは捨てられん!と思いきや、Emacs にもあった。tabbar.elってやつが...

さて、Emacs Lisp の方はというと、ちと印象が違う。多少の方言は覚悟しても、Common Lisp の簡易版ぐらいに思っていたのだが、本書は決定的な違いがあることを教えてくれる。その違いとは、グローバル変数やクロージャの思想、そして、Common Lisp がレキシカルスコープであるのに対し、Emacs Lisp はダイナミックスコープだということ。
例えば... 関数もどきの let ってやつは、Common Lisp ではレキシカルスコープだが、Emacs Lisp ではダイナミックスコープになるんだとか... おいおい!!!
Common Lisp の機能を提供するパッケージ(cl.el)ってやつもあるが、禁止事項があって制限が設けられているという。著者は、そんな無駄なことを... と愚痴を語ってくれる。ソフトウェアを使う上で、達人の愚痴ほど参考になるものはあるまい。Emacs Lisp の進化過程では、Common Lisp の機能から派生したものが多い。昔は、when すらなかったとか。徐々に Common Lisp に近づいていくとすれば、制限することになんの意味があるのか、と疑問を持つのも当然であろう。実際、cl.el は標準装備され、(require 'cl)ってやるだけで使える。Lispユーザは当たり前のように使っているそうな。いくら制限を設けても、民主主義によって淘汰されていくだろう。
また、Emacs lisp はシングルスレッドだが、emacs 自体はマルチスレッドで、擬似マルチスレッドプログラミングのための deferred.el というライブラリも紹介してくれる。

1. Emacs Lisp のためのパッケージ... auto-install.el
auto-install.el は、URLを指定するだけでネット上の Emacs Lisp プログラムをインストールできるようになるという。尚、EmacsWiki(http://www.emacswiki.org/)には、様々なパッケージが集められている。

$ mkdir -p ~/.emacs.d/auto-install
$ cd ~/.emacs.d/auto-install/
$ wget http://www.emacswiki.org/emacs/download/auto-install.el
$ emacs --batch -Q -f batch-byte-compile auto-install.el

.emacs.el
(add-to-list 'load-path "~/.emacs.d/auto-install/")
(require 'auto-install)
(auto-install-update-emacswiki-package-name t)
(auto-install-compatibility-setup)
(setq ediff-window-setup-function 'ediff-setup-windows-plain)

他にも、Lisp 使いに便利そうな5つのパッケージを紹介してくれる。
  open-junk-file.el          (試行錯誤用ファイルを開く)
  lispxmp.el                 (式の評価結果を注釈する)
  paredit.el                 (括弧の対応を保持して編集する)
  auto-async-byte-compile.el (保存時に自動バイトコンパイル)
  package.el                 (ELPA/Marmaladeインストーラ emacs24で標準)

ダウンロードは...
M-x install-elisp-from-emacswiki open-junk-file.el
M-x install-elisp-from-emacswiki lispxmp.el
M-x install-elisp http://mumble.net/~campbell/emacs/paredit.el
M-x install-elisp-from-emacswiki auto-async-byte-compile.el

ついでに、tabbar.el も...
M-x install-elisp-from-emacswiki tabbar.el
それぞれダウンロード後にファイルがポップアップするので、C-c C-c とすればインストール完了。

2. Lisp式の評価方法
対話的に評価できる方法が二つあるという。一つは、scratch バッファを使う方法。二つは、ielm(Interactive Emacs Lisp Mode)を使う方法。
scratch バッファでは、eval-print-last-sexp コマンドで直下に評価結果が出力される。eval-last-sexp でも評価できるが、出力場所がコマンドライン上で少し遠い。尚、eval-print-last-sexp には C-j が、eval-last-sexp には C-x C-e がキーバインドされている。
ielm は対話型インタプリタで、Rubyで言うところの irb(Interactive Ruby)か。M-x ielm とやれば起動する。
この二つだけでも感動しているというのに、本書はもっといいやり方を教えてくれる。上記の方法は、Emacs を終了すると結果が消える。そこで、open-junk-file.el パッケージを用いれば、ジャンクファイル上で評価して自動保存できる。ジャンクファイルとは、日時を元にしたファイル名をもつファイルのことで、M-x open-junk-file ってやれば起動する。惚れっぽい酔っ払いは、ジャンクにイチコロよ!

3. Common Lispパッケージ... cl.el
関数の名前空間は、Common Lisp と Emacs Lisp に違いがあって、衝突の可能性がある。なので、cl.el の禁止事項は、eval-when-compile でバイトコンパイル時にロードしてマクロを使う分には許可するが、Common Lisp の関数は使うな!ということらしい。つまり、(require 'cl) が禁止ということか?
本書は、(eval-when-compile (require 'cl)) ってやれば、Common Lisp のマクロを合法的に使えるとしている。ランタイムに cl.el のロードが禁止となれば関数は使えないが、コンパイル時に展開されるマクロならOKってか?ん~... 解釈の問題のような気もするが...
今となっては、Common Lisp に総入れ替えするわけにもいかないだろう。古い資産が誤動作しそうだし。Common Lisp と Emacs Lisp で、レキシカルスコープとダイナミックスコープの違いがあるのも、関数の変数をめぐって大きな問題となりそうだ。ならば、(require 'cl)を許可して、Common Lisp でオーバライドさせることを明示すれば良さそうな気もするが...
それはともかく、本書で紹介されるマクロは、なかなか便利そうである。リスト構造を分解して変数に代入する時、car, nth が冗長的なので、destructure-bind を使うとすっきりする。汎変数を使うと、代入の概念を拡張できる。setq は、その拡張版の setf が使える。汎変数には、car, nth といったリスト要素だけでなく、buffer-substring, point といったバッファ関連もあるようだ。
let/let* のレキシカルスコープ版は、lexical-let/lexical-let* があるという。ん~、これは微妙だなぁ!他には構造体が使えたり...
本書は、loop マクロをかなり丁寧に解説してくれる。こいつは、Common Lisp が提供するモンスターマクロだという。リストやベクタの要素の合計/最大値/最小値を与えたり、各要素に関数を適用したり、条件を満たす要素を抽出して演算を施したり... などの演算節が豊富で、統計情報を処理するのに強力なツールとなる。連想リストやハッシュテーブルのキーを求めたり、フィボナッチ数列を求めたりするのも、エレガントに書けるという。
また、非局所脱出メカニズムには二つあるという。Emacs Lisp 本来の catch/throw と Common Lisp の block/return-from。Common Lisp には block の概念があり、明示しなくても暗黙に block が形成される。この block がレキシカルスコープを実現している。block からは、return-from で脱出できる。一方、catch はダイナミックスコープの場合で、脱出時には、throw を呼び出す。cl.el のおかげで、Emacs Lisp でも block/return-from の仕掛けが使えるというわけか。

4. eshell のすゝめ
eshell は、Emacs Lisp で書かれているために、プラットフォームに依存しないという。zsh ライクで、使い勝手もよさそう。普通のシェルはC言語などで書かれているため、シェルスクリプトの範囲でしか拡張できないが、eshell はコマンド解釈の部分ですら乗っ取ることが可能で、コマンドラインを丸ごと zsh や Ruby に渡して実行することができるという。おぉ~...

2014-07-13

"実践 Common Lisp" Peter Seibel 著

本書を購入したのは、三年ぐらい前になろうか。時々横目で追い... 辞書代りにし... これを読破するには気が重い。ところが、改めて目を通してみると、意外とストーリー性があって、おもろいんでないかい!
それは、音楽ファイル(MP3)からタグ情報(ID3)を抽出し、曲情報をweb上で管理するという物語で、最終的に、曲の検索、プレイリストの追加、ストリーミングといった機能を備えるMP3ブラウザを作成することにある。
ここに含まれる技術要素は... 単語の頻度を調べるために、スパムフィルタでよく見かけるベイジアンフィルタを用いて学習する仕掛け。バイナリファイルのためのパーサの作成。リスト型言語らしいデータベースの構築。WebアプリケーションのためのWebサーバ(AllegroServe)の導入。HTMLライブラリの生成。ストリーミング再生のための、Shoutcastプロトコルの実装など...
実践と言うには、ちと話題がづれていそうだが、試してみると、なかなか役に立ちそうではないかい。もちろん、Common Lisp の処理系や、CLOS(Common Lisp Object System)といった話題も豊富!満腹すぎて吐きそうなほどに...

Lispは、FORTRANの時代を思い出させる言語で、その歴史は1950年代に遡る。だが、改良を重ね重ね、いまだ輝きを失っていない。オブジェクト指向の機能をもたらす CLOS は、もはや Common Lisp と分けて論じることができないほど馴染んでやがる。
今日のコンピューティングは、メモリ容量やCPU性能、あるいは、表示システムの高精細化や入力システムの操作性向上など、リソースは格段と進化している。プログラミングにおいても、ハードウェアをほとんど意識しなくて済み、本来の目的に傾注できる高水準言語が続々と登場する。おそらく万能な言語は存在しないだろうし、ドメイン固有言語という発想はますます広がるだろう。
そんな時代にあってもなお、Lisp が生き残ってこられたのは、言語自体に柔軟性があるのも確かであろうが、チューリング等価の記法という意味では、ソフトウェアはあまり進化していないのかもしれない。いずれにせよ、チューリングマシンが考案されて一世紀にも満たず、コンピューティングの歴史はいまだ過渡期にある。実際、新しい技術が品質やユーザビリティを落とすケースも珍しくないし、登場時期が早すぎたために廃れていくアイデアも少なくない。この手の書に触れる時は、新しいとか、古いとか、そうした意識は捨ててかかった方がよさそうである。引退間際の古代人には、なんでも真新しく映るけど...

Lisp信者は、こんなことを言う。Lispを学べば、もっとましなプログラマになれると。言語に対する思いは宗教的なところがあり、その座右の銘は禅問答に似たものがある。Lispの場合はこれだ。
「プログラム可能なプログラミング言語」
彼らは、マクロ機能の強力さをこわだかに話す。まるで万能言語であるかのように。だが、手続き型言語に慣れ親しんできた者にとっては、まるで宇宙人の文化だ。S式とかいうヘンテコな宣教師が、カッコカッコ... コッカコッカ... と呪文を唱えれば、カッコの奥から let とかいう控えめな教職者が lambda とかいう名もない浮浪者に見返り(返り値)をねだってやがる。実に、鬱陶しい奴らだ!
しかしながら、異質の言語に触れることにも意義がある。当たり前と思い込んでいる事でも、疑問を持つ機会を与えてくれる。最近、気に入っている感覚は、リスト型データ構造である。Lispが記号処理のために設計され、list processing を得意とすることは、その名が示している。
「リストは不均質で階層的なあらゆるデータを表すための格好のデータ構造だ。」
仕事では数学のアルゴリズムを検討することが多く、関数で多次元空間を記述する場合、返り値には多値を用いたい。例えば、C言語などの return変数は基本的に一つで、多値を返したければポインタ参照の形をとる。これが副作用の原因となりやすい。わざと副作用を利用することもあるので、一概に悪いとは言えないのだが。一方、リスト型データはもともと多値が想定されているので、そんな気遣いはいらない。尚、ここで言う「多値」とは、群論で言うところの集合体を意味し、論理学のそれとは意味が違うので注意されたし...
「関数プログラミングの真髄は、与えられた引数のみに依存して演算を行う副作用を持たない関数のみでプログラムを構成されることにある。」
本書は、リスト構造が柔軟であるがために、その弊害で、ユーザがリストに特化しすぎる傾向があると指摘している。そして、もっと効率的な方法として、コレクションの概念を用いたベクタやハッシュテーブルの事例を紹介してくれる。また、リスト型が複素数に対応してくれるのもありがたい。尚、今日では多くの言語で複素数型がサポートされている。C99ライブラリのように...

1. コレクションの概念
「リストを理解する手がかりは、そのほとんどがより基本的なデータ型のインスタンスであるオブジェクトの上に構築された幻想だと理解することにある。その単純なオブジェクトはコンスセルと呼ばれる値のペアであり、関数 CONS を呼び出すことによって作り出される。」
リスト型データ構造を効率的に用いる方法として、コレクションが紹介されるが、明確な違いがよく分からん!コレクションを操作する方法として、シーケンスというサブタイプがあるが、その多くはリストでも使えそうだし。ただ、シーケンスは非常に強力なために、リスト操作とは抽象度の違いを感じるのも確かで、コレクションという用語を新たに生み出すだけのことはありそうか。

例えば、ベクタでは...
固定サイズに vector関数、固定サイズと可変サイズの両方に make-array関数が用意される。要素の追加と削除には、vector-push, vector-pop があり、シーケンスのレベルでベクタとリストが区別されるかに見える。反復関数には、count, find, position, remove, substitute などがあり、これらの関数の末尾に、-if を付けて条件式として使える。count-if, find-if... といった具合に。
シーケンス全体の操作では、copy-seq, reverse、あるいは、連結に、concatenate がある。ソートには、sort, stable-sort。尚、stable- 述語で順番が入れ替わらないことを保証する。部分シーケンス操作には、subseq。尚、範囲は開始と終了インデックスで指定。他には、marge, search, mismatch など。
また、シーケンス述語に、every, some, notany, notevery がある。
 every    : すべての述語が満たされれば t、それ以外 nil。
 some     : 1つでも満たすものがあれば t、すべて満たさないとき nil。
 notany   : 1つでも満たされれば nil、1つも満たさない場合 t。
 notevery : 1つでも満たされれば t、1つも満たされない場合 nil。

複数のシーケンスに対して関数を施したい時は、map, map-into といったマッピング関数が使える。
また、一つのシーケンスに対しては、reduce が便利。
合計を求めるには...

  (reduce #'+ #(1 2 3 4 5 6 7 8 9 10))  => 55

最大値を見つけるには...

  (setf numbers '(10 12 14 16))
  (reduce #'max numbers)  => 16

キーワード引数には、:key, :from-end, :start, :end がある。
固有の引数には :initial-value があり、シーケンスの初期値が設定できる。

ハッシュテーブルでは...
生成に、make-hash-table。要素にアクセスするには、gethash。gethashに複数の返り値がある場合は、 multiple-value-bind マクロが用意される。
反復処理は、maphash でこんな感じ...

  (maphash #'(lambda (k v) (format t "~a => ~a~%" k v)) *hash*)

2. 例外処理とコンディションシステム
Lispの偉大な機能の一つにコンディションシステムがあるという。Java や Python や C++ における例外処理と似た目的で提供されるが、もっと柔軟でエラー処理にとどまらないという。プログラムの実行中に起こる出来事を記述できるので、例外よりも汎用性が高いということらしい。例外処理においては、エラーの捕捉とその通知が鍵となるが、Lispでは更に再起動という機能が付加される。
ところで、エラー処理とは、なんであろうか?プログラムは関数の階層によって組み立てられる。低位の関数の上に高位の関数が構築されれば、実行中の実体はコールスタックという形で現れる。低位のプロセスは、高位のプロセスのコールスタック上にあるということだ。
したがって、エラーを捕捉する格好の場所は、関数の境界ということになろう。実際、低位と高位の依存関係において問題が発生しやすい。例えば、呼び先のファイルが存在しないとか、メモリの空き容量が足りないとか、ネットワークが落ちているといった原因で。関数単体から見て、想定外の条件への対処とも言えよう。一方で、関数内で起こるエラーはそれこそバグであり、ここで扱う問題ではない。
例外機構を備えていないシステムでは、エラー通知は関数の呼び出し元に送ることになろうか。そして、復帰のための処理をするか、失敗を放置するかは、呼び出し元が決定することになる。単純にスキップするだけで何事も起こらなければいいが、現実はそう甘くない。
しかし、例外機構が具わっていれば、コンディションを監視することによって、何らかの対処をシステムレベルで可能にする。復帰処理において、スタックを巻き戻して関数の再起動を試みたり、保険処理のようなものも定義できそうだ。ただ、あくまでも想定外の条件に対処するわけで、却って仇となることもあろう。
Common Lispでは、エラーを回復するコードと、どうやって回復するかを決めるコードが分離されているという。戦略的には、どうやって回復するかは高位の関数に委ね、回復のためのコードを低位の関数に記述できるという仕掛けか。しかも、コンディションは一般オブジェクトと同等な扱いで定義できるようである。再起動によって効果をもたらすには、明確にコードを呼びださなければなるまい。復帰条件も異なろうが、複数の再起動が定義できるようである。コンディションハンドラは、警告をエラーに昇格させることも、その逆もできそうだ。
通知の基本関数は、signal 。なんとなく馴染みのある名前だ。これだけでプログラムのコンディションというよりは、システムコールレベルを想定していることが分かる。コンディションを理解する鍵は、コンディションを通知しただけでは制御フローに影響しないことを理解することだという。
「エラー処理には、プログラミングの教科書であっさりとしか説明されないという残念な宿命がある。エラー処理が適切かどうかは、解説用のコードと製品レベルの品質コードの最も大きな違いだといえる。後者を書くコツは、特定のプログラミング言語の構文の詳細ではなく、ソフトウェアについて特別な厳しい考え方を身につけることにある。」
ただ、あまり柔軟すぎると例外処理と通常処理の境界が曖昧になりそうだ。最もコードのセンスが問われるところでもあろうか。いずれにせよ、最悪の場合、リセットすべきか?再起動すべきか?あるいは、他の処理をすべきか?それはシステムによっても違ってくるし、ソフトウェアだけの問題ではない。
ちなみに、某原発事故では、あろうことか!電源を供給する電力会社が、電源を失うことを想定していなかったと平然と語られた。多くのシステム屋さんにとって、戒めの言葉に聞こえたことだろう...

3. loopマクロ
「皮肉なことだが、マクロを正確に理解する最大の障壁は、おそらくマクロがあまりにうまく言語に統合されてしまっていることにある。」
Lispを使っていると、まずもって不思議な感覚に見舞われるのは、マクロと関数の違いが曖昧にさせられることである。引数も取れば、値も返すし、ちょっと風変わりな関数にしか見えない。だが、実装は全く違う。マクロは単純に展開されるだけに、ローカル変数の束縛で悩ましい。だが、変数名が重複しないように、with-gensyms が用意される。
関数は言語の構文に従うが、マクロはそんな制約を受けないと言えばそうだが。あるいは、マクロはある種の翻訳機とも言えるわけだが...
「言語を"コアに標準ライブラリを追加したもの"と定義する利点のひとつに、理解や実装が容易になることがある。しかし本当のメリットは、言語が容易に拡張できる表現力にある。なにせ、言語だと思っているものの大半はただのライブラリなのだ。」
この感覚を味わうには、loopマクロがうってつけである。ループ構文には、do, dolist, dotimes とったものがある。ただ、これらの表現力は大げさ過ぎる。Lispで書かれていながら、using などの副節でカッコが省略されるところは、実にLispらしくない。
「なぜ LOOP の作者がこの副節で括弧なしスタイルに怖気づいたのか、私に訊かないでほしい。」

loopマクロの主な機能部品は、ざっとこんな感じ...
  • ローカル変数の生成とループ変数の自動更新。
  • 値の収集(collect)、計数(count)、合計(sum)、最小化(minimaize)、最大化(maxmize)。
  • 任意のLisp式の実行。
  • 条件付き終了。
などなど...
おまけに、前処理(initially)と後処理(finally)の節を用いて、ループの前後に任意の処理が指定できる。このあたりの実装は、unix上で動く awk の思想を感じる。

4. format関数
「Common Lisp の FORMAT関数は、LOOPマクロと並んで人々を感情的にさせる機能だ。信者もいればアンチもいる。」
format関数の複雑な制御文字は、電話のノイズに似ているという。確かに、printf風でありながらまったく違うし、正規表現とも違う。短く書けることが最善とするならば、あらゆる文書は暗号文となろう。いや、呪文か!
ただ、暗号ってやつは、解き明かせば恐れるに足らん。まず、すべての指示子は、~(チルダ)で始まる。指示子によっては、前置パラメータをとる場合がある。前置パラメータは、チルダのすぐ後に書き、複数ある場合はコンマで区切る。最も汎用な指示子は、~a で、人間の読める形に出力する。これだけ押さえれば、大概のことは解読できそうである。
改行を出力するには、~%。新しい行を出力するには、~&。尚、~% は常に改行するのに対して、~&は行頭でないときのみ改行する。

  (format t "~a~%" list)
  (format t "~5$" pi)  => 3.14159  ($ は小数点表示、デフォルトは2桁)
  (format t "~d" 1000000)  => 1000000 (d は10進数表示、他に、~x, ~o, ~b がある)
  (format t "~@d" 1000000) => +1000000 (符号付き)
  (format t "~:d" 1000000) => 1,000,000 (3桁ごとに区切る)
  (format t "$~:d" 1000000) => $1,000,000 (通貨単位ドル)

条件による整形には...
~[, ~] で囲んで、条件分岐を指示する。

  (format t "~[cero~;uno~;dos~]" 1)  => uno (~; で区切ってインデックスで指定)

~{, ~} で囲んで、反復を指示する。

  (format t "~{~a, ~}" (list 1 2 3)) => 1, 2, 3,

最も驚かされるのは英文制御が凝っていることだ。使うかどうかは別にして...
~r は、英語の指示子。

  (format t "~r" 1234)  => one thousand, two hundred and thirty-four
  (format t "~@r" 1234)  => MCCXXXIV (@ はローマ数字)
  (format t "~:@r" 1234)  => MCCXXXIIII (:@ は古いローマ数字)

単数形と複数形の制御に、~p を用いると、複数形の時、sを付加する。

  (format t "~r file~:p" 1)  => one file
  (format t "~r file~:p" 10)  => ten files

さらに、@ は単数形の時 y、複数形の時 ies を付加する。

  (format t "~r famil~:@p" 1)  => one family
  (format t "~r famil~:@p" 10)  => ten families

大文字と小文字制御では、~(, ~) で囲んで、その間の制御文字列を小文字で出力する。
@ は文字列の最初の文字が大文字。: はすべての単語の頭が大文字。両方つけると、すべて大文字。

  (format t "~(~a~)" "THE QUICK BROWN FOX")  => the quick brown fox
  (format t "~@(~a~)" "THE QUICK BROWN FOX")  => The quick brown fox
  (format t "~:(~a~)" "THE QUICK BROWN FOX")  => The Quick Brown Fox
  (format t "~:@(~a~)" "THE QUICK BROWN FOX") => THE QUICK BROWN FOX

5. Lisp in a BOX
REPL(read-eval-print loop)とは、読み取り(read)、評価(evaluate)、印字(print)の終りのないサイクル、すなわち、対話式機構のこと。この環境を手っ取り早く提供してくれるものに、「Lisp in a BOX」というものがあるそうな。それは、Emacsと Common Lisp開発環境 SLIME をパッケージ化したものだという。elispにはかなり方言があるようで、やはり SLIME がよさそうである。Emacs風のIDEといったところか...

6. AllegroServe
最近のブラウザは余計な機能が多すぎる。核となる機能は、Webサーバからページをリクエストし、それをレンダリングすること、これだけでもかなり遊べる。
仕事では、ドキュメント関連を、XMLで書け!って要求されることがある。閲覧するだけなら pdf でもよかろうが、検索機能や入力フォームなどが欲しいというわけだ。そのくせ向こうからは、word や excel の文書が提供されるけど。この手の自動生成ツールは、スペックが大げさで、しかもろくなコードを吐かない。結局、機能を限定したXML生成ライブラリを書く羽目に...
そこで、コードのテスト用に、簡易的なサーバが立ち上げられるとありがたい。本書は、そんな時にうってつけのWebサーバを紹介してくれる。AllegroServe と PortableAllegroServe だ。Rubyで言うところの、WEBrick のようなものか。ちなみに、Hunchentoot ってのもよさそう。

パッケージを導入するには...
Allegro Common LIsp ならば、AllegroServe に対して、require する。

  (require :aserve)

他のLispシステムでは、PortableAllegroServe に対して、require の代りに loadする。

  (load "./portableaserve/INSTALL.lisp")

localhostサーバを定義するには...(例えば、ポート2001の時)

  (net.aserve:start :port 2001)

ファイルやディレクトリを公開するには...

  (publish-file :path "/hello.html" :file "/tmp/html/hello.html")
  (publish-directory :prefix "/" :destination "/tmp/html/")

後はブラウザで、http://localhost:2001/hello.html にアクセスすればいい。

2014-07-06

"Coders at Work" Peter Seibel 著

この手の書は、なにやら忘れかけているものを思い出させてくれるような気がする。それは、好奇心や探究心といったものだ。同時に、むか~しの愚痴も甦るけど...
人は皆、面倒臭がり屋である反面、純粋な好奇心に対しては真摯になれる面がある。そして、探究心の持続こそが才能を覚醒させるのであろう。
本書は、ピーター・サイベルが、いまや伝説となった15人のプログラマからコード哲学を聞き出すインタビュー集である。尚、サイベル自身がプログラマであり、教科書的な存在である「実践Common Lisp」の著者でもある。
その15人とは...
Netscape の実装者ジェイミー・ザウィンスキー。ソーシャルネットワークの概念を広めたブラッド・フィッツパトリック。JSON(JavaScript Object Notation) の生みの親ダグラス・クロックフォード。JavaScript の設計者ブレンダン・アイク。Java プログラマの尊敬を集めるジョシュア・ブロック。並行処理指向言語 Erlang の設計者ジョー・アームストロング。先進的言語 Haskell の設計と実装の中心人物サイモン・ペイトン・ジョーンズ。NASA と Google という対照的な開発グループを率いたピーター・ノーヴィグ。Scheme と Fortress を作り、数々の主要言語の標準化に携わった多言語話者ガイ・スティール。Smalltalk の実装者ダン・インガルス。実行時コンパイラ技術を生み、Ghostscript を作ったL・ピーター・ドイチュ。Unix の開発者ケン・トンプソン。最適化コンパイラ技術で女性初のチューリング賞受賞者となったフラン・アレン。ARPANET の実装者バーニー・コーセル。そして真打ち登場、コンピュータ科学者ドナルド・クヌースである。

ノイマン型アーキテクチャが提唱されて半世紀余り、インタネット世代を代表するフィッツパトリックを除いて、ネアンデルタール人に属す世代になろうか。共感できる点が多いということは、おいらも古代人ってか?ちとショック!しかしながら、いまだに情熱を持ち続け、趣味の境地でコードを書き続けているのには頭が下がる。
ちなみに、おいらはプログラマではない。むか~し組込システムのOSを書いていた時期もあるが、今では回路設計の経験の方が長い。これといった専門はなく、ずーっと雑用係と称してきた。最近はアルゴリズムの検証ばかりで、実装から遠ざかり気味。それでも思考のスケッチのためにプログラムを書く。いや、電子機器の開発設計に携われば、プログラミングを避けることの方が難しいだろう。回路設計においてもハードウェア記述言語を用いるし、その検証ではコンピュータ言語と協調させて効率を図る。画像処理アルゴリズムの検討では、ImageMagick やスクリプト言語と組み合わせるのも悪くないし、数学の落ちこぼれには、Octave のような数値演算言語の存在もありがたい。
おそらく万能なプログラミング言語は存在しないだろうし、ドメイン固有言語という思想はますます広がるだろう。ハードウェアの進化がムーアの法則に従い、ソフトウェアも大規模化していく中で、プログラミング言語の進化が比較的遅いのは救いである。言語システムには、多くの本質が内包されているように映るからだ。その傾向は、人間社会の変化に対する自然言語の変化にも顕れている。エドガー・ダイクストラは、こう言ったとか。
「母国語で満足に書けないようなら、プログラミングはあきらめることだ!」
プログラムとは、クヌースが言うように本質的に文芸作品なのかもしれん。尚、「The Art of Computer Programming」は数学的に濃い内容だけど、いつか挑戦してやると思いつつ、既に20年が過ぎた...

プログラミング言語がどうあるべきか、その意見が様々であることは驚くに値しない。設計の立場が違えば、設計哲学も思考法も変わる。本書でもその傾向が見られる。コードの取っ掛かり方だけを見ても...
ザウィンスキーやインガルスが、プロトタイプのようにすぐ動くようにすることの重要性を唱えるのに対して、ブロックは、実装前の段階で要求分析の重要性を強調しすぎることはないとし、クヌースに至っては、TEX プログラムをコンピュータに一言も入力せずに紙と鉛筆で書き上げた!と言っている。
デバッグの流儀では、デバッガ派、print 文派、あるいは、assertion 派に色分けされる。あるいは、C や C++ の普及の善悪や、言語システムがどこまで機能を具えるべきか、などでも意見が分かれる。
もちろん共通点も多い。誰もが読めるコードを書くことの重要性を唱え、無条件にシステムが巨大化する昨今、無謀なプログラムが増殖していることを懸念し、過剰なブラックボックス化についても議論される。確かに、Web アプリケーションに触れると、何年も放置された些細なバグが目立つ。情報が溢れればノイズが増殖し、プログラミングが庶民化すれば質の低い作品が氾濫する。高度な情報化社会では、鈍感さがより一層求められるようだ。
ソフトウェア業界は、全体的に良い方向に進んでいるのかもしれないが、回り道をしていることも否めない。ここに登場する偉人たちもまた、誰一人としてプログラミングが解決済みの問題だとは考えていない。ドイチュに至っては、今日のプログラミング言語で SIMULA-67 や Smalltalk より質的に優れたものはないと断言している。なるほど世間では、進歩や進化という言葉が迷信化しているところがある。インターネット世代のフィッツパトリックまでも、こう釘を刺す。
「新しいものが最低でないことを願っているのかもしれません。新しいプログラミング言語でやりたいことができるようになると期待するみたいに、でもユーザだって同じことです。ユーザはいつもバージョン番号の高いものを手に入れようとします。たとえそれがよりひどいものであっても。」
また、マルチコアというCPU構造の複雑化が、コードを書く方法を大きく変えていることも見逃せない。多くの人が最も厄介なバグに並行プログラミングにおけるものを挙げており、STM(Software Transactional Memory) の是非にまで議論が及ぶのは、なかなかの見モノ!

1. C と C++ の善悪論議
C++ の善悪については一般的に論じられているが、偉人たちの意見は、C の普及の段階から真っ二つに分かれる。アレンはコンピュータサイエンスの研究を大きく損なったと難じ、コーセルは最大のセキュリティ問題と批判する一方で、トンプソンはセキュリティはプログラマの問題であって言語システムの問題ではないと主張し、クヌースはポインタを「記法における最も目覚ましい進歩」と言っている。
プログラムで、大きな問題となるのは動的メモリの管理である。メモリリークや残骸の蓄積は、自身のプログラムだけでなく、他プログラムにも影響を与える。そこで、ポインタ機能は直にメモリにアクセスできるために忌み嫌われる。尤も昔は高級言語扱いされたが、今ではアセンブラのような低級扱いされる。しかし、参照で用いる分には便利な面がある。大量のデータ領域を関数の引数で渡すような場合だ。
そもそも、アプリケーション設計者が触れるべき領域なのか?という疑問もある。当たり前のことだが... バッファの境界を越えないことを明示的に確認せずにバッファを読んではいけないし、メモリブロックを不適切なタイミングで解放して他のポインタを不安定にしてはいけないし、サイズの合わないものを格納して他の値とかぶってはいけない。だが、そうした問題を見つけることが意外と難しい。
だからといって昔は、システムをアセンブラで書いて、アプリケーションを Pascal で書くというのも抵抗があった。C はシステムプログラムに大きな恩恵をもたらしたが、その利便性からアプリケーションの領域にも入り込んだ。アメリカ政府は、C の危険性を回避するために、Ada を強制しようとして、Ada 以外での契約を拒否した。だが、C の勢いは政府の思惑までも潰した。システム用言語とアプリケーション用言語を分けるべきだというのも、もっともな意見である。コーセルは、こう言っている。
「C が有用性を超えて長生きしすぎたと言いたくはありませんが、あまりに多くの良いプログラマに使われた結果として、今では十分よくないプログラマがアプリケーションを作るのに使うようになり、結論を言うと彼らは十分な能力がなく、ちゃんとやることができないのです。C は本当に優れたシステムプログラマには完璧な言語なのかもしれませんが、あいにくとあまり優れていないシステムプログラマやアプリケーションプログラマが、使うべきでないのに使っているのです。」
現在、高機能化したスクリプト言語が普及しているのは、よい傾向なのかもしれない。例えば、ガベージコレクションのような機能があるだけで、つまらないストレスから解放される。
一方で、C++ の普及はどうであろうか?多くの大学で C++ を採用したオブジェクト指向を教える講義がある。そもそも、こいつはオブジェクト指向言語なのか?C++ の実装の特異性や奇妙さを、いったいどうやって区別させるのか?クラスベースの言語は、ちと静的過ぎる感がある。大きなクラス階層があると、わざわざ分解してまで使う気はしない。だからといって、動的な言語を用いると、至る箇所でその場しのぎをやってしまうのだけど...
ザウィンスキーは、C++ テンプレートが大好きというような人には近づかないようにしていると言っている。フィッツパトリックは、C++ を少し擁護しているが、なるほど...
「個人的には、少なくとも C++ で scoped_ptr みたいなものを使っている限りでは、自分でメモリ管理することも特に煩わしいとは思いません。new も delete も書くことなく何日も C++ を書いていることができます。」
志の高いプログラマにしか手を出してはいけない領域というものがあるのだろう。思想に優れた者しが踏み込んではいけないシャングリ・ラのような聖地が...

2. デバッグの流儀
最近のスクリプト言語は、動的メモリまで言語システムが管理してくれるので、print 文で大方の現象は掴めるだろう。だが、システムに近い領域ほど、実際に何が起こっているかを知る必要がある。言語システムが十分優れたデバッグ機能を具えているとすれば、わざわざ余計なコードを埋め込む必要はあるまい。よって、用いる言語系と、システムとの距離によって、デバッガ派と print 文派に分かれることになりそうだ。実際は、いろんな手法を組み合わせるのであろうが...
テストにおいては、誰もが怠け者になりがちである。最も厄介なのは微妙に動いているように見える現象で、おまけに放置されがち。そこで、assertion を埋め込んで、不変条件を自動チェックするといった考え方も有効である。おいらはこの思想が好きだ。
print 文派のアームストロングは、こう言っている。
「プログラミングの偉い神様が言っています。汝プログラムの間違っていると思われる部分に printf 文を置いて再コンパイルし実行せよ...
"ジョーのデバッグの法則"というものがあります。それは、すべてのバグは最後にプログラムを修正した箇所からプラスマイナス3ステートメント以内にある、というものです。」
そもそも、デバッガの吐き出す情報が正しいのか?という問題もある。デバッガが関与する時点で、物理的なタイミングのズレが生じ、不安定な動きをすることもある。したがって、検証においては、検証環境をも含めたデバッグを心掛けるようにと、おいらは周りの連中に指示している。そのためには、必然的にシステムを理解する必要があり、それが真の意図だけど...

3. 純粋関数型と静的型付け
関数プログラミングとオブジェクト指向プログラミングでは、どちらが生産的か?という議論をよく見かけるが、宗教論争に映る。ここでは、ジョーンズがもう少し突っ込んだ観点から純粋関数型言語の魅力を語ってくれる...
関数型言語の始まりが、ギーク的で数学的であることは想像に易い。尚、ここで言う関数とは、多くの手続き型言語が採用している関数とはかなりイメージが違う。少なくとも副作用がない。アーサー・ノーマンは、副作用のまったくない二重連結リストを構築する方法を示したという。二重連結リストを作ろうとすれば、セルを割り当てて互いに指すような仕組みが必要で、どこかに副作用が生じそうなもの。だが、純粋関数型言語ならば、副作用なしにそれを実現できるという。デビット・ターナーという人の論文に、SK コンビネータについてのものがあるそうな。SKI なら聞いたことがあるが。ラムダ計算を変換して実行する一つの方法で、I は SKK と等価で取り除くことができるらしい。任意の複雑なラムダ項を、なんらかの変換ステップによって、S と K の項に置き換えられるのだとか。この得たいの知れない S や K のコンビネータが実装できれば、任意の演算モデルが実装できるってか。にわかに信じがたい、まるで魔法のような抽象化演算モデル。純粋関数型言語とは、純粋数学言語のようなものであろうか?数学も言語であることに違いはない。この発想は、まだノイマン型アーキテクチャの領域に留まっているのだろうか?純粋な関数にできることは、答えを返すことがすべて。根本的に呼び出すというプロセスは必要ないってか。だから、カッコだけでつなぐ Lisp のような構造も可能となる。だが、Haskell はそんな次元ではなさそうである。
とはいえ、評価するプロセスは必要だし、評価した結果を出力するのがコードのすべてだ。つまり、応答した遅延評価を扱うことが、入出力の問題となる。ここで言う「純粋」というのはどういう意味であろうか?極めて強い静的な型ということらしいが... ん~、難しい!
ところで、プログラミング言語には、データ型というものがある。これが言語の本質だと思うから、言語リファレンスを読む時は必ず型の章から始める。ちなみに、Perl のような言語に触れると、型なんかお構いなしって感じで、やはりクレイジーに映る。むかーしは型が厳密でない言語を扱う気がしなかったものだが、近年は適度に融通が利く言語を好む。ジョーンズは、ほとんどのプログラムは静的型で書けると主張する。保守の面で素晴らしい恩恵があると。
「依存型プログラミングをやっている人たちは言うでしょう。型システムは究極的にはすべてを表現可能にすべきだと。しかし型というのは奇妙なところがあって、コンパクトな仕様言語のようなものです。型は関数についてなにがしかのことを言いますが、頭の中に一度に入れられないほどたくさんのことは言いません。だから型について重要なのはそれが明快なことです。」
なるほど、型が関数の抽象化をなしているという見方はできそうか。データ型を適切に定義するだけで、そのプログラムが何をするものかについて、かなりの事を語ってくれる。全体像として型を書いて、型が済んだから次はコードを考える、という2段階のプロセスではない。整理する順番は二段階だとしても、型の検討中にスケッチ用のコードを同時に書いている。型設計そのものがプログラム設計であるという発想は、まったく同感である。

4. 並行プログラミングとソフトウェアトランザクショナルメモリ
ジョーンズは、STM が世界を救うほどのものではないが、ロックや条件変数を使う方法よりマシだと言っている。複数のプログラムカウンタ、マルチスレッド、マルチコア上で共有メモリを使うぐらいなら、STM の方が優れていると。
ロックベースのプログラムは、競合を最小化するためにロックを保持する期間を最小限にしようとするだろう。だが、細かい粒度のロックはうまくやる事が難しい。この点で STM が大きく優っているらしい。非常に細かいロック並みの粒度を、シンプルな原則で手に入れられるという。STM の推論原理では、トップの不変条件を設定すれば、後は逐次処理で推論できるらしい。例えば、銀行口座の残高を管理する場合、取引トランザクションの開始時と終了時で不変条件が成り立つようにすれば、推論では逐次的であっても、引き出そうが、預けようが、トランザクションは分離できるという考え方である。
となれば、トップレベルの不変条件の設定が鍵となりそうである。トランザクションの前後を矛盾なく設定する必要がある。また、トランザクションの途中で例外が生じても、それを破棄して不変条件は絶対に破壊されないようにする必要がある。並行処理にもかかわらず、命令型のコードに対してシーケンシャルに推論できると言っているようだが、ほんまかいな?やはり用途によりそうだ。
いずれにせよ、ロックマネージャのようなヤツが、データベースの中で最も物々しい存在となりそうだし、あるデータがロックされて、アクセス不能になるといった現象は、STM でも生じそうな気がするけど...

5. 文芸的プログラミング
文芸的プログラミングの提唱者といえばクヌースだが、当人は趣味みたいなものだと言っている。いずれにせよ、これが最高のものという証明はできまい。考え方のセンスだから、うまくやる人とそうでない人もいるだろう。
クヌースは、文章を書くためのルールを二つ挙げている。一つは、読者を理解すること。二つは、技術的な文書という条件付きで、すべてを二通りの仕方で補うように書くこと。だから、通常の技術文章は冗長性があるという。へー...
確かに、一つの事を違った視点から語るだけで、頭の中に入ってきやすい。文芸的プログラミングは、コードを書いた後にドキュメントを書くといったものではなく、両方を同時に書くようなもので、そこにはコードがあるだけでなく、ドキュメントが共存することになる。優れたコードを読む楽しさは、優れた小説を読む喜びに似ている。
スティールは、C の欠陥は文芸的プログラミングツールをもってしても克服するのは難しいことだと言っている。Common Lisp 用の文芸的プログラミングツールがあれば、きっと早く飛びつくだろうと。
しかし、文芸的プログラミングの魅力を認めつつも、現実にコードに反映することは難しいという意見もある。トンプソンは、二つの書き方があるなら、片方は間違っていると指摘している。正しいのはマシンが実行する方だけと。ノーヴィグは、こう言っている。
「クヌースのオリジナルの"文芸的プログラミング"の論文を読むと、彼が本当に言おうとしているのは、"本を書くための最良の順序は何か"ということで、本全体が読まれることを前提としており、それが論理的な順序になるようにしようと考えています。みんな今ではそのようにはしていません。本を読みたいとは思っていなくて、インデックスを求めているのです。"読まなければならない最小限の部分はどこだろう?必要な3段落だけを見つけたい。それを示してくれ!"これは大きな変化だと思います。」
圧倒的多数はそうだろうが、中には一冊を隅々まで目を通したいという貧乏性の読者もいる。ここに。やはり好みの問題であろう。逆に、上辺だけを拾って回る読者を締め出すには良い方法とも言えそうか。実際、技術文書ってやつは、読者の理解よりも数学的な厳密性が優先されるもの、という見方をする人が多い。だから、なるべくコンパクトに書きなさい!とよく叱られる。誤解されないように意識すると、どうしても補足的な記述を加えずにはいられない。おまけに、酔っ払いはお喋りときた。なによりも自分に分からせようと書いている。このブログにしても、対象読者は十年後の自分だ。ただ、数ヶ月後に読み返すと既にチンプンカンプン!文芸的プログラミングへの道は遠すぎる。はぁ~...

6. 過剰なブラックボックス化
ライブラリを自分で書けないなら、やることはライブラリを呼び出すだけになる。ライブラリの使い方を丸暗記することが仕事になるのでは、寂しい!数学書には証明がいっぱい詰まっているが、用途にピッタリとはまる定理がなかなか見つからない。ライブラリにも似たような事情がある。
おまけに、お偉いさんには、とんでもないライブラリを強制する性癖がある。黒幕の潜むブラックボックスは、いつも悪臭が漂う。根拠のないスケジュールの短縮という思想に憑かれると、マイルストーン上に何かが埋まっているだけで仕事をした気になれるらしい。再利用の効果を過剰に強調すれば、なんでもブラックボックスに頼ろうとする。それで責任転嫁できればOKってか?設計哲学の合わないライブラリやブラックボックスを組み合わせれば、奇妙な設計資産を量産させるだろうに...

7. 民主主義の在り方
スティールの言葉は興味深い。
「Lisp は容易に成長してきた言語の例だと思います。そのマクロ機能の柔軟性のためです。またある程度までは、それを作ったグループの社会的な姿勢のためでもあります。
それと対照的に、Scheme はもっと苦難の道をたどっています。そのある部分は、Scheme コミュニティが初期において全員、ないしはほとんどの人が同意するのでない限り何も言語に付け加えないという文化を発展させたためです。反対投票の文化なのです。
一方で、Common Lisp のほうは多数であればみんなを満足させるに十分という文化です。人はほかのものを手に入れるためなら、そう熱烈に好きでないものも受け入れるのです。」