stack-overflow - bool 运算符尾调用优化？

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

想到了以下问题:

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

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

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

(test)

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

总而言之，我呢

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

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

我们可以跟踪它们并在调用深度中看到这一点:

(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