<p>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)?</p>

<implementation><interpreters><variables>
How to store variables in an interpreted language?
CC BY-SA 4.0
2023-10-02T15:44:36.230Z
Isn't it obviously some kind of `name->value` map data structure? What have you tried?
Barmar
<p>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:</p>
<ul>
<li>First check the current stack frame,</li>
<li>Otherwise if the current stack frame represents a closure, recursively check the closed-over stack frame,</li>
<li>Otherwise, check the globals.</li>
</ul>
<hr />
<p>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.</p>
<p>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 &quot;out of scope&quot;).</p>
<p>It may be convenient to use a dictionary type which encapsulates this behaviour; for example, Python's <code>collections</code> library has the class <a href="https://docs.python.org/3/library/collections.html#collections.ChainMap" rel="nofollow noreferrer"><code>ChainMap</code></a> which implements a stack of dictionaries like this. You can implement your own &quot;chain map&quot; data structure by writing a class which holds a dictionary and an optional reference to a parent, which would be another &quot;chain map&quot;.</p>
<hr />
<p>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, <a href="https://en.wikipedia.org/wiki/Java_bytecode" rel="nofollow noreferrer">Java bytecode</a> has instructions for loading or storing to the first, second, third, fourth or <em>n</em>th local variable.</p>
<p>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.</p>

CC BY-SA 4.0
2023-05-18T13:08:10.330Z
2023-10-02T18:00:00.373Z
2023-10-02T18:00:00.373Z
kaya3
CC BY-SA 4.0
2023-05-18T13:11:35.767Z
TIL `ChainMap` exists in python. Never knew it was a thing.
lyxal
<p>Adding to <a href="https://languagedesign.stackexchange.com/a/534/110">@kaya3's answer</a> regarding the stack-of-dictionaries, you'll still need something that the variable-name key points to. Eg., the user's identifier &quot;x&quot; must refer to some previously declared/instantiated &quot;x&quot;:</p>
<pre><code>x = 1

def foo():
    return x + 2  # what is x?
</code></pre>
<p>If your identifier resolution can be run at compile time, then you can store a pointer to the declared &quot;x&quot; in the AST node for your use of &quot;x&quot;. That implies that the dictionary maps from the identifier's name to the AST node where the identifier was declared.</p>

CC BY-SA 4.0
2023-05-19T12:17:45.700Z
2023-05-19T12:17:45.700Z
chrisaycock
# How to store variables in an interpreted language?
Posted by: username_0 on 2023-05-18
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)?
**Tags:** implementation interpreters variables
> **Comments:**
> **username_1**: Isn't it obviously some kind of `name->value` map data structure? What have you tried?  
---
## 2 answers
### Answer by username_2 on 2023-05-18. Score: 7
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`](https://docs.python.org/3/library/collections.html#collections.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](https://en.wikipedia.org/wiki/Java_bytecode) has instructions for loading or storing to the first, second, third, fourth or *n*th 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.
> **Comments:**
> **username_0** (2023-05-18): TIL `ChainMap` exists in python. Never knew it was a thing.  
---
### Answer by username_3 on 2023-05-19. Score: 2
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

def foo():
    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.
---
