动态范围 returns 未定义的变量

Question

下面的代码，在动态范围假设下，会 return 错误。

(let ((f (lambda (g)
  (lambda (n)
    (if (zero? n)
     1
     (* n ((g g) (- n 1))))))))
 ((f f) 5))

我的答案是 0，因为：

 n*(n-1)*(n-2)*(n-3)*(n-3)*(n-4)*1;; since the call with n=0, n bound to 0
 0*0*0*0*1

我在这里错过了什么？

Answer 1

使用动态作用域，g 将是未定义的，因为第 6 行没有名为 g 的变量。

Answer 2

(define test
  (let ((x 10))
    (lambda () x)))

这里我们 return lambda 函数来自范围，其中 x 是局部变量。在词法作用域下，环境附加到创建的 lambda 函数。此环境由创建 lambda 函数时可用的自由变量之上的绑定变量组成——此处 x，绑定到 10。因此，当调用此 returned lambda 函数时, 它的 x 只能是 10.

在动态范围内，let 是死代码。创建的 lambda 函数不存储其词法环境，因此当它被调用时，x 将在实际 时间重新查找 的调用。那个叫 x 值 10 的变量到那时将不复存在。 lambda 查找的 x 将是您 x 在调用时绑定到的任何内容：

(let ((x 20))
  (test))
; ==> 20

当然还有：

(test); == ERROR: Unbound variable x

所以对于您的代码来说，这是同样的问题。无论 g 是什么时候 (lambda (n) ...) 被评估，创建 lambda 函数，当该 lambda 函数被 returned 时超出范围，因此当该 returned lambda 函数是被调用时，g 将被重新查找，并且将是 g 在调用时绑定到的任何内容，就像以前一样。为了使其在动态范围内工作，您可以这样做：

(let ((f (lambda (g n)
             (if (zero? n)
                 1
                 (* n (g g (- n 1)))))))
  (f f 5))

这里的区别是 g 永远不会超出范围。这适用于动态和词法范围。您可以像这样针对动态范围简化它：

(let ((f (lambda (n)                          ; ((lambda (f) (f 5))
             (if (zero? n)                    ;  (lambda (n)
                 1                            ;    (if (zero? n) 
                 (* n (f (- n 1)))))))        ;      1
  (f 5))                                      ;       (* n (f (- n 1))))))

在词法作用域中，(lambda (n) ...)中的f是未绑定变量，但在动态作用域中，f首先建立，调用后(f 5)仍然可用对于所有嵌套调用，(f 4)、(f 3) 等，直到 (lambda (f) (f 5)) 内的 (f 5) 的计算完成；只有这样 f 才会被取消、销毁，当 lambda 退出 return 时 (f 5) 的结果。

在 Paul Grahams nice wrap-up of McCarthys original lisp paper 中，他提到论文中存在错误。第一个高阶函数 maplist 将 x 作为列表参数的名称。在演示 diff 中，他向 maplist 传递了一个以 x 作为参数的函数。这两个在第一对之后发生碰撞，因此由于动态范围而不起作用。动态作用域极易出错，在所有全局变量都是动态的 Common Lisp 中，*earmuffs* 命名约定是必要的，可以避免无数小时找到改变函数的全局变量来执行与预期完全不同的事情。

动态范围 returns 未定义的变量

dynamic scope returns undefined var

scheme

programming-languages

dynamic-scope