Implementing Lexical Scoping: Resolving Variable Names with De Bruijn Indices

mgcadmin 09-01-2026

Almost every modern programming language uses lexical scoping rules as the default strategy for variable name resolution. Lexical scoping is when a variables value/lifetime is determined in part by its location in the text of the code (lexicographically). This allows a programmer to more confidentally determine what a value should be by simply reading the code. It should be immediately apparent as to why this is a desirable trait. 

The alternative is the aptly named dynamic scoping, in which a variables value is dependent upon the internal state of the running program. Early versions of Lisp used dynamic scoping because of the perceived cost of implementing lexical scoping. Many interpreted languages, like AWK and Perl uses dynamic scoping because of its relative ease of implementation.

In todays post I'm going to go over some srategies for implementing lexical scoping.

What's In a Name?

The ability to give names to a value is one of the core abstractions in programming. The scope of a variable is the portion of the program where a name resolves to a certain variable. Block structured languages introduced the idea of shadowing, where a variable name can be re-used in different scopes, like the following:

int a = 13; //global scope

int funcEx(int a) {
     a *= 2;
     return a;
}

int funcEx2() {
    return a+a;
}

class ObjEx {
     private:
         int a;
    public:
         ObjEx(int x) {
             a = x;
         }
         int getA() {
             return a;
         }
         void setA(int x) {
             a = x;
         }
};

int main() {
      ObjEx tmp(5);
      cout<<a<<endl;
      cout<<tmp.getA()<<endl;
      cout<<funcEx(tmp.getA())<<endl;
      cout<<funcEx2()<<endl;
      return 0;
}

Lexical scoping not only allows for us to reason about the internal state of a program during execution, while allowing for the re-use of meaninful names in different scopes without worrying about them being accidentally overwritten. During execution when a new scope opens, a new activation record is placed on to the stack, making available a new "slot" for a new local definition of a previouly used variable name.

Environments, Stacks Of Environments, and Finding the Correct Environment

In a block structured language, code blocks can be thought of similar to procedures with no arguments and no return value in that the execution of a block triggers the creation of an activation record. The activation record of a lexically scoped language has two pointers: the control link and the access link. The control link points to the activation record immediately below the current record on the stack, while the access link  points to the Activation Record of the procedures defining environment. The access link is what's used to "close over" any free variables, making them accessible to enclosed scopes.  When a scope is closed, the control link is used to return to the previous scope. For code blocks both the access link and the control link point to the same record. For procedures or functions though this is not necessarily the case. 

 The following example illustrates variable shadowing where an identifier is re-used in an enclosed scope with a new declaration and different value. To be able to correctly resolve which instance of the variable we are referring to we augment each variable with a scope "depth" so that when we walk the chain of access links we know exactly how far to go. This can be done when building the symbol table or performed during an additional traversal of the AST. Where we previously used a single value as the "address" of the variable, we now have a tuple of <address, depth> called a De Bruijn Index.

let i := 6;
println i;
{
    let i := 13;
    println i; 
    {
        println i;
        let i := 24;
        {
            println i;
            let i := 56;
            println i;
        }
        println i;
    }
    i := 13;
    println i;
}
println i;

We still need one more piece to make everything work as we expect it to. Take a look at the inner scope and you will notice that in it's enclosing environment we shadow 'i' with a new variable, and immediately enter a new scope, we then print the value of 'i' before shadowing it again. A problem can arrise when generating instructions for the first print statement: 'i' will resolve to the instance in the local scope when we actually want the variable that is being shadowed in the enlosing scope. 

mgoren@AES:~/owlscript$ owlscript -f scripts/blocks.owl 
6
13
(nil)
(nil)
56
24
13
6

The above output is the end result and a look at the symbol table layout might give you more insight into what's happening:

Symbol table:
  i: 1, -1(0)                 <- 6
  Block0: 2, 1(0)
    i: 1, 1(0)                <- 13
    Block1: 2, 2(0)
      i: 1, 2(0)              <- 24
      Block2: 2, 3(0)
        i: 1, 3(0)            <- 56

How then can we ensure that upon entering block one that we resolve the print statements instance of 'i' to block zero and when we enter block two that the first print statement resolves 'i' to the value in block one? 

Declared but not ready for use, Defined and ready to go

Syntactic analysis allows the compiler to synthesize or inherit attributes for nodes from other nodes, using the information available to us. By performing syntactic analysis we are able to conceptually separate the declaration of a variable name from its definition. 

In order to resolve the correct instance of the desired variable we add a flag 'isReady' to symbol table entries which is initialized to false when the variable name is declared. We delay setting the 'isReady' flag to true until just before we emit the instructions that refer to it. This way the slot in the scope is still reserved during symbol table construction but we'll be able to determine if that's the instance we should be concerned with or not when resolving names. 

void ScopingST::makeReady(string name) {
    BlockScope* x = currentScope;
    while (x != nullptr) {
        auto t = x->find(name);
        if (t != x->end() && t.isReady == false) {    
            x->find(name).isReady = true;        
            return;
        }
        x = x->getEnclosing();
    }
}

When we are ready to use a variable we traverse the symbol table until we find the first instance NOT ready for use and flip its flag. We also change the way variables are looked up in the symbol table, so that we dont accidentally return the entry for an instance that isnt ready for use yet.

SymbolTableEntry ScopingST::findReady(string name) {
        BlockScope* x = currentScope;
    while (x != nullptr) {
        auto t = x->find(name);
        if (t != x->end() && t.isReady) {    
            return t;
        }
        x = x->getEnclosing();
    }
    return nfSentinel;
}

All that's left to do is incorporate the isReady and scope depth information into the bytecode generation phase.

 

---