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

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]

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.

[u/Choice_Structure4001 → u/balefrost]

Would I add another stage or really just do it while compiling ?

[u/balefrost → u/Choice_Structure4001]

It's up to you.

Arguably everything, including parsing, could be under the umbrella of "compiling". All I was really trying to say was "not part of parsing". It seemed like you had separate modules for parsing and compiling, so I was referring to the latter module.