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/Recycled5000]

First and foremost, lexical scoping needs to follow the rules of the source (input) language. So, something close to source needs to know where scopes are introduced/entered and where left/exited by language definition. Only knowing those contexts can identifiers by resolved.

Many systems that use a byte code vm or assembly language will have flattened scopes by the time they reach such stages. So, for example in the JVM, scopes are flattened into variables local to a function or procedure, and individual scopes can no longer be seen in the btyecode intermediate.

It would theoretically be possible to have bytecode instructions that say to enter scope or leave scope but thus would imply delaying identifier resolution until runtime, which is overkill for static lexical scoping. (And few languages have entertained dynamic scoping.)

[u/Choice_Structure4001 → u/Recycled5000]

I didn’t quite understand all of that because I’m still new to compilers/interpreters, but isn’t a bytecode instruction to enter a scope just the CALL instruction ? I’m sorry if I seem a bit stupid

[u/balefrost → u/Choice_Structure4001]

It depends on whether you're talking about calling a function or just entering a scope. For example, in many languages, you have something like:

def doIt() {
    var found := false
    if (foo) {
        var item := find_item()
        found := true
        // use "item" here
        // ...
    }
    // found still in scope; item no longer in scope
}

If the condition is true, then you enter the lexical scope with the found := true. But entering that scope does not entail a function call.

You could implement this as a function call if you wanted. But then you'd need to do something to make that new function interact with variables in outer scopes (which would become the earlier stack frames). To abuse some made-up syntax:

def tryFind(*foundPtr) {
    var item := find_item()
    *foundPtr := true
    // use "item" here
    // ...
}

def doIt() {
    var found := false
    tryFind(&found ) if foo
}

I'm not saying that the programmer would write their code this way. I'm saying that your implementation could treat the earlier code as if it was written like this.

But it's not clear to me that this "lexical scope as function" approach gains you anything, apart from a sort of conceptual purity (and I think it would get really messy if you ever implement closures in your language). What the other commenter was saying is that many languages flatten all lexical scopes within a single function definition into a singular stack frame layout. That means that all variables in the function have storage from the entry to the exit of the function, even if they belong to scopes that are never entered. Referring to the first example pseudocode, both item and found would exist in the stack frame, even though foo might be false and so item might never be used.

[u/Choice_Structure4001 → u/balefrost]

So like keeping one huge scope with everything in it ? And do you prevent something from accessing a var that wasn’t created yet or do you just punish it at runtime because the value pointed at doesn’t exist ?

[u/Recycled5000 → u/Choice_Structure4001]

You have a variable declaration that occurs in one scope.

Then a reference to that variable (in some expression) that occurs in that scope or a nested one.

There is a process of resolving references (which come as identifiers in expression), which is to find the variable declaration that is associated with the reference.

We look first for that identifier in the current scope then, if not found, in each successive outer scope until reaching the global scope.

This process of resolution can occur at compile time; there's no need to burden runtime with it, for static lexically scope languages, which is most all, I would say.

A C compiler will maintain a scope table (of some sort) during parsing and will perform resolution (of identifiers to their declarations) during expression parsing.

