scheme - 方案语言中嵌套函数的效率和成本如何

Question

在SICP ，我学会了使用函数，它很棒而且很有用。但是我对嵌套函数的成本感到困惑，如下面的代码:

(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
     (if (good-enough? guess)
       guess
       (sqrt-iter (improve guess))))
 (sqrt-iter 1.0))

定义了三个child-function，效率和成本如何？如果我使用更多功能这样调用？

更新:查看下面的代码，在 Searching for divisors 中

(define (smallest-divisor n)
  (find-divisor n 2))
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
  (= (remainder b a) 0))

(define (prime? n)
  (= n (smallest-divisor n)))

Q1:divides? 和smallest-divisor 不是必需的，只是为了说明。效率和成本如何？ Scheme 编译器是否针对这种情况进行了优化。我觉得我应该学点编译器的知识。(͡๏̯͡๏)

q2:在解释器中怎么样？

Answer 1

它依赖于实现。它没有说明闭包应该有多少成本，但是由于 Scheme 是围绕闭包设计的，因此任何实现都应该努力使闭包便宜。许多实现确实 CPS conversions并且每个评估操作都会引入一个闭包。

有一种编译技术叫做lambda lifting通过将不在全局范围内的自由变量更改为有界变量并将过程从定义它的过程中提取出来，局部函数被转换为全局函数。SICP 代码可能会被翻译成类似这样的东西:

(define (lift:good-enough? x guess)
  (< (abs (- (square guess) x)) 0.001))

(define (lift:improve x guess)
  (average guess (/ x guess)))

(define (lift:sqrt-iter x guess)
  (if (lift:good-enough? x guess)
      guess
      (lift:sqrt-iter (lift:improve x guess))))

(define (sqrt x)  
  (lift:sqrt-iter x 1.0))

其中所有 lift:- 前缀标识符都是唯一的，因此它不会与现有的全局绑定(bind)冲突。