( ) 【Common Lisp】
SBCLのREPLは単なるインタープリタでは
ない

by
  • SBCLのREPLは見た目はインタープリタだが、内部では式をネイティブコードにコンパイルしてから実行している。
  • REPLはインタープリタとコンパイラの両方を内包できる概念であり、SBCLはコンパイラを選んだ実装だ。
  • LispのマクロはコードをS式というリスト構造で扱うため、ReadとEvalの間でコードそのものを変換できる。

関連記事

1. インタープリタとコンパイラという古典的な二項対立

Common LispのREPLは、インタープリタのことだと思っていました。
Read Eval Print Loopという名前がそう聞こえるし、Pythonのシェルでも同じ略語を使います。
でも、Common Lispの実装 SBCL の REPL では、その先入観はちょっと違います。

インタープリタ vs コンパイラ — 古典的な二項対立 インタープリタ コードを1行ずつ読む ↓ そのまま実行 対話的 / 実行速度は遅め 例：BASIC コンパイラ コードを機械語に変換 ↓ 変換後に実行 高速 / 事前ビルドが必要 例：C ? SBCLは？

多くのプログラミングの入門書では、インタープリタとコンパイラの区別から始まります。

  • インタープリタは、コードを読んでそのまま実行する。
  • コンパイラは、コードを機械語に変換してから実行する。

対話的に使えるのがインタープリタで、速いのがコンパイラ、という整理です。

BASICのインタープリタを思い浮かべると分かりやすい。
1行読んで、すぐ実行するのがインタープリタ。

実は、BASICやCの処理系もいろいろあり、そう一概には言えないのですが、ここではSBCLの特徴を考えるために、典型的処理系を想定します。

1.1. SBCLのEvalはコンパイルしている

ところがSBCLのREPLは、この分類に収まりません。
対話環境で、コードをすぐに実行するのに、コンパイラなのです。

SBCLのREPL — 中身はコンパイラ 式を入力 REPLに打ち込む compile lambda→ネイティブ funcall メモリ上で即実行 結果 Print JIT との違い JIT（V8など） バイトコードVM で先に動かす ホットスポットを後で機械語化 SBCL VMなし / 実行前に機械語化 AOT（Ahead Of Time） REPL ⊃（インタープリタ ∪ コンパイラ） SBCLはコンパイラを選んだREPL

SBCLのドキュメントには、「SBCLは本質的にコンパイラのみの実装である」と書かれています。

その仕組みは、単純なシンボルの評価を除いて、複雑な式はすべてcompileを呼んでからfuncallで実行されます1。
つまり、REPLに式を打ち込むたびに、その式がネイティブコードにコンパイルされてメモリに展開され、即座に実行されています。
インタープリタのような見た目ですが、中身はれっきとしたコンパイラです。

これは、JITに似ているますが、それとも異なります。
V8やLuaJITのようなJITインタープリタは、バイトコードを解釈する仮想マシン（VM）の層を持ちつつ、実行中にホットスポットを検出して機械語に変換します2。
JITは、インタープリタの高速化として設計されていて、VMという抽象が前提にありますす。

SBCLには、そのVMがありません。
入力された式をEvalに渡す前に機械語への変換が完了しています。
JITが「走りながら速くなる」のに対して、SBCLは「走る前に機械語になっている」設計です3。
これは、AOT（Ahead Of Time）コンパイルと言えます。

すると、REPLとインタープリタの関係はこう整理できます。

REPL ⊃ （インタープリタ ∪ コンパイラ）

REPLでは、評価の実装は問わないので、インタープリタもコンパイラもその中に入れられるのです。
そして、SBCLはコンパイラを選んだREPLということになります。

2. Meta Read と Meta Eval

REPLは、Read Eval Print Loopですが、ReadからEvalまでの流れを、もう少し細かいステップに分けて考えてみます。

Meta Read と Meta Eval — 処理系の比較 処理系 Read Meta Read Meta Eval Eval BASIC インタープリタ テキストを 1行ずつ読む AST構築 なし なし ASTを そのまま 解釈・実行 C コンパイラ トークン分解 →AST構築 プリプロセッサ Read前に テキスト書換 機械語ファイル をディスクに 書き出す 別プロセスで OSがロード して実行 Common Lisp SBCL S式として リストに読込 マクロ展開 S式を リストで変換 Read↔Eval間 機械語を メモリに展開 AOT メモリ上の ネイティブ コードを実行

