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.

While dynamic scoping is known to be straightforward, In todays post I'm going to go over some strategies for implementing lexical scoping. While a bit more complicated to implement, its benefits far outweigh any trouble encountered along the way, so lets get to it.

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. 

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 want to mark a variable ready to use we look in the symbol table for the first instance of the desired name that has NOT been marked ready for use yet 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;
}

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 ByteCodeGenerator::emitLet(astnode* n) {
    markVariablesAsReadyToUse(n->left);
    switch (n->left->expr) {
        case BIN_EXPR:{
            emitBinaryOperator(n->left); 
        } break;
        case ID_EXPR: {
            genCode(n->left, true);
        } break;
    }  
}

To mark the variables we use a localized DFS, which only explores the current subtree, but not it's neighbors.

void ByteCodeGenerator::markVariablesAsReadyToUse(astnode* n) {
    if (n != nullptr) {
        if (n->kind == EXPRNODE && n->expr == ID_EXPR) {
            symTable.makeReady(n->token.getString());
        } else {
            markVariablesAsReadyToUse(n->left);
            markVariablesAsReadyToUse(n->right);
        }
    }
}

When accessing a variable we use the findReady() method from above to obtain the correct instance and then compare the depth its stored at to the current depth of the table to calculate the correct runtime offset.

void ByteCodeGenerator::emitLoad(astnode* n, bool needLvalue) {
    SymbolTableEntry item = symTable.findReady(n->token.getString());
    int depth = runtimeDepth(symTable.depth(), item.depth);
    if (needLvalue) {
        emitLoadAddress(item, n);
    } else {
        if (depth == GLOBAL_SCOPE) {
            emit(Instruction(ldglobal, item.addr));
        } else if (depth == 0) {
            emit(Instruction(ldlocal, item.addr));
        } else {
            emit(Instruction(ldupval, item.addr, depth));
        }
    }
}

This offset is also used to determine if we should be emitting global, local, or upvalue related instructions.

int ByteCodeGenerator::runtimeDepth(int currDepth, int itemDepth) {
    if (itemDepth == -1 || currDepth - itemDepth < 0)
        return -1;
    return currDepth - itemDepth;
}

The one downside to this approach is that it takes the logic for variable declaration/definition/initialization and spreads it out across multiple classes wich must then work together. If you dont mind the added overhead of a traversal over the entire AST then it is possible to separate this process into its own pass, where we track scope levels and variable life in a temporary symbol table and annotate the nodes with their calculated scope depth. If you are implementing a tree-walking interpreter instead of a bytecode interpreter, than that is probably the way you want to go.

---