HN 日本語サマリー

← 一覧へ戻る
プログラミング

FEXPRとvtable:LispEインタプリタの仕組み

FEXPRs vs. vtable: how LispE interpreter works (github.com)

17 pointsby birdculture4 コメント

要約

LispEは、コンパイルされたオブジェクトのインタプリタという逆説的なアプローチを採用しています。LispEでは、言語の各命令が`eval`メソッドを公開する派生クラスに変換され、抽象構文木(AST)がC++のオブジェクトとして最適化されます。この記事では、このアプローチが従来のLispにおけるFEXPRの課題をどのように克服し、不変性によって効率的な評価を実現しているかを解説しています。

全文翻訳

2.7 FEXPR vs. vtable

FEXPR vs. vtable: LispEはどのように命令を評価するか

LispEのパラドックス:コンパイル済みオブジェクトのインタープリターである。

ああ!インタープリターとコンパイラの有名な対立。一方では、柔軟性と可変性を備えた元のコードを保持しますが、機械レベルの最適化の余地はほとんどありません。他方では、コンパイルは効率的なバイナリを提供しますが、それはコンパイルされたマシンにひどくローカルなものです。少なくとも、通常はあらゆる方向に最適化できますが、コードはその形式で永遠に凍結されます。Lispにとっては、それは少し残念なことです。超最適化されたLispを構築しながら、ホモイコニシティーを失うのは、最適とは言えません。

しかし、LispEは歩くパラドックスです。なぜなら、LispEはこの選択を拒否するからです。それはコンパイル済みオブジェクトのインタープリターであることを選びます。知っています、そのように言うと非常にハードボイルドに聞こえます。それでも… LispEが提案するのは、言語の各命令をevalメソッドを公開する派生クラスにすることです。すべてのクラスは独自のevalオーバーライドを持ちます。そして、これらすべてのクラスが、オリジナルで示唆に富む名前を持つ単一の親クラス、Elementから派生するため、それらすべてを保持するC++ベクトルを構築できます。そして、ここで奇跡が起こります:ASTは生きたまま保持されますが、各ノードは完全なC++アーセナルで最大限に最適化できるオブジェクトです。

このテキストの主張は、この奇跡が単一の等価性にかかっているということです。残りの議論はそれを正確にし、防御します:

datum:        f()           ⟺ F.eval()
instruction:  f(a₁,..,aₙ)   ⟺ F(a₁,..,aₙ).eval()

ここでFは、引数をサブノードとして保持する普遍的なルートクラスから派生したクラスのインスタンスであり、evalは引数なしのメソッドで、階層全体で均一です。データムはゼロ項ケース、サブノードを持たない命令であり、そのevalはそれ自体を返します。等価性はFが不変である場合にのみ成り立つこと、そしてLispEが命令で行うすべてがこれから従うことを見ていきます。

しかし、まず、時間を遡り、人々がLispについて真の質問をしていた遠い昔、FEXPRsに関する議論に戻りましょう。

1. FEXPRとは何か?

初期のLisp(Lisp 1.5、MacLisp)では、演算子は2種類ありました:

  • EXPR:引数が呼び出し前に評価される通常の関数(適用順);
  • FEXPR:引数を評価されずに、生の形式で受け取り、実行時に自分で何を評価するかを決定し、必要に応じてevalを呼び戻す関数。

したがって、FEXPRは実行時メカニズムです。オペランドの評価を駆動するのはオペレーター自体です。これは非常に表現力豊かです。if、and、quote、ループなどをプレーンなFEXPRとして記述できますが、この表現力には代償が伴います:コンパイラへの不透明性。

;; FEXPRのアイデア:(test then else) を評価されずに受け取る
(fexpr my-if (test then else)
  (if (eval test) (eval then) (eval else)))

実行時にどの引数をどのように評価するかをFEXPRが決定するため、静的アナライザーはフォームについて何も知ることができません。インライン化なし、最適化なし、早期解決なし。すべての呼び出しはブラックボックスになります。これがKent Pitmanの中心的な議論(Special Forms in Lisp, 1980)であり、歴史的なLispがコンパイル可能性を維持するためにユーザーFEXPRから離れた理由です。LispEは同じ制約に答えますが、異なるルートで、そのルートは上記の等価性です。

2. 等価性 f(a₁,..,aₙ) ⟺ F(a₁,..,aₙ).eval()

関数適用を読み取る通常の方法は関数的です:f(a₁,..,aₙ)は、fをその引数に適用することによって得られる値を示します。オブジェクト指向の読み方は同じことを別様に言います:それらの引数を保持するオブジェクトFを構築し、それにevalメッセージを送信します。これらは類似していません。それらは2つの表記の下での同じ行為です。関数をその引数に適用することは、それらからオブジェクトを構築し、それを自己評価するように求めることです。

