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

Will recursively-called variable be free or bound?

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

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

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

谢谢!

  • guessx是参数。当函数被应用时,它们最终被绑定(到各自的参数)。

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

  • square 将是自由变量,前提是 what-kind-of-var? 未在其范围内定义。 (注意初始环境绑定sqr

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

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

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

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

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

它会在动态绑定下,但 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 中是绑定的。