替代模型是否需要一個環境

Question

我正在爲Scheme編寫一個小型評估器。

我需要使用替代模型編寫評估程序，因此不會使用像set!這樣的分配。

但是由於我仍然需要在某個地方存儲原始程序和用戶變量，我需要一個環境嗎？如果是這樣，替代模型和環境模型有什麼區別？

謝謝。

Answer 1

否 - 對於基於替換的簡單評估程序，您需要而不是需要一個環境。這是因爲只要你有一個綁定（例如，當你執行一個函數調用），你立即用名稱替換該值，所以不需要保持名稱 - >值映射。實際上，您可以將環境視爲一種避免替換的開銷，方法是緩存並稍後執行它們。請參閱PLAI以瞭解此視圖的教科書 - 事實上，它從替換到替代緩存，並且僅在稍後纔將術語更改爲環境。

但請注意，使用set!的問題與所有這一切無關。當你考慮set!時，你首先需要清楚你所談論的set!的級別：如果它的語言是而不是實現本身，那麼可以添加給定的任何類型的可變值 - 例如，在Racket中，您可以使用boxes，這足以在語言中實現set!。這通常是在基於環境的評估程序中完成的，其中環境類型從映射名稱更改爲映射名稱到位置（實現爲框或類似的可變值）。但是這並不是必須的：您仍然可以通過基於替代的評估程序來執行此操作，其中這些框將成爲您要替換的值域的一部分。舉一個具體的例子，你可以用一個表達式開始喜歡（使用方案，如語言）：

(let ((x 1)) 
    (begin (set! x 2) 
     (set! x 3))) 

和而不是爲x代1你會分配一個盒子拿着1，那麼替代品相同框導致

(begin (set! #<box> 2) 
     (set! #<box> 3)) 

其中兩個#<box> ES是單個框。 （請注意，這不是我正在討論的實現代碼，而是您正在評估的語言中的表達式。）通常不會這樣做的原因是它可能會造成混淆 - 您需要將值表示爲框可以被替代，那些框不是源用戶程序的一部分，但它們是解釋器應該處理的值（例如，最後的#<box>是返回值 - 但是它是你想要返回的值，而不是盒子），並且您需要注意盒子的標識（例如，對於上面的兩個盒子而言，重要的是爲了解釋第一個set!在第二個盒子中可見）是相同的盒子。

因此，如果您剛剛瞭解如何撰寫口譯員，不建議您這樣做。如果是這種情況，那麼我建議你只看該教科書。

Answer 2

是的，你仍然需要一個環境，因爲就像你說你需要能夠存儲變量等。

替代模型是一種幫助您瞭解給定過程如何評估的方法。例如，您可以定義平方函數

(define (square x) (* x x))

隨着替代模式，如果你叫

(square 4) 

則替換4到x的每次出現在你的函數定義，以便

(* 4 4) => 16 

該環境用於顯示變量和狀態如何存儲在解釋器中。因此，簡而言之，替代模型用於幫助您評估程序，而使用環境來了解您的解釋程序如何記住用戶在使用解釋程序時可能定義的變量和定義。