コードの読み取り（Read）とコードの評価（Eval）に付随するメタ処理を、ここでは「Meta Read」「Meta Eval」と捉え直してみます。
すると、3つの典型的な処理系の違いが整理できます。

ReadMeta ReadMeta EvalEval
BASIC Interpreterテキストを1行ずつ読んでASTを構築なしなしASTをそのまま解釈して実行
C Compilerテキストをトークン列に分解してASTを構築プリプロセッサがテキストを書き換える（Read前）機械語の実行ファイルを生成してディスクに書き出す別プロセスとしてOSが実行ファイルをロードして実行
Common Lisp REPLS式としてリストに読み込むマクロがS式をリストとして変換する（Read内）機械語を生成してメモリに展開するメモリ上のネイティブコードを即実行

2.1. コードがリストだから、マクロが自然に成立する

読み取ったコードは、解釈する際に「マクロ」によって操作できます。
C や CommonLispの「マクロ」は、読み取りのメタ処理、Meta Readのプロセスと言えます。

たとえば、Cには、読み取りのメタ処理として、プリプロセッサがあります。
しかし、これはコードをテキストとして書き換えるだけで、構造を解釈する Read の前に走ります。

一方、Lispのマクロは S式としてReadされ、Evalに渡る前に展開されます。
マクロが返したリストはRead列に追加されて次のReadステップに送られ、展開結果をReadが受け取り、そこにさらにマクロがあれば再び展開する。
この繰り返しがReadの内側で完結しているのです。

これは、LispのReadがほかの言語と大きく異なるからです。
それは、コードをS式、つまりリストとして読み込むことです。

(+ 1 2)Code language: Lisp (lisp)

このコードは、Readが終わった時点で、+、1、2という要素を持つリストになっています。
あとは、それを評価するだけです。

この性質がLisp処理系と一体的な Meta Read 、つまりLispマクロを可能にしています。
Lispにおいて、マクロは引数としてリストを受け取り、コードとしてリストを返す関数です。

(defmacro def-op (name op)
  (list 'defun name '(a b) (list op 'a 'b)))Code language: Lisp (lisp)

マクロ定義では、listでリストを組み立てているだけです。
ただし、マクロで生成されたリストはそのままコードとして評価されます。

def-op を使えば、演算子の名前を渡すだけで関数定義が生成されます。

(def-op my-add +)
(def-op my-sub -)

; マクロなしで同じことをするなら、関数ごとに手で書くしかない
(defun my-add (a b) (+ a b))
(defun my-sub (a b) (- a b))Code language: Lisp (lisp)

コードとデータが同じ構造であるS式で表現されているから、これが成立する。
この性質をhomoiconicityと呼びます4。

つまり、同じMeta Readという層にいながら、CはReadの外側でテキストを操作し、LispはReadの内側でS式を操作する。
操作対象がテキストかリストかで、マクロの柔軟性が根本的に違っています。

2.2. コンパイルされたコードはどこへ？

「コンパイル」に話を戻すと、これは、コードを解釈して作った抽象構文木（AST）をもとに、機械語に変換するステップと言えます。
これは、評価のメタ処理、Meta Eval と言えます。

たとえば、BASICインタープリタはここがなく、ASTをそのまま解釈・実行します。
他方、Cのコンパイラは、いったん機械語の実行ファイルを生成します。
したがって、コードの実行である Eval とは別プロセスになります。

SBCLのコンパイル処理も、評価前の Meta Eval ですが、マシン語はメモリに置いてそのままEvalに進みます。

つまり、インタープリタとコンパイラを分ける境界線は Meta Evalの有無にあるわけです。
コンパイルしながら対話環境で実行することも可能なのです。

3. CMUCLの設計

REPLの E はEvalです。
外から見ると「評価した」としか見えません。

しかし、SBCLでは式を評価するまでの間に、マクロ展開、AOTコンパイル、メモリへのロード、実行という一連の処理が走っています。
コンパイラ、ランタイム、GC、マクロ展開器、REPLが全部同一プロセスに同居していて、compileやcompile-fileはただの関数として呼び出せます5。

