Say I'm making an interpreted language. What's the best way for me to store variable name/value pairs (or type/name/value triplets in the case of languages with typing)?
Many dynamic languages have function scope, i.e. a variable is in scope within the whole of the function body that it is declared in, or if it is not declared within a function then it is global. In this case, each stack frame needs just one mapping from names to values, which could be a hashtable or any other dictionary data structure. To look up a name:
- First check the current stack frame,
- Otherwise if the current stack frame represents a closure, recursively check the closed-over stack frame,
- Otherwise, check the globals.
For languages with block scope, there are generally more scopes than there are stack frames, and local variables in a block may be allowed to shadow local variables declared in an outer block in the same function. In this case, each stack frame can have a stack of dictionaries, where each dictionary in the stack represents a block.
To check a name, iterate through the stack from top to bottom, trying each dictionary in order; to declare a variable, add it to the top-most dictionary in the stack; and to interpret a block statement, push a new dictionary to the stack before interpreting the child statements, and then pop it from the stack (so that the variables in that dictionary go "out of scope").
It may be convenient to use a dictionary type which encapsulates this behaviour; for example, Python's
collections library has the class
ChainMap which implements a stack of dictionaries like this. You can implement your own "chain map" data structure by writing a class which holds a dictionary and an optional reference to a parent, which would be another "chain map".
The use of dictionaries assumes that variable names are represented as strings in the AST. If you are interpreting a bytecode language, then local variable names may already have been replaced with numeric indices; for example, Java bytecode has instructions for loading or storing to the first, second, third, fourth or nth local variable.
In this case, you should know in advance how many local variables each function has; then, variables' values can be stored in an array, and accessed by index. Alternatively, if your interpreter is implemented in a low-level language with direct access to the call stack, then local variables can be stored on the stack directly, and then accessed by computed stack offsets. However, if you take this approach then you will need some other strategy for handling closures, which may capture the local variables of an outer function call beyond its lifetime on the stack.
Adding to @kaya3's answer regarding the stack-of-dictionaries, you'll still need something that the variable-name key points to. Eg., the user's identifier "x" must refer to some previously declared/instantiated "x":
x = 1
return x + 2 # what is x?
If your identifier resolution can be run at compile time, then you can store a pointer to the declared "x" in the AST node for your use of "x". That implies that the dictionary maps from the identifier's name to the AST node where the identifier was declared.