print.html

<!DOCTYPE HTML>
<html lang="en" class="light" dir="ltr">
    <head>
        <!-- Book generated using mdBook -->
        <meta charset="UTF-8">
        <title>Create Your Own Programming Language with Rust</title>
        <meta name="robots" content="noindex">


        <!-- Custom HTML head -->
        
        <meta name="description" content="">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="theme-color" content="#ffffff">

        <link rel="icon" href="favicon.svg">
        <link rel="shortcut icon" href="favicon.png">
        <link rel="stylesheet" href="css/variables.css">
        <link rel="stylesheet" href="css/general.css">
        <link rel="stylesheet" href="css/chrome.css">
        <link rel="stylesheet" href="css/print.css" media="print">

        <!-- Fonts -->
        <link rel="stylesheet" href="FontAwesome/css/font-awesome.css">
        <link rel="stylesheet" href="fonts/fonts.css">

        <!-- Highlight.js Stylesheets -->
        <link rel="stylesheet" href="highlight.css">
        <link rel="stylesheet" href="tomorrow-night.css">
        <link rel="stylesheet" href="ayu-highlight.css">

        <!-- Custom theme stylesheets -->
        <link rel="stylesheet" href="theme/custom.css">

    </head>
    <body class="sidebar-visible no-js">
    <div id="body-container">
        <!-- Provide site root to javascript -->
        <script>
            var path_to_root = "";
            var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "rust" : "light";
        </script>

        <!-- Work around some values being stored in localStorage wrapped in quotes -->
        <script>
            try {
                var theme = localStorage.getItem('mdbook-theme');
                var sidebar = localStorage.getItem('mdbook-sidebar');

                if (theme.startsWith('"') && theme.endsWith('"')) {
                    localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
                }

                if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
                    localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
                }
            } catch (e) { }
        </script>

        <!-- Set the theme before any content is loaded, prevents flash -->
        <script>
            var theme;
            try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
            if (theme === null || theme === undefined) { theme = default_theme; }
            var html = document.querySelector('html');
            html.classList.remove('light')
            html.classList.add(theme);
            var body = document.querySelector('body');
            body.classList.remove('no-js')
            body.classList.add('js');
        </script>

        <input type="checkbox" id="sidebar-toggle-anchor" class="hidden">

        <!-- Hide / unhide sidebar before it is displayed -->
        <script>
            var body = document.querySelector('body');
            var sidebar = null;
            var sidebar_toggle = document.getElementById("sidebar-toggle-anchor");
            if (document.body.clientWidth >= 1080) {
                try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
                sidebar = sidebar || 'visible';
            } else {
                sidebar = 'hidden';
            }
            sidebar_toggle.checked = sidebar === 'visible';
            body.classList.remove('sidebar-visible');
            body.classList.add("sidebar-" + sidebar);
        </script>

        <nav id="sidebar" class="sidebar" aria-label="Table of contents">
            <div class="sidebar-scrollbox">
                <ol class="chapter"><li class="chapter-item expanded "><a href="intro.html"><strong aria-hidden="true">1.</strong> Introduction</a></li><li class="chapter-item expanded "><a href="crash_course.html"><strong aria-hidden="true">2.</strong> Crash Course on Computing</a></li><li class="chapter-item expanded "><a href="01_calculator/calc_intro.html"><strong aria-hidden="true">3.</strong> Calculator</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="01_calculator/grammar_lexer_parser.html"><strong aria-hidden="true">3.1.</strong> Grammar, Lexer and Parser</a></li><li class="chapter-item expanded "><a href="01_calculator/ast.html"><strong aria-hidden="true">3.2.</strong> Abstract Syntax Tree (AST) and Interpreter</a></li><li class="chapter-item expanded "><a href="01_calculator/jit_intro.html"><strong aria-hidden="true">3.3.</strong> Just-In-Time (JIT) Compiler with LLVM</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="01_calculator/basic_llvm.html"><strong aria-hidden="true">3.3.1.</strong> Basic Example</a></li><li class="chapter-item expanded "><a href="01_calculator/ast_traversal.html"><strong aria-hidden="true">3.3.2.</strong> AST Traversal Patterns</a></li></ol></li><li class="chapter-item expanded "><a href="01_calculator/exercise.html"><strong aria-hidden="true">3.4.</strong> Exercises</a></li><li class="chapter-item expanded "><a href="01_calculator/vm.html"><strong aria-hidden="true">3.5.</strong> Virtual Machine (VM), Bytecode and Interpreter</a></li><li class="chapter-item expanded "><a href="01_calculator/repl.html"><strong aria-hidden="true">3.6.</strong> Read-Eval-Print Loop (REPL)</a></li></ol></li><li class="chapter-item expanded "><div><strong aria-hidden="true">4.</strong> Firstlang</div></li><li><ol class="section"><li class="chapter-item expanded "><div><strong aria-hidden="true">4.1.</strong> Static Typing and Type Inference</div></li></ol></li><li class="chapter-item expanded "><div><strong aria-hidden="true">5.</strong> Object System and Object Oriented Language</div></li><li class="chapter-item expanded "><div><strong aria-hidden="true">6.</strong> TENTATIVE: Mini Standard Library</div></li><li class="chapter-item expanded "><div><strong aria-hidden="true">7.</strong> Resources</div></li></ol>
            </div>
            <div id="sidebar-resize-handle" class="sidebar-resize-handle">
                <div class="sidebar-resize-indicator"></div>
            </div>
        </nav>

        <!-- Track and set sidebar scroll position -->
        <script>
            var sidebarScrollbox = document.querySelector('#sidebar .sidebar-scrollbox');
            sidebarScrollbox.addEventListener('click', function(e) {
                if (e.target.tagName === 'A') {
                    sessionStorage.setItem('sidebar-scroll', sidebarScrollbox.scrollTop);
                }
            }, { passive: true });
            var sidebarScrollTop = sessionStorage.getItem('sidebar-scroll');
            sessionStorage.removeItem('sidebar-scroll');
            if (sidebarScrollTop) {
                // preserve sidebar scroll position when navigating via links within sidebar
                sidebarScrollbox.scrollTop = sidebarScrollTop;
            } else {
                // scroll sidebar to current active section when navigating via "next/previous chapter" buttons
                var activeSection = document.querySelector('#sidebar .active');
                if (activeSection) {
                    activeSection.scrollIntoView({ block: 'center' });
                }
            }
        </script>

        <div id="page-wrapper" class="page-wrapper">

            <div class="page">
                                <div id="menu-bar-hover-placeholder"></div>
                <div id="menu-bar" class="menu-bar sticky">
                    <div class="left-buttons">
                        <label id="sidebar-toggle" class="icon-button" for="sidebar-toggle-anchor" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
                            <i class="fa fa-bars"></i>
                        </label>
                        <button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
                            <i class="fa fa-paint-brush"></i>
                        </button>
                        <ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
                            <li role="none"><button role="menuitem" class="theme" id="light">Light</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
                        </ul>
                        <button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
                            <i class="fa fa-search"></i>
                        </button>
                    </div>

                    <h1 class="menu-title">Create Your Own Programming Language with Rust</h1>

                    <div class="right-buttons">
                        <a href="print.html" title="Print this book" aria-label="Print this book">
                            <i id="print-button" class="fa fa-print"></i>
                        </a>

                    </div>
                </div>

                <div id="search-wrapper" class="hidden">
                    <form id="searchbar-outer" class="searchbar-outer">
                        <input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
                    </form>
                    <div id="searchresults-outer" class="searchresults-outer hidden">
                        <div id="searchresults-header" class="searchresults-header"></div>
                        <ul id="searchresults">
                        </ul>
                    </div>
                </div>

                <!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
                <script>
                    document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
                    document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
                    Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
                        link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
                    });
                </script>

                <div id="content" class="content">
                    <main>
                        <blockquote>
