site/types-of-values.html

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

<ul>
    <li><a href="#tagged-unions"><small>18.1</small> Tagged Unions</a></li>
    <li><a href="#lox-values-and-c-values"><small>18.2</small> Lox Values and C Values</a></li>
    <li><a href="#dynamically-typed-numbers"><small>18.3</small> Dynamically Typed Numbers</a></li>
    <li><a href="#two-new-types"><small>18.4</small> Two New Types</a></li>
    <li class="divider"></li>
    <li class="end-part"><a href="#challenges">Challenges</a></li>
</ul>


<div class="prev-next">
    <a href="compiling-expressions.html" title="Compiling Expressions" class="left">&larr;&nbsp;Previous</a>
    <a href="a-bytecode-virtual-machine.html" title="A Bytecode Virtual Machine">&uarr;&nbsp;Up</a>
    <a href="strings.html" title="Strings" 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="compiling-expressions.html" title="Compiling Expressions" class="prev">←</a>
<a href="strings.html" title="Strings" 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">Types of Values<small>18</small></a></h3>

<ul>
    <li><a href="#tagged-unions"><small>18.1</small> Tagged Unions</a></li>
    <li><a href="#lox-values-and-c-values"><small>18.2</small> Lox Values and C Values</a></li>
    <li><a href="#dynamically-typed-numbers"><small>18.3</small> Dynamically Typed Numbers</a></li>
    <li><a href="#two-new-types"><small>18.4</small> Two New Types</a></li>
    <li class="divider"></li>
    <li class="end-part"><a href="#challenges">Challenges</a></li>
</ul>


<div class="prev-next">
    <a href="compiling-expressions.html" title="Compiling Expressions" class="left">&larr;&nbsp;Previous</a>
    <a href="a-bytecode-virtual-machine.html" title="A Bytecode Virtual Machine">&uarr;&nbsp;Up</a>
    <a href="strings.html" title="Strings" class="right">Next&nbsp;&rarr;</a>
</div>  </div>
  <a id="expand-nav">≡</a>
</nav>
</div>

<article class="chapter">

  <div class="number">18</div>
  <h1>Types of Values</h1>

<blockquote>
<p>When you are a Bear of Very Little Brain, and you Think of Things, you find
sometimes that a Thing which seemed very Thingish inside you is quite
different when it gets out into the open and has other people looking at it.</p>
<p><cite>A. A. Milne, <em>Winnie-the-Pooh</em></cite></p>
</blockquote>
<p>The past few chapters were huge, packed full of complex techniques and pages of
code. In this chapter, there&rsquo;s only one new concept to learn and a scattering of
straightforward code. You&rsquo;ve earned a respite.</p>
<p>Lox is <span name="unityped">dynamically</span> typed. A single variable can
hold a Boolean, number, or string at different points in time. At least, that&rsquo;s
the idea. Right now, in clox, all values are numbers. By the end of the chapter,
it will also support Booleans and <code>nil</code>. While those aren&rsquo;t super interesting,
they force us to figure out how our value representation can dynamically handle
different types.</p>
<aside name="unityped">
<p>There is a third category next to statically typed and dynamically typed:
<strong>unityped</strong>. In that paradigm, all variables have a single type, usually a
machine register integer. Unityped languages aren&rsquo;t common today, but some
Forths and BCPL, the language that inspired C, worked like this.</p>
<p>As of this moment, clox is unityped.</p>
</aside>
<h2><a href="#tagged-unions" id="tagged-unions"><small>18&#8202;.&#8202;1</small>Tagged Unions</a></h2>
<p>The nice thing about working in C is that we can build our data structures from
the raw bits up. The bad thing is that we <em>have</em> to do that. C doesn&rsquo;t give you
much for free at compile time and even less at runtime. As far as C is
concerned, the universe is an undifferentiated array of bytes. It&rsquo;s up to us to
decide how many of those bytes to use and what they mean.</p>
<p>In order to choose a value representation, we need to answer two key questions:</p>
<ol>
<li>
<p><strong>How do we represent the type of a value?</strong> If you try to, say, multiply a
number by <code>true</code>, we need to detect that error at runtime and report it. In
order to do that, we need to be able to tell what a value&rsquo;s type is.</p>
</li>
<li>
<p><strong>How do we store the value itself?</strong> We need to not only be able to tell
that three is a number, but that it&rsquo;s different from the number four. I
know, seems obvious, right? But we&rsquo;re operating at a level where it&rsquo;s good
to spell these things out.</p>
</li>
</ol>
<p>Since we&rsquo;re not just designing this language but building it ourselves, when
answering these two questions we also have to keep in mind the implementer&rsquo;s
eternal quest: to do it <em>efficiently</em>.</p>
<p>Language hackers over the years have come up with a variety of clever ways to
pack the above information into as few bits as possible. For now, we&rsquo;ll start
with the simplest, classic solution: a <strong>tagged union</strong>. A value contains two
parts: a type &ldquo;tag&rdquo;, and a payload for the actual value. To store the value&rsquo;s
type, we define an enum for each kind of value the VM supports.</p>
<div class="codehilite"><pre class="insert-before">#include &quot;common.h&quot;

</pre><div class="source-file"><em>value.h</em></div>
<pre class="insert"><span class="k">typedef</span> <span class="k">enum</span> {
  <span class="a">VAL_BOOL</span>,
  <span class="a">VAL_NIL</span>,<span name="user-types"> </span>
  <span class="a">VAL_NUMBER</span>,
} <span class="t">ValueType</span>;

</pre><pre class="insert-after">typedef double Value;
</pre></div>
<div class="source-file-narrow"><em>value.h</em></div>

<aside name="user-types">
<p>The cases here cover each kind of value that has <em>built-in support in the VM</em>.
When we get to adding classes to the language, each class the user defines
doesn&rsquo;t need its own entry in this enum. As far as the VM is concerned, every
instance of a class is the same type: &ldquo;instance&rdquo;.</p>
<p>In other words, this is the VM&rsquo;s notion of &ldquo;type&rdquo;, not the user&rsquo;s.</p>
</aside>
<p>For now, we have only a couple of cases, but this will grow as we add strings,
functions, and classes to clox. In addition to the type, we also need to store
the data for the value<span class="em">&mdash;</span>the <code>double</code> for a number, <code>true</code> or <code>false</code> for a
Boolean. We could define a struct with fields for each possible type.</p><img src="image/types-of-values/struct.png" alt="A struct with two fields laid next to each other in memory." />
<p>But this is a waste of memory. A value can&rsquo;t simultaneously be both a number and
a Boolean. So at any point in time, only one of those fields will be used. C
lets you optimize this by defining a <span name="sum">union</span>. A union
looks like a struct except that all of its fields overlap in memory.</p>
<aside name="sum">
<p>If you&rsquo;re familiar with a language in the ML family, structs and unions in C
roughly mirror the difference between product and sum types, between tuples
and algebraic data types.</p>
</aside><img src="image/types-of-values/union.png" alt="A union with two fields overlapping in memory." />
<p>The size of a union is the size of its largest field. Since the fields all reuse
the same bits, you have to be very careful when working with them. If you store
data using one field and then access it using <span
name="reinterpret">another</span>, you will reinterpret what the underlying bits
mean.</p>
<aside name="reinterpret">
<p>Using a union to interpret bits as different types is the quintessence of C. It
opens up a number of clever optimizations and lets you slice and dice each byte
of memory in ways that memory-safe languages disallow. But it is also wildly
unsafe and will happily saw your fingers off if you don&rsquo;t watch out.</p>
</aside>
<p>As the name &ldquo;tagged union&rdquo; implies, our new value representation combines these
two parts into a single struct.</p>
<div class="codehilite"><pre class="insert-before">} ValueType;

