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

Question

我有一个部分完成的解释器,用于词法范围的"纯Lisp"(no set!),它使用按需调用的评估模型,该模型通过简单的缓存进行逐个调用,解释器自然地使用基于环境的评估模型.

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

我对这个问题的解决方案是用"查找函数"替换需要"环境"的概念,它只是将符号作为参数,并生成相关的数据.这可以很容易地从一个环境.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 单元和列表的主要问题，这些单元和列表只是传递到程序中的其他位置。

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