<p>Materials in this book are distributed under the terms of <a href="https://github.com/ehsanmok/create-your-own-lang-with-rust/blob/master/LICENSE">Creative Commons BY-NC-SA 4.0</a></p>
<p align="center">
   <a href><img alt="license" src="./img/by-nc-sa.png" width="250" height="100"> </a>
</p>
</blockquote>
<p>This book assumes some basic knowledge of Rust language. Please take a look at the official <a href="https://doc.rust-lang.org/book/">Rust book</a>.</p>
<p>The accompanying codes and materials for this book are available in <a href="https://github.com/ehsanmok/create-your-own-lang-with-rust">GitHub</a>. To follow along, make sure you have</p>
<ul>
<li>
<p><a href="https://www.rust-lang.org/tools/install">Rust toolchain installed</a></p>
</li>
<li>
<p>Cloned the repository</p>
<pre><code class="language-text">git clone https://github.com/ehsanmok/create-your-own-lang-with-rust
cd create-your-own-lang-with-rust
</code></pre>
</li>
<li>
<p>LLVM installed to run and test locally <code>cargo test --tests</code></p>
<ul>
<li>Easiest option is LLVM v14.0 (<a href="https://apt.llvm.org/">Debian/Ubuntu</a> or <a href="https://formulae.brew.sh/formula/llvm">macOS</a>)</li>
<li>Otherwise, in <code>Cargo.toml</code> you'd need to change the <code>inkwell = { ..., branch = "master", features = ["your-llvm-version"] }</code> with LLVM version on your system (output of <code>llvm-config --version</code>)</li>
</ul>
</li>
</ul>
<h2 id="motivations-and-goals"><a class="header" href="#motivations-and-goals">Motivations and Goals</a></h2>
<p>This book arises from my frustration of not finding modern, clear and concise teaching materials that are readily accessible to beginners like me who wants to learn a bit on how to create their own programming language.</p>
<p>The following are my guidelines</p>
<blockquote>
<p>"If you don't know how <em>compilers</em> work, then you don't know how computers work" <sup><a href="http://steve-yegge.blogspot.com/2007/06/rich-programmer-food.html?">1</a></sup></p>
</blockquote>
<blockquote>
<p>"If you can’t explain something in simple terms, you don’t understand it" <sup><a href="https://skeptics.stackexchange.com/questions/8742/did-einstein-say-if-you-cant-explain-it-simply-you-dont-understand-it-well-en">2</a></sup></p>
</blockquote>
<p><span style="font-family:Trebuchet MS"> Pedagogically, one of the most effective methods of teaching is co-creating interactively. Introducing the core aspects around the <em>simplest example</em> (here, our calculator language) helps a lot to build knowledge and confidence. For that, we will use mature technologies instead of spending tone of time on partially reinventing-the-wheel and bore the reader.</span></p>
<p>Here is the outline of the contents</p>
<ul>
<li><a href="./crash_course.html">Crash Course on Computing</a> which we briefly set up the definitions and foundations</li>
<li>We create our first programming language <code>Calc</code> that supports simple integer addition and subtraction. The simplicity allows us to touch a lot of important topics. We will use <a href="https://en.wikipedia.org/wiki/Parsing_expression_grammar">PEG</a> to define our grammar, <a href="https://bitbegin.github.io/pest-rs/">pest</a> to generate our <code>CalcParser</code> and explain what AST is and interpreting the AST means. Next, we will introduce JIT compilation and use <a href="https://github.com/TheDan64/inkwell">inkwell</a> to JIT compile our <code>Calc</code> language from its AST. To show an alternative compilation approach, we will create a Virtual Machine and a Runtime environment and discuss its features. Finally, we will write a simple REPL for our <code>Calc</code> language and test out different execution paths.</li>
<li>TODO: We will create <code>Firstlang</code>, a statically typed language, by gradually working our way up from our <code>Calc</code></li>
<li>TODO: Object system and minimal object oriented programming support</li>
<li>TENTATIVE: Create a mini standard library</li>
<li>TODO: Resources</li>
</ul>
<h2 id="donation"><a class="header" href="#donation">Donation</a></h2>
<p>If you have found this book useful, please consider donating to any of the organizations below</p>
<ul>
<li><a href="https://www.childfoundation.org/page/donate">Child Foundation</a></li>
<li><a href="https://blacklivesmatter.com/">Black Lives Matter</a></li>
<li><a href="https://www.foodbankscanada.ca/">Food Bank of Canada</a></li>
</ul>
<div style="break-before: page; page-break-before: always;"></div><p>Here is a bird's-eye view of a computer program execution</p>
<p align="center">
</br>
    <a href><img alt="compiler" src="./img/code_compiler_executor.svg"> </a>
</p>
<p>All these three components are intertwined together and learning their connections is crucial in understanding what makes <em>Computing</em> possible. Informally, a <em>language</em> is a structured text with syntax and semantics. A <em>Source Code</em> written in a programming language needs a translator/compiler of <em>some sort</em>, to translate it to <em>another</em> language/format. Then an executor of <em>some sort</em>, to execute/run the translated commands with the goal of matching the syntax (and semantics) to <em>some form</em> of output.</p>
<h2 id="elements-of-computing"><a class="header" href="#elements-of-computing">Elements of Computing</a></h2>
<h3 id="instructions-and-the-machine-language"><a class="header" href="#instructions-and-the-machine-language">Instructions and the Machine Language</a></h3>
<p>If you want to create a "computer" from scratch, you need to start by defining an <em>abstract model</em> for your computer. This abstract model is also referred to as <strong>Instruction Set Architecture (ISA)</strong> (instruction set or simply <em>instructions</em>). A CPU is an <em>implementation</em> of such ISA. A standard ISA defines its basic elements such as <em>data types</em>, <em>register</em> values, various hardware supports, I/O etc. and they all make up the  <em>lowest-level language</em> of computing which is the <strong>Machine Language Instructions.</strong></p>
<p>Instructions are comprised of <em>instruction code</em> (aka <em>operation code</em>, in short <strong>opcode</strong> or p-code) which are directly executed by CPU. An opcode can either have operand(s) or no operand. For example, in an 8-bits machine where instructions are 8-bits an opcode <em>load</em> might be defined by the 4-bits <strong>0011</strong> following by the second 4-bits as operand with <strong>0101</strong> that makes up the instruction <strong>00110101</strong> in the Machine Language while the opcode for <em>incrementing by 1</em> of the previously loaded value could be defined by <strong>1000</strong> with no operand.</p>
<p>Since <em>opcodes are like atoms of computing</em>, they are presented in an opcode table. An example of that is <a href="http://sparksandflames.com/files/x86InstructionChart.html">Intel x86 opcode table</a>.</p>
<h3 id="assembly-language"><a class="header" href="#assembly-language">Assembly Language</a></h3>
<p>Since it's hard to remember the opcodes by their bit-patterns, we can assign <em>abstract</em> symbols to opcodes matching their operations by name. This way, we can create Assembly language from the Machine Language. In the previous Machine Language example above, <strong>00110101</strong> (means load the binary <strong>0101</strong>), we can define the symbol <strong>LOAD</strong> referring to <strong>0011</strong> as a higher level abstraction so that <strong>00110101</strong> can be written as <strong>LOAD 0101</strong>.</p>
<p>The utility program that translates the Assembly language to Machine Language is called <strong>Assembler</strong>.</p>
<h3 id="compiler"><a class="header" href="#compiler">Compiler</a></h3>
<p align="center">
</br>
    <a href><img alt="compiler" src="./img/compiler.svg"> </a>
