为什么定义语法或在方案中需要考虑三个条件？

Question

我正在阅读方案编程语言,在第3章中,本书使用define-syntax来定义or和过程,它说下面的定义或者是不正确的:

(define-syntax or ; incorrect!
  (syntax-rules ()
    [(_) #f]
    [(_ e1 e2 ...)
     (let ([t e1])
       (if t t (or e2 ...)))]))

而正确的定义是:

(define-syntax or
  (syntax-rules ()
    [(_) #f]
    [(_ e) e]
    [(_ e1 e2 e3 ...)
     (let ([t e1])
       (if t t (or e2 e3 ...)))]))

为什么正确的定义需要三个条件？我运行了很多测试,这两个定义产生了相同的结果.怎么能告诉我为什么第一个定义是错的？

Answer 1

让我们考虑一下这本书的提示.

首先我们定义自己的版本or:

(define-syntax my-or ; incorrect!
  (syntax-rules ()
    [(_) #f]
    [(_ e1 e2 ...)
     (let ([t e1])
      (if t t (my-or e2 ...)))]))

然后我们看一下提示中的表达式.

   (letrec ([even?
              (lambda (x)
                (my-or (= x 0)
                       (odd? (- x 1))))]
             [odd?
              (lambda (x)
                (and (not (= x 0))
                     (even? (- x 1))))])      
      (list (even? 20) (odd? 20)))

让我们来看看扩展(我编辑完全扩展一点):

(letrec ([even? (lambda (x)
                  (let ([t (= x 0)])
                    (if t t (let ([t (odd? (- x 1))])
                              (if t t #f)))))]
         [odd? (lambda (x) (if (not (= x 0)) (even? (- x 1)) #f))])
  (list (even? 20) (odd? 20)))

这里的问题是对odd?in 的调用(let ([t (odd? (- x 1))]) ...) 不在尾部位置.对于每个循环,let表达式将分配一个新变量(在堆栈或其他地方),最终我们会遇到内存问题.

简而言之:语义or是在(or e1 ... en)最后一个表达式en中处于尾部位置.如果我们使用my-or宏的简单版本,那么

(my-or e1)

扩展到

(let ([t e1])
  (if t t #f))]))

并且表达式e1不在输出中的尾部位置.