What are Free and Bound variables?

Question

I've been programming for a long time (too long, actually), but I'm really struggling to get a handle on the terms "Free Variables" and "Bound Variables".

Most of the "explanations" I've found online start by talking about topics like Lambda calculus and Formal logic, or Axiomatic Semantics. which makes me want to reach for my revolver.

Can someone explain these two terms, ideally from an implementation perspective. Can they exist in compiled languages, and what low-level code do they translate to?

Answer 1

A free variable is a variable used in some function that its value depends on the context where the function is invoked, called or used. For example, in math terms, z is a free variable because is not bounded to any parameter. x is a bounded variable:

f(x) = x * z 

In programming languages terms, a free variable is determined dynamically at run time searching the name of the variable backwards on the function call stack.

A bounded variable evaluation does not depend on the context of the function call. This is the most common modern programming languages variable type. Local variables, global variables and parameters are all bounded variables.

A free variable is somewhat similar to the "pass by name" convention of some ancient programming languages.

Let's say you have a function f that just prints some variable:

def f():     print(X) 

This is Python. While X is not a local variable, its value follows the Python convention: it searches upwards on the chain of the blocks where the function is defined until it reaches the top level module.

Since in Python the value of X is determined by the function declaration context, we say that X is a bounded variable.

Hypothetically, if X were a free variable, this should print 10:

X = 2  def f():     print(X)  def g():     # X is a local variable to g, shadowing the global X     X = 10     f() 

In Python, this code prints 2 because both X variables are bounded. The local X variable on g is bounded as a local variable, and the one on f is bounded to the global X.

Implementation

The implementation of a programming language with free variables needs to take care the context on where each function is called, and for every free variable use some reflection to find which variable to use.

The value of a free variable can not be generally determined at compile time, since is heavily determined by the run time flow and the call stack.

Answer 2

Whether a variable is free or bound is relative; it depends on the fragment of code you are looking at.

In this fragment, x is bound:

function(x) {return x + x;}; 

And here, x occurs free:

return x + x; 

In other words, freeness is a property of the context. You don't say "x is a free variable" or "x is a bound variable," but instead identify the context you are talking about: "x is free in the expression E." For this reason, the same variable x can be either free or bound depending on which fragment of code you are talking about. If the fragment contains the variable's binding site (for example, it is listed in the function arguments) then it is bound, if not, it is free.

Where the free/bound distinction is important from an implementation perspective is when you are implementing how variable substitution works (e.g. what happens when you apply arguments to a function.) Consider the evaluation steps:

(function(x) {return x + x;})(3); => 3 + 3 => 6 

This works fine because x is free in the body of the function. If x was bound in the body of the function, however, our evaluation would need to be careful:

(function(x) {return (function(x){return x * 2;})(x + x);})(3); => (function(x){return x * 2;})(3 + 3); // careful to leave this x alone for now! => (function(x){return x * 2;})(6); => 6 * 2 => 12 

If our implementation didn't check for bound occurrences, it could have replaced the bound x for 3 and given us the wrong answer:

(function(x) {return (function(x){return x * 2;})(x + x);})(3); => (function(x){return 3 * 2;})(3 + 3); // Bad! We substituted for a bound x! => (function(x){return 3 * 2;})(6); => 3 * 2 => 6 

Also, it should be clarified that free vs. bound is a property of the syntax (i.e. the code itself), not a property of how a the code is evaluated at run-time. vz0 talks about dynamically scoped variables, which are somewhat related to, but not synonymous with, free variables. As vz0 correctly describes, dynamic variable scope is a language feature that allows expressions that contains free variables to be evaluated by looking at the run-time call-stack to find the value of a variable that shares the same name. However, It still makes sense to talk about free occurrences of variables in languages that don't allow dynamic scope: you would just get an error (like "x is not defined") if you were to try to evaluate an such expression in these languages.

And I can't restrain myself: I hope one day you can find the strength to put your revolvers away when people mention lambda calculus! Lambda calculus is a good tool for thinking about variables and bindings because it is an extremely minimal programming language that supports variables and substitution and nothing else. Real-world programming languages contain a lot of other junk (like dynamic scope, for example) that obscures the essence.