</pre><div class="source-file"><em>value.h</em><br>
add after enum <em>ValueType</em><br>
replace 1 line</div>
<pre class="insert"><span class="k">typedef</span> <span class="k">struct</span> {
  <span class="t">ValueType</span> <span class="i">type</span>;
  <span class="k">union</span> {
    <span class="t">bool</span> <span class="i">boolean</span>;
    <span class="t">double</span> <span class="i">number</span>;
  } <span class="i">as</span>;<span name="as"> </span>
} <span class="t">Value</span>;
</pre><pre class="insert-after">

typedef struct {
</pre></div>
<div class="source-file-narrow"><em>value.h</em>, add after enum <em>ValueType</em>, replace 1 line</div>

<p>There&rsquo;s a field for the type tag, and then a second field containing the union
of all of the underlying values. On a 64-bit machine with a typical C compiler,
the layout looks like this:</p>
<aside name="as">
<p>A smart language hacker gave me the idea to use &ldquo;as&rdquo; for the name of the union
field because it reads nicely, almost like a cast, when you pull the various
values out.</p>
</aside><img src="image/types-of-values/value.png" alt="The full value struct, with the type and as fields next to each other in memory." />
<p>The four-byte type tag comes first, then the union. Most architectures prefer
values be aligned to their size. Since the union field contains an eight-byte
double, the compiler adds four bytes of <span name="pad">padding</span> after
the type field to keep that double on the nearest eight-byte boundary. That
means we&rsquo;re effectively spending eight bytes on the type tag, which only needs
to represent a number between zero and three. We could stuff the enum in a
smaller size, but all that would do is increase the padding.</p>
<aside name="pad">
<p>We could move the tag field <em>after</em> the union, but that doesn&rsquo;t help much
either. Whenever we create an array of Values<span class="em">&mdash;</span>which is where most of our
memory usage for Values will be<span class="em">&mdash;</span>the C compiler will insert that same padding
<em>between</em> each Value to keep the doubles aligned.</p>
</aside>
<p>So our Values are 16 bytes, which seems a little large. We&rsquo;ll improve it
<a href="optimization.html">later</a>. In the meantime, they&rsquo;re still small enough to store on
the C stack and pass around by value. Lox&rsquo;s semantics allow that because the
only types we support so far are <strong>immutable</strong>. If we pass a copy of a Value
containing the number three to some function, we don&rsquo;t need to worry about the
caller seeing modifications to the value. You can&rsquo;t &ldquo;modify&rdquo; three. It&rsquo;s three
forever.</p>
<h2><a href="#lox-values-and-c-values" id="lox-values-and-c-values"><small>18&#8202;.&#8202;2</small>Lox Values and C Values</a></h2>
<p>That&rsquo;s our new value representation, but we aren&rsquo;t done. Right now, the rest of
clox assumes Value is an alias for <code>double</code>. We have code that does a straight C
cast from one to the other. That code is all broken now. So sad.</p>
<p>With our new representation, a Value can <em>contain</em> a double, but it&rsquo;s not
<em>equivalent</em> to it. There is a mandatory conversion step to get from one to the
other. We need to go through the code and insert those conversions to get clox
working again.</p>
<p>We&rsquo;ll implement these conversions as a handful of macros, one for each type and
operation. First, to promote a native C value to a clox Value:</p>
<div class="codehilite"><pre class="insert-before">} Value;
</pre><div class="source-file"><em>value.h</em><br>
add after struct <em>Value</em></div>
<pre class="insert">

<span class="a">#define BOOL_VAL(value)   ((Value){VAL_BOOL, {.boolean = value}})</span>
<span class="a">#define NIL_VAL           ((Value){VAL_NIL, {.number = 0}})</span>
<span class="a">#define NUMBER_VAL(value) ((Value){VAL_NUMBER, {.number = value}})</span>
</pre><pre class="insert-after">

typedef struct {
</pre></div>
<div class="source-file-narrow"><em>value.h</em>, add after struct <em>Value</em></div>

<p>Each one of these takes a C value of the appropriate type and produces a Value
that has the correct type tag and contains the underlying value. This hoists
statically typed values up into clox&rsquo;s dynamically typed universe. In order to
<em>do</em> anything with a Value, though, we need to unpack it and get the C value
back out.</p>
<div class="codehilite"><pre class="insert-before">} Value;
</pre><div class="source-file"><em>value.h</em><br>
add after struct <em>Value</em></div>
<pre class="insert">

<span class="a">#define AS_BOOL(value)    ((value).as.boolean)</span>
<span class="a">#define AS_NUMBER(value)  ((value).as.number)</span>
</pre><pre class="insert-after">

#define BOOL_VAL(value)   ((Value){VAL_BOOL, {.boolean = value}})
</pre></div>
<div class="source-file-narrow"><em>value.h</em>, add after struct <em>Value</em></div>

<aside name="as-null">
<p>There&rsquo;s no <code>AS_NIL</code> macro because there is only one <code>nil</code> value, so a Value with
type <code>VAL_NIL</code> doesn&rsquo;t carry any extra data.</p>
</aside>
<p><span name="as-null">These</span> macros go in the opposite direction. Given a
Value of the right type, they unwrap it and return the corresponding raw C
value. The &ldquo;right type&rdquo; part is important! These macros directly access the
union fields. If we were to do something like:</p>
<div class="codehilite"><pre><span class="t">Value</span> <span class="i">value</span> = <span class="a">BOOL_VAL</span>(<span class="k">true</span>);
<span class="t">double</span> <span class="i">number</span> = <span class="a">AS_NUMBER</span>(<span class="i">value</span>);
</pre></div>
<p>Then we may open a smoldering portal to the Shadow Realm. It&rsquo;s not safe to use
any of the <code>AS_</code> macros unless we know the Value contains the appropriate type.
To that end, we define a last few macros to check a Value&rsquo;s type.</p>
<div class="codehilite"><pre class="insert-before">} Value;
</pre><div class="source-file"><em>value.h</em><br>
add after struct <em>Value</em></div>
<pre class="insert">

<span class="a">#define IS_BOOL(value)    ((value).type == VAL_BOOL)</span>
<span class="a">#define IS_NIL(value)     ((value).type == VAL_NIL)</span>
<span class="a">#define IS_NUMBER(value)  ((value).type == VAL_NUMBER)</span>
</pre><pre class="insert-after">

#define AS_BOOL(value)    ((value).as.boolean)
</pre></div>
<div class="source-file-narrow"><em>value.h</em>, add after struct <em>Value</em></div>

