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

エラーが発生しました。このページをリロードしてください。 naver / lispe パブリック通知 通知設定を変更するにはサインインが必要です フォーク 19 スター 600 2.7 FEXPRとvtable Claude Rouxが2026年6月23日にこのページを編集しました · 9リビジョン FEXPRとvtable：LispEが命令を評価する方法 LispEのパラドックス：それはコンパイルされたオブジェクトのインタプリタである。ああ！インタプリタとコンパイラの有名な対立だ。一方では、元のコードを保持することで、柔軟性と可塑性を得られるが、マシンレベルの最適化の余地はほとんどない。他方では、コンパイルは効率的なバイナリをもたらすが、それはコンパイルされたマシンにひどくローカルなものだ。少なくとも、通常はあらゆる方向に最適化できるが、コードはその形式で永遠に固定される。Lispにとって、それは少し残念なことだ。 超最適化されたLispを構築しながら、その過程でホモイコニシティを失うのは、決して最適ではない。しかし、LispEは歩くパラドックスである。なぜなら、LispEはこの選択を拒否するからだ。LispEはコンパイルされたオブジェクトのインタプリタであることを選択する。分かっている、そう言われると非常に手ごわいように聞こえる。しかし… LispEが提案するのは、言語の各命令を、evalメソッドを公開する派生クラスに変えることだ。すべてのクラスは独自のevalのオーバーライドを持つ。そして、これらのクラスはすべて、Elementというオリジナルで示唆に富んだ名前の単一の親クラスから派生しているため、それらすべてを保持するC++のベクターを構築できる。そして、そこで奇跡が起こる。ASTは生き続け、各ノードはC++の全 Arsenalで徹底的に最適化できるオブジェクトになるのだ。 このテキストの主張は、この奇跡が単一の等価性に基づいているということであり、残りの議論はその等価性を明確にし、擁護する。 データ: f() ⟺ F.eval() 命令: 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つは類推的ではなく、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が不変である必要があるのか 等価性は、Fが不変であるという唯一の条件の下でのみ正確である。その理由は参照透過性にある。f(a₁,..,aₙ)が2回評価された場合、同じ結果を返し、どこでもその値を式に代入できる。したがって、F(a₁,..,aₙ).eval()の場合、evalはFを変更してはならない。もし評価がオブジェクトまたはそのサブノードを変更した場合、2回目の呼び出しは最初の呼び出しとは異なる状態を見るため、オブジェクト側で等価性が破れる。オブジェクトを変更するevalはもはや関数ではなく、副作用のあるプロシージャであり、全体の構造は命令型に戻ってしまう。ここで1つの区別をしなければならない。この純粋さはインタプリタのプロパティであり、それが実行するLispEプログラムのプロパティではない。ツリーを評価するメソッドは純粋関数であるが、それらが実行するプログラムは不純である可能性がある。矛盾はない。純粋な評価器は不純な言語を実行できる。 したがって、不変性は実装の改善ではなく、evalがそもそも関数であるための前提条件である。そして、それが等価性をf(a₁,..,aₙ)に単に等しい以上の豊かなものにする。Fは不変であるため、インスタンスは存続する。ノード(* a b)はAST内の安定したオブジェクトとして存在し、それを千回実行するループは同じインスタンスに千回evalを送る。1つのインスタンス、千回の評価。パスごとに形式を再決定する素朴なインタプリタはこれを行うことができない。ここでは形式は一度決定され、型に固定されるため、再実行は何も変更しない。千と一回目のevalは最初と同じ状態から始まる。ターンごとに変わるのはFではなく実行コンテキストである。Fは不変量であり、スタックは変量であり、evalは一方を読み取り、他方を進める純粋関数である。命令自体はステートレスであり、それ自身の可変状態は持たない。すべての状態は命令の外側のスタックに存在する。eval自体はインタプリタ以外の引数を取らないことに注意。引数a₁,..,aₙはevalに渡されない。それらはコンポジション時にインスタンスにサブノードとして記録される。F(a₁,..,aₙ).eval()が正確な形式である。Fはサブノードを保持し、それぞれは不変のElementであり、階層全体で統一されたevalは、定数に対する固定点、アトムに対するスタック上の解決、サブ命令に対する下降など、独自の体制に従ってそれぞれを評価する。このevalの均一性こそが、C++のvtableによるディスパッチを可能にする。1つの仮想メソッド、1つのシグネチャがクラスごとにオーバーライドされるのだ。 3. LispEが命令を実装する方法 基盤