site/local-variables.html

<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-type" content="text/html;charset=UTF-8" />
<title>Local Variables &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">Local Variables<small>22</small></a></h3>

<ul>
    <li><a href="#representing-local-variables"><small>22.1</small> Representing Local Variables</a></li>
    <li><a href="#block-statements"><small>22.2</small> Block Statements</a></li>
    <li><a href="#declaring-local-variables"><small>22.3</small> Declaring Local Variables</a></li>
    <li><a href="#using-locals"><small>22.4</small> Using Locals</a></li>
    <li class="divider"></li>
    <li class="end-part"><a href="#challenges">Challenges</a></li>
</ul>


<div class="prev-next">
    <a href="global-variables.html" title="Global Variables" class="left">&larr;&nbsp;Previous</a>
    <a href="a-bytecode-virtual-machine.html" title="A Bytecode Virtual Machine">&uarr;&nbsp;Up</a>
    <a href="jumping-back-and-forth.html" title="Jumping Back and Forth" 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="global-variables.html" title="Global Variables" class="prev">←</a>
<a href="jumping-back-and-forth.html" title="Jumping Back and Forth" 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">Local Variables<small>22</small></a></h3>

<ul>
    <li><a href="#representing-local-variables"><small>22.1</small> Representing Local Variables</a></li>
    <li><a href="#block-statements"><small>22.2</small> Block Statements</a></li>
    <li><a href="#declaring-local-variables"><small>22.3</small> Declaring Local Variables</a></li>
    <li><a href="#using-locals"><small>22.4</small> Using Locals</a></li>
    <li class="divider"></li>
    <li class="end-part"><a href="#challenges">Challenges</a></li>
</ul>


<div class="prev-next">
    <a href="global-variables.html" title="Global Variables" class="left">&larr;&nbsp;Previous</a>
    <a href="a-bytecode-virtual-machine.html" title="A Bytecode Virtual Machine">&uarr;&nbsp;Up</a>
    <a href="jumping-back-and-forth.html" title="Jumping Back and Forth" class="right">Next&nbsp;&rarr;</a>
</div>  </div>
  <a id="expand-nav">≡</a>
</nav>
</div>

<article class="chapter">

  <div class="number">22</div>
  <h1>Local Variables</h1>

<blockquote>
<p>And as imagination bodies forth<br />
The forms of things unknown, the poet&rsquo;s pen<br />
Turns them to shapes and gives to airy nothing<br />
A local habitation and a name.</p>
<p><cite>William Shakespeare, <em>A Midsummer Night&rsquo;s Dream</em></cite></p>
</blockquote>
<p>The <a href="global-variables.html">last chapter</a> introduced variables to clox, but only of the <span
name="global">global</span> variety. In this chapter, we&rsquo;ll extend that to
support blocks, block scope, and local variables. In jlox, we managed to pack
all of that and globals into one chapter. For clox, that&rsquo;s two chapters worth of
work partially because, frankly, everything takes more effort in C.</p>
<aside name="global">
<p>There&rsquo;s probably some dumb &ldquo;think globally, act locally&rdquo; joke here, but I&rsquo;m
struggling to find it.</p>
</aside>
<p>But an even more important reason is that our approach to local variables will
be quite different from how we implemented globals. Global variables are late
bound in Lox. &ldquo;Late&rdquo; in this context means &ldquo;resolved after compile time&rdquo;. That&rsquo;s
good for keeping the compiler simple, but not great for performance. Local
variables are one of the most-used <span name="params">parts</span> of a
language. If locals are slow, <em>everything</em> is slow. So we want a strategy for
local variables that&rsquo;s as efficient as possible.</p>
<aside name="params">
<p>Function parameters are also heavily used. They work like local variables too,
so we&rsquo;ll use the same implementation technique for them.</p>
</aside>
<p>Fortunately, lexical scoping is here to help us. As the name implies, lexical
scope means we can resolve a local variable just by looking at the text of the
program<span class="em">&mdash;</span>locals are <em>not</em> late bound. Any processing work we do in the
compiler is work we <em>don&rsquo;t</em> have to do at runtime, so our implementation of
local variables will lean heavily on the compiler.</p>
<h2><a href="#representing-local-variables" id="representing-local-variables"><small>22&#8202;.&#8202;1</small>Representing Local Variables</a></h2>
<p>The nice thing about hacking on a programming language in modern times is
there&rsquo;s a long lineage of other languages to learn from. So how do C and Java
manage their local variables? Why, on the stack, of course! They typically use
the native stack mechanisms supported by the chip and OS. That&rsquo;s a little too
low level for us, but inside the virtual world of clox, we have our own stack we
can use.</p>
<p>Right now, we only use it for holding on to <strong>temporaries</strong><span class="em">&mdash;</span>short-lived blobs
of data that we need to remember while computing an expression. As long as we
don&rsquo;t get in the way of those, we can stuff our local variables onto the stack
too. This is great for performance. Allocating space for a new local requires
only incrementing the <code>stackTop</code> pointer, and freeing is likewise a decrement.
Accessing a variable from a known stack slot is an indexed array lookup.</p>
<p>We do need to be careful, though. The VM expects the stack to behave like, well,
a stack. We have to be OK with allocating new locals only on the top of the
stack, and we have to accept that we can discard a local only when nothing is
above it on the stack. Also, we need to make sure temporaries don&rsquo;t interfere.</p>
<p>Conveniently, the design of Lox is in <span name="harmony">harmony</span> with
these constraints. New locals are always created by declaration statements.
Statements don&rsquo;t nest inside expressions, so there are never any temporaries on
the stack when a statement begins executing. Blocks are strictly nested. When a
block ends, it always takes the innermost, most recently declared locals with
it. Since those are also the locals that came into scope last, they should be on
top of the stack where we need them.</p>
<aside name="harmony">
<p>This alignment obviously isn&rsquo;t coincidental. I designed Lox to be amenable to
single-pass compilation to stack-based bytecode. But I didn&rsquo;t have to tweak the
language too much to fit in those restrictions. Most of its design should feel
pretty natural.</p>
<p>This is in large part because the history of languages is deeply tied to
single-pass compilation and<span class="em">&mdash;</span>to a lesser degree<span class="em">&mdash;</span>stack-based architectures.
Lox&rsquo;s block scoping follows a tradition stretching back to BCPL. As programmers,
our intuition of what&rsquo;s &ldquo;normal&rdquo; in a language is informed even today by the
hardware limitations of yesteryear.</p>
</aside>
<p>Step through this example program and watch how the local variables come in and
go out of scope:</p><img src="image/local-variables/scopes.png" alt="A series of local variables come into and out of scope in a stack-like fashion." />
<p>See how they fit a stack perfectly? It seems that the stack will work for
storing locals at runtime. But we can go further than that. Not only do we know
<em>that</em> they will be on the stack, but we can even pin down precisely <em>where</em>
they will be on the stack. Since the compiler knows exactly which local
variables are in scope at any point in time, it can effectively simulate the
stack during compilation and note <span name="fn">where</span> in the stack each
variable lives.</p>
<p>We&rsquo;ll take advantage of this by using these stack offsets as operands for the
bytecode instructions that read and store local variables. This makes working
with locals deliciously fast<span class="em">&mdash;</span>as simple as indexing into an array.</p>
<aside name="fn">
<p>In this chapter, locals start at the bottom of the VM&rsquo;s stack array and are
indexed from there. When we add <a href="calls-and-functions.html">functions</a>, that scheme gets a little more
complex. Each function needs its own region of the stack for its parameters and
local variables. But, as we&rsquo;ll see, that doesn&rsquo;t add as much complexity as you
might expect.</p>
</aside>
<p>There&rsquo;s a lot of state we need to track in the compiler to make this whole thing
go, so let&rsquo;s get started there. In jlox, we used a linked chain of &ldquo;environment&rdquo;
HashMaps to track which local variables were currently in scope. That&rsquo;s sort of
the classic, schoolbook way of representing lexical scope. For clox, as usual,
we&rsquo;re going a little closer to the metal. All of the state lives in a new
struct.</p>
<div class="codehilite"><pre class="insert-before">} ParseRule;
</pre><div class="source-file"><em>compiler.c</em><br>
add after struct <em>ParseRule</em></div>
<pre class="insert">

