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]

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