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

Question

我正在尝试更好地了解自由变量和绑定变量。这是一个示例代码：

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

我看到这里的绑定变量是 guess 和 x，自由变量是 <、abs、- 和 [=16] =].如果我递归调用 what-kind-of-var? 会怎样？它会是一个绑定变量，因为它正在绑定自己吗？

谢谢！

Answer 1

guess和x是参数。当函数被应用时，它们最终被绑定（到各自的参数）。
<、abs、-，实际上是绑定到初始环境中的程序。所以它们不是自由变量。
square 将是自由变量，前提是 what-kind-of-var? 未在其范围内定义。（注意初始环境绑定sqr）
what-kind-of-var? 也不是未绑定的，即使它递归调用自身（假设递归在语言中正确实现）。 (define (f param) body)可以看做是(define f (lambda (param) body)

Answer 2

你需要读一本逻辑手册或lambda演算手册，里面有变量概念的起源。

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

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

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

Answer 3

它会在动态绑定下，但 Scheme 具有词法范围。

但实际上两者都不是。 "Free" 或 "bound" 来自 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? 是绑定在 Y 下的新 lambda 表达式中。它在嵌套的内部 lambda 中是自由的，但在外部 lambda 中是绑定的。

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

Will recursively-called variable be free or bound?

scope

scheme

racket

free-variable

bound-variable