呼叫請求/按名稱呼叫Lisp解釋器策略的開銷

Question

我已經爲詞法範圍的'純Lisp'（不是set!）部分完成了解釋器，它使用了需求呼叫評估模型直到使用簡單緩存進行名稱調用，解釋器自然使用基於環境的評估模型。

評估lambda抽象的標準方法，如從構造一個新的環境中，從正式的對象和評估抽象的環境，以及簡單地將參數的評估放置在它們自己的環境中。然後在新環境中評估抽象的主體將不起作用，因爲這意味着按值調用的語義。

我對這個問題的解決方案是用'查找函數'替換'環境'的想法，只需要一個符號作爲參數，併產生一個相關的數據。這可以很容易地從一個環境中做出。 Lambda應用程序是通過再次使用由定義所在的環境和參數所在的環境創建的查找函數來評估主體來完成的。只有在需要時纔會對其進行懶惰評估。

我想知道這個模型的開銷是多少，爲每個應用程序生成這些查找的代價是多少，這些查找的代碼非常大。我知道Scheme中的lambda應用程序和創建相當便宜，許多消息來源提倡儘可能廣泛地使用它們來保持代碼的可讀性，即使在很多情況下它們會有輕微的開銷。但是，隨着lambda應用程序在任何lisp中無處不在，我不知道使用潛在不同模型可以節省多少性能。我試着在google上搜索這個，但是我發現的所有需求呼叫解釋器的模型都更加尷尬，但通常是爲了適應set!。

我的代碼的一些相關作品：

使用查找功能的評價：

; evaluates a datum using a lookup 
; lookup is a function which takes a symbol as an argument and produces the value 
; some sorts of more powerful environment 
; if lookup is a standard environment, treats it as such 
(define (eval-datum! d lookup) 
    (cond 
    ((quoted? d) (dequote d)) ; if quoted, just dequote 
    ((hastype d symbol-type) ; symbols ... 
    (if (procedure? lookup) ; checks if it's an environment or a lookup function 
     (lookup d) 
     (lookup-symbol d lookup))) 
    ((hastype d pair-type) (eval-pair! d lookup)) ; function application 
    (else d))) ; rest is considered self-evaluating 

和產生更高級的查找功能。這尤其令我感到擔憂，儘管它是尾遞歸的，並且使用非常便宜的eq?和null?比較，它看起來不如在環境列表上簡單地使用assq那樣有效，並且有些時候甚至沒有隨機訪問這些擔心一點點。

; extends a lookup for use in a lambda abstraction 
; the inner environment is where the lambda is defined 
; the outer environment where it is applied 
; params can be either a pair or a symbol 
; params automatically tries to match the argument's pattern 
(define (extend-lookup! params args inner-env outer-env) 
    (lambda (s) 
    (let checkparams ((params params) (args args)) 
     (cond 
     ((eq? s params) (datum args)) ; for an improper list or a single symbol, simply turn the arglist into an evaluable list 
     ((null? params) (lookup-symbol s inner-env)) ; if the number of paramatres are exhausted, simply use the inner-env 
     ((eq? s (car params)) ; in case of a formal parametre match ... 
       (refeval! args 0 outer-env)) ; evaluate the needed argument and return it 
     (else (checkparams (cdr params) (cdr args))))))) ; repeat for the next paramatre 

應該清楚的是，評估的工作原理是一個簡單的還原系統的長期，在列表計算表達式時，只是替換他們與他們的結果，引述他們只要結果不被視爲自我評估。這是可能的，因爲它是一個純粹的功能性脣齒相依。它還一次捕獲緩存和大部分垃圾收集。

我應該補充一點，我總是對開銷和複雜性理論有很差的概念。對於那些說'如果你想要表現，爲什麼你要在Lisp中做你的解釋器？'，這只是對一般結構的一個測試，看看它是否有效，我很快就會用C語言重寫它。

啊，我甚至不能提交這個，因爲標籤'需求呼叫'不存在，很有希望的開始。

Answer 1

'你'可能做的另一件事是簡單地標記每個單獨的數據與一個可以從數據結構中檢索的環境，它可能看起來是詳盡的，但最終所有需要標記的東西來想到它是列表和一個非常特殊的情況，lambda抽象的主體只包含一個符號。對於「您的」模型中的其他數據，其評估與其環境無關。

這也解決了一個懶惰的單元格和列表，只是傳遞到程序中的其他地方的主要問題。

因此，假設一個列表本身帶有一個環境標記，那麼只要評估環境就可以提取環境。