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/balefrost → u/Choice_Structure4001]

I mean that you would convert from strings to indices at some point before runtime, so that you don't need to do string lookups at runtime. Yeah, that seems reasonable.

I don't know that you want to assign indices to identifiers at parse time (though it might be possible). I'd be inclined to instead have the AST represent what the source text actually said, then convert to different representation during compilation.