方案：为什么内部定义比外部定义快？

我尝试运行下面的程序

(define (odd-internal x)
  (define (even x)
    (if (zero? x)
        #t
        (odd-internal (sub1 x))))
  (if (zero? x)
      #f
      (even (sub1 x))))

(define (odd-external x)
  (if (zero? x)
      #f
      (even (sub1 x))))

(define (even x)
  (if (zero? x)
      #t
      (odd-external (sub1 x))))

(begin (display "Using internal definition\n")
       (time (odd-internal 40000000)))

(begin (display "Using external definition\n")
       (time (odd-external 40000000)))

这是 Racket 中的结果

Using internal definition
cpu time: 166 real time: 165 gc time: 0
#f
Using external definition
cpu time: 196 real time: 196 gc time: 0
#f

在那里您可以看到使用内部定义要快得多。我尝试在 Chez Scheme 上运行，结果类似。这是为什么？

我很惊讶这是一个差异，所以根据 Lexis 答案的评论，我在每个文件中分割了两个版本internal.rkt and external.rkt并以这种方式编译和反编译它们：

raco make external.rkt
raco decompile compiled/external_rkt.zo

这比查看宏步进器中完全扩展的程序更进一步。它看起来非常不适合人类阅读，所以我用最重要的部分原封不动地对它进行了美化：

(define (odd-external x1)
  (if (zero? x1)
      '#f
      (let ((x2 (sub1 x1)))
        (if (zero? x2)
            '#t
            (let ((x3 (sub1 x2)))
              (if (zero? x3)
                  '#f
                  (let ((x4 (sub1 x3)))
                    (if (zero? x4)
                        '#t
                        (let ((x5 (sub1 x4)))
                          (if (zero? x5) '#f (even (sub1 x5))))))))))))

(define (even x1)
  (if (zero? x1)
       '#t
       (let ((x2 (sub1 x1)))
         (if (zero? x2)
           '#f
           (let ((x3 (sub1 x2)))
             (if (zero? x3)
               '#t
               (let ((x4 (sub1 x3)))
                 (if (zero? x4)
                   '#f
                   (let ((x5 (sub1 x4)))
                     (if (zero? x5)
                       '#t
                       (let ((x6 (sub1 x5)))
                         (if (zero? x6)
                           '#f
                           (let ((x7 (sub1 x6)))
                             (if (zero? x7)
                               '#t
                               (odd-external (sub1 x7))))))))))))))))

这里没什么特别的。它将循环展开一定次数并不断折叠。请注意，我们仍然存在相互递归，并且展开次数为 5 次和 7 次。常数甚至被折叠，所以它取代了我的电话(even 399999995)所以编译器也运行了代码 5 轮并放弃了。有趣的是内部版本：

(define (odd-internal x1)
  (if (zero? x1)
      '#f
      (let ((x2 (sub1 x1)))
        (if (zero? x2)
            '#t
            (let ((x3 (sub1 x2)))
              (if (zero? x3)
                  '#f
                  (let ((x4 (sub1 x3)))
                    (if (zero? x4)
                        '#t
                        (let ((x5 (sub1 x4)))
                          (if (zero? x5)
                              '#f
                              (let ((x6 (sub1 x5)))
                                (if (zero? x6)
                                    '#t
                                    (let ((x7 (sub1 x6)))
                                      (if (zero? x7)
                                          '#f
                                          (let ((x8 (sub1 x7)))
                                            (if (zero? x8)
                                                '#t
                                                (odd-internal
                                                 (sub1 x8))))))))))))))))))

它不再是相互递归，因为它在 8 次后调用了自己。每轮进行 8 轮，而另一个版本进行 7 轮，然后是 5 轮。在两轮中，内部版本完成了 16 轮，而另一个版本完成了 12 轮。内部版本的初始调用是(odd-internal '399999992)所以编译器做了8轮才放弃。

我猜想反编译器级别的函数内部的代码是开放编码的，并且每个步骤的代码都非常便宜，这使得调用次数成为速度提高 25% 的原因。毕竟每次递归多 4 次就多 25%，这与计算时间的差异一致。这是基于观察的推测，因此 Lexi 对此发表评论会很有趣。