Lispを実装したくなったら読んでほしい本６選
言語実装 Advent Calendar 2022の１日目の記事として書いた。
Lisp Advent Calendar 2022でも枠が空いていたのでダブル投稿。
プログラミング言語を実装してみたい！と思ったらまずは簡単なLispインタプリタから始めるというのは一つの王道だと思う。
複雑な構文解析は要らず最低限の再帰下降法パーサで手に入る構文木を、そのまま再帰的な関数で実行していくtree walking評価器。メモリ確保もヒープにそのまま置いていって、メモリ解放は実装言語のGCに任せるなりプログラムの終了時までやらなかったり。そんなインタプリタを作る経験から得られるものは非常に大きく、どんなプログラマでも一回は試してみてもいいのではないか？と思っている。（個人的な感想です）
そんな簡易Lispを実装してみて沼にハマってしまい、より精緻な言語処理系を作りたいと思ったとする。その時点で：
などを目標に掲げて邁進することも非常に面白いと思う。
しかし「せっかく簡単なインタプリタを作ったのだから、ここからさらにいいLisp処理系を作ろう」と考えるのも自然な流れだろう。構文解析や型システムに手間取られずにいろんな言語機能の実装、インタプリタのバイトコード化、コンパイラの作成、GCなどのランタイムといったトピックを試したいなら尚更だ。
本記事ではそんな人に役に立つと思われる以下の書籍を紹介する：
- Structure and Interpretation of Computer Programs
- Anatomy of LISP
- Lisp in Small Pieces
- Lisp System Implementation
- Functional Programming Application and Implementation
- Topics in Advanced Language Implementation
（ただし英語＆絶版のものもいくつかあるので注意）
Structure and Interpretation of Computer Programs
言わずと知れた魔術師本。MITのプログラミング入門の教科書として使われていたことでも有名。Lisp方言のSchemeを使って書かれたこの本では、最初の方ではプログラミング言語の基本機能について（かなりの駆け足で）語っているのだが、最後の2章ではSchemeを使ってSchemeのサブセットの処理系を書く話になる。本当にこの本でプログラミング入門した人がいるのか、いつも気になっている。
第4章ではMetacircular Evaluatorを作る。これは何やら難しそうな名前だが、基本的にSchemeでSchemeインタプリタを実装するというだけの話だ。この章ではさらに静的解析を行なうことで実行前に部分的に評価できるところはやってしまうといったインタプリタの効率化や、遅延評価・非決定的な演算などのインタプリタ拡張を行なっている。
第5章ではまずSchemeでレジスタマシンのシミュレータを書き、第4章と同じSchemeのサブセットをそのレジスタマシンで実行できるように、まずはそのレジスタマシン上で動くインタプリタを作り、そしてその後そのレジスタマシン向けのコンパイラを書く。Lispのデータをどうメモリで表現するか、どのようにガベージコレクションを行うか、なども見ていく。
Anatomy of LISP
今回のおすすめ本では一番古く（1978年）残念ながら絶版。どうにかして読む価値はあると思う。
本の前半はLispの解説で、なんとS式ではなくM式で話が進むので時代を感じる。後半では満を持して今まで解説してきたLispをどのように実行するかという話になる。そしてそれは「Lisp Machineという抽象機械上での実行」に絞られており、例えばSICPで出てくるようなインタプリタの話はない。
この抽象機械がどのようなメモリレイアウトやレジスタを持っていて、ガベージコレクタはどのようなアルゴリズムで、この抽象機械のマシン語にコンパイルするためのコードはこれこれ、さらにそれを最適化するための手法、とどんどんこの抽象機械を対象としたLisp処理系を深化させていく。この一点集中型の話がこの本の特色でかなり勉強になる。
Lisp in Small Pieces
Lisp実装についての本では一番有名だと思われる本。原著はフランス語で書かれていて、英訳されたものが頭文字がLiSPになるこの題名を付けられている。
章ごとに別のLispインタプリタ・コンパイラが書かれていて、実にさまざまなトピックについてどう言語処理系を（Lispで）書くかがこれでもかと紹介されている。
SICPよろしく簡単なmetacircular evaluatorからはじめて、Lisp-1とLisp-2の比較をしたと思ったら、継続のあるインタプリタの実装、さらにそのような複雑なソース言語を実行できるラムダ計算的なdenotationalインタプリタなどを書いていった上で、効率化のための部分的コンパイル、バイトコードへのコンパイル、実行時に言語のさまざまな部分を参照・変更できるreflectionやマクロシステム、LispコードのC言語へのトランスパイル、そして最後にはオブジェクトシステムの実装。この一冊でLispの諸機能の実装方法についてはとりあえず包括的に触れられるぐらいの幅を持っている。また継続についてはMLコミュニティなどでもこの本の内容を参考にしている話が出たりするのでLispに限らず言語実装全般において役に立つ。
一つ難をあげるとすれば、翻訳されたものだからか何となく読みにくく感じてしまう点。書いてあるトピックは文句なしに面白いのだが・・・。
Lisp System Implementation
LISP9というオレオレLisp処理系の解説書。作者のNils M HolmはR6RSのAcknowledgementsにも名前を連ねている。（が本人はR4RSが好きでR6RSは嫌いらしい）
6000行弱のC言語による処理系のコードをかなり詳しく解説している。処理系としてはバイトコード・コンパイラと抽象機械の組み合わせ。扱っているトピックについてウェブサイトを引用すると：
LISP data objects, syntax analysis, closure conversion, lambda lifting, operational semantics, bytecode generation, bytecode interpretation, primitive functions, bootstrapping LISP code, macro expansion, lexical and dynamic binding, tail call elimination, garbage collection, non-local exits, the read-eval-print loop (REPL), reading and printing LISP objects, input and output ports, error handling, heap image files, etc ...
と多岐にわたっている。文字列の処理などある程度実用に耐える処理系としての機能をそろえているようで、コードリーディング・写経などに良さそう。個人的には近いうちにZigの勉強がてら移植してみたいと考えている。
Functional Programming Application and Implementation
Lispkit Lispという純粋関数型な（副作用がない）Lispの言語機能と処理系の解説。この本の最大の特徴はLispのコンパイル先の抽象機械がPeter LandinのSECDマシンだということ。SECD抽象機械とそのマシン語をターゲットにするコンパイラの実装を学ぶには多分最良の資料だと思われる。
ちなみにこの本を元ネタとして記事を何本か書いた：
またSECD機械の非決定性や遅延評価への拡張などの話題もあって楽しい。
ただしSECDがLispのための効率的な処理系になるかというといろいろと疑義が出ている。実際の処理系で使う抽象機械としてはFelleisenのCESKやLeroyのZincの方がおすすめかもしれない。
Topics in Advanced Language Implementation
１５人のプログラミング言語実装の専門家によるアンソロジー。かなりLispの話題が多い。Lisp関連の章題を抜き出してみると：
- Data-Flow Analysis and Type Recovery in Scheme
- Design Considerations for CMU Common Lisp
- Compilation Issues in the Screme Implementation for the 88000
- The Implementation of Oaklisp
- An Experimental Implementation of Connection Machine Lisp
- A Simple System for Object Storage in Common Lisp
というものがある。各章は短めとはいえ実装者による生の経験談なので「実用的なLispを実装するためにどのようなデザイン上の選択肢があってどのような意思決定をしたのか」という話が豊富。メモリ、GC、並列化、オブジェクト指向などの話題もカバーされていてLisp in Small Piecesとはまた違う形で非常に幅広いトピックを漁れる。
まとめ
見直してみるとLisp実装本の豊富さに驚く。方言があるので単一言語ではないとはいえ、例えば「ML系言語の実装本」だとここまで多くはならないだろう（論文はたくさんあるが）。やはり言語実装者の心の琴線に触れる何かがあるのだろうか。
何はともあれ、この記事では
- 入門的なStructure and Interpretation of Computer Programs
- 個別の実装について詳しくみていくAnatomy of LISP、Lisp System Implementation, Functional Programming Application and Implementation
- Lisp実装におけるさまざまなトピックをみていくLisp in Small Pieces、Topics in Advanced Language Implementation
と趣の違う本を6冊紹介してみた。皆様がLisp実装沼にハマる一因となれば幸いである。