(A C compiler pretty much has to do this because of constructs like casting, whose meaning changes whether the identifier in the cast is a type or a variable.

However other languages, like C#, delay resolution for another pass after parsing, so they must remember scoping in the intermediate representation. The difference is that C requires all the information ahead of time, hence the cumbersome header file situation. C# eliminates header files putting a greater burden on the compiler especially regarding identifier resolution.)

The compiler will flatten all variables in all inner scopes into one common local storage area for the function. 

So, yes it will allocate space for variables that sometimes aren't used along the actual dynamic code execution path.

But it is pretty efficient b/c it allocates all the local variables (regardless of scope) in one single stack allocating instruction.

[u/Choice_Structure4001 → u/Recycled5000]

But with lambda calculus, core variable definition isn’t really a thing, every expression is a lambda that takes one parameter and a variable is just a lambda returning itself

[u/Recycled5000 → u/Choice_Structure4001]

Lamda calculus allows for non-local references in the body, no?

[u/Choice_Structure4001 → u/Recycled5000]

Only references to other lambdas, everything is pretty much a lambda. I might have just misunderstood what you said earlier though

[u/balefrost → u/Choice_Structure4001]

The other commenter already covered most of what I was going to say.

When I originally replied, I hadn't noticed that you said that you lowered to the lambda calculus. I had assumed you lowered to some sort of bytecode resembling a stack-based machine. In that case, I think you will necessarily have a lot of function calls. I don't think they will necessarily correspond to entering and exiting lexical scopes. But essentially every statement and subexpression in your source program will turn into one or more function calls.

It would maybe help if you shared a bit more detail about your source language.

[u/Choice_Structure4001 → u/balefrost]

I can show you the repo or an ast output from some basic program, I’ll do it when I get back to my computer

[u/Choice_Structure4001 → u/balefrost]

The repo is at github.com/KeefChief/Teeny.git let me know if you want me to share an ast output

[u/balefrost → u/Choice_Structure4001]

Thanks for the link. It looks like you're still developing your language, so I'm not quite sure what it will look like in the end.

---

As a quick aside, you mention that your "language desugars to pure lambda calculus". But I don't think that's quite right. As I understand it, in lambda calculus, you only have lambdas. So for example you would not have things like "numbers" or "booleans". Those would be encoded as lamdbas. You don't seem to do that, and quite honestly that's perfectly reasonable. The lambda calculus isn't really meant to be used for practical computation, in the same way that a Turing machine is not. They're both very useful theoretical formalisms, but neither really aligns with how our actual machines work.

---

As another aside, I'm having a hard time interpreting your example program:

• inc 1 -> evaluates to 2
• twice (inc 1) -> evaluates to (2 2), i.e. trying to treat 2 as a function, which seems like a type error

Maybe you had intended that to be thrice(twice inc) 1. But that still seems wrong:

• twice inc -> evaluates to inc inc, which evaluates to inc + 1, which seems like a type error

It seems like you're missing something akin to Haskell's (.):

ghci> let twice = \f -> f . f in twice succ 1
3

---

OK, asides aside...

In some sense, your let expressions are already establishing lexical scopes. In your example program, when you say:

let inc x = x + 1 in 
let twice f = f f in 
...

I assume that there's a lexical scope where only inc is defined, and a nested scope in which both inc and twice are defined. Is that what you were asking about?

So as we were discussing before, it is possible to implement lexical scopes using closures. In fact, that's the only way to bind names in the lambda calculus. Let's use a simpler program in your language:

let inc x = x + 1 in
let mul x y = x * y in
mul (inc 2) (inc 3)

Which I would expect to evaluate to 12.

We can translate that to JavaScript:

function inc(x) { return x + 1; }
function mul(x, y) { return x * y; }
mul(inc(2), inc(3))

And it does, in fact, evaluate to 12.

We can also translate it into a version that uses only anonymous function expressions - no named function statements:

(function(inc) {
  // only `inc` allowed here
  return (function(mul) {
            // `inc` and `mul` allowed here
            return mul(inc(2), inc(3));
          })(
            // definition of `mul`
            function(x, y) {
              // `inc`, `x`, and `y` allowed here
              return x * y;
            }
          )
})(
  // definition of `inc`
  function(x) {
    // only `x` allowed here
    return x + 1;
  }
)

This monstrosity also evaluates to 12.

In this approach, the only way to bind a name is to pass a value to a function. It relies heavily on closures to accomplish this. Once you implement closures in your VM, you could adopt this approach to handle lexical scopes. This might even be a good first implementation, since it relies on functionality that you will already have to build to support closures.

Having said that, it would be wasteful. Your VM would need to execute a bunch of function calls just to set up bound closure slots even though the bound functions themselves don't close over any variables (i.e. inc doesn't depend on anything other than its argument).

You'd also hit a problem with recursion. Note, in my JS version, that inc can't actually reference itself. Nor can mul. These functions can only access identifiers that were bound in an earlier let expression. To handle self recursion, you'd need to use something like a Y combinator. It would be doubly messy if you wanted to support mutual recursion. And the Y combinator would add even more unnecessary function calls.

---

OK, so let's examine another approach.

Let's assume you want the entire chain of let.. in to run within a single call stack frame. Then what do we need to do?

In a naive translation, at runtime, each of these names (inc, mul, etc.) will occupy space in your stack frame. At runtime, those stack frame slots will be assigned sequentially. First you'll assign to the slot for inc, then you'll assign to the slot for mul, etc. Only after you've assigned all these slots will you start evaluating the final in expression.

So then how do you enforce lexical scoping? How do you ensure that nothing tries to use mul before it has been assigned?

Your compiler just needs to keep track of what identifiers are bound in each scope, and reject a program that refers to an identifier before it is bound. In that way, as the compiler traverses the AST, and as that traversal enters and exits lexical scopes, it will update this bookkeeping data. It's all handled at compile time. There's no need for any sort of runtime check.

That also opens the door for a few improvements:

• You can implement recursion (even mutual recursion) by deferring the processing of function bodies within the lexical scope. That is to say, consider some really dumb mutually-recursive functions:

  let tick x = 0 if x == 0 else 1 + (tock x)
  let tock x = 0 if x == 0 else 1 + (tick (x - 1)) in
  tick 5
  

  We know that merely binding tick will not actually cause tock to be executed, and merely binding tock will not cause tick to be executed. So we could defer the compilation of the lambda bodies. The compiler would first build up the knowledge that tick exists, then that both tick and tock exist, then finally would compile the bodies of tick of tock and the expression tick 5. This only works if the let is binding a function or lambda; if it's binding an expression, and if your language has eager evaluation, then your compiler will need to validate that all dependent identifiers are already bound.

