Names, bindings, scope and environments

Every language lets programmers give names to things: variables, functions, types, modules, fields. A surprising amount of language design is about deciding what a name refers to at each point in a program. This lesson defines bindings and their timing, distinguishes scope from lifetime, compares lexical and dynamic scoping, and introduces the environment model that interpreters use to implement them. Along the way we build an interpreter for a small functional language with first-class functions and closures, the core of every interpreter in the rest of the course.

CMPUT-274 lesson 2 used closures as a programming tool and showed Python's late-binding surprise in passing. Here we look underneath: what a closure is as a data structure, why late binding happens, and how one line in an interpreter decides between two quite different scoping rules.

Bindings and binding times

A binding is an association between a name and something it stands for: a value, a memory location, a type, a function. The binding time is when that association is made. Some bindings happen when the language is designed (the meaning of + or the keyword while), some when the language is implemented (the size of an int in C), some at compile time (the type of a declared variable in Java), some at link time (which library function a call reaches), some at load time (the address of a global variable) and some at run time (the value of a local variable, or which method a virtual call reaches).

Early binding generally means efficiency and early error detection; late binding means flexibility. A C compiler that knows every type can generate fast code and reject type errors before the program runs. Python binds types to values at run time, so the same function works for integers, strings and user classes, at the cost of run-time checks. Much of the history of language design is a negotiation over which bindings to make early and which to leave late.

Scope and lifetime

The scope of a binding is the region of program text in which the name refers to that binding. The lifetime of an object is the period of execution during which it exists. These are different. A static local variable in C has local scope (visible only inside its function) but a lifetime as long as the program. A heap object in Java may outlive every variable that ever named it until the garbage collector reclaims it. A dangling pointer is a name whose scope is still active while the object it refers to has reached the end of its lifetime, a classic source of bugs in C and C++.

An occurrence of a name is bound if it refers to a binding introduced within the expression being considered, and free otherwise. In fun x -> x + y, the x in the body is bound by the parameter and y is free; its meaning must come from the surrounding context. Inner bindings shadow outer ones with the same name. Computing free variables is a basic operation in compilers, used for closure conversion, for renaming in the lambda calculus (lesson 5) and for checking that every name is declared.

# Free and bound variables, computed over a small abstract syntax.
#   e ::= n | x | ("+", e, e) | ("let", x, e, e) | ("fun", x, e) | ("app", e, e)
def free(e):
    if isinstance(e, int): return set()
    if isinstance(e, str): return {e}
    tag = e[0]
    if tag == "+":   return free(e[1]) | free(e[2])
    if tag == "let": return free(e[2]) | (free(e[3]) - {e[1]})   # x is bound in the body only
    if tag == "fun": return free(e[2]) - {e[1]}
    if tag == "app": return free(e[1]) | free(e[2])

examples = {
    "x + y":                         ("+", "x", "y"),
    "let x = 1 in x + y":            ("let", "x", 1, ("+", "x", "y")),
    "fun x -> x + y":                ("fun", "x", ("+", "x", "y")),
    "let x = x in x":                ("let", "x", "x", "x"),
    "(fun x -> x) z":                ("app", ("fun", "x", "x"), "z"),
}
for text, e in examples.items():
    print(f"{text:28} free = {sorted(free(e))}")

x + y                        free = ['x', 'y']
let x = 1 in x + y           free = ['y']
fun x -> x + y               free = ['y']
let x = x in x               free = ['x']
(fun x -> x) z               free = ['z']

Lexical and dynamic scope

When a function body mentions a free variable, where does its value come from? Under lexical scope, also called static scope, a free variable refers to the binding in the text surrounding the function's definition. Under dynamic scope, it refers to the most recent binding still active at run time, which usually means the binding in effect where the function is called. Almost every modern language uses lexical scope, because a reader can determine what a name means by looking at the program text. Early Lisps used dynamic scope, Emacs Lisp used it by default until lexical binding became available in version 24 (2012), and Unix shells still use it.

