scope - 递归调用的变量是自由的还是绑定的？

Question

我试图更好地理解自由和绑定变量。这是一个示例代码：

(define (what-kind-of-var? guess x)
    (< (abs (- (square guess) x))
        0.001))

我看到这里的绑定变量是guessandx和自由变量<, abs, -, and square。如果我what-kind-of-var?递归调用怎么办？它会是一个绑定变量，因为它本身就是绑定的吗？

谢谢！

Answer 1

• guess是x参数。当函数被应用时，它们最终被绑定（到各自的参数）。

• <, abs, -, 实际上绑定到初始环境中的过程。所以它们不是自由变量。

• squarewhat-kind-of-var?将是自由变量，受制于未在其范围内定义的事实。（注意sqr在初始环境中绑定）。

• what-kind-of-var?也不是未绑定的，即使它递归地调用自己（假设递归在语言中正确实现）。(define (f param) body)可以看作(define f (lambda (param) body)

Answer 2

它会在动态绑定下，但 Scheme 有词法作用域。

但实际上两者都不是。“自由”或“绑定”来自 lambda 演算。what-kind-of-var?是一个顶级变量，命名该 lambda 表达式，

(define what-kind-of-var? 
  (lambda (guess x)                        ;; this
     (< (abs (- (square guess) x))
         0.001)))

但在 lambda 演算中，表达式不能命名。在 lambda 演算中递归调用它的唯一方法是使用Y组合器：

((Y (lambda (what-kind-of-var?)                ;; outer
      (lambda (guess x)                            ;; inner
         (if (< (abs (- (square guess) x))
                0.001)
           guess
           (what-kind-of-var? (+ 1 guess) x)))))
  4 25)

现在当然what-kind-of-var? 是绑定在 . 下的新 lambda 表达式中Y。它在嵌套的内部 lambda 中是免费的，但在外部 lambda 中是绑定的。

Answer 3

您需要阅读逻辑或 lambda 演算手册，这是变量概念的起源。

当一个变量在函数内部并且该函数将该变量作为参数时，无论该函数是否递归，它都是绑定的。

绑定的概念意味着分配了一个内存位置，变量符号表示该位置。并非每个绑定位置都可以通过变量访问。

在自由变量的情况下，有很多方法可以将它绑定到某个东西（在 C 语言中，一些自由变量受链接过程的约束，而有些则永远不会绑定）。在 Lisp 中，可以通过多种方式绑定自由变量——动态绑定、静态/范围绑定，或者在lisp_N中，N > 2有很多不同的方式来绑定变量。但是无论变量的实现是什么，这个概念的起源都来自数学逻辑。