これは通常の階層を逆転させます。私たちはオブジェクトを関数を実装する方法として考えがちです。fをFに具体化して、それを運ぶことができるようにします。等価性は反対のことを言います:f(a₁,..,aₙ)は表面的な表記であり、F(a₁,..,aₙ).eval()は、それ自身の評価ルールを運ぶオブジェクトである基盤となる形式です。Lispの(op . args)、C++のF(args)、数学者のf(args)は、Element(args).eval()の3つのスペルです。

微妙な点を述べる必要があります。なぜなら、それはモデルを閉じ込めるからです。データムは、(+ a b)とは性質の異なるオブジェクトではありません。それは、評価ルールが恒等関数である命令です:X.eval()はXを返します。上記の表記では、それはゼロ項ケース、f() ⟺ F.eval()、サブノードを持たない命令であり、その評価はインスタンス自体を生成します。データは命令の退化したケース、evalの不動点です。これが、単一のルートクラスElementがすべてをカバーできる理由です:評価が下降するリストと、評価がそれ自体を返す値は、1つの型の2つのレジームです。命令は std::vector<Element*>であり、各セルは自己評価する方法を知っているElementであり、リーフもサブリストも同様です。「コード」セルと「データ」セルを区別するタグはありません。なぜなら、区別するものは存在しないからです。これはC++で実現されたホモイコニシティーです。「コードはデータのように見える」のではなく、「データは最小限のコードであり、その評価が不動点である」ということです。

なぜ等価性はFが不変であることを要求するのか

等価性は、1つの条件の下でのみ正確です:Fは不変でなければなりません。理由は参照透過性です。f(a₁,..,aₙ)を2回評価すると同じ結果が得られ、値をどこにでも式で置き換えることができます。したがって、F(a₁,..,aₙ).eval()の場合、evalはFを変更してはなりません。評価がオブジェクトまたはそのサブノードを突然変異させた場合、2回目の呼び出しは1回目とは異なる状態を目にし、等価性はオブジェクト側で壊れます。突然変異するevalはもはや関数ではなく副作用のある手続きであり、全体の構築はすべて命令型に戻ってしまいます。

ここで1つの区別を引く必要があります:この純粋さはインタープリターのプロパティであり、それが実行するLispEプログラムのプロパティではありません。ツリーを評価するメソッドは純粋な関数ですが、実行するプログラムは不純である可能性があります。矛盾はありません。純粋な評価者は不純な言語を実行できます。

したがって、不変性は実装の洗練ではなく、evalがそもそも関数であるための前提条件です。そして、それは等価性をf(a₁,..,aₙ)よりも豊かにするものであり、単にそれに等しいというものではありません。Fが不変であるため、インスタンスは永続します:ノード(* a b)はAST内の安定したオブジェクトとして存在し、それを1000回実行するループは同じインスタンスに1000回evalを送信します。1つのインスタンス、1000回の評価。パスごとにフォームを再決定する単純なインタープリターはこれを実行できません。ここではフォームは一度決定され、型に凍結されているため、再実行は何も変更しません。1001回目のevalは、最初と同じ状態から始まります。ターンごとに変わるのはFではなく実行コンテキストです:Fは不変量であり、スタックはバリアントであり、evalは1つを読み取り、もう1つを進める純粋な関数です。命令自体はステートレスであり、独自の変更可能な状態を保持しません。すべての状態はスタック内に、命令の外にあります。

eval自体はインタープリター以外の引数を取らないことに注意してください。引数a₁,..,aₙはevalに渡されません。それらは構成時にサブノードとしてインスタンスに記録されます。F(a₁,..,aₙ).eval()が正確な形式です:Fはサブノードを保持し、それぞれが不変のElementであり、階層全体で均一なevalは、各々がその独自のレジームに従って評価します。定数なら不動点、アトムならスタック上の解決、サブ命令なら下降です。このevalの均一性が、C++ vtableによるディスパッチを可能にするまさにそのものです。1つの仮想メソッド、1つのシグネチャが、クラスごとにオーバーライドされます。

3. LispEはどのように命令を実装するか

基盤は直接従います。LispEが評価するのは、各ノードがElementである抽象構文木です。入力時に、各フォーム(op …)は、opに従って選択されたListのサブクラスのインスタンスにコンパイルされます:

(cons a b)   ->  instance of List_cons_eval
(+ a b)      ->  instance of List_plusn
(defun f …)  ->  calls to f compiled into List_function_eval
(defpat p …) ->  calls to p compiled into List_pattern_eval