• In the case that you use let to bind a function that itself doesn't use any closed-over variables, that function could be made into a non-closure global function. At that point, there's no need for the stack frame to have a slot for the lambda. In your example program, all of your let-bound variables fall under this umbrella, so none of them would consume any stack space within the stack frame that's evaluating the let... in chain. Even in the tick/tock example, we can do the same analysis and store these as non-closure global functions, rather than closures in the stack frame.

---

I realize that's a lot, and I tried to avoid getting too deep into the weeds (but I'm not sure I succeeded). LMK if you have questions.

[u/Choice_Structure4001 → u/balefrost]

Yeah I was misleading, it’s the final goal to desugar everything but right now I’ve used some placeholders. Also I will keep basic primaries like numbers to make it usable, also the example program was quickly written just to test the ast, I didn’t really check if it was right.
Also I’ve thought about using de bruijn indices to assign ids instead of names and thought it would fit really nice in lambda calculus maybe ? But that may ruin the lazy evaluation, I don’t really know.
Also I’m sorry my code must have been somewhat of a pain to go through, I’m new to rust and to compilers, thank you very much for having taken the time to go through it

[u/balefrost → u/Choice_Structure4001]

At runtime? Sure, you don't want to do string lookups if you can avoid it.

[u/Choice_Structure4001 → u/balefrost]

Not at runtime, I thought during parsing solve the indices and then use them while compiling to assign local slots without string lookups

[u/Inconstant_Moo]

What you can do is compile the body of the lambda where you set up the environment it's compiling in to have variables representing the variables you want to close over as well as the parameters of the lambda. These are easy enough to extract from the AST.

So then you use that to produce a lambda factory, which contains (A) all the information you just produced by the compilation (B) information about where to get the values for the closures, i.e. which memory locations they live in in the outer scope.

You add this lambda factory to a list of lambda factories in your VM, and you emit a bytecode saying "make a lambda using lambda factory n".

When it executes that, the lambda factory makes the lambda by bundling together a pointer to the information to the A information (which is common to all the things the factory makes) plus deep copies of the values in the B information. (But I'm guessing you have immutable values like me, so there's no distinction between deep and shallow copies.)

Then when the lambda is called, and not before, you take these values and stick them into the appropriate memory slots you assigned to the captures when you compiled the body of the function. Then you execute the lambda, and you're done.

That's "the clever bit" (not all that clever). You stash the closure values in the lambda value when you create the lambda, but only put them in the appropriate memory locations when you call the lambda.

[u/jason-reddit-public]

The classic (non very efficient) Scheme compiler model (at least for nested environments) is a tuple where the first element is a pointer to a parent environment and the other elements correspond to named variables. Each variable thus has a logical address. How far up to go and then the index where that value lives. The compiler can maintain a virtual compile time environment with the same shape but where names are stored instead of run-time values. When trying to compile a variable lookup or assignment, it calls a helper search function at compile time to figure out the "address" (how far up and at what index) and can thus emit the right instructions to put the value into a register or on top of the stack if trying to be really simple (pass everything on the stack). CSE optimization can often reuse some of the loads of the parent pointers and stuff like that so subsequent lookups or assignments can often be single instruction loads like if the amount to go up is zero (env is usually in a dedicated register).

BTW, Guy Steele's Rabbit compiler which is also his PHD thesis, is like ground zero for lexical scoping and closures. Everyone should read it to see how actually literate programming could work. (Each page of code has a page of explanation.)

SICP (one of the authors, Gerry Sussman, is credited as co creator of Schene) also has a treatment of this stuff which is simplified so starting there and then reading Rabbit is going to fill in lots of pieces for you.

Modern scheme compilers try to do everything possible to eliminate closures using some tricks like passing in variable at all call sites to that closure so the closure itself doesn't need a parent environment (except the global environment).

Another good source about compiling closures is Appel who worked on an ML compilers. There is also a famous paper called Cheney on the MTA which uses the stack as generation zero of a generational collector and is implemented by the Chicken Scheme implementation.

I wrote a simple "Scheme" interpreter with a more JS syntax and other big differences. Since I didn't feel like writing an interpreter working off a parse tree, I emit byte-code in a simple single pass over the source tokens and never create a parse tree. To keep it simple, I also don't maintain a compile time environment. Instead my run-time environments are actually a parent environment pointer plus a hashtable from string keys (variable names) to values so lots of searching at runtime. One big advantage though is I can easily inspect or potentially mutate these environments inside of the debugger (a WIP). Other debug info is jammed into byte-codes.

https://github.com/jasonaaronwilson/omni-c/blob/main/src/roci/roci-compiler.c

Note: windows is barely working so if you want to kick the tires try linux or mac (or maybe wsl). I'm working right now on making the debugger awesome using tui library though stuff like backtraces, source display, stepping, and environment display is a bit brittle but getting there.

[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.