1

我对在 Scheme 中定义多个可以相互调用的词法范围函数感到好奇。在 SICP 工作时，我使用块结构生成了以下函数来解决练习 1.8（使用牛顿法计算立方根）：

(define (cbrt x)
  (define (good-enough? guess prev-guess)
    (< (/ (abs (- guess prev-guess))
          guess)
       0.001))
  (define (improve guess)
    (/ (+ (/ x (square guess))
          (* 2 guess))
       3))
  (define (cbrt-iter guess prev-guess)
    (if (good-enough? guess prev-guess)
        guess
        (cbrt-iter (improve guess)
                   guess)))
  (cbrt-iter 1.0 0.0))

这很好用，但它让我想知道 Scheme（也许还有 Common Lisp）如何使用词法作用域和let表单来处理相同的场景。我尝试使用let以下 kludgy 代码来实现它：

(define (cbrt x)
  (let ((calc-cbrt
         (lambda (guess prev-guess)
           (let ((good-enough?
                  (lambda (guess prev-guess)
                    (< (/ (abs (- guess prev-guess))
                          guess)
                       0.001))))
             (good-enough? guess prev-guess))
           (let ((improve
                  (lambda (guess)
                    (/ (+ (/ x (square guess))
                          (* 2 guess))
                       3))))
             (improve guess))
           (let ((cbrt-iter
                  (lambda (guess prev-guess)
                    (if (good-enough? guess prev-guess)
                        guess
                        (cbrt-iter (improve guess)
                                   guess)))))
             (cbrt-iter 1.0 0.0)))))
    (calc-cbrt 1.0 0.0)))

我在下面看到的问题是cbrt-iter尝试调用该good-enough?过程时。由于该good-enough?过程仅在第一个嵌套 let块的范围内是本地的，cbrt-iter因此无法访问它。似乎可以通过将cbrt-iter函数嵌套在 的let中来解决good-enough，但这似乎也很笨拙和尴尬。

define在这种情况下，有什么不同的形式？表单是否define扩展到lambda表达式而不是“让 lambda”表单（我记得在 Little Schemer 书中使用表单做了类似的事情((lambda (x) x x) (lambda (y) ...))，但我不确定这将如何工作）。此外，作为比较，Common Lisp 如何处理这种情况——是否可以使用词法范围defun的 's ？

4

1 回答 1

1

首先，你不需要引入一个新的过程calc-cbrt——你可以直接调用calc-iter。

其次，和的含义define大相径庭let。 Define 将定义安装到本地范围中，如您的示例中所示。然而，let表达式只是表达式的语法糖lambda（详见 SICP 1.3 节）。结果（正如您提到的），声明的变量 via(let (<decl1> ...) <body>)仅在<body>. 因此，您的模式(let <decls1> <body1>) (let <decls2> <body2>) ...不起作用，因为没有一个定义将“幸存”以在其他范围内看到。

所以，我们应该这样写：

(define (cbrt x)
   (let ((good-enough? (lambda ...))
         (improve (lambda ...))
         (cbrt-iter (lambda ...)))
     (cbrt-iter 1.0 0.0)))

现在，至少，调用cbrt-iter可以看到cbrt-iter.

但是还是有问题。当我们评估 时，我们评估where(cbrt-iter 1.0 0.0)的主体并取值 1.0 和 0.0。但是，在 的主体中，变量和不在范围内。cbrt-iterguessprev-guesscbrt-iterimprovegood-enough?

您可能很想使用嵌套let的 s，这通常是一个不错的选择：

(define (cbrt x)
   (let ((good-enough? (lambda ...))
         (improve (lambda ...)))
     (let ((cbrt-iter (lambda ...)))
       (cbrt-iter 1.0 0.0))))

问题是 cbrt-iter 需要调用自己，但直到 inner 的主体才在范围内let！

这里的解决方案是使用letrec，这类似于let但使新绑定在所有声明以及正文中可见：

(define (cbrt x)
   (let ((good-enough? (lambda ...))
         (improve (lambda ...)))
     (letrec ((cbrt-iter (lambda ...)))
       (cbrt-iter 1.0 0.0))))

我们甚至可以letrec用来创建相互递归的过程，就像我们可以使用define.

不幸的是，我需要一些时间来解释如何letrec以及define实际工作，但这是秘密：它们都在内部使用突变来在环境数据结构中创建循环，允许递归。（还有一种方法可以使用 only 创建递归lambda，称为Y 组合器，但它相当复杂且效率低下。）

幸运的是，所有这些秘密都将在第 3 章和第 4 章中揭晓！

从另一个角度来看，你可以看看布朗大学的在线 PL 课程，它基本上直接进入了这个主题（虽然它省略了define），但我发现 SICP 更擅长强迫你理解所创建的有时复杂的环境结构。

于 2012-10-31T01:33:16.833 回答