performance - 按需调用/按名称调用 Lisp 解释器策略的开销

Question

我有一个部分完成的解释器，用于词法范围的“纯 Lisp”(没有 set!)，它使用按需调用评估模型，归结为按名称调用简单的缓存，解释器自然会使用基于环境的评估模型。

评估 lambda 抽象的标准方法，例如，从形式参数和评估抽象的环境构建一个新环境，并将参数的评估简单地放在它们自己的环境中。然后在新环境中评估抽象的主体是行不通的，因为这意味着按值调用语义。

我对这个问题的解决方案是在需要的地方用“查找函数”替换“环境”的概念，它只接受一个符号作为参数，并产生一个关联的数据。可以很容易地从环境中制作。 Lambda 应用程序只是通过使用查找函数再次评估主体来完成，该查找函数由定义所在的环境和参数所在的环境组成。它会延迟评估它们，并且仅在需要时才对其进行评估。

但我想知道的是这个模型的开销是多少，为每个应用程序生成这些查找的成本是多少，这些查找的代码非常大。我知道在 Scheme 中应用和创建 lambda 是相当便宜的，许多消息来源提倡广泛使用它们来保持代码的可读性，即使在很多情况下它们会有轻微的开销。但由于 lambda 应用程序在任何 lisp 中无处不在，我想知道使用可能不同的模型可以节省多少性能。我试着在谷歌上搜索这个，但我发现所有用于按需调用解释器的模型都更加笨拙，但通常是为了适应 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。它还一次性捕获缓存和大部分垃圾收集。

我应该补充一点，我一直对开销和复杂性理论的概念很差。对于那些说“如果你想要性能，你为什么要用 Lisp 制作解释器？”的人，这只是对一般结构的测试，看看它是否有效，我将很快用 C 语言重写它。

啊，一开始我什至无法提交这个，因为标签“按需调用”还不存在，很有希望的开始。

Answer 1

“你”可能做的另一件事是简单地用一个环境标记每个单独的数据，可以在数据结构中从中检索它，它可能看起来详尽无遗，但最终所有需要标记的都来了把它想象成列表和一个非常特殊的情况，即 lambda 抽象的主体只包含一个符号。对于“您的”模型中的其他数据，其评估与其环境无关。

这也解决了惰性 cons 单元和列表的一个主要问题，这些单元和列表只是传递到程序中的其他地方。

因此假设列表本身标有环境，您可以在评估它时提取环境。