</p>
<p>Compiler is any program that translates (maps, encodes) a language A to language B. Each compiler has two major components</p>
<ul>
<li><strong>Frontend:</strong> deals with mapping the source code string to a structured format called <strong>Abstract Syntax Tree (AST)</strong></li>
<li><strong>Backend (code generator):</strong> translates the AST into the <a href="./crash_course.html#bytecode">Bytecode</a> / <a href="./crash_course.html#intermediate-representation-ir">IR</a> or Assembly</li>
</ul>
<p>Most often, when we talk about compiler, we mean <strong>Ahead-Of-Time (AOT)</strong> compiler where the translation happens <em>before</em> execution. Another form of translation is <strong>Just-In-Time (JIT)</strong> compilation where translation happens right at the time of the execution.</p>
<p>From the diagram above, to distinguish between a program that translates for example, Python to Assembly vs. Python to Java, the former is called compiler and the latter <strong>transpiler</strong>.</p>
<h4 id="relativity-of-low-level-high-level"><a class="header" href="#relativity-of-low-level-high-level"><em>Relativity of low-level, high-level</em></a></h4>
<p>Assembly is a <em>high-level</em> language compared to the Machine Language but is considered <em>low-level</em> when viewing it from C/C++/Rust. High-level and low-level are relative terms conveying the amount of <em>abstractions</em> involved.</p>
<h3 id="virtual-machine-vm"><a class="header" href="#virtual-machine-vm">Virtual Machine (VM)</a></h3>
<p><a href="./crash_course.html#instructions-and-the-machine-language">Instructions</a> are hardware and vendor specific. That is, an Intel CPU instructions are different from AMD CPU. A <strong>VM</strong> abstracts away details of the underlying hardware or operating system so that programs translated/compiled into the VM language becomes platform agnostic. A famous example is the <strong>Java Virtual Machine (JVM)</strong>
which translates/compiles Java programs to JVM language aka Java <strong>Bytecode</strong>. Therefore, if you have a valid Java Bytecode and <em>Java Runtime Environment (JRE)</em> in your system, you can execute the Bytecode, regardless on what platform it was compiled on.</p>
<h4 id="bytecode"><a class="header" href="#bytecode">Bytecode</a></h4>
<p>Another technique to translate a source code to Machine Code, is emulating the Instruction Set with a new (human friendly) encoding (perhaps easier than assembly). Bytecode is such an <em>intermediate language/representation</em> which is lower-level than the actual programming language that has been translated from and higher-level than Assembly language.</p>
<h4 id="stack-machine"><a class="header" href="#stack-machine">Stack Machine</a></h4>
<p>Stack Machine is a simple model for a computing machine with two main components</p>
<ul>
<li>a memory (stack) array keeping the Bytecode instructions that supports <code>push</code>ing and <code>pop</code>ing instructions</li>
<li>an instruction pointer (IP) and stack pointer (SP) guiding which instruction was executed and what is next.</li>
</ul>
<h3 id="intermediate-representation-ir"><a class="header" href="#intermediate-representation-ir">Intermediate Representation (IR)</a></h3>
<p>Any representation that's between source code and (usually) Assembly language is considered an intermediate representation. Mainstream languages usually have more than one such representations and going from one IR to another IR is called <em>lowering</em>.</p>
<h3 id="code-generation"><a class="header" href="#code-generation">Code Generation</a></h3>
<p>Code generation for a compiler is when the compiler <em>converts an IR to some Machine Code</em>. But it has a wider semantic too for example, when using Rust declarative macro via <code>macro_rules!</code> to automate some repetitive implementations, you're essentially generating codes (as well as expanding the syntax).</p>
<h2 id="conclusion"><a class="header" href="#conclusion">Conclusion</a></h2>
<p>In conclusion, we want to settle one of the most frequently asked questions</p>
<h2 id="is-python-or-a-language-x-compiled-or-interpreted"><a class="header" href="#is-python-or-a-language-x-compiled-or-interpreted"><span style="color:blue">Is Python (or a language X) Compiled or Interpreted?</span></a></h2>
<p>This is in fact the <span style="color:red">WRONG</span> question to ask!</p>
<p>Being AOT compiled, JIT compiled or interpreted is <strong>implementation-dependent</strong>. For example, the standard Python <em>implementation</em> is <a href="https://www.python.org/"><strong>CPython</strong></a> which compiles a Python source code (in CPython VM) to CPython Bytecode (contents of <code>.pyc</code>) and <strong>interprets</strong> the Bytecode. However, another implementation of Python is <a href="https://www.pypy.org/"><strong>PyPy</strong></a> which (more or less) compiles a Python source code (in PyPy VM) to PyPy Bytecode and <strong>JIT</strong> compiles the PyPy Bytecode to the Machine Code (and is usually faster than CPython interpreter).</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="calculator"><a class="header" href="#calculator">Calculator</a></h1>
<p>Our first programming language is a simple calculator supporting addition and subtraction. This is perhaps the <em>simplest language</em> that helps us introducing the major topics from grammar to compilation and virtual machine.</p>
<p>If you haven't cloned the <a href="https://github.com/ehsanmok/create-your-own-lang-with-rust">GitHub</a> repo already, please do and navigate to the <code>calculator</code> subdirectory.</p>
<p>To start, we have <code>1 + 1;</code> in <a href="https://github.com/ehsanmok/create-your-own-lang-with-rust/blob/master/calculator/examples/simple.calc">examples/simple.calc</a> where you can compile with</p>
<pre><code class="language-text">cargo build --bin main // create a simple executable for Calc
../target/debug/main examples/simple.calc
</code></pre>
<p>or simply</p>
<pre><code class="language-text">cargo run --bin main examples/simple.calc
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h2 id="grammar-lexer-parser-pipeline"><a class="header" href="#grammar-lexer-parser-pipeline">Grammar-Lexer-Parser Pipeline</a></h2>
<p>Here is a high-level view of a compiler <em>frontend</em> pipeline</p>
<p align="center">
</br>
    <a href><img alt="grammar, lexer, parser" src="01_calculator/../img/grammar_lexer_parser.svg"> </a>
