<p>Let's say I have some code in my target language like:</p>
<pre><code>fun someFunction(arg1: Int, arg2: String) {
    var a = foo()
    if a &lt; 10 {
        var b = a+1    
        var a = a+b+2  
        ...
    }    
</code></pre>
<p>The second <code>a</code> <a href="https://en.wikipedia.org/wiki/Variable_shadowing" rel="noreferrer">shadows</a> the first one.</p>
<p>In my compiler, I created a <code>Scope</code> class to track names and their definitions. The scopes roughly correspond to the nodes in the abstract syntax tree (AST). Each scope has a map of name → info, and a pointer to its enclosing scope.</p>
<img src="https://i.sstatic.net/gMpQf.png" width="145"/>
<p>But my problem is that this data structure doesn't work well when I get shadowing like this. For example, in what <code>Scope</code> do you evaluate <code>a+b+2</code>? If it's in the function body scope, then it misses the <code>b</code>, if it's in the <code>if's</code> scope, then it gets the uninitialized <code>a</code>, not the outer shadowed one, which I think is what it should use.</p>
<p>Perhaps I have not modeled this correctly. Perhaps it's more accurate to say that each <code>var</code> declaration creates a new nested <code>Scope</code>, used by the code that comes after it in a given <code>{...}</code> block. So the scope tree has more nodes, and they do not so exactly correspond to AST nodes or curly brace blocks.</p>
<img src="https://i.sstatic.net/ISOnb.png" width="130"/>
<p>If I implement this, then many of my <code>Scope</code> objects would be nothing but a single variable, and looking up a name would be a linear walk up the linked list (stack) of scopes. Maybe that's fine, but I'm wondering if there are some standard data structures used in compilers that are better than this linked list stack approach.</p>
<p>I think I would make <code>Scope</code> an abstract class and so that some scopes with many names could use an internal hash table. Scopes for a <code>class</code> could be like this, while scopes created by local <code>var</code> declarations could have just the one name, and a different implementation of a virtual <code>lookup(name)</code> method.</p>

<compilers><implementation><semantics><scoping>
Data structures for scopes and variable shadowing
CC BY-SA 4.0
2023-09-14T19:20:00.437Z
Is allowing `var a = a+b+2` core to the language design here? Most block-structured languages have scoping rules that preclude this sort of construction, but yours doesn’t have to; it seems like your `var` is more like the `let … in …` construct typical in functional languages. The standard data structures are aligned with standard designs and you can borrow from them when that’s what you have, but we should check what it is that’s needed first.
Michael Homer
CC BY-SA 4.0
2023-09-14T20:58:53.967Z
Rust, for example, allows multiple let declarations that shadow each other, right in the same `{...}` block. Eg, you say `let x = 1;` and on the next line `let x = x+1` and that's a second `x` that will be 2. Other languages I've seen allow you shadow variables, but you need to at least be in a nested block. So, yes, I guess my `var` is like a `let ... in ...` but without the rightward drift that happens in some languages I've used.
Rob N
CC BY-SA 4.0
2023-09-14T21:43:47.973Z
JavaScript, for example, would generate an error for `let a = a + b + 2;` because the `let` binding shadows the outer `a` for the entire block, and you can't reference a variable before its initialization is complete.
Barmar
CC BY-SA 4.0
2023-09-15T19:12:59.913Z
Stacks go brrrr
Seggan
<p>This is actually a question about language semantics, not about scopes. Your data structure is correct in essence.
The question is if the languages introduces the inner var a before evaluating its initializer.
If you can choose yourself because it's your language, create an intermittent error declaration with the semantics of using it results in an &quot;unitialized entity used&quot; error.
If the language allows using the outer <code>a</code> in the inner initializer, then the natural implementation is to evaluate the initializer's AST before the variable declaration itself.</p>
<p>For local name resolution, I'd actually walk up the AST.
The number of reachable variable declarations and enclosing blocks is usually very small resulting in overall better performance than building chains of maps.</p>

CC BY-SA 4.0
2023-09-14T19:36:25.310Z
2023-09-14T19:36:25.310Z
feldentm
<p>This is called a <a href="https://en.wikipedia.org/wiki/Persistent_array" rel="nofollow noreferrer">persistent array</a>.</p>
<p>If you don't need the <code>Scope</code> object accessible after finishing processing a scope, you could just use one symbol table, modify the symbol table directly when entering a scope, but record the modifications so that you could undo the modifications in reversed order when exiting a scope. You could use a stack to store information about the current scope and its ancestors. And you only have information about these scopes. All other <code>Scope</code> objects are destroyed.</p>
<p>Each variable name could also be considered an independent stack. Without the following improvements, you may need a unified stack to record which variable names are modified, but the exact modifications are independent from each other.</p>
<p>Then if you want the <code>Scope</code> object available after exiting the scope, for each variable name, you could sort the modifications (shadow and unshadow) of the variable in the above process by time, and maintain them in a search tree. Each <code>Scope</code> is bound to a time (version id). The current state of a variable name is the new value in the latest modification of that variable name before the version id. When you want to create a subscope, create two version ids for entering and exiting the scope just after entering its parent scope, and create the appropriate modifications on the entering version, and undo modifications on the exiting version. The version ids could be created and compared in another shared tree, instead of just using integers, if you may create subscopes in non-sequential order. A parent scope itself should not be modified after a subscope is created, so the the new value on undo could just be a copy of the previous value and don't need to be updated.</p>
<p>The structure is like a simplified Euler tour tree. It is possible to also support modifying a parent scope while there are already subscopes, if used in combination with a full Euler tour tree, to replace undoing.</p>
<p>This is O(logn) time and O(1) space per operation, where n is the number of scopes, assuming variable names are prehashed and don't cost extra time for looking up the tree bound to that variable name.</p>
<p>Some improvements using vEB trees and constant time data structure for maintaining version ids could make it O(loglogn) per operation, though I doubt anyone would really want to implement it.</p>
<p>You could also just use a persistent search tree to store the symbol table, but with O(logn) space overhead per operation.</p>

CC BY-SA 4.0
2023-09-14T21:25:27.353Z
2023-09-15T06:36:04.677Z
2023-09-15T06:36:04.677Z
user23013
CC BY-SA 4.0
2023-09-16T05:36:05.980Z
Are there non-research languages, where you can bind a name from a left local scope?
feldentm
CC BY-SA 4.0
2023-09-17T20:06:13.497Z
@feldentm If you are asking about using a name after exiting a scope, I think classes might be a case, where the stack is the inheritance path. But it might be more practical to just copy the symbol table, as vtables already work like that, and it isn't very useful to create a new class after each member definition.
user23013
<p>The real issue, I would argue, is that there is no one-size-fits-all:</p>
<ul>
<li>At module/file scope, you may have a large number of unique identifiers, especially counting the imported ones. Here, a map definitely makes sense.</li>
<li>At class/type scope, you may still have a fairly large number of identifiers. The <a href="https://doc.rust-lang.org/nightly/std/iter/trait.Iterator.html" rel="nofollow noreferrer"><code>Iterator</code> trait (Rust)</a> has a whooping ~75 methods at the time of writing, and it's one trait amongst many that a type may implement, coming on top of the inherent methods, and fields, of the type.</li>
<li>At function scope, you typically have only a handful of arguments and variables.</li>
</ul>
<p>As a result, I think your idea of using a Scope interface, and a polymorphic implementation makes sense, so you can specialize based on the type of Scope.</p>
<hr />
<p>For handling the variables (and arguments) of a function, I would argue for... a <strong>stack</strong>!</p>
<p>You are, in essence, already thinking of creating a stack of Scopes... it'll be much more efficient to have a single Scope with a stack of variables instead! You'll need a separate one, for popping, too:</p>
<pre class="lang-python prettyprint-override"><code>class VariableScope(Scope):
    def __init__(self, parent: Scope):
        self.parent = parent
        self.variables: List[(String, ???)] = list()
        self.blocks: List[Int] = list()

    def enter_block(self):
        self.blocks.append(len(self.variables))

    def exit_block(self):
        before = self.blocks.pop()
        del self.variables[before:]

    def add_variable(self, name: String, data: ???):
        self.variables.append((name, data))

    def search_variable(self, name: String) -&gt; Option[???]:
        for n, d in reversed(self.variables):
            if n == name:
                 return d

        return self.parent.search_variable(name)
</code></pre>
<hr />
<p>Finally, with regard to your issue about <code>var a := a + 1</code>, it's just a matter of <em>timing</em>.</p>
<p>If you do not want the newly declared <code>a</code> to be visible in <code>a + 1</code>, insert it into the scope only <em>after</em> having resolved <code>a + 1</code>. That's all there is to it.</p>

CC BY-SA 4.0
2023-09-15T11:32:50.010Z
2023-09-15T11:32:50.010Z
Matthieu M.
<p>I assume the semantics of your language is that the function body is evaluated as if executed sequentially, one line after the other, the same as when reading text. Also, the meaning of names is given by the same order, plus scopes. (As opposed to, for example, code given just dependencies and letting compiler decide evaluation order.)</p>
<p>Perhaps you are thinking scopes as static, as expressed by the graph/drawing.</p>
<p>But perhaps you can solve this by <em>growing</em> scopes: e.g. for the <code>if</code> scope,</p>
<ol>
<li>it starts empty,</li>
<li>then it contains <code>b</code>'s definition; at this point it does not yet contain <code>a</code>, so <code>a</code> gets resolved to the containing scope;</li>
<li>then you add <code>a</code>'s definition; at this point you already have <code>b</code>, and whether <code>a</code> means this <code>a</code> or the outer one is up to your language, as pointed out in ohter answers and comments (but you can resolve it either way).</li>
</ol>
<p>Just an idea. :)</p>

