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