</p>
<p>Every language needs a (formal) grammar to describe its syntax and semantics. Once a program adheres to the rules of the grammar in <em>Source Code</em> (for example as input string or file format), it is <em>tokenized</em> and then <em>lexer</em> adds some metadata to each token for example, where each token starts and finishes in the original source code. Lastly, parsing (reshaping or restructuring) of the lexed outputs to <a href="01_calculator/./ast.html">Abstract Syntax Tree</a>.</p>
<h2 id="grammar"><a class="header" href="#grammar">Grammar</a></h2>
<p>While there are varieties of ways to define the grammar, in this book we will use the <a href="https://en.wikipedia.org/wiki/Parsing_expression_grammar">Parsing Expression Grammar (PEG)</a>.</p>
<p>Here is how our simple calculator language <code>Calc</code> (supporting addition and subtraction) grammar looks like in PEG</p>
<pre><code class="language-text">Program = _{ SOI ~ Expr ~ EOF }

Expr = { UnaryExpr | BinaryExpr | Term }

Term = _{Int | "(" ~ Expr ~ ")" }

UnaryExpr = { Operator ~ Term }

BinaryExpr = { Term ~ (Operator ~ Term)+ }

Operator = { "+" | "-" }

Int = @{ Operator? ~ ASCII_DIGIT+ }

WHITESPACE = _{ " " | "\t" }

EOF = _{ EOI | ";" }
</code></pre>
<p><span class="filename">Filename: calculator/src/grammar.pest</span></p>
<p>This grammar basically defines the syntax and semantics where</p>
<ul>
<li>each <code>Program</code> consists of expressions (<code>Expr</code>)</li>
<li>expressions are either unary (<code>-1</code>) or binary (<code>1 + 2</code>)</li>
<li>unary or binary expressions are made of <code>Term</code> and <code>Operator</code> (<code>"+"</code> and <code>"-"</code>)</li>
<li>the only <em>atom</em> is integer <code>Int</code></li>
</ul>
<p>Given our grammar, we will use <a href="https://pest.rs/">pest</a> which is a powerful <em>parser generator</em> of PEG grammars. (For more details on pest, checkout the <a href="https://pest.rs/book/">pest book</a></p>
<p><code>pest</code> <em>derives</em> the parser <code>CalcParser::parse</code> from our grammar</p>
<pre><code class="language-rust ignore">#[derive(pest_derive::Parser)]
#[grammar = "grammar.pest"]
struct CalcParser;</code></pre>
<p><span class="filename">Filename: calculator/src/parser.rs</span></p>
<p>and does all the steps of the frontend pipeline that we mentioned so that we can start parsing any <code>Calc</code> source code (<code>source: &amp;str</code>) via the <code>Rule</code>s of our grammar</p>
<pre><code class="language-rust ignore">CalcParser::parse(Rule::Program, source)</code></pre>
<p>Before doing that, we need to define our Abstract Syntax Tree (AST) in the <a href="01_calculator/./ast.html">next section</a>.</p>
<div style="break-before: page; page-break-before: always;"></div><h2 id="abstract-syntax-tree-ast"><a class="header" href="#abstract-syntax-tree-ast">Abstract Syntax Tree (AST)</a></h2>
<p>AST comes into picture when we want to go from the string representation of our program like <code>"-1"</code> or <code>"1 + 2"</code> to something more manageable and easier to work with. Since our program is not a random string (the grammar is for), we can use the structure within the expressions <code>"-1"</code> and <code>"1 + 2"</code> to our own advantage and come up with a <em>new representation</em> like a <a href="https://en.wikipedia.org/wiki/Tree_structure">tree</a></p>
<p align="center">
  </br>
    <a href><img  alt="ast" src="01_calculator/../img/ast.svg"> </a>
</p>
<p>One thing to note here is that the <em>kinds</em> of the nodes in our tree are not the same i.e. <code>+</code> node is different from <code>1</code> node. In fact, <code>+</code> has an <strong>Operator</strong> type and <code>1</code> is an integer <strong>Int</strong> type</p>
<p align="center">
  </br>
    <a href><img  alt="ast" src="01_calculator/../img/ast_typed.svg"> </a>
</p>
<p>so we define our AST nodes as</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>pub enum Operator {
    Plus,
    Minus,
}

pub enum Node {
    Int(i32),
}
<span class="boring">}</span></code></pre></pre>
<p>Referring back to our grammar, we actually have different kinds of <em>recursive</em> expressions;</p>
<ul>
<li><strong>unary</strong> grammar
<pre><code>UnaryExpr = { Operator ~ Term }
</code></pre>
</li>
<li><strong>binary</strong> grammar
<pre><code>BinaryExpr = { Term ~ (Operator ~ Term)* }
</code></pre>
</li>
</ul>
<p>So for example, the expression <code>"-1 + (2 + 3)"</code> has this recursive structure</p>
<p align="center">
</br>
    <a href><img alt="compiler" src="01_calculator/../img/ast_recursive.svg"> </a>
</p>
<p>To include those into our AST to make it an actual <a href="https://en.wikipedia.org/wiki/Binary_tree">tree data structure</a>,
we complete our AST definition as follows</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>pub enum Operator {
    Plus,
    Minus,
}

pub enum Node {
    Int(i32),
    UnaryExpr {
        op: Operator,
        child: Box&lt;Node&gt;,
    },
    BinaryExpr {
        op: Operator,
        lhs: Box&lt;Node&gt;,
        rhs: Box&lt;Node&gt;,
    },
}
<span class="boring">}</span></code></pre></pre>
<p><span class="filename">Filename: calculator/src/ast.rs</span></p>
<p>Now, we can use the <code>pest</code> generated <code>CalcParser::parse</code> to map the Rules of our <code>Calc</code> language string to our AST.</p>
<pre><code class="language-rust ignore">
pub fn parse(source: &amp;str) -&gt; std::result::Result&lt;Vec&lt;Node&gt;, pest::error::Error&lt;Rule&gt;&gt; {
    let mut ast = vec![];
    let pairs = CalcParser::parse(Rule::Program, source)?;
    for pair in pairs {
        if let Rule::Expr = pair.as_rule() {
            ast.push(build_ast_from_expr(pair));
        }
    }
    Ok(ast)
}</code></pre>
<p>Checkout <a href="https://github.com/ehsanmok/create-your-own-lang-with-rust/blob/master/calculator/src/parser.rs">calculator/src/parser.rs</a>.</p>
<p>Note that <code>CalcParser::parse</code> takes care of the AST traversal and correctly maps it to <code>Vec&lt;Node&gt;</code> for easier access
in later stages of compilation.</p>
<h2 id="interpreter"><a class="header" href="#interpreter">Interpreter</a></h2>
<p>CPU is the <em>ultimate interpreter</em>. That is, it executes opcodes as it goes. To do that, after we have changed the representation (aka <em>lowered</em> the representation) of our source code <code>&amp;str</code> to AST <code>Node</code>, a basic interpreter looks at each node of the AST (via any <a href="https://en.wikipedia.org/wiki/Tree_traversal">tree traversal methods</a>) and simply <strong>evaluates</strong> it <em>recursively</em></p>
<pre><code class="language-rust ignore">    pub fn eval(&amp;self, node: &amp;Node) -&gt; i32 {
        match node {
            Node::Int(n) =&gt; *n,
            Node::UnaryExpr { op, child } =&gt; {
                let child = self.eval(child);
                match op {
                    Operator::Plus =&gt; child,
                    Operator::Minus =&gt; -child,
                }
            }
            Node::BinaryExpr { op, lhs, rhs } =&gt; {
                let lhs_ret = self.eval(lhs);
                let rhs_ret = self.eval(rhs);

                match op {
                    Operator::Plus =&gt; lhs_ret + rhs_ret,
                    Operator::Minus =&gt; lhs_ret - rhs_ret,
                }
            }
        }
    }</code></pre>
