评估器的数据导向实现 [SICP]

Data-directed implementation of an evaluator [SICP]

我正在解决 SICP 练习 4.3 它是关于编写一个数据导向的评估器(eval 过程)而不是书中 section 4.1.1 中介绍的那个。基本思想是根据每种类型的表达式而不是使用条件从table中获取eval使用的程序。书中介绍的eval程序的开头实现如下:

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        [...]

数据导向版本可以是:

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((get 'op (car exp)) exp env)
        [...]

其中除了self-evaluating?variable?之外的所有情况都将由get直接处理。此过程链接到具有所需过程(用 'op 标识)的 table 和 returns 与表达式类型 (car exp) 关联的过程。

我遇到的问题是有些程序只有一个参数 ((text-of-quotation exp)) 而其他程序使用两个 ((eval-assignment exp env)),所以一旦 (get 'op (car exp)) returns适当的程序,我无法获得正确数量的参数(我已经在 ((get 'op (car exp)) exp env).

中使用了两个参数

我在 scheme wiki (here) 上找到的一个解决方案执行以下操作来处理获取过程和参数:

((get 'op (car expr)) (get 'op (car expr) expr env)) 

但是,我完全不明白 (get 'op (car expr) expr env) 部分如何获得正确的参数以应用于 (get 'op (car expr))

如果有人能向我解释这个 scheme wiki 解决方案如何处理特定代码行的参数,我将不胜感激,因为它非常优雅地处理了我遇到的困难。

在我看来,scheme wiki 上的一些答案存在潜在问题。我认为最能回答您问题的解决方案是来自 Sphinxsky 的解决方案:

 (define (eval- exp- env) 
     (cond ((self-evaluating? exp-) exp-) 
         ((variable? exp-) (lookup-variable-value exp- env)) 
         (else 
             (let ((op (get 'eval (car exp-)))) 
                 (if op 
                     (op exp- env) 
                     (error "Unknown expression type -- EVAL" exp-)))))) 

首先,我们正在执行的 'operation' 是评估,因此 'eval 用于表示这一点(因为 table 也可以包含算术过程)。

(get 'eval (car exp-))

其中 (car exp-) 将指示需要计算的表达式类型(例如,quotedefinebegin、...)

代码检查对象(过程)是否被 returned 并使用 (op exp- env) 调用它,正如您所说的传递两个参数 exp-env

             ...
             (let ((op (get 'eval (car exp-)))) 
                 (if op 
                     (op exp- env) 
                     (error "Unknown expression type -- EVAL" exp-)))))) 

几乎所有的专业评价者都接受两个论点,引文可能是唯一的例外。但这可以通过让引号 'evaluator' 接受两个参数并简单地忽略第二个未使用的参数来处理。 Sphinxsky 通过安装一个带有两个参数的 lambda 来完成此操作,然后仅使用其中一个参数调用 text-of-quotation:

     (put 'eval 'quote 
         (lambda (exp- env) 
             (text-of-quotation exp-)))    

关于BE的回答,我觉得少了一对括号

(cond
  ...
  ((get 'op (car expr)) (get 'op (car expr) expr env))
  ...

应该是:

(cond
  ...                    v                  v          
  ((get 'op (car expr)) ((get 'op (car expr)) expr env))
  ...

如果 ((get 'op (car expr)) return 的第一次调用是一个值,那么我们评估 ((get 'op (car expr)) expr env) 这会导致重复查找,但我们知道它将 return 一个值所以:

((get 'op (car expr)) expr env)

变成:

(<the-evalutor> expr env)

双重查找并不理想,但练习 4.5 将展示如何避免这种情况。

阅读第 4 章和第 5 章的答案时,您可能需要谨慎一些。对于前面的大部分章节,人们将发布他们拥有的代码 运行,因此在某种程度上已经过测试(语法肯定是正确的)。但是,相当合理的是,并不是每个人都会花时间编写完整的评估器来 运行 并测试他们的代码,因此一些答案是 'pencil and paper' 代码。 Fwiw,我自己的解决方案是 github。我现在可能会做不同的事情,但确实如此 运行.