PostgreSQL (POSTGRES) におけるLisp

前書き

LispからPostgreSQLを扱う記事…ではなく、PostgreSQLの歴史に見え隠れするLispについての調査もどき記事です。

発端は次のようなものです。仕事柄PostgreSQLのメーリスやソースを見たり見なかったりするのですが、今年の1月にRustgreSQLというスレッドがありました。PostgreSQLをRust言語にポーティングするような話はないのかという 何を言っているんだこいつは 話題です。あり得るとしてもせいぜいC++だろうとか、いまだにC99ですらなっていないのに…*1とか、PostgreSQLのC言語の使い倒しっぷりを考えると死ぬほど非現実的だよとか、大変好意的な返信が並ぶ中、Robert Haas *2 の以下の発言が目を惹きました。

I'm tempted to snarkily reply that we should start by finishing the conversion of PostgreSQL from LISP to C before we worry about converting it to anything else.

なんとPostgreSQLの歴史上Lispで書かれていた時期があるようです。当時はへーと思って終わっていたのですが、ふと思い出して気になったので調べてみたという次第です。

PostgreSQLのソースにおけるLispの残滓

現行のPostgreSQLのソースにLispらしき痕跡があるのかを少し見てみます。Robert Haasは上記の発言に続いてこう言っています。

There are various code comments that imply that it actually was LISP at one time and I can certainly believe that given our incredibly wasteful use of linked lists in so many places.

論点は2つで、1つ目はコメントにLISPであった名残が見られることで、もう1つは現行のPostgreSQLがリンクリストを過剰に利用している原点はLispだろうということです。

前者の例としてgram.yのコメントを挙げています。

 * HISTORY
 *    AUTHOR            DATE            MAJOR EVENT
 *    Andrew Yu         Sept, 1994     POSTQUEL to SQL conversion
 *    Andrew Yu         Oct, 1994      lispy code conversion

確かにLispからコンバートしたと書かれています。このスレッドには書かれていませんが、似たようなものとして命名規則にもLispの名残が見られます。リスト操作用のヘッダはsrc/include/nodes/pg_list.hですが、ここを眺めてみると…

/* ※下記実際には行が離れていますが、一々省略記号を書くのも面倒なので続けて引用しています */
#define NIL                        ((List *) NULL)
extern List *lappend(List *list, void *datum);
extern List *lcons(void *datum, List *list);
define nconc(l1, l2)                list_concat(l1, l2)
#define nth(n, list)               list_nth(list, n)

Lispだ…。なお、残念ながらcarやcdrはありませんでした。

もう1つの論点であるリンクリストの多用についてですが…確かにあちこちリストだらけだなという程度で、余りLispっぽい印象を受けたことがないです…。とりあえずLispでプロトタイプを書くとリスト濫用になるよねというのは分かるのですが。

補足：POSTGRESとPostgreSQL

本題である、実際にPostgreSQLがLispで書かれていた時代について…の前に、用語の補足です。今では「ポストグレス」と言えばPostgreSQLのことですが、実はPOSTGRESという前身となるデータベースが存在しています。詳しい歴史はWikipediaのPostgreSQLの記事などにありますが、概要は下記の通りです。以降の話題であるLisp時代を直接に経験しているのはこのPOSTGRESの方になります。

• POSTGRES
  • 1986年、マイケル・ストーンブレーカー博士により、自身の開発したRDBであるIngresの後継としてPOSTGRES（= Post + Ingres）プロジェクトが発足された
  • 1987年には最初のプロトタイプが公開された
  • 問い合わせ言語はSQLではなく、Ingresの流れを汲むQUELであった
  • 1993年にはこのPOSTGRESプロジェクトは終了した
• PostgreSQL
  • BSDライセンスで公開されていたPOSTGRESのソースを元に、問い合わせ言語をSQLに変更したものが起源になっている
  • 1995年に初版が公開された
  • 1997年まではPostgres95という名称だった

実際にLispで書かれていた時代

さて、現在の名残は前述の通りですが、実際にLispで書かれていた当時のことが分かるものとして下記の2つが見つかりました。

