This all started with a simple question about the R programming language: is R lexically or dynamically scoped?

To answer that question, we need to understand what scope is, along with lexical scope and dynamic scope.

In this blog post, I’d like to explain the differences between lexical scope and dynamic scope, and also explore some of the history behind those ideas. In a subsequent post, I’ll discuss scoping in R and why it can be confusing.

What is scope?

Scope refers to the places in a program where a variable is visible and can be referenced.

An interesting situation is when a function has free variables. Consider the example below:

1
2
3
4
5
6
7

x <- 1
f <- function(a) x + a
g <- function() {
  x <- 2
  f(0)
}
g() # what does this return?

On line 1, we create a mapping for x with value 1. On line 2, we define a function f whose body uses the parameter a, but also the free variable x. On line 3, we define a function g, whose body creates a new mapping for x with value 2, and then calls f(0). (Note that line 4 does not update the mapping created on line 1.) Finally, on line 7, we call g().

What value does g return when it is called? What mapping does the free variable x on line 2 refer to? Does it refer to the mapping on line 1 that was visible when f was defined? Or does it refer to the mapping on line 4 that was created just before f was called?

Lexical scoping

Under lexical scoping (also known as static scoping), the scope of a variable is determined by the lexical (i.e., textual) structure of a program.

In the example above, the definition of x on line 1 creates a scope that starts after its definition and extends into the bodies of f and g. However, the second definition of x on line 4 creates a new scope that (1) shadows the previous definition of x, and (2) does not extend into the call f(0) on line 5. Looking at this from another direction, the use of x on line 2 is within the scope created by the definition on line 1, and thus refers to that definition.

Therefore, under lexical scoping, the example program returns 1.

Most programming languages we use today are lexically scoped. Intuitively, a human (or compiler) can determine the scope of a variable by just examining the source code of a program. In other words, a compiler can determine which definition each variable refers to—but it may not be able to determine the values of each variable.

Dynamic scoping

Under dynamic scoping, a variable is bound to the most recent value assigned to that variable, i.e., the most recent assignment during the program’s execution.

In the example above, the free variable x in the body of f is evaluated when f(0) is called on line 5. At that point (during program execution), the most recent assignment was on line 4.

Therefore, under dynamic scoping, the example program returns 2.

Dynamically scoped programming languages include bash, LaTeX, and the original version of Lisp. Emacs Lisp is dynamically scoped, but allows the programmer to select lexical scoping. Conversely, Perl and Common Lisp are lexically scoped by default, but allow the programmer to select dynamic scoping.

(Edited 2020/08/13: As of Emacs 27.1, “lexical binding is now used by default when evaluating interactive Elisp.” Thanks to Artem Pelenitsyn for bringing this to my attention.)

Now for a digression

These are the definitions I learned from my classes and textbooks, and should be similar to other definitions and explanations you might find online.

However, it took me many drafts and attempts before arriving at the current version. I had difficulty writing an explanation that I was satisfied with—a definition that was not circular, did not appeal to some intuition or familiarity, and did not conflate terms. Even some of the resources I consulted had these issues.¹

I am much happier with my current version, but it still bothers me slightly. If lexical scope and dynamic scope are related concepts, then why are the definitions so different? Why does the definition for dynamic scope not mention scope at all? If scope is about “where a variable is visible,” and that definition is with respect to a variable definition, then why do so many explanations and examples define lexical and dynamic scope in terms of variable use?

Scope and Extent

I found some answers in Guy Steele’s Common Lisp the Language, 2nd Edition,² which Matthias Felleisen recommended to me.

In chapter 3, Steele introduces the concepts of scope and extent:

Scope refers to the spatial or textual region of the program within which references may occur. Extent refers to the interval of time during which references may occur.

In addition, there are four interesting cases of scope and extent, with respect to Common Lisp:

• Lexical scope: a reference can only occur within certain textual regions of the program, which are determined by the establishing construct, e.g., the body of a variable definition.

• Indefinite scope: a reference can occur anywhere in the program.

• Dynamic extent: a reference can occur during the time between an entity’s creation and its explicit destruction, e.g., when a local variable is created upon entering a function and destroyed when returning from that function.

• Indefinite extent: an entity may exist as long as it is possible to be referenced. (Note that this is the idea behind garbage collection: an entity can be destroyed once references to it are impossible.)

Steele points out that dynamic scope is a misnomer, even though it is both a traditional and useful concept. It can be defined as indefinite scope and dynamic extent. In other words, references to a variable may occur anywhere in a program, as long as that variable has been initialized and has not yet been explicitly destroyed. Furthermore, a later initialization hides an earlier one.

Discussion

I found this approach very informative, because it explicitly distinguishes between space (scope) and time (extent), which further implies a separation between compile time and run time. This explains my unease with the definition of “dynamic scope”—it is nominally about textual regions in a program, but also requires consideration of run-time behaviour. Dynamic scope is a misnomer!

The above definitions are specifically for Common Lisp, but I believe we can learn from them and adapt them for other programming languages.

A brief and incomplete history of lexical scope

During my research of different definitions of lexical scope, I began to wonder if there was an “original” definition of lexical scope. I did not find one, but I was able to trace some of the connections between Lisp, Scheme, and ALGOL 60. This history is certainly incomplete, but I hope it is somewhat useful and interesting.

• 1960. John McCarthy publishes the original paper on Lisp.³ In History of Lisp,⁴ McCarthy writes that he borrowed the λ-notation from Alonzo Church’s lambda calculus, but none of the other ideas. He also recounts an incident where a programmer desired lexical scoping, but Lisp used dynamic scoping. McCarthy considered this to be a bug, which Steve Russell later fixed by developing the “FUNARG device.”

• 1963. After a few years of work, the Revised Report on Algorithm Language ALGOL 60 is published.⁵ While “lexical scope” is not explicitly mentioned, it is recognizable in the specification.

• 1964. Peter Landin shows how expressions in programming languages can be modelled in Church’s λ-notation.⁶ He also introduces the concept of a closure, which pairs a lambda expression with the environment it was evaluated in.

• 1970. Joel Moses describes the problem of free variables in functions.⁷ He considers both the “downward” case (where a function is passed to another function) and the “upward” case (where a function returns a function), and remarks on the correspondence between Lisp’s FUNARG device and Landin’s closures.

• 1975. Gerald Sussman and Guy Steele publish the first Scheme paper.⁸ They describe their goal of a Lisp-like language that is based on the lambda calculus. As a consequence, they implement lexical scoping with closures, to preserve the substitution semantics of the lambda calculus. They compare this scoping discipline to ALGOL’s.

• 1978. Steele and Sussman describe various programming language design choices, by developing an interpreter for each programming language variation.⁹ In particular, they provide a detailed discussion on lexical and dynamic scoping.

Next stop, R

Now that we have examined the definitions of lexical and dynamic scope, and also explored some history, we are ready to return to the original question. Is R lexically or dynamically scoped?

In the next blog post, we’ll answer that question, and also see how R can be very confusing.

I would like to thank Sam Caldwell, Ben Greenman, and Artem Pelenitsyn for their comments and feedback on this blog post.