<span class="k">typedef</span> <span class="k">struct</span> {
  <span class="t">Local</span> <span class="i">locals</span>[<span class="a">UINT8_COUNT</span>];
  <span class="t">int</span> <span class="i">localCount</span>;
  <span class="t">int</span> <span class="i">scopeDepth</span>;
} <span class="t">Compiler</span>;
</pre><pre class="insert-after">

Parser parser;
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, add after struct <em>ParseRule</em></div>

<p>We have a simple, flat array of all locals that are in scope during each point in
the compilation process. They are <span name="order">ordered</span> in the array
in the order that their declarations appear in the code. Since the instruction
operand we&rsquo;ll use to encode a local is a single byte, our VM has a hard limit on
the number of locals that can be in scope at once. That means we can also give
the locals array a fixed size.</p>
<aside name="order">
<p>We&rsquo;re writing a single-pass compiler, so it&rsquo;s not like we have <em>too</em> many other
options for how to order them in the array.</p>
</aside>
<div class="codehilite"><pre class="insert-before">#define DEBUG_TRACE_EXECUTION
</pre><div class="source-file"><em>common.h</em></div>
<pre class="insert">

<span class="a">#define UINT8_COUNT (UINT8_MAX + 1)</span>
</pre><pre class="insert-after">

#endif
</pre></div>
<div class="source-file-narrow"><em>common.h</em></div>

<p>Back in the Compiler struct, the <code>localCount</code> field tracks how many locals are
in scope<span class="em">&mdash;</span>how many of those array slots are in use. We also track the &ldquo;scope
depth&rdquo;. This is the number of blocks surrounding the current bit of code we&rsquo;re
compiling.</p>
<p>Our Java interpreter used a chain of maps to keep each block&rsquo;s variables
separate from other blocks&rsquo;. This time, we&rsquo;ll simply number variables with the
level of nesting where they appear. Zero is the global scope, one is the first
top-level block, two is inside that, you get the idea. We use this to track
which block each local belongs to so that we know which locals to discard when a
block ends.</p>
<p>Each local in the array is one of these:</p>
<div class="codehilite"><pre class="insert-before">} ParseRule;
</pre><div class="source-file"><em>compiler.c</em><br>
add after struct <em>ParseRule</em></div>
<pre class="insert">

<span class="k">typedef</span> <span class="k">struct</span> {
  <span class="t">Token</span> <span class="i">name</span>;
  <span class="t">int</span> <span class="i">depth</span>;
} <span class="t">Local</span>;
</pre><pre class="insert-after">

