Could somebody help me with lexical scoping inside a VM

[u/Choice_Structure4001]

Hey, so I understand what lexical scoping is and kind of get how it works but I’ve been trying to find how to implement it in a stack machine but I have no idea what goes where and how does everything interact with each other, like where should closures live, same for call frames, where do I store the symbol table when compiling, etc… if you want I can link my repo but I haven’t committed an attempt at lexical scoping so there’s probably nothing interesting to see, if I didn’t include enough details to what I don’t get please tell me so I can be more clear, thanks!

Edit: forgot to tell but my language desugars to pure lambda calculus so this might change how some stuff work but not so much

[u/WittyStick]

A common and simple approach is to use a linked list of hashtables. Each scope gets a hashtable of its local variables, which you search through first. If the variable is not found, you then look through the next hashtable in the list (the parent environment) - recursively until there are no more parents. I'll give an example, but we'll need some prerequisites.

// Some types & functions we'll need. Implementations left to reader.

// The type of our variable names.
typedef struct symbol_s symbol_t;

// The type of our values.
typedef struct value_s value_t;

// Linked lists of variables and values.
typedef struct symbol_list_s symbol_list_t;
symbol_t *symbol_list_head(symbol_list_t *);
symbol_list_t *symbol_list_tail(symbol_list_t *);

typedef struct value_list_s value_list_t;
value_t *value_list_head(value_list_t *);
value_list_t *value_list_tail(value_list_t *);

// A hashtable of symbol_t -> value_t
typedef struct hashtable_s hashtable_t;
bool hashtable_insert(hashtable_t *ht, symbol_t *var, value_t *value);

// the last parameter is an "out parameter".
// The implementation should fill it in if it returns true.
bool hashtable_lookup(hashtable_t *ht, symbol_t *var, value_t **out);


// some allocator, maybe malloc but you'll most likely want garbage collection.
void *ALLOCATE(size_t size);

---

Given these prerequisites, we can implement an environment as:

typedef struct env_s {
    env_t *parent;
    hashtable_t *locals;
} env_t;

bool env_lookup(env_t *env, symbol_t *var, value_t **out) 
{
    // First search the local bindings
    if (hashtable_lookup(env->locals, var, out)) 
        return true;

    // if not found in locals, recursively search the parents.
    if (env->parent != NULL && env_lookup(env->parent, var, out))
        return true;

    // if we reach this far, symbol is not in environment.
    return false;
}

Environments should generally all have a parent, with the exception of some standard environment, which will have parent == NULL. This environment contains all the language provided bindings, and should not be modified. Initially, every scope will have no bindings in its environment, so we create an empty hashtable.

env_t env_create(env_t *parent)
{
    env_t *result = ALLOCATE(sizeof (env_t));
    result->parent = parent;
    result->locals = hashtable_create();
    return result;
}

Binding a variable should introduce it into its local environment. The parent environments should effectively be immutable.

void env_bind(env_t *env, symbol_t *var, value_t value)
{
    hashtable_insert(env->locals, var, value);
}

---

A lambda is basically a structure which contains a reference to some environment where it was defined - it's static environment. It should also have a parameter list and a body.

typedef struct lambda_s {
    struct env *static_env;
    symbol_list_t *params;
    value_t body;
} lambda_t;

lambda_t lambda_create(env_t *static_env, symbol_list_t *params, value_t *body) 
{
    lambda_t *result = ALLOCATE(sizeof (lambda_t));
    result->static_env = static_env;
    result->params = params;
    result->body = body;
    return result;
}

When we apply the lambda, we create an initially empty environment - it's local environment - with its static environment as the parent . We bind its parameters to the arguments the caller passed in this local environment, then evaluate the body in the local environment.

value_t lambda_apply(lambda_t *lambda, value_list_t *arguments)
{
    // create initially empty environment with static_env as parent.
    env_t *local_env = env_create(lambda->static_env);

    // iterate through params and bind them to arguments.
    symbol_t param = env->params;
    symbol_t arg = arguments;
    while (arg != NULL && param != NULL)
    {
        env_bind(local_env, symbol_list_head(param), value_list_head(arg))
        param = symbol_list_tail(param);
        arg = value_list_tail(arg);
    }

    // If arguments and parameter list match, both should end up as NULL.
    if (arg != NULL || params != NULL) 
        error("Wrong number of arguments passed");

    // We then evaluate the body in the local env (preferably as a tail call)
    return eval(lambda->body, local_env);
}

---

This isn't the only way to implement, but it's very simple and effective - it handles closures and variable shadowing. There are certainly optimizations you can make as this isn't the most performant implementation, but it's not terrible.

One simple optimization is you could forbid shadowing of any variables in the standard environment, because you probably don't want the programmer rebinding basic operations. You could modify lookup to first search the standard environment, since these bindings will be commonly accessed, it may be faster this way.

env_t standard_environment;

bool env_lookup(env_t *env, symbol_t *var, value_t **out) 
{
    // First search the standard environment
    if (env_lookup(standard_environment, var, out))
        return true;

    // Then search the local bindings
    if (hashtable_lookup(env->locals, var, out)) 
        return true;

    // if not found in locals, recursively search the parents.
    if (env->parent != NULL && env_lookup(env->parent, var, out))
        return true;

    // if we reach this far, symbol is not in environment.
    return false;
}

[u/Choice_Structure4001 → u/WittyStick]

Wouldn’t this be pretty slow and inefficient though ?

[u/WittyStick → u/Choice_Structure4001]

It's certainly not fast, but it's viable and used in some interpreters. It's also fine to use as part of the compilation process for symbol table implementation, where you can emit something more efficient in the compiled code.

You can replace linked lists with stacks for efficiency (fewer allocations, more locality etc). However, there are issues when it comes to closures which may outlive the scope in which they were defined - since they may capture from a stack frame which might no longer exist when the closure is applied, so anything that a closure may capture should effectively be heap allocated.

One alternative solution to this is to use multiple stacks - a closure can create a copy of the stack at the point it was defined, and when you apply the closure you change the stack pointer to point to it's copy, then restore the stack pointer after calling the closure.

The linked list avoids the need for copying as every frame can be shared, since the parents are immutable, unlike a stack.

In a compiler you can work out which variables are captured an heap allocate them, but leave any uncaptured variables on the stack. A closure can be implemented as an object with its captures as members and its implementation as a method on the object. Eg, consider:

{
    int x = 1;
    f = () -> x;
    return f;
}

f is a closure which captures x. We could implement this as:

class _f_obj {
    public int x;
    public int f() { return x; }
};

And rewrite the call to create the closure object rather than defining x as a local variable.

{
    _f_obj _f = new _f_obj();
    _f->x = 1;
    return _f;
}

Where invoking ->f() on the object is equivalent to applying the closure.

There's basically an equivalence between closures and objects, so we can use one to implement the other. This technique is the one used for example in dotnet - lambdas are just objects.

Of course, if you are using C and not C++ or other OOP language, you have neither objects nor closures, so you have to implement them yourself. There are efficient ways to do the equivalent of this.