2

環境の関連するサブセットのみを再帰eval呼び出しに渡すSchemeインタープリターを構築する効率的な方法はありますか?

たとえば、次の式を考えてみましょう。

(let ([x 1]
      [y 2])
  (+ x 3))

評価する(eval '(+ x 3) env)と、環境にはバインディングが含まれます{ x : 1, y : 2 }。環境にのみが含まれるように、効率的なインタープリターをどのように作成します{ x : 1 }か?

もちろん、一般に、値が使用されるかどうかを事前に知ることはできません。私が探しているのは、おそらくコンパイラの最適化手法に基づく粗い構文アプローチです。これは、再帰呼び出しのたびに環境の大部分を調べて、eval無関係な値を除外するよりも効率的です。

(背景:メモ化する Scheme インタプリタを書きたいという私の探求。)

4

2 に答える 2

3

確かに: すべての部分式に対して、その部分式の自由変数を計算し、それを何らかの方法で AST にアタッチします。次に、 を再帰的に呼び出すたびにeval、環境を評価しようとしている式の自由変数だけに制限します。

コンパイラは通常、lambda境界でこれを行い、不要な値への参照を保持するクロージャーを作成しないようにします。これらの参照を保持すると、オブジェクトが GC されるのを防ぐ可能性があるためです。つまり、次のプログラムでは

(let ([x 1]
      [y 2])
  (lambda (z)  ;; free vars = {x}
    (+ x z))

式のクロージャにlambdaは の値が含まれますが、 は含まれxませんy。しかし、一般的に、それを行うと、非常に単純な「フレームのリスト」環境表現を使用できないことを意味します。それを平坦化する必要があるかもしれません (または、少なくともコピーしてプルーニングします)。

一部の実装では、ローカル変数 (クロージャーによって保持されていない変数、レジスターまたはスタック上にあると予想される種類) が使用されなくなったときに、特に末尾以外の呼び出しの前にそれらをゼロにします。あれは、

(let ([x some-big-object])
  (f (g x) long-running-expression-not-involving-x))

の低レベルの同等物に変換される可能性があります

(let ([x some-big-object])
  (let ([tmp1 (g x)])
    (set! x #f)
    (let ([tmp2 long-running-expression-not-involving-x])
      (f tmp1 tmp2))))

理由は同じです。参照をできるだけ早く削除すると、オブジェクトをより早く解放できる可能性があるということです。(これは、閉鎖の場合と同様に、キャプチャされた継続によって保持されないことも意味します。) 詳細については、Google の「安全なスペース」を参照してください。

于 2012-05-03T22:24:31.530 に答える
0

ここでは、デッド コードの除去という一般的なコンパイラの最適化がうまくいきます。Y は使用されないため、Y バインドは単純に削除できます。

効率的なインタープリターを作成する方法に関する一般的な質問に答えるために、AST を作成し、部分解釈などのさまざまな最適化手法を使用して AST を複数回渡し、事前に計算して可能な限り単純化することをお勧めします。

于 2012-05-06T18:03:11.540 に答える