そのような各インスタンスは不変であり、その型自体に評価ルールを保持します。ツリーの評価は、各ノードにevalを送信する問題になります。これはホストの仮想メソッドテーブルを通じて右のオーバーライドされたevalにディスパッチされます。フォームを検査して分岐する中央評価者はいません。ツリーは自己評価し、各ノードは独自のルールを保持します。これはまさにvtableが何であるか、オブジェクトに分散されたディスパッチであり、中央集権化されたループではなく、FEXPRのまさに反対です。FEXPRは中央集権化された実行時評価の原型です。

evall_blockが下降を具体化します。ブロックはシーケンスで評価されるフォームのリストです。その値は最後のフォームの値です:

Element* List::evall_block(LispE* lisp) {
    long listsize = liste.size();

    if (listsize == 2)
        return liste[1]->eval(lisp);

    Element* element = null_;

    for (long i = 1; i < listsize && element->type != l_return; i++) {
        element->release();
        element = liste[i]->eval(lisp);
    }

    return element;
}

ループはトラバース自体です。各liste[i]->eval(lisp)は、ノード自身の型でディスパッチされ、親側での検査は不要です。インスタンスは不変であるため、このブロック自体は再構築なしで、ループ内で何度も再評価できます。各中間結果は、次の結果がそれを上書きされるとすぐにelement->release()によって解放されます。命令自体は不変であるため、決して変更されません。

セクション1の議論を締めくくる主張がここで見えます。FEXPRになされた非難は、コンパイラへの不透明性でした。実行時に何を評価するかを決定するため、静的最適化は不可能です。LispEは逆の経路をたどります。構成時に決定し、各命令をネイティブC++クラスに凍結するため、そのコードは他のどのC++コードと同様にコンパイラに公開された通常のコードになります。FEXPRが最適化を制限する場所で、LispEの命令のコンパイルは、同じ理由を逆転させて、決定がなされた瞬間に最適化を可能にします。「コンパイル済みオブジェクトのインタープリター」とはまさにこれです。インスタンスは不変の関数型オブジェクトFであり、そのクラスはネイティブC++コードを保持するため、同じアーティファクトが純粋な関数型項であり、シリコンまで最適化されたオブジェクトでもあります。

ループが1つのインスタンスを再利用できるようにする同じステートレス性は、複数のスレッドがそれを共有できるようにします。命令は変更可能な状態を保持しないため、ASTはコピーやツリー上のロックなしで並行して評価できます。各スレッドに独自のスタックを与えれば、不変の命令は読み取り専用であり、構築によって安全に共有されます。並列インタープリターの難しい部分、共有評価状態の保護は、保護すべき共有変更可能状態が存在しないため、単に発生しません。並行性は、純粋性や再実行と同じ決定から生まれます。命令は不変量であり、スタックはスレッドごとのバリアントです。

4. evalは一面に過ぎない

F(a₁,..,aₙ).eval()はインスタンスの一面であり、その定義ではありません。同じ不変オブジェクトが他のメッセージにも応答します。asString()はテキスト形式を生成します。unify()はパターンとして別の項と一致します。これらが単一のメソッドであることを強制するものはありません。また、インスタンスが存在するのが評価のためだけであることを強制するものもありません。1つのC++オブジェクト、複数の動作。それぞれが送信するメソッドによって選択され、すべてが同じ不変データを読み取ります。

これが、同じElement階層が、3つの別々の表現なしに評価、シリアライゼーション、および統合をサポートする理由です。数値は自己評価する方法(それ自体を返す)、自己印刷する方法、および別の項と統合する方法(等しい場合に一致する)を知っています。List_cons_evalは、評価する方法(ペアを構築する)、印刷する方法((cons a b))、および統合する方法(ヘッドとヘッド、テールとテールを一致させる)を知っています。命令は評価が実行する手続きではありません。それは、印刷をサポートする方法と同様に、評価をサポートするオブジェクトです。evalはこの記事が扱っている側面ですが、他の側面と対等に並んでいます。そして、それらはすべて同じ事実に依存しています。インスタンスは不変であるため、すべての側面は変更を恐れることなくそれを読み取ります。

これは、実質的にHaskellの型クラスと同じ考え方です。ルートElementは、各派生クラスがオーバーライドすることを期待されるメソッドのセットを宣言します:

u_ustring asUString(LispE* lisp);
Element* equal(LispE* lisp, Element* e);
Element* less(LispE* lisp, Element* e);
Element* lessorequal(LispE* lisp, Element* e);
Element* more(LispE* lisp, Element* e);
Element* moreorequal(LispE* lisp, Element* e);