<p>To sum up, we define a <code>Compile</code> trait that we will use throughout this chapter</p>
<pre><code class="language-rust ignore">pub trait Compile {
    type Output;

    fn from_ast(ast: Vec&lt;Node&gt;) -&gt; Self::Output;

    fn from_source(source: &amp;str) -&gt; Self::Output {
        println!("Compiling the source: {}", source);
        let ast: Vec&lt;Node&gt; = parser::parse(source).unwrap();
        println!("{:?}", ast);
        Self::from_ast(ast)
    }
}</code></pre>
<p>and we can now implement our interpreter</p>
<pre><code class="language-rust ignore">pub struct Interpreter;

impl Compile for Interpreter {
    type Output = Result&lt;i32&gt;;

    fn from_ast(ast: Vec&lt;Node&gt;) -&gt; Self::Output {
        let mut ret = 0i32;
        let evaluator = Eval::new();
        for node in ast {
            ret += evaluator.eval(&amp;node);
        }
        Ok(ret)
    }
}</code></pre>
<p><span class="filename">Filename: calculator/src/compiler/interpreter.rs</span></p>
<p>and test</p>
<pre><code class="language-rust ignore">assert_eq!(Interpreter::from_source("1 + 2").unwrap(), 3);</code></pre>
<p>Run such tests locally with</p>
<pre><code class="language-text">cargo test interpreter --tests
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h2 id="just-in-time-jit-compiler-with-llvm"><a class="header" href="#just-in-time-jit-compiler-with-llvm">Just-In-Time (JIT) Compiler with LLVM</a></h2>
<p>JIT compilation is a combination of Ahead-Of-Time (AOT) compilation and interpretation. As we saw previously, our <code>Calc</code> interpreter evaluates AST to values (actual integer <code>i32</code> values) but a JIT compiler differs from an interpreter in what it outputs. Intuitively, JIT outputs are like AOT outputs but generated at runtime when traversing the AST.</p>
<h3 id="llvm"><a class="header" href="#llvm">LLVM</a></h3>
<p><a href="https://en.wikipedia.org/wiki/LLVM">LLVM</a> (which is <em>not</em> an acronym) is a mature compiler backend (code generator) infrastructure powering many languages such as <a href="https://clang.llvm.org/">Clang</a>, <a href="https://www.rust-lang.org/">Rust</a>, <a href="https://swift.org/">Swift</a>, etc. It has its own IR and Virtual Machine Bytecode abstracting away the underlying platform-specific differences.</p>
<p>We will use <a href="https://github.com/TheDan64/inkwell">inkwell</a> which provides a safe Rust wrapper around LLVM.</p>
<h3 id="alternatives"><a class="header" href="#alternatives">Alternatives</a></h3>
<p>Other code generators that you can use (see the <a href="01_calculator/./exercise.html">exercises</a>) in this book (not at mature as LLVM) are <a href="https://docs.rs/cranelift-simplejit/0.64.0/cranelift_simplejit/index.html">cratelift-simpljit</a> and <a href="https://github.com/swgillespie/gccjit.rs">gcc-jit</a>.</p>
<div style="break-before: page; page-break-before: always;"></div><h2 id="addition"><a class="header" href="#addition">Addition</a></h2>
<h3 id="setup"><a class="header" href="#setup">Setup</a></h3>
<p>The code is available in <a href="https://github.com/ehsanmok/create-your-own-lang-with-rust/blob/master/calculator/examples/llvm/src/main.rs"><code>calculator/examples/llvm/src/main.rs</code></a>. Because my <code>llvm-config --version</code> shows <code>14.0.6</code> so I'm using <code>features = ["llvm14-0"]</code> in inkwell</p>
<pre><code class="language-text">inkwell = { git = "https://github.com/TheDan64/inkwell", branch = "master", features = ["llvm14-0"] }
</code></pre>
<p>Go to <a href="https://github.com/ehsanmok/create-your-own-lang-with-rust/blob/master/calculator/examples/llvm/"><code>calculator/examples/llvm</code></a> sub-crate and <code>cargo run</code>.</p>
<h3 id="add-function"><a class="header" href="#add-function">Add Function</a></h3>
<p>We want to define an add function like</p>
<pre><code>add(x: i32, y: i32) -&gt; i32 { x + y }
</code></pre>
<p>but using the <strong>LLVM language</strong> and JIT it. For that, we need to define <em>every</em> bit of what makes up a function through LLVM basic constructs such as context, module, function signature setups, argument types, basic block, etc.</p>
<p>Here is how to <em>stitch</em> our add function in LLVM</p>
<ol>
<li>We start by creating a <code>context</code>, adding the <code>addition</code> module and setting up the data type we want to use <code>i32_type</code> of type <a href="https://thedan64.github.io/inkwell/inkwell/types/struct.IntType.html"><code>IntType</code></a></li>
</ol>
<pre><code class="language-rust ignore">    let context = Context::create();
    let module = context.create_module("addition");
    let i32_type = context.i32_type();</code></pre>
<ol start="2">
<li>We define the signature of <code>add(i32, i32) -&gt; i32</code>, add the function to our module, create a <a href="https://thedan64.github.io/inkwell/inkwell/basic_block/index.html">basic block</a> entry point and a builder to add later parts</li>
</ol>
<pre><code class="language-rust ignore">
    let fn_type = i32_type.fn_type(&amp;[i32_type.into(), i32_type.into()], false);
    let fn_val = module.add_function("add", fn_type, None);
    let entry_basic_block = context.append_basic_block(fn_val, "entry");

    let builder = context.create_builder();
    builder.position_at_end(entry_basic_block);</code></pre>
<ol start="3">
<li>We create the arguments <code>x</code> and <code>y</code> and add them to the <code>builder</code> to make up the return instruction</li>
</ol>
<pre><code class="language-rust ignore">    let x = fn_val.get_nth_param(0).unwrap().into_int_value();
    let y = fn_val.get_nth_param(1).unwrap().into_int_value();

    let ret = builder.build_int_add(x, y, "add").unwrap();
    let return_instruction = builder.build_return(Some(&amp;ret)).unwrap();</code></pre>
<ol start="4">
<li>Finally, we create a JIT execution engine (with no optimization for now) and let LLVM handle rest of the work for us</li>
</ol>
<pre><code class="language-rust ignore">    let execution_engine = module
        .create_jit_execution_engine(OptimizationLevel::None)
        .unwrap();
    unsafe {
        type Addition = unsafe extern "C" fn(i32, i32) -&gt; i32;
        let add: JitFunction&lt;Addition&gt; = execution_engine.get_function("add").unwrap();
        let x = 1;
        let y = 2;
        assert_eq!(add.call(x, y), x + y);
    }</code></pre>
