Pretty printer を支える技術。

Common Lispは言語仕様にPretty Printerが含まれます。
Pretty Printerとはものすごく大雑把にいうとコードフォーマッタです。
Common Lispは言語仕様にコードフォーマッタが含まれる世にも珍しい言語なのです（？）。

XP.

Common Lispは名前が示すとおり、すでに存在している複数のLisp処理系間で可搬的にコードを書けるように一大統一定義を作成しようとして出来上がったものです。
それまでは各処理系が独自にPretty Printerを持っていたのですが、それらは処理系内部のものでユーザに開放されてはおりませんでした。
そこで拡張可能なPretty Printerとして提案されたのがXPです。
（おそらくeXtensible Printerの略記かと思われるのですが、詳細は不明です。）

このたび、XPのコードが発掘されgithubに公開されていたので興味本位でフォークして弄り倒しました。
その結果最適化等、大変興味深い発見が複数あったのでここに記します。

Adjustable vector.

Common LispはAdjustable Arrayをサポートしている言語です。
Adjustable Arrayとは可変長配列のことです。

要素の追加にはVECTOR-PUSH-EXTENDを使います。

* (defvar aa (make-array 1 :adjustable t :fill-pointer 0))
AA

* aa
#()

* (vector-push-extend :a aa)
0

* aa
#(:A)

ListへのPUSHが先頭から行われるのと異なり、Adjustable ArrayへのVECTOR-PUSH-EXTENDは末尾へ要素を追加します。

* (vector-push-extend :b aa)
1

* aa
#(:A :B)

すでに上に見たとおり、要素数がいっぱいになった場合、処理系が背後でいい具合に長さを拡張してくれます。
変数AAに束縛されたAdjustable Arrayは最初長さ1で定義されましたが、今では長さが2に拡張されています。

大変便利なものですが、トレードオフとして計算量の増加が挙げられます。

XPでは最適化のため、Adjustable Arrayを模した配列操作が行われています。
POSITIONやFILLといった各種シーケンス関数からAREFといった配列操作関数まで、Adjustableな配列より通常の配列の方が処理系はすばやく処理できます。

拡張に関する戦略はHASH-TABLEのそれに似ていて、入力が最大長を超えると、ある程度の長さをまとめて確保し以後はその新しい配列を参照するというものです。

欠点としては、要素を追加する際は必ず長さチェックのコードを人間が書いておかなくてはならない点です。
美点としては、どこでチェックするかを制御できる点です。

ある関数が配列への入力処理を複数回行う場合、最終的に必要となる長さを求め、冒頭でチェックを一度すればそれで事足ります。
このような細やかな制御は自動化されていないからこそできることです。

Vector queue.

わかりやすさのためにRGBによるビットマップ画像を例として挙げましょう。
配列にRGBが入っていますが、これを各RGB値をメンバ変数に持つcolorオブジェクトとする場合、コストが大変高くつきます。
オブジェクトの作成（コンストラクト/new/アロケート）は割と高く付く操作だからです。

そこでこれを二次元配列として、各行をcolorとみなします。
こうすればcolorオブジェクトを作る必要はありません。
各RGB値には配列へのインデックスで直接アクセスします。

先に見た通り、XPは一次元可変長配列を持っています。
そこでXPでは、二次元配列ではなく一次元配列でこれを管理します。
一次元配列にRGBRGBRGB...と並んでいると思ってください。
各colorをループで回していく場合は行数*要素数+オフセットでアクセスするわけです。

XPではqueueがこのような実装となっています。

Object pooling.

先にも記した通り、オブジェクトの作成は高価です。
そこでXPでは一度作成したオブジェクトを破棄せずプールして再利用する設計になっています。

XP-STRUCTUREというSTREAM的なオブジェクトとcircularityチェックのためのHASH-TABLEがプーリングされます。

Layered function.

Adjustable Vectorでも記しましたが、XPではinner-loop（同じ結果になる計算をループの内側で繰り返し行うこと）を徹底的に避けるように設計されています。
最下層の関数は範囲チェックを行わない危険なもので、可能な限り上層部で一度のチェックで済ます設計になっています。

Identified error.

XPはCommon Lispが現在の形になる前に書かれたものです。
つまりEXTENDED-LOOP、CLOS、CONDITION-SYSTEMがCommon Lispに含まれる前に書かれたものです。

大変興味深かったのはエラーハンドリングです。

現在ではエラーはその種類によってCONDITIONを定義するのが定石です。

しかしながらXPでは各エラーにIDが振られ、それをTHROWする作りとなっています。

エラーナンバーでエラーの種類を表すというのはなんとも古風なやり口で訝しんだものですが、少々見直しました。

というのもこのエラーIDがテストの網羅性に一役かっているからです。

CONDITIONの型でエラーの種類を表す場合、残念ながらテストの網羅性には寄与しません。

Conclusion.

泥臭い最適化が多くてしみじみしました。