SICP:可以或者在lisp中定义为没有gensym的语法转换？

Question

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

(或ab ... c)等于第一个真值,如果没有值,则为false.

我想要接近它的方法是将例如(或abc)转换为

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

这个问题是a,b和c会被评估两次,如果它们中的任何一个有副作用,可能会得到不正确的结果.所以我想要像let这样的东西

(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将破坏绑定.因此,我们必须让syma是不在b或c中的符号.

现在我们遇到了障碍; 我能看出来这个洞的唯一方式是有符号不能一直在传递给eval任何表情.(这包括可能已被其他语法转换传入的符号).

但是因为我不能直接访问表达式,所以我不确定是否有合理的方法来生成这样的符号; 我认为Common Lisp具有用于此目的的函数gensym(这意味着在metacircular解释器中保持状态,危及任何并发使用).

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

Answer 1

我认为你可能想要做的是转换为语法扩展,其中各种形式的评估不是嵌套的.你可以这样做,例如,将每个表单包装为一个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中,但是lambda函数的定义位于这样的位置,即在嵌套的ifs和lets中调用它们不会对捕获的绑定造成任何困难.)没有解决你如何获得变量的问题l1- l3而且v1- v3但这并不重要,它们都不在lambda函数体的范围内,所以你不必担心它们是否出现在身体与否.实际上,您可以对所有结果使用相同的变量:

(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))

这种方法也适用于一个答案,以为什么(申请和"(1 2 3))不同时(1 2 3)工作在R5RS工作？.而且这一切都不需要GENSYM!