(他にもあります)。asUStringはShow、つまり値がテキストにレンダリングされる方法です。equalはEqです。4つの順序メソッドはOrdです。Haskellがこれらの契約を型が1つずつ実装する別々のクラスに分割するのに対し(instance Show、instance Eq、instance Ord)、LispEはそれらを親クラスに折りたたみ、各派生クラスにそれらを埋めることを要求します。同じ原則、型が操作ごとに1つの動作を提供する、異なるグループ化:型クラスは型からインスタンスを解決し、LispEはvtableを通じてそれを解決します。そして、前述のように、オブジェクトが変化しないため、側面は共存できます。

//2つの要素の比較
Element* List_eq_eval::eval(LispE* lisp) {
    Element* first_element = liste[1]->eval(lisp);
    Element* second_element = liste[2]->eval(lisp);

    //同じポインタ
    //またはfirst_elementの基盤となる実装に従った比較
    bool test = ( (first_element == second_element) || first_element->egal(second_element));

    second_element->release();        
    first_element->release();
    return booleans_[test];
}

5. 動的なケース:明示的なテーブル evals[]

オンザフライで構築されるコードが残っています:

(eval (list 'cons 'a 'b))

ここでは、List_cons_evalオブジェクトはありません。リストは実行時に構築され、その型はコンパイル時に知ることができません。そして、静的型を想定するC++のvtableは、何もディスパッチできません。そこで、LispEが自分で管理するインデックステーブル evals[] を介して、List::evalが引き継ぎます。命令のラベルでインデックスが付けられます:

Element* List::eval(LispE* lisp) {
    Element* e = (this->*lisp->delegation->evals[lisp->checkState(this, liste.size())])(lisp);
    ...
}

checkStateは命令の最初のラベルを16ビット整数として返します。また、インタープリターの状態をチェックする機会も得ます。

evals[t_atom]     = &List::eval_call_function;
evals[t_function] = &List::evalt_function;
evals[t_pattern]  = &List::evalt_pattern;
evals[t_lambda]   = &List::evalt_lambda;
...

決定的な点は、これが最初のものとは反対の、2番目の、中央集権化されたメカニズムではないということです。vtableとevals[]テーブルは、2つの異なるレジームの下で、型をメソッドにインデックス付けするという同じ作業を行います。型がコンパイル時にわかっている場合、C++は暗黙的にディスパッチvtableを提供します。型が実行時にのみ解決される場合、この暗黙的なメカニズムは適用されなくなり、LispEは同じテーブルを明示的に、手でインデックス付けされたevals[]を提供します。ディスパッチは両方のケースで型によって分散されたままです。テーブルを保持しているのは誰が変わるだけです。実際、各命令定義は両方のメカニズムに同時に供給され、evals[]テーブルがクラス実装と同期していることが保証されます。

そして、明示的なテーブルはvtableに収束します。このパスでは、eval_list_instructionは、バッファ共有の意味で、List_cons_evalオブジェクトを(コピーなしで)借用してフォームを評価します:

Element* List::eval_list_instruction(LispE* lisp) {
    List* l = lisp->borrowing((Listincode*)this, size());
    Element* e;
    try {
        e = l->eval(lisp);
    }
    catch(Error* err) {
        lisp->relax(l);
        return lisp->check_error(this, err, -1);
    }
    lisp->relax(l);
    return e;
}

したがって、明示的なテーブルは単なる前置きであり、動的なケースのために、構成では作成できなかった特殊化されたオブジェクトを再構築し、その後、通常のvtableレジームに再び合流します。機能的には、このパスは生のフォームを受け取り、その評価を駆動します。これはFEXPRの動作ですが、拡張メカニズムとして公開されるのではなく、動的なケースのみに限定され、分散ディスパッチに反対するのではなく、オンザフライコードをそれに戻すことによってそれをサポートします。テーブルは、キャッチオールではなく完全なネットワークです。evals[]はすべてeval_errorに初期化され、有効なエントリのみが埋め込まれるため、評価不可能な型のリストヘッドは、未定義の動作ではなく、クリーンなエラーにフォールバックします。

6. 結論

LispEは、Fが不変であるため有効な等価性f(a₁,..,aₙ) ⟺ F(a₁,..,aₙ).eval()に基づいています。その単一の同一性からすべてが導かれます:各命令はElementから派生したクラスの不変インスタンスであり、独自のevalを保持します。ASTはこのようなインスタンスのツリーとして生きたまま保持され、仮想ディスパッチによって自己評価します。インスタンスは、その中の何も変更されないため、ループで1000回実行できます。変更されるのは周囲のコンテキストだけです。型が実行時までわからない場合は、同じ型インデックスディスパッチが明示的にevals[]テーブルによって提供され、特殊化されたオブジェクトを再構築してvtableに合流します。FEXPRは遅延決定し不透明なまま留まりました。LispEは構成時に決定し、コンパイラに透明なまま留まります。だからこそ、パラドックスなしに、コンパイル済みオブジェクトのインタープリターになれるのです。