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

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

更新:看看下面的代码，在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:除法？和最小除数不是必需的，只是为了澄清。效率和成本如何？ 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)发生冲突。