site/resolving-and-binding.html

<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-type" content="text/html;charset=UTF-8" />
<title>Resolving and Binding &middot; Crafting Interpreters</title>

<!-- Tell mobile browsers we're optimized for them and they don't need to crop
     the viewport. -->
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<link rel="stylesheet" type="text/css" href="style.css" />

<!-- Oh, God, Source Code Pro is so beautiful it makes me want to cry. -->
<link href='https://fonts.googleapis.com/css?family=Source+Code+Pro:400|Source+Sans+Pro:300,400,600' rel='stylesheet' type='text/css'>

<link rel="icon" type="image/png" href="image/favicon.png" />
<script src="jquery-3.4.1.min.js"></script>
<script src="script.js"></script>

<!-- Google analytics -->
<script>
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');

  ga('create', 'UA-42804721-2', 'auto');
  ga('send', 'pageview');
</script>

</head>
<body id="top">

<!-- <div class="scrim"></div> -->
<nav class="wide">
  <a href="/"><img src="image/logotype.png" title="Crafting Interpreters"></a>
  <div class="contents">
<h3><a href="#top">Resolving and Binding<small>11</small></a></h3>

<ul>
    <li><a href="#static-scope"><small>11.1</small> Static Scope</a></li>
    <li><a href="#semantic-analysis"><small>11.2</small> Semantic Analysis</a></li>
    <li><a href="#a-resolver-class"><small>11.3</small> A Resolver Class</a></li>
    <li><a href="#interpreting-resolved-variables"><small>11.4</small> Interpreting Resolved Variables</a></li>
    <li><a href="#resolution-errors"><small>11.5</small> Resolution Errors</a></li>
    <li class="divider"></li>
    <li class="end-part"><a href="#challenges">Challenges</a></li>
</ul>


<div class="prev-next">
    <a href="functions.html" title="Functions" class="left">&larr;&nbsp;Previous</a>
    <a href="a-tree-walk-interpreter.html" title="A Tree-Walk Interpreter">&uarr;&nbsp;Up</a>
    <a href="classes.html" title="Classes" class="right">Next&nbsp;&rarr;</a>
</div>  </div>
</nav>

<nav class="narrow">
<a href="/"><img src="image/logotype.png" title="Crafting Interpreters"></a>
<a href="functions.html" title="Functions" class="prev">←</a>
<a href="classes.html" title="Classes" class="next">→</a>
</nav>

<div class="page">
<div class="nav-wrapper">
<nav class="floating">
  <a href="/"><img src="image/logotype.png" title="Crafting Interpreters"></a>
  <div class="expandable">
<h3><a href="#top">Resolving and Binding<small>11</small></a></h3>

<ul>
    <li><a href="#static-scope"><small>11.1</small> Static Scope</a></li>
    <li><a href="#semantic-analysis"><small>11.2</small> Semantic Analysis</a></li>
    <li><a href="#a-resolver-class"><small>11.3</small> A Resolver Class</a></li>
    <li><a href="#interpreting-resolved-variables"><small>11.4</small> Interpreting Resolved Variables</a></li>
    <li><a href="#resolution-errors"><small>11.5</small> Resolution Errors</a></li>
    <li class="divider"></li>
    <li class="end-part"><a href="#challenges">Challenges</a></li>
</ul>


<div class="prev-next">
    <a href="functions.html" title="Functions" class="left">&larr;&nbsp;Previous</a>
    <a href="a-tree-walk-interpreter.html" title="A Tree-Walk Interpreter">&uarr;&nbsp;Up</a>
    <a href="classes.html" title="Classes" class="right">Next&nbsp;&rarr;</a>
</div>  </div>
  <a id="expand-nav">≡</a>
</nav>
</div>

<article class="chapter">

  <div class="number">11</div>
  <h1>Resolving and Binding</h1>

