2

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

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

更新：在搜索除数中查看下面的代码

(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 : 在口译中怎么样？

4

4 回答 4

2

它依赖于实现。它没有说明闭包应该有多少成本，但是由于 Scheme 是围绕闭包设计的，因此任何实现都应该大步前进以使闭包变得便宜。许多实现都会进行CPS 转换，并且会在每个评估操作中引入闭包。

有一种称为lambda 提升的编译器技术，其中通过将不在全局范围内的自由变量更改为有界变量并将过程从定义的过程中提升出来，将局部函数转换为全局函数。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:-prefixed 标识符都是唯一的，因此它不会与现有的全局绑定发生冲突。

于 2013-12-11T19:27:01.153 回答
1

不相干。

设计编程语言的一个重要方面通常是在一方面的效率和另一方面的表现力之间进行选择。在大多数情况下，这两个方面分别定义了低级和高级语言的特征。

Scheme 是 Lisp 语言家族中一种小巧但功能强大的高级语言。Scheme 最强大的特性之一是它的表现力和抽象能力。作为 Scheme 的程序员，您在过程中使用块结构，因为它封装了相关的行为并以结构化的方式解决您的问题，但您不考虑这种行为的低级属性，例如调用过程的运行时成本或分配列表. 这是使用高级语言（例如 Scheme）进行编程的一部分乐趣。

正如你所说：它很棒而且很有用，所以继续你的工作并创造一些美好的东西。在程序运行变得相当缓慢之前，我不会关心这些事情，而只会专注于更难的问题，例如在程序中定义概念和行为。

于 2013-12-11T14:15:14.747 回答
1

效率问题分解为编译器优化问题。improve通常，只要您有一个引用自由变量（例如 your ）的词法过程（例如您的过程），x就需要创建一个闭包。闭包有一个“环境”，必须分配它来存储所有自由变量。因此存在一些空间开销和一些时间开销（分配内存和填充内存）。

编译器优化在哪里发挥作用？当一个词法过程没有“转义”它的词法块时，比如你所有的词法块，那么编译器可以内联过程。在这种情况下，不需要创建带有其环境的闭包。

但是，重要的是，在日常使用中，您不必担心词汇程序的使用。

于 2013-12-11T16:25:04.360 回答
1

一言以蔽之：微不足道。使用嵌套函数而不是顶级定义函数不会对性能产生明显影响，我们使用嵌套函数（SICP术语中的“块结构”）是为了清晰和更好地构建过程，而不是为了提高效率：

这种定义的嵌套，称为块结构，基本上是最简单的名称打包问题的正确解决方案

根据定义的位置，查找函数所需的时间可能会略有不同，但这取决于解释器的实现细节。不值得担心。

于 2013-12-11T13:42:54.187 回答