<p>Yes! all of this just to add two integers.</p>
<div style="break-before: page; page-break-before: always;"></div><h2 id="ast-traversal-patterns"><a class="header" href="#ast-traversal-patterns">AST Traversal Patterns</a></h2>
<p>Recall from the previous section that JITing our <a href="01_calculator/./basic_llvm.html">add function</a> was very detailed and cumbersome to write. Fortunately, there are some useful patterns for traversing complicated ASTs (and IRs)</p>
<ul>
<li><strong>Builder pattern</strong></li>
<li><strong>Visitor pattern</strong> (Will be introduced in chapter 4)</li>
</ul>
<h3 id="builder-pattern"><a class="header" href="#builder-pattern">Builder Pattern</a></h3>
<p>Recall how we have interpreted our AST by traversing recursively and evaluating the nodes</p>
<pre><code class="language-rust  no_run  noplaypen">struct Eval;

impl Eval {
    pub fn new() -&gt; Self {
        Self
    }
    pub fn eval(&amp;self, node: &amp;Node) -&gt; i32 {
        match node {
            Node::Int(n) =&gt; *n,
            Node::UnaryExpr { op, child } =&gt; {
                let child = self.eval(child);
                match op {
                    Operator::Plus =&gt; child,
                    Operator::Minus =&gt; -child,
                }
            }
            Node::BinaryExpr { op, lhs, rhs } =&gt; {
                let lhs_ret = self.eval(lhs);
                let rhs_ret = self.eval(rhs);

                match op {
                    Operator::Plus =&gt; lhs_ret + rhs_ret,
                    Operator::Minus =&gt; lhs_ret - rhs_ret,
                }
            }
        }
    }
}</code></pre>
<p><span class="filename">Filename: calculator/src/compiler/interpreter.rs</span></p>
<p>but instead, we can take advantage of the <a href="https://thedan64.github.io/inkwell/inkwell/builder/struct.Builder.html">inkwell Builder</a> and recursively traverse our <code>Calc</code> AST as follows</p>
<pre><code class="language-rust  no_run  noplaypen">struct RecursiveBuilder&lt;'a&gt; {
    i32_type: IntType&lt;'a&gt;,
    builder: &amp;'a Builder&lt;'a&gt;,
}

impl&lt;'a&gt; RecursiveBuilder&lt;'a&gt; {
    pub fn new(i32_type: IntType&lt;'a&gt;, builder: &amp;'a Builder) -&gt; Self {
        Self { i32_type, builder }
    }
    pub fn build(&amp;self, ast: &amp;Node) -&gt; IntValue {
        match ast {
            Node::Int(n) =&gt; self.i32_type.const_int(*n as u64, true),
            Node::UnaryExpr { op, child } =&gt; {
                let child = self.build(child);
                match op {
                    Operator::Minus =&gt; child.const_neg(),
                    Operator::Plus =&gt; child,
                }
            }
            Node::BinaryExpr { op, lhs, rhs } =&gt; {
                let left = self.build(lhs);
                let right = self.build(rhs);

                match op {
                    Operator::Plus =&gt; self
                        .builder
                        .build_int_add(left, right, "plus_temp")
                        .unwrap(),
                    Operator::Minus =&gt; self
                        .builder
                        .build_int_sub(left, right, "minus_temp")
                        .unwrap(),
                }
            }
        }
    }
}</code></pre>
<p>and similar to our addition example, we can JIT the builder output</p>
<pre><code class="language-rust  no_run  noplaypen">pub struct Jit;

impl Compile for Jit {
    type Output = Result&lt;i32&gt;;

    fn from_ast(ast: Vec&lt;Node&gt;) -&gt; Self::Output {
        let context = Context::create();
        let module = context.create_module("calculator");

        let builder = context.create_builder();

        let execution_engine = module
            .create_jit_execution_engine(OptimizationLevel::None)
            .unwrap();

        let i32_type = context.i32_type();
        let fn_type = i32_type.fn_type(&amp;[], false);

        let function = module.add_function("jit", fn_type, None);
        let basic_block = context.append_basic_block(function, "entry");

        builder.position_at_end(basic_block);

        for node in ast {
            let recursive_builder = RecursiveBuilder::new(i32_type, &amp;builder);
            let return_value = recursive_builder.build(&amp;node);
            let _ = builder.build_return(Some(&amp;return_value));
        }
        println!(
            "Generated LLVM IR: {}",
            function.print_to_string().to_string()
        );

        unsafe {
            let jit_function: JitFunction&lt;JitFunc&gt; = execution_engine.get_function("jit").unwrap();

            Ok(jit_function.call())
        }
    }
}</code></pre>
<p><span class="filename">Filename: calculator/src/compiler/jit.rs</span></p>
<p>Finally, we can test it</p>
<pre><code class="language-rust ignore">assert_eq!(Jit::from_source("1 + 2").unwrap(), 3)</code></pre>
<p>Run such tests locally with</p>
<pre><code class="language-text">cargo test jit --tests
</code></pre>
<div style="break-before: page; page-break-before: always;"></div><h2 id="exercise"><a class="header" href="#exercise">Exercise</a></h2>
<p>To get most out of this chapter, it is recommended to at least try the first exercise below</p>
<ol>
<li>Add support for multiplication and division to the calculator and allow computations on floating numbers <code>f32</code>. Can you include standard operator precedence?</li>
<li>JIT with <a href="https://docs.rs/cranelift-simplejit/0.64.0/cranelift_simplejit/">cranelift-simplejit</a></li>
<li>JIT with <a href="https://github.com/swgillespie/gccjit.rs">gcc-jit</a></li>
</ol>
<div style="break-before: page; page-break-before: always;"></div><h2 id="virtual-machine"><a class="header" href="#virtual-machine">Virtual Machine</a></h2>
<p>Recall from the <a href="01_calculator/../crash_course.html#virtual-machine-vm">crash course</a> that a (process) VM abstracts away hardware specific instructions so that its Bytecodes (abstract instructions) can be executed in any environment that has the Bytecode runtime support. So to create our VM and its runtime, we need to define our</p>
<ul>
<li>Opcodes (new encoding atoms)</li>
<li>Bytecode representation and</li>
<li><strong>Runtime model</strong>  as <a href="01_calculator/../crash_course.html#stack-machine">Stack Machine</a></li>
</ul>
<h3 id="opcode"><a class="header" href="#opcode">Opcode</a></h3>
<p>Since our expression based <code>Calc</code> language is made up of</p>
<ul>
<li><em>constant</em> integers</li>
<li><em>unary</em> (plus, minus sign) operators and</li>
<li><em>binary</em> (addition, subtraction) operators</li>
</ul>
<p>we can define our new opcode encodings like</p>
<pre><code class="language-rust ignore">pub enum OpCode {
    OpConstant(u16), // pointer to constant table
    OpPop,           // pop is needed for execution
    OpAdd,
    OpSub,
    OpPlus,
    OpMinus,
}</code></pre>
<p><span class="filename">Filename: calculator/src/compiler/vm/opcode.rs</span></p>
<p>We choose the simplest form of encoding i.e. encoding the ops as bytes <code>u8</code> (in hex format). That is,</p>
<pre><code class="language-rust ignore">        OpCode::OpConstant(arg) =&gt; make_three_byte_op(0x01, arg),
        OpCode::OpPop =&gt; vec![0x02],  // decimal repr is 2
        OpCode::OpAdd =&gt; vec![0x03],  // decimal repr is 3
        OpCode::OpSub =&gt; vec![0x04],  // decimal repr is 4
        OpCode::OpPlus =&gt; vec![0x0A], // decimal repr is 10
        OpCode::OpMinus =&gt; vec![0x0B], // decimal repr is 11</code></pre>
