6

我正在尝试解决计算机编程的结构和解释问题 4.4 的最后一部分；任务是实现或作为句法转换。只定义了基本句法形式；引用、if、begin、cond、define、apply 和 lambda。

(或 ab ... c) 等于第一个真值，如果没有值为真，则为假。

我想要处理的方法是将例如（或 abc）转换为

(if a a (if b b (if c c false)))

这样做的问题是 a、b 和 c 将被评估两次，如果其中任何一个有副作用，这可能会给出不正确的结果。所以我想要一个像让

(let ((syma a)) 
     (if syma syma (let ((symb b)) 
                        (if symb symb (let ((symc c))
                                           (if (symc symc false)) )) )) )

这又可以通过 lambda 实现，如练习 4.6 中所示。现在的问题是确定符号 syma、symb 和 symc；例如，如果表达式 b 包含对变量 syma 的引用，那么 let 将破坏绑定。因此，我们必须认为 sema 是不在 b 或 c 中的符号。

现在我们遇到了障碍；我能从这个洞中看到的唯一方法是让符号不能在传递给 eval 的任何表达式中出现。（这包括可能由其他句法转换传入的符号）。

但是，由于我无法直接访问表达式中的环境，因此我不确定是否有任何合理的方法可以生成此类符号；我认为 Common Lisp 为此目的具有 gensym 功能（这意味着元循环解释器中的粘滞状态，危及任何并发使用）。

我错过了什么吗？有没有办法实现或不使用 gensym？我知道 Scheme 有它自己的 hygenic 宏系统，但我还没有弄清楚它是如何工作的，我不确定它下面是否有一个 gensym。

4

2 回答 2

6

我认为您可能想要在这里做的是转换为不嵌套各种形式的评估的句法扩展。您可以这样做，例如，将每个表单包装为一个lambda函数，然后您使用的方法就可以了。例如，你可以做类似的事情

(or a b c)

进入

(let ((l1 (lambda () a))
      (l2 (lambda () b))
      (l3 (lambda () c)))
  (let ((v1 (l1)))
    (if v1 v1
      (let ((v2 (l2)))
        (if v2 v2
          (let ((v3 (l3)))
            (if v3 v3
              false)))))))

（实际上，lambda函数调用的求值仍然嵌套在ifs 和lets 中，但是函数的定义位于这样的位置，这样在嵌套的 s 和s 中lambda调用它们不会对捕获的绑定造成任何困难。）没有解决如何获取变量–<code>l3 和–<code>v3 的问题，但这并不重要，它们都不在函数体的范围内，所以你不要无需担心它们是否出现在体内。事实上，您可以对所有结果使用相同的变量：ifletl1v1lambda

(let ((l1 (lambda () a))
      (l2 (lambda () b))
      (l3 (lambda () c)))
  (let ((v (l1)))
    (if v v
      (let ((v (l2)))
        (if v v
          (let ((v (l3)))
            (if v v
              false)))))))

此时，您实际上只是在对更一般的形式进行循环展开，例如：

(define (functional-or . functions)
  (if (null? functions)
      false
      (let ((v ((first functions))))
        (if v v
            (functional-or (rest functions))))))

的扩展(or a b c)很简单

(functional-or (lambda () a) (lambda () b) (lambda () c))

这种方法也用于回答Why (apply and '(1 2 3)) doesn't work while (and 1 2 3) works in R5RS? . 而这一切都不需要任何GENSYMing！

于 2013-08-17T11:47:24.453 回答
1

在 SICP 中，您有两种实现或的方式。一种将它们作为微不足道的特殊形式处理，另一种作为派生表达式处理。我不确定他们是否真的认为你会认为这是一个问题，但你可以通过实现gensym或更改variable?以及如何制作这样的派生变量来做到这一点：

;; a unique tag to identify special variables
(define id (vector 'id))

;; a way to make such variable
(define (make-var x)
  (list id x))

;; redefine variable? to handle macro-variables
(define (variable? exp) 
  (or (symbol? exp)
      (tagged-list? exp id)))


;; makes combinations so that you don't evaluate
;; every part twice in case of side effects (set!)
(define (or->combination terms)
  (if (null? terms)
      'false
      (let ((tmp (make-var 'tmp)))
        (list (make-lambda (list tmp)
                           (list (make-if tmp 
                                    tmp 
                                    (or->combination (cdr terms)))))
              (car terms)))))


;; My original version
;; This might not be good since it uses backquotes not introduced 
;; until chapter 5 and uses features from exercise 4.6
;; Though, might be easier to read for some so I'll leave it.
(define (or->combination terms)
  (if (null? terms)
      'false
      (let ((tmp (make-var 'tmp)))
        `(let ((,tmp ,(car terms)))
           (if ,tmp
               ,tmp
               ,(or->combination (cdr terms)))))))

它的工作原理是make-var每次调用它时都会创建一个新列表，即使使用相同的参数也是如此。由于它具有id第一个元素，因此variable?将其标识为变量。因为它是一个列表，它只会在变量查找中匹配eq?它是否是同一个列表，所以几个嵌套的 or->combination tmp-vars 都将被视为不同，lookup-variable-value因为(eq? (list) (list)) => #f特殊变量是列表，它们永远不会隐藏代码中的任何符号.

这受到eiod和 Al Petrofsky 的影响，它以类似的方式实现语法规则。除非您将其他实现视为破坏者，否则您应该阅读它。

于 2013-08-17T11:48:42.287 回答