c++ - C /C++でインタプリタを実装するために必要な参照

Question

私は、インタプリタを既存のアプリケーションに整数化するプロジェクトに執着していることに気づきました。解釈される言語は、アプリケーション固有の組み込みを備えたLispの派生語です。個々の「プログラム」は、アプリケーションでバッチスタイルで実行されます。

何年にもわたって、いくつかのコンパイラーといくつかのデータ言語トランスレーター/パーサーを作成してきたことに驚いていますが、実際にインタープリターを作成したことはありません。プロトタイプはかなり進んでおり、C++で構文ツリーウォーカーとして実装されています。私はおそらくプロトタイプを超えてアーキテクチャに影響を与えることができますが、実装言語（C ++）には影響を与えません。したがって、制約：

• 実装はC++で行われます
• 構文解析はおそらくyacc/bison文法で処理されます（現在は）
• NekoVMやLLVMのような完全なVM/インタプリタエコロジーの提案は、おそらくこのプロジェクトでは実用的ではありません。これがNIHのように聞こえても、自己完結型の方が優れています。

私が本当に探しているのは、通訳者の実装の基本に関する資料を読むことです。私はSOと、Lambda the Ultimateとして知られている別のサイトをブラウジングしましたが、それらはプログラミング言語理論をより重視しています。

私がこれまでに集めた一口のいくつか：

• クリスチャンQueinnecによる小さな断片のLisp 。それを推奨する人は、「些細なインタプリタからより高度な技術に移行し、バイトコードと「SchemetoC」コンパイラの提示を終了する」と述べました。

• NekoVM。上で述べたように、このプロジェクトをサポートするためにVMフレームワーク全体を組み込むことが許可されるとは思えません。

• コンピュータプログラムの構造と解釈。もともと私はこれはやり過ぎかもしれないと提案しましたが、健全なチャンクを処理したので、@JBFに同意します。非常に有益で、心を広げます。

• ポール・グレアムによるLispについて。私はこれを読みました、そしてそれはLispの原則への有益な紹介ですが、インタプリタの構築をすぐに始めるには十分ではありません。

• オウムの実装。これは楽しい読み物のようです。それが私に基本を提供するかどうかはわかりません。

• スクラッチからのスキーム。Peter Michauxは、Cで記述された迅速で汚いSchemeインタープリター（後のプロジェクトでブートストラップとして使用するため）からコンパイルされたSchemeコードまで、Schemeのさまざまな実装を攻撃しています。これまでのところ非常に興味深い。

• 言語実装パターン：独自のドメイン固有および一般的なプログラミング言語を作成します。これは、通訳言語の作成に関する書籍のコメントスレッドで推奨されています。この本には、通訳者の作成の練習に専念する2つの章が含まれているので、私はそれを私の読書キューに追加しています。

• 新しい（そしてまだ古い、すなわち1979年）：PJブラウンによるインタラクティブなコンパイラーとインタープリターの作成。これは長い間印刷されていませんが、基本的なインタープリターの実装に関連するさまざまなタスクの概要を提供するのに興味深いものです。これについてはさまざまなレビューを見てきましたが、安いので（注文時に約3.50ドルで使用しています）、試してみます。

では、どうですか？新生児を手に取って、Lispのような言語のためにC / C ++でインタプリタを構築する方法を示す良い本はありますか？構文ツリーウォーカーまたはバイトコードインタープリターを好みますか？

@JBFに答えるには：

• 現在のプロトタイプはインタプリタであり、任意のコードファイルへのパスを受け入れてアプリケーション環境で実行しているので、私には理にかなっています。ビルトインは、メモリ内のデータ表現に影響を与えるために使用されます。

• ひどく遅くてはいけません。現在のツリーウォーカーは許容できるようです。

• 言語はLispに基づいていますが、Lispではないため、標準への準拠は必要ありません。

• 上記のように、この問題を解決するために完全な外部VM/インタープリタープロジェクトを追加できる可能性はほとんどありません。

他のポスターにも、あなたの引用をチェックします。皆さんありがとう！

Answer 1

簡潔な答え：

Lisp インタプリタの基本的な読み物リストは SICP です。本の最初の部分で資格が過剰だと感じた場合は、第 4 章にジャンプして通訳を開始します (ただし、第 1 章から第 3 章は本当に優れているため、これは損失になると思います!) .

LISP in Small Pieces (LISP 以降) の第 1 章から第 3 章を追加。特に重要なコントロールフォームを実装する必要がある場合は、第 3 章を参照してください。