• 文献1: 1990年のストーンブレーカー博士の論文：THE IMPLEMENTATION OF POSTGRES (PDF)
  • 「5.3. Programming Language Used」に言語選択に関する記載があります
• 文献2: メーリスのスレッド：Re: [HACKERS] Historical trivia (was Re: First Major Open Source Database)
  • 投稿者は当時の開発者の一人のようです

お互い微妙に情報が足りないので、適宜両者を参照して進めていきます。

まず、そもそもLispが選択された動機についてです。これは文献1に記載があります。だいぶ端折って説明すると、CはIngresで使ったから真新しさがないし、C++はまだ安定した処理系がないし、他に検討した言語も諸々の理由で落とした結果Lispが残ったようです。ポジティブな理由としては、リスト処理（≒木構造処理）が得意なLispはオプティマイザや推論エンジン（？）が作りやすいのではないかと考えたそうです。

Lispといってもどの方言なのか書いてないのですが、それは文献2の方に記載があります。それによると、Franz Lispを使っていたとのことです。この辺りの古い方言は馴染みがないのですが…、g000001さんの「レトロLisp探検: Franz Lisp」などを見るとC言語との連携性の高さに特徴があるようです。POSTGRESの初版は結果的にLispが17000行、C言語が63000行となったそうです（文献1）が、最初の選択の時点でその辺りが斟酌されたのかは分かりません。なお、結果的にC言語を併用することになったのは、メモリ周りなどの低レイヤの処理を扱うにはやはり一日の長があったからとのことです（文献1）。

横道ですが、Franz Lispを作っていたFranz社は、現在では主要な商用Common Lisp処理系の一つであるAllegro Common Lispで知られています。この処理系が登場したのが1986年でPOSTGRESプロジェクトの発足とちょうど同じ年です。もう少しPOSTGRESプロジェクトの発足が遅ければCommon Lispが使われていたのかもしれません。

本題に戻って、次にLispがどの部分で使われたのか、すなわち前述のLisp17000行とC言語63000行の内訳はどうなっていたかです。これも文献1には記載がなく、、文献2の方に記載があります。parser（クエリの解析）、optimizer（実行計画の作成、plannerとも）、executor（その名の通り実際に実行する人）辺りがLispで作られていたようです。…ただ、parserに関しては、

steven wrote and maintained the parser, which was always written using lex/yacc (i.e., C) but had to generate (in C!) a lisp parse tree.

と書いてあり、lex/yaccからLispコードを生成したということなんでしょうか…？

最後に、当時は確かに存在していたLispコードがなぜ消滅することになったのか…ですが、文献1によるとLisp選んだのは完全に失敗だったねという評価になったからのようです（哀しい…）。最大の理由は、2言語の混ぜ合わせはとにかくデバッグが辛かったというところにあるとのことです。他に、大きな欠点として下記3つを挙げています。

• メモリ使用量が大き過ぎる
  • 全体として、走らせるだけで4MBものメモリを使うことになってしまった（数値に時代を感じます）
• DBとしてはガベージコレクタの動作は許容しがたい
  • GCが動かないように頑張ったそうです
• 遅い
  • Lispエキスパートがいればなんとかなったのかも知れないが…とは補足しています

なお、（Lisp単体の範囲では）生産性の高さという部分で恩恵もあったようですが、言語自体よりはインタラクティブなデバッガなど環境面の素晴らしさにによるものだろうと評価しています。

in late 1989, jeff goh wrote a postgres-specific lisp->C translator that automated most of the conversion.

そんな訳で1989年にはコンバータが作られてLispコード消滅の運びとなりました（文献2）*3。

---

以上、PostgreSQL (POSTGRES) におけるLispの歴史の調査でした。

---

*1:移植性の問題で過去に却下されたようです。代表的なところではVisual C++がC99サポートし始めたのがようやく2013年…

*2:PostgreSQLの主要なコミッターの一人です

*3:上の方で引用したコードのコメントでは1994年となっているのが不思議ですが、文献1の書かれた時期を考えても1989年が実際にコンバートされた時期で、1994年はまた別の契機のように思います