<p><span name="universe">These</span> macros return <code>true</code> if the Value has that
type. Any time we call one of the <code>AS_</code> macros, we need to guard it behind a
call to one of these first. With these eight macros, we can now safely shuttle
data between Lox&rsquo;s dynamic world and C&rsquo;s static one.</p>
<aside name="universe"><img src="image/types-of-values/universe.png" alt="The earthly C firmament with the Lox heavens above." />
<p>The <code>_VAL</code> macros lift a C value into the heavens. The <code>AS_</code> macros bring it
back down.</p>
</aside>
<h2><a href="#dynamically-typed-numbers" id="dynamically-typed-numbers"><small>18&#8202;.&#8202;3</small>Dynamically Typed Numbers</a></h2>
<p>We&rsquo;ve got our value representation and the tools to convert to and from it. All
that&rsquo;s left to get clox running again is to grind through the code and fix every
place where data moves across that boundary. This is one of those sections of
the book that isn&rsquo;t exactly mind-blowing, but I promised I&rsquo;d show you every
single line of code, so here we are.</p>
<p>The first values we create are the constants generated when we compile number
literals. After we convert the lexeme to a C double, we simply wrap it in a
Value before storing it in the constant table.</p>
<div class="codehilite"><pre class="insert-before">  double value = strtod(parser.previous.start, NULL);
</pre><div class="source-file"><em>compiler.c</em><br>
in <em>number</em>()<br>
replace 1 line</div>
<pre class="insert">  <span class="i">emitConstant</span>(<span class="a">NUMBER_VAL</span>(<span class="i">value</span>));
</pre><pre class="insert-after">}
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, in <em>number</em>(), replace 1 line</div>

<p>Over in the runtime, we have a function to print values.</p>
<div class="codehilite"><pre class="insert-before">void printValue(Value value) {
</pre><div class="source-file"><em>value.c</em><br>
in <em>printValue</em>()<br>
replace 1 line</div>
<pre class="insert"> <span class="i">printf</span>(<span class="s">&quot;%g&quot;</span>, <span class="a">AS_NUMBER</span>(<span class="i">value</span>));
</pre><pre class="insert-after">}
</pre></div>
<div class="source-file-narrow"><em>value.c</em>, in <em>printValue</em>(), replace 1 line</div>

<p>Right before we send the Value to <code>printf()</code>, we unwrap it and extract the
double value. We&rsquo;ll revisit this function shortly to add the other types, but
let&rsquo;s get our existing code working first.</p>
<h3><a href="#unary-negation-and-runtime-errors" id="unary-negation-and-runtime-errors"><small>18&#8202;.&#8202;3&#8202;.&#8202;1</small>Unary negation and runtime errors</a></h3>
<p>The next simplest operation is unary negation. It pops a value off the stack,
negates it, and pushes the result. Now that we have other types of values, we
can&rsquo;t assume the operand is a number anymore. The user could just as well do:</p>
<div class="codehilite"><pre><span class="k">print</span> -<span class="k">false</span>; <span class="c">// Uh...</span>
</pre></div>
<p>We need to handle that gracefully, which means it&rsquo;s time for <em>runtime errors</em>.
Before performing an operation that requires a certain type, we need to make
sure the Value <em>is</em> that type.</p>
<p>For unary negation, the check looks like this:</p>
<div class="codehilite"><pre class="insert-before">      case OP_DIVIDE:   BINARY_OP(/); break;
</pre><div class="source-file"><em>vm.c</em><br>
in <em>run</em>()<br>
replace 1 line</div>
<pre class="insert">      <span class="k">case</span> <span class="a">OP_NEGATE</span>:
        <span class="k">if</span> (!<span class="a">IS_NUMBER</span>(<span class="i">peek</span>(<span class="n">0</span>))) {
          <span class="i">runtimeError</span>(<span class="s">&quot;Operand must be a number.&quot;</span>);
          <span class="k">return</span> <span class="a">INTERPRET_RUNTIME_ERROR</span>;
        }
        <span class="i">push</span>(<span class="a">NUMBER_VAL</span>(-<span class="a">AS_NUMBER</span>(<span class="i">pop</span>())));
        <span class="k">break</span>;
