Naming

In static scoping, it is always possible to determine the scope of a variable from the program's AST. Because scopes can be determined from syntax, static scoping is also called lexical scoping.

We've seen static scoping before: lambda parameters in FL are statically scoped. Here's another example, written in C:

void func(int x) {
  // in scope: x
  int y = x + 1;
  // in scope: x, y
  for (int i = y; i > 0; i--) {
    x++; // in scope: x, y, i
  }
  // in scope: x, y
  return x;
}

The scope of local variables and function arguments in C extends from the declaration of the variable to the end of the block. This is clearly a syntactic property of the program. Lexical scopes can usually be nested, and when looking up an identifier, the most enclosing scope that contains a binding of that identifier is chosen.

Many languages have multiple forms of static scope. For example, C offers block scope for local variables, file scope for global variables, function scope for labels (that is, the targets for goto), and function prototype scope (for the variable names inside function prototypes). The scoping rules for C have actually evolved over time; older versions of C did not introduce new scopes for the bodies of loops and conditionals. Notice how different scopes are used for different entities: function scope for labels vs block scope for variables.

In contrast, in dynamic scoping the scope of a variable can depend on the execution path of the program. Dynamic scope is much less common than static scope in modern programming languages, although it was used more extensively in older languages. In particular, early Lisp languages used dynamic scoping by default. Some lisps, like Emacs Lisp, still default to dynamic scope.

Here's an example from the Emacs manual:

(defvar x -99)    ; x receives an initial value of -99.

(defun getx () x) ; x is used free in this function.

(let ((x 1))      ; x is dynamically bound.
  (getx))
⇒ 1

;; After the let form finishes, x reverts to its previous value, which is -99.
(getx)
⇒ -99

As this example shows, looking up x from within getx can return different values depending on where it is called. If getx is called from a context that binds x, then getx sees that value of that binding. Otherwise, it sees the initial value.

One way to think about dynamic scope is that when we look up a variable, we walk up the call stack until we find a frame that contains a binding for that variable.

We often distinguish between first and second class entities in a language. The idea of a first class citizen comes from Strachey, and it refers to entities that act like values (Christopher S. Strachey, 2000). Strachey uses Algol as an example; in Algol, numbers are first class, but procedures are not. This is because numbers have the properties of values: they can be assigned to variables, passed to functions, and they have operations defined on them, and they can appear as the result of evaluating an expression. Procedures cannot be assigned to variables, passed to other procedures, or appear as the result of evaluation; they can only be called and must be called directly by name.

Modern languages have tended to make more entities first class, since this makes the language more expressive. First class functions are common; some languages offer more exotic constructs like first class types.

For example, in C we can use the same name (x) to refer to a variable, a struct field, and a type:

#include <stdio.h>

typedef struct {
  int x;
} x;

int f(x x) {
  return x.x + x.x;
}

int main() {
  x x = { 2 };
  printf("%d\n", f(x));
}

4

All the references to x appear in overlapping scopes; C can disambiguate them because they appear in different syntactic positions. Types and struct fields are not first class in C—they cannot be passed as arguments or stored in variables. The contents of a field can be, but the field itself cannot. We can't write a function that takes a list of struct fields and returns a new struct. When a variable and a type or field name can never appear in the same syntactic position, there's no need to use a shared namespace for them, and we can give the programmer more freedom to choose names by separating their namespaces.

Modern languages have tended to make more entities first class than historical languages. For example, even C treats functions as first class objects (this is why we can't rename f to x in our example).

The number of namespaces was a source of significant debate in the Lisp community. Traditionally, Lisp had separate namespaces for functions and variables. Scheme introduced several new ideas, including lexical scoping, and also eliminated the split between functions and variables. Some of these ideas, like lexical scoping, were added to Common Lisp, but the single namespace was not.

It's interesting to look back at the debate about this choice, because it's a great example of a programming language design dilemma that appears to have an obvious answer today, but was much less clear at the time.

A Lisp language with a single namespace is called a Lisp-1; two namespaces is a Lisp-2. Gabriel & Pitman lay out the arguments for and against Lisp-1 in "Technical Issues of Separation in Function Cells and Value Cells".