<blockquote>
<p>Once in a while you find yourself in an odd situation. You get into it by
degrees and in the most natural way but, when you are right in the midst of
it, you are suddenly astonished and ask yourself how in the world it all came
about.</p>
<p><cite>Thor Heyerdahl, <em>Kon-Tiki</em></cite></p>
</blockquote>
<p>Oh, no! Our language implementation is taking on water! Way back when we <a href="statements-and-state.html">added
variables and blocks</a>, we had scoping nice and tight. But when we
<a href="functions.html">later added closures</a>, a hole opened in our formerly waterproof
interpreter. Most real programs are unlikely to slip through this hole, but as
language implementers, we take a sacred vow to care about correctness even in
the deepest, dampest corners of the semantics.</p>
<p>We will spend this entire chapter exploring that leak, and then carefully
patching it up. In the process, we will gain a more rigorous understanding of
lexical scoping as used by Lox and other languages in the C tradition. We&rsquo;ll
also get a chance to learn about <em>semantic analysis</em><span class="em">&mdash;</span>a powerful technique for
extracting meaning from the user&rsquo;s source code without having to run it.</p>
<h2><a href="#static-scope" id="static-scope"><small>11&#8202;.&#8202;1</small>Static Scope</a></h2>
<p>A quick refresher: Lox, like most modern languages, uses <em>lexical</em> scoping. This
means that you can figure out which declaration a variable name refers to just
by reading the text of the program. For example:</p>
<div class="codehilite"><pre><span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;outer&quot;</span>;
{
  <span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;inner&quot;</span>;
  <span class="k">print</span> <span class="i">a</span>;
}
</pre></div>
<p>Here, we know that the <code>a</code> being printed is the variable declared on the
previous line, and not the global one. Running the program doesn&rsquo;t<span class="em">&mdash;</span><em>can&rsquo;t</em><span class="em">&mdash;</span>affect this. The scope rules are part of the <em>static</em> semantics of the language,
which is why they&rsquo;re also called <em>static scope</em>.</p>
<p>I haven&rsquo;t spelled out those scope rules, but now is the time for <span
name="precise">precision</span>:</p>
<aside name="precise">
<p>This is still nowhere near as precise as a real language specification. Those
docs must be so explicit that even a Martian or an outright malicious programmer
would be forced to implement the correct semantics provided they followed the
letter of the spec.</p>
<p>That exactitude is important when a language may be implemented by competing
companies who want their product to be incompatible with the others to lock
customers onto their platform. For this book, we can thankfully ignore those
kinds of shady shenanigans.</p>
</aside>
<p><strong>A variable usage refers to the preceding declaration with the same name in the
innermost scope that encloses the expression where the variable is used.</strong></p>
<p>There&rsquo;s a lot to unpack in that:</p>
<ul>
<li>
<p>I say &ldquo;variable usage&rdquo; instead of &ldquo;variable expression&rdquo; to cover both
variable expressions and assignments. Likewise with &ldquo;expression where the
variable is used&rdquo;.</p>
</li>
<li>
<p>&ldquo;Preceding&rdquo; means appearing before <em>in the program text</em>.</p>
<div class="codehilite"><pre><span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;outer&quot;</span>;
{
  <span class="k">print</span> <span class="i">a</span>;
  <span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;inner&quot;</span>;
}
</pre></div>
<p>Here, the <code>a</code> being printed is the outer one since it appears <span
name="hoisting">before</span> the <code>print</code> statement that uses it. In most
cases, in straight line code, the declaration preceding in <em>text</em> will also
precede the usage in <em>time</em>. But that&rsquo;s not always true. As we&rsquo;ll see,
functions may defer a chunk of code such that its <em>dynamic temporal</em>
execution no longer mirrors the <em>static textual</em> ordering.</p>
<aside name="hoisting">
<p>In JavaScript, variables declared using <code>var</code> are implicitly &ldquo;hoisted&rdquo; to
the beginning of the block. Any use of that name in the block will refer to
that variable, even if the use appears before the declaration. When you
write this in JavaScript:</p>
<div class="codehilite"><pre>{
  <span class="i">console</span>.<span class="i">log</span>(<span class="i">a</span>);
  <span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;value&quot;</span>;
}
</pre></div>
<p>It behaves like:</p>
<div class="codehilite"><pre>{
  <span class="k">var</span> <span class="i">a</span>; <span class="c">// Hoist.</span>
  <span class="i">console</span>.<span class="i">log</span>(<span class="i">a</span>);
  <span class="i">a</span> = <span class="s">&quot;value&quot;</span>;
}
</pre></div>
<p>That means that in some cases you can read a variable before its initializer
has run<span class="em">&mdash;</span>an annoying source of bugs. The alternate <code>let</code> syntax for
declaring variables was added later to address this problem.</p>
</aside></li>
<li>
<p>&ldquo;Innermost&rdquo; is there because of our good friend shadowing. There may be more
than one variable with the given name in enclosing scopes, as in:</p>
<div class="codehilite"><pre><span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;outer&quot;</span>;
{
  <span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;inner&quot;</span>;
  <span class="k">print</span> <span class="i">a</span>;
}
</pre></div>
<p>Our rule disambiguates this case by saying the innermost scope wins.</p>
</li>
</ul>
<p>Since this rule makes no mention of any runtime behavior, it implies that a
variable expression always refers to the same declaration through the entire
execution of the program. Our interpreter so far <em>mostly</em> implements the rule
correctly. But when we added closures, an error snuck in.</p>
<div class="codehilite"><pre><span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;global&quot;</span>;
{
  <span class="k">fun</span> <span class="i">showA</span>() {
    <span class="k">print</span> <span class="i">a</span>;
  }

  <span class="i">showA</span>();
  <span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;block&quot;</span>;
  <span class="i">showA</span>();
}
</pre></div>
<p><span name="tricky">Before</span> you type this in and run it, decide what you
think it <em>should</em> print.</p>
<aside name="tricky">
<p>I know, it&rsquo;s a totally pathological, contrived program. It&rsquo;s just <em>weird</em>. No
reasonable person would ever write code like this. Alas, more of your life than
you&rsquo;d expect will be spent dealing with bizarro snippets of code like this if
you stay in the programming language game for long.</p>
</aside>
<p>OK<span class="ellipse">&thinsp;.&thinsp;.&thinsp;.&nbsp;</span>got it? If you&rsquo;re familiar with closures in other languages, you&rsquo;ll expect
it to print &ldquo;global&rdquo; twice. The first call to <code>showA()</code> should definitely print
&ldquo;global&rdquo; since we haven&rsquo;t even reached the declaration of the inner <code>a</code> yet. And
by our rule that a variable expression always resolves to the same variable,
that implies the second call to <code>showA()</code> should print the same thing.</p>
<p>Alas, it prints:</p>
<div class="codehilite"><pre>global
block
</pre></div>
<p>Let me stress that this program never reassigns any variable and contains only a
single <code>print</code> statement. Yet, somehow, that <code>print</code> statement for a
never-assigned variable prints two different values at different points in time.
We definitely broke something somewhere.</p>
<h3><a href="#scopes-and-mutable-environments" id="scopes-and-mutable-environments"><small>11&#8202;.&#8202;1&#8202;.&#8202;1</small>Scopes and mutable environments</a></h3>
<p>In our interpreter, environments are the dynamic manifestation of static scopes.
The two mostly stay in sync with each other<span class="em">&mdash;</span>we create a new environment when
we enter a new scope, and discard it when we leave the scope. There is one other
operation we perform on environments: binding a variable in one. This is where
our bug lies.</p>
<p>Let&rsquo;s walk through that problematic example and see what the environments look
like at each step. First, we declare <code>a</code> in the global scope.</p><img src="image/resolving-and-binding/environment-1.png" alt="The global environment with 'a' defined in it." />
<p>That gives us a single environment with a single variable in it. Then we enter
the block and execute the declaration of <code>showA()</code>.</p><img src="image/resolving-and-binding/environment-2.png" alt="A block environment linking to the global one." />
<p>We get a new environment for the block. In that, we declare one name, <code>showA</code>,
which is bound to the LoxFunction object we create to represent the function.
That object has a <code>closure</code> field that captures the environment where the
function was declared, so it has a reference back to the environment for the
block.</p>
<p>Now we call <code>showA()</code>.</p><img src="image/resolving-and-binding/environment-3.png" alt="An empty environment for showA()'s body linking to the previous two. 'a' is resolved in the global environment." />
<p>The interpreter dynamically creates a new environment for the function body of
<code>showA()</code>. It&rsquo;s empty since that function doesn&rsquo;t declare any variables. The
parent of that environment is the function&rsquo;s closure<span class="em">&mdash;</span>the outer block
environment.</p>
<p>Inside the body of <code>showA()</code>, we print the value of <code>a</code>. The interpreter looks
up this value by walking the chain of environments. It gets all the way
to the global environment before finding it there and printing <code>"global"</code>.
Great.</p>
<p>Next, we declare the second <code>a</code>, this time inside the block.</p><img src="image/resolving-and-binding/environment-4.png" alt="The block environment has both 'a' and 'showA' now." />
<p>It&rsquo;s in the same block<span class="em">&mdash;</span>the same scope<span class="em">&mdash;</span>as <code>showA()</code>, so it goes into the
same environment, which is also the same environment <code>showA()</code>&rsquo;s closure refers
to. This is where it gets interesting. We call <code>showA()</code> again.</p><img src="image/resolving-and-binding/environment-5.png" alt="An empty environment for showA()'s body linking to the previous two. 'a' is resolved in the block environment." />
<p>We create a new empty environment for the body of <code>showA()</code> again, wire it up to
that closure, and run the body. When the interpreter walks the chain of
environments to find <code>a</code>, it now discovers the <em>new</em> <code>a</code> in the block
environment. Boo.</p>
<p>I chose to implement environments in a way that I hoped would agree with your
informal intuition around scopes. We tend to consider all of the code within a
block as being within the same scope, so our interpreter uses a single
environment to represent that. Each environment is a mutable hash table. When a
new local variable is declared, it gets added to the existing environment for
that scope.</p>
<p>That intuition, like many in life, isn&rsquo;t quite right. A block is not necessarily
all the same scope. Consider:</p>
<div class="codehilite"><pre>{
  <span class="k">var</span> <span class="i">a</span>;
  <span class="c">// 1.</span>
  <span class="k">var</span> <span class="i">b</span>;
  <span class="c">// 2.</span>
}
</pre></div>
<p>At the first marked line, only <code>a</code> is in scope. At the second line, both <code>a</code> and
<code>b</code> are. If you define a &ldquo;scope&rdquo; to be a set of declarations, then those are
clearly not the same scope<span class="em">&mdash;</span>they don&rsquo;t contain the same declarations. It&rsquo;s
like each <code>var</code> statement <span name="split">splits</span> the block into two
separate scopes, the scope before the variable is declared and the one after,
which includes the new variable.</p>
<aside name="split">
<p>Some languages make this split explicit. In Scheme and ML, when you declare a
local variable using <code>let</code>, you also delineate the subsequent code where the new
variable is in scope. There is no implicit &ldquo;rest of the block&rdquo;.</p>
</aside>
<p>But in our implementation, environments do act like the entire block is one
scope, just a scope that changes over time. Closures do not like that. When a
function is declared, it captures a reference to the current environment. The
function <em>should</em> capture a frozen snapshot of the environment <em>as it existed at
the moment the function was declared</em>. But instead, in the Java code, it has a
reference to the actual mutable environment object. When a variable is later
declared in the scope that environment corresponds to, the closure sees the new
variable, even though the declaration does <em>not</em> precede the function.</p>
<h3><a href="#persistent-environments" id="persistent-environments"><small>11&#8202;.&#8202;1&#8202;.&#8202;2</small>Persistent environments</a></h3>
<p>There is a style of programming that uses what are called <strong>persistent data
structures</strong>. Unlike the squishy data structures you&rsquo;re familiar with in
imperative programming, a persistent data structure can never be directly
modified. Instead, any &ldquo;modification&rdquo; to an existing structure produces a <span
name="copy">brand</span> new object that contains all of the original data and
the new modification. The original is left unchanged.</p>
<aside name="copy">
<p>This sounds like it might waste tons of memory and time copying the structure
for each operation. In practice, persistent data structures share most of their
data between the different &ldquo;copies&rdquo;.</p>
</aside>
<p>If we were to apply that technique to Environment, then every time you declared
a variable it would return a <em>new</em> environment that contained all of the
previously declared variables along with the one new name. Declaring a variable
would do the implicit &ldquo;split&rdquo; where you have an environment before the variable
is declared and one after:</p><img src="image/resolving-and-binding/split.png" alt="Separate environments before and after the variable is declared." />
<p>A closure retains a reference to the Environment instance in play when the
function was declared. Since any later declarations in that block would produce
new Environment objects, the closure wouldn&rsquo;t see the new variables and our bug
would be fixed.</p>
<p>This is a legit way to solve the problem, and it&rsquo;s the classic way to implement
environments in Scheme interpreters. We could do that for Lox, but it would mean
going back and changing a pile of existing code.</p>
<p>I won&rsquo;t drag you through that. We&rsquo;ll keep the way we represent environments the
same. Instead of making the data more statically structured, we&rsquo;ll bake the
static resolution into the access <em>operation</em> itself.</p>
<h2><a href="#semantic-analysis" id="semantic-analysis"><small>11&#8202;.&#8202;2</small>Semantic Analysis</a></h2>
<p>Our interpreter <strong>resolves</strong> a variable<span class="em">&mdash;</span>tracks down which declaration it
refers to<span class="em">&mdash;</span>each and every time the variable expression is evaluated. If that
variable is swaddled inside a loop that runs a thousand times, that variable
gets re-resolved a thousand times.</p>
<p>We know static scope means that a variable usage always resolves to the same
declaration, which can be determined just by looking at the text. Given that,
why are we doing it dynamically every time? Doing so doesn&rsquo;t just open the hole
that leads to our annoying bug, it&rsquo;s also needlessly slow.</p>
<p>A better solution is to resolve each variable use <em>once</em>. Write a chunk of code
that inspects the user&rsquo;s program, finds every variable mentioned, and figures
out which declaration each refers to. This process is an example of a <strong>semantic
analysis</strong>. Where a parser tells only if a program is grammatically correct (a
<em>syntactic</em> analysis), semantic analysis goes farther and starts to figure out
what pieces of the program actually mean. In this case, our analysis will
resolve variable bindings. We&rsquo;ll know not just that an expression <em>is</em> a
variable, but <em>which</em> variable it is.</p>
<p>There are a lot of ways we could store the binding between a variable and its
declaration. When we get to the C interpreter for Lox, we&rsquo;ll have a <em>much</em> more
efficient way of storing and accessing local variables. But for jlox, I want to
minimize the collateral damage we inflict on our existing codebase. I&rsquo;d hate to
throw out a bunch of mostly fine code.</p>
<p>Instead, we&rsquo;ll store the resolution in a way that makes the most out of our
existing Environment class. Recall how the accesses of <code>a</code> are interpreted in
the problematic example.</p><img src="image/resolving-and-binding/environment-3.png" alt="An empty environment for showA()'s body linking to the previous two. 'a' is resolved in the global environment." />
<p>In the first (correct) evaluation, we look at three environments in the chain
before finding the global declaration of <code>a</code>. Then, when the inner <code>a</code> is later
declared in a block scope, it shadows the global one.</p><img src="image/resolving-and-binding/environment-5.png" alt="An empty environment for showA()'s body linking to the previous two. 'a' is resolved in the block environment." />
<p>The next lookup walks the chain, finds <code>a</code> in the <em>second</em> environment and
stops there. Each environment corresponds to a single lexical scope where
variables are declared. If we could ensure a variable lookup always walked the
<em>same</em> number of links in the environment chain, that would ensure that it
found the same variable in the same scope every time.</p>
<p>To &ldquo;resolve&rdquo; a variable usage, we only need to calculate how many &ldquo;hops&rdquo; away
the declared variable will be in the environment chain. The interesting question
is <em>when</em> to do this calculation<span class="em">&mdash;</span>or, put differently, where in our
interpreter&rsquo;s implementation do we stuff the code for it?</p>
<p>Since we&rsquo;re calculating a static property based on the structure of the source
code, the obvious answer is in the parser. That is the traditional home, and is
where we&rsquo;ll put it later in clox. It would work here too, but I want an excuse to
show you another technique. We&rsquo;ll write our resolver as a separate pass.</p>
<h3><a href="#a-variable-resolution-pass" id="a-variable-resolution-pass"><small>11&#8202;.&#8202;2&#8202;.&#8202;1</small>A variable resolution pass</a></h3>
<p>After the parser produces the syntax tree, but before the interpreter starts
executing it, we&rsquo;ll do a single walk over the tree to resolve all of the
variables it contains. Additional passes between parsing and execution are
common. If Lox had static types, we could slide a type checker in there.
Optimizations are often implemented in separate passes like this too. Basically,
any work that doesn&rsquo;t rely on state that&rsquo;s only available at runtime can be done
in this way.</p>
<p>Our variable resolution pass works like a sort of mini-interpreter. It walks the
tree, visiting each node, but a static analysis is different from a dynamic
execution:</p>
<ul>
<li>
<p><strong>There are no side effects.</strong> When the static analysis visits a print
statement, it doesn&rsquo;t actually print anything. Calls to native functions or
other operations that reach out to the outside world are stubbed out and
have no effect.</p>
</li>
<li>
<p><strong>There is no control flow.</strong> Loops are visited only <span
name="fix">once</span>. Both branches are visited in <code>if</code> statements. Logic
operators are not short-circuited.</p>
</li>
</ul>
<aside name="fix">
<p>Variable resolution touches each node once, so its performance is <em>O(n)</em> where
<em>n</em> is the number of syntax tree nodes. More sophisticated analyses may have
greater complexity, but most are carefully designed to be linear or not far from
it. It&rsquo;s an embarrassing faux pas if your compiler gets exponentially slower as
the user&rsquo;s program grows.</p>
</aside>
<h2><a href="#a-resolver-class" id="a-resolver-class"><small>11&#8202;.&#8202;3</small>A Resolver Class</a></h2>
<p>Like everything in Java, our variable resolution pass is embodied in a class.</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
create new file</div>
<pre><span class="k">package</span> <span class="i">com.craftinginterpreters.lox</span>;

