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.