Jens Axel Søgaard による最小限の自己ホスティング スキームに関する投稿 ( http://www.scheme.dk/blog/2006/12/self-evaluating-evaluator.html ) を参照してください。

少し長い答え：

通訳者に何を求めているかを知らずにアドバイスをすることは困難です。

• 本当にインタプリタである必要があるのか​​、それとも実際に Lisp コードを実行できる必要があるのか​​?
• 高速である必要がありますか？
• 標準への準拠が必要ですか？コモンリスプ? R5RS? R6RS? 必要な SFRI はありますか?

単純な構文ツリー ウォーカーよりも優れたものが必要な場合は、高速スキーム サブシステムを埋め込むことを強くお勧めします。ギャンビット スキームが思い浮かびます: http://dynamo.iro.umontreal.ca/~gambit/wiki/index.php/Main_Page。

それがオプションでない場合は、SICP の第 5 章と LISP の第 5 章-- より高速な実行のためのターゲット コンパイル。

解釈を高速化するために、最新の JavaScript インタープリター/コンパイラーを調べます。JavaScript を高速に実行するためには、さまざまな工夫がなされているようで、おそらくそこから学ぶことができます。V8 は 2 つの重要な論文を引用しています。

正規のスキーム ペーパーもあります: RABBIT コンパイラのhttp://library.readscheme.org/page1.html 。

少し時期尚早な憶測をするなら、メモリ管理は難しい問題かもしれません。Nils M Holm は本「Scheme 9 from empty space」http://www.t3x.org/s9fes/を出版しました。この本には、単純なストップ ザ ワールド マークとスイープ ガベージ コレクターが含まれています。ソース入り。

John Rose (最近の JVM で有名) は、Scheme を C に統合する方法についての論文を書いています: http://library.readscheme.org/servlets/cite.ss?pattern=AcmDL-Ros-92。

Answer 2

はい、SICPで。

私はこのタスクを何度か実行しましたが、私があなただったら次のようにします。

最初にメモリ モデルを設計します。ある種の GC システムが必要になります。後でボルトで固定するよりも、最初にこれを行う方がとても簡単です。

データ構造を設計します。私の実装では、アトム、文字列、数値、リスト、ブール、プリミティブ関数など、いくつかの基本型を持つ基本的なコンス ボックスがありました。

VM を設計し、API をクリーンに保つようにしてください。私の最後の実装では、これをトップレベル API として使用していました (フォーマットを許してください - SO は私のプレビューをプーチングしています)

ConsBoxFactory &GetConsBoxFactory() { return mConsFactory; }
AtomFactory &GetAtomFactory() { return mAtomFactory; }
Environment &GetEnvironment() { return mEnvironment; }
t_ConsBox *Read(iostream &stm);
t_ConsBox *Eval(t_ConsBox *box);
void Print(basic_ostream<char> &stm, t_ConsBox *box);
void RunProgram(char *program);
void RunProgram(iostream &stm);

RunProgram は必要ありません。Read、Eval、および Print に関して実装されています。REPL は、インタープリター、特に LISP の一般的なパターンです。

ConsBoxFactory を使用して、新しいコンス ボックスを作成し、それらを操作できます。AtomFactory は、同等のシンボリック アトムが正確に 1 つのオブジェクトにマップされるように使用されます。Environment は、コンス ボックスへのシンボルのバインドを維持するために使用されます。

ほとんどの作業は、これら 3 つのステップに進む必要があります。次に、クライアント コードとサポート コードが LISP に非常によく似ていることがわかります。

t_ConsBox *ConsBoxFactory::Cadr(t_ConsBox *list)
{
    return Car(Cdr(list));
}

パーサーは yacc/lex で記述できますが、わざわざ書く必要はありません。Lisp は信じられないほど単純な文法とスキャナー/再帰降下パーサーのペアで、約 2 時間の作業で済みます。最悪の部分は、トークンを識別するための述語 (つまり、IsString、IsNumber、IsQuotedExpr など) を作成し、トークンをコンス ボックスに変換するルーチンを作成することです。

C コードの内外で簡単にグルーを記述できるようにし、問題が発生したときに問題を簡単にデバッグできるようにします。

Answer 3

Samuel Kamin の著書Programming Languages, An Interpreter-Based Approachの Kamin Interpretersは、Timothy Budd によって C++ に翻訳されました。この本に付属することを意図していたので、生のソースコードがどれほど役立つかはわかりませんが、ガベージコレクションなどを含む低レベル言語で Lisp を実装するための基本をカバーする優れた本です (それは、一般的なプログラミング言語であるこの本の焦点では​​ありませんが、カバーされています。)

Lisp in Small Piecesはさらに深く掘り下げますが、それはあなたの場合には良いことでも悪いことでもあります。コンパイルなどには関係のない資料がたくさんあり、その単純なインタープリターは C++ ではなく、Scheme にあります。

SICPは間違いなく良いです。やり過ぎではありませんが、もちろん、インタープリターを書くことは本のほんの一部に過ぎません。

JScheme の提案も良いものですが (私がいくつかのコードを組み込んでいます)、GC のようなものは役に立ちません。

後でさらに提案して、これを具体化するかもしれません。

編集:私のawklispから学んだという人が何人かいます。これは確かに一種の奇妙な提案ですが、非常に小さく、読みやすく、実際に使用可能であり、他の小さいながらも読みやすいおもちゃの Lisp とは異なり、基礎となる高レベルの実装言語に依存する代わりに、独自のガベージ コレクターとデータ表現を実装しています。それらを提供します。

Answer 4

PeterNorvigのJSchemeをチェックしてください。これは驚くほど簡単に理解でき、C++に移植できることがわかりました。ええと、スクリプト言語としてスキームを使用することについてはわかりませんが、jnrsにそれを教えるのは面倒で、時代遅れだと感じます（helloooo1980年代）。

Answer 5

プログラミング言語の推奨事項を拡張したいと思います: アプリケーションと解釈. 通訳者を書きたい場合、その本は非常に短い道のりでそこに連れて行ってくれます。読んだコードを書いて演習を行うと、似たようなインタープリターがたくさんできあがりますが、それらは異なります (1 つは熱心で、もう 1 つは怠惰で、1 つは動的で、もう 1 つはタイピングがあり、1 つは動的スコープを持ち、1 つは動的スコープを持ち、 other にはレキシカル スコープなどがあります)。