<span class="k">import</span> <span class="i">java.util.HashMap</span>;
<span class="k">import</span> <span class="i">java.util.List</span>;
<span class="k">import</span> <span class="i">java.util.Map</span>;
<span class="k">import</span> <span class="i">java.util.Stack</span>;

<span class="k">class</span> <span class="t">Resolver</span> <span class="k">implements</span> <span class="t">Expr</span>.<span class="t">Visitor</span>&lt;<span class="t">Void</span>&gt;, <span class="t">Stmt</span>.<span class="t">Visitor</span>&lt;<span class="t">Void</span>&gt; {
  <span class="k">private</span> <span class="k">final</span> <span class="t">Interpreter</span> <span class="i">interpreter</span>;

  <span class="t">Resolver</span>(<span class="t">Interpreter</span> <span class="i">interpreter</span>) {
    <span class="k">this</span>.<span class="i">interpreter</span> = <span class="i">interpreter</span>;
  }
}
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, create new file</div>

<p>Since the resolver needs to visit every node in the syntax tree, it implements
the visitor abstraction we already have in place. Only a few kinds of nodes are
interesting when it comes to resolving variables:</p>
<ul>
<li>
<p>A block statement introduces a new scope for the statements it contains.</p>
</li>
<li>
<p>A function declaration introduces a new scope for its body and binds its
parameters in that scope.</p>
</li>
<li>
<p>A variable declaration adds a new variable to the current scope.</p>
</li>
<li>
<p>Variable and assignment expressions need to have their variables resolved.</p>
</li>
</ul>
<p>The rest of the nodes don&rsquo;t do anything special, but we still need to implement
visit methods for them that traverse into their subtrees. Even though a <code>+</code>
expression doesn&rsquo;t <em>itself</em> have any variables to resolve, either of its
operands might.</p>
<h3><a href="#resolving-blocks" id="resolving-blocks"><small>11&#8202;.&#8202;3&#8202;.&#8202;1</small>Resolving blocks</a></h3>
<p>We start with blocks since they create the local scopes where all the magic
happens.</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>Resolver</em>()</div>
<pre>  <span class="a">@Override</span>
  <span class="k">public</span> <span class="t">Void</span> <span class="i">visitBlockStmt</span>(<span class="t">Stmt</span>.<span class="t">Block</span> <span class="i">stmt</span>) {
    <span class="i">beginScope</span>();
    <span class="i">resolve</span>(<span class="i">stmt</span>.<span class="i">statements</span>);
    <span class="i">endScope</span>();
    <span class="k">return</span> <span class="k">null</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>Resolver</em>()</div>

<p>This begins a new scope, traverses into the statements inside the block, and
then discards the scope. The fun stuff lives in those helper methods. We start
with the simple one.</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>Resolver</em>()</div>
<pre>  <span class="t">void</span> <span class="i">resolve</span>(<span class="t">List</span>&lt;<span class="t">Stmt</span>&gt; <span class="i">statements</span>) {
    <span class="k">for</span> (<span class="t">Stmt</span> <span class="i">statement</span> : <span class="i">statements</span>) {
      <span class="i">resolve</span>(<span class="i">statement</span>);
    }
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>Resolver</em>()</div>

<p>This walks a list of statements and resolves each one. It in turn calls:</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>visitBlockStmt</em>()</div>
<pre>  <span class="k">private</span> <span class="t">void</span> <span class="i">resolve</span>(<span class="t">Stmt</span> <span class="i">stmt</span>) {
    <span class="i">stmt</span>.<span class="i">accept</span>(<span class="k">this</span>);
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>visitBlockStmt</em>()</div>

<p>While we&rsquo;re at it, let&rsquo;s add another overload that we&rsquo;ll need later for
resolving an expression.</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>resolve</em>(Stmt stmt)</div>
<pre>  <span class="k">private</span> <span class="t">void</span> <span class="i">resolve</span>(<span class="t">Expr</span> <span class="i">expr</span>) {
    <span class="i">expr</span>.<span class="i">accept</span>(<span class="k">this</span>);
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>resolve</em>(Stmt stmt)</div>

<p>These methods are similar to the <code>evaluate()</code> and <code>execute()</code> methods in
Interpreter<span class="em">&mdash;</span>they turn around and apply the Visitor pattern to the given
syntax tree node.</p>
<p>The real interesting behavior is around scopes. A new block scope is created
like so:</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>resolve</em>()</div>
<pre>  <span class="k">private</span> <span class="t">void</span> <span class="i">beginScope</span>() {
    <span class="i">scopes</span>.<span class="i">push</span>(<span class="k">new</span> <span class="t">HashMap</span>&lt;<span class="t">String</span>, <span class="t">Boolean</span>&gt;());
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>resolve</em>()</div>

<p>Lexical scopes nest in both the interpreter and the resolver. They behave like a
stack. The interpreter implements that stack using a linked list<span class="em">&mdash;</span>the chain of
Environment objects. In the resolver, we use an actual Java Stack.</p>
<div class="codehilite"><pre class="insert-before">  private final Interpreter interpreter;
</pre><div class="source-file"><em>lox/Resolver.java</em><br>
in class <em>Resolver</em></div>
<pre class="insert">  <span class="k">private</span> <span class="k">final</span> <span class="t">Stack</span>&lt;<span class="t">Map</span>&lt;<span class="t">String</span>, <span class="t">Boolean</span>&gt;&gt; <span class="i">scopes</span> = <span class="k">new</span> <span class="t">Stack</span>&lt;&gt;();
</pre><pre class="insert-after">

  Resolver(Interpreter interpreter) {
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, in class <em>Resolver</em></div>

<p>This field keeps track of the stack of scopes currently, uh, in scope. Each
element in the stack is a Map representing a single block scope. Keys, as in
Environment, are variable names. The values are Booleans, for a reason I&rsquo;ll
explain soon.</p>
<p>The scope stack is only used for local block scopes. Variables declared at the
top level in the global scope are not tracked by the resolver since they are
more dynamic in Lox. When resolving a variable, if we can&rsquo;t find it in the stack
of local scopes, we assume it must be global.</p>
<p>Since scopes are stored in an explicit stack, exiting one is straightforward.</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>beginScope</em>()</div>
<pre>  <span class="k">private</span> <span class="t">void</span> <span class="i">endScope</span>() {
    <span class="i">scopes</span>.<span class="i">pop</span>();
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>beginScope</em>()</div>

<p>Now we can push and pop a stack of empty scopes. Let&rsquo;s put some things in them.</p>
<h3><a href="#resolving-variable-declarations" id="resolving-variable-declarations"><small>11&#8202;.&#8202;3&#8202;.&#8202;2</small>Resolving variable declarations</a></h3>
<p>Resolving a variable declaration adds a new entry to the current innermost
scope&rsquo;s map. That seems simple, but there&rsquo;s a little dance we need to do.</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>visitBlockStmt</em>()</div>
<pre>  <span class="a">@Override</span>
  <span class="k">public</span> <span class="t">Void</span> <span class="i">visitVarStmt</span>(<span class="t">Stmt</span>.<span class="t">Var</span> <span class="i">stmt</span>) {
    <span class="i">declare</span>(<span class="i">stmt</span>.<span class="i">name</span>);
    <span class="k">if</span> (<span class="i">stmt</span>.<span class="i">initializer</span> != <span class="k">null</span>) {
      <span class="i">resolve</span>(<span class="i">stmt</span>.<span class="i">initializer</span>);
    }
    <span class="i">define</span>(<span class="i">stmt</span>.<span class="i">name</span>);
    <span class="k">return</span> <span class="k">null</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>visitBlockStmt</em>()</div>

<p>We split binding into two steps, declaring then defining, in order to handle
funny edge cases like this:</p>
<div class="codehilite"><pre><span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;outer&quot;</span>;
{
  <span class="k">var</span> <span class="i">a</span> = <span class="i">a</span>;
}
</pre></div>
<p>What happens when the initializer for a local variable refers to a variable with
the same name as the variable being declared? We have a few options:</p>
<ol>
<li>
<p><strong>Run the initializer, then put the new variable in scope.</strong> Here, the new
local <code>a</code> would be initialized with &ldquo;outer&rdquo;, the value of the <em>global</em> one.
In other words, the previous declaration would desugar to:</p>
<div class="codehilite"><pre><span class="k">var</span> <span class="i">temp</span> = <span class="i">a</span>; <span class="c">// Run the initializer.</span>
<span class="k">var</span> <span class="i">a</span>;        <span class="c">// Declare the variable.</span>
<span class="i">a</span> = <span class="i">temp</span>;     <span class="c">// Initialize it.</span>
</pre></div>
</li>
<li>
<p><strong>Put the new variable in scope, then run the initializer.</strong> This means you
could observe a variable before it&rsquo;s initialized, so we would need to figure
out what value it would have then. Probably <code>nil</code>. That means the new local
<code>a</code> would be re-initialized to its own implicitly initialized value, <code>nil</code>.
Now the desugaring would look like:</p>
<div class="codehilite"><pre><span class="k">var</span> <span class="i">a</span>; <span class="c">// Define the variable.</span>
<span class="i">a</span> = <span class="i">a</span>; <span class="c">// Run the initializer.</span>
</pre></div>
</li>
<li>
<p><strong>Make it an error to reference a variable in its initializer.</strong> Have the
interpreter fail either at compile time or runtime if an initializer
mentions the variable being initialized.</p>
</li>
</ol>
<p>Do either of those first two options look like something a user actually
<em>wants</em>? Shadowing is rare and often an error, so initializing a shadowing
variable based on the value of the shadowed one seems unlikely to be deliberate.</p>
<p>The second option is even less useful. The new variable will <em>always</em> have the
value <code>nil</code>. There is never any point in mentioning it by name. You could use an
explicit <code>nil</code> instead.</p>
<p>Since the first two options are likely to mask user errors, we&rsquo;ll take the
third. Further, we&rsquo;ll make it a compile error instead of a runtime one. That
way, the user is alerted to the problem before any code is run.</p>
<p>In order to do that, as we visit expressions, we need to know if we&rsquo;re inside
the initializer for some variable. We do that by splitting binding into two
steps. The first is <strong>declaring</strong> it.</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>endScope</em>()</div>
<pre>  <span class="k">private</span> <span class="t">void</span> <span class="i">declare</span>(<span class="t">Token</span> <span class="i">name</span>) {
    <span class="k">if</span> (<span class="i">scopes</span>.<span class="i">isEmpty</span>()) <span class="k">return</span>;

    <span class="t">Map</span>&lt;<span class="t">String</span>, <span class="t">Boolean</span>&gt; <span class="i">scope</span> = <span class="i">scopes</span>.<span class="i">peek</span>();
    <span class="i">scope</span>.<span class="i">put</span>(<span class="i">name</span>.<span class="i">lexeme</span>, <span class="k">false</span>);
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>endScope</em>()</div>

<p>Declaration adds the variable to the innermost scope so that it shadows any
outer one and so that we know the variable exists. We mark it as &ldquo;not ready yet&rdquo;
by binding its name to <code>false</code> in the scope map. The value associated with a key
in the scope map represents whether or not we have finished resolving that
variable&rsquo;s initializer.</p>
<p>After declaring the variable, we resolve its initializer expression in that same
scope where the new variable now exists but is unavailable. Once the initializer
expression is done, the variable is ready for prime time. We do that by
<strong>defining</strong> it.</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>declare</em>()</div>
<pre>  <span class="k">private</span> <span class="t">void</span> <span class="i">define</span>(<span class="t">Token</span> <span class="i">name</span>) {
    <span class="k">if</span> (<span class="i">scopes</span>.<span class="i">isEmpty</span>()) <span class="k">return</span>;
    <span class="i">scopes</span>.<span class="i">peek</span>().<span class="i">put</span>(<span class="i">name</span>.<span class="i">lexeme</span>, <span class="k">true</span>);
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>declare</em>()</div>

<p>We set the variable&rsquo;s value in the scope map to <code>true</code> to mark it as fully
initialized and available for use. It&rsquo;s alive! </p>
<h3><a href="#resolving-variable-expressions" id="resolving-variable-expressions"><small>11&#8202;.&#8202;3&#8202;.&#8202;3</small>Resolving variable expressions</a></h3>
<p>Variable declarations<span class="em">&mdash;</span>and function declarations, which we&rsquo;ll get to<span class="em">&mdash;</span>write
to the scope maps. Those maps are read when we resolve variable expressions.</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>visitVarStmt</em>()</div>
<pre>  <span class="a">@Override</span>
  <span class="k">public</span> <span class="t">Void</span> <span class="i">visitVariableExpr</span>(<span class="t">Expr</span>.<span class="t">Variable</span> <span class="i">expr</span>) {
    <span class="k">if</span> (!<span class="i">scopes</span>.<span class="i">isEmpty</span>() &amp;&amp;
        <span class="i">scopes</span>.<span class="i">peek</span>().<span class="i">get</span>(<span class="i">expr</span>.<span class="i">name</span>.<span class="i">lexeme</span>) == <span class="t">Boolean</span>.<span class="i">FALSE</span>) {
      <span class="t">Lox</span>.<span class="i">error</span>(<span class="i">expr</span>.<span class="i">name</span>,
          <span class="s">&quot;Can&#39;t read local variable in its own initializer.&quot;</span>);
    }

    <span class="i">resolveLocal</span>(<span class="i">expr</span>, <span class="i">expr</span>.<span class="i">name</span>);
    <span class="k">return</span> <span class="k">null</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>visitVarStmt</em>()</div>

<p>First, we check to see if the variable is being accessed inside its own
initializer. This is where the values in the scope map come into play. If the
variable exists in the current scope but its value is <code>false</code>, that means we
have declared it but not yet defined it. We report that error.</p>
<p>After that check, we actually resolve the variable itself using this helper:</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>define</em>()</div>
<pre>  <span class="k">private</span> <span class="t">void</span> <span class="i">resolveLocal</span>(<span class="t">Expr</span> <span class="i">expr</span>, <span class="t">Token</span> <span class="i">name</span>) {
    <span class="k">for</span> (<span class="t">int</span> <span class="i">i</span> = <span class="i">scopes</span>.<span class="i">size</span>() - <span class="n">1</span>; <span class="i">i</span> &gt;= <span class="n">0</span>; <span class="i">i</span>--) {
      <span class="k">if</span> (<span class="i">scopes</span>.<span class="i">get</span>(<span class="i">i</span>).<span class="i">containsKey</span>(<span class="i">name</span>.<span class="i">lexeme</span>)) {
        <span class="i">interpreter</span>.<span class="i">resolve</span>(<span class="i">expr</span>, <span class="i">scopes</span>.<span class="i">size</span>() - <span class="n">1</span> - <span class="i">i</span>);
        <span class="k">return</span>;
      }
    }
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>define</em>()</div>

<p>This looks, for good reason, a lot like the code in Environment for evaluating a
variable. We start at the innermost scope and work outwards, looking in each map
for a matching name. If we find the variable, we resolve it, passing in the
number of scopes between the current innermost scope and the scope where the
variable was found. So, if the variable was found in the current scope, we
pass in 0. If it&rsquo;s in the immediately enclosing scope, 1. You get the idea.</p>
<p>If we walk through all of the block scopes and never find the variable, we leave
it unresolved and assume it&rsquo;s global. We&rsquo;ll get to the implementation of that
<code>resolve()</code> method a little later. For now, let&rsquo;s keep on cranking through the
other syntax nodes.</p>
<h3><a href="#resolving-assignment-expressions" id="resolving-assignment-expressions"><small>11&#8202;.&#8202;3&#8202;.&#8202;4</small>Resolving assignment expressions</a></h3>
<p>The other expression that references a variable is assignment. Resolving one
looks like this:</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>visitVarStmt</em>()</div>
<pre>  <span class="a">@Override</span>
  <span class="k">public</span> <span class="t">Void</span> <span class="i">visitAssignExpr</span>(<span class="t">Expr</span>.<span class="t">Assign</span> <span class="i">expr</span>) {
    <span class="i">resolve</span>(<span class="i">expr</span>.<span class="i">value</span>);
    <span class="i">resolveLocal</span>(<span class="i">expr</span>, <span class="i">expr</span>.<span class="i">name</span>);
    <span class="k">return</span> <span class="k">null</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>visitVarStmt</em>()</div>

<p>First, we resolve the expression for the assigned value in case it also contains
references to other variables. Then we use our existing <code>resolveLocal()</code> method
to resolve the variable that&rsquo;s being assigned to.</p>
<h3><a href="#resolving-function-declarations" id="resolving-function-declarations"><small>11&#8202;.&#8202;3&#8202;.&#8202;5</small>Resolving function declarations</a></h3>
<p>Finally, functions. Functions both bind names and introduce a scope. The name of
the function itself is bound in the surrounding scope where the function is
declared. When we step into the function&rsquo;s body, we also bind its parameters
into that inner function scope.</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>visitBlockStmt</em>()</div>
<pre>  <span class="a">@Override</span>
  <span class="k">public</span> <span class="t">Void</span> <span class="i">visitFunctionStmt</span>(<span class="t">Stmt</span>.<span class="t">Function</span> <span class="i">stmt</span>) {
    <span class="i">declare</span>(<span class="i">stmt</span>.<span class="i">name</span>);
    <span class="i">define</span>(<span class="i">stmt</span>.<span class="i">name</span>);

    <span class="i">resolveFunction</span>(<span class="i">stmt</span>);
    <span class="k">return</span> <span class="k">null</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>visitBlockStmt</em>()</div>

<p>Similar to <code>visitVariableStmt()</code>, we declare and define the name of the function
in the current scope. Unlike variables, though, we define the name eagerly,
before resolving the function&rsquo;s body. This lets a function recursively refer to
itself inside its own body.</p>
<p>Then we resolve the function&rsquo;s body using this:</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>resolve</em>()</div>
<pre>  <span class="k">private</span> <span class="t">void</span> <span class="i">resolveFunction</span>(<span class="t">Stmt</span>.<span class="t">Function</span> <span class="i">function</span>) {
    <span class="i">beginScope</span>();
    <span class="k">for</span> (<span class="t">Token</span> <span class="i">param</span> : <span class="i">function</span>.<span class="i">params</span>) {
      <span class="i">declare</span>(<span class="i">param</span>);
      <span class="i">define</span>(<span class="i">param</span>);
    }
    <span class="i">resolve</span>(<span class="i">function</span>.<span class="i">body</span>);
    <span class="i">endScope</span>();
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>resolve</em>()</div>

<p>It&rsquo;s a separate method since we will also use it for resolving Lox methods when
we add classes later. It creates a new scope for the body and then binds
variables for each of the function&rsquo;s parameters.</p>
<p>Once that&rsquo;s ready, it resolves the function body in that scope. This is
different from how the interpreter handles function declarations. At <em>runtime</em>,
declaring a function doesn&rsquo;t do anything with the function&rsquo;s body. The body
doesn&rsquo;t get touched until later when the function is called. In a <em>static</em>
analysis, we immediately traverse into the body right then and there.</p>
<h3><a href="#resolving-the-other-syntax-tree-nodes" id="resolving-the-other-syntax-tree-nodes"><small>11&#8202;.&#8202;3&#8202;.&#8202;6</small>Resolving the other syntax tree nodes</a></h3>
<p>That covers the interesting corners of the grammars. We handle every place where
a variable is declared, read, or written, and every place where a scope is
created or destroyed. Even though they aren&rsquo;t affected by variable resolution,
we also need visit methods for all of the other syntax tree nodes in order to
recurse into their subtrees. <span name="boring">Sorry</span> this bit is
boring, but bear with me. We&rsquo;ll go kind of &ldquo;top down&rdquo; and start with statements.</p>
<aside name="boring">
<p>I did say the book would have every single line of code for these interpreters.
I didn&rsquo;t say they&rsquo;d all be exciting.</p>
</aside>
<p>An expression statement contains a single expression to traverse.</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>visitBlockStmt</em>()</div>
<pre>  <span class="a">@Override</span>
  <span class="k">public</span> <span class="t">Void</span> <span class="i">visitExpressionStmt</span>(<span class="t">Stmt</span>.<span class="t">Expression</span> <span class="i">stmt</span>) {
    <span class="i">resolve</span>(<span class="i">stmt</span>.<span class="i">expression</span>);
    <span class="k">return</span> <span class="k">null</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>visitBlockStmt</em>()</div>

<p>An if statement has an expression for its condition and one or two statements
for the branches.</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>visitFunctionStmt</em>()</div>
<pre>  <span class="a">@Override</span>
  <span class="k">public</span> <span class="t">Void</span> <span class="i">visitIfStmt</span>(<span class="t">Stmt</span>.<span class="t">If</span> <span class="i">stmt</span>) {
    <span class="i">resolve</span>(<span class="i">stmt</span>.<span class="i">condition</span>);
    <span class="i">resolve</span>(<span class="i">stmt</span>.<span class="i">thenBranch</span>);
    <span class="k">if</span> (<span class="i">stmt</span>.<span class="i">elseBranch</span> != <span class="k">null</span>) <span class="i">resolve</span>(<span class="i">stmt</span>.<span class="i">elseBranch</span>);
    <span class="k">return</span> <span class="k">null</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>visitFunctionStmt</em>()</div>

<p>Here, we see how resolution is different from interpretation. When we resolve an
<code>if</code> statement, there is no control flow. We resolve the condition and <em>both</em>
branches. Where a dynamic execution steps only into the branch that <em>is</em> run, a
static analysis is conservative<span class="em">&mdash;</span>it analyzes any branch that <em>could</em> be run.
Since either one could be reached at runtime, we resolve both.</p>
<p>Like expression statements, a <code>print</code> statement contains a single subexpression.</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>visitIfStmt</em>()</div>
<pre>  <span class="a">@Override</span>
  <span class="k">public</span> <span class="t">Void</span> <span class="i">visitPrintStmt</span>(<span class="t">Stmt</span>.<span class="t">Print</span> <span class="i">stmt</span>) {
    <span class="i">resolve</span>(<span class="i">stmt</span>.<span class="i">expression</span>);
    <span class="k">return</span> <span class="k">null</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>visitIfStmt</em>()</div>

<p>Same deal for return.</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>visitPrintStmt</em>()</div>
<pre>  <span class="a">@Override</span>
  <span class="k">public</span> <span class="t">Void</span> <span class="i">visitReturnStmt</span>(<span class="t">Stmt</span>.<span class="t">Return</span> <span class="i">stmt</span>) {
    <span class="k">if</span> (<span class="i">stmt</span>.<span class="i">value</span> != <span class="k">null</span>) {
      <span class="i">resolve</span>(<span class="i">stmt</span>.<span class="i">value</span>);
    }

    <span class="k">return</span> <span class="k">null</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>visitPrintStmt</em>()</div>

<p>As in <code>if</code> statements, with a <code>while</code> statement, we resolve its condition and
resolve the body exactly once.</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>visitVarStmt</em>()</div>
<pre>  <span class="a">@Override</span>
  <span class="k">public</span> <span class="t">Void</span> <span class="i">visitWhileStmt</span>(<span class="t">Stmt</span>.<span class="t">While</span> <span class="i">stmt</span>) {
    <span class="i">resolve</span>(<span class="i">stmt</span>.<span class="i">condition</span>);
    <span class="i">resolve</span>(<span class="i">stmt</span>.<span class="i">body</span>);
    <span class="k">return</span> <span class="k">null</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>visitVarStmt</em>()</div>

<p>That covers all the statements. On to expressions<span class="ellipse">&thinsp;.&thinsp;.&thinsp;.&nbsp;</span></p>
<p>Our old friend the binary expression. We traverse into and resolve both
operands.</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>visitAssignExpr</em>()</div>
<pre>  <span class="a">@Override</span>
  <span class="k">public</span> <span class="t">Void</span> <span class="i">visitBinaryExpr</span>(<span class="t">Expr</span>.<span class="t">Binary</span> <span class="i">expr</span>) {
    <span class="i">resolve</span>(<span class="i">expr</span>.<span class="i">left</span>);
    <span class="i">resolve</span>(<span class="i">expr</span>.<span class="i">right</span>);
    <span class="k">return</span> <span class="k">null</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>visitAssignExpr</em>()</div>

<p>Calls are similar<span class="em">&mdash;</span>we walk the argument list and resolve them all. The thing
being called is also an expression (usually a variable expression), so that gets
resolved too.</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>visitBinaryExpr</em>()</div>
<pre>  <span class="a">@Override</span>
  <span class="k">public</span> <span class="t">Void</span> <span class="i">visitCallExpr</span>(<span class="t">Expr</span>.<span class="t">Call</span> <span class="i">expr</span>) {
    <span class="i">resolve</span>(<span class="i">expr</span>.<span class="i">callee</span>);

    <span class="k">for</span> (<span class="t">Expr</span> <span class="i">argument</span> : <span class="i">expr</span>.<span class="i">arguments</span>) {
      <span class="i">resolve</span>(<span class="i">argument</span>);
    }

    <span class="k">return</span> <span class="k">null</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>visitBinaryExpr</em>()</div>

<p>Parentheses are easy.</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>visitCallExpr</em>()</div>
<pre>  <span class="a">@Override</span>
  <span class="k">public</span> <span class="t">Void</span> <span class="i">visitGroupingExpr</span>(<span class="t">Expr</span>.<span class="t">Grouping</span> <span class="i">expr</span>) {
    <span class="i">resolve</span>(<span class="i">expr</span>.<span class="i">expression</span>);
    <span class="k">return</span> <span class="k">null</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>visitCallExpr</em>()</div>

<p>Literals are easiest of all.</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>visitGroupingExpr</em>()</div>
<pre>  <span class="a">@Override</span>
  <span class="k">public</span> <span class="t">Void</span> <span class="i">visitLiteralExpr</span>(<span class="t">Expr</span>.<span class="t">Literal</span> <span class="i">expr</span>) {
    <span class="k">return</span> <span class="k">null</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>visitGroupingExpr</em>()</div>

<p>A literal expression doesn&rsquo;t mention any variables and doesn&rsquo;t contain any
subexpressions so there is no work to do.</p>
<p>Since a static analysis does no control flow or short-circuiting, logical
expressions are exactly the same as other binary operators.</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>visitLiteralExpr</em>()</div>
<pre>  <span class="a">@Override</span>
  <span class="k">public</span> <span class="t">Void</span> <span class="i">visitLogicalExpr</span>(<span class="t">Expr</span>.<span class="t">Logical</span> <span class="i">expr</span>) {
    <span class="i">resolve</span>(<span class="i">expr</span>.<span class="i">left</span>);
    <span class="i">resolve</span>(<span class="i">expr</span>.<span class="i">right</span>);
    <span class="k">return</span> <span class="k">null</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>visitLiteralExpr</em>()</div>

<p>And, finally, the last node. We resolve its one operand.</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>visitLogicalExpr</em>()</div>
<pre>  <span class="a">@Override</span>
  <span class="k">public</span> <span class="t">Void</span> <span class="i">visitUnaryExpr</span>(<span class="t">Expr</span>.<span class="t">Unary</span> <span class="i">expr</span>) {
    <span class="i">resolve</span>(<span class="i">expr</span>.<span class="i">right</span>);
    <span class="k">return</span> <span class="k">null</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>visitLogicalExpr</em>()</div>

<p>With all of these visit methods, the Java compiler should be satisfied that
Resolver fully implements Stmt.Visitor and Expr.Visitor. Now is a good time to
take a break, have a snack, maybe a little nap.</p>
<h2><a href="#interpreting-resolved-variables" id="interpreting-resolved-variables"><small>11&#8202;.&#8202;4</small>Interpreting Resolved Variables</a></h2>
<p>Let&rsquo;s see what our resolver is good for. Each time it visits a variable, it
tells the interpreter how many scopes there are between the current scope and
the scope where the variable is defined. At runtime, this corresponds exactly to
the number of <em>environments</em> between the current one and the enclosing one where
the interpreter can find the variable&rsquo;s value. The resolver hands that number to
the interpreter by calling this:</p>
<div class="codehilite"><div class="source-file"><em>lox/Interpreter.java</em><br>
add after <em>execute</em>()</div>
<pre>  <span class="t">void</span> <span class="i">resolve</span>(<span class="t">Expr</span> <span class="i">expr</span>, <span class="t">int</span> <span class="i">depth</span>) {
    <span class="i">locals</span>.<span class="i">put</span>(<span class="i">expr</span>, <span class="i">depth</span>);
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Interpreter.java</em>, add after <em>execute</em>()</div>

<p>We want to store the resolution information somewhere so we can use it when the
variable or assignment expression is later executed, but where? One obvious
place is right in the syntax tree node itself. That&rsquo;s a fine approach, and
that&rsquo;s where many compilers store the results of analyses like this.</p>
<p>We could do that, but it would require mucking around with our syntax tree
generator. Instead, we&rsquo;ll take another common approach and store it off to the
<span name="side">side</span> in a map that associates each syntax tree node
with its resolved data.</p>
<aside name="side">
<p>I <em>think</em> I&rsquo;ve heard this map called a &ldquo;side table&rdquo; since it&rsquo;s a tabular data
structure that stores data separately from the objects it relates to. But
whenever I try to Google for that term, I get pages about furniture.</p>
</aside>
<p>Interactive tools like IDEs often incrementally reparse and re-resolve parts of
the user&rsquo;s program. It may be hard to find all of the bits of state that need
recalculating when they&rsquo;re hiding in the foliage of the syntax tree. A benefit
of storing this data outside of the nodes is that it makes it easy to <em>discard</em>
it<span class="em">&mdash;</span>simply clear the map.</p>
<div class="codehilite"><pre class="insert-before">  private Environment environment = globals;
</pre><div class="source-file"><em>lox/Interpreter.java</em><br>
in class <em>Interpreter</em></div>
<pre class="insert">  <span class="k">private</span> <span class="k">final</span> <span class="t">Map</span>&lt;<span class="t">Expr</span>, <span class="t">Integer</span>&gt; <span class="i">locals</span> = <span class="k">new</span> <span class="t">HashMap</span>&lt;&gt;();
</pre><pre class="insert-after">

  Interpreter() {
</pre></div>
<div class="source-file-narrow"><em>lox/Interpreter.java</em>, in class <em>Interpreter</em></div>

<p>You might think we&rsquo;d need some sort of nested tree structure to avoid getting
confused when there are multiple expressions that reference the same variable,
but each expression node is its own Java object with its own unique identity. A
single monolithic map doesn&rsquo;t have any trouble keeping them separated.</p>
<p>As usual, using a collection requires us to import a couple of names.</p>
<div class="codehilite"><pre class="insert-before">import java.util.ArrayList;
</pre><div class="source-file"><em>lox/Interpreter.java</em></div>
<pre class="insert"><span class="k">import</span> <span class="i">java.util.HashMap</span>;
</pre><pre class="insert-after">import java.util.List;
</pre></div>
<div class="source-file-narrow"><em>lox/Interpreter.java</em></div>

<p>And:</p>
<div class="codehilite"><pre class="insert-before">import java.util.List;
</pre><div class="source-file"><em>lox/Interpreter.java</em></div>
<pre class="insert"><span class="k">import</span> <span class="i">java.util.Map</span>;
</pre><pre class="insert-after">

class Interpreter implements Expr.Visitor&lt;Object&gt;,
</pre></div>
<div class="source-file-narrow"><em>lox/Interpreter.java</em></div>

<h3><a href="#accessing-a-resolved-variable" id="accessing-a-resolved-variable"><small>11&#8202;.&#8202;4&#8202;.&#8202;1</small>Accessing a resolved variable</a></h3>
<p>Our interpreter now has access to each variable&rsquo;s resolved location. Finally, we
get to make use of that. We replace the visit method for variable expressions
with this:</p>
<div class="codehilite"><pre class="insert-before">  public Object visitVariableExpr(Expr.Variable expr) {
</pre><div class="source-file"><em>lox/Interpreter.java</em><br>
in <em>visitVariableExpr</em>()<br>
replace 1 line</div>
<pre class="insert">    <span class="k">return</span> <span class="i">lookUpVariable</span>(<span class="i">expr</span>.<span class="i">name</span>, <span class="i">expr</span>);
</pre><pre class="insert-after">  }
</pre></div>
<div class="source-file-narrow"><em>lox/Interpreter.java</em>, in <em>visitVariableExpr</em>(), replace 1 line</div>

<p>That delegates to:</p>
<div class="codehilite"><div class="source-file"><em>lox/Interpreter.java</em><br>
add after <em>visitVariableExpr</em>()</div>
<pre>  <span class="k">private</span> <span class="t">Object</span> <span class="i">lookUpVariable</span>(<span class="t">Token</span> <span class="i">name</span>, <span class="t">Expr</span> <span class="i">expr</span>) {
    <span class="t">Integer</span> <span class="i">distance</span> = <span class="i">locals</span>.<span class="i">get</span>(<span class="i">expr</span>);
    <span class="k">if</span> (<span class="i">distance</span> != <span class="k">null</span>) {
      <span class="k">return</span> <span class="i">environment</span>.<span class="i">getAt</span>(<span class="i">distance</span>, <span class="i">name</span>.<span class="i">lexeme</span>);
    } <span class="k">else</span> {
      <span class="k">return</span> <span class="i">globals</span>.<span class="i">get</span>(<span class="i">name</span>);
    }
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Interpreter.java</em>, add after <em>visitVariableExpr</em>()</div>

<p>There are a couple of things going on here. First, we look up the resolved
distance in the map. Remember that we resolved only <em>local</em> variables. Globals
are treated specially and don&rsquo;t end up in the map (hence the name <code>locals</code>). So,
if we don&rsquo;t find a distance in the map, it must be global. In that case, we
look it up, dynamically, directly in the global environment. That throws a
runtime error if the variable isn&rsquo;t defined.</p>
<p>If we <em>do</em> get a distance, we have a local variable, and we get to take
advantage of the results of our static analysis. Instead of calling <code>get()</code>, we
call this new method on Environment:</p>
<div class="codehilite"><div class="source-file"><em>lox/Environment.java</em><br>
add after <em>define</em>()</div>
<pre>  <span class="t">Object</span> <span class="i">getAt</span>(<span class="t">int</span> <span class="i">distance</span>, <span class="t">String</span> <span class="i">name</span>) {
    <span class="k">return</span> <span class="i">ancestor</span>(<span class="i">distance</span>).<span class="i">values</span>.<span class="i">get</span>(<span class="i">name</span>);
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Environment.java</em>, add after <em>define</em>()</div>

<p>The old <code>get()</code> method dynamically walks the chain of enclosing environments,
scouring each one to see if the variable might be hiding in there somewhere. But
now we know exactly which environment in the chain will have the variable. We
reach it using this helper method:</p>
<div class="codehilite"><div class="source-file"><em>lox/Environment.java</em><br>
add after <em>define</em>()</div>
<pre>  <span class="t">Environment</span> <span class="i">ancestor</span>(<span class="t">int</span> <span class="i">distance</span>) {
    <span class="t">Environment</span> <span class="i">environment</span> = <span class="k">this</span>;
    <span class="k">for</span> (<span class="t">int</span> <span class="i">i</span> = <span class="n">0</span>; <span class="i">i</span> &lt; <span class="i">distance</span>; <span class="i">i</span>++) {
      <span class="i">environment</span> = <span class="i">environment</span>.<span class="i">enclosing</span>;<span name="coupled"> </span>
    }

    <span class="k">return</span> <span class="i">environment</span>;
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Environment.java</em>, add after <em>define</em>()</div>

<p>This walks a fixed number of hops up the parent chain and returns the
environment there. Once we have that, <code>getAt()</code> simply returns the value of the
variable in that environment&rsquo;s map. It doesn&rsquo;t even have to check to see if the
variable is there<span class="em">&mdash;</span>we know it will be because the resolver already found it
before.</p>
<aside name="coupled">
<p>The way the interpreter assumes the variable is in that map feels like flying
blind. The interpreter code trusts that the resolver did its job and resolved
the variable correctly. This implies a deep coupling between these two classes.
In the resolver, each line of code that touches a scope must have its exact
match in the interpreter for modifying an environment.</p>
<p>I felt that coupling firsthand because as I wrote the code for the book, I
ran into a couple of subtle bugs where the resolver and interpreter code were
slightly out of sync. Tracking those down was difficult. One tool to make that
easier is to have the interpreter explicitly assert<span class="em">&mdash;</span>using Java&rsquo;s assert
statements or some other validation tool<span class="em">&mdash;</span>the contract it expects the resolver
to have already upheld.</p>
</aside>
<h3><a href="#assigning-to-a-resolved-variable" id="assigning-to-a-resolved-variable"><small>11&#8202;.&#8202;4&#8202;.&#8202;2</small>Assigning to a resolved variable</a></h3>
<p>We can also use a variable by assigning to it. The changes to visiting an
assignment expression are similar.</p>
<div class="codehilite"><pre class="insert-before">  public Object visitAssignExpr(Expr.Assign expr) {
    Object value = evaluate(expr.value);
</pre><div class="source-file"><em>lox/Interpreter.java</em><br>
in <em>visitAssignExpr</em>()<br>
replace 1 line</div>
<pre class="insert">

    <span class="t">Integer</span> <span class="i">distance</span> = <span class="i">locals</span>.<span class="i">get</span>(<span class="i">expr</span>);
    <span class="k">if</span> (<span class="i">distance</span> != <span class="k">null</span>) {
      <span class="i">environment</span>.<span class="i">assignAt</span>(<span class="i">distance</span>, <span class="i">expr</span>.<span class="i">name</span>, <span class="i">value</span>);
    } <span class="k">else</span> {
      <span class="i">globals</span>.<span class="i">assign</span>(<span class="i">expr</span>.<span class="i">name</span>, <span class="i">value</span>);
    }

</pre><pre class="insert-after">    return value;
</pre></div>
<div class="source-file-narrow"><em>lox/Interpreter.java</em>, in <em>visitAssignExpr</em>(), replace 1 line</div>

<p>Again, we look up the variable&rsquo;s scope distance. If not found, we assume it&rsquo;s
global and handle it the same way as before. Otherwise, we call this new method:</p>
<div class="codehilite"><div class="source-file"><em>lox/Environment.java</em><br>
add after <em>getAt</em>()</div>
<pre>  <span class="t">void</span> <span class="i">assignAt</span>(<span class="t">int</span> <span class="i">distance</span>, <span class="t">Token</span> <span class="i">name</span>, <span class="t">Object</span> <span class="i">value</span>) {
    <span class="i">ancestor</span>(<span class="i">distance</span>).<span class="i">values</span>.<span class="i">put</span>(<span class="i">name</span>.<span class="i">lexeme</span>, <span class="i">value</span>);
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Environment.java</em>, add after <em>getAt</em>()</div>

<p>As <code>getAt()</code> is to <code>get()</code>, <code>assignAt()</code> is to <code>assign()</code>. It walks a fixed
number of environments, and then stuffs the new value in that map.</p>
<p>Those are the only changes to Interpreter. This is why I chose a representation
for our resolved data that was minimally invasive. All of the rest of the nodes
continue working as they did before. Even the code for modifying environments is
unchanged.</p>
<h3><a href="#running-the-resolver" id="running-the-resolver"><small>11&#8202;.&#8202;4&#8202;.&#8202;3</small>Running the resolver</a></h3>
<p>We do need to actually <em>run</em> the resolver, though. We insert the new pass after
the parser does its magic.</p>
<div class="codehilite"><pre class="insert-before">    // Stop if there was a syntax error.
    if (hadError) return;

</pre><div class="source-file"><em>lox/Lox.java</em><br>
in <em>run</em>()</div>
<pre class="insert">    <span class="t">Resolver</span> <span class="i">resolver</span> = <span class="k">new</span> <span class="t">Resolver</span>(<span class="i">interpreter</span>);
    <span class="i">resolver</span>.<span class="i">resolve</span>(<span class="i">statements</span>);

</pre><pre class="insert-after">    interpreter.interpret(statements);
</pre></div>
<div class="source-file-narrow"><em>lox/Lox.java</em>, in <em>run</em>()</div>

<p>We don&rsquo;t run the resolver if there are any parse errors. If the code has a
syntax error, it&rsquo;s never going to run, so there&rsquo;s little value in resolving it.
If the syntax is clean, we tell the resolver to do its thing. The resolver has a
reference to the interpreter and pokes the resolution data directly into it as
it walks over variables. When the interpreter runs next, it has everything it
needs.</p>
<p>At least, that&rsquo;s true if the resolver <em>succeeds</em>. But what about errors during
resolution?</p>
<h2><a href="#resolution-errors" id="resolution-errors"><small>11&#8202;.&#8202;5</small>Resolution Errors</a></h2>
<p>Since we are doing a semantic analysis pass, we have an opportunity to make
Lox&rsquo;s semantics more precise, and to help users catch bugs early before running
their code. Take a look at this bad boy:</p>
<div class="codehilite"><pre><span class="k">fun</span> <span class="i">bad</span>() {
  <span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;first&quot;</span>;
  <span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;second&quot;</span>;
}
</pre></div>
<p>We do allow declaring multiple variables with the same name in the <em>global</em>
scope, but doing so in a local scope is probably a mistake. If they knew the
variable already existed, they would have assigned to it instead of using <code>var</code>.
And if they <em>didn&rsquo;t</em> know it existed, they probably didn&rsquo;t intend to overwrite
the previous one.</p>
<p>We can detect this mistake statically while resolving.</p>
<div class="codehilite"><pre class="insert-before">    Map&lt;String, Boolean&gt; scope = scopes.peek();
</pre><div class="source-file"><em>lox/Resolver.java</em><br>
in <em>declare</em>()</div>
<pre class="insert">    <span class="k">if</span> (<span class="i">scope</span>.<span class="i">containsKey</span>(<span class="i">name</span>.<span class="i">lexeme</span>)) {
      <span class="t">Lox</span>.<span class="i">error</span>(<span class="i">name</span>,
          <span class="s">&quot;Already a variable with this name in this scope.&quot;</span>);
    }

</pre><pre class="insert-after">    scope.put(name.lexeme, false);
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, in <em>declare</em>()</div>

<p>When we declare a variable in a local scope, we already know the names of every
variable previously declared in that same scope. If we see a collision, we
report an error.</p>
<h3><a href="#invalid-return-errors" id="invalid-return-errors"><small>11&#8202;.&#8202;5&#8202;.&#8202;1</small>Invalid return errors</a></h3>
<p>Here&rsquo;s another nasty little script:</p>
<div class="codehilite"><pre><span class="k">return</span> <span class="s">&quot;at top level&quot;</span>;
</pre></div>
<p>This executes a <code>return</code> statement, but it&rsquo;s not even inside a function at all.
It&rsquo;s top-level code. I don&rsquo;t know what the user <em>thinks</em> is going to happen, but
I don&rsquo;t think we want Lox to allow this.</p>
<p>We can extend the resolver to detect this statically. Much like we track scopes
as we walk the tree, we can track whether or not the code we are currently
visiting is inside a function declaration.</p>
<div class="codehilite"><pre class="insert-before">  private final Stack&lt;Map&lt;String, Boolean&gt;&gt; scopes = new Stack&lt;&gt;();
</pre><div class="source-file"><em>lox/Resolver.java</em><br>
in class <em>Resolver</em></div>
<pre class="insert">  <span class="k">private</span> <span class="t">FunctionType</span> <span class="i">currentFunction</span> = <span class="t">FunctionType</span>.<span class="i">NONE</span>;
</pre><pre class="insert-after">

  Resolver(Interpreter interpreter) {
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, in class <em>Resolver</em></div>

<p>Instead of a bare Boolean, we use this funny enum:</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
add after <em>Resolver</em>()</div>
<pre>  <span class="k">private</span> <span class="k">enum</span> <span class="t">FunctionType</span> {
    <span class="i">NONE</span>,
    <span class="i">FUNCTION</span>
  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, add after <em>Resolver</em>()</div>

<p>It seems kind of dumb now, but we&rsquo;ll add a couple more cases to it later and
then it will make more sense. When we resolve a function declaration, we pass
that in.</p>
<div class="codehilite"><pre class="insert-before">    define(stmt.name);

</pre><div class="source-file"><em>lox/Resolver.java</em><br>
in <em>visitFunctionStmt</em>()<br>
replace 1 line</div>
<pre class="insert">    <span class="i">resolveFunction</span>(<span class="i">stmt</span>, <span class="t">FunctionType</span>.<span class="i">FUNCTION</span>);
</pre><pre class="insert-after">    return null;
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, in <em>visitFunctionStmt</em>(), replace 1 line</div>

<p>Over in <code>resolveFunction()</code>, we take that parameter and store it in the field
before resolving the body.</p>
<div class="codehilite"><div class="source-file"><em>lox/Resolver.java</em><br>
method <em>resolveFunction</em>()<br>
replace 1 line</div>
<pre class="insert">  <span class="k">private</span> <span class="t">void</span> <span class="i">resolveFunction</span>(
      <span class="t">Stmt</span>.<span class="t">Function</span> <span class="i">function</span>, <span class="t">FunctionType</span> <span class="i">type</span>) {
    <span class="t">FunctionType</span> <span class="i">enclosingFunction</span> = <span class="i">currentFunction</span>;
    <span class="i">currentFunction</span> = <span class="i">type</span>;

</pre><pre class="insert-after">    beginScope();
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, method <em>resolveFunction</em>(), replace 1 line</div>

<p>We stash the previous value of the field in a local variable first. Remember,
Lox has local functions, so you can nest function declarations arbitrarily
deeply. We need to track not just that we&rsquo;re in a function, but <em>how many</em> we&rsquo;re
in.</p>
<p>We could use an explicit stack of FunctionType values for that, but instead
we&rsquo;ll piggyback on the JVM. We store the previous value in a local on the Java
stack. When we&rsquo;re done resolving the function body, we restore the field to that
value.</p>
<div class="codehilite"><pre class="insert-before">    endScope();
</pre><div class="source-file"><em>lox/Resolver.java</em><br>
in <em>resolveFunction</em>()</div>
<pre class="insert">    <span class="i">currentFunction</span> = <span class="i">enclosingFunction</span>;
</pre><pre class="insert-after">  }
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, in <em>resolveFunction</em>()</div>

<p>Now that we can always tell whether or not we&rsquo;re inside a function declaration,
we check that when resolving a <code>return</code> statement.</p>
<div class="codehilite"><pre class="insert-before">  public Void visitReturnStmt(Stmt.Return stmt) {
</pre><div class="source-file"><em>lox/Resolver.java</em><br>
in <em>visitReturnStmt</em>()</div>
<pre class="insert">    <span class="k">if</span> (<span class="i">currentFunction</span> == <span class="t">FunctionType</span>.<span class="i">NONE</span>) {
      <span class="t">Lox</span>.<span class="i">error</span>(<span class="i">stmt</span>.<span class="i">keyword</span>, <span class="s">&quot;Can&#39;t return from top-level code.&quot;</span>);
    }

</pre><pre class="insert-after">    if (stmt.value != null) {
</pre></div>
<div class="source-file-narrow"><em>lox/Resolver.java</em>, in <em>visitReturnStmt</em>()</div>

<p>Neat, right?</p>
<p>There&rsquo;s one more piece. Back in the main Lox class that stitches everything
together, we are careful to not run the interpreter if any parse errors are
encountered. That check runs <em>before</em> the resolver so that we don&rsquo;t try to
resolve syntactically invalid code.</p>
<p>But we also need to skip the interpreter if there are resolution errors, so we
add <em>another</em> check.</p>
<div class="codehilite"><pre class="insert-before">    resolver.resolve(statements);
</pre><div class="source-file"><em>lox/Lox.java</em><br>
in <em>run</em>()</div>
<pre class="insert">

    <span class="c">// Stop if there was a resolution error.</span>
    <span class="k">if</span> (<span class="i">hadError</span>) <span class="k">return</span>;
</pre><pre class="insert-after">

    interpreter.interpret(statements);
</pre></div>
<div class="source-file-narrow"><em>lox/Lox.java</em>, in <em>run</em>()</div>

<p>You could imagine doing lots of other analysis in here. For example, if we added
<code>break</code> statements to Lox, we would probably want to ensure they are only used
inside loops.</p>
<p>We could go farther and report warnings for code that isn&rsquo;t necessarily <em>wrong</em>
but probably isn&rsquo;t useful. For example, many IDEs will warn if you have
unreachable code after a <code>return</code> statement, or a local variable whose value is
never read. All of that would be pretty easy to add to our static visiting pass,
or as <span name="separate">separate</span> passes.</p>
<aside name="separate">
<p>The choice of how many different analyses to lump into a single pass is
difficult. Many small isolated passes, each with their own responsibility, are
simpler to implement and maintain. However, there is a real runtime cost to
traversing the syntax tree itself, so bundling multiple analyses into a single
pass is usually faster.</p>
</aside>
<p>But, for now, we&rsquo;ll stick with that limited amount of analysis. The important
part is that we fixed that one weird annoying edge case bug, though it might be
surprising that it took this much work to do it.</p>
<div class="challenges">
<h2><a href="#challenges" id="challenges">Challenges</a></h2>
<ol>
<li>
<p>Why is it safe to eagerly define the variable bound to a function&rsquo;s name
when other variables must wait until after they are initialized before they
can be used?</p>
</li>
<li>
<p>How do other languages you know handle local variables that refer to the
same name in their initializer, like:</p>
<div class="codehilite"><pre><span class="k">var</span> <span class="i">a</span> = <span class="s">&quot;outer&quot;</span>;
{
  <span class="k">var</span> <span class="i">a</span> = <span class="i">a</span>;
}
</pre></div>
<p>Is it a runtime error? Compile error? Allowed? Do they treat global
variables differently? Do you agree with their choices? Justify your answer.</p>
</li>
<li>
<p>Extend the resolver to report an error if a local variable is never used.</p>
</li>
<li>
<p>Our resolver calculates <em>which</em> environment the variable is found in, but
it&rsquo;s still looked up by name in that map. A more efficient environment
representation would store local variables in an array and look them up by
index.</p>
<p>Extend the resolver to associate a unique index for each local variable
declared in a scope. When resolving a variable access, look up both the
scope the variable is in and its index and store that. In the interpreter,
use that to quickly access a variable by its index instead of using a map.</p>
</li>
</ol>
</div>

<footer>
<a href="classes.html" class="next">
  Next Chapter: &ldquo;Classes&rdquo; &rarr;
</a>
Handcrafted by Robert Nystrom&ensp;&mdash;&ensp;<a href="https://github.com/munificent/craftinginterpreters/blob/master/LICENSE" target="_blank">&copy; 2015&hairsp;&ndash;&hairsp;2021</a>
</footer>
</article>

</div>
</body>
</html>