CC BY-SA 4.0
2023-09-15T14:53:40.953Z
2023-09-15T14:53:40.953Z
Pablo H
# Data structures for scopes and variable shadowing
Posted by: username_0 on 2023-09-14
Let's say I have some code in my target language like:
fun someFunction(arg1: Int, arg2: String) {
    var a = foo()
    if a < 10 {
        var b = a+1    
        var a = a+b+2  
        ...
    }    

The second a shadows the first one.
In my compiler, I created a Scope class to track names and their definitions. The scopes roughly correspond to the nodes in the abstract syntax tree (AST). Each scope has a map of name → info, and a pointer to its enclosing scope.

But my problem is that this data structure doesn't work well when I get shadowing like this. For example, in what Scope do you evaluate a+b+2? If it's in the function body scope, then it misses the b, if it's in the if's scope, then it gets the uninitialized a, not the outer shadowed one, which I think is what it should use.
Perhaps I have not modeled this correctly. Perhaps it's more accurate to say that each var declaration creates a new nested Scope, used by the code that comes after it in a given {...} block. So the scope tree has more nodes, and they do not so exactly correspond to AST nodes or curly brace blocks.

If I implement this, then many of my Scope objects would be nothing but a single variable, and looking up a name would be a linear walk up the linked list (stack) of scopes. Maybe that's fine, but I'm wondering if there are some standard data structures used in compilers that are better than this linked list stack approach.
I think I would make Scope an abstract class and so that some scopes with many names could use an internal hash table. Scopes for a class could be like this, while scopes created by local var declarations could have just the one name, and a different implementation of a virtual lookup(name) method.
**Tags:** compilers implementation semantics scoping
> **Comments:**
> **username_1**: Is allowing `var a = a+b+2` core to the language design here? Most block-structured languages have scoping rules that preclude this sort of construction, but yours doesn’t have to; it seems like your `var` is more like the `let … in …` construct typical in functional languages. The standard data structures are aligned with standard designs and you can borrow from them when that’s what you have, but we should check what it is that’s needed first.  
> **username_0**: Rust, for example, allows multiple let declarations that shadow each other, right in the same `{...}` block. Eg, you say `let x = 1;` and on the next line `let x = x+1` and that's a second `x` that will be 2. Other languages I've seen allow you shadow variables, but you need to at least be in a nested block. So, yes, I guess my `var` is like a `let ... in ...` but without the rightward drift that happens in some languages I've used.  
> **username_2**: JavaScript, for example, would generate an error for `let a = a + b + 2;` because the `let` binding shadows the outer `a` for the entire block, and you can't reference a variable before its initialization is complete.  
> **username_3**: Stacks go brrrr  
---
## 4 answers
### Answer by username_4 on 2023-09-14. Score: 7
This is actually a question about language semantics, not about scopes. Your data structure is correct in essence.
The question is if the languages introduces the inner var a before evaluating its initializer.
If you can choose yourself because it's your language, create an intermittent error declaration with the semantics of using it results in an "unitialized entity used" error.
If the language allows using the outer `a` in the inner initializer, then the natural implementation is to evaluate the initializer's AST before the variable declaration itself.

For local name resolution, I'd actually walk up the AST.
The number of reachable variable declarations and enclosing blocks is usually very small resulting in overall better performance than building chains of maps.
---
### Answer by username_5 on 2023-09-14. Score: 5
This is called a [persistent array](https://en.wikipedia.org/wiki/Persistent_array).

If you don't need the `Scope` object accessible after finishing processing a scope, you could just use one symbol table, modify the symbol table directly when entering a scope, but record the modifications so that you could undo the modifications in reversed order when exiting a scope. You could use a stack to store information about the current scope and its ancestors. And you only have information about these scopes. All other `Scope` objects are destroyed.

Each variable name could also be considered an independent stack. Without the following improvements, you may need a unified stack to record which variable names are modified, but the exact modifications are independent from each other.

Then if you want the `Scope` object available after exiting the scope, for each variable name, you could sort the modifications (shadow and unshadow) of the variable in the above process by time, and maintain them in a search tree. Each `Scope` is bound to a time (version id). The current state of a variable name is the new value in the latest modification of that variable name before the version id. When you want to create a subscope, create two version ids for entering and exiting the scope just after entering its parent scope, and create the appropriate modifications on the entering version, and undo modifications on the exiting version. The version ids could be created and compared in another shared tree, instead of just using integers, if you may create subscopes in non-sequential order. A parent scope itself should not be modified after a subscope is created, so the the new value on undo could just be a copy of the previous value and don't need to be updated.

The structure is like a simplified Euler tour tree. It is possible to also support modifying a parent scope while there are already subscopes, if used in combination with a full Euler tour tree, to replace undoing.

This is O(logn) time and O(1) space per operation, where n is the number of scopes, assuming variable names are prehashed and don't cost extra time for looking up the tree bound to that variable name.

Some improvements using vEB trees and constant time data structure for maintaining version ids could make it O(loglogn) per operation, though I doubt anyone would really want to implement it.

You could also just use a persistent search tree to store the symbol table, but with O(logn) space overhead per operation.
> **Comments:**
> **username_4** (2023-09-16): Are there non-research languages, where you can bind a name from a left local scope?  
> **username_5** (2023-09-17): @feldentm If you are asking about using a name after exiting a scope, I think classes might be a case, where the stack is the inheritance path. But it might be more practical to just copy the symbol table, as vtables already work like that, and it isn't very useful to create a new class after each member definition.  
---
### Answer by username_6 on 2023-09-15. Score: 3
The real issue, I would argue, is that there is no one-size-fits-all:

At module/file scope, you may have a large number of unique identifiers, especially counting the imported ones. Here, a map definitely makes sense.
At class/type scope, you may still have a fairly large number of identifiers. The Iterator trait (Rust) has a whooping ~75 methods at the time of writing, and it's one trait amongst many that a type may implement, coming on top of the inherent methods, and fields, of the type.
At function scope, you typically have only a handful of arguments and variables.

As a result, I think your idea of using a Scope interface, and a polymorphic implementation makes sense, so you can specialize based on the type of Scope.

For handling the variables (and arguments) of a function, I would argue for... a stack!
You are, in essence, already thinking of creating a stack of Scopes... it'll be much more efficient to have a single Scope with a stack of variables instead! You'll need a separate one, for popping, too:
class VariableScope(Scope):
    def __init__(self, parent: Scope):
        self.parent = parent
        self.variables: List[(String, ???)] = list()
        self.blocks: List[Int] = list()

    def enter_block(self):
        self.blocks.append(len(self.variables))

    def exit_block(self):
        before = self.blocks.pop()
        del self.variables[before:]

    def add_variable(self, name: String, data: ???):
        self.variables.append((name, data))

    def search_variable(self, name: String) -> Option[???]:
        for n, d in reversed(self.variables):
            if n == name:
                 return d

        return self.parent.search_variable(name)


Finally, with regard to your issue about var a := a + 1, it's just a matter of timing.
If you do not want the newly declared a to be visible in a + 1, insert it into the scope only after having resolved a + 1. That's all there is to it.
---
### Answer by username_7 on 2023-09-15. Score: 2
I assume the semantics of your language is that the function body is evaluated as if executed sequentially, one line after the other, the same as when reading text. Also, the meaning of names is given by the same order, plus scopes. (As opposed to, for example, code given just dependencies and letting compiler decide evaluation order.)

Perhaps you are thinking scopes as static, as expressed by the graph/drawing.

But perhaps you can solve this by *growing* scopes: e.g. for the `if` scope,

1. it starts empty,
2. then it contains `b`'s definition; at this point it does not yet contain `a`, so `a` gets resolved to the containing scope;
3. then you add `a`'s definition; at this point you already have `b`, and whether `a` means this `a` or the outer one is up to your language, as pointed out in ohter answers and comments (but you can resolve it either way).

Just an idea. :)
---
