2

スタックとポインターを使用して AST をたどって評価する、非再帰的なスキーム インタープリターを設計しようとしました。

純粋なプロシージャ コールだけに取り組む必要がある場合は、問題ありません。ただし、マクロが登場すると、不規則な構文により、非再帰ルーチンを作成するのが難しくなります。(異なるセマンティクスが混在しているため) さらに悪いことに、組み込みマクロ (if、conf let など)を考慮すると、非再帰的アプローチは非常に複雑に見えます。

非再帰インタープリターの実装に関する良い提案はありますか? またはその上の資料はありますか？私は一生懸命グーグルで検索しましたが、何も見つかりませんでした。

そして、主流のSchemeインタプリタはこの種のアプローチを使用するのだろうか. 多分私は再帰で書くことができ、それは非難されません。

4

2 に答える 2

6

通常の r5rs スキームでは、マクロは AST を再配置するための単なる DSL です。それらは純粋に構文レベルで動作し、インタープリターから分離する必要があります。

R6RS や CL などでは、マクロは実際に計算を行うことができます。つまり、インタープリターを 2 回実行する必要があります。1 回はマクロを展開し、もう 1 回は結果の AST を評価します。

たとえば、このコードが与えられた場合

 (let ((x 5))
   (if (= x 5)
       (display "Woohoo")
       (error)))

AST を終了する最初のフェーズでマクロ エキスパンダーを実行する必要があります。

 ((lambda (x)
    (cond
      ((= x 5) (display "Woohoo"))
      (else (error)))) 5)

これを行うと、no codeと評価されます。単に AST を再配置します。次に、インタープリターがそれを実行するときに、マクロが存在することを知る必要さえありません。

したがって、最終的なスキーム インタープリターは次のようになります。

Parse File
   |
   |
   |
Expand All Macros
   |
   |
   |
Optimize/Black Magic
   |
   |
   |
Optional ByteCode compilation or similar IL
   |
   |
Evaluate
   |
   |
Profit
于 2013-07-29T13:56:38.553 に答える
4

私のSchemeコンパイラを研究している間、私はコンパイルに関連するあらゆる種類の古い問題について多くの論文を読みました. マクロに関連し、@jozefg の実際の解釈とマクロ espansion を分離する素晴らしいイラストは、Al Petrofskyによって書かれた Alexpander でした。彼はまた、1 つの define で Eval を作成しました。これは、構文規則を備えた優れたインタープリターです。

私は以前、Brainf*ck で動作する Lisp1 インタープリターを作成しました。set-car へのセル アドレスが交互になるスタックがありました。結果と評価される式。

Eval は次のようなものです。

(pop_stack register1) ; expression
(while-not-zero register1
   ... do computation
   (pop_stack register2) ; return address
   (open-cons register2) ; opens location
   (set-car register1)   ; sets value 
   (pop_stack register1)) ; next job

マクロ (flambda) を含む標準の McCharty LISP1 をサポートしています。

(cons 'a 'b) のような単純な式は、次のように、while ループで 6 ラウンドを使用します。

  1. (cons 'a 'b)
  2. cons => プロシージャ:cons
  3. (事前適用手順:cons 'a 'b)
  4. 'a => a
  5. 'b => b
  6. (適用手順:cons 'a 'b)

このため、すべてのキーワードの名前を変更できました。例えば。これは機能します：

(let ((mylambda lambda))
   (mylambda (x) (cons '1 x)))
于 2013-07-29T17:00:24.643 に答える