布尔运算符尾调用优化？

Question

在学习 Racket 和开始编程时，我用两种不同的方式定义 ormap：

(define (or-map proc lst)
  (cond
    [(null? lst) #false]
    [(proc (car lst)) #true]
    [else (or-map proc (cdr lst))]))


(define (or-map proc lst)
  (if (null? lst)
      #false
      (or (proc (car lst)) ; <-- this one
          (or-map proc (cdr lst)))))

想到以下问题：

第二个tail-call优化了吗？我不确定注释行是否被丢弃（或者 (or ...) 堆叠它的参数），因为如果它是 #true 函数调用结束，如果它是 #false它应该与 (or ...) 语句的进一步评估无关。

所以我运行进行了以下测试并查看了任务管理器的内存使用情况：

(define (test)
  (or #f
      (test)))

(test)

内存保持不变。所以我想我可以得出结论 (or ...*) 得到了尾调用优化？我假设 (and ...*) 和其他布尔运算符保持正确，但是当我在 中更改 or (test)到也不内存满了。

总而言之，我

到目前为止我的结论有没有错误？
nor-test 是怎么回事？
正确地假设我对 or-map 的两个定义在性能方面是等效的，或者一个比另一个更可取？
（在这种情况下我对任务管理器的使用甚至是合法的吗？当内存填满 Whosebug 时我在那里看到的现象或其暗示是什么？）

Answer 1

鉴于您的用户名是 Tracer，您可能会觉得很有趣，您可以使用 racket/trace 来检查它。 :)

首先是一个您希望使用而不是尾部消除的函数示例：

#lang racket

(define (tail-call xs [results '()])
  (match xs
    [(list) results]
    [(cons x xs) (tail-call xs (cons x results))]))

(define (no-tail-call xs)
  (match xs
    [(list) (list)]
    [(cons x xs) (cons x (no-tail-call xs))]))

我们可以 trace 他们并在调用深度中看到这一点：

(require racket/trace)
(trace tail-call no-tail-call)

(tail-call '(1 2 3 4 5))
;; >(tail-call '(1 2 3 4 5))
;; >(tail-call '(2 3 4 5) '(1))
;; >(tail-call '(3 4 5) '(2 1))
;; >(tail-call '(4 5) '(3 2 1))
;; >(tail-call '(5) '(4 3 2 1))
;; >(tail-call '() '(5 4 3 2 1))
;; <'(5 4 3 2 1)
;; '(5 4 3 2 1)

(no-tail-call '(1 2 3 4 5))
;; >(no-tail-call '(1 2 3 4 5))
;; > (no-tail-call '(2 3 4 5))
;; > >(no-tail-call '(3 4 5))
;; > > (no-tail-call '(4 5))
;; > > >(no-tail-call '(5))
;; > > > (no-tail-call '())
;; < < < '()
;; < < <'(5)
;; < < '(4 5)
;; < <'(3 4 5)
;; < '(2 3 4 5)
;; <'(1 2 3 4 5)
;; '(1 2 3 4 5)

接下来让我们对 or-map 的两个定义执行此操作。我们看到两者的形状相同，平坦：

(define (or-map/v1 proc lst)
  (cond
    [(null? lst) #false]
    [(proc (car lst)) #true]
    [else (or-map/v1 proc (cdr lst))]))

(define (or-map/v2 proc lst)
  (if (null? lst)
      #false
      (or (proc (car lst)) ; <-- this one
          (or-map/v2 proc (cdr lst)))))

(trace or-map/v1 or-map/v2)

(or-map/v1 even? '(1 1 1 2))
;; >(or-map/v1 #<procedure:even?> '(1 1 1 2))
;; >(or-map/v1 #<procedure:even?> '(1 1 2))
;; >(or-map/v1 #<procedure:even?> '(1 2))
;; >(or-map/v1 #<procedure:even?> '(2))
;; <#t
;; #t

(or-map/v2 even? '(1 1 1 2))
;; >(or-map/v2 #<procedure:even?> '(1 1 1 2))
;; >(or-map/v2 #<procedure:even?> '(1 1 2))
;; >(or-map/v2 #<procedure:even?> '(1 2))
;; >(or-map/v2 #<procedure:even?> '(2))
;; <#t
;; #t

Answer 2

and 和 or 会评估它们在尾部位置的最后一个表达式。这是由 Scheme 标准保证的；参见，例如 http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-14.html#node_sec_11.20.

另一方面，

nor 必须否定 or 的结果。根据定义，这意味着 or 的结果不会在尾部位置求值，因为它必须在返回给调用者之前传递给 not。

Answer 3

您在问：

rightfully assume both of my definitions of or-map are equivalent performance wise, or is one preferable over the other?

但请注意，您的第一个函数不等同于第二个函数（不会产生相同的结果）。如果您通过以下方式调用它们，您可以验证这一点：

(or-map (lambda (x) (member x '(1 2 3))) '(1 2 a))

原因是在第一个函数中 return #true 当 (proc (car lst)) return 与 #false 不同时，函数应该 return (proc (car lst)) 的值。所以“正确”的版本（即相当于球拍的版本ormap）只是第二个。

布尔运算符尾调用优化？

Boolean operators tail-call optimized?

stack-overflow

tail-call-optimization

boolean-operations

racket