## Free and bound variables in Lisp

September 23rd, 2007 at 6:55 amIn 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

unchangedby 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

changedby 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:

September 24th, 2007 at 06:29

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.

July 7th, 2009 at 13:03

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.