Free and bound variables in Lisp

September 23rd, 2007 at 6:55 am

In discussions of Lisp code, you will often see the terms free variable and bound variable used. Understanding these terms is essential in order to really grok how lexical scoping and closures work in Lisp.

Today, while watching one of the SICP video lectures (5.1a), I saw a great definition for these terms that I want to record here. A bound variable:

A variable, V, is “bound in an expression”, E, if the meaning of E is unchanged by the uniform replacement of a variable, W, not occurring in E, for every occurrence of V in E.

And a free variable:

A variable, V, is “free in an expression”, E, if the meaning of E is changed by the uniform of replacement of a variable, W, not occurring in E, for every occurrence of V in E.

Let’s look at an example:

(lambda (x) (* x 2))

In this expression, x is bound according to the definition, because of we change every occurrence of x by w, we get:

(lambda (w) (* w 2))

Which is essentially the same expression. On the other hand, consider:

(lambda (x) (* x y))

Here, x is still bound, but y is free. That is because if we change y to, say, z:

(lambda (x) (* x z))

We get an expression with a different meaning. To see an all-encompassing example, consider this snippet of code :

((lambda (x) (* x 2)) 6)
=> 12

((lambda (w) (* w 2)) 6)
=> 12

Nothing changes, really, because x (and now w) is bound in the expression. On the other hand:

(define y 5)
(define z 2)

((lambda (x) (* x y)) 9)
=> 45

((lambda (x) (* x z)) 9)
=> 18

Since y is free in the expression, substituting it for z changes the expression’s meaning.

Related posts:

  1. The parentheses of Lisp
  2. back to lisp
  3. Coding in C++, wishing it were Lisp (or Perl)
  4. SEO for Lisp’s sake (Lisp tutorial)
  5. Book review: “Successful Lisp” by David Lamkins

2 Responses to “Free and bound variables in Lisp”

  1. Chen YufeiNo Gravatar Says:

    I guess you may also be interested in the “Lambda calculus” entry in wikipedia. It contains some explanation on free and bound variables in lambda calculus.

  2. John MiddlemasNo Gravatar Says:

    A free variable is one that is not bound to a storage location.
    http://en.wiktionary.org/wiki/free_variable

    Not sure how your definition using lamba fits in with that? You don’t mention storage locations.