David's Coding Blog

Interpreter - How scoping is implemented

Most programming languages have support for the concept of variable scoping.
How is this logic implemented inside of an interpreter?

What is scoping?

If a variable is declared inside a function, it is not accessible outside of this function. But a global variable can be accessed inside this function.

<?php
// Declare global variable $foo
$foo = 42;

function localVariable(): void
{
    // Access to global variable $foo function is possible
    global $foo;
    echo $foo;  // Prints: 42

    // Declare local variable $bar
    $bar = 'bar';   // Prints: bar
    echo $bar;
}

localVariable();

// Access to local variable from function is not possible
echo $bar;  // Prints: Warning: Undefined variable $bar

How scoping is implemented?

The interpeter functions responsible to process the AST (abstract syntax tree) receive the environment as an argument. This environment contains the variables, constants, etc. available in the current scope.
It also has a pointer to its parent environment. This allows the access to global variables.

Let us take a closer look at the code shown above.

1. The $foo variable is stored in the global environment.
2. When the function call is processed, a new environment is created with the global environment as its parent.
3. So the variable $bar is stored in the functions environment.
4. After processing the function call, the interpreter is back in the previous environment, which in this case is the global one.
5. So the access to the variable $bar fails, because it is not found.

The code for the variable lookup could be the following:

<?php
class Environment
{
    private ?Environment $parent;

    // Associative arrays/dictionary/map
    // Key: string
    // Value: mixed
    private array $variables;

    public function __construct(?Environment $parent = null)
    {
        $this->parent = $parent;
        $this->variables = [];
    }

    public function lookupVariable(string $name): mixed
    {
        // If the variable is stored in this env, return the value
        if (array_key_exists($name, $this->variables)) {
            return $this->variables[$name];
        }

        // If this env has a parent, call lookup function on it
        if ($this->parent !== null) {
            return $this->parent->lookupVariable($name);
        }

        // The variable is not declared in the current env or its parents
        throw new Exception("Variable '$name' is not declared");
    }
}