CODEWITHSUNDEEP
scopeschemeracketfree-variablebound-variable
Isaac
Isaac

Reputation: 321

Will recursively-called variable be free or bound?

I am trying to have a better understanding about free and bound variables. Here is an example code:

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

I see that bound variables here would be guess and x, and free variables <, abs, -, and square. What if I called what-kind-of-var? recursively? Would it be a bound variable because it is binding itself?

Thanks!

Upvotes: 2

Views: 262

Answers (2)

Will Ness
Will Ness

Reputation: 71065

It would, under dynamic binding, but Scheme has lexical scoping.

But actually it is neither. "Free" or "bound" comes from lambda calculus. what-kind-of-var? is a top-level variable, naming that lambda expression,

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

but in lambda calculus expressions cannot be named. The only way to call it recursively in lambda calculus is to use Y combinator:

((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)

and now of course what-kind-of-var? is bound inside that new lambda expression under Y. It's free in the nested, inner lambda, but bound in the outer one.

Upvotes: 0

Atharva Shukla
Atharva Shukla

Reputation: 2137

  • guess and x are parameters. They're eventually bound (to respective arguments) when the function is applied.

  • <, abs, -, are actually bound to procedures in the initial environment. So they're not free variables.

  • square would be the free variable, subject to the fact that what-kind-of-var? is not defined in its scope. (note that sqr is bound in the initial environment).

  • what-kind-of-var? is also not unbound, even if it calls itself recursively (assuming recursion is implemented properly in the language). (define (f param) body) can be seen as (define f (lambda (param) body)

Upvotes: 0

Related Questions