</pre><pre class="insert-after">      case OP_RETURN: {
</pre></div>
<div class="source-file-narrow"><em>vm.c</em>, in <em>run</em>(), replace 1 line</div>

<p>First, we check to see if the Value on top of the stack is a number. If it&rsquo;s
not, we report the runtime error and <span name="halt">stop</span> the
interpreter. Otherwise, we keep going. Only after this validation do we unwrap
the operand, negate it, wrap the result and push it.</p>
<aside name="halt">
<p>Lox&rsquo;s approach to error-handling is rather<span class="ellipse">&thinsp;.&thinsp;.&thinsp;.&nbsp;</span><em>spare</em>. All errors are fatal and
immediately halt the interpreter. There&rsquo;s no way for user code to recover from
an error. If Lox were a real language, this is one of the first things I would
remedy.</p>
</aside>
<p>To access the Value, we use a new little function.</p>
<div class="codehilite"><div class="source-file"><em>vm.c</em><br>
add after <em>pop</em>()</div>
<pre><span class="k">static</span> <span class="t">Value</span> <span class="i">peek</span>(<span class="t">int</span> <span class="i">distance</span>) {
  <span class="k">return</span> <span class="i">vm</span>.<span class="i">stackTop</span>[-<span class="n">1</span> - <span class="i">distance</span>];
}
</pre></div>
<div class="source-file-narrow"><em>vm.c</em>, add after <em>pop</em>()</div>

<p>It returns a Value from the stack but doesn&rsquo;t <span name="peek">pop</span> it.
The <code>distance</code> argument is how far down from the top of the stack to look: zero
is the top, one is one slot down, etc.</p>
<aside name="peek">
<p>Why not just pop the operand and then validate it? We could do that. In later
chapters, it will be important to leave operands on the stack to ensure the
garbage collector can find them if a collection is triggered in the middle of
the operation. I do the same thing here mostly out of habit.</p>
</aside>
<p>We report the runtime error using a new function that we&rsquo;ll get a lot of mileage
out of over the remainder of the book.</p>
<div class="codehilite"><div class="source-file"><em>vm.c</em><br>
add after <em>resetStack</em>()</div>
<pre><span class="k">static</span> <span class="t">void</span> <span class="i">runtimeError</span>(<span class="k">const</span> <span class="t">char</span>* <span class="i">format</span>, ...) {
  <span class="t">va_list</span> <span class="i">args</span>;
  <span class="i">va_start</span>(<span class="i">args</span>, <span class="i">format</span>);
  <span class="i">vfprintf</span>(<span class="i">stderr</span>, <span class="i">format</span>, <span class="i">args</span>);
  <span class="i">va_end</span>(<span class="i">args</span>);
  <span class="i">fputs</span>(<span class="s">&quot;</span><span class="e">\n</span><span class="s">&quot;</span>, <span class="i">stderr</span>);

  <span class="t">size_t</span> <span class="i">instruction</span> = <span class="i">vm</span>.<span class="i">ip</span> - <span class="i">vm</span>.<span class="i">chunk</span>-&gt;<span class="i">code</span> - <span class="n">1</span>;
  <span class="t">int</span> <span class="i">line</span> = <span class="i">vm</span>.<span class="i">chunk</span>-&gt;<span class="i">lines</span>[<span class="i">instruction</span>];
  <span class="i">fprintf</span>(<span class="i">stderr</span>, <span class="s">&quot;[line %d] in script</span><span class="e">\n</span><span class="s">&quot;</span>, <span class="i">line</span>);
  <span class="i">resetStack</span>();
}
</pre></div>
<div class="source-file-narrow"><em>vm.c</em>, add after <em>resetStack</em>()</div>

<p>You&rsquo;ve certainly <em>called</em> variadic functions<span class="em">&mdash;</span>ones that take a varying number
of arguments<span class="em">&mdash;</span>in C before: <code>printf()</code> is one. But you may not have <em>defined</em>
your own. This book isn&rsquo;t a C <span name="tutorial">tutorial</span>, so I&rsquo;ll
skim over it here, but basically the <code>...</code> and <code>va_list</code> stuff let us pass an
arbitrary number of arguments to <code>runtimeError()</code>. It forwards those on to
<code>vfprintf()</code>, which is the flavor of <code>printf()</code> that takes an explicit
<code>va_list</code>.</p>
<aside name="tutorial">
<p>If you are looking for a C tutorial, I love <em><a href="https://www.cs.princeton.edu/~bwk/cbook.html">The C Programming Language</a></em>,
usually called &ldquo;K&amp;R&rdquo; in honor of its authors. It&rsquo;s not entirely up to date, but
the quality of the writing more than makes up for it.</p>
</aside>
<p>Callers can pass a format string to <code>runtimeError()</code> followed by a number of
arguments, just like they can when calling <code>printf()</code> directly. <code>runtimeError()</code>
then formats and prints those arguments. We won&rsquo;t take advantage of that in this
chapter, but later chapters will produce formatted runtime error messages that
contain other data.</p>
<p>After we show the hopefully helpful error message, we tell the user which <span
name="stack">line</span> of their code was being executed when the error
occurred. Since we left the tokens behind in the compiler, we look up the line
in the debug information compiled into the chunk. If our compiler did its job
right, that corresponds to the line of source code that the bytecode was
compiled from.</p>
<p>We look into the chunk&rsquo;s debug line array using the current bytecode instruction
index <em>minus one</em>. That&rsquo;s because the interpreter advances past each instruction
before executing it. So, at the point that we call <code>runtimeError()</code>, the failed
instruction is the previous one.</p>
<aside name="stack">
<p>Just showing the immediate line where the error occurred doesn&rsquo;t provide much
context. Better would be a full stack trace. But we don&rsquo;t even have functions to
call yet, so there is no call stack to trace.</p>
</aside>
<p>In order to use <code>va_list</code> and the macros for working with it, we need to bring
in a standard header.</p>
<div class="codehilite"><div class="source-file"><em>vm.c</em><br>
add to top of file</div>
<pre class="insert"><span class="a">#include &lt;stdarg.h&gt;</span>
</pre><pre class="insert-after">#include &lt;stdio.h&gt;
</pre></div>
<div class="source-file-narrow"><em>vm.c</em>, add to top of file</div>

<p>With this, our VM can not only do the right thing when we negate numbers (like
it used to before we broke it), but it also gracefully handles erroneous
attempts to negate other types (which we don&rsquo;t have yet, but still).</p>
<h3><a href="#binary-arithmetic-operators" id="binary-arithmetic-operators"><small>18&#8202;.&#8202;3&#8202;.&#8202;2</small>Binary arithmetic operators</a></h3>
<p>We have our runtime error machinery in place now, so fixing the binary operators
is easier even though they&rsquo;re more complex. We support four binary operators
today: <code>+</code>, <code>-</code>, <code>*</code>, and <code>/</code>. The only difference between them is which
underlying C operator they use. To minimize redundant code between the four
operators, we wrapped up the commonality in a big preprocessor macro that takes
the operator token as a parameter.</p>
<p>That macro seemed like overkill a <a href="a-virtual-machine.html#binary-operators">few chapters ago</a>, but we get the benefit
from it today. It lets us add the necessary type checking and conversions in one
place.</p>
<div class="codehilite"><pre class="insert-before">#define READ_CONSTANT() (vm.chunk-&gt;constants.values[READ_BYTE()])
</pre><div class="source-file"><em>vm.c</em><br>
in <em>run</em>()<br>
replace 6 lines</div>
<pre class="insert"><span class="a">#define BINARY_OP(valueType, op) \</span>
<span class="a">    do { \</span>
<span class="a">      if (!IS_NUMBER(peek(0)) || !IS_NUMBER(peek(1))) { \</span>
<span class="a">        runtimeError(&quot;Operands must be numbers.&quot;); \</span>
<span class="a">        return INTERPRET_RUNTIME_ERROR; \</span>
<span class="a">      } \</span>
<span class="a">      double b = AS_NUMBER(pop()); \</span>
<span class="a">      double a = AS_NUMBER(pop()); \</span>
<span class="a">      push(valueType(a op b)); \</span>
<span class="a">    } while (false)</span>
</pre><pre class="insert-after">

  for (;;) {
</pre></div>
<div class="source-file-narrow"><em>vm.c</em>, in <em>run</em>(), replace 6 lines</div>

<p>Yeah, I realize that&rsquo;s a monster of a macro. It&rsquo;s not what I&rsquo;d normally consider
good C practice, but let&rsquo;s roll with it. The changes are similar to what we did
for unary negate. First, we check that the two operands are both numbers. If
either isn&rsquo;t, we report a runtime error and yank the ejection seat lever.</p>
<p>If the operands are fine, we pop them both and unwrap them. Then we apply the
given operator, wrap the result, and push it back on the stack. Note that we
don&rsquo;t wrap the result by directly using <code>NUMBER_VAL()</code>. Instead, the wrapper to
use is passed in as a macro <span name="macro">parameter</span>. For our
existing arithmetic operators, the result is a number, so we pass in the
<code>NUMBER_VAL</code> macro.</p>
<aside name="macro">
<p>Did you know you can pass macros as parameters to macros? Now you do!</p>
</aside>
<div class="codehilite"><pre class="insert-before">      }
</pre><div class="source-file"><em>vm.c</em><br>
in <em>run</em>()<br>
replace 4 lines</div>
<pre class="insert">      <span class="k">case</span> <span class="a">OP_ADD</span>:      <span class="a">BINARY_OP</span>(<span class="a">NUMBER_VAL</span>, +); <span class="k">break</span>;
      <span class="k">case</span> <span class="a">OP_SUBTRACT</span>: <span class="a">BINARY_OP</span>(<span class="a">NUMBER_VAL</span>, -); <span class="k">break</span>;
      <span class="k">case</span> <span class="a">OP_MULTIPLY</span>: <span class="a">BINARY_OP</span>(<span class="a">NUMBER_VAL</span>, *); <span class="k">break</span>;
      <span class="k">case</span> <span class="a">OP_DIVIDE</span>:   <span class="a">BINARY_OP</span>(<span class="a">NUMBER_VAL</span>, /); <span class="k">break</span>;
</pre><pre class="insert-after">      case OP_NEGATE:
</pre></div>
<div class="source-file-narrow"><em>vm.c</em>, in <em>run</em>(), replace 4 lines</div>

<p>Soon, I&rsquo;ll show you why we made the wrapping macro an argument.</p>
<h2><a href="#two-new-types" id="two-new-types"><small>18&#8202;.&#8202;4</small>Two New Types</a></h2>
<p>All of our existing clox code is back in working order. Finally, it&rsquo;s time to
add some new types. We&rsquo;ve got a running numeric calculator that now does a
number of pointless paranoid runtime type checks. We can represent other types
internally, but there&rsquo;s no way for a user&rsquo;s program to ever create a Value of
one of those types.</p>
<p>Not until now, that is. We&rsquo;ll start by adding compiler support for the three new
literals: <code>true</code>, <code>false</code>, and <code>nil</code>. They&rsquo;re all pretty simple, so we&rsquo;ll do all
three in a single batch.</p>
<p>With number literals, we had to deal with the fact that there are billions of
possible numeric values. We attended to that by storing the literal&rsquo;s value in
the chunk&rsquo;s constant table and emitting a bytecode instruction that simply
loaded that constant. We could do the same thing for the new types. We&rsquo;d store,
say, <code>true</code>, in the constant table, and use an <code>OP_CONSTANT</code> to read it out.</p>
<p>But given that there are literally (heh) only three possible values we need to
worry about with these new types, it&rsquo;s gratuitous<span class="em">&mdash;</span>and <span
name="small">slow!</span><span class="em">&mdash;</span>to waste a two-byte instruction and a constant
table entry on them. Instead, we&rsquo;ll define three dedicated instructions to push
each of these literals on the stack.</p>
<aside name="small" class="bottom">
<p>I&rsquo;m not kidding about dedicated operations for certain constant values being
faster. A bytecode VM spends much of its execution time reading and decoding
instructions. The fewer, simpler instructions you need for a given piece of
behavior, the faster it goes. Short instructions dedicated to common operations
are a classic optimization.</p>
<p>For example, the Java bytecode instruction set has dedicated instructions for
loading 0.0, 1.0, 2.0, and the integer values from -1 through 5. (This ends up
being a vestigial optimization given that most mature JVMs now JIT-compile the
bytecode to machine code before execution anyway.)</p>
</aside>
<div class="codehilite"><pre class="insert-before">  OP_CONSTANT,
</pre><div class="source-file"><em>chunk.h</em><br>
in enum <em>OpCode</em></div>
<pre class="insert">  <span class="a">OP_NIL</span>,
  <span class="a">OP_TRUE</span>,
  <span class="a">OP_FALSE</span>,
</pre><pre class="insert-after">  OP_ADD,
</pre></div>
<div class="source-file-narrow"><em>chunk.h</em>, in enum <em>OpCode</em></div>

<p>Our scanner already treats <code>true</code>, <code>false</code>, and <code>nil</code> as keywords, so we can
skip right to the parser. With our table-based Pratt parser, we just need to
slot parser functions into the rows associated with those keyword token types.
We&rsquo;ll use the same function in all three slots. Here:</p>
<div class="codehilite"><pre class="insert-before">  [TOKEN_ELSE]          = {NULL,     NULL,   PREC_NONE},
</pre><div class="source-file"><em>compiler.c</em><br>
replace 1 line</div>
<pre class="insert">  [<span class="a">TOKEN_FALSE</span>]         = {<span class="i">literal</span>,  <span class="a">NULL</span>,   <span class="a">PREC_NONE</span>},
</pre><pre class="insert-after">  [TOKEN_FOR]           = {NULL,     NULL,   PREC_NONE},
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, replace 1 line</div>

<p>Here:</p>
<div class="codehilite"><pre class="insert-before">  [TOKEN_THIS]          = {NULL,     NULL,   PREC_NONE},
</pre><div class="source-file"><em>compiler.c</em><br>
replace 1 line</div>
<pre class="insert">  [<span class="a">TOKEN_TRUE</span>]          = {<span class="i">literal</span>,  <span class="a">NULL</span>,   <span class="a">PREC_NONE</span>},
</pre><pre class="insert-after">  [TOKEN_VAR]           = {NULL,     NULL,   PREC_NONE},
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, replace 1 line</div>

<p>And here:</p>
<div class="codehilite"><pre class="insert-before">  [TOKEN_IF]            = {NULL,     NULL,   PREC_NONE},
</pre><div class="source-file"><em>compiler.c</em><br>
replace 1 line</div>
<pre class="insert">  [<span class="a">TOKEN_NIL</span>]           = {<span class="i">literal</span>,  <span class="a">NULL</span>,   <span class="a">PREC_NONE</span>},
</pre><pre class="insert-after">  [TOKEN_OR]            = {NULL,     NULL,   PREC_NONE},
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, replace 1 line</div>

<p>When the parser encounters <code>false</code>, <code>nil</code>, or <code>true</code>, in prefix position, it
calls this new parser function:</p>
<div class="codehilite"><div class="source-file"><em>compiler.c</em><br>
add after <em>binary</em>()</div>
<pre><span class="k">static</span> <span class="t">void</span> <span class="i">literal</span>() {
  <span class="k">switch</span> (<span class="i">parser</span>.<span class="i">previous</span>.<span class="i">type</span>) {
    <span class="k">case</span> <span class="a">TOKEN_FALSE</span>: <span class="i">emitByte</span>(<span class="a">OP_FALSE</span>); <span class="k">break</span>;
    <span class="k">case</span> <span class="a">TOKEN_NIL</span>: <span class="i">emitByte</span>(<span class="a">OP_NIL</span>); <span class="k">break</span>;
    <span class="k">case</span> <span class="a">TOKEN_TRUE</span>: <span class="i">emitByte</span>(<span class="a">OP_TRUE</span>); <span class="k">break</span>;
    <span class="k">default</span>: <span class="k">return</span>; <span class="c">// Unreachable.</span>
  }
}
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, add after <em>binary</em>()</div>

<p>Since <code>parsePrecedence()</code> has already consumed the keyword token, all we need to
do is output the proper instruction. We <span name="switch">figure</span> that
out based on the type of token we parsed. Our front end can now compile Boolean
and nil literals to bytecode. Moving down the execution pipeline, we reach the
interpreter.</p>
<aside name="switch">
<p>We could have used separate parser functions for each literal and saved
ourselves a switch but that felt needlessly verbose to me. I think it&rsquo;s mostly a
matter of taste.</p>
</aside>
<div class="codehilite"><pre class="insert-before">      case OP_CONSTANT: {
        Value constant = READ_CONSTANT();
        push(constant);
        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_NIL</span>: <span class="i">push</span>(<span class="a">NIL_VAL</span>); <span class="k">break</span>;
      <span class="k">case</span> <span class="a">OP_TRUE</span>: <span class="i">push</span>(<span class="a">BOOL_VAL</span>(<span class="k">true</span>)); <span class="k">break</span>;
      <span class="k">case</span> <span class="a">OP_FALSE</span>: <span class="i">push</span>(<span class="a">BOOL_VAL</span>(<span class="k">false</span>)); <span class="k">break</span>;
</pre><pre class="insert-after">      case OP_ADD:      BINARY_OP(NUMBER_VAL, +); break;
</pre></div>
<div class="source-file-narrow"><em>vm.c</em>, in <em>run</em>()</div>

<p>This is pretty self-explanatory. Each instruction summons the appropriate value
and pushes it onto the stack. We shouldn&rsquo;t forget our disassembler either.</p>
<div class="codehilite"><pre class="insert-before">    case OP_CONSTANT:
      return constantInstruction(&quot;OP_CONSTANT&quot;, chunk, 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_NIL</span>:
      <span class="k">return</span> <span class="i">simpleInstruction</span>(<span class="s">&quot;OP_NIL&quot;</span>, <span class="i">offset</span>);
    <span class="k">case</span> <span class="a">OP_TRUE</span>:
      <span class="k">return</span> <span class="i">simpleInstruction</span>(<span class="s">&quot;OP_TRUE&quot;</span>, <span class="i">offset</span>);
    <span class="k">case</span> <span class="a">OP_FALSE</span>:
      <span class="k">return</span> <span class="i">simpleInstruction</span>(<span class="s">&quot;OP_FALSE&quot;</span>, <span class="i">offset</span>);
</pre><pre class="insert-after">    case OP_ADD:
</pre></div>
<div class="source-file-narrow"><em>debug.c</em>, in <em>disassembleInstruction</em>()</div>

<p>With this in place, we can run this Earth-shattering program:</p>
<div class="codehilite"><pre><span class="k">true</span>
</pre></div>
<p>Except that when the interpreter tries to print the result, it blows up. We need
to extend <code>printValue()</code> to handle the new types too:</p>
<div class="codehilite"><pre class="insert-before">void printValue(Value value) {
</pre><div class="source-file"><em>value.c</em><br>
in <em>printValue</em>()<br>
replace 1 line</div>
<pre class="insert">  <span class="k">switch</span> (<span class="i">value</span>.<span class="i">type</span>) {
    <span class="k">case</span> <span class="a">VAL_BOOL</span>:
      <span class="i">printf</span>(<span class="a">AS_BOOL</span>(<span class="i">value</span>) ? <span class="s">&quot;true&quot;</span> : <span class="s">&quot;false&quot;</span>);
      <span class="k">break</span>;
    <span class="k">case</span> <span class="a">VAL_NIL</span>: <span class="i">printf</span>(<span class="s">&quot;nil&quot;</span>); <span class="k">break</span>;
    <span class="k">case</span> <span class="a">VAL_NUMBER</span>: <span class="i">printf</span>(<span class="s">&quot;%g&quot;</span>, <span class="a">AS_NUMBER</span>(<span class="i">value</span>)); <span class="k">break</span>;
  }
</pre><pre class="insert-after">}
</pre></div>
<div class="source-file-narrow"><em>value.c</em>, in <em>printValue</em>(), replace 1 line</div>

<p>There we go! Now we have some new types. They just aren&rsquo;t very useful yet. Aside
from the literals, you can&rsquo;t really <em>do</em> anything with them. It will be a while
before <code>nil</code> comes into play, but we can start putting Booleans to work in the
logical operators.</p>
<h3><a href="#logical-not-and-falsiness" id="logical-not-and-falsiness"><small>18&#8202;.&#8202;4&#8202;.&#8202;1</small>Logical not and falsiness</a></h3>
<p>The simplest logical operator is our old exclamatory friend unary not.</p>
<div class="codehilite"><pre><span class="k">print</span> !<span class="k">true</span>; <span class="c">// &quot;false&quot;</span>
</pre></div>
<p>This new operation gets a new instruction.</p>
<div class="codehilite"><pre class="insert-before">  OP_DIVIDE,
</pre><div class="source-file"><em>chunk.h</em><br>
in enum <em>OpCode</em></div>
<pre class="insert">  <span class="a">OP_NOT</span>,
</pre><pre class="insert-after">  OP_NEGATE,
</pre></div>
<div class="source-file-narrow"><em>chunk.h</em>, in enum <em>OpCode</em></div>

<p>We can reuse the <code>unary()</code> parser function we wrote for unary negation to
compile a not expression. We just need to slot it into the parsing table.</p>
<div class="codehilite"><pre class="insert-before">  [TOKEN_STAR]          = {NULL,     binary, PREC_FACTOR},
</pre><div class="source-file"><em>compiler.c</em><br>
replace 1 line</div>
<pre class="insert">  [<span class="a">TOKEN_BANG</span>]          = {<span class="i">unary</span>,    <span class="a">NULL</span>,   <span class="a">PREC_NONE</span>},
</pre><pre class="insert-after">  [TOKEN_BANG_EQUAL]    = {NULL,     NULL,   PREC_NONE},
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, replace 1 line</div>

<p>Because I knew we were going to do this, the <code>unary()</code> function already has a
switch on the token type to figure out which bytecode instruction to output. We
merely add another case.</p>
<div class="codehilite"><pre class="insert-before">  switch (operatorType) {
</pre><div class="source-file"><em>compiler.c</em><br>
in <em>unary</em>()</div>
<pre class="insert">    <span class="k">case</span> <span class="a">TOKEN_BANG</span>: <span class="i">emitByte</span>(<span class="a">OP_NOT</span>); <span class="k">break</span>;
</pre><pre class="insert-after">    case TOKEN_MINUS: emitByte(OP_NEGATE); break;
    default: return; // Unreachable.
  }
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, in <em>unary</em>()</div>

<p>That&rsquo;s it for the front end. Let&rsquo;s head over to the VM and conjure this
instruction into life.</p>
<div class="codehilite"><pre class="insert-before">      case OP_DIVIDE:   BINARY_OP(NUMBER_VAL, /); 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_NOT</span>:
        <span class="i">push</span>(<span class="a">BOOL_VAL</span>(<span class="i">isFalsey</span>(<span class="i">pop</span>())));
        <span class="k">break</span>;
</pre><pre class="insert-after">      case OP_NEGATE:
</pre></div>
<div class="source-file-narrow"><em>vm.c</em>, in <em>run</em>()</div>

<p>Like our previous unary operator, it pops the one operand, performs the
operation, and pushes the result. And, as we did there, we have to worry about
dynamic typing. Taking the logical not of <code>true</code> is easy, but there&rsquo;s nothing
preventing an unruly programmer from writing something like this:</p>
<div class="codehilite"><pre><span class="k">print</span> !<span class="k">nil</span>;
</pre></div>
<p>For unary minus, we made it an error to negate anything that isn&rsquo;t a <span
name="negate">number</span>. But Lox, like most scripting languages, is more
permissive when it comes to <code>!</code> and other contexts where a Boolean is expected.
The rule for how other types are handled is called &ldquo;falsiness&rdquo;, and we implement
it here:</p>
<aside name="negate">
<p>Now I can&rsquo;t help but try to figure out what it would mean to negate other types
of values. <code>nil</code> is probably its own negation, sort of like a weird pseudo-zero.
Negating a string could, uh, reverse it?</p>
</aside>
<div class="codehilite"><div class="source-file"><em>vm.c</em><br>
add after <em>peek</em>()</div>
<pre><span class="k">static</span> <span class="t">bool</span> <span class="i">isFalsey</span>(<span class="t">Value</span> <span class="i">value</span>) {
  <span class="k">return</span> <span class="a">IS_NIL</span>(<span class="i">value</span>) || (<span class="a">IS_BOOL</span>(<span class="i">value</span>) &amp;&amp; !<span class="a">AS_BOOL</span>(<span class="i">value</span>));
}
</pre></div>
<div class="source-file-narrow"><em>vm.c</em>, add after <em>peek</em>()</div>

<p>Lox follows Ruby in that <code>nil</code> and <code>false</code> are falsey and every other value
behaves like <code>true</code>. We&rsquo;ve got a new instruction we can generate, so we also
need to be able to <em>un</em>generate it in the disassembler.</p>
<div class="codehilite"><pre class="insert-before">    case OP_DIVIDE:
      return simpleInstruction(&quot;OP_DIVIDE&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_NOT</span>:
      <span class="k">return</span> <span class="i">simpleInstruction</span>(<span class="s">&quot;OP_NOT&quot;</span>, <span class="i">offset</span>);
</pre><pre class="insert-after">    case OP_NEGATE:
</pre></div>
<div class="source-file-narrow"><em>debug.c</em>, in <em>disassembleInstruction</em>()</div>

<h3><a href="#equality-and-comparison-operators" id="equality-and-comparison-operators"><small>18&#8202;.&#8202;4&#8202;.&#8202;2</small>Equality and comparison operators</a></h3>
<p>That wasn&rsquo;t too bad. Let&rsquo;s keep the momentum going and knock out the equality
and comparison operators too: <code>==</code>, <code>!=</code>, <code>&lt;</code>, <code>&gt;</code>, <code>&lt;=</code>, and <code>&gt;=</code>. That covers
all of the operators that return Boolean results except the logical operators
<code>and</code> and <code>or</code>. Since those need to short-circuit (basically do a little
control flow) we aren&rsquo;t ready for them yet.</p>
<p>Here are the new instructions for those operators:</p>
<div class="codehilite"><pre class="insert-before">  OP_FALSE,
</pre><div class="source-file"><em>chunk.h</em><br>
in enum <em>OpCode</em></div>
<pre class="insert">  <span class="a">OP_EQUAL</span>,
  <span class="a">OP_GREATER</span>,
  <span class="a">OP_LESS</span>,
</pre><pre class="insert-after">  OP_ADD,
</pre></div>
<div class="source-file-narrow"><em>chunk.h</em>, in enum <em>OpCode</em></div>

<p>Wait, only three? What about <code>!=</code>, <code>&lt;=</code>, and <code>&gt;=</code>? We could create instructions
for those too. Honestly, the VM would execute faster if we did, so we <em>should</em>
do that if the goal is performance.</p>
<p>But my main goal is to teach you about bytecode compilers. I want you to start
internalizing the idea that the bytecode instructions don&rsquo;t need to closely
follow the user&rsquo;s source code. The VM has total freedom to use whatever
instruction set and code sequences it wants as long as they have the right
user-visible behavior.</p>
<p>The expression <code>a != b</code> has the same semantics as <code>!(a == b)</code>, so the compiler
is free to compile the former as if it were the latter. Instead of a dedicated
<code>OP_NOT_EQUAL</code> instruction, it can output an <code>OP_EQUAL</code> followed by an <code>OP_NOT</code>.
Likewise, <code>a &lt;= b</code> is the <span name="same">same</span> as <code>!(a &gt; b)</code> and <code>a &gt;= b</code> is <code>!(a &lt; b)</code>. Thus, we only need three new instructions.</p>
<aside name="same" class="bottom">
<p><em>Is</em> <code>a &lt;= b</code> always the same as <code>!(a &gt; b)</code>? According to <a href="https://en.wikipedia.org/wiki/IEEE_754">IEEE 754</a>, all
comparison operators return false when an operand is NaN. That means <code>NaN &lt;= 1</code>
is false and <code>NaN &gt; 1</code> is also false. But our desugaring assumes the latter is
always the negation of the former.</p>
<p>For the book, we won&rsquo;t get hung up on this, but these kinds of details will
matter in your real language implementations.</p>
</aside>
<p>Over in the parser, though, we do have six new operators to slot into the parse
table. We use the same <code>binary()</code> parser function from before. Here&rsquo;s the row
for <code>!=</code>:</p>
<div class="codehilite"><pre class="insert-before">  [TOKEN_BANG]          = {unary,    NULL,   PREC_NONE},
</pre><div class="source-file"><em>compiler.c</em><br>
replace 1 line</div>
<pre class="insert">  [<span class="a">TOKEN_BANG_EQUAL</span>]    = {<span class="a">NULL</span>,     <span class="i">binary</span>, <span class="a">PREC_EQUALITY</span>},
</pre><pre class="insert-after">  [TOKEN_EQUAL]         = {NULL,     NULL,   PREC_NONE},
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, replace 1 line</div>

<p>The remaining five operators are a little farther down in the table.</p>
<div class="codehilite"><pre class="insert-before">  [TOKEN_EQUAL]         = {NULL,     NULL,   PREC_NONE},
</pre><div class="source-file"><em>compiler.c</em><br>
replace 5 lines</div>
<pre class="insert">  [<span class="a">TOKEN_EQUAL_EQUAL</span>]   = {<span class="a">NULL</span>,     <span class="i">binary</span>, <span class="a">PREC_EQUALITY</span>},
  [<span class="a">TOKEN_GREATER</span>]       = {<span class="a">NULL</span>,     <span class="i">binary</span>, <span class="a">PREC_COMPARISON</span>},
  [<span class="a">TOKEN_GREATER_EQUAL</span>] = {<span class="a">NULL</span>,     <span class="i">binary</span>, <span class="a">PREC_COMPARISON</span>},
  [<span class="a">TOKEN_LESS</span>]          = {<span class="a">NULL</span>,     <span class="i">binary</span>, <span class="a">PREC_COMPARISON</span>},
  [<span class="a">TOKEN_LESS_EQUAL</span>]    = {<span class="a">NULL</span>,     <span class="i">binary</span>, <span class="a">PREC_COMPARISON</span>},
</pre><pre class="insert-after">  [TOKEN_IDENTIFIER]    = {NULL,     NULL,   PREC_NONE},
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, replace 5 lines</div>

<p>Inside <code>binary()</code> we already have a switch to generate the right bytecode for
each token type. We add cases for the six new operators.</p>
<div class="codehilite"><pre class="insert-before">  switch (operatorType) {
</pre><div class="source-file"><em>compiler.c</em><br>
in <em>binary</em>()</div>
<pre class="insert">    <span class="k">case</span> <span class="a">TOKEN_BANG_EQUAL</span>:    <span class="i">emitBytes</span>(<span class="a">OP_EQUAL</span>, <span class="a">OP_NOT</span>); <span class="k">break</span>;
    <span class="k">case</span> <span class="a">TOKEN_EQUAL_EQUAL</span>:   <span class="i">emitByte</span>(<span class="a">OP_EQUAL</span>); <span class="k">break</span>;
    <span class="k">case</span> <span class="a">TOKEN_GREATER</span>:       <span class="i">emitByte</span>(<span class="a">OP_GREATER</span>); <span class="k">break</span>;
    <span class="k">case</span> <span class="a">TOKEN_GREATER_EQUAL</span>: <span class="i">emitBytes</span>(<span class="a">OP_LESS</span>, <span class="a">OP_NOT</span>); <span class="k">break</span>;
    <span class="k">case</span> <span class="a">TOKEN_LESS</span>:          <span class="i">emitByte</span>(<span class="a">OP_LESS</span>); <span class="k">break</span>;
    <span class="k">case</span> <span class="a">TOKEN_LESS_EQUAL</span>:    <span class="i">emitBytes</span>(<span class="a">OP_GREATER</span>, <span class="a">OP_NOT</span>); <span class="k">break</span>;
</pre><pre class="insert-after">    case TOKEN_PLUS:          emitByte(OP_ADD); break;
</pre></div>
<div class="source-file-narrow"><em>compiler.c</em>, in <em>binary</em>()</div>

<p>The <code>==</code>, <code>&lt;</code>, and <code>&gt;</code> operators output a single instruction. The others output
a pair of instructions, one to evalute the inverse operation, and then an
<code>OP_NOT</code> to flip the result. Six operators for the price of three instructions!</p>
<p>That means over in the VM, our job is simpler. Equality is the most general
operation.</p>
<div class="codehilite"><pre class="insert-before">      case OP_FALSE: push(BOOL_VAL(false)); 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_EQUAL</span>: {
        <span class="t">Value</span> <span class="i">b</span> = <span class="i">pop</span>();
        <span class="t">Value</span> <span class="i">a</span> = <span class="i">pop</span>();
        <span class="i">push</span>(<span class="a">BOOL_VAL</span>(<span class="i">valuesEqual</span>(<span class="i">a</span>, <span class="i">b</span>)));
        <span class="k">break</span>;
      }
</pre><pre class="insert-after">      case OP_ADD:      BINARY_OP(NUMBER_VAL, +); break;
</pre></div>
<div class="source-file-narrow"><em>vm.c</em>, in <em>run</em>()</div>

<p>You can evaluate <code>==</code> on any pair of objects, even objects of different types.
There&rsquo;s enough complexity that it makes sense to shunt that logic over to a
separate function. That function always returns a C <code>bool</code>, so we can safely
wrap the result in a <code>BOOL_VAL</code>. The function relates to Values, so it lives
over in the &ldquo;value&rdquo; module.</p>
<div class="codehilite"><pre class="insert-before">} ValueArray;

</pre><div class="source-file"><em>value.h</em><br>
add after struct <em>ValueArray</em></div>
<pre class="insert"><span class="t">bool</span> <span class="i">valuesEqual</span>(<span class="t">Value</span> <span class="i">a</span>, <span class="t">Value</span> <span class="i">b</span>);
</pre><pre class="insert-after">void initValueArray(ValueArray* array);
</pre></div>
<div class="source-file-narrow"><em>value.h</em>, add after struct <em>ValueArray</em></div>

<p>And here&rsquo;s the implementation:</p>
<div class="codehilite"><div class="source-file"><em>value.c</em><br>
add after <em>printValue</em>()</div>
<pre><span class="t">bool</span> <span class="i">valuesEqual</span>(<span class="t">Value</span> <span class="i">a</span>, <span class="t">Value</span> <span class="i">b</span>) {
  <span class="k">if</span> (<span class="i">a</span>.<span class="i">type</span> != <span class="i">b</span>.<span class="i">type</span>) <span class="k">return</span> <span class="k">false</span>;
  <span class="k">switch</span> (<span class="i">a</span>.<span class="i">type</span>) {
    <span class="k">case</span> <span class="a">VAL_BOOL</span>:   <span class="k">return</span> <span class="a">AS_BOOL</span>(<span class="i">a</span>) == <span class="a">AS_BOOL</span>(<span class="i">b</span>);
    <span class="k">case</span> <span class="a">VAL_NIL</span>:    <span class="k">return</span> <span class="k">true</span>;
    <span class="k">case</span> <span class="a">VAL_NUMBER</span>: <span class="k">return</span> <span class="a">AS_NUMBER</span>(<span class="i">a</span>) == <span class="a">AS_NUMBER</span>(<span class="i">b</span>);
    <span class="k">default</span>:         <span class="k">return</span> <span class="k">false</span>; <span class="c">// Unreachable.</span>
  }
}
</pre></div>
<div class="source-file-narrow"><em>value.c</em>, add after <em>printValue</em>()</div>

<p>First, we check the types. If the Values have <span
name="equal">different</span> types, they are definitely not equal. Otherwise,
we unwrap the two Values and compare them directly.</p>
<aside name="equal">
<p>Some languages have &ldquo;implicit conversions&rdquo; where values of different types may
be considered equal if one can be converted to the other&rsquo;s type. For example,
the number 0 is equivalent to the string &ldquo;0&rdquo; in JavaScript. This looseness was a
large enough source of pain that JS added a separate &ldquo;strict equality&rdquo; operator,
<code>===</code>.</p>
<p>PHP considers the strings &ldquo;1&rdquo; and &ldquo;01&rdquo; to be equivalent because both can be
converted to equivalent numbers, though the ultimate reason is because PHP was
designed by a Lovecraftian eldritch god to destroy the mind.</p>
<p>Most dynamically typed languages that have separate integer and floating-point
number types consider values of different number types equal if the numeric
values are the same (so, say, 1.0 is equal to 1), though even that seemingly
innocuous convenience can bite the unwary.</p>
</aside>
<p>For each value type, we have a separate case that handles comparing the value
itself. Given how similar the cases are, you might wonder why we can&rsquo;t simply
<code>memcmp()</code> the two Value structs and be done with it. The problem is that
because of padding and different-sized union fields, a Value contains unused
bits. C gives no guarantee about what is in those, so it&rsquo;s possible that two
equal Values actually differ in memory that isn&rsquo;t used.</p><img src="image/types-of-values/memcmp.png" alt="The memory respresentations of two equal values that differ in unused bytes." />
<p>(You wouldn&rsquo;t believe how much pain I went through before learning this fact.)</p>
<p>Anyway, as we add more types to clox, this function will grow new cases. For
now, these three are sufficient. The other comparison operators are easier since
they work only on numbers.</p>
<div class="codehilite"><pre class="insert-before">        push(BOOL_VAL(valuesEqual(a, b)));
        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_GREATER</span>:  <span class="a">BINARY_OP</span>(<span class="a">BOOL_VAL</span>, &gt;); <span class="k">break</span>;
      <span class="k">case</span> <span class="a">OP_LESS</span>:     <span class="a">BINARY_OP</span>(<span class="a">BOOL_VAL</span>, &lt;); <span class="k">break</span>;
</pre><pre class="insert-after">      case OP_ADD:      BINARY_OP(NUMBER_VAL, +); break;
</pre></div>
<div class="source-file-narrow"><em>vm.c</em>, in <em>run</em>()</div>

<p>We already extended the <code>BINARY_OP</code> macro to handle operators that return
non-numeric types. Now we get to use that. We pass in <code>BOOL_VAL</code> since the
result value type is Boolean. Otherwise, it&rsquo;s no different from plus or minus.</p>
<p>As always, the coda to today&rsquo;s aria is disassembling the new instructions.</p>
<div class="codehilite"><pre class="insert-before">    case OP_FALSE:
      return simpleInstruction(&quot;OP_FALSE&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_EQUAL</span>:
      <span class="k">return</span> <span class="i">simpleInstruction</span>(<span class="s">&quot;OP_EQUAL&quot;</span>, <span class="i">offset</span>);
    <span class="k">case</span> <span class="a">OP_GREATER</span>:
      <span class="k">return</span> <span class="i">simpleInstruction</span>(<span class="s">&quot;OP_GREATER&quot;</span>, <span class="i">offset</span>);
    <span class="k">case</span> <span class="a">OP_LESS</span>:
      <span class="k">return</span> <span class="i">simpleInstruction</span>(<span class="s">&quot;OP_LESS&quot;</span>, <span class="i">offset</span>);
</pre><pre class="insert-after">    case OP_ADD:
</pre></div>
<div class="source-file-narrow"><em>debug.c</em>, in <em>disassembleInstruction</em>()</div>

<p>With that, our numeric calculator has become something closer to a general
expression evaluator. Fire up clox and type in:</p>
<div class="codehilite"><pre>!(<span class="n">5</span> - <span class="n">4</span> &gt; <span class="n">3</span> * <span class="n">2</span> == !<span class="k">nil</span>)
</pre></div>
<p>OK, I&rsquo;ll admit that&rsquo;s maybe not the most <em>useful</em> expression, but we&rsquo;re making
progress. We have one missing built-in type with its own literal form: strings.
Those are much more complex because strings can vary in size. That tiny
difference turns out to have implications so large that we give strings <a href="strings.html">their
very own chapter</a>.</p>
<div class="challenges">
<h2><a href="#challenges" id="challenges">Challenges</a></h2>
<ol>
<li>
<p>We could reduce our binary operators even further than we did here. Which
other instructions can you eliminate, and how would the compiler cope with
their absence?</p>
</li>
<li>
<p>Conversely, we can improve the speed of our bytecode VM by adding more
specific instructions that correspond to higher-level operations. What
instructions would you define to speed up the kind of user code we added
support for in this chapter?</p>
</li>
</ol>
</div>

<footer>
<a href="strings.html" class="next">
  Next Chapter: &ldquo;Strings&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>