The difference shows up when a function is called somewhere other than where it was defined. In the program below, addx is defined where x is 10 but called where x is 1000. Lexical scope gives 15; dynamic scope gives 1005. In the interpreter, the only difference between the two is one line: when applying a function, extend the environment saved in the closure (lexical) or the caller's current environment (dynamic).

# An interpreter for a small functional language, with a switch between lexical and dynamic scope.
#   e ::= n | x | (op, e, e) | ("if0", e, e, e) | ("let", x, e, e) | ("fun", x, e) | ("app", e, e)
class Env:
    """An environment is a chain of frames; lookup walks outward."""
    def __init__(self, frame, parent=None): self.frame, self.parent = frame, parent
    def lookup(self, x):
        env = self
        while env is not None:
            if x in env.frame: return env.frame[x]
            env = env.parent
        raise NameError(f"unbound variable {x}")
    def extend(self, x, v): return Env({x: v}, self)

class Closure:
    def __init__(self, param, body, env): self.param, self.body, self.env = param, body, env

def ev(e, env, dynamic=False):
    if isinstance(e, int): return e
    if isinstance(e, str): return env.lookup(e)
    tag = e[0]
    if tag in ("+", "-", "*"):
        a, b = ev(e[1], env, dynamic), ev(e[2], env, dynamic)
        return a + b if tag == "+" else a - b if tag == "-" else a * b
    if tag == "if0":
        return ev(e[2], env, dynamic) if ev(e[1], env, dynamic) == 0 else ev(e[3], env, dynamic)
    if tag == "let":
        return ev(e[3], env.extend(e[1], ev(e[2], env, dynamic)), dynamic)
    if tag == "fun":
        return Closure(e[1], e[2], env)          # capture the defining environment
    if tag == "app":
        f, arg = ev(e[1], env, dynamic), ev(e[2], env, dynamic)
        base = env if dynamic else f.env         # the one line that decides the scoping rule
        return ev(f.body, base.extend(f.param, arg), dynamic)

# let x = 10 in
#   let addx = fun y -> y + x in
#     let x = 1000 in
#       addx 5
prog = ("let", "x", 10,
        ("let", "addx", ("fun", "y", ("+", "y", "x")),
         ("let", "x", 1000,
          ("app", "addx", 5))))
print("lexical scope:", ev(prog, Env({})))
print("dynamic scope:", ev(prog, Env({}), dynamic=True))

lexical scope: 15
dynamic scope: 1005

show() { echo "inside show, x = $x"; }
outer() { local x="set by outer"; show; }
x="global"
show
outer

$ bash scope.sh
inside show, x = global
inside show, x = set by outer

Dynamic scope has one genuine use: passing context implicitly through many layers of calls, such as the current output stream or a debugging flag. Lexically scoped languages provide controlled versions of this idea instead of making every variable dynamic: Common Lisp's special variables, Racket's parameters, Scala's implicits and Python's contextvars module all give dynamic binding to a few chosen names while everything else stays lexical.

Environments and closures

An environment maps names to values. Interpreters usually represent it as a chain of frames: each frame holds the bindings introduced by one let, one function call or one block, and points to its enclosing frame. Looking up a name walks outward along the chain until the name is found. A closure is a pair of a function's code and the environment in which the function was defined. Closures are what make first-class functions work under lexical scope: when the function is later called, its body runs in an extension of the saved environment, so free variables mean what they meant at the definition.

Closures also explain Python's late-binding surprise. A closure captures the variable, meaning the binding in its environment, not a snapshot of the value. A list comprehension creates one binding for its loop variable, which all the lambdas share, so when they run after the loop they all see its final value. Binding the value as a default argument, or creating a new scope with a factory function, gives each closure its own binding. JavaScript faced the same problem with var, which is scoped to the whole function; the let keyword, added in 2015, creates a fresh binding on each loop iteration.

# Python closures capture variables, not values: the classic late-binding surprise.
fs = [lambda: i for i in range(3)]
print("late binding :", [f() for f in fs])

# Fix 1: bind the current value as a default argument (evaluated at definition time).
fs = [lambda i=i: i for i in range(3)]
print("default arg  :", [f() for f in fs])

