<blockquote>
<p>“Python is about having the simplest, dumbest compiler imaginable.”<br />
—Guido van Rossum, <em>Masterminds of Programming</em></p>
</blockquote>
<p>People write source code, machines run machine code. A compiler turns
one into the other—how? Somehow stones, taught to read our commands,
obey, and the compiler acts at the heart of this magic: it’s the spell
that interprets the spell.</p>
<p>Take a course following one of the excellent traditional textbooks
such as the <a href="https://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811">Dragon Book</a>—whose cover art acknowledges the aura of the
fearsome and uncanny around the subject—and you might spend all
semester building one compiler, for a language much simpler than the
one you write it in. Did you just call on a big genie to make a small
one?</p>
<p>In this article, we’ll make a self-reliant genie—that is, a
small compiler able to compile itself. We’ll write it in and for a
subset of Python 3. The result—call it Tailbiter—will be a toy,
but less of a toy than usual in an introduction: besides the
self-compiling, it’ll include some details of debugging support. To
make room for these emphases, we will ignore the topic of
optimization—or, in plainer terms, of making the output code less
stupid.</p>
<p>All you’ll need to follow along is comfort with recursion
over a tree, nested functions, and reading a program
dependent on some built-in Python libraries and types that I’ll survey
but not delve into.</p>
<p>I wrote this article to accompany <a href="http://aosabook.org/en/500L/a-python-interpreter-written-in-python.html">“A Python Interpreter Written in
Python”</a>
by fellow Recurser Allison Kaptur. Her chapter explains the CPython
bytecode virtual machine, which takes the output of a compiler and
executes it. I’ve tried to make this article self-contained, but
you’re encouraged to read the other as well. You may also find it
helpful to <a href="https://github.com/darius/tailbiter">read or run the code</a>
without all this prose around it.</p>
<p>So, where do we start?</p>
<p>When I began this project, I knew quite a bit about how to write a compiler,
but not very much about the Python virtual machine which we’re targeting. Right
away I hit the first snag the textbooks don’t talk about: inadequate
documentation.</p>
<p>We’ll respond to this challenge by building in stages, from a seed just capable of
turning the simplest source code into working bytecode, learning from each
stage how to grow into the next. Start with an example of our input and our
output: a trivial program, from its source text to parsed syntax and then to
runnable bytecode. This technique of “growing” your program in small stages is
useful when working in an uncertain domain.</p>
<h2 id="the-input-an-abstract-syntax-tree">The input: an abstract syntax tree</h2>
<p>Say hello!</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in greet.py:
</span><span class="n">name</span> <span class="o">=</span> <span class="s">'Chrysophylax'</span>
<span class="k">print</span><span class="p">(</span><span class="s">'Hi,'</span><span class="p">,</span> <span class="n">name</span><span class="p">)</span>
</code></pre></div>
<p>The first step is to dissect this text and expose its grammatical
structure: that is, to parse it. The parsed form is called an abstract
syntax tree (or AST); Python’s <code class="language-plaintext highlighter-rouge">ast.parse</code> function can produce it for
us. How <code class="language-plaintext highlighter-rouge">ast.parse</code> works would take a whole separate article.</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in transcripts:
</span><span class="o">>>></span> <span class="kn">import</span> <span class="nn">ast</span><span class="p">,</span> <span class="n">dis</span><span class="p">,</span> <span class="n">astpp</span> <span class="c1"># astpp from http://alexleone.blogspot.com/2010/01/python-ast-pretty-printer.html
</span><span class="o">>>></span> <span class="k">with</span> <span class="nb">open</span><span class="p">(</span><span class="s">'greet.py'</span><span class="p">)</span> <span class="k">as</span> <span class="n">f</span><span class="p">:</span> <span class="n">module_text</span> <span class="o">=</span> <span class="n">f</span><span class="p">.</span><span class="n">read</span><span class="p">()</span>
<span class="p">...</span>
<span class="o">>>></span> <span class="n">module_ast</span> <span class="o">=</span> <span class="n">ast</span><span class="p">.</span><span class="n">parse</span><span class="p">(</span><span class="n">module_text</span><span class="p">)</span>
<span class="o">>>></span> <span class="k">print</span><span class="p">(</span><span class="n">astpp</span><span class="p">.</span><span class="n">dump</span><span class="p">(</span><span class="n">module_ast</span><span class="p">,</span> <span class="n">include_attributes</span><span class="o">=</span><span class="bp">True</span><span class="p">))</span>
<span class="n">Module</span><span class="p">(</span><span class="n">body</span><span class="o">=</span><span class="p">[</span>
<span class="n">Assign</span><span class="p">(</span><span class="n">targets</span><span class="o">=</span><span class="p">[</span>
<span class="n">Name</span><span class="p">(</span><span class="nb">id</span><span class="o">=</span><span class="s">'name'</span><span class="p">,</span> <span class="n">ctx</span><span class="o">=</span><span class="n">Store</span><span class="p">(),</span> <span class="n">lineno</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span> <span class="n">col_offset</span><span class="o">=</span><span class="mi">0</span><span class="p">),</span>
<span class="p">],</span> <span class="n">value</span><span class="o">=</span><span class="n">Str</span><span class="p">(</span><span class="n">s</span><span class="o">=</span><span class="s">'Chrysophylax'</span><span class="p">,</span> <span class="n">lineno</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span> <span class="n">col_offset</span><span class="o">=</span><span class="mi">7</span><span class="p">),</span> <span class="n">lineno</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span> <span class="n">col_offset</span><span class="o">=</span><span class="mi">0</span><span class="p">),</span>
<span class="n">Expr</span><span class="p">(</span><span class="n">value</span><span class="o">=</span><span class="n">Call</span><span class="p">(</span><span class="n">func</span><span class="o">=</span><span class="n">Name</span><span class="p">(</span><span class="nb">id</span><span class="o">=</span><span class="s">'print'</span><span class="p">,</span> <span class="n">ctx</span><span class="o">=</span><span class="n">Load</span><span class="p">(),</span> <span class="n">lineno</span><span class="o">=</span><span class="mi">2</span><span class="p">,</span> <span class="n">col_offset</span><span class="o">=</span><span class="mi">0</span><span class="p">),</span> <span class="n">args</span><span class="o">=</span><span class="p">[</span>
<span class="n">Str</span><span class="p">(</span><span class="n">s</span><span class="o">=</span><span class="s">'Hi,'</span><span class="p">,</span> <span class="n">lineno</span><span class="o">=</span><span class="mi">2</span><span class="p">,</span> <span class="n">col_offset</span><span class="o">=</span><span class="mi">6</span><span class="p">),</span>
<span class="n">Name</span><span class="p">(</span><span class="nb">id</span><span class="o">=</span><span class="s">'name'</span><span class="p">,</span> <span class="n">ctx</span><span class="o">=</span><span class="n">Load</span><span class="p">(),</span> <span class="n">lineno</span><span class="o">=</span><span class="mi">2</span><span class="p">,</span> <span class="n">col_offset</span><span class="o">=</span><span class="mi">16</span><span class="p">),</span>
<span class="p">],</span> <span class="n">keywords</span><span class="o">=</span><span class="p">[],</span> <span class="n">starargs</span><span class="o">=</span><span class="bp">None</span><span class="p">,</span> <span class="n">kwargs</span><span class="o">=</span><span class="bp">None</span><span class="p">,</span> <span class="n">lineno</span><span class="o">=</span><span class="mi">2</span><span class="p">,</span> <span class="n">col_offset</span><span class="o">=</span><span class="mi">0</span><span class="p">),</span> <span class="n">lineno</span><span class="o">=</span><span class="mi">2</span><span class="p">,</span> <span class="n">col_offset</span><span class="o">=</span><span class="mi">0</span><span class="p">),</span>
<span class="p">])</span>
</code></pre></div>
<p>We get an <code class="language-plaintext highlighter-rouge">ast.Module</code> whose <code class="language-plaintext highlighter-rouge">body</code> is a list of more
of these <code class="language-plaintext highlighter-rouge">ast</code> objects—in this case two, an <code class="language-plaintext highlighter-rouge">ast.Assign</code>
representing <code class="language-plaintext highlighter-rouge">name = 'Chrysophylax'</code> and an <code class="language-plaintext highlighter-rouge">ast.Expr</code> representing the call
to <code class="language-plaintext highlighter-rouge">print</code>—each of these being built out of further <code class="language-plaintext highlighter-rouge">ast</code> objects: a
tree of them. Each object has fields proper to its type, plus a
<code class="language-plaintext highlighter-rouge">lineno</code> (line number) and <code class="language-plaintext highlighter-rouge">col_offset</code> telling where in the source
text it was parsed from. We’ll sweat these details more when we get to
them.</p>
<p>You can find all the AST classes and their fields in
<a href="https://github.com/python/cpython/blob/3.4/Parser/Python.asdl">Python.asdl</a>
in the Python 3 source distribution. It’s 100+ lines long, with
roughly one line per class; we’ll need to handle a fair fraction of
them to achieve our goal of a self-hosting compiler.</p>
<h2 id="the-output-bytecode">The output: bytecode</h2>
<p>Compiling the module (with Python’s built-in compiler, for now)
yields a code object, which is an internal Python type:</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in transcripts:
</span><span class="o">>>></span> <span class="n">module_code</span> <span class="o">=</span> <span class="nb">compile</span><span class="p">(</span><span class="n">module_ast</span><span class="p">,</span> <span class="s">'greet.py'</span><span class="p">,</span> <span class="s">'exec'</span><span class="p">)</span>
<span class="o">>>></span> <span class="n">module_code</span>
<span class="o"><</span><span class="n">code</span> <span class="nb">object</span> <span class="o"><</span><span class="n">module</span><span class="o">></span> <span class="n">at</span> <span class="mh">0xffdd76b0</span><span class="p">,</span> <span class="nb">file</span> <span class="s">"greet.py"</span><span class="p">,</span> <span class="n">line</span> <span class="mi">1</span><span class="o">></span>
</code></pre></div>
<p>It has a bunch of attributes prefixed with <code class="language-plaintext highlighter-rouge">co_</code>:</p>
<div class="highlight"><pre><code># in examples:
co_argcount 0
co_cellvars ()
co_code b'd\x00\x00Z\x00\x00e\x01\x00d\x01\x00e\x00\x00\x83\x02\x00\x01d\x02\x00S'
co_consts ('Chrysophylax', 'Hi,', None)
co_filename greet.py
co_firstlineno 1
co_flags 64
co_freevars ()
co_kwonlyargcount 0
co_lnotab b'\x06\x01'
co_name <module>
co_names ('name', 'print')
co_nlocals 0
co_stacksize 3
co_varnames ()
</code></pre></div>
<p>What happened to our program? Mostly it’s encoded into <code class="language-plaintext highlighter-rouge">co_code</code>: a
sequence of bytecodes in a bytestring<sup id="fnref:1"><a class="footnote" href="https://codewords.recurse.com/feed.xml#fn:1">1</a></sup>. These bytecodes can be
“disassembled” (made human-readable) using <code class="language-plaintext highlighter-rouge">dis.dis</code>:</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in transcripts:
</span><span class="o">>>></span> <span class="n">dis</span><span class="p">.</span><span class="n">dis</span><span class="p">(</span><span class="n">module_code</span><span class="p">)</span>
<span class="mi">1</span> <span class="mi">0</span> <span class="n">LOAD_CONST</span> <span class="mi">0</span> <span class="p">(</span><span class="s">'Chrysophylax'</span><span class="p">)</span>
<span class="mi">3</span> <span class="n">STORE_NAME</span> <span class="mi">0</span> <span class="p">(</span><span class="n">name</span><span class="p">)</span>
<span class="mi">2</span> <span class="mi">6</span> <span class="n">LOAD_NAME</span> <span class="mi">1</span> <span class="p">(</span><span class="k">print</span><span class="p">)</span>
<span class="mi">9</span> <span class="n">LOAD_CONST</span> <span class="mi">1</span> <span class="p">(</span><span class="s">'Hi,'</span><span class="p">)</span>
<span class="mi">12</span> <span class="n">LOAD_NAME</span> <span class="mi">0</span> <span class="p">(</span><span class="n">name</span><span class="p">)</span>
<span class="mi">15</span> <span class="n">CALL_FUNCTION</span> <span class="mi">2</span> <span class="p">(</span><span class="mi">2</span> <span class="n">positional</span><span class="p">,</span> <span class="mi">0</span> <span class="n">keyword</span> <span class="n">pair</span><span class="p">)</span>
<span class="mi">18</span> <span class="n">POP_TOP</span>
<span class="mi">19</span> <span class="n">LOAD_CONST</span> <span class="mi">2</span> <span class="p">(</span><span class="bp">None</span><span class="p">)</span>
<span class="mi">22</span> <span class="n">RETURN_VALUE</span>
</code></pre></div>
<p>On the left are source-code line numbers (1 and 2); down the middle go
bytecode instructions, each labeled with the address it’s encoded at;
and on the right each instruction may get an optional argument. The
first line, then, shows us the instruction at address 0: a <code class="language-plaintext highlighter-rouge">LOAD_CONST</code>
instruction, with 0 as an argument. (For a <code class="language-plaintext highlighter-rouge">LOAD_CONST</code> the argument
means an index into the <code class="language-plaintext highlighter-rouge">co_consts</code> attribute, whose 0th entry, above,
is indeed <code class="language-plaintext highlighter-rouge">'Chrysophylax'</code>.) This instruction appears in <code class="language-plaintext highlighter-rouge">co_code</code> as
<code class="language-plaintext highlighter-rouge">d\x00\x00</code>: one byte <code class="language-plaintext highlighter-rouge">d</code> which happens to mean <code class="language-plaintext highlighter-rouge">LOAD_CONST</code>, followed
by two bytes encoding the integer 0. (Don’t worry yet about the exact
details; we’re looking for a general impression of how the program is encoded.)</p>
<p>Since that first instruction took three bytes, the next (<code class="language-plaintext highlighter-rouge">STORE_NAME</code>)
appears at address 3. It also has 0 as its argument, but this time
indexing into <code class="language-plaintext highlighter-rouge">co_names</code>. (That is, at runtime the bytecode
interpreter will take the value it just loaded and store it in the
variable listed at index 0 of <code class="language-plaintext highlighter-rouge">co_names</code>: in this case, <code class="language-plaintext highlighter-rouge">name</code>.)</p>
<p>Those two bytecodes implemented the first line of source code (<code class="language-plaintext highlighter-rouge">name =
'Chrysophylax'</code>). The second line’s bytecode follows at addresses 6 through
18, with some new wrinkles in instruction arguments: <code class="language-plaintext highlighter-rouge">CALL_FUNCTION</code>
has two, each of one byte; and <code class="language-plaintext highlighter-rouge">POP_TOP</code> has no argument, making the
whole instruction fit in a byte. (What <code class="language-plaintext highlighter-rouge">POP_TOP</code> does, we’ll come back
to; likewise the details of how <code class="language-plaintext highlighter-rouge">print</code>’s arguments get passed.)</p>
<p>Finally, the last two instructions (at 19 and 22) return from running
the module.</p>
<p>Zooming back out, what did the compiler do? It converted a tree
structure into a sequence of instructions to perform the operations in
the right order. Each subtree of the parse tree turned into a
subsequence of the instructions. Diagramming the AST together with the
assembly code shows this correspondence<sup id="fnref:2"><a class="footnote" href="https://codewords.recurse.com/feed.xml#fn:2">2</a></sup>:</p>
<div class="highlight"><pre><code>Module(
body=[
Assign(
value=Str(s='Chrysophylax'), 0 LOAD_CONST 0 ('Chrysophylax')
targets=[Name(id='name',ctx=Store())] 3 STORE_NAME 0 (name)
),
Expr(
value=Call(
func=Name(id='print', ctx=Load()), 6 LOAD_NAME 1 (print)
args=[
Str(s='Hi,'), 9 LOAD_CONST 1 ('Hi,')
Name(id='name', ctx=Load()), 12 LOAD_NAME 0 (name)
]
) 15 CALL_FUNCTION 2 (2 positional, 0 keyword pair)
) 18 POP_TOP
] 19 LOAD_CONST 2 (None)
22 RETURN_VALUE
)
</code></pre></div>
<p>Many of the nodes in this tree turned into one bytecode instruction
each, in almost the same order. (<code class="language-plaintext highlighter-rouge">Call</code> precedes its arguments in the
tree, but <code class="language-plaintext highlighter-rouge">CALL_FUNCTION</code> follows them.) That’s a common pattern but
with plenty of exceptions.</p>
<p>The bytecode we just saw was meant for CPython 3.4; in other versions
of Python the bytecode varies, maybe even
for this tiny example. It might crash other interpreters. The AST types
can also change from version to version, though typically less, and with
less drastic consequences (an exception instead of a crash or a subtle
low-level bug). In this article we’ll stick to Python 3.4; you can find
the tweaks for 3.5 or 3.6 in <a href="https://github.com/darius/tailbiter/tree/master/article-code">the code repository</a>.</p>
<h3 id="a-symbolic-assembly-form">A symbolic assembly form</h3>
<p>Now that we’ve defined our problem a bit better, we can take our first step:
building a compiler that can compile <code class="language-plaintext highlighter-rouge">greet.py</code>. We will do this by somehow
translating the ast produced by <code class="language-plaintext highlighter-rouge">greet.py</code> into bytecode.</p>
<p>To create the code object we saw above, it’d help to be able to write
Python code that resembles the disassembly. Like this:</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in examples.py:
</span><span class="n">assembly_for_greet</span> <span class="o">=</span> <span class="p">(</span> <span class="n">SetLineNo</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span>
<span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">LOAD_CONST</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span>
<span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">STORE_NAME</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span>
<span class="o">+</span> <span class="n">SetLineNo</span><span class="p">(</span><span class="mi">2</span><span class="p">)</span>
<span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">LOAD_NAME</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span>
<span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">LOAD_CONST</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span>
<span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">LOAD_NAME</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span>
<span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">CALL_FUNCTION</span><span class="p">(</span><span class="mi">2</span><span class="p">)</span>
<span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">POP_TOP</span>
<span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">LOAD_CONST</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span>
<span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">RETURN_VALUE</span><span class="p">)</span>
</code></pre></div>
<p>Later we’ll get to the support code that lets us write this; first
let’s see how it’s used. <code class="language-plaintext highlighter-rouge">SetLineNo</code> tells which source line the
following instructions derive from; it’s a pseudo-instruction,
supplying debug info to the code object, instead of going into the
bytecode string with <code class="language-plaintext highlighter-rouge">op.LOAD_CONST(0)</code> and the rest. These
symbolic instructions and pseudo-instructions are all Python objects
that understand <code class="language-plaintext highlighter-rouge">+</code> to mean concatenation. Their “sum” then is <em>also</em>
an object representing assembly code (as in the Gang of Four
“composite” pattern, or a monoid if that’s how you were raised). Thus,
we can build our code in pieces to be strung together, like</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in examples.py:
</span><span class="n">stmt1</span> <span class="o">=</span> <span class="n">op</span><span class="p">.</span><span class="n">LOAD_CONST</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span> <span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">STORE_NAME</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span>
<span class="n">call</span> <span class="o">=</span> <span class="p">(</span><span class="n">op</span><span class="p">.</span><span class="n">LOAD_NAME</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span> <span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">LOAD_CONST</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span> <span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">LOAD_NAME</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span>
<span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">CALL_FUNCTION</span><span class="p">(</span><span class="mi">2</span><span class="p">))</span>
<span class="n">stmt2</span> <span class="o">=</span> <span class="n">call</span> <span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">POP_TOP</span>
<span class="n">assembly_for_greet</span> <span class="o">=</span> <span class="p">(</span> <span class="n">SetLineNo</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span> <span class="o">+</span> <span class="n">stmt1</span>
<span class="o">+</span> <span class="n">SetLineNo</span><span class="p">(</span><span class="mi">2</span><span class="p">)</span> <span class="o">+</span> <span class="n">stmt2</span>
<span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">LOAD_CONST</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span> <span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">RETURN_VALUE</span><span class="p">)</span>
</code></pre></div>
<p>which produces the same bytecode: it doesn’t matter how we chunk the
assembly.</p>
<p>There are a couple of reasons why this intermediate “assembly
language” is a useful place to start building our program. Since the
bytecode specification is a source of major uncertainty for us, this
layer isolates our tinkering with the bytecode to a very specific
place in our program. Since the bytecode specification also changes
more often than the AST spec does, this also provides us with an
“insulating layer” between these two problem domains.</p>
<p>A higher-level assembly language could’ve been made where instead of
<code class="language-plaintext highlighter-rouge">op.LOAD_CONST(0)</code> this example would say <code class="language-plaintext highlighter-rouge">op.LOAD_CONST('Chrysophylax')</code>,
leaving it to the assembler to turn <code class="language-plaintext highlighter-rouge">'Chrysophylax'</code> into an index into
<code class="language-plaintext highlighter-rouge">co_consts</code>. Likewise <code class="language-plaintext highlighter-rouge">op.STORE_NAME</code> would take a string argument,
and so on. Such a design would better suit a general-purpose bytecode
assembler; but Tailbiter will be ruthless in doing only what’s
needed.
It’s simple for the code generator to encode the arguments into
integers, more so than for the assembler.</p>
<h2 id="the-seed-a-hello-world-compiler">The seed: a “hello world” compiler</h2>
<p>We want to build a code object, but we don’t know all the details that
go into one. To face these uncertainties and start learning, let’s
make a complete working system for a tiny core subset of the problem:
just enough to run our <code class="language-plaintext highlighter-rouge">greet.py</code>.</p>
<div class="highlight"><pre><code># in figure 0: AST types understood by Tailbiter version 0.
mod = Module(stmt* body)
stmt = Assign(expr* targets, expr value)
| Expr(expr value)
expr = Call(expr func, expr* args, keyword* keywords)
| Num(object n)
| Str(string s)
| Bytes(bytes s)
| NameConstant(singleton value)
| Name(identifier id, expr_context ctx)
expr_context = Load | Store
keyword = (identifier arg, expr value)
</code></pre></div>
<p>Figure 0 lists the AST classes we’ll need to handle, and
their fields. The second line, for instance, means that one type of
statement is <code class="language-plaintext highlighter-rouge">ast.Assign</code>, which has a list of target expressions (the
<code class="language-plaintext highlighter-rouge">*</code> means a list) and a value expression. This represents statements
like <code class="language-plaintext highlighter-rouge">x = y = 2+3</code>, with <code class="language-plaintext highlighter-rouge">x</code> and <code class="language-plaintext highlighter-rouge">y</code> as targets.</p>
<p>CPython uses a tool to generate all of the AST classes from these
declarations—it’s another tiny compiler of a sort—though to us
they’re just documentation.</p>
<p>Here is the whole compiler as a “literate program”: a part in angle
brackets like <code class="language-plaintext highlighter-rouge"><<the assembler>></code> stands for more code we’ll see later. When we do, we’ll show
it starting with <code class="language-plaintext highlighter-rouge"># in the assembler:</code>. Later we’ll get to two
fancier versions of the same compiler, and they’ll sometimes
use chunks like <code class="language-plaintext highlighter-rouge"># in the assembler v1:</code> (replacing the earlier
version, <code class="language-plaintext highlighter-rouge">v0</code>) and <code class="language-plaintext highlighter-rouge"># in CodeGen v1+:</code> (appearing in <code class="language-plaintext highlighter-rouge">v1</code> and
also <code class="language-plaintext highlighter-rouge">v2</code>; this lets us say <code class="language-plaintext highlighter-rouge"># in CodeGen v2</code> to add to and not replace
<code class="language-plaintext highlighter-rouge">v1</code>).</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in tailbiter.py:
</span><span class="kn">import</span> <span class="nn">ast</span><span class="p">,</span> <span class="n">collections</span><span class="p">,</span> <span class="n">dis</span><span class="p">,</span> <span class="n">types</span><span class="p">,</span> <span class="n">sys</span>
<span class="kn">from</span> <span class="nn">functools</span> <span class="kn">import</span> <span class="nb">reduce</span>
<span class="kn">from</span> <span class="nn">itertools</span> <span class="kn">import</span> <span class="n">chain</span>
<span class="kn">from</span> <span class="nn">check_subset</span> <span class="kn">import</span> <span class="n">check_conformity</span>
<span class="o"><<</span><span class="n">the</span> <span class="n">assembler</span><span class="o">>></span>
<span class="o"><<</span><span class="n">the</span> <span class="n">code</span> <span class="n">generator</span><span class="o">>></span>
<span class="o"><<</span><span class="nb">compile</span> <span class="ow">and</span> <span class="n">run</span> <span class="n">a</span> <span class="nb">file</span><span class="o">>></span>
<span class="k">if</span> <span class="n">__name__</span> <span class="o">==</span> <span class="s">'__main__'</span><span class="p">:</span>
<span class="n">sys</span><span class="p">.</span><span class="n">argv</span><span class="p">.</span><span class="n">pop</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span>
<span class="n">run</span><span class="p">(</span><span class="n">sys</span><span class="p">.</span><span class="n">argv</span><span class="p">[</span><span class="mi">0</span><span class="p">],</span> <span class="s">'__main__'</span><span class="p">)</span>
</code></pre></div>
<p>Note that we’ve chosen to write a very small but working compiler as
our first step—the code generator and the assembler will implement
only fragments of the full job of a code generator or assembler, just
the fragments needed by our first Python subset. Alternatively, we
could have restricted our exploration to just one of the layers
(e.g. translating our assembly to bytecode) and completed it before
moving on.</p>
<p>The technique of writing a minimalist but fully-functioning prototype
is often called a “spike.” This is because we are writing a
program that “drives” through all the layers that we think we are
going to exist in our finished product.</p>
<p>The goal of a spike is to detect any obvious problems in our overall design as
early as possible. It is thus important that we accept we may have to throw all
of this code away—in fact, there are many development methodologies that
<em>require</em> you to throw away the code and start again, no matter how successful
the spike was in proving the design.</p>
<p>Let’s further explore our proposed spike. <code class="language-plaintext highlighter-rouge">sys.argv.pop(0)</code> removes the
initial <code class="language-plaintext highlighter-rouge">argv[0]</code> to leave the command-line arguments the same as if
we’d run Python on the source program directly: thus (with the
compiler in <code class="language-plaintext highlighter-rouge">tailbiter.py</code>) you can run <code class="language-plaintext highlighter-rouge">python greet.py</code>, or <code class="language-plaintext highlighter-rouge">python
tailbiter.py greet.py</code>, or (eventually) <code class="language-plaintext highlighter-rouge">python tailbiter.py
tailbiter.py greet.py</code>…</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in compile and run a file:
</span><span class="k">def</span> <span class="nf">run</span><span class="p">(</span><span class="n">filename</span><span class="p">,</span> <span class="n">module_name</span><span class="p">):</span>
<span class="n">f</span> <span class="o">=</span> <span class="nb">open</span><span class="p">(</span><span class="n">filename</span><span class="p">)</span>
<span class="n">source</span> <span class="o">=</span> <span class="n">f</span><span class="p">.</span><span class="n">read</span><span class="p">()</span>
<span class="n">f</span><span class="p">.</span><span class="n">close</span><span class="p">()</span>
<span class="k">return</span> <span class="n">module_from_ast</span><span class="p">(</span><span class="n">module_name</span><span class="p">,</span> <span class="n">filename</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">parse</span><span class="p">(</span><span class="n">source</span><span class="p">))</span>
<span class="k">def</span> <span class="nf">module_from_ast</span><span class="p">(</span><span class="n">module_name</span><span class="p">,</span> <span class="n">filename</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="n">code</span> <span class="o">=</span> <span class="n">code_for_module</span><span class="p">(</span><span class="n">module_name</span><span class="p">,</span> <span class="n">filename</span><span class="p">,</span> <span class="n">t</span><span class="p">)</span>
<span class="n">module</span> <span class="o">=</span> <span class="n">types</span><span class="p">.</span><span class="n">ModuleType</span><span class="p">(</span><span class="n">module_name</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">get_docstring</span><span class="p">(</span><span class="n">t</span><span class="p">))</span>
<span class="k">exec</span><span class="p">(</span><span class="n">code</span><span class="p">,</span> <span class="n">module</span><span class="p">.</span><span class="n">__dict__</span><span class="p">)</span>
<span class="k">return</span> <span class="n">module</span>
<span class="o"><<</span><span class="nb">compile</span> <span class="n">to</span> <span class="n">code</span><span class="o">>></span>
</code></pre></div>
<p>Throughout the compiler, <code class="language-plaintext highlighter-rouge">t</code> (for “tree”) names an AST object (also
called a “node”). Here <code class="language-plaintext highlighter-rouge">ast.parse</code> gives us a tree, we make a code object
from it with <code class="language-plaintext highlighter-rouge">code_for_module</code> (to be written), then we let CPython
execute the code to populate a new module object.
These are the same actions as Python performs when you <code class="language-plaintext highlighter-rouge">import</code> a module,
except for calling on our new compiler in place of <code class="language-plaintext highlighter-rouge">compile</code>. (We won’t look into
how Python’s import-hook machinery could let us make <code class="language-plaintext highlighter-rouge">import</code> call on
our loader instead of the default one.)</p>
<h3 id="from-ast-to-code">From AST to code</h3>
<p>The last underspecified step in our spike is <code class="language-plaintext highlighter-rouge"><<compile to code>></code>,
which we will implement in <code class="language-plaintext highlighter-rouge">code_for_module</code>. This function takes the
module’s AST and converts it to bytecode.
This means that we’re going to need some tools to help
us traverse the AST.</p>
<p>We could try doing this from scratch, in a style like:</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in examples.py:
</span><span class="k">def</span> <span class="nf">example</span><span class="p">(</span><span class="n">t</span><span class="p">):</span>
<span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">t</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">Module</span><span class="p">):</span>
<span class="k">return</span> <span class="s">"(A module {})"</span><span class="p">.</span><span class="nb">format</span><span class="p">(</span><span class="s">' '</span><span class="p">.</span><span class="n">join</span><span class="p">(</span><span class="nb">map</span><span class="p">(</span><span class="n">example</span><span class="p">,</span> <span class="n">t</span><span class="p">.</span><span class="n">body</span><span class="p">)))</span>
<span class="k">elif</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">t</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">Expr</span><span class="p">):</span>
<span class="k">return</span> <span class="s">"(An expression {})"</span><span class="p">.</span><span class="nb">format</span><span class="p">(</span><span class="n">example</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">value</span><span class="p">))</span>
<span class="k">elif</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">t</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">Num</span><span class="p">):</span>
<span class="k">return</span> <span class="s">"(A number {})"</span><span class="p">.</span><span class="nb">format</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">n</span><span class="p">)</span>
<span class="k">else</span><span class="p">:</span>
<span class="k">raise</span> <span class="n">Error</span><span class="p">(</span><span class="s">"I don't know how to handle this kind of node"</span><span class="p">,</span> <span class="n">t</span><span class="p">)</span>
</code></pre></div>
<p>However, the visitor classes in Python’s <code class="language-plaintext highlighter-rouge">ast</code> module make our task a
little more convenient:</p>
<div class="highlight"><pre><code class="language-python"><span class="k">class</span> <span class="nc">ExampleVisitor</span><span class="p">(</span><span class="n">ast</span><span class="p">.</span><span class="n">NodeVisitor</span><span class="p">):</span>
<span class="k">def</span> <span class="nf">visit_Module</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">return</span> <span class="s">"(A module {})"</span><span class="p">.</span><span class="nb">format</span><span class="p">(</span><span class="s">' '</span><span class="p">.</span><span class="n">join</span><span class="p">(</span><span class="nb">map</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">visit</span><span class="p">,</span> <span class="n">t</span><span class="p">.</span><span class="n">body</span><span class="p">)))</span>
<span class="k">def</span> <span class="nf">visit_Expr</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">return</span> <span class="s">"(An expression {})"</span><span class="p">.</span><span class="nb">format</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">visit</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">value</span><span class="p">))</span>
<span class="k">def</span> <span class="nf">visit_Num</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">return</span> <span class="s">"(A number {})"</span><span class="p">.</span><span class="nb">format</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">n</span><span class="p">)</span>
</code></pre></div>
<p>This is called like so:</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in transcripts:
</span><span class="o">>>></span> <span class="n">v</span> <span class="o">=</span> <span class="n">ExampleVisitor</span><span class="p">()</span>
<span class="o">>>></span> <span class="n">v</span><span class="p">.</span><span class="n">visit</span><span class="p">(</span><span class="n">ast</span><span class="p">.</span><span class="n">parse</span><span class="p">(</span><span class="s">'5'</span><span class="p">))</span>
<span class="s">'(A module (An expression (A number 5)))'</span>
<span class="o">>>></span> <span class="k">print</span><span class="p">(</span><span class="n">astpp</span><span class="p">.</span><span class="n">dump</span><span class="p">(</span><span class="n">ast</span><span class="p">.</span><span class="n">parse</span><span class="p">(</span><span class="s">'5'</span><span class="p">)))</span>
<span class="n">Module</span><span class="p">(</span><span class="n">body</span><span class="o">=</span><span class="p">[</span>
<span class="n">Expr</span><span class="p">(</span><span class="n">value</span><span class="o">=</span><span class="n">Num</span><span class="p">(</span><span class="n">n</span><span class="o">=</span><span class="mi">5</span><span class="p">)),</span>
<span class="p">])</span>
</code></pre></div>
<p>The visitor pattern separates the concern of traversing the tree
(which is the same every time) from what we actually want to do in
each traversal (which is situational). This lets us define
separately-callable methods one a time rather than inserting <code class="language-plaintext highlighter-rouge">elif</code>s
into a master function. These single-purpose methods are easy to
understand, test, and reuse later if the need arises.</p>
<h3 id="a-module-becomes-a-code-object">A module becomes a code object</h3>
<p>We’ve designed our compiler as a visitor that returns assembly code.
As it walks through the tree, it remembers the names and constants
it’s seen, so that the emitted instructions can refer to names and
constants by index. After the walk it assembles the assembly code into
a code object.</p>
<p>Let’s instantiate this code-generation visitor and set it to work in
our main compiler flow:</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in compile to code v0:
</span><span class="k">def</span> <span class="nf">code_for_module</span><span class="p">(</span><span class="n">module_name</span><span class="p">,</span> <span class="n">filename</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">return</span> <span class="n">CodeGen</span><span class="p">(</span><span class="n">filename</span><span class="p">,</span> <span class="n">StubScope</span><span class="p">()).</span><span class="n">compile_module</span><span class="p">(</span><span class="n">t</span><span class="p">,</span> <span class="n">module_name</span><span class="p">)</span>
<span class="k">class</span> <span class="nc">StubScope</span><span class="p">:</span> <span class="n">freevars</span><span class="p">,</span> <span class="n">cellvars</span><span class="p">,</span> <span class="n">derefvars</span> <span class="o">=</span> <span class="p">(),</span> <span class="p">(),</span> <span class="p">()</span>
<span class="o"><<</span><span class="n">CodeGen</span><span class="o">>></span>
</code></pre></div>
<p>(For the first time, we’re seeing stub code that will be superseded
in a fancier version of the compiler. We’ll return here later!)</p>
<p>Our <code class="language-plaintext highlighter-rouge">CodeGen</code> visitor will have:</p>
<ul>
<li>Methods to start traversing and to wrap up the completed code object.</li>
<li>Tables holding the traversal state.</li>
<li><code class="language-plaintext highlighter-rouge">visit_X</code> methods for each type of AST node, each returning an assembly-code sequence.</li>
<li>Helper methods to generate some common code sequences.</li>
</ul>
<!-- XXX this line is for markdown formatting only XXX -->
<div class="highlight"><pre><code class="language-python"><span class="c1"># in CodeGen v0+:
</span><span class="k">class</span> <span class="nc">CodeGen</span><span class="p">(</span><span class="n">ast</span><span class="p">.</span><span class="n">NodeVisitor</span><span class="p">):</span>
<span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">filename</span><span class="p">,</span> <span class="n">scope</span><span class="p">):</span>
<span class="bp">self</span><span class="p">.</span><span class="n">filename</span> <span class="o">=</span> <span class="n">filename</span>
<span class="bp">self</span><span class="p">.</span><span class="n">scope</span> <span class="o">=</span> <span class="n">scope</span>
<span class="bp">self</span><span class="p">.</span><span class="n">constants</span> <span class="o">=</span> <span class="n">make_table</span><span class="p">()</span>
<span class="bp">self</span><span class="p">.</span><span class="n">names</span> <span class="o">=</span> <span class="n">make_table</span><span class="p">()</span>
<span class="bp">self</span><span class="p">.</span><span class="n">varnames</span> <span class="o">=</span> <span class="n">make_table</span><span class="p">()</span>
</code></pre></div>
<p>Recall the disassembly of a module, above: there was the body code,
then <code class="language-plaintext highlighter-rouge">LOAD_CONST</code> of <code class="language-plaintext highlighter-rouge">None</code>, then <code class="language-plaintext highlighter-rouge">RETURN_VALUE</code>. We turn that
assembly into a code object:</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in CodeGen v0+:
</span> <span class="k">def</span> <span class="nf">compile_module</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">,</span> <span class="n">name</span><span class="p">):</span>
<span class="n">assembly</span> <span class="o">=</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">body</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">load_const</span><span class="p">(</span><span class="bp">None</span><span class="p">)</span> <span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">RETURN_VALUE</span>
<span class="k">return</span> <span class="bp">self</span><span class="p">.</span><span class="n">make_code</span><span class="p">(</span><span class="n">assembly</span><span class="p">,</span> <span class="n">name</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">make_code</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">assembly</span><span class="p">,</span> <span class="n">name</span><span class="p">,</span> <span class="n">argcount</span><span class="p">):</span>
<span class="n">kwonlyargcount</span> <span class="o">=</span> <span class="mi">0</span>
<span class="n">nlocals</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">varnames</span><span class="p">)</span>
<span class="n">stacksize</span> <span class="o">=</span> <span class="n">plumb_depths</span><span class="p">(</span><span class="n">assembly</span><span class="p">)</span>
<span class="n">flags</span> <span class="o">=</span> <span class="p">(</span> <span class="p">(</span><span class="mh">0x02</span> <span class="k">if</span> <span class="n">nlocals</span> <span class="k">else</span> <span class="mi">0</span><span class="p">)</span>
<span class="o">|</span> <span class="p">(</span><span class="mh">0x10</span> <span class="k">if</span> <span class="bp">self</span><span class="p">.</span><span class="n">scope</span><span class="p">.</span><span class="n">freevars</span> <span class="k">else</span> <span class="mi">0</span><span class="p">)</span>
<span class="o">|</span> <span class="p">(</span><span class="mh">0x40</span> <span class="k">if</span> <span class="ow">not</span> <span class="bp">self</span><span class="p">.</span><span class="n">scope</span><span class="p">.</span><span class="n">derefvars</span> <span class="k">else</span> <span class="mi">0</span><span class="p">))</span>
<span class="n">firstlineno</span><span class="p">,</span> <span class="n">lnotab</span> <span class="o">=</span> <span class="n">make_lnotab</span><span class="p">(</span><span class="n">assembly</span><span class="p">)</span>
<span class="k">return</span> <span class="n">types</span><span class="p">.</span><span class="n">CodeType</span><span class="p">(</span><span class="n">argcount</span><span class="p">,</span> <span class="n">kwonlyargcount</span><span class="p">,</span>
<span class="n">nlocals</span><span class="p">,</span> <span class="n">stacksize</span><span class="p">,</span> <span class="n">flags</span><span class="p">,</span> <span class="n">assemble</span><span class="p">(</span><span class="n">assembly</span><span class="p">),</span>
<span class="bp">self</span><span class="p">.</span><span class="n">collect_constants</span><span class="p">(),</span>
<span class="n">collect</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">names</span><span class="p">),</span> <span class="n">collect</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">varnames</span><span class="p">),</span>
<span class="bp">self</span><span class="p">.</span><span class="n">filename</span><span class="p">,</span> <span class="n">name</span><span class="p">,</span> <span class="n">firstlineno</span><span class="p">,</span> <span class="n">lnotab</span><span class="p">,</span>
<span class="bp">self</span><span class="p">.</span><span class="n">scope</span><span class="p">.</span><span class="n">freevars</span><span class="p">,</span> <span class="bp">self</span><span class="p">.</span><span class="n">scope</span><span class="p">.</span><span class="n">cellvars</span><span class="p">)</span>
</code></pre></div>
<p>Note that we begin the traversal process by calling
<code class="language-plaintext highlighter-rouge">self(t.body)</code>—this is because <code class="language-plaintext highlighter-rouge">CodeGen</code> is a <a href="https://docs.python.org/3/reference/datamodel.html#emulating-callable-objects">callable
object</a>. This means when you invoke an instance <code class="language-plaintext highlighter-rouge">c</code> of CodeGen as if
it is a function, Python will translate that into <code class="language-plaintext highlighter-rouge">c.__call__(your args)</code>.
So what does <code class="language-plaintext highlighter-rouge">__call__</code> do on <code class="language-plaintext highlighter-rouge">CodeGen</code>?</p>
<div class="highlight"><pre><code class="language-python"> <span class="k">def</span> <span class="nf">__call__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">t</span><span class="p">,</span> <span class="nb">list</span><span class="p">):</span> <span class="k">return</span> <span class="n">concat</span><span class="p">(</span><span class="nb">map</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">))</span>
<span class="n">assembly</span> <span class="o">=</span> <span class="bp">self</span><span class="p">.</span><span class="n">visit</span><span class="p">(</span><span class="n">t</span><span class="p">)</span>
<span class="k">return</span> <span class="n">SetLineNo</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">lineno</span><span class="p">)</span> <span class="o">+</span> <span class="n">assembly</span> <span class="k">if</span> <span class="nb">hasattr</span><span class="p">(</span><span class="n">t</span><span class="p">,</span> <span class="s">'lineno'</span><span class="p">)</span> <span class="k">else</span> <span class="n">assembly</span>
</code></pre></div>
<p>It takes an AST node or a list of such nodes; when it’s a list we get
back all the results concatenated. We could define separate methods
for visiting a list vs. a node, but conflating them turns out to unify
some code to come.</p>
<p>Once we visit a node, producing its assembly code, we can annotate the
assembly with the node’s source-line number. This spares us from
writing the same in every <code class="language-plaintext highlighter-rouge">visit_Whatever</code> method.</p>
<p>We haven’t implemented <code class="language-plaintext highlighter-rouge">visit</code> yet, but we’re calling it here. This is
the default, <code class="language-plaintext highlighter-rouge">NodeVisitor</code> superclass implementation of the
<code class="language-plaintext highlighter-rouge">visit</code> method: it calls the right <code class="language-plaintext highlighter-rouge">visit_Whatever</code> method for the
type of the node visited.</p>
<p>If this <code class="language-plaintext highlighter-rouge">visit_Whatever</code> is missing, <code class="language-plaintext highlighter-rouge">NodeVisitor.visit</code> will then call the
template method <code class="language-plaintext highlighter-rouge">generic_visit</code>. This should never happen; however,
we’re certainly going to make some mistakes during development. The
default implementation of <code class="language-plaintext highlighter-rouge">generic_visit</code> does nothing, which makes it
hard for us to notice when we’ve tried to handle a node type we’re not
ready for yet. So, let’s make some noise if this ever happens:</p>
<div class="highlight"><pre><code class="language-python"> <span class="k">def</span> <span class="nf">generic_visit</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">raise</span> <span class="nb">NotImplementedError</span><span class="p">()</span>
</code></pre></div>
<h3 id="the-state-of-a-traversal">The state of a traversal</h3>
<p><code class="language-plaintext highlighter-rouge">make_code</code> wants to make a code object that’s littered with fields:</p>
<ul>
<li>
<p>The bytecode bytes themselves, from <code class="language-plaintext highlighter-rouge">assemble(assembly)</code>.</p>
</li>
<li>
<p>Redundant info too costly to compute at runtime, like <code class="language-plaintext highlighter-rouge">stacksize</code>.</p>
</li>
<li>
<p>Metadata like <code class="language-plaintext highlighter-rouge">lnotab</code>. <code class="language-plaintext highlighter-rouge">lnotab</code> tells what line number in the source file produced what part of the bytecode. (The name’s not my fault!)</p>
</li>
<li>
<p>The above-mentioned tables for constants and names.</p>
</li>
</ul>
<p>These tables are built from defaultdicts that grow as we walk the
tree, to appear as tuples when collected into the code object:</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in the code generator:
</span><span class="k">def</span> <span class="nf">make_table</span><span class="p">():</span>
<span class="n">table</span> <span class="o">=</span> <span class="n">collections</span><span class="p">.</span><span class="n">defaultdict</span><span class="p">(</span><span class="k">lambda</span><span class="p">:</span> <span class="nb">len</span><span class="p">(</span><span class="n">table</span><span class="p">))</span>
<span class="k">return</span> <span class="n">table</span>
<span class="k">def</span> <span class="nf">collect</span><span class="p">(</span><span class="n">table</span><span class="p">):</span>
<span class="k">return</span> <span class="nb">tuple</span><span class="p">(</span><span class="nb">sorted</span><span class="p">(</span><span class="n">table</span><span class="p">,</span> <span class="n">key</span><span class="o">=</span><span class="n">table</span><span class="p">.</span><span class="n">get</span><span class="p">))</span>
</code></pre></div>
<p>For <code class="language-plaintext highlighter-rouge">names</code> and <code class="language-plaintext highlighter-rouge">varnames</code>, the keys are the name strings; but it gets
trickier for <code class="language-plaintext highlighter-rouge">constants</code>. Equal names get the same slot in a names
table, but “equal” constants might not: for example, <code class="language-plaintext highlighter-rouge">5 == 5.0</code> is
true, but <code class="language-plaintext highlighter-rouge">5</code> and <code class="language-plaintext highlighter-rouge">5.0</code> are nonetheless distinct. Therefore we key on
the type as well as the value of the constant:</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in CodeGen v0+:
</span> <span class="k">def</span> <span class="nf">load_const</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">constant</span><span class="p">):</span>
<span class="k">return</span> <span class="n">op</span><span class="p">.</span><span class="n">LOAD_CONST</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">constants</span><span class="p">[</span><span class="n">constant</span><span class="p">,</span> <span class="nb">type</span><span class="p">(</span><span class="n">constant</span><span class="p">)])</span>
<span class="k">def</span> <span class="nf">collect_constants</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="k">return</span> <span class="nb">tuple</span><span class="p">([</span><span class="n">constant</span> <span class="k">for</span> <span class="n">constant</span><span class="p">,</span><span class="n">_</span> <span class="ow">in</span> <span class="n">collect</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">constants</span><span class="p">)])</span>
</code></pre></div>
<p>There’s a further subtlety in comparing with signed floating-point
zeroes, which we’ll punt on by expelling negative zeroes in constants
from the subset of the language we’re going to handle. A
<code class="language-plaintext highlighter-rouge">check_conformity</code> module, not presented in this article, can be
called to make sure the input program is in our subset.</p>
<h3 id="expressions-employ-the-stack">Expressions employ the stack</h3>
<p>Our first tiny mini-Python understands only assignment and expression
statements, where the expressions may be names, simple constants,
and function calls. A constant expression turns into a
<code class="language-plaintext highlighter-rouge">LOAD_CONST</code> instruction:</p>
<div class="highlight"><pre><code class="language-python"> <span class="k">def</span> <span class="nf">visit_NameConstant</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="p">.</span><span class="n">load_const</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">value</span><span class="p">)</span> <span class="c1"># for None/True/False
</span> <span class="k">def</span> <span class="nf">visit_Num</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="p">.</span><span class="n">load_const</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">n</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">visit_Str</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="p">.</span><span class="n">load_const</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">s</span><span class="p">)</span>
<span class="n">visit_Bytes</span> <span class="o">=</span> <span class="n">visit_Str</span>
</code></pre></div>
<p>A variable name also becomes a single instruction, but the choice depends on
context: a name can appear as the target of an assignment, not just in
an expression. Python ASTs use the same node-type for both roles, with
a <code class="language-plaintext highlighter-rouge">ctx</code> field to distinguish them:</p>
<div class="highlight"><pre><code class="language-python"> <span class="k">def</span> <span class="nf">visit_Name</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">ctx</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">Load</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="p">.</span><span class="n">load</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="nb">id</span><span class="p">)</span>
<span class="k">elif</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">ctx</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">Store</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="p">.</span><span class="n">store</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="nb">id</span><span class="p">)</span>
<span class="k">else</span><span class="p">:</span> <span class="k">assert</span> <span class="bp">False</span>
<span class="o"><<</span><span class="n">generate</span> <span class="n">variable</span> <span class="n">accesses</span><span class="o">>></span>
</code></pre></div>
<p>Later, when we compile functions and classes, they’ll need fancier
logic for loads and stores because names will live in different scopes;
but for now all names are global:</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in generate variable accesses v0:
</span> <span class="k">def</span> <span class="nf">load</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">name</span><span class="p">):</span> <span class="k">return</span> <span class="n">op</span><span class="p">.</span><span class="n">LOAD_NAME</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">names</span><span class="p">[</span><span class="n">name</span><span class="p">])</span>
<span class="k">def</span> <span class="nf">store</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">name</span><span class="p">):</span> <span class="k">return</span> <span class="n">op</span><span class="p">.</span><span class="n">STORE_NAME</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">names</span><span class="p">[</span><span class="n">name</span><span class="p">])</span>
</code></pre></div>
<p>Now, function calls: a call like <code class="language-plaintext highlighter-rouge">f(x, y, key=42)</code> compiles to</p>
<div class="highlight"><pre><code># in examples:
0 LOAD_NAME 0 (f)
3 LOAD_NAME 1 (x)
6 LOAD_NAME 2 (y)
9 LOAD_CONST 0 ('key')
12 LOAD_CONST 1 (42)
15 CALL_FUNCTION 258 (2 positional, 1 keyword pair)
</code></pre></div>
<p>Evidently the load instructions stash their values somewhere for
<code class="language-plaintext highlighter-rouge">CALL_FUNCTION</code> to use. That somewhere is the “stack:” a growing and
shrinking list of values. Each load appends to it, and each call
removes a function and its arguments from the end and replaces them
with one value: the result of the call.<sup id="fnref:3"><a class="footnote" href="https://codewords.recurse.com/feed.xml#fn:3">3</a></sup> This scheme gives for a
more complex expression like <code class="language-plaintext highlighter-rouge">f(g(7), h())</code> a place for the
partial results to live:</p>
<div class="highlight"><pre><code># in examples:
(the stack afterwards)
0 LOAD_NAME 0 (f) [f]
3 LOAD_NAME 1 (g) [f, g]
6 LOAD_CONST 0 (7) [f, g, 7]
9 CALL_FUNCTION 1 [f, g(7)]
12 LOAD_NAME 2 (h) [f, g(7), h]
15 CALL_FUNCTION 0 [f, g(7), h()]
18 CALL_FUNCTION 2 [f(g(7), h())]
</code></pre></div>
<p>The assembly code for the full, compound call is a concatenation of
the assembly for its parts: if you compiled just <code class="language-plaintext highlighter-rouge">g(7)</code> or <code class="language-plaintext highlighter-rouge">h()</code>,
you’d get some of the same code above (except perhaps for the choice of indices
assigned to the names <code class="language-plaintext highlighter-rouge">g</code> and <code class="language-plaintext highlighter-rouge">h</code>).</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in CodeGen v0+:
</span> <span class="k">def</span> <span class="nf">visit_Call</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">assert</span> <span class="nb">len</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">args</span><span class="p">)</span> <span class="o"><</span> <span class="mi">256</span> <span class="ow">and</span> <span class="nb">len</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">keywords</span><span class="p">)</span> <span class="o"><</span> <span class="mi">256</span>
<span class="k">return</span> <span class="p">(</span><span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">func</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">args</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">keywords</span><span class="p">)</span>
<span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">CALL_FUNCTION</span><span class="p">((</span><span class="nb">len</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">keywords</span><span class="p">)</span> <span class="o"><<</span> <span class="mi">8</span><span class="p">)</span> <span class="o">|</span> <span class="nb">len</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">args</span><span class="p">)))</span>
<span class="k">def</span> <span class="nf">visit_keyword</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">return</span> <span class="bp">self</span><span class="p">.</span><span class="n">load_const</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">arg</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">value</span><span class="p">)</span>
</code></pre></div>
<p>We recursively generate code for the function, the arguments, and the
keyword arguments (which in turn are built from the keyword name
<code class="language-plaintext highlighter-rouge">t.arg</code> and the value expression), then chain them together with
<code class="language-plaintext highlighter-rouge">CALL_FUNCTION</code> at the end.<sup id="fnref:4"><a class="footnote" href="https://codewords.recurse.com/feed.xml#fn:4">4</a></sup> The stack made this code generation
simple: if instead we’d been assigning values to numbered registers,
for instance, then we’d have had to keep track of these assignments
and generate code depending on them.</p>
<h3 id="statements-evaluate-expressions">Statements evaluate expressions</h3>
<p>Executing a statement should leave the stack unchanged. For an
expression statement (consisting of just an expression, typically a
call), we evaluate the expression and then remove its value from the
stack:</p>
<div class="highlight"><pre><code class="language-python"> <span class="k">def</span> <span class="nf">visit_Expr</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">return</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">value</span><span class="p">)</span> <span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">POP_TOP</span>
</code></pre></div>
<p>An assignment evaluates the expression as well, then stores it in the
target; all the store instructions also pop the stack.</p>
<div class="highlight"><pre><code class="language-python"> <span class="k">def</span> <span class="nf">visit_Assign</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">def</span> <span class="nf">compose</span><span class="p">(</span><span class="n">left</span><span class="p">,</span> <span class="n">right</span><span class="p">):</span> <span class="k">return</span> <span class="n">op</span><span class="p">.</span><span class="n">DUP_TOP</span> <span class="o">+</span> <span class="n">left</span> <span class="o">+</span> <span class="n">right</span>
<span class="k">return</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">value</span><span class="p">)</span> <span class="o">+</span> <span class="nb">reduce</span><span class="p">(</span><span class="n">compose</span><span class="p">,</span> <span class="nb">map</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">.</span><span class="n">targets</span><span class="p">))</span>
</code></pre></div>
<p>The complication here deals with multiple assignments like <code class="language-plaintext highlighter-rouge">x = y =
42</code>: there’s a <em>list</em> of targets (<code class="language-plaintext highlighter-rouge">x</code> and <code class="language-plaintext highlighter-rouge">y</code>). If we followed the
expression’s code with two store instructions, the second would be
stuck without the value to store, because the first popped it off; so
before the first one, we insert a <code class="language-plaintext highlighter-rouge">DUP_TOP</code> instruction, which will
push a duplicate reference to the value.</p>
<p>(We already covered generating the store instructions: the targets are
the <code class="language-plaintext highlighter-rouge">Name</code> nodes we saw in <code class="language-plaintext highlighter-rouge">visit_Name</code>.)</p>
<h3 id="we-fabricate-an-assembler">We fabricate an assembler</h3>
<p>We still need to create assembly code—instructions, <code class="language-plaintext highlighter-rouge">SetLineNo</code>
pseudo-instructions, and concatenations—and to compute three
functions of it: the maximum stack depth, the line-number table, and
the encoded bytecode. The most direct and minimal stub represents an
assembly instruction as its final bytecode sequence, makes the
line-number table empty, and pretends the stack depth is, say,
10—don’t try it with too-complex nested calls.</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in assembly types and functions v0:
</span><span class="k">def</span> <span class="nf">Instruction</span><span class="p">(</span><span class="n">opcode</span><span class="p">,</span> <span class="n">arg</span><span class="p">):</span>
<span class="k">return</span> <span class="nb">bytes</span><span class="p">([</span><span class="n">opcode</span><span class="p">]</span> <span class="k">if</span> <span class="n">arg</span> <span class="ow">is</span> <span class="bp">None</span> <span class="k">else</span> <span class="p">[</span><span class="n">opcode</span><span class="p">,</span> <span class="n">arg</span> <span class="o">%</span> <span class="mi">256</span><span class="p">,</span> <span class="n">arg</span> <span class="o">//</span> <span class="mi">256</span><span class="p">])</span>
<span class="k">def</span> <span class="nf">concat</span><span class="p">(</span><span class="n">assemblies</span><span class="p">):</span> <span class="k">return</span> <span class="sa">b</span><span class="s">''</span><span class="p">.</span><span class="n">join</span><span class="p">(</span><span class="n">assemblies</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">SetLineNo</span><span class="p">(</span><span class="n">lineno</span><span class="p">):</span> <span class="k">return</span> <span class="sa">b</span><span class="s">''</span>
<span class="k">def</span> <span class="nf">make_lnotab</span><span class="p">(</span><span class="n">assembly</span><span class="p">):</span> <span class="k">return</span> <span class="mi">1</span><span class="p">,</span> <span class="sa">b</span><span class="s">''</span>
<span class="k">def</span> <span class="nf">plumb_depths</span><span class="p">(</span><span class="n">assembly</span><span class="p">):</span> <span class="k">return</span> <span class="mi">10</span>
<span class="k">def</span> <span class="nf">assemble</span><span class="p">(</span><span class="n">assembly</span><span class="p">):</span> <span class="k">return</span> <span class="n">assembly</span>
</code></pre></div>
<p>We fill in <code class="language-plaintext highlighter-rouge">op</code> so that <code class="language-plaintext highlighter-rouge">op.DUP_TOP</code> and all the rest work.</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in the assembler:
</span><span class="o"><<</span><span class="n">assembly</span> <span class="n">types</span> <span class="ow">and</span> <span class="n">functions</span><span class="o">>></span>
<span class="k">def</span> <span class="nf">denotation</span><span class="p">(</span><span class="n">opcode</span><span class="p">):</span>
<span class="k">if</span> <span class="n">opcode</span> <span class="o"><</span> <span class="n">dis</span><span class="p">.</span><span class="n">HAVE_ARGUMENT</span><span class="p">:</span>
<span class="k">return</span> <span class="n">Instruction</span><span class="p">(</span><span class="n">opcode</span><span class="p">,</span> <span class="bp">None</span><span class="p">)</span>
<span class="k">else</span><span class="p">:</span>
<span class="k">return</span> <span class="k">lambda</span> <span class="n">arg</span><span class="p">:</span> <span class="n">Instruction</span><span class="p">(</span><span class="n">opcode</span><span class="p">,</span> <span class="n">arg</span><span class="p">)</span>
<span class="n">op</span> <span class="o">=</span> <span class="nb">type</span><span class="p">(</span><span class="s">'op'</span><span class="p">,</span> <span class="p">(),</span> <span class="nb">dict</span><span class="p">([(</span><span class="n">name</span><span class="p">,</span> <span class="n">denotation</span><span class="p">(</span><span class="n">opcode</span><span class="p">))</span>
<span class="k">for</span> <span class="n">name</span><span class="p">,</span> <span class="n">opcode</span> <span class="ow">in</span> <span class="n">dis</span><span class="p">.</span><span class="n">opmap</span><span class="p">.</span><span class="n">items</span><span class="p">()]))</span>
</code></pre></div>
<p>And at last <code class="language-plaintext highlighter-rouge">greet.py</code> works. Hurrah!</p>
<div class="highlight"><pre><code># in transcripts:
$ python3 tailbiter0.py greet.py
Hi, Chrysophylax
</code></pre></div>
<h2 id="a-compiler-half-grown-assembling-control-flow">A compiler half-grown: assembling control flow</h2>
<p>Now that we have driven our spike through all of the layers of our
compiler architecture, we can think about how to build out more
complicated use cases. We don’t yet have any control flow in our
Python subset, which is a pretty critical omission. We can’t
<code class="language-plaintext highlighter-rouge">import</code> either, meaning our programs can’t even get at Python’s
standard library in the usual way. Let’s tackle these issues, and
handle more of the basic expression and statement types, in version 1.</p>
<div class="highlight"><pre><code># in figure 1: AST types added in Tailbiter version 1.
stmt = For(expr target, expr iter, stmt* body)
| While(expr test, stmt* body)
| If(expr test, stmt* body, stmt* orelse)
| Raise(expr exc)
| Import(alias* names)
| ImportFrom(identifier? module, alias* names, int? level)
| Pass
alias = (identifier name, identifier? asname)
expr = BoolOp(boolop op, expr* values)
| BinOp(expr left, operator op, expr right)
| UnaryOp(unaryop op, expr operand)
| IfExp(expr test, expr body, expr orelse)
| Dict(expr* keys, expr* values)
| Compare(expr left, cmpop* ops, expr* comparators)
| Attribute(expr value, identifier attr, expr_context ctx)
| Subscript(expr value, slice slice, expr_context ctx)
| List(expr* elts, expr_context ctx)
| Tuple(expr* elts, expr_context ctx)
slice = Index(expr value)
boolop = And | Or
operator = Add | Sub | Mult | Div | Mod | Pow | LShift
| RShift | BitOr | BitXor | BitAnd | FloorDiv
unaryop = Invert | Not | UAdd | USub
cmpop = Eq | NotEq | Lt | LtE | Gt | GtE | Is | IsNot | In | NotIn
</code></pre></div>
<p>At this point, it’s worth asking ourselves if we’re going to face any
problems in v1 that are materially different from what we faced in v0.
What if we made a design decision in v0 that makes it impossible to
proceed?</p>
<p>Indeed, control-flow constructs like <code class="language-plaintext highlighter-rouge">if</code>-<code class="language-plaintext highlighter-rouge">else</code> do present us with a
challenge we haven’t faced yet: they require us to “jump around” in
the bytecode.</p>
<p>For example, the statement</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in examples:
</span><span class="k">if</span> <span class="n">ok</span><span class="p">:</span>
<span class="n">yes</span>
<span class="k">else</span><span class="p">:</span>
<span class="n">no</span>
</code></pre></div>
<p>becomes</p>
<div class="highlight"><pre><code> 1 0 LOAD_NAME 0 (ok)
3 POP_JUMP_IF_FALSE 13
2 6 LOAD_NAME 1 (yes)
9 POP_TOP
10 JUMP_FORWARD 4 (to 17)
4 >> 13 LOAD_NAME 2 (no)
16 POP_TOP
>> 17 ...
</code></pre></div>
<p>where <code class="language-plaintext highlighter-rouge">POP_JUMP_IF_FALSE</code> does what it says: pops the value left by
<code class="language-plaintext highlighter-rouge">ok</code>, tests it, and if it’s false jumps to index 13—that is,
executes that instruction next. Otherwise execution continues to
the usual next instruction, at 6. <code class="language-plaintext highlighter-rouge">JUMP_FORWARD</code> likewise jumps to
index 17, to skip <code class="language-plaintext highlighter-rouge">no</code> if we chose <code class="language-plaintext highlighter-rouge">yes</code>.</p>
<p>Why’s this a problem that our current design can’t handle?
During code generation the compiler may not yet know the bytecode
index where the jump target will be.</p>
<p>Our answer: we augment the assembly language with symbolic labels for
the targets, to be resolved later by the <code class="language-plaintext highlighter-rouge">assemble</code> function.</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in CodeGen v1+:
</span> <span class="k">def</span> <span class="nf">visit_If</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="n">orelse</span><span class="p">,</span> <span class="n">after</span> <span class="o">=</span> <span class="n">Label</span><span class="p">(),</span> <span class="n">Label</span><span class="p">()</span>
<span class="k">return</span> <span class="p">(</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">test</span><span class="p">)</span> <span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">POP_JUMP_IF_FALSE</span><span class="p">(</span><span class="n">orelse</span><span class="p">)</span>
<span class="o">+</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">body</span><span class="p">)</span> <span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">JUMP_FORWARD</span><span class="p">(</span><span class="n">after</span><span class="p">)</span>
<span class="o">+</span> <span class="n">orelse</span> <span class="o">+</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">orelse</span><span class="p">)</span>
<span class="o">+</span> <span class="n">after</span><span class="p">)</span>
</code></pre></div>
<p>A label like <code class="language-plaintext highlighter-rouge">after</code> can appear in two kinds of places: as an
instruction’s argument (like <code class="language-plaintext highlighter-rouge">op.JUMP_FORWARD(after)</code>) or on its own
(like <code class="language-plaintext highlighter-rouge">+ after</code>). <code class="language-plaintext highlighter-rouge">assemble</code> will have to note the position where it
appeared in the code on its own, and encode the bytecode address of
that position for the <code class="language-plaintext highlighter-rouge">JUMP_FORWARD</code> instruction.</p>
<p>This design is not inevitable. Notice that the example’s
<code class="language-plaintext highlighter-rouge">JUMP_FORWARD</code> argument was encoded as 4, when the target is at index
17: 4 means the distance, taken from the instruction right after the
jump (at index 13), to the target. Encoded this way, it’s a “relative”
jump.</p>
<p>Suppose all the jumps were relative. We could easily compute the
offsets, just knowing the encoded size of each block of code: e.g. the
offset from the <code class="language-plaintext highlighter-rouge">JUMP_FORWARD</code> to <code class="language-plaintext highlighter-rouge">after</code> is the size of
<code class="language-plaintext highlighter-rouge">self(t.orelse)</code>. There’d be a similar computation for the jump to
<code class="language-plaintext highlighter-rouge">orelse</code>. We could skip the symbolic assembly phase and keep
generating bytecode strings directly, like Tailbiter v0.</p>
<p>Sadly for this dream, <code class="language-plaintext highlighter-rouge">POP_JUMP_IF_FALSE</code> here encodes its target differently, as
the absolute address 13. We could consider designing this part more like
a “linker” than an assembler, but it is safer to keep to CPython’s
design: it makes surprises less likely.</p>
<h3 id="we-analyze-assembly-code">We analyze assembly code</h3>
<p>Let’s make labels work, and unstub the rest of the assembler:
computing stack depths and line-number tables.</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in assembly types and functions v1:
</span><span class="k">def</span> <span class="nf">assemble</span><span class="p">(</span><span class="n">assembly</span><span class="p">):</span>
<span class="k">return</span> <span class="nb">bytes</span><span class="p">(</span><span class="nb">iter</span><span class="p">(</span><span class="n">assembly</span><span class="p">.</span><span class="n">encode</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="nb">dict</span><span class="p">(</span><span class="n">assembly</span><span class="p">.</span><span class="n">resolve</span><span class="p">(</span><span class="mi">0</span><span class="p">)))))</span>
</code></pre></div>
<p>Assembly code is now some kind of object we’ll define—several kinds,
for instructions, labels, <code class="language-plaintext highlighter-rouge">SetLineNo</code>, and a couple more. To turn it
into bytecode, we first <em>resolve</em> the addresses of its labels
(starting at address 0), then <em>encode</em> it into bytes using the
addresses now known—a “two-pass assembler.”</p>
<div class="highlight"><pre><code class="language-python"><span class="k">def</span> <span class="nf">plumb_depths</span><span class="p">(</span><span class="n">assembly</span><span class="p">):</span>
<span class="n">depths</span> <span class="o">=</span> <span class="p">[</span><span class="mi">0</span><span class="p">]</span>
<span class="n">assembly</span><span class="p">.</span><span class="n">plumb</span><span class="p">(</span><span class="n">depths</span><span class="p">)</span>
<span class="k">return</span> <span class="nb">max</span><span class="p">(</span><span class="n">depths</span><span class="p">)</span>
</code></pre></div>
<p>For the maximum stack depth, we ask <code class="language-plaintext highlighter-rouge">plumb</code> to compute the depth after
every instruction, appending them all to <code class="language-plaintext highlighter-rouge">depths</code>. (This uses more
space than needed, to make <code class="language-plaintext highlighter-rouge">Assembly.plumb</code>’s job simple.)</p>
<p>Computing the line-number table calls on a <code class="language-plaintext highlighter-rouge">line_nos</code> method which
yields pairs of (bytecode address, source-code line-number), the smaller
addresses first. <code class="language-plaintext highlighter-rouge">make_lnotab</code> consumes them and encodes them into a
bytestring in a format imposed by the VM interpreter, designed to try
to keep the table small: usually just a couple of bytes per line.
Each successive pair of bytes in the table encodes an (address,
line_number) pair as the differences from the previous pair. With a
byte’s limited range, 0 to 255, this design faces two problems:</p>
<ul>
<li>
<p>A difference could be negative. Given <code class="language-plaintext highlighter-rouge">x = </code><em>(two_line_expression)</em>,
for instance, the bytecode for the store to <code class="language-plaintext highlighter-rouge">x</code> goes after the
bytecode for the expression. As there’s no way to express this
reversal in this format, we have to decide how to distort it. Like
CPython, we’ll pretend the store to <code class="language-plaintext highlighter-rouge">x</code> is on the last line of source.</p>
</li>
<li>
<p>The difference could exceed 255. Then the entry must take up
multiple successive byte-pairs, first increasing only the address
part in each, and then increasing the line number. (If we increased
both at once, there’d be ambiguity about whether an intermediate
line number covered part of the range, as <a href="https://github.com/python/cpython/blob/3.4/Objects/lnotab_notes.txt">explained in CPython’s
implementation notes</a>.)</p>
</li>
</ul>
<!-- XXX this line is for markdown formatting only XXX -->
<div class="highlight"><pre><code class="language-python"><span class="k">def</span> <span class="nf">make_lnotab</span><span class="p">(</span><span class="n">assembly</span><span class="p">):</span>
<span class="n">firstlineno</span><span class="p">,</span> <span class="n">lnotab</span> <span class="o">=</span> <span class="bp">None</span><span class="p">,</span> <span class="p">[]</span>
<span class="n">byte</span><span class="p">,</span> <span class="n">line</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="bp">None</span>
<span class="k">for</span> <span class="n">next_byte</span><span class="p">,</span> <span class="n">next_line</span> <span class="ow">in</span> <span class="n">assembly</span><span class="p">.</span><span class="n">line_nos</span><span class="p">(</span><span class="mi">0</span><span class="p">):</span>
<span class="k">if</span> <span class="n">firstlineno</span> <span class="ow">is</span> <span class="bp">None</span><span class="p">:</span>
<span class="n">firstlineno</span> <span class="o">=</span> <span class="n">line</span> <span class="o">=</span> <span class="n">next_line</span>
<span class="k">elif</span> <span class="n">line</span> <span class="o"><</span> <span class="n">next_line</span><span class="p">:</span>
<span class="k">while</span> <span class="n">byte</span><span class="o">+</span><span class="mi">255</span> <span class="o"><</span> <span class="n">next_byte</span><span class="p">:</span>
<span class="n">lnotab</span><span class="p">.</span><span class="n">extend</span><span class="p">([</span><span class="mi">255</span><span class="p">,</span> <span class="mi">0</span><span class="p">])</span>
<span class="n">byte</span> <span class="o">=</span> <span class="n">byte</span><span class="o">+</span><span class="mi">255</span>
<span class="k">while</span> <span class="n">line</span><span class="o">+</span><span class="mi">255</span> <span class="o"><</span> <span class="n">next_line</span><span class="p">:</span>
<span class="n">lnotab</span><span class="p">.</span><span class="n">extend</span><span class="p">([</span><span class="n">next_byte</span><span class="o">-</span><span class="n">byte</span><span class="p">,</span> <span class="mi">255</span><span class="p">])</span>
<span class="n">byte</span><span class="p">,</span> <span class="n">line</span> <span class="o">=</span> <span class="n">next_byte</span><span class="p">,</span> <span class="n">line</span><span class="o">+</span><span class="mi">255</span>
<span class="k">if</span> <span class="p">(</span><span class="n">byte</span><span class="p">,</span> <span class="n">line</span><span class="p">)</span> <span class="o">!=</span> <span class="p">(</span><span class="n">next_byte</span><span class="p">,</span> <span class="n">next_line</span><span class="p">):</span>
<span class="n">lnotab</span><span class="p">.</span><span class="n">extend</span><span class="p">([</span><span class="n">next_byte</span><span class="o">-</span><span class="n">byte</span><span class="p">,</span> <span class="n">next_line</span><span class="o">-</span><span class="n">line</span><span class="p">])</span>
<span class="n">byte</span><span class="p">,</span> <span class="n">line</span> <span class="o">=</span> <span class="n">next_byte</span><span class="p">,</span> <span class="n">next_line</span>
<span class="k">return</span> <span class="n">firstlineno</span> <span class="ow">or</span> <span class="mi">1</span><span class="p">,</span> <span class="nb">bytes</span><span class="p">(</span><span class="n">lnotab</span><span class="p">)</span>
</code></pre></div>
<p>And <code class="language-plaintext highlighter-rouge">concat</code> can’t be just <code class="language-plaintext highlighter-rouge">b''.join</code> anymore:</p>
<div class="highlight"><pre><code class="language-python"><span class="k">def</span> <span class="nf">concat</span><span class="p">(</span><span class="n">assemblies</span><span class="p">):</span>
<span class="k">return</span> <span class="nb">sum</span><span class="p">(</span><span class="n">assemblies</span><span class="p">,</span> <span class="n">no_op</span><span class="p">)</span>
</code></pre></div>
<p>Assembly objects will need an <code class="language-plaintext highlighter-rouge">__add__</code> method for all the code we’ve
been seeing like <code class="language-plaintext highlighter-rouge">assembly + op.POP_TOP</code>. Python’s <code class="language-plaintext highlighter-rouge">sum()</code> calls the
same method.</p>
<h3 id="assembly-comes-in-types">Assembly comes in types</h3>
<p>The simplest assembly fragment is the no-op:</p>
<div class="highlight"><pre><code class="language-python"><span class="k">class</span> <span class="nc">Assembly</span><span class="p">:</span>
<span class="k">def</span> <span class="nf">__add__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
<span class="k">return</span> <span class="n">Chain</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">)</span>
<span class="n">length</span> <span class="o">=</span> <span class="mi">0</span>
<span class="k">def</span> <span class="nf">resolve</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">start</span><span class="p">):</span>
<span class="k">return</span> <span class="p">()</span>
<span class="k">def</span> <span class="nf">encode</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">start</span><span class="p">,</span> <span class="n">addresses</span><span class="p">):</span>
<span class="k">return</span> <span class="sa">b</span><span class="s">''</span>
<span class="k">def</span> <span class="nf">line_nos</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">start</span><span class="p">):</span>
<span class="k">return</span> <span class="p">()</span>
<span class="k">def</span> <span class="nf">plumb</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">depths</span><span class="p">):</span>
<span class="k">pass</span>
<span class="n">no_op</span> <span class="o">=</span> <span class="n">Assembly</span><span class="p">()</span>
</code></pre></div>
<p>For <code class="language-plaintext highlighter-rouge">resolve</code>’s use, all our assembly objects hold a <code class="language-plaintext highlighter-rouge">length</code> counting
how many bytes of bytecode they’ll become. We’ll take it to be
constant, since we don’t support the extended-length argument
format. (Suppose there were a relative jump to an address over 65535
bytes away. The jump instruction would need to occupy more than the
usual 3 bytes; if we’d assumed 3 bytes, this could imply cascading
changes to other offsets.)</p>
<p>A <code class="language-plaintext highlighter-rouge">Label</code> is just like <code class="language-plaintext highlighter-rouge">no_op</code>, except resolving to an address.</p>
<div class="highlight"><pre><code class="language-python"><span class="k">class</span> <span class="nc">Label</span><span class="p">(</span><span class="n">Assembly</span><span class="p">):</span>
<span class="k">def</span> <span class="nf">resolve</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">start</span><span class="p">):</span>
<span class="k">return</span> <span class="p">((</span><span class="bp">self</span><span class="p">,</span> <span class="n">start</span><span class="p">),)</span>
</code></pre></div>
<p>So is a <code class="language-plaintext highlighter-rouge">SetLineNo</code> except for adding to the line-number table.</p>
<div class="highlight"><pre><code class="language-python"><span class="k">class</span> <span class="nc">SetLineNo</span><span class="p">(</span><span class="n">Assembly</span><span class="p">):</span>
<span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">line</span><span class="p">):</span>
<span class="bp">self</span><span class="p">.</span><span class="n">line</span> <span class="o">=</span> <span class="n">line</span>
<span class="k">def</span> <span class="nf">line_nos</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">start</span><span class="p">):</span>
<span class="k">return</span> <span class="p">((</span><span class="n">start</span><span class="p">,</span> <span class="bp">self</span><span class="p">.</span><span class="n">line</span><span class="p">),)</span>
</code></pre></div>
<p>There are four kinds of bytecode instruction: absolute jumps, relative
jumps, and non-jumps with or without an argument. (‘Jump’ for our
purposes means any instruction taking a label argument.)</p>
<div class="highlight"><pre><code class="language-python"><span class="k">class</span> <span class="nc">Instruction</span><span class="p">(</span><span class="n">Assembly</span><span class="p">):</span>
<span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">opcode</span><span class="p">,</span> <span class="n">arg</span><span class="p">):</span>
<span class="bp">self</span><span class="p">.</span><span class="n">opcode</span> <span class="o">=</span> <span class="n">opcode</span>
<span class="bp">self</span><span class="p">.</span><span class="n">arg</span> <span class="o">=</span> <span class="n">arg</span>
<span class="bp">self</span><span class="p">.</span><span class="n">length</span> <span class="o">=</span> <span class="mi">1</span> <span class="k">if</span> <span class="n">arg</span> <span class="ow">is</span> <span class="bp">None</span> <span class="k">else</span> <span class="mi">3</span>
<span class="k">def</span> <span class="nf">encode</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">start</span><span class="p">,</span> <span class="n">addresses</span><span class="p">):</span>
<span class="k">if</span> <span class="bp">self</span><span class="p">.</span><span class="n">opcode</span> <span class="ow">in</span> <span class="n">dis</span><span class="p">.</span><span class="n">hasjabs</span><span class="p">:</span> <span class="n">arg</span> <span class="o">=</span> <span class="n">addresses</span><span class="p">[</span><span class="bp">self</span><span class="p">.</span><span class="n">arg</span><span class="p">]</span>
<span class="k">elif</span> <span class="bp">self</span><span class="p">.</span><span class="n">opcode</span> <span class="ow">in</span> <span class="n">dis</span><span class="p">.</span><span class="n">hasjrel</span><span class="p">:</span> <span class="n">arg</span> <span class="o">=</span> <span class="n">addresses</span><span class="p">[</span><span class="bp">self</span><span class="p">.</span><span class="n">arg</span><span class="p">]</span> <span class="o">-</span> <span class="p">(</span><span class="n">start</span><span class="o">+</span><span class="mi">3</span><span class="p">)</span>
<span class="k">else</span><span class="p">:</span> <span class="n">arg</span> <span class="o">=</span> <span class="bp">self</span><span class="p">.</span><span class="n">arg</span>
<span class="k">if</span> <span class="n">arg</span> <span class="ow">is</span> <span class="bp">None</span><span class="p">:</span> <span class="k">return</span> <span class="nb">bytes</span><span class="p">([</span><span class="bp">self</span><span class="p">.</span><span class="n">opcode</span><span class="p">])</span>
<span class="k">else</span><span class="p">:</span> <span class="k">return</span> <span class="nb">bytes</span><span class="p">([</span><span class="bp">self</span><span class="p">.</span><span class="n">opcode</span><span class="p">,</span> <span class="n">arg</span> <span class="o">%</span> <span class="mi">256</span><span class="p">,</span> <span class="n">arg</span> <span class="o">//</span> <span class="mi">256</span><span class="p">])</span>
<span class="k">def</span> <span class="nf">plumb</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">depths</span><span class="p">):</span>
<span class="n">arg</span> <span class="o">=</span> <span class="mi">0</span> <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">arg</span><span class="p">,</span> <span class="n">Label</span><span class="p">)</span> <span class="k">else</span> <span class="bp">self</span><span class="p">.</span><span class="n">arg</span>
<span class="n">depths</span><span class="p">.</span><span class="n">append</span><span class="p">(</span><span class="n">depths</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">dis</span><span class="p">.</span><span class="n">stack_effect</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">opcode</span><span class="p">,</span> <span class="n">arg</span><span class="p">))</span>
</code></pre></div>
<p><code class="language-plaintext highlighter-rouge">plumb</code> computes the stack depth after the instruction as a change
from the depth before it: for example, a <code class="language-plaintext highlighter-rouge">BINARY_ADD</code> instruction will
remove two values from the stack and replace them with one, for a net
change in the stack depth of -1. <code class="language-plaintext highlighter-rouge">dis.stack_effect</code> gives us this
net change.</p>
<p>What about jump instructions? The stack depth right after a jump
instruction could be unrelated to the depth before it: instead the
depth should be the same at the jump <em>target</em>. CPython’s compiler
therefore traces through the jumps, propagating the depths along every
path and making sure they’re consistent; but Tailbiter is much
simpler. We can almost get away with treating jumps like other
instructions, because the code for a statement has no net stack
effect: anything it will push on the stack it will later also pop. An
if-then-else statement, as we saw above in <code class="language-plaintext highlighter-rouge">visit_If</code>, has a test
expression, a then-block, and an else-block, with branch and jump
instructions in between. The stack depth at the start of the
else-block should be the same as at the start of the then-block, but
that’s just what it would be if we got there by running the then-block
instead of branching around it: we can use the above <code class="language-plaintext highlighter-rouge">plumb</code> logic
unchanged, as long as <code class="language-plaintext highlighter-rouge">dis.stack_effect</code> of the jump instruction is
also 0, which it is.</p>
<p>The same nice coincidence doesn’t quite hold for an if <em>expression</em>
(like <code class="language-plaintext highlighter-rouge">then_exp if test else else_exp</code>). If we compile this the same
way—the code for <code class="language-plaintext highlighter-rouge">test</code>, a branch, <code class="language-plaintext highlighter-rouge">then_exp</code>, a jump, and
<code class="language-plaintext highlighter-rouge">else_exp</code>—then the stack after <code class="language-plaintext highlighter-rouge">then_exp</code> will be 1 deeper than
before it. If we’re to analyze the stack depth <em>as if</em> this were all
straight-line code with no branches, then we need an extra note that
the stack at the start of <code class="language-plaintext highlighter-rouge">else_exp</code> is one slot less deep than this
analysis would otherwise arrive at. We can hack this into shape by inventing a
pseudoinstruction to include at that point in the code:</p>
<div class="highlight"><pre><code class="language-python"><span class="k">class</span> <span class="nc">OffsetStack</span><span class="p">(</span><span class="n">Assembly</span><span class="p">):</span>
<span class="k">def</span> <span class="nf">plumb</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">depths</span><span class="p">):</span>
<span class="n">depths</span><span class="p">.</span><span class="n">append</span><span class="p">(</span><span class="n">depths</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span>
</code></pre></div>
<p>So an if expression is compiled exactly like an if statement, except
for the added <code class="language-plaintext highlighter-rouge">OffsetStack()</code> directive:</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in CodeGen v1+:
</span> <span class="k">def</span> <span class="nf">visit_IfExp</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="n">orelse</span><span class="p">,</span> <span class="n">after</span> <span class="o">=</span> <span class="n">Label</span><span class="p">(),</span> <span class="n">Label</span><span class="p">()</span>
<span class="k">return</span> <span class="p">(</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">test</span><span class="p">)</span> <span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">POP_JUMP_IF_FALSE</span><span class="p">(</span><span class="n">orelse</span><span class="p">)</span>
<span class="o">+</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">body</span><span class="p">)</span> <span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">JUMP_FORWARD</span><span class="p">(</span><span class="n">after</span><span class="p">)</span>
<span class="o">+</span> <span class="n">OffsetStack</span><span class="p">()</span>
<span class="o">+</span> <span class="n">orelse</span> <span class="o">+</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">orelse</span><span class="p">)</span>
<span class="o">+</span> <span class="n">after</span><span class="p">)</span>
</code></pre></div>
<p>We’ll see <code class="language-plaintext highlighter-rouge">OffsetStack</code> appearing in a couple more places later for
the same sort of reason.</p>
<p>A <code class="language-plaintext highlighter-rouge">Chain</code> catenates two assembly-code fragments in sequence. It uses
<code class="language-plaintext highlighter-rouge">itertools.chain</code> to catenate the label resolutions, bytecodes, and
<code class="language-plaintext highlighter-rouge">lnotab</code> entries produced in the different methods.</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in assembly types and functions v1:
</span><span class="k">class</span> <span class="nc">Chain</span><span class="p">(</span><span class="n">Assembly</span><span class="p">):</span>
<span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">assembly1</span><span class="p">,</span> <span class="n">assembly2</span><span class="p">):</span>
<span class="bp">self</span><span class="p">.</span><span class="n">part1</span> <span class="o">=</span> <span class="n">assembly1</span>
<span class="bp">self</span><span class="p">.</span><span class="n">part2</span> <span class="o">=</span> <span class="n">assembly2</span>
<span class="bp">self</span><span class="p">.</span><span class="n">length</span> <span class="o">=</span> <span class="n">assembly1</span><span class="p">.</span><span class="n">length</span> <span class="o">+</span> <span class="n">assembly2</span><span class="p">.</span><span class="n">length</span>
<span class="k">def</span> <span class="nf">resolve</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">start</span><span class="p">):</span>
<span class="k">return</span> <span class="n">chain</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">part1</span><span class="p">.</span><span class="n">resolve</span><span class="p">(</span><span class="n">start</span><span class="p">),</span>
<span class="bp">self</span><span class="p">.</span><span class="n">part2</span><span class="p">.</span><span class="n">resolve</span><span class="p">(</span><span class="n">start</span> <span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">part1</span><span class="p">.</span><span class="n">length</span><span class="p">))</span>
<span class="k">def</span> <span class="nf">encode</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">start</span><span class="p">,</span> <span class="n">addresses</span><span class="p">):</span>
<span class="k">return</span> <span class="n">chain</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">part1</span><span class="p">.</span><span class="n">encode</span><span class="p">(</span><span class="n">start</span><span class="p">,</span> <span class="n">addresses</span><span class="p">),</span>
<span class="bp">self</span><span class="p">.</span><span class="n">part2</span><span class="p">.</span><span class="n">encode</span><span class="p">(</span><span class="n">start</span> <span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">part1</span><span class="p">.</span><span class="n">length</span><span class="p">,</span> <span class="n">addresses</span><span class="p">))</span>
<span class="k">def</span> <span class="nf">line_nos</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">start</span><span class="p">):</span>
<span class="k">return</span> <span class="n">chain</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">part1</span><span class="p">.</span><span class="n">line_nos</span><span class="p">(</span><span class="n">start</span><span class="p">),</span>
<span class="bp">self</span><span class="p">.</span><span class="n">part2</span><span class="p">.</span><span class="n">line_nos</span><span class="p">(</span><span class="n">start</span> <span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">part1</span><span class="p">.</span><span class="n">length</span><span class="p">))</span>
<span class="k">def</span> <span class="nf">plumb</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">depths</span><span class="p">):</span>
<span class="bp">self</span><span class="p">.</span><span class="n">part1</span><span class="p">.</span><span class="n">plumb</span><span class="p">(</span><span class="n">depths</span><span class="p">)</span>
<span class="bp">self</span><span class="p">.</span><span class="n">part2</span><span class="p">.</span><span class="n">plumb</span><span class="p">(</span><span class="n">depths</span><span class="p">)</span>
</code></pre></div>
<p>(I was a little surprised that no stack overflows bit me with this
code, at least not in compiling a program the size of Tailbiter
itself. I made no effort to keep the chains balanced.)</p>
<h3 id="expression-types-proliferate-more-code-generation">Expression types proliferate: more code generation</h3>
<p>Dict literals like <code class="language-plaintext highlighter-rouge">{'a': 'x', 'b': 'y'}</code> turn into code like</p>
<div class="highlight"><pre><code># in examples:
0 BUILD_MAP 2
3 LOAD_CONST 0 ('x')
6 LOAD_CONST 1 ('a')
9 STORE_MAP
10 LOAD_CONST 2 ('y')
13 LOAD_CONST 3 ('b')
16 STORE_MAP
</code></pre></div>
<p>So:</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in CodeGen v1+:
</span> <span class="k">def</span> <span class="nf">visit_Dict</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">return</span> <span class="p">(</span><span class="n">op</span><span class="p">.</span><span class="n">BUILD_MAP</span><span class="p">(</span><span class="nb">min</span><span class="p">(</span><span class="mh">0xFFFF</span><span class="p">,</span> <span class="nb">len</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">keys</span><span class="p">)))</span>
<span class="o">+</span> <span class="n">concat</span><span class="p">([</span><span class="bp">self</span><span class="p">(</span><span class="n">v</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="p">(</span><span class="n">k</span><span class="p">)</span> <span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">STORE_MAP</span>
<span class="k">for</span> <span class="n">k</span><span class="p">,</span> <span class="n">v</span> <span class="ow">in</span> <span class="nb">zip</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">keys</span><span class="p">,</span> <span class="n">t</span><span class="p">.</span><span class="n">values</span><span class="p">)]))</span>
</code></pre></div>
<p>The argument to <code class="language-plaintext highlighter-rouge">BUILD_MAP</code> gives the runtime a hint of the dict’s
size. It’s allowed to be wrong, since dicts can grow and shrink—but
not to overflow the two bytes allotted to an argument in
bytecode. Thus the <code class="language-plaintext highlighter-rouge">min</code>.</p>
<p>A simple subscript expression, <code class="language-plaintext highlighter-rouge">a[x]</code>, becomes</p>
<div class="highlight"><pre><code># in examples:
0 LOAD_NAME 0 (a)
3 LOAD_NAME 1 (x)
6 BINARY_SUBSCR
</code></pre></div>
<p>Similarly, <code class="language-plaintext highlighter-rouge">a.x</code> becomes</p>
<div class="highlight"><pre><code># in examples:
0 LOAD_NAME 0 (a)
3 LOAD_ATTR 1 (x)
</code></pre></div>
<p>Like name nodes, subscript nodes can appear on the left-hand side of
an assignment statement, like <code class="language-plaintext highlighter-rouge">a.x = 42</code>. They carry a <code class="language-plaintext highlighter-rouge">t.ctx</code> field
just like a name’s.</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in CodeGen v1+:
</span> <span class="k">def</span> <span class="nf">visit_Subscript</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">return</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">value</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="nb">slice</span><span class="p">.</span><span class="n">value</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">subscr_ops</span><span class="p">[</span><span class="nb">type</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">ctx</span><span class="p">)]</span>
<span class="n">subscr_ops</span> <span class="o">=</span> <span class="p">{</span><span class="n">ast</span><span class="p">.</span><span class="n">Load</span><span class="p">:</span> <span class="n">op</span><span class="p">.</span><span class="n">BINARY_SUBSCR</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">Store</span><span class="p">:</span> <span class="n">op</span><span class="p">.</span><span class="n">STORE_SUBSCR</span><span class="p">}</span>
<span class="k">def</span> <span class="nf">visit_Attribute</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="n">sub_op</span> <span class="o">=</span> <span class="bp">self</span><span class="p">.</span><span class="n">attr_ops</span><span class="p">[</span><span class="nb">type</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">ctx</span><span class="p">)]</span>
<span class="k">return</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">value</span><span class="p">)</span> <span class="o">+</span> <span class="n">sub_op</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">names</span><span class="p">[</span><span class="n">t</span><span class="p">.</span><span class="n">attr</span><span class="p">])</span>
<span class="n">attr_ops</span> <span class="o">=</span> <span class="p">{</span><span class="n">ast</span><span class="p">.</span><span class="n">Load</span><span class="p">:</span> <span class="n">op</span><span class="p">.</span><span class="n">LOAD_ATTR</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">Store</span><span class="p">:</span> <span class="n">op</span><span class="p">.</span><span class="n">STORE_ATTR</span><span class="p">}</span>
</code></pre></div>
<p>A list or tuple can also appear in both load and store contexts. As a
load, <code class="language-plaintext highlighter-rouge">['a', 'b']</code> becomes</p>
<div class="highlight"><pre><code># in examples:
0 LOAD_CONST 0 ('a')
3 LOAD_CONST 1 ('b')
6 BUILD_LIST 2
</code></pre></div>
<p>where 2 is the length of the list. Unlike with <code class="language-plaintext highlighter-rouge">BUILD_MAP</code> the length
must be exact.</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in CodeGen v1+:
</span> <span class="k">def</span> <span class="nf">visit_List</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="p">.</span><span class="n">visit_sequence</span><span class="p">(</span><span class="n">t</span><span class="p">,</span> <span class="n">op</span><span class="p">.</span><span class="n">BUILD_LIST</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">visit_Tuple</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span> <span class="k">return</span> <span class="bp">self</span><span class="p">.</span><span class="n">visit_sequence</span><span class="p">(</span><span class="n">t</span><span class="p">,</span> <span class="n">op</span><span class="p">.</span><span class="n">BUILD_TUPLE</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">visit_sequence</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">,</span> <span class="n">build_op</span><span class="p">):</span>
<span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">ctx</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">Load</span><span class="p">):</span>
<span class="k">return</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">elts</span><span class="p">)</span> <span class="o">+</span> <span class="n">build_op</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">elts</span><span class="p">))</span>
<span class="k">elif</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">ctx</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">Store</span><span class="p">):</span>
<span class="k">return</span> <span class="n">op</span><span class="p">.</span><span class="n">UNPACK_SEQUENCE</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">elts</span><span class="p">))</span> <span class="o">+</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">elts</span><span class="p">)</span>
<span class="k">else</span><span class="p">:</span>
<span class="k">assert</span> <span class="bp">False</span>
</code></pre></div>
<p>A unary operator works just like a function call except it gets its
own instruction, for efficiency. <code class="language-plaintext highlighter-rouge">not -x</code> gets compiled to</p>
<div class="highlight"><pre><code># in examples:
0 LOAD_NAME 0 (x)
3 UNARY_NEGATIVE
4 UNARY_NOT
</code></pre></div>
<p>so:</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in CodeGen v1+:
</span> <span class="k">def</span> <span class="nf">visit_UnaryOp</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">return</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">operand</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">ops1</span><span class="p">[</span><span class="nb">type</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">op</span><span class="p">)]</span>
<span class="n">ops1</span> <span class="o">=</span> <span class="p">{</span><span class="n">ast</span><span class="p">.</span><span class="n">UAdd</span><span class="p">:</span> <span class="n">op</span><span class="p">.</span><span class="n">UNARY_POSITIVE</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">Invert</span><span class="p">:</span> <span class="n">op</span><span class="p">.</span><span class="n">UNARY_INVERT</span><span class="p">,</span>
<span class="n">ast</span><span class="p">.</span><span class="n">USub</span><span class="p">:</span> <span class="n">op</span><span class="p">.</span><span class="n">UNARY_NEGATIVE</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">Not</span><span class="p">:</span> <span class="n">op</span><span class="p">.</span><span class="n">UNARY_NOT</span><span class="p">}</span>
</code></pre></div>
<p>Binary operators get compiled the same way:</p>
<div class="highlight"><pre><code class="language-python"> <span class="k">def</span> <span class="nf">visit_BinOp</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">return</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">left</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">right</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">ops2</span><span class="p">[</span><span class="nb">type</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">op</span><span class="p">)]</span>
<span class="n">ops2</span> <span class="o">=</span> <span class="p">{</span><span class="n">ast</span><span class="p">.</span><span class="n">Pow</span><span class="p">:</span> <span class="n">op</span><span class="p">.</span><span class="n">BINARY_POWER</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">Add</span><span class="p">:</span> <span class="n">op</span><span class="p">.</span><span class="n">BINARY_ADD</span><span class="p">,</span>
<span class="n">ast</span><span class="p">.</span><span class="n">LShift</span><span class="p">:</span> <span class="n">op</span><span class="p">.</span><span class="n">BINARY_LSHIFT</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">Sub</span><span class="p">:</span> <span class="n">op</span><span class="p">.</span><span class="n">BINARY_SUBTRACT</span><span class="p">,</span>
<span class="n">ast</span><span class="p">.</span><span class="n">RShift</span><span class="p">:</span> <span class="n">op</span><span class="p">.</span><span class="n">BINARY_RSHIFT</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">Mult</span><span class="p">:</span> <span class="n">op</span><span class="p">.</span><span class="n">BINARY_MULTIPLY</span><span class="p">,</span>
<span class="n">ast</span><span class="p">.</span><span class="n">BitOr</span><span class="p">:</span> <span class="n">op</span><span class="p">.</span><span class="n">BINARY_OR</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">Mod</span><span class="p">:</span> <span class="n">op</span><span class="p">.</span><span class="n">BINARY_MODULO</span><span class="p">,</span>
<span class="n">ast</span><span class="p">.</span><span class="n">BitAnd</span><span class="p">:</span> <span class="n">op</span><span class="p">.</span><span class="n">BINARY_AND</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">Div</span><span class="p">:</span> <span class="n">op</span><span class="p">.</span><span class="n">BINARY_TRUE_DIVIDE</span><span class="p">,</span>
<span class="n">ast</span><span class="p">.</span><span class="n">BitXor</span><span class="p">:</span> <span class="n">op</span><span class="p">.</span><span class="n">BINARY_XOR</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">FloorDiv</span><span class="p">:</span> <span class="n">op</span><span class="p">.</span><span class="n">BINARY_FLOOR_DIVIDE</span><span class="p">}</span>
</code></pre></div>
<p>compiling, for example, <code class="language-plaintext highlighter-rouge">x-1</code> to</p>
<div class="highlight"><pre><code># in examples:
0 LOAD_NAME 0 (x)
3 LOAD_CONST 0 (1)
6 BINARY_SUBTRACT
</code></pre></div>
<p>Comparisons, like <code class="language-plaintext highlighter-rouge">x<2</code>, take a slightly different form in the AST,
because Python treats a chain of comparisons specially: <code class="language-plaintext highlighter-rouge">1<x<2</code> is a
single expression as a single AST node holding a list of operators and
a list of their right operands. Our subset of Python doesn’t cover
this case, only binary comparisons like <code class="language-plaintext highlighter-rouge">x<2</code>.</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in CodeGen v1+:
</span> <span class="k">def</span> <span class="nf">visit_Compare</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="p">[</span><span class="n">operator</span><span class="p">],</span> <span class="p">[</span><span class="n">right</span><span class="p">]</span> <span class="o">=</span> <span class="n">t</span><span class="p">.</span><span class="n">ops</span><span class="p">,</span> <span class="n">t</span><span class="p">.</span><span class="n">comparators</span>
<span class="n">cmp_index</span> <span class="o">=</span> <span class="n">dis</span><span class="p">.</span><span class="n">cmp_op</span><span class="p">.</span><span class="n">index</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">ops_cmp</span><span class="p">[</span><span class="nb">type</span><span class="p">(</span><span class="n">operator</span><span class="p">)])</span>
<span class="k">return</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">left</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="p">(</span><span class="n">right</span><span class="p">)</span> <span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">COMPARE_OP</span><span class="p">(</span><span class="n">cmp_index</span><span class="p">)</span>
<span class="n">ops_cmp</span> <span class="o">=</span> <span class="p">{</span><span class="n">ast</span><span class="p">.</span><span class="n">Eq</span><span class="p">:</span> <span class="s">'=='</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">NotEq</span><span class="p">:</span> <span class="s">'!='</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">Is</span><span class="p">:</span> <span class="s">'is'</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">IsNot</span><span class="p">:</span> <span class="s">'is not'</span><span class="p">,</span>
<span class="n">ast</span><span class="p">.</span><span class="n">Lt</span><span class="p">:</span> <span class="s">'<'</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">LtE</span><span class="p">:</span> <span class="s">'<='</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">In</span><span class="p">:</span> <span class="s">'in'</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">NotIn</span><span class="p">:</span> <span class="s">'not in'</span><span class="p">,</span>
<span class="n">ast</span><span class="p">.</span><span class="n">Gt</span><span class="p">:</span> <span class="s">'>'</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">GtE</span><span class="p">:</span> <span class="s">'>='</span><span class="p">}</span>
</code></pre></div>
<p>For <code class="language-plaintext highlighter-rouge">and</code> and <code class="language-plaintext highlighter-rouge">or</code> expressions, like <code class="language-plaintext highlighter-rouge">if</code>, we need to be careful
about the stack depth across different branches of control.
<code class="language-plaintext highlighter-rouge">print(x or y)</code> compiles to</p>
<div class="highlight"><pre><code># in examples:
0 LOAD_NAME 0 (print)
3 LOAD_NAME 1 (x)
6 JUMP_IF_TRUE_OR_POP 12
9 LOAD_NAME 2 (y)
>> 12 CALL_FUNCTION 1 (1 positional, 0 keyword pair)
</code></pre></div>
<p><code class="language-plaintext highlighter-rouge">JUMP_IF_TRUE_OR_POP</code> only pops the tested value if it came out
false. At index 12, whichever way execution got there, the stack has
the same height: two entries.</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in CodeGen v1+:
</span> <span class="k">def</span> <span class="nf">visit_BoolOp</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="n">op_jump</span> <span class="o">=</span> <span class="bp">self</span><span class="p">.</span><span class="n">ops_bool</span><span class="p">[</span><span class="nb">type</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">op</span><span class="p">)]</span>
<span class="k">def</span> <span class="nf">compose</span><span class="p">(</span><span class="n">left</span><span class="p">,</span> <span class="n">right</span><span class="p">):</span>
<span class="n">after</span> <span class="o">=</span> <span class="n">Label</span><span class="p">()</span>
<span class="k">return</span> <span class="n">left</span> <span class="o">+</span> <span class="n">op_jump</span><span class="p">(</span><span class="n">after</span><span class="p">)</span> <span class="o">+</span> <span class="n">OffsetStack</span><span class="p">()</span> <span class="o">+</span> <span class="n">right</span> <span class="o">+</span> <span class="n">after</span>
<span class="k">return</span> <span class="nb">reduce</span><span class="p">(</span><span class="n">compose</span><span class="p">,</span> <span class="nb">map</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">.</span><span class="n">values</span><span class="p">))</span>
<span class="n">ops_bool</span> <span class="o">=</span> <span class="p">{</span><span class="n">ast</span><span class="p">.</span><span class="n">And</span><span class="p">:</span> <span class="n">op</span><span class="p">.</span><span class="n">JUMP_IF_FALSE_OR_POP</span><span class="p">,</span>
<span class="n">ast</span><span class="p">.</span><span class="n">Or</span><span class="p">:</span> <span class="n">op</span><span class="p">.</span><span class="n">JUMP_IF_TRUE_OR_POP</span><span class="p">}</span>
</code></pre></div>
<p>Since a <code class="language-plaintext highlighter-rouge">BoolOp</code> collects all of the subexpressions of an expression
like <code class="language-plaintext highlighter-rouge">a and b and c</code> (instead of Python representing this as a tree of
binary <code class="language-plaintext highlighter-rouge">BoolOp</code>s), we must <code class="language-plaintext highlighter-rouge">reduce</code> over the list.</p>
<p><code class="language-plaintext highlighter-rouge">OffsetStack()</code> is needed here because, for some reason, for these two
branch instructions <code class="language-plaintext highlighter-rouge">dis.stack_effect</code> gives the stack effect seen if
the jump is taken, instead of at the next instruction.</p>
<h3 id="more-statement-types">More statement types</h3>
<div class="highlight"><pre><code class="language-python"> <span class="k">def</span> <span class="nf">visit_Pass</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">return</span> <span class="n">no_op</span>
<span class="k">def</span> <span class="nf">visit_Raise</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">return</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">exc</span><span class="p">)</span> <span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">RAISE_VARARGS</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span>
</code></pre></div>
<p>We handle only the most common form of <code class="language-plaintext highlighter-rouge">raise</code>: <code class="language-plaintext highlighter-rouge">raise foo</code>.</p>
<div class="highlight"><pre><code class="language-python"> <span class="k">def</span> <span class="nf">visit_Import</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">return</span> <span class="n">concat</span><span class="p">([</span><span class="bp">self</span><span class="p">.</span><span class="n">import_name</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="bp">None</span><span class="p">,</span> <span class="n">alias</span><span class="p">.</span><span class="n">name</span><span class="p">)</span>
<span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">store</span><span class="p">(</span><span class="n">alias</span><span class="p">.</span><span class="n">asname</span> <span class="ow">or</span> <span class="n">alias</span><span class="p">.</span><span class="n">name</span><span class="p">.</span><span class="n">split</span><span class="p">(</span><span class="s">'.'</span><span class="p">)[</span><span class="mi">0</span><span class="p">])</span>
<span class="k">for</span> <span class="n">alias</span> <span class="ow">in</span> <span class="n">t</span><span class="p">.</span><span class="n">names</span><span class="p">])</span>
<span class="k">def</span> <span class="nf">visit_ImportFrom</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="n">fromlist</span> <span class="o">=</span> <span class="nb">tuple</span><span class="p">([</span><span class="n">alias</span><span class="p">.</span><span class="n">name</span> <span class="k">for</span> <span class="n">alias</span> <span class="ow">in</span> <span class="n">t</span><span class="p">.</span><span class="n">names</span><span class="p">])</span>
<span class="k">return</span> <span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">import_name</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">level</span><span class="p">,</span> <span class="n">fromlist</span><span class="p">,</span> <span class="n">t</span><span class="p">.</span><span class="n">module</span><span class="p">)</span>
<span class="o">+</span> <span class="n">concat</span><span class="p">([</span><span class="n">op</span><span class="p">.</span><span class="n">IMPORT_FROM</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">names</span><span class="p">[</span><span class="n">alias</span><span class="p">.</span><span class="n">name</span><span class="p">])</span>
<span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">store</span><span class="p">(</span><span class="n">alias</span><span class="p">.</span><span class="n">asname</span> <span class="ow">or</span> <span class="n">alias</span><span class="p">.</span><span class="n">name</span><span class="p">)</span>
<span class="k">for</span> <span class="n">alias</span> <span class="ow">in</span> <span class="n">t</span><span class="p">.</span><span class="n">names</span><span class="p">])</span>
<span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">POP_TOP</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">import_name</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">level</span><span class="p">,</span> <span class="n">fromlist</span><span class="p">,</span> <span class="n">name</span><span class="p">):</span>
<span class="k">return</span> <span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">load_const</span><span class="p">(</span><span class="n">level</span><span class="p">)</span>
<span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">load_const</span><span class="p">(</span><span class="n">fromlist</span><span class="p">)</span>
<span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">IMPORT_NAME</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">names</span><span class="p">[</span><span class="n">name</span><span class="p">]))</span>
</code></pre></div>
<p>The <code class="language-plaintext highlighter-rouge">import</code> visitors are full of technical details I’ll pass over. We
could instead have turned <code class="language-plaintext highlighter-rouge">import</code> statements into <code class="language-plaintext highlighter-rouge">__import__()</code>
calls and assignments, to pass on to the rest of the code generator;
but that would take about as much compiler
code, to produce worse compiled
code.</p>
<div class="highlight"><pre><code class="language-python"> <span class="k">def</span> <span class="nf">visit_While</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="n">loop</span><span class="p">,</span> <span class="n">end</span> <span class="o">=</span> <span class="n">Label</span><span class="p">(),</span> <span class="n">Label</span><span class="p">()</span>
<span class="k">return</span> <span class="p">(</span> <span class="n">loop</span> <span class="o">+</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">test</span><span class="p">)</span> <span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">POP_JUMP_IF_FALSE</span><span class="p">(</span><span class="n">end</span><span class="p">)</span>
<span class="o">+</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">body</span><span class="p">)</span> <span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">JUMP_ABSOLUTE</span><span class="p">(</span><span class="n">loop</span><span class="p">)</span>
<span class="o">+</span> <span class="n">end</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">visit_For</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="n">loop</span><span class="p">,</span> <span class="n">end</span> <span class="o">=</span> <span class="n">Label</span><span class="p">(),</span> <span class="n">Label</span><span class="p">()</span>
<span class="k">return</span> <span class="p">(</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="nb">iter</span><span class="p">)</span> <span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">GET_ITER</span>
<span class="o">+</span> <span class="n">loop</span> <span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">FOR_ITER</span><span class="p">(</span><span class="n">end</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">target</span><span class="p">)</span>
<span class="o">+</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">body</span><span class="p">)</span> <span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">JUMP_ABSOLUTE</span><span class="p">(</span><span class="n">loop</span><span class="p">)</span>
<span class="o">+</span> <span class="n">end</span> <span class="o">+</span> <span class="n">OffsetStack</span><span class="p">())</span>
</code></pre></div>
<p>Compiling <code class="language-plaintext highlighter-rouge">while</code> and <code class="language-plaintext highlighter-rouge">for</code>, for our subset, is much like <code class="language-plaintext highlighter-rouge">if</code>. A
<code class="language-plaintext highlighter-rouge">for</code> loop coerces the value of the <code class="language-plaintext highlighter-rouge">t.iter</code> expression to an iterator
object, via <code class="language-plaintext highlighter-rouge">GET_ITER</code>, leaving the iterator on the stack throughout
the loop. When the iterator is exhausted,<code class="language-plaintext highlighter-rouge">FOR_ITER(end)</code> pops it off
and jumps to <code class="language-plaintext highlighter-rouge">end</code>; there we must account for the pop in the
stack-depth analysis (<code class="language-plaintext highlighter-rouge">OffsetStack()</code>).</p>
<p>Now we have a runnable program again, that can compile
nontrivial computations! We could flesh it out further with more node
types—<code class="language-plaintext highlighter-rouge">break</code> and <code class="language-plaintext highlighter-rouge">continue</code>, for example; however, those don’t add
materially to the complexity of the kinds of programs we can compile.
Consider them an exercise for the reader.</p>
<h2 id="a-completed-compiler-rendering-functions-and-classes">A completed compiler: rendering functions and classes</h2>
<p>The next biggest gain of expressiveness will be in compiling functions
and classes. As we’ll see shortly, this requires even bigger changes
to our design.</p>
<div class="highlight"><pre><code># in figure 2: ASTs added in Tailbiter version 2.
stmt = FunctionDef(identifier name, arguments args, stmt* body, expr* decorator_list)
| ClassDef(identifier name, expr* bases, stmt* body)
| Return(expr? value)
| Assert(expr test, expr? msg)
arguments = (arg* args)
arg = (identifier arg)
expr = Lambda(arguments args, expr body)
| ListComp(expr elt, comprehension* generators)
comprehension = (expr target, expr iter, expr* ifs)
</code></pre></div>
<p>Once again, we ask ourselves if our current design can handle the
complexity we’ve added in this version. Tailbiter v1 jumped
immediately into generating code, but now the code for a variable
access will depend on how the variable appears in the rest of the
source program. It might be a local or a global variable, for
instance. As another issue, function definitions and lambda
expressions have a lot in common; it’d be easy to end up with
duplicated logic in generating code for them. The same goes for list
comprehensions (<code class="language-plaintext highlighter-rouge">ListComp</code> above) because they act like a nested
function (to bound the scope of the loop variables). Therefore,
before starting to generate code we’ll do some setup:</p>
<ul>
<li>
<p>First we “desugar” the AST, replacing some of the nodes with
equivalent code that uses only simpler node types. (The language
minus certain features is less sweet but equally nutritious.) We’ll
turn list comprehensions into local functions with a loop, we’ll
reduce function defs and lambda expressions to a common form, and
while we’re at it we’ll turn <code class="language-plaintext highlighter-rouge">assert</code> into <code class="language-plaintext highlighter-rouge">if</code> plus <code class="language-plaintext highlighter-rouge">raise</code>.
CPython has no desugaring pass, though it’s been suggested by some:
optimizations would be easier to express as AST rewrites
than bytecode rewrites. (A trivial example: change <code class="language-plaintext highlighter-rouge">2+3</code> to <code class="language-plaintext highlighter-rouge">5</code>.)</p>
</li>
<li>
<p>We complain if the desugared AST departs from our subset of
Python. CPython lacks this pass, of course, and we won’t examine
it. It’s valuable in two ways: documenting what we claim to compile
correctly, and failing fast on input we never meant to support.</p>
</li>
<li>
<p>Then we analyze the scope of variables: their definitions and uses
in classes and functions (including the functions introduced by
desugaring). This scope information is needed to decide where each
variable should live at runtime: a global variable will appear in
the module’s dictionary, looked up by name, while a local variable
appears in a local environment at a known integer
index—this is why local variable access is fast. Variables may
also be defined in the body of a class—these are similar to global
variables—or in an outer scope and then accessed from a lambda
expression or nested function definition. These “nonlocal” variables
turn into different bytecode than local and global ones.</p>
</li>
<li>
<p>With the scope info in hand we finally generate bytecode as before, by
walking the AST.</p>
</li>
</ul>
<p>Do we need the complication of nonlocal variables? Maybe not: the
final compiler uses just two lambda expressions. However, there are
nine list comprehensions, and Python’s just no fun without them. To
compile them correctly we can’t avoid nested scopes.</p>
<p>Python comes with a scope analyzer built in, the <code class="language-plaintext highlighter-rouge">symtable</code>
module—but we can’t use it! It requires a source-code string, not an
AST, and ASTs lack a method to give us back source code. In
Tailbiter’s early development I used <code class="language-plaintext highlighter-rouge">symtable</code> anyway, as
scaffolding; this forced it to take textual source code instead of an
AST for its input.</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in compile to code v2:
</span><span class="k">def</span> <span class="nf">code_for_module</span><span class="p">(</span><span class="n">module_name</span><span class="p">,</span> <span class="n">filename</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="n">t</span> <span class="o">=</span> <span class="n">desugar</span><span class="p">(</span><span class="n">t</span><span class="p">)</span>
<span class="n">check_conformity</span><span class="p">(</span><span class="n">t</span><span class="p">)</span>
<span class="k">return</span> <span class="n">CodeGen</span><span class="p">(</span><span class="n">filename</span><span class="p">,</span> <span class="n">top_scope</span><span class="p">(</span><span class="n">t</span><span class="p">)).</span><span class="n">compile_module</span><span class="p">(</span><span class="n">t</span><span class="p">,</span> <span class="n">module_name</span><span class="p">)</span>
<span class="o"><<</span><span class="n">CodeGen</span><span class="o">>></span>
</code></pre></div>
<h3 id="sugar-delenda-est">Sugar delenda est</h3>
<p>Besides <code class="language-plaintext highlighter-rouge">NodeVisitor</code>, Python’s <code class="language-plaintext highlighter-rouge">ast</code> module defines another visitor
class, for not just walking through but <em>transforming</em> trees. It expects each visit method to
return an AST node, which will be taken to replace the node that was
the argument. The default behavior recurses on child nodes, leaving
the node otherwise unchanged. Desugaring uses such a transformer:</p>
<div class="highlight"><pre><code class="language-python"><span class="k">def</span> <span class="nf">desugar</span><span class="p">(</span><span class="n">t</span><span class="p">):</span>
<span class="k">return</span> <span class="n">ast</span><span class="p">.</span><span class="n">fix_missing_locations</span><span class="p">(</span><span class="n">Desugarer</span><span class="p">().</span><span class="n">visit</span><span class="p">(</span><span class="n">t</span><span class="p">))</span>
<span class="k">class</span> <span class="nc">Desugarer</span><span class="p">(</span><span class="n">ast</span><span class="p">.</span><span class="n">NodeTransformer</span><span class="p">):</span>
</code></pre></div>
<p>For a start, we rewrite statements like <code class="language-plaintext highlighter-rouge">assert cookie, "Want
cookie!"</code> into <code class="language-plaintext highlighter-rouge">if not cookie: raise AssertionError("Want cookie!")</code><sup id="fnref:5"><a class="footnote" href="https://codewords.recurse.com/feed.xml#fn:5">5</a></sup>.
(Rather, into an if-then-else with the <code class="language-plaintext highlighter-rouge">raise</code> in the <code class="language-plaintext highlighter-rouge">else</code>
clause: this is slightly simpler.)</p>
<div class="highlight"><pre><code class="language-python"> <span class="k">def</span> <span class="nf">visit_Assert</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="n">t</span> <span class="o">=</span> <span class="bp">self</span><span class="p">.</span><span class="n">generic_visit</span><span class="p">(</span><span class="n">t</span><span class="p">)</span>
<span class="n">result</span> <span class="o">=</span> <span class="n">ast</span><span class="p">.</span><span class="n">If</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">test</span><span class="p">,</span>
<span class="p">[],</span>
<span class="p">[</span><span class="n">ast</span><span class="p">.</span><span class="n">Raise</span><span class="p">(</span><span class="n">Call</span><span class="p">(</span><span class="n">ast</span><span class="p">.</span><span class="n">Name</span><span class="p">(</span><span class="s">'AssertionError'</span><span class="p">,</span> <span class="n">load</span><span class="p">),</span>
<span class="p">[]</span> <span class="k">if</span> <span class="n">t</span><span class="p">.</span><span class="n">msg</span> <span class="ow">is</span> <span class="bp">None</span> <span class="k">else</span> <span class="p">[</span><span class="n">t</span><span class="p">.</span><span class="n">msg</span><span class="p">]),</span>
<span class="bp">None</span><span class="p">)])</span>
<span class="k">return</span> <span class="n">ast</span><span class="p">.</span><span class="n">copy_location</span><span class="p">(</span><span class="n">result</span><span class="p">,</span> <span class="n">t</span><span class="p">)</span>
</code></pre></div>
<p><code class="language-plaintext highlighter-rouge">generic_visit</code> visits and replaces the children of <code class="language-plaintext highlighter-rouge">t</code>, as mentioned
above. <code class="language-plaintext highlighter-rouge">ast.copy_location</code> interpolates a source-line number for any
new nodes introduced.</p>
<p>What was the point of this visitor? Without it, we’d need to define a
<code class="language-plaintext highlighter-rouge">visit_Assert</code> in the code generator instead—OK, fine. This would
then need to generate code to perform a test, a call, and a raise. To
do this without duplicating logic within the compiler, we’d define
code-generation functions for each of those, to be invoked by both the
new <code class="language-plaintext highlighter-rouge">visit_Assert</code> and by the code generator’s <code class="language-plaintext highlighter-rouge">visit_If</code>,
<code class="language-plaintext highlighter-rouge">visit_Raise</code>, and so on. That’s not onerous, but if we’re desugaring
at all, this is a good use for it: it’s easier and clearer.</p>
<p>Lambda expressions and function definitions get rewritten in terms of
a new AST node type we’ll define, called <code class="language-plaintext highlighter-rouge">Function</code>:</p>
<div class="highlight"><pre><code class="language-python"> <span class="k">def</span> <span class="nf">visit_Lambda</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="n">t</span> <span class="o">=</span> <span class="bp">self</span><span class="p">.</span><span class="n">generic_visit</span><span class="p">(</span><span class="n">t</span><span class="p">)</span>
<span class="n">result</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'<lambda>'</span><span class="p">,</span> <span class="n">t</span><span class="p">.</span><span class="n">args</span><span class="p">,</span> <span class="p">[</span><span class="n">ast</span><span class="p">.</span><span class="n">Return</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">body</span><span class="p">)])</span>
<span class="k">return</span> <span class="n">ast</span><span class="p">.</span><span class="n">copy_location</span><span class="p">(</span><span class="n">result</span><span class="p">,</span> <span class="n">t</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">visit_FunctionDef</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="n">t</span> <span class="o">=</span> <span class="bp">self</span><span class="p">.</span><span class="n">generic_visit</span><span class="p">(</span><span class="n">t</span><span class="p">)</span>
<span class="n">fn</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">name</span><span class="p">,</span> <span class="n">t</span><span class="p">.</span><span class="n">args</span><span class="p">,</span> <span class="n">t</span><span class="p">.</span><span class="n">body</span><span class="p">)</span>
<span class="k">for</span> <span class="n">d</span> <span class="ow">in</span> <span class="nb">reversed</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">decorator_list</span><span class="p">):</span>
<span class="n">fn</span> <span class="o">=</span> <span class="n">Call</span><span class="p">(</span><span class="n">d</span><span class="p">,</span> <span class="p">[</span><span class="n">fn</span><span class="p">])</span>
<span class="n">result</span> <span class="o">=</span> <span class="n">ast</span><span class="p">.</span><span class="n">Assign</span><span class="p">([</span><span class="n">ast</span><span class="p">.</span><span class="n">Name</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">name</span><span class="p">,</span> <span class="n">store</span><span class="p">)],</span> <span class="n">fn</span><span class="p">)</span>
<span class="k">return</span> <span class="n">ast</span><span class="p">.</span><span class="n">copy_location</span><span class="p">(</span><span class="n">result</span><span class="p">,</span> <span class="n">t</span><span class="p">)</span>
</code></pre></div>
<p>This is as if we turned <code class="language-plaintext highlighter-rouge">def answer(): return 42</code> into <code class="language-plaintext highlighter-rouge">answer =
lambda: 42</code>, except that a lambda expression can’t carry a
name. Reducing to just one type of function node will save work not
just in code generation but in scope analysis too, and give us a
simpler expansion for list comprehensions. As a bonus, adding a new node
type to the language feels like getting away with something.</p>
<p>(The last lines, implementing function decorators, could be left
out since Tailbiter doesn’t use decorators.)</p>
<p>List comprehensions also create a <code class="language-plaintext highlighter-rouge">Function</code> node, holding the loop,
because the loop variables must be defined in their own scope, not
polluting the current scope as they did in Python 2.</p>
<div class="highlight"><pre><code class="language-python"> <span class="k">def</span> <span class="nf">visit_ListComp</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="n">t</span> <span class="o">=</span> <span class="bp">self</span><span class="p">.</span><span class="n">generic_visit</span><span class="p">(</span><span class="n">t</span><span class="p">)</span>
<span class="n">add_element</span> <span class="o">=</span> <span class="n">ast</span><span class="p">.</span><span class="n">Attribute</span><span class="p">(</span><span class="n">ast</span><span class="p">.</span><span class="n">Name</span><span class="p">(</span><span class="s">'.elements'</span><span class="p">,</span> <span class="n">load</span><span class="p">),</span> <span class="s">'append'</span><span class="p">,</span> <span class="n">load</span><span class="p">)</span>
<span class="n">body</span> <span class="o">=</span> <span class="n">ast</span><span class="p">.</span><span class="n">Expr</span><span class="p">(</span><span class="n">Call</span><span class="p">(</span><span class="n">add_element</span><span class="p">,</span> <span class="p">[</span><span class="n">t</span><span class="p">.</span><span class="n">elt</span><span class="p">]))</span>
<span class="k">for</span> <span class="n">loop</span> <span class="ow">in</span> <span class="nb">reversed</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">generators</span><span class="p">):</span>
<span class="k">for</span> <span class="n">test</span> <span class="ow">in</span> <span class="nb">reversed</span><span class="p">(</span><span class="n">loop</span><span class="p">.</span><span class="n">ifs</span><span class="p">):</span>
<span class="n">body</span> <span class="o">=</span> <span class="n">ast</span><span class="p">.</span><span class="n">If</span><span class="p">(</span><span class="n">test</span><span class="p">,</span> <span class="p">[</span><span class="n">body</span><span class="p">],</span> <span class="p">[])</span>
<span class="n">body</span> <span class="o">=</span> <span class="n">ast</span><span class="p">.</span><span class="n">For</span><span class="p">(</span><span class="n">loop</span><span class="p">.</span><span class="n">target</span><span class="p">,</span> <span class="n">loop</span><span class="p">.</span><span class="nb">iter</span><span class="p">,</span> <span class="p">[</span><span class="n">body</span><span class="p">],</span> <span class="p">[])</span>
<span class="n">fn</span> <span class="o">=</span> <span class="p">[</span><span class="n">body</span><span class="p">,</span>
<span class="n">ast</span><span class="p">.</span><span class="n">Return</span><span class="p">(</span><span class="n">ast</span><span class="p">.</span><span class="n">Name</span><span class="p">(</span><span class="s">'.elements'</span><span class="p">,</span> <span class="n">load</span><span class="p">))]</span>
<span class="n">args</span> <span class="o">=</span> <span class="n">ast</span><span class="p">.</span><span class="n">arguments</span><span class="p">([</span><span class="n">ast</span><span class="p">.</span><span class="n">arg</span><span class="p">(</span><span class="s">'.elements'</span><span class="p">,</span> <span class="bp">None</span><span class="p">)],</span> <span class="bp">None</span><span class="p">,</span> <span class="p">[],</span> <span class="bp">None</span><span class="p">,</span> <span class="p">[],</span> <span class="p">[])</span>
<span class="n">result</span> <span class="o">=</span> <span class="n">Call</span><span class="p">(</span><span class="n">Function</span><span class="p">(</span><span class="s">'<listcomp>'</span><span class="p">,</span> <span class="n">args</span><span class="p">,</span> <span class="n">fn</span><span class="p">),</span>
<span class="p">[</span><span class="n">ast</span><span class="p">.</span><span class="n">List</span><span class="p">([],</span> <span class="n">load</span><span class="p">)])</span>
<span class="k">return</span> <span class="n">ast</span><span class="p">.</span><span class="n">copy_location</span><span class="p">(</span><span class="n">result</span><span class="p">,</span> <span class="n">t</span><span class="p">)</span>
</code></pre></div>
<p>For instance, <code class="language-plaintext highlighter-rouge">[n for n in numbers if n]</code> becomes a call to a
locally-defined function almost like below:</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in example.py:
</span><span class="k">def</span> <span class="nf">listcomp</span><span class="p">(</span><span class="n">elements</span><span class="p">)</span>
<span class="k">for</span> <span class="n">n</span> <span class="ow">in</span> <span class="n">numbers</span><span class="p">:</span>
<span class="k">if</span> <span class="n">n</span><span class="p">:</span>
<span class="n">elements</span><span class="p">.</span><span class="n">append</span><span class="p">(</span><span class="n">n</span><span class="p">)</span>
<span class="k">return</span> <span class="n">elements</span>
</code></pre></div>
<p><code class="language-plaintext highlighter-rouge">elements</code> gets its starting value, a new <code class="language-plaintext highlighter-rouge">[]</code>, from the call to the
local function. The actual tree we generate can’t quite be written as
Python source: the function called <code class="language-plaintext highlighter-rouge">listcomp</code> above is actually
anonymous (the name <code class="language-plaintext highlighter-rouge"><listcomp></code> will appear only as the name of the
code object, not as a Python variable), and <code class="language-plaintext highlighter-rouge">elements</code> gets named
<code class="language-plaintext highlighter-rouge">.elements</code>, a name which can’t occur in real Python source code and
thus can’t clash with variables from the source.</p>
<p>CPython generates more-efficient bytecode directly from the
comprehension, in a hairier way.</p>
<p>We round out <code class="language-plaintext highlighter-rouge">Desugarer</code> with a few helpers:</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in compile to code v2:
</span><span class="k">class</span> <span class="nc">Function</span><span class="p">(</span><span class="n">ast</span><span class="p">.</span><span class="n">FunctionDef</span><span class="p">):</span>
<span class="n">_fields</span> <span class="o">=</span> <span class="p">(</span><span class="s">'name'</span><span class="p">,</span> <span class="s">'args'</span><span class="p">,</span> <span class="s">'body'</span><span class="p">)</span>
<span class="n">load</span><span class="p">,</span> <span class="n">store</span> <span class="o">=</span> <span class="n">ast</span><span class="p">.</span><span class="n">Load</span><span class="p">(),</span> <span class="n">ast</span><span class="p">.</span><span class="n">Store</span><span class="p">()</span>
<span class="k">def</span> <span class="nf">Call</span><span class="p">(</span><span class="n">fn</span><span class="p">,</span> <span class="n">args</span><span class="p">):</span>
<span class="k">return</span> <span class="n">ast</span><span class="p">.</span><span class="n">Call</span><span class="p">(</span><span class="n">fn</span><span class="p">,</span> <span class="n">args</span><span class="p">,</span> <span class="p">[],</span> <span class="bp">None</span><span class="p">,</span> <span class="bp">None</span><span class="p">)</span>
</code></pre></div>
<p>(<code class="language-plaintext highlighter-rouge">Function</code> derives from <code class="language-plaintext highlighter-rouge">FunctionDef</code> so that
<code class="language-plaintext highlighter-rouge">ast.get_docstring</code> will work on it.)</p>
<h3 id="variables-live-in-nested-scopes">Variables live in nested scopes</h3>
<p>Functions and classes introduce a new complication: local and nonlocal
variables. Consider:</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in example.py:
</span><span class="k">def</span> <span class="nf">a_function</span><span class="p">():</span>
<span class="n">f1</span> <span class="o">=</span> <span class="s">"I'm a fast one."</span>
<span class="k">def</span> <span class="nf">f2</span><span class="p">():</span> <span class="k">return</span> <span class="n">d</span>
<span class="n">d</span> <span class="o">=</span> <span class="s">"I'm a deref."</span>
<span class="k">return</span> <span class="n">a_global_var</span><span class="p">,</span> <span class="n">f1</span><span class="p">,</span> <span class="n">f2</span><span class="p">,</span> <span class="n">d</span>
</code></pre></div>
<p><code class="language-plaintext highlighter-rouge">f1</code> is a local variable used only locally within <code class="language-plaintext highlighter-rouge">a_function</code>. The
interpreter has special support for variables like this: for
efficiency their values live in an array instead of a general
dictionary structure. (Each call to the function gets a fresh new
array.) Once our <code class="language-plaintext highlighter-rouge">scope</code>
determines this, our revised code generator can emit <code class="language-plaintext highlighter-rouge">LOAD_FAST</code> or
<code class="language-plaintext highlighter-rouge">STORE_FAST</code> to access the variable at a known position in the array:</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in generate variable accesses v2:
</span> <span class="k">def</span> <span class="nf">load</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">name</span><span class="p">):</span>
<span class="n">access</span> <span class="o">=</span> <span class="bp">self</span><span class="p">.</span><span class="n">scope</span><span class="p">.</span><span class="n">access</span><span class="p">(</span><span class="n">name</span><span class="p">)</span>
<span class="k">if</span> <span class="n">access</span> <span class="o">==</span> <span class="s">'fast'</span><span class="p">:</span> <span class="k">return</span> <span class="n">op</span><span class="p">.</span><span class="n">LOAD_FAST</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">varnames</span><span class="p">[</span><span class="n">name</span><span class="p">])</span>
<span class="k">elif</span> <span class="n">access</span> <span class="o">==</span> <span class="s">'name'</span><span class="p">:</span> <span class="k">return</span> <span class="n">op</span><span class="p">.</span><span class="n">LOAD_NAME</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">names</span><span class="p">[</span><span class="n">name</span><span class="p">])</span>
<span class="k">elif</span> <span class="n">access</span> <span class="o">==</span> <span class="s">'deref'</span><span class="p">:</span> <span class="k">return</span> <span class="n">op</span><span class="p">.</span><span class="n">LOAD_DEREF</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">cell_index</span><span class="p">(</span><span class="n">name</span><span class="p">))</span>
<span class="k">else</span><span class="p">:</span> <span class="k">assert</span> <span class="bp">False</span>
<span class="k">def</span> <span class="nf">store</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">name</span><span class="p">):</span>
<span class="n">access</span> <span class="o">=</span> <span class="bp">self</span><span class="p">.</span><span class="n">scope</span><span class="p">.</span><span class="n">access</span><span class="p">(</span><span class="n">name</span><span class="p">)</span>
<span class="k">if</span> <span class="n">access</span> <span class="o">==</span> <span class="s">'fast'</span><span class="p">:</span> <span class="k">return</span> <span class="n">op</span><span class="p">.</span><span class="n">STORE_FAST</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">varnames</span><span class="p">[</span><span class="n">name</span><span class="p">])</span>
<span class="k">elif</span> <span class="n">access</span> <span class="o">==</span> <span class="s">'name'</span><span class="p">:</span> <span class="k">return</span> <span class="n">op</span><span class="p">.</span><span class="n">STORE_NAME</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">names</span><span class="p">[</span><span class="n">name</span><span class="p">])</span>
<span class="k">elif</span> <span class="n">access</span> <span class="o">==</span> <span class="s">'deref'</span><span class="p">:</span> <span class="k">return</span> <span class="n">op</span><span class="p">.</span><span class="n">STORE_DEREF</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">cell_index</span><span class="p">(</span><span class="n">name</span><span class="p">))</span>
<span class="k">else</span><span class="p">:</span> <span class="k">assert</span> <span class="bp">False</span>
<span class="k">def</span> <span class="nf">cell_index</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">name</span><span class="p">):</span>
<span class="k">return</span> <span class="bp">self</span><span class="p">.</span><span class="n">scope</span><span class="p">.</span><span class="n">derefvars</span><span class="p">.</span><span class="n">index</span><span class="p">(</span><span class="n">name</span><span class="p">)</span>
</code></pre></div>
<p>Recall that <code class="language-plaintext highlighter-rouge">self.varnames</code> maps from local variable names to their
positions in the list of such names; the interpreter will know
to build an environment of the right size because we included this
information in the compiled function’s code object, in <code class="language-plaintext highlighter-rouge">make_code</code>.</p>
<p>What about the other variables in this example? <code class="language-plaintext highlighter-rouge">f2</code> is local like
<code class="language-plaintext highlighter-rouge">f1</code>. (We’ll come back soon to consider the function it names.)
<code class="language-plaintext highlighter-rouge">a_global_var</code> is global, getting looked up by name at runtime: it has
access type <code class="language-plaintext highlighter-rouge">'name'</code>, above. CPython’s compiler can use a fourth access
type, <code class="language-plaintext highlighter-rouge">'global'</code>, as an optimization: the <code class="language-plaintext highlighter-rouge">LOAD_GLOBAL</code> instruction
looks up the variable name directly in the module’s global
environment, but <code class="language-plaintext highlighter-rouge">LOAD_NAME</code>, which we use instead, first checks the local
environment. We do it this way because Python will need the <code class="language-plaintext highlighter-rouge">'name'</code>
access type for the variables in class definitions, as we’ll see, and
it’s simplest to use the same type for both.</p>
<p>Finally, there are <code class="language-plaintext highlighter-rouge">'deref'</code> variables like <code class="language-plaintext highlighter-rouge">d</code>, which is not global,
yet “less local” than <code class="language-plaintext highlighter-rouge">f1</code> in that it’s also used from another scope,
the body of <code class="language-plaintext highlighter-rouge">f2</code>. Pretend for a moment as if Python didn’t support
nonlocal variables. We’d have to transform our example to use only
locals and globals, like</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in example.py:
</span><span class="k">def</span> <span class="nf">a_function</span><span class="p">():</span>
<span class="n">d</span> <span class="o">=</span> <span class="n">Cell</span><span class="p">()</span>
<span class="n">f1</span> <span class="o">=</span> <span class="s">"I'm a fast one."</span>
<span class="k">def</span> <span class="nf">f2</span><span class="p">(</span><span class="n">d</span><span class="o">=</span><span class="n">d</span><span class="p">):</span> <span class="k">return</span> <span class="n">d</span><span class="p">.</span><span class="n">contents</span>
<span class="n">d</span><span class="p">.</span><span class="n">contents</span> <span class="o">=</span> <span class="s">"I'm a deref."</span>
<span class="k">return</span> <span class="n">a_global_var</span><span class="p">,</span> <span class="n">f1</span><span class="p">,</span> <span class="n">f2</span><span class="p">,</span> <span class="n">d</span><span class="p">.</span><span class="n">contents</span>
<span class="k">class</span> <span class="nc">Cell</span><span class="p">:</span> <span class="k">pass</span>
</code></pre></div>
<p><code class="language-plaintext highlighter-rouge">d</code> is now tightly local in each of its scopes, and the <code class="language-plaintext highlighter-rouge">d</code>
inside <code class="language-plaintext highlighter-rouge">f2</code> is explicitly passed into <code class="language-plaintext highlighter-rouge">f2</code> from the enclosing scope.
<code class="language-plaintext highlighter-rouge">d</code> no longer refers directly to the value <code class="language-plaintext highlighter-rouge">"I'm a deref."</code>, it refers
to a data structure, the <code class="language-plaintext highlighter-rouge">Cell</code>, whose <em>contents</em> is the value. This
indirection makes it possible to pass <code class="language-plaintext highlighter-rouge">d</code> into <code class="language-plaintext highlighter-rouge">f2</code> before we’ve
assigned its contents. For this to work we had to transform each use
of <code class="language-plaintext highlighter-rouge">d</code> into <code class="language-plaintext highlighter-rouge">d.contents</code>. We also had to create the cell first, before
the transformed code.</p>
<p>So, one way to compile our example would be to rewrite it in just this
way using a <code class="language-plaintext highlighter-rouge">NodeTransformer</code> like the desugarer, then continue,
knowing that all the scopes now are “flat”. But we won’t, because the virtual
machine was designed to be compiled to directly, with built-in support
for a data type similar to our notional <code class="language-plaintext highlighter-rouge">Cell</code> class. Each code object
will get a tuple of its cell variable names (such as <code class="language-plaintext highlighter-rouge">d</code> in <code class="language-plaintext highlighter-rouge">a_function</code>);
before the interpreter starts running a function, it will
automatically create the cells; there are <code class="language-plaintext highlighter-rouge">LOAD_DEREF</code> and
<code class="language-plaintext highlighter-rouge">STORE_DEREF</code> instructions corresponding to our uses of <code class="language-plaintext highlighter-rouge">d.contents</code>;
and finally, as we’ll see, the instruction to create a function can
take a tuple of cells as an argument, corresponding to our <code class="language-plaintext highlighter-rouge">d=d</code>. The
upshot is that we can compile the body of a function just as we’ve been
compiling module-scope code, except we’ll need to distinguish the
<code class="language-plaintext highlighter-rouge">'deref'</code> variables like <code class="language-plaintext highlighter-rouge">d</code> from the <code class="language-plaintext highlighter-rouge">'fast'</code> and <code class="language-plaintext highlighter-rouge">'name'</code> variables.</p>
<p>There’s one more issue: classes also introduce scopes. Unlike a function
scope, a class scope doesn’t get fast or deref variables—only its
function-type subscopes do, such as its method definitions. The
class’s variables and methods are <code class="language-plaintext highlighter-rouge">'name'</code> variables instead. The
interpreter will, after running the compiled body of the class
definition, just take the resulting dictionary as the data to build
the class object out of.</p>
<p>Tailbiter forbids nested classes, to avoid some of Python’s dark
corners, and likewise forbids <code class="language-plaintext highlighter-rouge">del</code> statements and explicit <code class="language-plaintext highlighter-rouge">nonlocal</code>
and <code class="language-plaintext highlighter-rouge">global</code> declarations.</p>
<h3 id="we-collate-the-variables-and-sub-scopes">We collate the variables and sub-scopes</h3>
<p>Now we know what we need out of our scope objects. We’ll build them in
two passes:</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in compile to code v2:
</span><span class="k">def</span> <span class="nf">top_scope</span><span class="p">(</span><span class="n">t</span><span class="p">):</span>
<span class="n">top</span> <span class="o">=</span> <span class="n">Scope</span><span class="p">(</span><span class="n">t</span><span class="p">,</span> <span class="p">())</span>
<span class="n">top</span><span class="p">.</span><span class="n">visit</span><span class="p">(</span><span class="n">t</span><span class="p">)</span>
<span class="n">top</span><span class="p">.</span><span class="n">analyze</span><span class="p">(</span><span class="nb">set</span><span class="p">())</span>
<span class="k">return</span> <span class="n">top</span>
</code></pre></div>
<p>The first creates subscopes for classes and functions and records the
<em>local</em> uses and definitions of variables. We must walk the AST to
collect this information, another job for an AST visitor. Unlike the
<code class="language-plaintext highlighter-rouge">NodeTransformer</code> last time, we’ll leave the AST alone: our visit
methods should instead fill out attributes of the <code class="language-plaintext highlighter-rouge">Scope</code>. That’s the
protocol for a <code class="language-plaintext highlighter-rouge">NodeVisitor</code>:</p>
<div class="highlight"><pre><code class="language-python"><span class="k">class</span> <span class="nc">Scope</span><span class="p">(</span><span class="n">ast</span><span class="p">.</span><span class="n">NodeVisitor</span><span class="p">):</span>
<span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">,</span> <span class="n">defs</span><span class="p">):</span>
<span class="bp">self</span><span class="p">.</span><span class="n">t</span> <span class="o">=</span> <span class="n">t</span>
<span class="bp">self</span><span class="p">.</span><span class="n">children</span> <span class="o">=</span> <span class="p">{}</span> <span class="c1"># Enclosed sub-scopes
</span> <span class="bp">self</span><span class="p">.</span><span class="n">defs</span> <span class="o">=</span> <span class="nb">set</span><span class="p">(</span><span class="n">defs</span><span class="p">)</span> <span class="c1"># Variables defined
</span> <span class="bp">self</span><span class="p">.</span><span class="n">uses</span> <span class="o">=</span> <span class="nb">set</span><span class="p">()</span> <span class="c1"># Variables referenced
</span>
<span class="k">def</span> <span class="nf">visit_ClassDef</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="bp">self</span><span class="p">.</span><span class="n">defs</span><span class="p">.</span><span class="n">add</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">name</span><span class="p">)</span>
<span class="k">for</span> <span class="n">expr</span> <span class="ow">in</span> <span class="n">t</span><span class="p">.</span><span class="n">bases</span><span class="p">:</span> <span class="bp">self</span><span class="p">.</span><span class="n">visit</span><span class="p">(</span><span class="n">expr</span><span class="p">)</span>
<span class="n">subscope</span> <span class="o">=</span> <span class="n">Scope</span><span class="p">(</span><span class="n">t</span><span class="p">,</span> <span class="p">())</span>
<span class="bp">self</span><span class="p">.</span><span class="n">children</span><span class="p">[</span><span class="n">t</span><span class="p">]</span> <span class="o">=</span> <span class="n">subscope</span>
<span class="k">for</span> <span class="n">stmt</span> <span class="ow">in</span> <span class="n">t</span><span class="p">.</span><span class="n">body</span><span class="p">:</span> <span class="n">subscope</span><span class="p">.</span><span class="n">visit</span><span class="p">(</span><span class="n">stmt</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">visit_Function</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="n">subscope</span> <span class="o">=</span> <span class="n">Scope</span><span class="p">(</span><span class="n">t</span><span class="p">,</span> <span class="p">[</span><span class="n">arg</span><span class="p">.</span><span class="n">arg</span> <span class="k">for</span> <span class="n">arg</span> <span class="ow">in</span> <span class="n">t</span><span class="p">.</span><span class="n">args</span><span class="p">.</span><span class="n">args</span><span class="p">])</span>
<span class="bp">self</span><span class="p">.</span><span class="n">children</span><span class="p">[</span><span class="n">t</span><span class="p">]</span> <span class="o">=</span> <span class="n">subscope</span>
<span class="k">for</span> <span class="n">stmt</span> <span class="ow">in</span> <span class="n">t</span><span class="p">.</span><span class="n">body</span><span class="p">:</span> <span class="n">subscope</span><span class="p">.</span><span class="n">visit</span><span class="p">(</span><span class="n">stmt</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">visit_Import</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">for</span> <span class="n">alias</span> <span class="ow">in</span> <span class="n">t</span><span class="p">.</span><span class="n">names</span><span class="p">:</span>
<span class="bp">self</span><span class="p">.</span><span class="n">defs</span><span class="p">.</span><span class="n">add</span><span class="p">(</span><span class="n">alias</span><span class="p">.</span><span class="n">asname</span> <span class="ow">or</span> <span class="n">alias</span><span class="p">.</span><span class="n">name</span><span class="p">.</span><span class="n">split</span><span class="p">(</span><span class="s">'.'</span><span class="p">)[</span><span class="mi">0</span><span class="p">])</span>
<span class="k">def</span> <span class="nf">visit_ImportFrom</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">for</span> <span class="n">alias</span> <span class="ow">in</span> <span class="n">t</span><span class="p">.</span><span class="n">names</span><span class="p">:</span>
<span class="bp">self</span><span class="p">.</span><span class="n">defs</span><span class="p">.</span><span class="n">add</span><span class="p">(</span><span class="n">alias</span><span class="p">.</span><span class="n">asname</span> <span class="ow">or</span> <span class="n">alias</span><span class="p">.</span><span class="n">name</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">visit_Name</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">ctx</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">Load</span><span class="p">):</span> <span class="bp">self</span><span class="p">.</span><span class="n">uses</span><span class="p">.</span><span class="n">add</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="nb">id</span><span class="p">)</span>
<span class="k">elif</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">ctx</span><span class="p">,</span> <span class="n">ast</span><span class="p">.</span><span class="n">Store</span><span class="p">):</span> <span class="bp">self</span><span class="p">.</span><span class="n">defs</span><span class="p">.</span><span class="n">add</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="nb">id</span><span class="p">)</span>
<span class="k">else</span><span class="p">:</span> <span class="k">assert</span> <span class="bp">False</span>
</code></pre></div>
<p>There’s a visit action for each type of AST node that either introduces
a subscope (<code class="language-plaintext highlighter-rouge">ClassDef</code> and <code class="language-plaintext highlighter-rouge">Function</code>) or references a variable (the
rest). The variable references get collected into two sets, of
definitions and uses.</p>
<p>With this information, the <code class="language-plaintext highlighter-rouge">analyze</code> pass can then deduce the <em>non</em>local uses of
variables. It walks down accumulating the definitions from enclosing
function scopes, then back up accumulating the references from enclosed ones:</p>
<div class="highlight"><pre><code class="language-python"> <span class="k">def</span> <span class="nf">analyze</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">parent_defs</span><span class="p">):</span>
<span class="bp">self</span><span class="p">.</span><span class="n">fastvars</span> <span class="o">=</span> <span class="bp">self</span><span class="p">.</span><span class="n">defs</span> <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">t</span><span class="p">,</span> <span class="n">Function</span><span class="p">)</span> <span class="k">else</span> <span class="nb">set</span><span class="p">()</span>
<span class="k">for</span> <span class="n">child</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">.</span><span class="n">children</span><span class="p">.</span><span class="n">values</span><span class="p">():</span>
<span class="n">child</span><span class="p">.</span><span class="n">analyze</span><span class="p">(</span><span class="n">parent_defs</span> <span class="o">|</span> <span class="bp">self</span><span class="p">.</span><span class="n">fastvars</span><span class="p">)</span>
<span class="n">child_uses</span> <span class="o">=</span> <span class="nb">set</span><span class="p">([</span><span class="n">var</span> <span class="k">for</span> <span class="n">child</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">.</span><span class="n">children</span><span class="p">.</span><span class="n">values</span><span class="p">()</span>
<span class="k">for</span> <span class="n">var</span> <span class="ow">in</span> <span class="n">child</span><span class="p">.</span><span class="n">freevars</span><span class="p">])</span>
<span class="n">uses</span> <span class="o">=</span> <span class="bp">self</span><span class="p">.</span><span class="n">uses</span> <span class="o">|</span> <span class="n">child_uses</span>
<span class="bp">self</span><span class="p">.</span><span class="n">cellvars</span> <span class="o">=</span> <span class="nb">tuple</span><span class="p">(</span><span class="n">child_uses</span> <span class="o">&</span> <span class="bp">self</span><span class="p">.</span><span class="n">fastvars</span><span class="p">)</span>
<span class="bp">self</span><span class="p">.</span><span class="n">freevars</span> <span class="o">=</span> <span class="nb">tuple</span><span class="p">(</span><span class="n">uses</span> <span class="o">&</span> <span class="p">(</span><span class="n">parent_defs</span> <span class="o">-</span> <span class="bp">self</span><span class="p">.</span><span class="n">fastvars</span><span class="p">))</span>
<span class="bp">self</span><span class="p">.</span><span class="n">derefvars</span> <span class="o">=</span> <span class="bp">self</span><span class="p">.</span><span class="n">cellvars</span> <span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">freevars</span>
</code></pre></div>
<p>A “cell variable” is a deref defined in the current scope; a “free
variable” comes from an enclosing scope instead. In our
example, <code class="language-plaintext highlighter-rouge">d</code> is a free variable in the lambda expression but a cell
variable in the rest of <code class="language-plaintext highlighter-rouge">a_function</code>. The code generator will need to
know about free variables in order to compile the creation of function
objects.</p>
<p>The code generator uses <code class="language-plaintext highlighter-rouge">cellvars</code> and <code class="language-plaintext highlighter-rouge">freevars</code>, plus this method:</p>
<div class="highlight"><pre><code class="language-python"> <span class="k">def</span> <span class="nf">access</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">name</span><span class="p">):</span>
<span class="k">return</span> <span class="p">(</span><span class="s">'deref'</span> <span class="k">if</span> <span class="n">name</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">.</span><span class="n">derefvars</span> <span class="k">else</span>
<span class="s">'fast'</span> <span class="k">if</span> <span class="n">name</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">.</span><span class="n">fastvars</span> <span class="k">else</span>
<span class="s">'name'</span><span class="p">)</span>
</code></pre></div>
<p>Does scope analysis need to precede code generation? If we turned it
around, first the code generator would generate a version of symbolic assembly with
named variables, then we’d analyze the uses of variables in the <em>assembly</em> code,
and finally emit bytecode, treating some of the <code class="language-plaintext highlighter-rouge">LOAD_NAME</code>s as
<code class="language-plaintext highlighter-rouge">LOAD_FAST</code>, etc. This could be more useful as part of a bytecode
rewriting system—for disassembling, transforming, and reassembling, it’d
be nice to be able to transform without worrying about the mechanics of cell and
free variables—and it might take roughly the same amount of
logic. In varying from CPython’s approach, though, it’s riskier.</p>
<h3 id="we-generate-code-for-functions">We generate code for functions</h3>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in CodeGen v2:
</span> <span class="k">def</span> <span class="nf">visit_Return</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">return</span> <span class="p">((</span><span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">value</span><span class="p">)</span> <span class="k">if</span> <span class="n">t</span><span class="p">.</span><span class="n">value</span> <span class="k">else</span> <span class="bp">self</span><span class="p">.</span><span class="n">load_const</span><span class="p">(</span><span class="bp">None</span><span class="p">))</span>
<span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">RETURN_VALUE</span><span class="p">)</span>
</code></pre></div>
<p>We handle both <code class="language-plaintext highlighter-rouge">return foo</code> and the no-argument <code class="language-plaintext highlighter-rouge">return</code>. (The latter
is never used by this compiler.)</p>
<p>A <code class="language-plaintext highlighter-rouge">Function</code> node is an expression desugared from a lambda expression,
function definition, or list comprehension. Compiling one takes two
steps: first, compile its whole body into a separate code
object. Second, generate assembly code that will build a function
object out of this code object.</p>
<div class="highlight"><pre><code class="language-python"> <span class="k">def</span> <span class="nf">visit_Function</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="n">code</span> <span class="o">=</span> <span class="bp">self</span><span class="p">.</span><span class="n">sprout</span><span class="p">(</span><span class="n">t</span><span class="p">).</span><span class="n">compile_function</span><span class="p">(</span><span class="n">t</span><span class="p">)</span>
<span class="k">return</span> <span class="bp">self</span><span class="p">.</span><span class="n">make_closure</span><span class="p">(</span><span class="n">code</span><span class="p">,</span> <span class="n">t</span><span class="p">.</span><span class="n">name</span><span class="p">)</span>
</code></pre></div>
<p>The new <code class="language-plaintext highlighter-rouge">CodeGen</code> for this new code object requires a subscope of the
current scope—previously computed by the scope analyzer, now recovered
by <code class="language-plaintext highlighter-rouge">self.scope.children[t]</code>.</p>
<div class="highlight"><pre><code class="language-python"> <span class="k">def</span> <span class="nf">sprout</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="k">return</span> <span class="n">CodeGen</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">filename</span><span class="p">,</span> <span class="bp">self</span><span class="p">.</span><span class="n">scope</span><span class="p">.</span><span class="n">children</span><span class="p">[</span><span class="n">t</span><span class="p">])</span>
</code></pre></div>
<p>Building a function out of a code object depends on whether it has
free variables. <code class="language-plaintext highlighter-rouge">lambda x: lambda y: x + y</code> compiles to</p>
<div class="highlight"><pre><code># in examples:
0 LOAD_CONST 1 (<code object <lambda> at ...)
3 LOAD_CONST 2 ('<lambda>')
6 MAKE_FUNCTION 0
</code></pre></div>
<p>where the first constant is the code object for <code class="language-plaintext highlighter-rouge">lambda y: x +
y</code>, whose code in turn should be</p>
<div class="highlight"><pre><code> 0 LOAD_CLOSURE 0 (x)
3 BUILD_TUPLE 1
6 LOAD_CONST 1 (<code object <lambda> at ...)
9 LOAD_CONST 2 ('<lambda>')
12 MAKE_CLOSURE 0
15 RETURN_VALUE
</code></pre></div>
<p>The code object loaded by the instruction at 6 (and not shown here)
finally does the actual adding of <code class="language-plaintext highlighter-rouge">x</code> and <code class="language-plaintext highlighter-rouge">y</code>.</p>
<p>The outer lambda, with no free variables, becomes a <code class="language-plaintext highlighter-rouge">MAKE_FUNCTION</code>;
the inner one becomes a <code class="language-plaintext highlighter-rouge">MAKE_CLOSURE</code> passed a tuple of deref
cells. (<code class="language-plaintext highlighter-rouge">LOAD_CLOSURE</code> will load <code class="language-plaintext highlighter-rouge">x</code>’s <em>cell</em>, instead of the
contents of the cell as <code class="language-plaintext highlighter-rouge">LOAD_DEREF</code> would do. The scope analyzer
already arranged for the needed cells to be among the current scope’s
<code class="language-plaintext highlighter-rouge">cellvars</code>.) The second <code class="language-plaintext highlighter-rouge">LOAD_CONST</code> in either case loads the name of
the new function. (In “real” Python the nested lambda’s name would be
<code class="language-plaintext highlighter-rouge"><lambda>.<locals>.<lambda></code>, reflecting the nesting.)</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in CodeGen v2:
</span> <span class="k">def</span> <span class="nf">make_closure</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">code</span><span class="p">,</span> <span class="n">name</span><span class="p">):</span>
<span class="k">if</span> <span class="n">code</span><span class="p">.</span><span class="n">co_freevars</span><span class="p">:</span>
<span class="k">return</span> <span class="p">(</span><span class="n">concat</span><span class="p">([</span><span class="n">op</span><span class="p">.</span><span class="n">LOAD_CLOSURE</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">cell_index</span><span class="p">(</span><span class="n">freevar</span><span class="p">))</span>
<span class="k">for</span> <span class="n">freevar</span> <span class="ow">in</span> <span class="n">code</span><span class="p">.</span><span class="n">co_freevars</span><span class="p">])</span>
<span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">BUILD_TUPLE</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">code</span><span class="p">.</span><span class="n">co_freevars</span><span class="p">))</span>
<span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">load_const</span><span class="p">(</span><span class="n">code</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">load_const</span><span class="p">(</span><span class="n">name</span><span class="p">)</span>
<span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">MAKE_CLOSURE</span><span class="p">(</span><span class="mi">0</span><span class="p">))</span>
<span class="k">else</span><span class="p">:</span>
<span class="k">return</span> <span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">load_const</span><span class="p">(</span><span class="n">code</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">load_const</span><span class="p">(</span><span class="n">name</span><span class="p">)</span>
<span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">MAKE_FUNCTION</span><span class="p">(</span><span class="mi">0</span><span class="p">))</span>
</code></pre></div>
<p>Recall that <code class="language-plaintext highlighter-rouge">visit_Function</code> wanted a code object for the function in
question. On a new <code class="language-plaintext highlighter-rouge">CodeGen</code> instance, it called <code class="language-plaintext highlighter-rouge">compile_function</code>:</p>
<div class="highlight"><pre><code class="language-python"> <span class="k">def</span> <span class="nf">compile_function</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="bp">self</span><span class="p">.</span><span class="n">load_const</span><span class="p">(</span><span class="n">ast</span><span class="p">.</span><span class="n">get_docstring</span><span class="p">(</span><span class="n">t</span><span class="p">))</span>
<span class="k">for</span> <span class="n">arg</span> <span class="ow">in</span> <span class="n">t</span><span class="p">.</span><span class="n">args</span><span class="p">.</span><span class="n">args</span><span class="p">:</span>
<span class="bp">self</span><span class="p">.</span><span class="n">varnames</span><span class="p">[</span><span class="n">arg</span><span class="p">.</span><span class="n">arg</span><span class="p">]</span>
<span class="n">assembly</span> <span class="o">=</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">body</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">load_const</span><span class="p">(</span><span class="bp">None</span><span class="p">)</span> <span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">RETURN_VALUE</span>
<span class="k">return</span> <span class="bp">self</span><span class="p">.</span><span class="n">make_code</span><span class="p">(</span><span class="n">assembly</span><span class="p">,</span> <span class="n">t</span><span class="p">.</span><span class="n">name</span><span class="p">,</span> <span class="nb">len</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">args</span><span class="p">.</span><span class="n">args</span><span class="p">))</span>
</code></pre></div>
<p>When CPython wants a function’s docstring, it looks in the code
object’s constants table at the first entry. We put the docstring there,
in the first entry, by calling <code class="language-plaintext highlighter-rouge">load_const</code> with it first, before we
generate any code. (The actual <code class="language-plaintext highlighter-rouge">LOAD_CONST</code> instruction returned is
discarded.) This depends on our table preserving the order that we add
to it.</p>
<p>As with the docstring, the parameter names become the first elements
of the <code class="language-plaintext highlighter-rouge">varnames</code> table. (Remember they’re <code class="language-plaintext highlighter-rouge">defaultdict</code>s: fetching
adds to them as needed.)</p>
<p>We generate assembly that will run the function’s body and return
<code class="language-plaintext highlighter-rouge">None</code> (in case the body had no <code class="language-plaintext highlighter-rouge">return</code> of its own); then we assemble
it all into a code object.</p>
<h3 id="classes-too">Classes too</h3>
<p>Like functions, class definitions sprout a new <code class="language-plaintext highlighter-rouge">CodeGen</code> to compile
down to a code object; but the assembly for building the class
object is a little bit fancier.</p>
<div class="highlight"><pre><code class="language-python"> <span class="k">def</span> <span class="nf">visit_ClassDef</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="n">code</span> <span class="o">=</span> <span class="bp">self</span><span class="p">.</span><span class="n">sprout</span><span class="p">(</span><span class="n">t</span><span class="p">).</span><span class="n">compile_class</span><span class="p">(</span><span class="n">t</span><span class="p">)</span>
<span class="k">return</span> <span class="p">(</span><span class="n">op</span><span class="p">.</span><span class="n">LOAD_BUILD_CLASS</span> <span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">make_closure</span><span class="p">(</span><span class="n">code</span><span class="p">,</span> <span class="n">t</span><span class="p">.</span><span class="n">name</span><span class="p">)</span>
<span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">load_const</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">name</span><span class="p">)</span>
<span class="o">+</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">bases</span><span class="p">)</span>
<span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">CALL_FUNCTION</span><span class="p">(</span><span class="mi">2</span> <span class="o">+</span> <span class="nb">len</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">bases</span><span class="p">))</span>
<span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">store</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">name</span><span class="p">))</span>
</code></pre></div>
<p>The class definition’s code object resembles an ordinary function’s
with some magic local-variable definitions prepended. (The docstring
<em>doesn’t</em> start the constants table, for these.) Python’s class
builder (<code class="language-plaintext highlighter-rouge">LOAD_BUILD_CLASS</code>) will populate the new class’s attributes
from the locals dictionary as of the point this function returns. This again
is why scope analysis must not classify the locals of a class
definition as <code class="language-plaintext highlighter-rouge">'fast'</code>: they need to live in a dictionary, not an array.</p>
<div class="highlight"><pre><code class="language-python"> <span class="k">def</span> <span class="nf">compile_class</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="n">docstring</span> <span class="o">=</span> <span class="n">ast</span><span class="p">.</span><span class="n">get_docstring</span><span class="p">(</span><span class="n">t</span><span class="p">)</span>
<span class="n">assembly</span> <span class="o">=</span> <span class="p">(</span> <span class="bp">self</span><span class="p">.</span><span class="n">load</span><span class="p">(</span><span class="s">'__name__'</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">store</span><span class="p">(</span><span class="s">'__module__'</span><span class="p">)</span>
<span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">load_const</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">name</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">store</span><span class="p">(</span><span class="s">'__qualname__'</span><span class="p">)</span>
<span class="o">+</span> <span class="p">(</span><span class="n">no_op</span> <span class="k">if</span> <span class="n">docstring</span> <span class="ow">is</span> <span class="bp">None</span> <span class="k">else</span>
<span class="bp">self</span><span class="p">.</span><span class="n">load_const</span><span class="p">(</span><span class="n">docstring</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">store</span><span class="p">(</span><span class="s">'__doc__'</span><span class="p">))</span>
<span class="o">+</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">body</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="p">.</span><span class="n">load_const</span><span class="p">(</span><span class="bp">None</span><span class="p">)</span> <span class="o">+</span> <span class="n">op</span><span class="p">.</span><span class="n">RETURN_VALUE</span><span class="p">)</span>
<span class="k">return</span> <span class="bp">self</span><span class="p">.</span><span class="n">make_code</span><span class="p">(</span><span class="n">assembly</span><span class="p">,</span> <span class="n">t</span><span class="p">.</span><span class="n">name</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span>
</code></pre></div>
<p>OK, so! Wind it all up and watch the tail-eating:</p>
<div class="highlight"><pre><code># in transcripts:
$ python3 tailbiter2.py tailbiter2.py tailbiter2.py greet.py
Hi, Chrysophylax
</code></pre></div>
<p>Or try it on a buggy program—i.e., most programs most of the
time—and get a proper traceback.</p>
<h2 id="but-why-compile">But why compile?</h2>
<p>We’ve taken considerable trouble to convert from one fairly-arbitrary
representation to another. After so many mundane details, you might
reasonably ask why you ever thought compilers might be cool. We’ve
cost ourselves not just this work and complexity of translating, but
also of translating <em>back</em>: debuggers and profilers must map what
happens in bytecode to terms meaningful in the source. Why not
interpret programs directly in their first form, the AST?</p>
<p>First, for the compact linear form of bytecode. An AST is fatter and
distributed in memory, interlinked by pointers; the size and the
pointer-chasing both would slow an interpreter down. One core job,
then, was mere rearrangement: taking a data structure (the AST) meant
for arbitrary viewing and changing, and laying it out just right for
the interpreter, who will find each element ready to hand at the moment
it’s needed—like, for us, reading a recipe and starting by laying
the ingredients and pans onto the counter in a sensible order.</p>
<p>Second, to precompute. We analyzed the scopes and how they used
variables, to find, ahead of time, the place in the runtime
environment where a variable will live—letting the interpreter skip
looking up the name.</p>
<p>A third kind of win is possible in rewriting the program as we compile
it—“optimization.” Perhaps the compiler could notice that <code class="language-plaintext highlighter-rouge">[i*2 for
i in range(10)]</code> would go faster as <code class="language-plaintext highlighter-rouge">list(range(0, 20, 2))</code>. This is
precomputation in a broader, open-ended sense (sometimes called the
Full Employment Theorem for Compiler Writers). But isn’t this orthogonal
to translating source to binary? Aren’t there independent source- and
machine-code optimizers? Yes, but a compiler might improve
the target code based on analysis of the <em>source</em>.
An optimizer ignorant of the original source may have much
more trouble understanding the machine code it’s trying to optimize; on the
other hand, a source-to-source optimizer deals in the wrong language
to even express some machine-level optimizations. A compiler can
potentially unite a high-level view with grubby hands.</p>
<p>Well, that sounds compelling. Maybe. But CPython hardly optimizes at all.
(PyPy is another story.) Could we get the first two advantages more easily?
What if we ran the scope analysis
and performed a <em>generic</em> kind of rearrangement: that is,
re-represented the AST in a tight linear form, with the debug info
pushed off to the side? The code generator could look vaguely like</p>
<div class="highlight"><pre><code class="language-python"><span class="c1"># in bluesky.py:
</span><span class="k">def</span> <span class="nf">visit_If</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<span class="n">test</span><span class="p">,</span> <span class="n">body</span><span class="p">,</span> <span class="n">orelse</span> <span class="o">=</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">test</span><span class="p">),</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">body</span><span class="p">),</span> <span class="bp">self</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">orelse</span><span class="p">)</span>
<span class="k">return</span> <span class="p">[</span><span class="n">compact_ast</span><span class="p">.</span><span class="n">IF</span><span class="p">,</span> <span class="nb">len</span><span class="p">(</span><span class="n">test</span><span class="p">),</span> <span class="nb">len</span><span class="p">(</span><span class="n">body</span><span class="p">)]</span> <span class="o">+</span> <span class="n">test</span> <span class="o">+</span> <span class="n">body</span> <span class="o">+</span> <span class="n">orelse</span>
</code></pre></div>
<p>(But instead of writing a lot of stereotyped visitor methods like this
we’d try to derive all the logic automatically from the ASDL
definitions of the AST datatypes.)</p>
<p>With this
“compact AST” you’d point to an AST node’s representation via a
numeric offset into an array such as this method returns: so the
<code class="language-plaintext highlighter-rouge">t.test</code> passed in here becomes a subarray starting at index <code class="language-plaintext highlighter-rouge">3</code>,
<code class="language-plaintext highlighter-rouge">t.body</code> then follows starting from <code class="language-plaintext highlighter-rouge">3+array[1]</code>, and so on. This form
could be nearly as tight as bytecode (once we use bytes and not the
general integers which were quicker to explain), while still viewable
as just another form of AST, making the compiler and surrounding tools
all simpler. In numbers, how much better is the bytecode virtual
machine?</p>
<p>Exploring that question exceeds my scope here—but maybe not yours.</p>
<h2 id="continuations">Continuations</h2>
<p>Where next? Since writing this, I’ve let it grow a little to be able
to compile an interpreter (adapted from <a href="http://aosabook.org/en/500L/a-python-interpreter-written-in-python.html">Byterun</a>) of the CPython bytecodes we emit;
you can find both together in the <a href="https://github.com/darius/tailbiter">Tailbiter
repo</a>.
There’s a start on a
Python parser; finish that and add an implementation of the core
Python runtime features like dictionaries and classes, and you’d be
approaching a genuinely self-sustaining system like Smalltalk. (I
think the biggest remaining lacuna would be exception
handling.)</p>
<p>An optimizer’s yet unwritten. I can imagine one serving to prototype a
successor for CPython’s peephole optimizer, someday. And how fast can
we compile? Faster than I did, that can’t be hard.</p>
<p>Peter Norvig’s <a href="http://norvig.com/paip.html"><em>Paradigms of Artificial Intelligence Programming</em></a>,
despite the title, presents short compilers for Scheme, Prolog, and a
pattern-matching rewrite-rule language. They all go to some trouble to
produce efficient output. The code is of the highest quality.</p>
<p>Niklaus Wirth’s <a href="http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf"><em>Compiler
Construction</em></a>
details a simple compiler from Oberon-0 to RISC machine code. Wirth
and Gutknecht’s <a href="http://projectoberon.com/"><em>Project Oberon: The Design of an Operating System, a
Compiler, and a Computer</em></a> elaborates it to
the full Oberon language it’s written in, ending up at about 3000
lines.</p>
<p>Andrew Appel’s <a href="http://www.cs.princeton.edu/~appel/modern/"><em>Modern Compiler Implementation in
ML</em></a> explains the ideas
behind fancier optimizing compilers.</p>
<p>CPython 2 has a <a href="https://github.com/python/cpython/tree/2.7/Lib/compiler">compiler</a> module in 4500 lines of Python, seemingly
included just for fun. For the compiler that’s normally run, see
<a href="https://docs.python.org/devguide/compiler.html">the guide</a>,
<a href="https://github.com/python/cpython/blob/master/Python/compile.c">compile.c</a>, and <a href="https://github.com/python/cpython/blob/master/Python/symtable.c">symtable.c</a>; there’s also the optimizer <a href="https://github.com/python/cpython/blob/master/Python/peephole.c">peephole.c</a>.</p>
<p>Our compiler compiled itself, but we stopped short of applying this
ability towards anything remarkable. (Can you change the language
yet?) Ken Thompson showed one surprising direction to take, in
<a href="https://www.recurse.com/blog/42-paper-of-the-week-reflections-on-trusting-trust">“Reflections on Trusting Trust”</a>.</p>
<blockquote>
<p>So it came over him all of a sudden that he would take Tailbiter and go dragon-hunting.<br />
—J.R.R. Tolkien, <em>Farmer Giles of Ham</em></p>
</blockquote>
<hr />
<p><strong>Thanks</strong> to Michael DiBernardo for editing earlier drafts of this
chapter for <a href="http://aosabook.org/en/index.html"><em>500 Lines or Less</em></a>,
and especially for his grace when I abandoned it; Andrew Gwozdziewycz
and Chris Seaton for reviewing a draft of the code; Dave Long for
conversations about assembly and code generation; Shae Erisson and
Kevin Lee for beta reading; and David Albert and Rachel Vincent for
shepherding this through to the end.</p>
<p>The tool used here for multi-version literate programming is a hacked
version of
<a href="https://github.com/kragen/peg-bootstrap/blob/master/handaxeweb.md">handaxeweb</a>
by Kragen Sitaker.</p>
<div class="footnotes">
<ol>
<li id="fn:1">
<p>A Python bytestring, such as <code class="language-plaintext highlighter-rouge">b'foo'</code>, is like a string, but of 8-bit bytes instead of Unicode characters. <a class="reversefootnote" href="https://codewords.recurse.com/feed.xml#fnref:1">↩</a></p>
</li>
<li id="fn:2">
<p>There’s no tool to dump the AST and the disassembly together like this. <a class="reversefootnote" href="https://codewords.recurse.com/feed.xml#fnref:2">↩</a></p>
</li>
<li id="fn:3">
<p>The virtual machine makes the stack not an actual Python list object, but a low-level array of words in memory. It’s conventionally pictured as vertical instead of horizontal: a stack with a top we “push” onto and “pop” from, changing its “depth.” <a class="reversefootnote" href="https://codewords.recurse.com/feed.xml#fnref:3">↩</a></p>
</li>
<li id="fn:4">
<p>As a technicality, the <code class="language-plaintext highlighter-rouge">CALL_FUNCTION</code> instruction’s argument is a two-byte integer (like all instruction arguments, when present) but encoding two individual bytes: the counts of keyword and positional arguments. Python’s bytecode format does give a way to encode bigger numbers, but we punt on them. <a class="reversefootnote" href="https://codewords.recurse.com/feed.xml#fnref:4">↩</a></p>
</li>
<li id="fn:5">
<p>You might wonder if this is quite correct: what if the code being compiled redefines <code class="language-plaintext highlighter-rouge">AssertionError</code>? But <code class="language-plaintext highlighter-rouge">assert</code> itself at runtime calls whatever <code class="language-plaintext highlighter-rouge">AssertionError</code> is bound to. <a class="reversefootnote" href="https://codewords.recurse.com/feed.xml#fnref:5">↩</a></p>
</li>
</ol>
</div>