functional-programming - 为什么define-syntax of or in scheme需要考虑三个条件？

Question

我正在阅读方案编程语言，在第 3 章中，该书使用 define-syntax 来定义 or 和 and 过程，它说 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 ...)))]))

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

标签： functional-programmingschemelispracket

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不在输出中的尾部位置。