# Fix 2: a factory function creates a fresh scope per call.
def make(i):
    return lambda: i
print("factory      :", [make(i)() for i in range(3)])

# nonlocal lets an inner function rebind a variable in an enclosing function's scope.
def counter():
    n = 0
    def tick():
        nonlocal n
        n += 1
        return n
    return tick
t = counter()
print("counter      :", t(), t(), t())

late binding : [2, 2, 2]
default arg  : [0, 1, 2]
factory      : [0, 1, 2]
counter      : 1 2 3

// var is function-scoped; let is block-scoped, with a fresh binding per loop iteration.
const withVar = [], withLet = [];
for (var i = 0; i < 3; i++) withVar.push(() => i);
for (let j = 0; j < 3; j++) withLet.push(() => j);
console.log("var:", withVar.map(f => f()));
console.log("let:", withLet.map(f => f()));

var: [ 3, 3, 3 ]
let: [ 0, 1, 2 ]

Python's scoping rules are lexical, with a twist. Names are looked up in the LEGB order: local, enclosing function, global and built-in. Assignment inside a function creates a local binding unless the name is declared global or nonlocal, which is why forgetting nonlocal in a counter function raises an error about using a local variable before assignment. Python also decides a name's scope for the whole function body at compile time, so a name assigned anywhere in a function is local everywhere in it.

Recursion and letrec

A function that calls itself needs its own name to be in scope inside its body. With a plain let, the function expression is evaluated in the outer environment, before the name exists, so a recursive call fails. A recursive binding form, often called letrec, creates the new frame first and then evaluates the function in an environment that includes that frame, so the closure points to the very frame that holds it. The resulting cycle in the data structure is what implements recursion. Python's def and JavaScript's function declarations behave like letrec; ML and OCaml make the distinction explicit with let and let rec.

# Recursion needs a binding that refers to itself.  letrec ties a knot in the environment.
class Env:
    def __init__(self, frame, parent=None): self.frame, self.parent = frame, parent
    def lookup(self, x):
        e = self
        while e:
            if x in e.frame: return e.frame[x]
            e = e.parent
        raise NameError(x)
class Closure:
    def __init__(self, p, b, env): self.p, self.b, self.env = p, b, env

def ev(e, env):
    if isinstance(e, int): return e
    if isinstance(e, str): return env.lookup(e)
    t = e[0]
    if t in ("-", "*"):
        a, b = ev(e[1], env), ev(e[2], env)
        return a - b if t == "-" else a * b
    if t == "if0": return ev(e[2], env) if ev(e[1], env) == 0 else ev(e[3], env)
    if t == "fun": return Closure(e[1], e[2], env)
    if t == "app":
        f = ev(e[1], env); return ev(f.b, Env({f.p: ev(e[2], env)}, f.env))
    if t == "let": return ev(e[3], Env({e[1]: ev(e[2], env)}, env))
    if t == "letrec":
        frame = {}; new = Env(frame, env)
        frame[e[1]] = ev(e[2], new)          # the closure captures the frame it is stored in
        return ev(e[3], new)

fact = ("fun", "n", ("if0", "n", 1, ("*", "n", ("app", "fact", ("-", "n", 1)))))
print("letrec fact 6 =", ev(("letrec", "fact", fact, ("app", "fact", 6)), Env({})))
try:
    ev(("let", "fact", fact, ("app", "fact", 6)), Env({}))
except NameError as err:
    print("plain let fails: unbound variable", err)

letrec fact 6 = 720
plain let fails: unbound variable fact

Where frames live: stack or heap

In C, a function's local variables live in a stack frame that disappears when the function returns. That is cheap, but it makes returning a closure impossible, because the closure would refer to a frame that no longer exists. This is the classic upward funarg problem. Languages with first-class closures solve it by allocating captured variables on the heap, where they live as long as some closure needs them. Compilers usually do this selectively: variables that no closure captures stay on the stack, and only captured ones are moved, a transformation called closure conversion. Rust takes a third route, making the programmer state whether a closure borrows or moves its captured variables, so the compiler can check lifetimes at compile time.

Worked examples