<p>For easy of access, we store constant <code>Node::Int(i32)</code> nodes in a separate memory and <code>OpConstant(arg)</code> tracks these values.
In a unary expression like <code>"1"</code>, we encode <code>Node::Int(1)</code> as the opcode <code>[1, 0, 0]</code> as the first constant. (<strong>0x01</strong> in decimal is <strong>1</strong>).</p>
<h3 id="bytecode-1"><a class="header" href="#bytecode-1">Bytecode</a></h3>
<p>We define</p>
<pre><code class="language-rust ignore">pub struct Bytecode {
    pub instructions: Vec&lt;u8&gt;,
    pub constants: Vec&lt;Node&gt;,
}</code></pre>
<p><span class="filename">Filename: calculator/src/compiler/vm/bytecode.rs</span></p>
<p>and pictorially, here is how <code>"1 + 2"</code> AST to Bytecode conversion would look like</p>
<p align="center">
</br>
    <a href><img alt="ast bytecode" src="01_calculator/../img/ast_bytecode.svg"> </a>
</p>
<p>and in Rust</p>
<pre><code class="language-rust  ignore">ByteCode {
    instructions: [1, 0, 0, 1, 0, 1, 3, 2],
    constants: [Int(1), Int(2)]
}</code></pre>
<p>Now, we can implement our Bytecode interpreter</p>
<pre><code class="language-rust ignore">pub struct Interpreter {
    bytecode: Bytecode,
}

impl Compile for Interpreter {
    type Output = Bytecode;

    fn from_ast(ast: Vec&lt;Node&gt;) -&gt; Self::Output {
        let mut interpreter = Interpreter {
            bytecode: Bytecode::new(),
        };
        for node in ast {
            println!("compiling node {:?}", node);
            interpreter.interpret_node(node);
            // pop one element from the stack after
            // each expression statement to clean up
            interpreter.add_instruction(OpCode::OpPop);
        }
        interpreter.bytecode
    }
}</code></pre>
<p><span class="filename">Filename: calculator/src/compiler/vm/bytecode.rs</span></p>
<h3 id="runtime"><a class="header" href="#runtime">Runtime</a></h3>
<p>From previous example, our interpreter goes through the bytecode instructions and executes them.</p>
<p>Continuing our <code>"1 + 2"</code> Bytecode example,</p>
<pre><code class="language-text">instructions: [1, 0, 0, 1, 0, 1,   3,   2],
              -------- --------    -    -
                 |         |       |    |
constants: [  Int(1),   Int(2)]  OpAdd  OpPop

[1, 0, 0] points to the first element in constants table i.e. Int(1)
[1, 0, 1] points to Int(2)
[3] (or [0x03]) corresponding to the Opcode *OpAdd*, performs the addition operation Int(1 + 2)
[2] (or [0x02]) corresponding to the Opcode *OpPop* pops out the computed Bytecodes
</code></pre>
<p>and since we want to model our runtime as a Stack Machine so we define our VM as struct with Bytecode, stack memory (in Stack Machine) and a stack pointer to the next free space</p>
<pre><code class="language-rust ignore">const STACK_SIZE: usize = 512;

pub struct VM {
    bytecode: Bytecode,
    stack: [Node; STACK_SIZE],
    stack_ptr: usize, // points to the next free space
}</code></pre>
<p>and with the help of <em>instruction pointer (IP)</em>, we execute the Bytecodes as follows</p>
<pre><code class="language-rust ignore">    pub fn run(&amp;mut self) {
        let mut ip = 0; // instruction pointer
        while ip &lt; self.bytecode.instructions.len() {
            let inst_addr = ip;
            ip += 1;

            match self.bytecode.instructions[inst_addr] {
                0x01 =&gt; {
                    //OpConst
                    let const_idx = convert_two_u8s_to_usize(
                        self.bytecode.instructions[ip],
                        self.bytecode.instructions[ip + 1],
                    );
                    ip += 2;
                    self.push(self.bytecode.constants[const_idx].clone());
                }
                0x02 =&gt; {
                    //OpPop
                    self.pop();
                }
                0x03 =&gt; {
                    // OpAdd
                    match (self.pop(), self.pop()) {
                        (Node::Int(rhs), Node::Int(lhs)) =&gt; self.push(Node::Int(lhs + rhs)),
                        _ =&gt; panic!("Unknown types to OpAdd"),
                    }
                }
                0x04 =&gt; {
                    // OpSub
                    match (self.pop(), self.pop()) {
                        (Node::Int(rhs), Node::Int(lhs)) =&gt; self.push(Node::Int(lhs - rhs)),
                        _ =&gt; panic!("Unknown types to OpSub"),
                    }
                }
                0x0A =&gt; {
                    // OpPlus
                    match self.pop() {
                        Node::Int(num) =&gt; self.push(Node::Int(num)),
                        _ =&gt; panic!("Unknown arg type to OpPlus"),
                    }
                }
                0x0B =&gt; {
                    // OpMinus
                    match self.pop() {
                        Node::Int(num) =&gt; self.push(Node::Int(-num)),
                        _ =&gt; panic!("Unknown arg type to OpMinus"),
                    }
                }
                _ =&gt; panic!("Unknown instruction"),
            }
        }
    }

    pub fn push(&amp;mut self, node: Node) {
        self.stack[self.stack_ptr] = node;
        self.stack_ptr += 1; // ignoring the potential stack overflow
    }

    pub fn pop(&amp;mut self) -&gt; Node {
        // ignoring the potential of stack underflow
        // cloning rather than mem::replace for easier testing
        let node = self.stack[self.stack_ptr - 1].clone();
        self.stack_ptr -= 1;
        node
    }</code></pre>