typedef struct {
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, add after struct <em>ParseRule</em></div>

<p>We store the name of the variable. When we&rsquo;re resolving an identifier, we
compare the identifier&rsquo;s lexeme with each local&rsquo;s name to find a match. It&rsquo;s
pretty hard to resolve a variable if you don&rsquo;t know its name. The <code>depth</code> field
records the scope depth of the block where the local variable was declared.
That&rsquo;s all the state we need for now.</p>
<p>This is a very different representation from what we had in jlox, but it still
lets us answer all of the same questions our compiler needs to ask of the
lexical environment. The next step is figuring out how the compiler <em>gets</em> at
this state. If we were <span name="thread">principled</span> engineers, we&rsquo;d
give each function in the front end a parameter that accepts a pointer to a
Compiler. We&rsquo;d create a Compiler at the beginning and carefully thread it
through each function call<span class="ellipse">&thinsp;.&thinsp;.&thinsp;.&nbsp;</span>but that would mean a lot of boring changes to
the code we already wrote, so here&rsquo;s a global variable instead:</p>
<aside name="thread">
<p>In particular, if we ever want to use our compiler in a multi-threaded
application, possibly with multiple compilers running in parallel, then using a
global variable is a <em>bad</em> idea.</p>
</aside>
<div class="codehilite"><pre class="insert-before">Parser parser;
</pre><div class="source-file"><em>compiler.c</em><br>
add after variable <em>parser</em></div>
<pre class="insert"><span class="t">Compiler</span>* <span class="i">current</span> = <span class="a">NULL</span>;
</pre><pre class="insert-after">Chunk* compilingChunk;
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, add after variable <em>parser</em></div>

<p>Here&rsquo;s a little function to initialize the compiler:</p>
<div class="codehilite"><div class="source-file"><em>compiler.c</em><br>
add after <em>emitConstant</em>()</div>
<pre><span class="k">static</span> <span class="t">void</span> <span class="i">initCompiler</span>(<span class="t">Compiler</span>* <span class="i">compiler</span>) {
  <span class="i">compiler</span>-&gt;<span class="i">localCount</span> = <span class="n">0</span>;
  <span class="i">compiler</span>-&gt;<span class="i">scopeDepth</span> = <span class="n">0</span>;
  <span class="i">current</span> = <span class="i">compiler</span>;
}
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, add after <em>emitConstant</em>()</div>

<p>When we first start up the VM, we call it to get everything into a clean state.</p>
<div class="codehilite"><pre class="insert-before">  initScanner(source);
</pre><div class="source-file"><em>compiler.c</em><br>
in <em>compile</em>()</div>
<pre class="insert">  <span class="t">Compiler</span> <span class="i">compiler</span>;
  <span class="i">initCompiler</span>(&amp;<span class="i">compiler</span>);
</pre><pre class="insert-after">  compilingChunk = chunk;
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, in <em>compile</em>()</div>

<p>Our compiler has the data it needs, but not the operations on that data. There&rsquo;s
no way to create and destroy scopes, or add and resolve variables. We&rsquo;ll add
those as we need them. First, let&rsquo;s start building some language features.</p>
<h2><a href="#block-statements" id="block-statements"><small>22&#8202;.&#8202;2</small>Block Statements</a></h2>
<p>Before we can have any local variables, we need some local scopes. These come
from two things: function bodies and <span name="block">blocks</span>. Functions
are a big chunk of work that we&rsquo;ll tackle in <a href="calls-and-functions.html">a later chapter</a>, so
for now we&rsquo;re only going to do blocks. As usual, we start with the syntax. The
new grammar we&rsquo;ll introduce is:</p>
<div class="codehilite"><pre><span class="i">statement</span>      → <span class="i">exprStmt</span>
               | <span class="i">printStmt</span>
               | <span class="i">block</span> ;

<span class="i">block</span>          → <span class="s">&quot;{&quot;</span> <span class="i">declaration</span>* <span class="s">&quot;}&quot;</span> ;
</pre></div>
<aside name="block">
<p>When you think about it, &ldquo;block&rdquo; is a weird name. Used metaphorically, &ldquo;block&rdquo;
usually means a small indivisible unit, but for some reason, the Algol 60
committee decided to use it to refer to a <em>compound</em> structure<span class="em">&mdash;</span>a series of
statements. It could be worse, I suppose. Algol 58 called <code>begin</code> and <code>end</code>
&ldquo;statement parentheses&rdquo;.</p><img src="image/local-variables/block.png" alt="A cinder block." class="above" />
</aside>
<p>Blocks are a kind of statement, so the rule for them goes in the <code>statement</code>
production. The corresponding code to compile one looks like this:</p>
<div class="codehilite"><pre class="insert-before">  if (match(TOKEN_PRINT)) {
    printStatement();
</pre><div class="source-file"><em>compiler.c</em><br>
in <em>statement</em>()</div>
<pre class="insert">  } <span class="k">else</span> <span class="k">if</span> (<span class="i">match</span>(<span class="a">TOKEN_LEFT_BRACE</span>)) {
    <span class="i">beginScope</span>();
    <span class="i">block</span>();
    <span class="i">endScope</span>();
</pre><pre class="insert-after">  } else {
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, in <em>statement</em>()</div>

<p>After <span name="helper">parsing</span> the initial curly brace, we use this
helper function to compile the rest of the block:</p>
<aside name="helper">
<p>This function will come in handy later for compiling function bodies.</p>
</aside>
<div class="codehilite"><div class="source-file"><em>compiler.c</em><br>
add after <em>expression</em>()</div>
<pre><span class="k">static</span> <span class="t">void</span> <span class="i">block</span>() {
  <span class="k">while</span> (!<span class="i">check</span>(<span class="a">TOKEN_RIGHT_BRACE</span>) &amp;&amp; !<span class="i">check</span>(<span class="a">TOKEN_EOF</span>)) {
    <span class="i">declaration</span>();
  }

  <span class="i">consume</span>(<span class="a">TOKEN_RIGHT_BRACE</span>, <span class="s">&quot;Expect &#39;}&#39; after block.&quot;</span>);
}
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, add after <em>expression</em>()</div>

<p>It keeps parsing declarations and statements until it hits the closing brace. As
we do with any loop in the parser, we also check for the end of the token
stream. This way, if there&rsquo;s a malformed program with a missing closing curly,
the compiler doesn&rsquo;t get stuck in a loop.</p>
<p>Executing a block simply means executing the statements it contains, one after
the other, so there isn&rsquo;t much to compiling them. The semantically interesting
thing blocks do is create scopes. Before we compile the body of a block, we call
this function to enter a new local scope:</p>
<div class="codehilite"><div class="source-file"><em>compiler.c</em><br>
add after <em>endCompiler</em>()</div>
<pre><span class="k">static</span> <span class="t">void</span> <span class="i">beginScope</span>() {
  <span class="i">current</span>-&gt;<span class="i">scopeDepth</span>++;
}
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, add after <em>endCompiler</em>()</div>

<p>In order to &ldquo;create&rdquo; a scope, all we do is increment the current depth. This is
certainly much faster than jlox, which allocated an entire new HashMap for
each one. Given <code>beginScope()</code>, you can probably guess what <code>endScope()</code> does.</p>
<div class="codehilite"><div class="source-file"><em>compiler.c</em><br>
add after <em>beginScope</em>()</div>
<pre><span class="k">static</span> <span class="t">void</span> <span class="i">endScope</span>() {
  <span class="i">current</span>-&gt;<span class="i">scopeDepth</span>--;
}
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, add after <em>beginScope</em>()</div>

<p>That&rsquo;s it for blocks and scopes<span class="em">&mdash;</span>more or less<span class="em">&mdash;</span>so we&rsquo;re ready to stuff some
variables into them.</p>
<h2><a href="#declaring-local-variables" id="declaring-local-variables"><small>22&#8202;.&#8202;3</small>Declaring Local Variables</a></h2>
<p>Usually we start with parsing here, but our compiler already supports parsing
and compiling variable declarations. We&rsquo;ve got <code>var</code> statements, identifier
expressions and assignment in there now. It&rsquo;s just that the compiler assumes
all variables are global. So we don&rsquo;t need any new parsing support, we just need
to hook up the new scoping semantics to the existing code.</p><img src="image/local-variables/declaration.png" alt="The code flow within varDeclaration()." />
<p>Variable declaration parsing begins in <code>varDeclaration()</code> and relies on a couple
of other functions. First, <code>parseVariable()</code> consumes the identifier token for
the variable name, adds its lexeme to the chunk&rsquo;s constant table as a string,
and then returns the constant table index where it was added. Then, after
<code>varDeclaration()</code> compiles the initializer, it calls <code>defineVariable()</code> to emit
the bytecode for storing the variable&rsquo;s value in the global variable hash table.</p>
<p>Both of those helpers need a few changes to support local variables. In
<code>parseVariable()</code>, we add:</p>
<div class="codehilite"><pre class="insert-before">  consume(TOKEN_IDENTIFIER, errorMessage);
</pre><div class="source-file"><em>compiler.c</em><br>
in <em>parseVariable</em>()</div>
<pre class="insert">

  <span class="i">declareVariable</span>();
  <span class="k">if</span> (<span class="i">current</span>-&gt;<span class="i">scopeDepth</span> &gt; <span class="n">0</span>) <span class="k">return</span> <span class="n">0</span>;

</pre><pre class="insert-after">  return identifierConstant(&amp;parser.previous);
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, in <em>parseVariable</em>()</div>

<p>First, we &ldquo;declare&rdquo; the variable. I&rsquo;ll get to what that means in a second. After
that, we exit the function if we&rsquo;re in a local scope. At runtime, locals aren&rsquo;t
looked up by name. There&rsquo;s no need to stuff the variable&rsquo;s name into the
constant table, so if the declaration is inside a local scope, we return a dummy
table index instead.</p>
<p>Over in <code>defineVariable()</code>, we need to emit the code to store a local variable
if we&rsquo;re in a local scope. It looks like this:</p>
<div class="codehilite"><pre class="insert-before">static void defineVariable(uint8_t global) {
</pre><div class="source-file"><em>compiler.c</em><br>
in <em>defineVariable</em>()</div>
<pre class="insert">  <span class="k">if</span> (<span class="i">current</span>-&gt;<span class="i">scopeDepth</span> &gt; <span class="n">0</span>) {
    <span class="k">return</span>;
  }

</pre><pre class="insert-after">  emitBytes(OP_DEFINE_GLOBAL, global);
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, in <em>defineVariable</em>()</div>

<p>Wait, what? Yup. That&rsquo;s it. There is no code to create a local variable at
runtime. Think about what state the VM is in. It has already executed the code
for the variable&rsquo;s initializer (or the implicit <code>nil</code> if the user omitted an
initializer), and that value is sitting right on top of the stack as the only
remaining temporary. We also know that new locals are allocated at the top of
the stack<span class="ellipse">&thinsp;.&thinsp;.&thinsp;.&nbsp;</span>right where that value already is. Thus, there&rsquo;s nothing to do. The
temporary simply <em>becomes</em> the local variable. It doesn&rsquo;t get much more
efficient than that.</p>
<p><span name="locals"></span></p><img src="image/local-variables/local-slots.png" alt="Walking through the bytecode execution showing that each initializer's result ends up in the local's slot." />
<aside name="locals">
<p>The code on the left compiles to the sequence of instructions on the right.</p>
</aside>
<p>OK, so what&rsquo;s &ldquo;declaring&rdquo; about? Here&rsquo;s what that does:</p>
<div class="codehilite"><div class="source-file"><em>compiler.c</em><br>
add after <em>identifierConstant</em>()</div>
<pre><span class="k">static</span> <span class="t">void</span> <span class="i">declareVariable</span>() {
  <span class="k">if</span> (<span class="i">current</span>-&gt;<span class="i">scopeDepth</span> == <span class="n">0</span>) <span class="k">return</span>;

  <span class="t">Token</span>* <span class="i">name</span> = &amp;<span class="i">parser</span>.<span class="i">previous</span>;
  <span class="i">addLocal</span>(*<span class="i">name</span>);
}
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, add after <em>identifierConstant</em>()</div>

<p>This is the point where the compiler records the existence of the variable. We
only do this for locals, so if we&rsquo;re in the top-level global scope, we just bail
out. Because global variables are late bound, the compiler doesn&rsquo;t keep track of
which declarations for them it has seen.</p>
<p>But for local variables, the compiler does need to remember that the variable
exists. That&rsquo;s what declaring it does<span class="em">&mdash;</span>it adds it to the compiler&rsquo;s list of
variables in the current scope. We implement that using another new function.</p>
<div class="codehilite"><div class="source-file"><em>compiler.c</em><br>
add after <em>identifierConstant</em>()</div>
<pre><span class="k">static</span> <span class="t">void</span> <span class="i">addLocal</span>(<span class="t">Token</span> <span class="i">name</span>) {
  <span class="t">Local</span>* <span class="i">local</span> = &amp;<span class="i">current</span>-&gt;<span class="i">locals</span>[<span class="i">current</span>-&gt;<span class="i">localCount</span>++];
  <span class="i">local</span>-&gt;<span class="i">name</span> = <span class="i">name</span>;
  <span class="i">local</span>-&gt;<span class="i">depth</span> = <span class="i">current</span>-&gt;<span class="i">scopeDepth</span>;
}
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, add after <em>identifierConstant</em>()</div>

<p>This initializes the next available Local in the compiler&rsquo;s array of variables.
It stores the variable&rsquo;s <span name="lexeme">name</span> and the depth of the
scope that owns the variable.</p>
<aside name="lexeme">
<p>Worried about the lifetime of the string for the variable&rsquo;s name? The Local
directly stores a copy of the Token struct for the identifier. Tokens store a
pointer to the first character of their lexeme and the lexeme&rsquo;s length. That
pointer points into the original source string for the script or REPL entry
being compiled.</p>
<p>As long as that string stays around during the entire compilation process<span class="em">&mdash;</span>which it must since, you know, we&rsquo;re compiling it<span class="em">&mdash;</span>then all of the tokens
pointing into it are fine.</p>
</aside>
<p>Our implementation is fine for a correct Lox program, but what about invalid
code? Let&rsquo;s aim to be robust. The first error to handle is not really the user&rsquo;s
fault, but more a limitation of the VM. The instructions to work with local
variables refer to them by slot index. That index is stored in a single-byte
operand, which means the VM only supports up to 256 local variables in scope at
one time.</p>
<p>If we try to go over that, not only could we not refer to them at runtime, but
the compiler would overwrite its own locals array, too. Let&rsquo;s prevent that.</p>
<div class="codehilite"><pre class="insert-before">static void addLocal(Token name) {
</pre><div class="source-file"><em>compiler.c</em><br>
in <em>addLocal</em>()</div>
<pre class="insert">  <span class="k">if</span> (<span class="i">current</span>-&gt;<span class="i">localCount</span> == <span class="a">UINT8_COUNT</span>) {
    <span class="i">error</span>(<span class="s">&quot;Too many local variables in function.&quot;</span>);
    <span class="k">return</span>;
  }

</pre><pre class="insert-after">  Local* local = &amp;current-&gt;locals[current-&gt;localCount++];
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, in <em>addLocal</em>()</div>

<p>The next case is trickier. Consider:</p>
<div class="codehilite"><pre>{
  <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>At the top level, Lox allows redeclaring a variable with the same name as a
previous declaration because that&rsquo;s useful for the REPL. But inside a local
scope, that&rsquo;s a pretty <span name="rust">weird</span> thing to do. It&rsquo;s likely
to be a mistake, and many languages, including our own Lox, enshrine that
assumption by making this an error.</p>
<aside name="rust">
<p>Interestingly, the Rust programming language <em>does</em> allow this, and idiomatic
code relies on it.</p>
</aside>
<p>Note that the above program is different from this one:</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>;
  }
}
</pre></div>
<p>It&rsquo;s OK to have two variables with the same name in <em>different</em> scopes, even
when the scopes overlap such that both are visible at the same time. That&rsquo;s
shadowing, and Lox does allow that. It&rsquo;s only an error to have two variables
with the same name in the <em>same</em> local scope.</p>
<p>We detect that error like so:</p>
<div class="codehilite"><pre class="insert-before">  Token* name = &amp;parser.previous;
</pre><div class="source-file"><em>compiler.c</em><br>
in <em>declareVariable</em>()</div>
<pre class="insert">  <span class="k">for</span> (<span class="t">int</span> <span class="i">i</span> = <span class="i">current</span>-&gt;<span class="i">localCount</span> - <span class="n">1</span>; <span class="i">i</span> &gt;= <span class="n">0</span>; <span class="i">i</span>--) {
    <span class="t">Local</span>* <span class="i">local</span> = &amp;<span class="i">current</span>-&gt;<span class="i">locals</span>[<span class="i">i</span>];
    <span class="k">if</span> (<span class="i">local</span>-&gt;<span class="i">depth</span> != -<span class="n">1</span> &amp;&amp; <span class="i">local</span>-&gt;<span class="i">depth</span> &lt; <span class="i">current</span>-&gt;<span class="i">scopeDepth</span>) {
      <span class="k">break</span>;<span name="negative"> </span>
    }

    <span class="k">if</span> (<span class="i">identifiersEqual</span>(<span class="i">name</span>, &amp;<span class="i">local</span>-&gt;<span class="i">name</span>)) {
      <span class="i">error</span>(<span class="s">&quot;Already a variable with this name in this scope.&quot;</span>);
    }
  }

</pre><pre class="insert-after">  addLocal(*name);
}
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, in <em>declareVariable</em>()</div>

<aside name="negative">
<p>Don&rsquo;t worry about that odd <code>depth != -1</code> part yet. We&rsquo;ll get to what that&rsquo;s
about later.</p>
</aside>
<p>Local variables are appended to the array when they&rsquo;re declared, which means the
current scope is always at the end of the array. When we declare a new variable,
we start at the end and work backward, looking for an existing variable with the
same name. If we find one in the current scope, we report the error. Otherwise,
if we reach the beginning of the array or a variable owned by another scope,
then we know we&rsquo;ve checked all of the existing variables in the scope.</p>
<p>To see if two identifiers are the same, we use this:</p>
<div class="codehilite"><div class="source-file"><em>compiler.c</em><br>
add after <em>identifierConstant</em>()</div>
<pre><span class="k">static</span> <span class="t">bool</span> <span class="i">identifiersEqual</span>(<span class="t">Token</span>* <span class="i">a</span>, <span class="t">Token</span>* <span class="i">b</span>) {
  <span class="k">if</span> (<span class="i">a</span>-&gt;<span class="i">length</span> != <span class="i">b</span>-&gt;<span class="i">length</span>) <span class="k">return</span> <span class="k">false</span>;
  <span class="k">return</span> <span class="i">memcmp</span>(<span class="i">a</span>-&gt;<span class="i">start</span>, <span class="i">b</span>-&gt;<span class="i">start</span>, <span class="i">a</span>-&gt;<span class="i">length</span>) == <span class="n">0</span>;
}
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, add after <em>identifierConstant</em>()</div>

<p>Since we know the lengths of both lexemes, we check that first. That will fail
quickly for many non-equal strings. If the <span name="hash">lengths</span> are
the same, we check the characters using <code>memcmp()</code>. To get to <code>memcmp()</code>, we
need an include.</p>
<aside name="hash">
<p>It would be a nice little optimization if we could check their hashes, but
tokens aren&rsquo;t full LoxStrings, so we haven&rsquo;t calculated their hashes yet.</p>
</aside>
<div class="codehilite"><pre class="insert-before">#include &lt;stdlib.h&gt;
</pre><div class="source-file"><em>compiler.c</em></div>
<pre class="insert"><span class="a">#include &lt;string.h&gt;</span>
</pre><pre class="insert-after">

#include &quot;common.h&quot;
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em></div>

<p>With this, we&rsquo;re able to bring variables into being. But, like ghosts, they
linger on beyond the scope where they are declared. When a block ends, we need
to put them to rest.</p>
<div class="codehilite"><pre class="insert-before">  current-&gt;scopeDepth--;
</pre><div class="source-file"><em>compiler.c</em><br>
in <em>endScope</em>()</div>
<pre class="insert">

  <span class="k">while</span> (<span class="i">current</span>-&gt;<span class="i">localCount</span> &gt; <span class="n">0</span> &amp;&amp;
         <span class="i">current</span>-&gt;<span class="i">locals</span>[<span class="i">current</span>-&gt;<span class="i">localCount</span> - <span class="n">1</span>].<span class="i">depth</span> &gt;
            <span class="i">current</span>-&gt;<span class="i">scopeDepth</span>) {
    <span class="i">emitByte</span>(<span class="a">OP_POP</span>);
    <span class="i">current</span>-&gt;<span class="i">localCount</span>--;
  }
</pre><pre class="insert-after">}
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, in <em>endScope</em>()</div>

<p>When we pop a scope, we walk backward through the local array looking for any
variables declared at the scope depth we just left. We discard them by simply
decrementing the length of the array.</p>
<p>There is a runtime component to this too. Local variables occupy slots on the
stack. When a local variable goes out of scope, that slot is no longer needed
and should be freed. So, for each variable that we discard, we also emit an
<code>OP_POP</code> <span name="pop">instruction</span> to pop it from the stack.</p>
<aside name="pop">
<p>When multiple local variables go out of scope at once, you get a series of
<code>OP_POP</code> instructions that get interpreted one at a time. A simple optimization
you could add to your Lox implementation is a specialized <code>OP_POPN</code> instruction
that takes an operand for the number of slots to pop and pops them all at once.</p>
</aside>
<h2><a href="#using-locals" id="using-locals"><small>22&#8202;.&#8202;4</small>Using Locals</a></h2>
<p>We can now compile and execute local variable declarations. At runtime, their
values are sitting where they should be on the stack. Let&rsquo;s start using them.
We&rsquo;ll do both variable access and assignment at the same time since they touch
the same functions in the compiler.</p>
<p>We already have code for getting and setting global variables, and<span class="em">&mdash;</span>like good
little software engineers<span class="em">&mdash;</span>we want to reuse as much of that existing code as
we can. Something like this:</p>
<div class="codehilite"><pre class="insert-before">static void namedVariable(Token name, bool canAssign) {
</pre><div class="source-file"><em>compiler.c</em><br>
in <em>namedVariable</em>()<br>
replace 1 line</div>
<pre class="insert">  <span class="t">uint8_t</span> <span class="i">getOp</span>, <span class="i">setOp</span>;
  <span class="t">int</span> <span class="i">arg</span> = <span class="i">resolveLocal</span>(<span class="i">current</span>, &amp;<span class="i">name</span>);
  <span class="k">if</span> (<span class="i">arg</span> != -<span class="n">1</span>) {
    <span class="i">getOp</span> = <span class="a">OP_GET_LOCAL</span>;
    <span class="i">setOp</span> = <span class="a">OP_SET_LOCAL</span>;
  } <span class="k">else</span> {
    <span class="i">arg</span> = <span class="i">identifierConstant</span>(&amp;<span class="i">name</span>);
    <span class="i">getOp</span> = <span class="a">OP_GET_GLOBAL</span>;
    <span class="i">setOp</span> = <span class="a">OP_SET_GLOBAL</span>;
  }
</pre><pre class="insert-after">

  if (canAssign &amp;&amp; match(TOKEN_EQUAL)) {
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, in <em>namedVariable</em>(), replace 1 line</div>

<p>Instead of hardcoding the bytecode instructions emitted for variable access and
assignment, we use a couple of C variables. First, we try to find a local
variable with the given name. If we find one, we use the instructions for
working with locals. Otherwise, we assume it&rsquo;s a global variable and use the
existing bytecode instructions for globals.</p>
<p>A little further down, we use those variables to emit the right instructions.
For assignment:</p>
<div class="codehilite"><pre class="insert-before">  if (canAssign &amp;&amp; match(TOKEN_EQUAL)) {
    expression();
</pre><div class="source-file"><em>compiler.c</em><br>
in <em>namedVariable</em>()<br>
replace 1 line</div>
<pre class="insert">    <span class="i">emitBytes</span>(<span class="i">setOp</span>, (<span class="t">uint8_t</span>)<span class="i">arg</span>);
</pre><pre class="insert-after">  } else {
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, in <em>namedVariable</em>(), replace 1 line</div>

<p>And for access:</p>
<div class="codehilite"><pre class="insert-before">    emitBytes(setOp, (uint8_t)arg);
  } else {
</pre><div class="source-file"><em>compiler.c</em><br>
in <em>namedVariable</em>()<br>
replace 1 line</div>
<pre class="insert">    <span class="i">emitBytes</span>(<span class="i">getOp</span>, (<span class="t">uint8_t</span>)<span class="i">arg</span>);
</pre><pre class="insert-after">  }
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, in <em>namedVariable</em>(), replace 1 line</div>

<p>The real heart of this chapter, the part where we resolve a local variable, is
here:</p>
<div class="codehilite"><div class="source-file"><em>compiler.c</em><br>
add after <em>identifiersEqual</em>()</div>
<pre><span class="k">static</span> <span class="t">int</span> <span class="i">resolveLocal</span>(<span class="t">Compiler</span>* <span class="i">compiler</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">compiler</span>-&gt;<span class="i">localCount</span> - <span class="n">1</span>; <span class="i">i</span> &gt;= <span class="n">0</span>; <span class="i">i</span>--) {
    <span class="t">Local</span>* <span class="i">local</span> = &amp;<span class="i">compiler</span>-&gt;<span class="i">locals</span>[<span class="i">i</span>];
    <span class="k">if</span> (<span class="i">identifiersEqual</span>(<span class="i">name</span>, &amp;<span class="i">local</span>-&gt;<span class="i">name</span>)) {
      <span class="k">return</span> <span class="i">i</span>;
    }
  }

  <span class="k">return</span> -<span class="n">1</span>;
}
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, add after <em>identifiersEqual</em>()</div>

<p>For all that, it&rsquo;s straightforward. We walk the list of locals that are
currently in scope. If one has the same name as the identifier token, the
identifier must refer to that variable. We&rsquo;ve found it! We walk the array
backward so that we find the <em>last</em> declared variable with the identifier. That
ensures that inner local variables correctly shadow locals with the same name in
surrounding scopes.</p>
<p>At runtime, we load and store locals using the stack slot index, so that&rsquo;s what
the compiler needs to calculate after it resolves the variable. Whenever a
variable is declared, we append it to the locals array in Compiler. That means
the first local variable is at index zero, the next one is at index one, and so
on. In other words, the locals array in the compiler has the <em>exact</em> same layout
as the VM&rsquo;s stack will have at runtime. The variable&rsquo;s index in the locals array
is the same as its stack slot. How convenient!</p>
<p>If we make it through the whole array without finding a variable with the given
name, it must not be a local. In that case, we return <code>-1</code> to signal that it
wasn&rsquo;t found and should be assumed to be a global variable instead.</p>
<h3><a href="#interpreting-local-variables" id="interpreting-local-variables"><small>22&#8202;.&#8202;4&#8202;.&#8202;1</small>Interpreting local variables</a></h3>
<p>Our compiler is emitting two new instructions, so let&rsquo;s get them working. First
is loading a local variable:</p>
<div class="codehilite"><pre class="insert-before">  OP_POP,
</pre><div class="source-file"><em>chunk.h</em><br>
in enum <em>OpCode</em></div>
<pre class="insert">  <span class="a">OP_GET_LOCAL</span>,
</pre><pre class="insert-after">  OP_GET_GLOBAL,
</pre></div>
<div class="source-file-narrow"><em>chunk.h</em>, in enum <em>OpCode</em></div>

<p>And its implementation:</p>
<div class="codehilite"><pre class="insert-before">      case OP_POP: pop(); break;
</pre><div class="source-file"><em>vm.c</em><br>
in <em>run</em>()</div>
<pre class="insert">      <span class="k">case</span> <span class="a">OP_GET_LOCAL</span>: {
        <span class="t">uint8_t</span> <span class="i">slot</span> = <span class="a">READ_BYTE</span>();
        <span class="i">push</span>(<span class="i">vm</span>.<span class="i">stack</span>[<span class="i">slot</span>]);<span name="slot"> </span>
        <span class="k">break</span>;
      }
</pre><pre class="insert-after">      case OP_GET_GLOBAL: {
</pre></div>
<div class="source-file-narrow"><em>vm.c</em>, in <em>run</em>()</div>

<p>It takes a single-byte operand for the stack slot where the local lives. It
loads the value from that index and then pushes it on top of the stack where
later instructions can find it.</p>
<aside name="slot">
<p>It seems redundant to push the local&rsquo;s value onto the stack since it&rsquo;s already
on the stack lower down somewhere. The problem is that the other bytecode
instructions only look for data at the <em>top</em> of the stack. This is the core
aspect that makes our bytecode instruction set <em>stack</em>-based.
<a href="a-virtual-machine.html#design-note">Register-based</a> bytecode instruction sets avoid this stack juggling at the
cost of having larger instructions with more operands.</p>
</aside>
<p>Next is assignment:</p>
<div class="codehilite"><pre class="insert-before">  OP_GET_LOCAL,
</pre><div class="source-file"><em>chunk.h</em><br>
in enum <em>OpCode</em></div>
<pre class="insert">  <span class="a">OP_SET_LOCAL</span>,
</pre><pre class="insert-after">  OP_GET_GLOBAL,
</pre></div>
<div class="source-file-narrow"><em>chunk.h</em>, in enum <em>OpCode</em></div>

<p>You can probably predict the implementation.</p>
<div class="codehilite"><pre class="insert-before">      }
</pre><div class="source-file"><em>vm.c</em><br>
in <em>run</em>()</div>
<pre class="insert">      <span class="k">case</span> <span class="a">OP_SET_LOCAL</span>: {
        <span class="t">uint8_t</span> <span class="i">slot</span> = <span class="a">READ_BYTE</span>();
        <span class="i">vm</span>.<span class="i">stack</span>[<span class="i">slot</span>] = <span class="i">peek</span>(<span class="n">0</span>);
        <span class="k">break</span>;
      }
</pre><pre class="insert-after">      case OP_GET_GLOBAL: {
</pre></div>
<div class="source-file-narrow"><em>vm.c</em>, in <em>run</em>()</div>

<p>It takes the assigned value from the top of the stack and stores it in the stack
slot corresponding to the local variable. Note that it doesn&rsquo;t pop the value
from the stack. Remember, assignment is an expression, and every expression
produces a value. The value of an assignment expression is the assigned value
itself, so the VM just leaves the value on the stack.</p>
<p>Our disassembler is incomplete without support for these two new instructions.</p>
<div class="codehilite"><pre class="insert-before">      return simpleInstruction(&quot;OP_POP&quot;, offset);
</pre><div class="source-file"><em>debug.c</em><br>
in <em>disassembleInstruction</em>()</div>
<pre class="insert">    <span class="k">case</span> <span class="a">OP_GET_LOCAL</span>:
      <span class="k">return</span> <span class="i">byteInstruction</span>(<span class="s">&quot;OP_GET_LOCAL&quot;</span>, <span class="i">chunk</span>, <span class="i">offset</span>);
    <span class="k">case</span> <span class="a">OP_SET_LOCAL</span>:
      <span class="k">return</span> <span class="i">byteInstruction</span>(<span class="s">&quot;OP_SET_LOCAL&quot;</span>, <span class="i">chunk</span>, <span class="i">offset</span>);
</pre><pre class="insert-after">    case OP_GET_GLOBAL:
</pre></div>
<div class="source-file-narrow"><em>debug.c</em>, in <em>disassembleInstruction</em>()</div>

<p>The compiler compiles local variables to direct slot access. The local
variable&rsquo;s name never leaves the compiler to make it into the chunk at all.
That&rsquo;s great for performance, but not so great for introspection. When we
disassemble these instructions, we can&rsquo;t show the variable&rsquo;s name like we could
with globals. Instead, we just show the slot number.</p>
<aside name="debug">
<p>Erasing local variable names in the compiler is a real issue if we ever want to
implement a debugger for our VM. When users step through code, they expect to
see the values of local variables organized by their names. To support that,
we&rsquo;d need to output some additional information that tracks the name of each
local variable at each stack slot.</p>
</aside>
<div class="codehilite"><div class="source-file"><em>debug.c</em><br>
add after <em>simpleInstruction</em>()</div>
<pre><span class="k">static</span> <span class="t">int</span> <span class="i">byteInstruction</span>(<span class="k">const</span> <span class="t">char</span>* <span class="i">name</span>, <span class="t">Chunk</span>* <span class="i">chunk</span>,
                           <span class="t">int</span> <span class="i">offset</span>) {
  <span class="t">uint8_t</span> <span class="i">slot</span> = <span class="i">chunk</span>-&gt;<span class="i">code</span>[<span class="i">offset</span> + <span class="n">1</span>];
  <span class="i">printf</span>(<span class="s">&quot;%-16s %4d</span><span class="e">\n</span><span class="s">&quot;</span>, <span class="i">name</span>, <span class="i">slot</span>);
  <span class="k">return</span> <span class="i">offset</span> + <span class="n">2</span>;<span name="debug"> </span>
}
</pre></div>
<div class="source-file-narrow"><em>debug.c</em>, add after <em>simpleInstruction</em>()</div>

<h3><a href="#another-scope-edge-case" id="another-scope-edge-case"><small>22&#8202;.&#8202;4&#8202;.&#8202;2</small>Another scope edge case</a></h3>
<p>We already sunk some time into handling a couple of weird edge cases around
scopes. We made sure shadowing works correctly. We report an error if two
variables in the same local scope have the same name. For reasons that aren&rsquo;t
entirely clear to me, variable scoping seems to have a lot of these wrinkles.
I&rsquo;ve never seen a language where it feels completely <span
name="elegant">elegant</span>.</p>
<aside name="elegant">
<p>No, not even Scheme.</p>
</aside>
<p>We&rsquo;ve got one more edge case to deal with before we end this chapter. Recall this strange beastie we first met in <a href="resolving-and-binding.html#resolving-variable-declarations">jlox&rsquo;s implementation of variable resolution</a>:</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>We slayed it then by splitting a variable&rsquo;s declaration into two phases, and
we&rsquo;ll do that again here:</p><img src="image/local-variables/phases.png" alt="An example variable declaration marked 'declared uninitialized' before the variable name and 'ready for use' after the initializer." />
<p>As soon as the variable declaration begins<span class="em">&mdash;</span>in other words, before its
initializer<span class="em">&mdash;</span>the name is declared in the current scope. The variable exists,
but in a special &ldquo;uninitialized&rdquo; state. Then we compile the initializer. If at
any point in that expression we resolve an identifier that points back to this
variable, we&rsquo;ll see that it is not initialized yet and report an error. After we
finish compiling the initializer, we mark the variable as initialized and ready
for use.</p>
<p>To implement this, when we declare a local, we need to indicate the
&ldquo;uninitialized&rdquo; state somehow. We could add a new field to Local, but let&rsquo;s be a
little more parsimonious with memory. Instead, we&rsquo;ll set the variable&rsquo;s scope
depth to a special sentinel value, <code>-1</code>.</p>
<div class="codehilite"><pre class="insert-before">  local-&gt;name = name;
</pre><div class="source-file"><em>compiler.c</em><br>
in <em>addLocal</em>()<br>
replace 1 line</div>
<pre class="insert">  <span class="i">local</span>-&gt;<span class="i">depth</span> = -<span class="n">1</span>;
</pre><pre class="insert-after">}
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, in <em>addLocal</em>(), replace 1 line</div>

<p>Later, once the variable&rsquo;s initializer has been compiled, we mark it
initialized.</p>
<div class="codehilite"><pre class="insert-before">  if (current-&gt;scopeDepth &gt; 0) {
</pre><div class="source-file"><em>compiler.c</em><br>
in <em>defineVariable</em>()</div>
<pre class="insert">    <span class="i">markInitialized</span>();
</pre><pre class="insert-after">    return;
  }
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, in <em>defineVariable</em>()</div>

<p>That is implemented like so:</p>
<div class="codehilite"><div class="source-file"><em>compiler.c</em><br>
add after <em>parseVariable</em>()</div>
<pre><span class="k">static</span> <span class="t">void</span> <span class="i">markInitialized</span>() {
  <span class="i">current</span>-&gt;<span class="i">locals</span>[<span class="i">current</span>-&gt;<span class="i">localCount</span> - <span class="n">1</span>].<span class="i">depth</span> =
      <span class="i">current</span>-&gt;<span class="i">scopeDepth</span>;
}
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, add after <em>parseVariable</em>()</div>

<p>So this is <em>really</em> what &ldquo;declaring&rdquo; and &ldquo;defining&rdquo; a variable means in the
compiler. &ldquo;Declaring&rdquo; is when the variable is added to the scope, and &ldquo;defining&rdquo;
is when it becomes available for use.</p>
<p>When we resolve a reference to a local variable, we check the scope depth to see
if it&rsquo;s fully defined.</p>
<div class="codehilite"><pre class="insert-before">    if (identifiersEqual(name, &amp;local-&gt;name)) {
</pre><div class="source-file"><em>compiler.c</em><br>
in <em>resolveLocal</em>()</div>
<pre class="insert">      <span class="k">if</span> (<span class="i">local</span>-&gt;<span class="i">depth</span> == -<span class="n">1</span>) {
        <span class="i">error</span>(<span class="s">&quot;Can&#39;t read local variable in its own initializer.&quot;</span>);
      }
</pre><pre class="insert-after">      return i;
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, in <em>resolveLocal</em>()</div>

<p>If the variable has the sentinel depth, it must be a reference to a variable in
its own initializer, and we report that as an error.</p>
<p>That&rsquo;s it for this chapter! We added blocks, local variables, and real,
honest-to-God lexical scoping. Given that we introduced an entirely different
runtime representation for variables, we didn&rsquo;t have to write a lot of code. The
implementation ended up being pretty clean and efficient.</p>
<p>You&rsquo;ll notice that almost all of the code we wrote is in the compiler. Over in
the runtime, it&rsquo;s just two little instructions. You&rsquo;ll see this as a continuing
<span name="static">trend</span> in clox compared to jlox. One of the biggest
hammers in the optimizer&rsquo;s toolbox is pulling work forward into the compiler so
that you don&rsquo;t have to do it at runtime. In this chapter, that meant resolving
exactly which stack slot every local variable occupies. That way, at runtime, no
lookup or resolution needs to happen.</p>
<aside name="static">
<p>You can look at static types as an extreme example of this trend. A statically
typed language takes all of the type analysis and type error handling and sorts
it all out during compilation. Then the runtime doesn&rsquo;t have to waste any time
checking that values have the proper type for their operation. In fact, in some
statically typed languages like C, you don&rsquo;t even <em>know</em> the type at runtime.
The compiler completely erases any representation of a value&rsquo;s type leaving just
the bare bits.</p>
</aside>
<div class="challenges">
<h2><a href="#challenges" id="challenges">Challenges</a></h2>
<ol>
<li>
<p>Our simple local array makes it easy to calculate the stack slot of each
local variable. But it means that when the compiler resolves a reference to
a variable, we have to do a linear scan through the array.</p>
<p>Come up with something more efficient. Do you think the additional
complexity is worth it?</p>
</li>
<li>
<p>How do other languages handle code like this:</p>
<div class="codehilite"><pre><span class="k">var</span> <span class="i">a</span> = <span class="i">a</span>;
</pre></div>
<p>What would you do if it was your language? Why?</p>
</li>
<li>
<p>Many languages make a distinction between variables that can be reassigned
and those that can&rsquo;t. In Java, the <code>final</code> modifier prevents you from
assigning to a variable. In JavaScript, a variable declared with <code>let</code> can
be assigned, but one declared using <code>const</code> can&rsquo;t. Swift treats <code>let</code> as
single-assignment and uses <code>var</code> for assignable variables. Scala and Kotlin
use <code>val</code> and <code>var</code>.</p>
<p>Pick a keyword for a single-assignment variable form to add to Lox. Justify
your choice, then implement it. An attempt to assign to a variable declared
using your new keyword should cause a compile error.</p>
</li>
<li>
<p>Extend clox to allow more than 256 local variables to be in scope at a time.</p>
</li>
</ol>
</div>

<footer>
<a href="jumping-back-and-forth.html" class="next">
  Next Chapter: &ldquo;Jumping Back and Forth&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>