環境の関連サブセットのみをevalに渡すSchemeインタプリタ

Question

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

はたとえば、次の式を考えてみます。

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

我々は(eval '(+ x 3) env)評価

は、環境がバインディング { x : 1, y : 2 }が含まれています。環境には { x : 1 }しか含まれないような効率的な通訳をどのように書くのでしょうか？

もちろん、一般的に値が使用されるかどうかはわかりません。私が探しているのは、おそらくコンパイラの最適化テクニックに基づく、粗い構文アプローチです。無関係の値を除外するために、それぞれの再帰呼び出しで環境の多くを移動するよりも効率的です。eval

（背景：私のquest memoizingのSchemeインタプリタを書くこと。）

Answer 1

確かに：その部分式のfree variablesを計算し、何とかASTにそれを添付して、すべての部分式のために。そして、再帰的呼び出しであるevalを呼び出すたびに、評価しようとしている式の空き変数だけに環境を制限します。

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

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

xの値が含まれますlambda発現させるための閉鎖ではなく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の詳細については、「スペースの安全」を参照してください。

Answer 2

一般的なコンパイラ最適化dead code eliminationはここでトリックを行います。 Yは使用されないので、Yバインディングは単に削除することができます。

効率的な通訳を作成する方法の一般的な質問に答えるために、ASTを作成し、部分的な解釈などのさまざまな最適化手法を使用して複数回にわたって渡して、できるだけ事前計算して簡略化することをお勧めします。