この設計は、CMUCLとして1980年代にCarnegie Mellon大学で始まりました6。

Read Eval Print Loopという名前の簡潔さと、そのEvalの中身の複雑さ。
SBCLのREPLには、コンパイラ理論と動的言語の設計思想が詰まっています。

3.1. 動的型付けをコンパイルするという難しさ

ところで、Lispをコンパイルするのは、大変そうです。
それは、実行時に型が決まるからです。

動的型付けのままネイティブコードを生成し、同一プロセスでREPLが動く、という処理系は珍しいです。
ClojureはJVM上で動き、Racketもデフォルトではバイトコード実行です。
動的型付けのままAOTコンパイルしてREPLと同居させる、というのは、SBCL系統のユニークな特徴です。

REPLを持ちながらネイティブコードにコンパイルする点で、HaskellのGHCiは SBCLに近いです。
しかし、Hindley-Milner型推論によってコード全体の型を静的に確定させてからコンパイルします7。

静的型付け言語のコンパイラは型を契約として扱うことができます。
型が確定しなければコンパイルエラーにして終われます。

一方、Common Lispは動的型付けなので、型が実行時まで決まりません。
それをネイティブコードにコンパイルするには、型の確定度合いに応じてコードを変える仕組みが必要です。

SBCLでは、型宣言がなければ実行時の型チェックコードを生成します。
declareで型を教えれば最適化できますが、declareを書かなくても動きます。

(defun fast-add (a b)
  (declare (type fixnum a b))
  (+ a b))Code language: Lisp (lisp)

プログラマが最適化するかどうかを選べる設計で、SBCLは型宣言があればその情報を使ってコンパイル時に型チェックをし、実行時の型チェックを省いた機械語を生成できます8。

静的型付けは「型を与えなければ動かない」という制約から始まります。
SBCLは「何も書かなくても動く」から始まって、型ヒントを加えるほど効率が上がる。
自由を前提にして絞れる部分だけ絞る、発想の順序が逆の設計なんです。

  1. SBCL User Manual「Compiler-only Implementation」セクションに明記されている。evalはlambda式を生成し、compileでネイティブコードにコンパイルし、funcallで実行するという手順を踏む。 – SBCL User Manual
  2. V8はIgnitionというバイトコードインタープリタでまず実行し、頻繁に呼ばれる「ホット」な関数をTurboFanがJITコンパイルして機械語に変換する4段階のパイプラインを持つ。 – Maglev – V8’s Fastest Optimizing JIT
  3. SBCLマニュアルには「SBCLの直接の祖先はCMUCLのx86移植版で、レジスタの少ないx86アーキテクチャをサポートするために多くの奇妙な変更が必要だった」と記録されている。 – SBCL User Manual
  4. homoiconicityは「homo（同じ）」と「icon（表現）」を組み合わせた語。Lispはプログラムコードの構造がリストという標準データ構造に直接反映される最初の言語とされ、この性質が後にhomoiconicityと名付けられた。 – Lisp (programming language) – Wikipedia
  5. SBCLは自分自身をCommon Lispで書かれており、ANSI準拠の任意のCommon Lisp実装からbootstrapできる。CMUCLは自身のコンパイル済みバイナリがなければソースをコンパイルできなかったが、SBCLはこの制約を解消した。 – SBCL: a Sanely-Bootstrappable Common Lisp
  6. CMUCLはSpice Lispを起源とし、1980年代のMachオペレーティングシステム上のIBM RT向け実装から始まった。SBCLは1999年12月にWilliam NewmanがCMUCLのx86移植版からフォークして発表した。名前の「Steel Bank」はAndrew CarnegieとAndrew Mellonへの敬意を示す。 – Steel Bank Common Lisp – Wikipedia
  7. GHCはネイティブコードコンパイラだが、GHCiはデフォルトではバイトコードにコンパイルして実行するインタープリタモードで動作する。ネイティブコードでのコンパイルは:set -fobject-codeで有効にできる。 – GHC User Guide
  8. SBCLのコンパイラはCMUCLのコンパイラ（内部名Python）を継承しており、Common Lisp型システムへの高度な理解と型宣言の保守的な扱いを特徴とする。型推論によって宣言なしでも型を絞り込み、宣言があればさらなる最適化が可能になる。 – SBCL User Manual – Handling of Types