3

我正在研究计算机程序的结构和实现一书，其中一章中有一些代码用于计算数字的阶乘：

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
    (if (> counter max-count)
        product
        (fact-iter (* counter product)
                   (+ counter 1)
                   max-count)))

在本书的前面，我了解到我可以在另一个函数中内联定义函数，如下所示：

(define (factorial n)
  (define (fact-iter product counter max-count)
    (if (> counter max-count)
        product
        (fact-iter (* counter product)
                   (+ counter 1)
                   max-count)))
  (fact-iter 1 1 n))

我知道使用第二种方法fact-iter将无法在范围之外访问，factorial但我想知道当我运行第二个版本时会发生什么factorial？

定义了符号的新本地绑定fact-iter并创建了新函数，或者此绑定仅在程序编译时创建一次？

我来自java背景，这对我来说还不清楚。

4

2 回答 2

4

它取决于方案的实施（在SICP的后续章节中讨论的策略）。从概念上讲，一个新函数会在每次调用中定义/编译factorial它的第二个定义。但是，一个好的编译器可以转换此代码，使其更像您的第一个定义。

由于这种结构在 Scheme 中非常常见（编写循环的惯用方式是命名let结构，它也动态定义函数），Scheme 编译器应该非常擅长进行这种优化。实际上，您的示例对于优化器来说很容易处理，因为内部函数的定义实际上并不依赖于外部函数绑定的任何变量，因此它几乎可以按原样取出（可能只需要更改名称） .

于 2013-03-06T14:59:31.083 回答
2

每次调用阶乘时都不会编译一个新函数。函数形式上是一段代码和一个环境；每次通话都会改变环境。例如：

(define (find x l)
  (define (equal-to-x y) (equal? x y))
  ....)

在上面，每次调用 'find' 都会产生一个新函数 'equal-to-x'。“equal-to-x”函数的“环境”引用了在另一个范围内定义的变量“x”。但是，一个合适的编译器可能会注意到，equal-to-x 永远不会返回或绑定到范围外的变量，因此编译器可能会“内联”代码 - 因此不需要新函数（代码 + 环境）。

在您的代码中，内部定义的 fact-iter（您的第二种情况）的自由引用（+、* 和 >）都是全局定义的，并且不会返回（或绑定）fact-iter 函数。因此，一个足够好的编译器会内联它。

这是一个不太好的编译器的例子。您可以在“find”的反汇编中看到创建了一个函数/闭包（代码+环境），并且在“ex”的反汇编中使用了环境引用（以获取“x”）。

=> (define find (lambda (x l) 
     (define ex (lambda (y) (= x y))) 
     (ex (car l))))
(=>)
=> (sys:disassemble find)
;; Address  :  0x00327e90
;; Label    :  find
;; Constants:
;;         0:  #t
;;         1:  #[<code> ex 1]
;;         2:  (<cons> 6)
;; Code     :
;;       0-1:  explode 2
;;       2-3:  check 2
;;       4-5:  get-loc 0
;;       6-8:  closure 1, 1
;;      9-10:  get-loc 2
;;     11-13:  get-loc-res 1, 2
;;        14:  cons$car
;;     15-16:  call-tail-check 1
;;          :
;; Address  :  0x0031fb40
;; Label    :  ex
;; Constants:
;;         0:  #t
;;         1:  (<number> 1 142 42 154 158)
;; Code     :
;;       0-1:  explode 1
;;       2-3:  check 1
;;       4-6:  get-env-res 0, 1
;;       7-9:  get-loc-res 0, 1
;;        10:  number$=
;;     11-12:  return 1
;;          :
;; Env      :
#[<function> find 2]
于 2013-03-06T15:15:27.163 回答