<p><span class="filename">Filename: calculator/src/compiler/vm/vm.rs</span></p>
<p>To examine the generated Bytecodes and run our VM, we can do</p>
<pre><code class="language-rust ignore">let byte_code = Interpreter::from_source(source);
println!("byte code: {:?}", byte_code);
let mut vm = VM::new(byte_code);
vm.run();
println!("{}", vm.pop_last());</code></pre>
<p>Run tests locally for our VM with</p>
<pre><code class="language-text">cargo test vm --tests
</code></pre>
<p>Checkout the <a href="01_calculator/./repl.html">next section</a> on how to create a REPL for our <code>Calc</code> to compare different compilation paths.</p>
<div style="break-before: page; page-break-before: always;"></div><h2 id="read-eval-print-loop-repl"><a class="header" href="#read-eval-print-loop-repl">Read-Eval-Print Loop (REPL)</a></h2>
<p>REPL (as its name implies) loops through every line of the input and compiles it. We use <a href="https://github.com/kkawakam/rustyline">rustyline</a> crate to create our REPL. For each line of input, we can optionally choose to</p>
<ul>
<li>directly interpret the AST</li>
<li>JIT the AST</li>
<li>compile to our bytecode VM and interpret it</li>
</ul>
<pre><code class="language-rust no_run noplaypen">fn main() -&gt; Result&lt;()&gt; {
    let mut rl = DefaultEditor::new()?;
    println!("Calculator prompt. Expressions are line evaluated.");
    loop {
        let readline = rl.readline("&gt;&gt; ");
        match readline {
            Ok(line) =&gt; {
                cfg_if! {
                    if #[cfg(any(feature = "jit", feature = "interpreter"))] {
                        match Engine::from_source(&amp;line) {
                            Ok(result) =&gt; println!("{}", result),
                            Err(e) =&gt; eprintln!("{}", e),
                        };
                    }
                    else if #[cfg(feature = "vm")] {
                        let byte_code = Engine::from_source(&amp;line);
                        println!("byte code: {:?}", byte_code);
                        let mut vm = VM::new(byte_code);
                        vm.run();
                        println!("{}", vm.pop_last());
                    }
                }
            }
            Err(ReadlineError::Interrupted) =&gt; {
                println!("CTRL-C");
                break;
            }
            Err(ReadlineError::Eof) =&gt; {
                println!("CTRL-D");
                break;
            }
            Err(err) =&gt; {
                println!("Error: {:?}", err);
                break;
            }
        }
    }
    Ok(())</code></pre>
<p><span class="filename">Filename: calculator/src/bin/repl.rs</span></p>
<p>Now, we can use run the REPL and choose different compilation path</p>
<pre><code>cargo run --bin repl --features jit
// OR
cargo run --bin repl --features interpreter
// OR
cargo run --bin repl --features vm
</code></pre>
<p>In any of them, you should see the prompt like</p>
<pre><code class="language-text">Calculator prompt. Expressions are line evaluated.
&gt;&gt;&gt;
</code></pre>
<p>waiting for your inputs. Here are some sample outputs of different compilation paths in debug mode.</p>
<ul>
<li>with <code>--features jit</code></li>
</ul>
<pre><code class="language-text">Calculator prompt. Expressions are line evaluated.
&gt;&gt; 1 + 2
Compiling the source: 1 + 2
[BinaryExpr { op: Plus, lhs: Int(1), rhs: Int(2) }]
Generated LLVM IR: define i32 @jit() {
entry:
  ret i32 3
}

3
&gt;&gt; (1 + 2) - (8 - 10)
Compiling the source: (1 + 2) - (8 - 10)
[BinaryExpr { op: Minus, lhs: BinaryExpr { op: Plus, lhs: Int(1), rhs: Int(2) }, rhs: BinaryExpr { op: Minus, lhs: Int(8), rhs: Int(10) } }]
Generated LLVM IR: define i32 @jit() {
entry:
  ret i32 5
}

5
&gt;&gt;
CTRL-C
</code></pre>
<ul>
<li>with <code>--features vm</code></li>
</ul>
<pre><code class="language-text">Calculator prompt. Expressions are line evaluated.
&gt;&gt; 1 + 2
Compiling the source: 1 + 2
[BinaryExpr { op: Plus, lhs: Int(1), rhs: Int(2) }]
compiling node BinaryExpr { op: Plus, lhs: Int(1), rhs: Int(2) }
added instructions [1, 0, 0] from opcode OpConstant(0)
added instructions [1, 0, 0, 1, 0, 1] from opcode OpConstant(1)
added instructions [1, 0, 0, 1, 0, 1, 3] from opcode OpAdd
added instructions [1, 0, 0, 1, 0, 1, 3, 2] from opcode OpPop
byte code: Bytecode { instructions: [1, 0, 0, 1, 0, 1, 3, 2], constants: [Int(1), Int(2)] }
3
&gt;&gt; (1 + 2) - (8 - 10)
Compiling the source: (1 + 2) - (8 - 10)
[BinaryExpr { op: Minus, lhs: BinaryExpr { op: Plus, lhs: Int(1), rhs: Int(2) }, rhs: BinaryExpr { op: Minus, lhs: Int(8), rhs: Int(10) } }]
compiling node BinaryExpr { op: Minus, lhs: BinaryExpr { op: Plus, lhs: Int(1), rhs: Int(2) }, rhs: BinaryExpr { op: Minus, lhs: Int(8), rhs: Int(10) } }
added instructions [1, 0, 0] from opcode OpConstant(0)
added instructions [1, 0, 0, 1, 0, 1] from opcode OpConstant(1)
added instructions [1, 0, 0, 1, 0, 1, 3] from opcode OpAdd
added instructions [1, 0, 0, 1, 0, 1, 3, 1, 0, 2] from opcode OpConstant(2)
added instructions [1, 0, 0, 1, 0, 1, 3, 1, 0, 2, 1, 0, 3] from opcode OpConstant(3)
added instructions [1, 0, 0, 1, 0, 1, 3, 1, 0, 2, 1, 0, 3, 4] from opcode OpSub
added instructions [1, 0, 0, 1, 0, 1, 3, 1, 0, 2, 1, 0, 3, 4, 4] from opcode OpSub
added instructions [1, 0, 0, 1, 0, 1, 3, 1, 0, 2, 1, 0, 3, 4, 4, 2] from opcode OpPop
byte code: Bytecode { instructions: [1, 0, 0, 1, 0, 1, 3, 1, 0, 2, 1, 0, 3, 4, 4, 2], constants: [Int(1), Int(2), Int(8), Int(10)] }
5
&gt;&gt;&gt;
CTRL-C
</code></pre>
<h2 id="conclusion-1"><a class="header" href="#conclusion-1">Conclusion</a></h2>
<p>This concludes our <a href="01_calculator/./calc_intro.html">Calculator</a> chapter. We took advantage of the simplicity of our <code>Calc</code> language to touch on a lot of topics.</p>
<p>Thanks for following along and reading up this far!</p>
<p>Stay tuned for the next chapter where we gradually work our way up to create a statically typed language named creatively as <strong>Firstlang</strong> :D</p>

                    </main>

                    <nav class="nav-wrapper" aria-label="Page navigation">
                        <!-- Mobile navigation buttons -->


                        <div style="clear: both"></div>
                    </nav>
                </div>
            </div>

            <nav class="nav-wide-wrapper" aria-label="Page navigation">

            </nav>

        </div>


        <!-- Google Analytics Tag -->
        <script>
            var localAddrs = ["localhost", "127.0.0.1", ""];

            // make sure we don't activate google analytics if the developer is
            // inspecting the book locally...
            if (localAddrs.indexOf(document.location.hostname) === -1) {
                (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
                (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
                m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
                })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');

                ga('create', 'UA-168768722-1', 'auto');
                ga('send', 'pageview');
            }
        </script>


        <script>
            window.playground_copyable = true;
        </script>


        <script src="elasticlunr.min.js"></script>
        <script src="mark.min.js"></script>
        <script src="searcher.js"></script>

        <script src="clipboard.min.js"></script>
        <script src="highlight.js"></script>
        <script src="book.js"></script>

        <!-- Custom JS scripts -->

        <script>
        window.addEventListener('load', function() {
            window.setTimeout(window.print, 100);
        });
        </script>

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