<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[basecs - Medium]]></title>
        <description><![CDATA[Exploring the basics of computer science, every Monday, for a year. - Medium]]></description>
        <link>https://medium.com/basecs?source=rss----9bf4a8406d1d---4</link>
        <image>
            <url>https://cdn-images-1.medium.com/proxy/1*TGH72Nnw24QL3iV9IOm4VA.png</url>
            <title>basecs - Medium</title>
            <link>https://medium.com/basecs?source=rss----9bf4a8406d1d---4</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 02:54:07 GMT</lastBuildDate>
        <atom:link href="https://medium.com/feed/basecs" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com" rel="hub"/>
        <item>
            <title><![CDATA[A Most Perfect Union: Just-In-Time Compilers]]></title>
            <link>https://medium.com/basecs/a-most-perfect-union-just-in-time-compilers-2938712a9f6a?source=rss----9bf4a8406d1d---4</link>
            <guid isPermaLink="false">https://medium.com/p/2938712a9f6a</guid>
            <category><![CDATA[jit]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[compilers]]></category>
            <category><![CDATA[interpreters]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Vaidehi Joshi]]></dc:creator>
            <pubDate>Sat, 30 Dec 2017 19:17:51 GMT</pubDate>
            <atom:updated>2017-12-30T21:56:51.074Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_3hkAwB9QzUH_-K-8QxYPg.jpeg" /><figcaption>A most perfect union: just-in-time compilers.</figcaption></figure><p>The world of computer science always seems to come down to tradeoffs. Sometimes, we’re forced to choose between two data structures, algorithms, or functions that could both get the job done, but are very different in nature. At the end of the day, the thing that we’re really choosing between which things we care about and value the most — and which things we’re willing to sacrifice.</p><p>But it’s not just computer science that this truth applies to; it’s all of computing. Even if we’re not directly working with computer science concepts, we still have to make choices and weigh tradeoffs when it comes to our code and how we write it. On an broader level, we have to consider the pros and cons of different technologies, design decisions, and implementation strategies, too. Again: more tradeoffs!</p><p>But tradeoffs in technology aren’t all bad. Sometimes, they’re exactly what drives us forward. New frameworks and languages are often created just so that developers don’t need to choose between things — in other words, so that the tradeoffs we must choose between don’t have to be so steep in nature. Many technologies aim to make these choices easier and far less painful so that other programmers don’t need to pick between two very different ways of solving a problem. Instead, these new approaches try to take the best of both worlds and find a happy medium, all the while learning from and fusing together concepts that already exist in the world. In the world of computing, this has happened time and time again.</p><p>Perhaps the most interesting example of this is the union of the compiler and the interpreter; it combines two powerful technologies, and created something new, which we now know today as the <em>just-in-time compiler</em>.</p><h3>A rare breed: the compiler-interpreter mix</h3><p>Last week, we took <a href="https://medium.com/basecs/a-deeper-inspection-into-compilation-and-interpretation-d98952ebc842">a deeper look</a> at the compiler and the interpreter, how both of them work, and the ways that allowed one — the compiler — to lead to the creation of the other — the interpreter. As it turns out, the history of the interpreter is intrinsically connected to what came soon afterwards: the<strong> </strong>just-in-time compiler.</p><p>We’ll recall that the interpreter was invented in 1958, by Steve Russell, who was working with a MIT professor at the time, named John McCarthy. McCarthy had written a paper on the Lisp programming language, and Russell had been drawn to working with his professor after reading his paper on the subject.</p><p>However, John McCarthy also wrote another paper called <a href="http://www-formal.stanford.edu/jmc/recursive/recursive.html">“Recursive Functions of Symbolic Expressions and Their Computation by Machine”</a>, which was published in 1960. Although we can’t be entirely sure, this paper appears to contain some of <a href="http://www.cs.tufts.edu/comp/150IPL/papers/aycock03jit.pdf">the earliest references</a> to just-in-time compilation.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*u75870zWDeKbm42XQto0Og.jpeg" /><figcaption>The IBM 7094 operator’s console, © <a href="https://en.wikipedia.org/wiki/IBM_7090#/media/File:IBM_7094_console2.agr.JPG">Wikimedia Foundation</a></figcaption></figure><p>Another early reference to just-in-time compilers appears in 1966, in the manual for the University of Michigan’s Executive System for the IBM 7090. The manual for this particular machine’s system explains how it is possible to both translate and load code while executing it, a clue that just-in-time compilers were already starting to be implemented on a more practical level by the mid 60’s!</p><p>Okay, but hang on a second — what exactly did that manual mean? We’ve looked at when and where the just-in-time compiler first showed up…but what even <em>is</em> a just-in-time compiler to begin with?</p><p>Well, a simple way to think about it is this: the <strong><em>just-in-time compiler</em></strong> (or <strong><em>JIT</em></strong> for short) is the child of it’s parents, the compiler and the interpreter.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*srX_spd2qzZ2aH1Eo_6T7g.jpeg" /><figcaption>Just-in-time compilers: a definition.</figcaption></figure><p>The JIT is a fusion or combination of the interpreter and the compiler, which are each two types of translators in their own right. A just-in-time compiler has many of the benefits of both of these two translation techniques, all rolled up into one.</p><p>We’ll recall that both the compiler and the interpreter do the work of translating a programmer’s source code into executable machine code, either by translating it in one shot (compiler), or by interpreting and running the code line-by-line (interpreter).</p><p>A compiler can act as a great translator because it makes code fast to execute; however, it has to translate all of the source code into a binary file first, before it can execute any of it, which can make it painful to debug something from the source when we only have machine code to work with.</p><p>On the other hand, the interpreter can directly execute pieces of code during runtime, which means that if something goes wrong, it can maintain the context of where the executed code was called when it is run. However, the interpreter has to retranslate code multiple times, which can make it slow and less efficient.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*bRfB9avGGBhB0XYWyo5v9Q.jpeg" /><figcaption>A JIT compared to its parents: the compiler and the interpreter.</figcaption></figure><p>So where does the JIT fit into this? Well, to start off, the JIT acts like one of its parents — namely, it acts like an <em>interpreter</em> at first, executing and re-running code as it is called. However, if the JIT finds code that is called many times and invoked repeatedly, it behaves like its other parent: the compiler.</p><p>The JIT acts like an interpreter until it notices that it is doing a bunch of repeated work. At that point, it behaves more like a compiler, and will optimize the repeatedly-called code by compiling it directly. This allows a JIT to pull in the best of both of its “parent” translators — the compiler and the interpreter. While it does begin by interpreting the source text, it does so in a special way. The JIT has to keep a careful watch on the code that it is running inline during interpretation.</p><p>A JIT needs to be able to answer the question:</p><blockquote>Can I keep interpreting this code directly, or should I just go ahead and compile this so I don’t need to keep repeating the work of translating?</blockquote><p>So how does it answer this sometimes difficult question? Well, the JIT keeps a close eye on what’s happening, and <strong><em>monitors</em></strong> or <strong><em>profiles</em></strong> the code that it is executing.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BEZ-PWgl2UvdMUP0KADFyg.jpeg" /><figcaption>How the JIT initially interprets the code in a source text.</figcaption></figure><p>While the JIT is interpreting the code, it simultaneously monitors it. When it notices repeated work, it thinks to itself: <em>“Hey! This is silly. I don’t need to do this unneccesary work. Let me be smart about how I deal with this code.”</em></p><p>Now, this seems great in theory. But how does the JIT know how to answer this question in practice, exactly? Time to find out!</p><h3>Smoke leads to fire, fire leads to compilation</h3><p>We know that a JIT has to keep a close eye on the code that it runs. But how exactly does it monitor what’s going on? Well, we might imagine what we would do if we were monitoring something from the outside: we’d probably have a piece of paper or a notepad and mark things as they happened in order to keep track of events as they happen.</p><p>The JIT does exactly that. It usually has an internal monitor that “marks” code that seems suspect. For example, if a section of our source code is called a few times, the JIT will make a note of the fact that this code is called often; this is often referred to as <strong><em>“warm” code</em></strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0lmvQX9D1WSo4CUJ57odJw.jpeg" /><figcaption>The JIT uses warmth and heat to determine how to optimize our code!</figcaption></figure><p>By the same token, if some lines in our source code are run many, many times, the JIT will make a note of it by marking that section as <strong><em>“hot” code</em></strong>. By using these delimiters, the JIT can easily figure out which lines and sections of code could be optimized — in other words, could be <em>compiled</em> rather than <em>interpreted</em>— later on.</p><p>Understanding the value and usefulness of “warm” and “hot” code makes a lot more sense with an example. So, let’s take a look at an abstracted version of some source text, which could be in any language, and of any size. For our purposes, we can imagine that this is a very short program that is only 6 lines of code long.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7U5lXmGC6V9N2J2edSmgPQ.jpeg" /><figcaption>How does the JIT know what to do with a hot line of code, a warm line, and a line that is never even called?</figcaption></figure><p>Looking at the illustration shown here, we can see that line 1 is called very, very often. The JIT will recognize pretty quickly that line 1 is “hot” code.</p><p>Line 4, on the other hand, is never actually called; perhaps it is setting a variable that is never used, or is a line of code that never ends up being invoked. This is what is sometimes called <strong><em>“dead” code</em></strong>.</p><p>Finally, line 5 is sometimes called often, but not nearly as much as line 1. The JIT will recognize that this is “warm” code, and could potentially be optimized in some way.</p><p>The JIT needs to consider what it should do with all of these lines of code so that it can figure out what is the best way to optimize. The reason that this consideration needs to be taken into account is that <em>not all optimization is actually good</em>. Depending on the efficiency with which the JIT decides to optimize, the optimization might not actually be all that helpful!</p><p>Let’s look at some of these lines to see how exactly the JIT could end up making a poor optimization choice if it isn’t clever enough.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Dttv73ZwQwIehqXQu78iIg.jpeg" /><figcaption>Baseline compilation: a definition.</figcaption></figure><p>We’ll start with line 1. In this situation, the code on line 1 is executed very, very often. Let’s say that the JIT notices (monitors) that this line is being repeated often. It will inevitably take that “hot” line of code and decide to compile it.</p><p>But the way that the JIT decides to compile this code is just as important as the fact that it is compiling it to begin with.</p><p>A JIT can perform different kinds of compilations, some of them quick, and some of them more complex. A quick compilation of code is often a lower-performance optimization, and involves compiling the code and then storing the compiled result without taking too much time. This form of quick optimization is known as <strong><em>baseline optimization</em></strong>.</p><p>However, if the JIT chose to do a baseline optimization of line 1, how would that affect the runtime of our code overall? Well, the result of a poor optimization choice on line 1 would result in our runtime increasing and rising linearly (<em>O(n)</em>) as the number of calls to the method on line 1 increased.</p><p>Alternatively, the JIT could also perform a longer, more in-depth kind of performance optimization called <strong><em>optimizing compilation</em></strong>, or <strong><em>opt-compiling</em></strong>. Opt-compiling involves spending time up front and investing in optimizing a piece of code by compiling as efficient as possible, and then using the stored value of that optimization.</p><blockquote>We can think of baseline compilation versus opt-compiling as two different approaches to editing an essay.</blockquote><p>Baseline compilation is a little bit like editing an essay for spelling, punctuation, and grammar; we’re not doing an in-depth improvement of the essay, but we are making a few improvements. On the other hand, opt-compiling is akin to editing an essay for content, clarity, and readability — in addition to spelling and grammar. Opt-compiling takes more up-front work, but leads to a better end result.</p><p>The nice thing about opt-compiling is that, once we’ve compiled a section of code in the most optimized way possible, we can store the result of that optimized code and perpetually run that compiled code again and again. This means that no matter how many times we call a method in the section of code that we’ve optimized, it will take constant time to run that code since we’re really just running the same compiled file each time. Even as the number of method calls goes up, the runtime for code execution stays the same; this results in constant time (<em>O(1)</em>) for code that has been opt-compiled.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Q-FGSMJ5__jQ0MnW6eNmmQ.jpeg" /><figcaption>Optimizing compilation: a definition.</figcaption></figure><p>Based on the Big O Notation of opt-compiling alone, it might sound like opt-compiling should always be the way to go! However, there are some instances when opt-compiling can be wasted effort.</p><p>For example, what would happen if our JIT went ahead and started opt-compiling everything? We’ll recall that line 4 is never actually called and is “dead” code. If our JIT took the time up front to opt-compile line 4, which is never even run, then it will spend an unnecessary amount of time in order to prematurely optimize a line of code that is never invoked. In this scenario, opt-compiling blindly, without taking a deeper look at what’s actually going on in the code and without relying on the hotness of the code itself ends up being rather wasteful!</p><p>So, what’s a JIT compiler to do? Well, ultimately, it needs to find a happy medium between baseline compilation and opt-compiling. This is exactly where the “hotness” of code comes into play.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_NnYS04l7k9iqMW5dumkmA.jpeg" /><figcaption>Finding a happy medium between baseline and opt-compiling.</figcaption></figure><p>The JIT uses the “hotness” of a line of code in order to decide not just how important it is for that code to be compiled, but also which strategy — either <em>baseline</em> or <em>opt-compiling</em>—to use when it compiles.</p><h3>A happy, hot path leads to optimal JIT compiling</h3><p>We already know that the JIT uses the “hotness” of code in order to decide which kind of compilation strategy to use. But how does it make its decision, exactly?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XuZ3nduRSxFk8hFTdWYQcg.jpeg" /><figcaption>Combining hotness and optimal compilation strategies!</figcaption></figure><p>For code that is neither “hot” nor “warm” — including code that is “dead” — the JIT will behave just like an interpreter, and won’t even bother making any compiler optimizations whatsoever.</p><p>But, for code that is “warm” but not “hot”, the JIT will use the quicker, baseline form of compilation during program execution. In other words, as it interprets this code and notices that is is “warm”, it sends it off to be compiled while the code is still being executed. It will compile that “warm” code in a simple way — the quickest, low-performance way possible. This means that it makes a slight improvement because even baseline compilation is better than nothing for “warm” code.</p><p>However, for code that is “hot” and called upon frequently, the JIT will make a note of this, and when it is called enough times, it will interrupt program execution (interpretation), and send that code to be opt-compiled — optimized in the best possible way, which also means more time invested in compilation up front. The benefit to this is that the “hot” code only needs to be optimized the one time, even though it is slightly more work to do so. Once the “hot” code has been optimized, the JIT will just keep reusing and rerunning the machine code for the optimized version again and again during runtime, without ever having to need to send it off to be recompiled again and again.</p><p>The basic rule of thumb to remember is this:</p><blockquote>For code that is not called often, the JIT will use baseline compilation, which is faster. However, for code that is called frequently, the JIT will use the longer opt-compile method, because it knows that it is worth the effort.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*LETkOZtFLXqgkGFQxmsW7g.jpeg" /><figcaption>The risk of dynamic translation.</figcaption></figure><p>Ever so rarely, the JIT will make a call that is incorrect. That is to say, it will determine that some piece of code is called enough to be opt-compiled, but as it turns out, maybe it isn’t! For example, if our JIT looks for lines of code called 5 times before it is opt-compiled, and it sees a line of code that is called 4 times, on the 5th time, it will likely send it off to be opt-compiled. In very rare occurrences, it might so happen that the line of code that it opt-compiled is never ever called again! In which case, all the work it put into compiling that line went to waste.</p><p>This is just a part of the story when it comes to <strong><em>dynamic translation</em></strong>, which is what just-in-time-compiliation happens to be. Every so often, the JIT could decide to pre-optimize a piece of code that won’t actually ever be called again. This is pretty rare though, because most lines of code are either called very frequently, or only a handful of times. It’s likely that most modern-day JITs can account for this very well, but it is possible for a JIT to be wrong every once in awhile.</p><p>Most of the time, a JIT is pretty good about knowing when it should behave like an interpreter and when it should take a piece of code and compile it. The nice thing about this is that our JIT allows us speed up only the things that <em>need</em> to be sped up. Just-in-time compliation allows us to optimize and compile the code that we run the most often.</p><p>Furthermore, it allows us to continue to hold onto the place in our source code where that compiled code was run in the first place! In other words, we can still reference where some compiled code was run.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ddwl6qKtsL9R1RsEPd2EMA.jpeg" /><figcaption>The benefits of the just-in-time compiler!</figcaption></figure><p>For example, in the image above, our JIT determined that function one() is a high “hotness”, and can be opt-compiled to be more efficient. Even though function one() was compiled, we can still reference where that compiled came from in our source text. Effectively, if there are any errors in this compiled code, we now know where exactly it came from in the source text. Since the compilation happens during runtime, we can easily debug any errors or problems, because we know to look at function one() for clues, since the error is coming from the compiled code generated by this particular line.</p><p>The just-in-time compiler gives us the benefits of both worlds: it allows us to run fast code that can be optimized and executed via compilation, while still retaining the maintained context from the intepreter, which programmers love to have while debugging.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7BUm-FvG8jXwfloKgEEBLw.jpeg" /><figcaption>A JIT gives us the best of the interpreter and the compiler.</figcaption></figure><p>The JIT is a perfect example of every once in awhile we get lucky in comnputer science, and don’t have to choose between tradeoffs. Every so often, it turns out we can have our compiler and interpreter our code, too!</p><h3>Resources</h3><p>Even though the JIT compiler is implemented within languages that are commonly-used in computing today, it can be hard to find good resources that really explain what they are, how they work, and why they are important. There are, of course, some videos and articles that do a good job of answering these questions, but you have to dig a little bit to find them. Luckily, I did the digging for you! Here are some good places to start if you’re looking for further JIT-related reading.</p><ol><li><a href="https://hacks.mozilla.org/2017/02/a-crash-course-in-just-in-time-jit-compilers/">A crash course in just-in-time (JIT) compilers</a>, Lin Clark</li><li><a href="https://www.youtube.com/watch?v=svJerixawV0">What are Interpreters, Compilers &amp; JIT compilers?</a>, Avelx</li><li><a href="https://www.youtube.com/watch?v=yQ27DjKnxwo">Just in Time Compilation</a>, SEPL Goethe University Frankfurt</li><li><a href="https://aboullaite.me/understanding-jit-compiler-just-in-time-compiler/">Understanding JIT compiler (just-in-time compiler)</a>, Aboullaite Mohammed</li><li><a href="http://www.cs.columbia.edu/~aho/cs6998/Lectures/14-09-22_Croce_JIT.pdf">Just in Time Compilation</a>, Professor Louis Croce</li><li><a href="http://www.cs.tufts.edu/comp/150IPL/papers/aycock03jit.pdf">A Brief History of Just-In-Time</a>, Professor John Aycock</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2938712a9f6a" width="1" height="1" alt=""><hr><p><a href="https://medium.com/basecs/a-most-perfect-union-just-in-time-compilers-2938712a9f6a">A Most Perfect Union: Just-In-Time Compilers</a> was originally published in <a href="https://medium.com/basecs">basecs</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A Deeper Inspection Into Compilation And Interpretation]]></title>
            <link>https://medium.com/basecs/a-deeper-inspection-into-compilation-and-interpretation-d98952ebc842?source=rss----9bf4a8406d1d---4</link>
            <guid isPermaLink="false">https://medium.com/p/d98952ebc842</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[interpreters]]></category>
            <category><![CDATA[code]]></category>
            <category><![CDATA[compilers]]></category>
            <category><![CDATA[computer-science]]></category>
            <dc:creator><![CDATA[Vaidehi Joshi]]></dc:creator>
            <pubDate>Wed, 13 Dec 2017 17:05:20 GMT</pubDate>
            <atom:updated>2017-12-14T02:50:00.364Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*boC06EC2PGmMYNjpHtrL4A.jpeg" /><figcaption>A deeper inspection into compilation vs. interpretation</figcaption></figure><p>There is perhaps nothing more satisfying than seeing the pieces of a puzzle come together. This is the case for actual puzzles, which I am pretty bad at because I always seem to lose pieces under the couch, and more metaphorical puzzles, which I am generally better at what with no pieces to lose in strange places.</p><p>The puzzle of learning is certainly one of the more complicated enigmas out there. Learning a new thing is hard because you’re trying to constantly piece together ideas and construct concepts without always necessarily knowing how those parts fit into the larger whole. It can be difficult to try to wrap your head around something new when you constantly find yourself wondering what this new thing has to do with the broader picture that you’re already familiar with. It’s a little bit like finding a random puzzle piece and then trying to find the pieces that fit around it, but not necessarily knowing how those pieces fit into the big picture.</p><p>The same is true for learning a specific topic, like computer science. Oftentimes, it can feel like you’re picking up little bit of information — a data structure here, an algorithm there — without always knowing how one piece connects to another. I tend to think that this is the reason that learning computer science is so hard: there just aren’t very many resources that can construct the picture of the field with all of these perfectly pieces fit into one another.</p><p>However, every so often, if you really stick with a topic for long enough, you’ll find that some pieces will start to come together. And as we round out this series together, it’s time for that to finally happen!</p><h3>A translator we know and love</h3><p>When we first started this series nearly a year ago, the very first topic that we explored was something that is often thought of as the “cornerstone” of computer science: <a href="https://medium.com/basecs/bits-bytes-building-with-binary-13cb4289aafa">binary</a>. We learned that, at their very core, binary is the language that every computer speaks and understands. Our machines, at the end of the day, each run on ones and zeros.</p><p>Since then, we’ve explored different data structures, like <a href="https://medium.com/basecs/how-to-not-be-stumped-by-trees-5f36208f68a7">trees</a>, <a href="https://medium.com/basecs/a-gentle-introduction-to-graph-theory-77969829ead8">graphs</a>, and <a href="https://medium.com/basecs/whats-a-linked-list-anyway-part-1-d8b7e6508b9d">linked lists</a>, as well as <a href="https://medium.com/basecs/sorting-out-the-basics-behind-sorting-algorithms-b0a032873add">sorting algorithms</a> and <a href="https://medium.com/basecs/finding-the-shortest-path-with-a-little-help-from-dijkstra-613149fbdc8e">traversal or searching</a> algorithms. Now it’s time to finally bring it all together — or rather, bring it all <em>back</em> to binary.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*JrvsA3pmJCWqlPMGnIoSYA.jpeg" /><figcaption>We started with some source code and now we’re here.</figcaption></figure><p>We’ve gone around the world when it comes to core concepts in computing as well as computer science. But there’s one question that we haven’t really answered yet, even though it’s possible that we’ve been thinking about it this whole year: How on earth do we go from our code into the one’s and zero’s of our computer?</p><p>Well, before we get too far into <em>how</em> the code we write gets turned into binary, let’s clarify what we really mean when we use the term binary in this context. The “binary” code that a computer reads and understands is generally referred to as <strong><em>machine language</em></strong> or <strong><em>machine code</em></strong>, which is a set of instructions given to a machine and run by a its <strong><em>central processing unit</em></strong> (or <strong><em>CPU</em></strong>).</p><p>An important thing to note is that there are different kinds of machine code, some of which are literally 0’s and 1’s, and others of which are decimals or <a href="https://medium.com/basecs/hexs-and-other-magical-numbers-9785bc26b7ee">hexadecimals</a> (which we already know a lot about!). Regardless of which exact format a machine language is written in, it has to be fairly rudimentary because it needs to be understood by or computer. This is why machine languages are referred to as low level languages, because they need to be simplified enough to be processed by our machine’s CPU, which we already know is just a bunch of switches, internally.</p><blockquote>We can think of low level languages as the “mother-tongues” of our computer; machine code should be directly readable by our machine, and shouldn’t ever need to be translated by them.</blockquote><p>But how do we go from <em>our </em>code to a machine-friendly (<em>machine code</em>) version of the exact same thing? Well, the code that we write as programmers and the machine code that a computer’s processor reads are nothing more than two different types of <em>languages</em>. If we think about it, all we really need to do is translate between these two languages.</p><p>Now comes another problem: we have no idea how to translate between our code and machine code! Okay, just kidding — this isn’t <em>really</em> a problem. Because we have two helpful friends who can help us out here.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*i6IkXutqKYWpm0JwlvzPUA.jpeg" /><figcaption>Translators make our source text understandable to our machines!</figcaption></figure><p>In order for us to transform our source code into some computer-readable machine code in a binary format, we’ll need to rely on translators to help us make our source text understandable to our machines.</p><p>A <strong><em>translator</em></strong>, which is also sometimes called a programming language processor, is nothing more than a program that translates a <strong><em>source</em></strong> language into a <strong><em>target</em></strong> language, while maintaining the logical structure of the code that it is translating.</p><p>We’re already a little bit familiar with one kind of translator already, even though we might not know it just yet. Previously in this series, we’ve looked at the <a href="https://medium.com/basecs/leveling-up-ones-parsing-game-with-asts-d7a6fc2400ff">lexical and syntax analysis</a> phases (the front end) of the compiler, and the different data structures involved in the process.</p><p>As it turns out, the compiler is a <em>kind</em> of translator! There is another translator, too, whose name often gets thrown around in conjunction with the compiler’s, called the <strong><em>interpreter</em></strong>. Both the compiler and the interpreter make or code readable to our computers, but in very different ways.</p><p>But let’s first start with what we already know, first: the compiler.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hmOcXMhDgZ3FiZTURbSgiA.jpeg" /><figcaption>The compiler: a definition.</figcaption></figure><p>The <strong><em>compiler</em></strong> is nothing more than a program that takes a high level language — the language that we write our code in — and converts it into machine code. The compiler has many moving parts to it (or rather, within it), including, potentially, a scanner, a lexer/tokenizer, and a parser. But at the end of the day, even with its complexity, it’s just a program that turns our code into machine-readable code.</p><p>However, even though its job might seem simple when we put it like this, the way that a compiler does this important task is worth highlighting.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*US267VbwKwSVaLa-2MIGOw.jpeg" /><figcaption>How the compiler does its job.</figcaption></figure><p>For most cases, the compiler does the job of translating our code into machine code in one fell swoop. In other words, the compiler translates all of a programmer’s source code before the source code can ever be executed or run. It takes our source code and converts it into a single file that is written in machine code. It is that very machine code file — called an <strong><em>executable</em></strong> file and often ending with an .exe extension — which actually allows us to run the original code that we wrote.</p><p>The most important idiosyncrasy of a compiler is the fact that it takes a source text, and translates it into machine code binary in “one shot”. It returns the translated, compiled file to the programmer, who will be able to run their code via the outputted executable.</p><blockquote>The executable file returned by the compiler can be run again and again once it has been translated; the compiler doesn’t need to be around for any subsequent reruns!</blockquote><p>Once the compiler translates all the source code into machine code, the compiler’s job is done. The programmer can run the compiled code as many times as they want, with whichever inputs that they’d like to use. They can also share this compiled code with others, without ever having to share their original source code.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cV0BYWBDTFZbUr6iFjFNrg.jpeg" /><figcaption>Grace Hopper, © <a href="https://techcrunch.com/2016/11/17/grace-hopper-and-margaret-hamilton-awarded-presidential-medal-of-freedom-for-computing-advances/">TechCrunch</a></figcaption></figure><p>The concept behind this specific translator— as well as the term “compiler” itself — was coined by the illustrious <strong><em>Grace Hopper</em></strong>, back in 1952, in the most interesting of circumstances.</p><p>At the time, Hopper had been working at the Eckert-Mauchly Computer Corporation, helping develop the UNIVAC I computer as a mathematician on the team. Effectively, she was working on turning mathematical code into its own language (A-0 System language).</p><p>However, she had bigger ideas. She wanted to write an entirely new programming language that would words in English, rather than the limited number of mathematical symbols. However, when she shared this idea with her colleages. They shot her down, and told her that her idea wasn’t possible because “computers didn’t understand English”. But she was not deterred.</p><p>After three years of working on this team, Hopper had her very first working compiler. But no one believed that she had actually done it! In her biography, <em>Grace Hopper : Navy Admiral and Computer Pioneer</em>, she <a href="http://www.public.navy.mil/surfor/ddg70/Pages/namesake.aspx#.WjA760zGxE4">explains</a>:</p><blockquote>I had a running compiler and nobody would touch it. … they carefully told me, computers could only do arithmetic; they could not do programs.</blockquote><p>It’s a good thing that Grace Hopper didn’t listen to any of those nonbelievers, because she ended up continuing her work and developing one of the earliest high level programming languages, called COBOL. She also won the <a href="https://techcrunch.com/2016/11/17/grace-hopper-and-margaret-hamilton-awarded-presidential-medal-of-freedom-for-computing-advances/">Presidential Medal of Freedom</a>, among many, many, many other accomplishments.</p><p>Indeed, if she <em>had</em> listened to all of those pepole, she would have likely never taken computing to an entirely new level with her early work in constructing and designing the very first compiler. Grace Hopper’s work on the first compiler laid the groundwork for the another translator that came into existence a few years later: the interpreter.</p><h3>Step-by-step translation</h3><p>In 1958, a few years after Grace Hopper’s work on the compiler, some students at MIT were in a lab, working with an <a href="https://en.wikipedia.org/wiki/IBM_704">IBM 704</a> computer, a fairly new technology that had been introduced just four years earlier. One of these students, named Steve Russell, was working on a project called the MIT Artificial Intelligence Project, with his professor, John McCarthy.</p><p>Russell was working with the Lisp programming language at the time, and he had read a paper written by his professor on the subject. He came up with the idea to transform the eval function in Lisp into machine code, which set him on the path to creating the first Lisp interpreter, which was used to evaluate expressions in the language — the equivalent of running a program in Lisp at the time.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*hql6HmnIb5Jlw6xBVhMHMQ.jpeg" /><figcaption>Steve Russell, © <a href="http://www.masswerk.at/spacewar/SpacewarOrigin.html">mass:werk</a></figcaption></figure><p>Indeed, Hopper’s work directly impacted Russell’s invention. The first version of the Lisp interpreter was compiled by hand. In an interview with the Computer History Museum in 2008, Russell <a href="http://archive.computerhistory.org/resources/access/text/2012/08/102746453-05-01-acc.pdf">explains</a> how compilers played into his work at MIT:</p><blockquote>And my remembrance is that John [McCarthy] sort of came in one day, in late September or October or something like, that with the universal M-expression, that is the Lisp interpreter written out as an M-expression, and we sort of looked at it and said, “Oh yeah, that’ll work,” and I looked at it and said, “Oh, that’s just a matter of doing more hand compiling, like I’ve been doing. I can do that.”</blockquote><blockquote>…I got something working before Christmas, which was a useable interpreter; no garbage collector, but there weren’t any big programs yet.</blockquote><p>Russell and his colleagues would go on to <a href="http://www.computerhistory.org/pdp-1/steve-slug-russell/">hand-compile</a> the first two version of the Lisp interpreter. Today, most programmers wouldn’t even dream of hand-compiling any of their code! Indeed, many of us interact with an interpreter and use it multiple times in application development — we just might not always be aware of it.</p><p>So, what exactly <em>is</em> an interpreter? It’s about time for an official definition!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*W3b3zEDlsm3ECrl6ZcsuKg.jpeg" /><figcaption>The interpreter: a definition.</figcaption></figure><p>An <strong><em>interpreter</em></strong> is also a translator, just like a compiler, in that it takes a high level language (our source text) and converts it into machine code. However, it does something slightly different: it actually runs and <em>executes</em> the code that it translates immediately (inline) as it translates.</p><blockquote>We can think of an interpreter as the more “methodical” translator in the family. Rather than doing the work of translating our code into machine language in one single shot, it’s far more systematic about how it works.</blockquote><p>An interpreter does its job piece by piece. It will translate a section of our source text at a time, rather than translating it all at once.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cB2ZxcXz1ZKu7CxfdjIcNw.jpeg" /><figcaption>How the interpreter does its job.</figcaption></figure><p>Unlike a compiler, it doesn’t translate everything and hand over a file to us, the programmers, to execute. Instead, an interpreter will translate a single line/section of code at a time. Once it has finished translating one line, it will take the machine code version of it, and run it immediately.</p><p>Another way of thinking about it is that once a piece of code has been translated by the interpreter, only then can it be run. This seems fairly intuitive at first thought, because of course how can an interpreter run a line of code without knowing what it means in binary/machine code? But, if we think about it more deeply, there are other implications. Only once the interpreter finishes running one line of code successfully will it actually move onto the next line. We can imagine how this may or may not be a good thing, depending on what we’re trying to do.</p><p>For example, imagine we want to run our program with 10 different inputs. Our interpreter would have to run our program 10 times, interpreting it line by line, for each of our inputs. However, if we made a fatal flaw in our code, our interpreter could catch it for us the moment that it happens because it has literally just tried to run our (broken) line of code after it translated it!</p><p>By now, we might start to be able to see how both the interpreter and the compiler have tradeoffs. We’ve seen how different tools have pros and cons to them time and again in this series, and it’s probably a hallmark trait within the world of computer science. Keeping with this theme, let’s weigh the fundamental differences between interpretation and compilation as translation techniques.</p><h3>Two translators, both alike in dignity</h3><p>The differences between interpretation and compilation and their respective translators tells us a lot about how these two programs are implemented. If we compare these two methodologies, we’ll start to see how they both accomplish the same task, but in fundamentally very different ways.</p><p>The illustration below illustrates this in a more obvious way.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZxXGe3fv1pzTQi8QLucYcQ.jpeg" /><figcaption>Compilation vs. interpretation: the tradeoffs.</figcaption></figure><ol><li><strong><em>Returned result.</em></strong> While a compiler will take some source code and return a compiled, executable file, an interpreter will actually translate and then execute the source code itself, returning the result of the translation directly.</li><li><strong><em>Run frequency. </em></strong>A compiler will run only once, and will need to be called again to re-translate source code if it changes. On the other hand, an interpreter will run again and reinterpret source code when it changes; the interpreter “sticks around” to continually translate.</li><li><strong><em>Flexibility. </em></strong>The compiler translates the source code in one shot, which means that the source code isn’t required again after compilation. However, the interpreter does require the source code in order to translate and execute the program, every single time that it is ever run.</li><li><strong><em>Debugging.</em></strong> The compiler generally makes it more difficult to determine where mistakes occur in the source code, because the entire program has already been translated, and the error’s location might not be easily identifyable in the machine code. However, identifying errors is easier with an interpreter because it can maintain the location of an error or bug, and surface that issue to the programmer who wrote the code.</li></ol><p>Because of these major differences, compiled code — code that is translated and run using the compilation process — tends to run a bit <strong><em>faster</em></strong> than interpreted code. This is because the work of translating the source text into machine code has already been done, before the code is ever executed.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*tEaHNTcgH3ksRTn_PPvUIA.jpeg" /><figcaption>Compiled code as compared to interpreted code.</figcaption></figure><p>On the flip side, interpreted code is far more <strong><em>flexible</em></strong>, since the interpreter stays around for the course of the translation “process” to read and process our code.</p><p>Flexibility in this context means being able to change our code and being able to immediately run it afterwards. There is no need to recompile our code if we make a change; the interpreter will just pick up on that chance, and reinterpret the code, making it a much more <em>interactive</em> form of translation. Using an interpreter makes it much easier to test out small (or big!) changes in a source file.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*bEjIOSRlVoqme1h2uddSUQ.jpeg" /><figcaption>The benefits of compilation as compared to interpretation.</figcaption></figure><p>However, when it comes to interpretation, we actually need the source code in order to be able to do anything. It definitely is easier to test out changes and debug issues, but the source text has to be accessible, first and foremost. With compilation, this isn’t the case. Once we have compiled our code into an executable file, we don’t ever have to worry about the source code again — unless, of course, we need to recompile.</p><p>This can often make a compiler the “safer” choice, because our source code is not exposed; rather, the only output is the executable file itself, which is just 1’s and 0’s, and doesn’t ever show anyone <em>how</em> we wrote our code or what it actually ever <em>said</em>, since it’s all machine language at that point.</p><blockquote>Compilation and interpretation play into our roles not just as developers of software, but also as consumers of it.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*G_MKTnRevNPkNVeh7Xu8hw.jpeg" /><figcaption>The easy and speed of compilation, in action.</figcaption></figure><p>For example, whenever we download a file, or run a program from an .exe file, we’re relying on the creators of some software to have compiled an executable for us.</p><p>Using compilation, we can easily distribute a program as an executable file. This will allow someone else to run the exact same code as us, but without ever actually showing them or giving them our literal code itself. A consumer of a compiled file never needs to see a source text, because they can simply be given an executable file to run on their own, local machine.</p><p>However, the issue with distributing a compiled file is creating files that are compatible on different platforms (like a Windows operating system versus OS X). As programmers, it’s our job to make sure our compiled executables run successfully on various platforms, and sometimes, this means recompiling our code!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rqrqsd2_SZApubCulF0jwg.jpeg" /><figcaption>The efficiency and benefits of interpretation, in action.</figcaption></figure><p>On the other hand, when we use interpretation, we can distribute our source code directly, rather than worrying about platform-specific executables, or thinking about how we’ll go about compiling binaries for everyone to use.</p><p>However, in this case, we’ll need the consumer of our program to download an interpreter — which often actually just comes along with a language — and be sure that the interpreter exists on their machine(s). Once they have the interpreter, they can see our original source code, take that code, and then rely on their own version of the interpreter to run it locally.</p><p>In this scenario, we rely on the interpreter to make the compatible on all platforms, and we, as programmers and consumers, don’t need to think about it. Also, if something goes wrong (either something in the source that we wrote, or something relating to their own platform), the consumer of our code can figure out what the issue is much more easily than with a compiled file. The interpreter will make it easy to debug any problems, regardless of who is running our code.</p><p>But, regardless of whether we choose compilation or interpretation, the end goal is the same: to speak a language that our computers can understand! As it turns out, at the end of the day, it really just all <em>is</em> binary.</p><h3>Resources</h3><p>Because both interpreters and compilers have been around for many years now, there are a good amount of resources out there on both of these types of translators. From an implementation perspective, there are many different approaches to writing a compiler versus an interpreter. But, if you’re looking to simply learn more or dig a little deeper, these resources are a good place to start.</p><ol><li><a href="https://www.youtube.com/watch?v=_C5AHaS1mOA">Interpreters and Compilers (Bits and Bytes, Episode 6)</a>, Bits and Bytes TVO</li><li><a href="https://tomassetti.me/difference-between-compiler-interpreter/">The difference between a compiler and an interpreter</a>, Gabriele Tomassetti</li><li><a href="https://www.youtube.com/watch?v=JNMy969SjyU">Compilation vs Interpretation</a>, BogeysDevTips</li><li><a href="https://www.youtube.com/watch?v=1OukpDfsuXE">Machine Code and High level Languages Using Interpreters and Compilers</a>, Banchory Academy Computing Science</li><li><a href="http://www2.hawaii.edu/~takebaya/ics111/process_of_programming/process_of_programming.html">The Programming Process</a>, Professor Vern Takebayashi</li><li><a href="https://softwareengineering.stackexchange.com/questions/251431/why-was-the-first-compiler-written-before-the-first-interpreter">Why was the first compiler written before the first interpreter?</a>, StackOverflow</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d98952ebc842" width="1" height="1" alt=""><hr><p><a href="https://medium.com/basecs/a-deeper-inspection-into-compilation-and-interpretation-d98952ebc842">A Deeper Inspection Into Compilation And Interpretation</a> was originally published in <a href="https://medium.com/basecs">basecs</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Leveling Up One’s Parsing Game With ASTs]]></title>
            <link>https://medium.com/basecs/leveling-up-ones-parsing-game-with-asts-d7a6fc2400ff?source=rss----9bf4a8406d1d---4</link>
            <guid isPermaLink="false">https://medium.com/p/d7a6fc2400ff</guid>
            <category><![CDATA[compilers]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[ast]]></category>
            <category><![CDATA[data-structures]]></category>
            <dc:creator><![CDATA[Vaidehi Joshi]]></dc:creator>
            <pubDate>Tue, 05 Dec 2017 03:59:31 GMT</pubDate>
            <atom:updated>2017-12-05T03:59:31.088Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kxqNtKNa_YzMpz1aahvJUQ.jpeg" /><figcaption>Leveling up one’s parsing game with ASTs!</figcaption></figure><p>Before I started on this journey of trying to learn computer science, there were certain terms and phrases that made me want to run the other direction.</p><p>But instead of running, I feigned knowledge of it, nodding along in conversations, pretending like I knew what someone was referencing even though the truth was that I had no idea and had actually stopped listening entirely when I heard That Super Scary Computer Science Term™. Throughout the course of this series, I’ve managed to cover a lot of ground and many of those terms have actually become a whole lot less scary!</p><p>There is one big one, though, that I’ve been avoiding for awhile. Up until now, whenever I had heard this term, I felt paralyzed. It has come up in casual conversation at meet ups and sometimes in conference talks. Every single time, I think of machines spinning and computers spitting out strings of code that are indecipherable except that everyone else around me <em>can</em> <em>actually</em> <em>decipher</em> <em>them</em> so it’s actually just me who doesn’t know what’s going on (whoops how did this happen?!).</p><p>Perhaps I’m not the only one who has felt that way. But, I suppose I should tell you what this term actually is, right? Well, get ready, because I’m referring to ever-elusive and seemingly confusing <em>abstract syntax tree</em>, or <em>AST</em> for short. After many years of being intimidated, I’m excited to finally stop being afraid of this term and truly understand what on earth it is.</p><p>It’s time to face the root of the abstract syntax tree head on — and level up our parsing game!</p><h3>From concrete to abstract</h3><p>Every good quest starts with a solid foundation, and our mission to demystify this structure should begin in the exact same way: with a definition, of course!</p><p>An<strong><em> abstract syntax tree</em></strong> (usually just referred to as an <strong><em>AST</em></strong>) is really nothing more than a simplified, condensed version of a parse tree. In the context of compiler design, the term “<em>AST”</em> is used interchangeably with <strong><em>syntax tree</em></strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*mhIbxxlr1hyvUemAMMeNCw.jpeg" /><figcaption>Abstract syntax tree: a definition</figcaption></figure><p>We often think about syntax trees (and how they are constructed) in comparison to their parse tree counterparts, which <a href="https://medium.com/basecs/grammatically-rooting-oneself-with-parse-trees-ec9daeda7dad">we’re already pretty familiar with</a>. We know that <em>parse trees </em>are tree data structures that contain the grammatical structure of our code; in other words, they contain all the syntactic information that appears in a code “sentence”, and is derived directly from the grammar of the programming language itself.</p><p>A <em>abstract syntax tree</em>, on the other hand, ignores a significant amount of the syntatic information that a parse tree would otherwise contain.</p><blockquote>By contrast, an AST only contains the information related to analyzing the source text, and skips any other extra content that is used while parsing the text.</blockquote><p>This distinction starts to make a whole lot more sense if we focus in on the “abstractness” of an AST.</p><p>We’ll recall that a <strong><em>parse tree</em></strong> is an illustrated, pictorial version of the grammatical structure of a sentence. In other words, we can say that a parse tree represents exactly what an expression, sentence, or text looks like. It’s basically a direct translation of the text itself; we take the sentence and turn every little piece of it — from the punctuation to the expressions to the tokens — into a tree data structure. It reveals the concrete syntax of a text, which is why it is also referred to as a <strong><em>concrete syntax tree</em></strong>, or <strong><em>CST</em></strong>. We use the term concrete to describe this structure because it’s a grammatical copy of our code, token by token, in tree format.</p><p>But what makes something concrete versus abstract? Well, an abstract syntax tree doesn’t show us <em>exactly</em> what an expression looks like, the way that a parse tree does.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OOHu35k6ivk8f3s3CM_YRg.jpeg" /><figcaption>Concrete versus abstract syntax trees</figcaption></figure><p>Rather, an abstract syntax tree shows us the “important” bits — the things that we really care about, which give meaning to our code “sentence” itself. Syntax trees show us the significant pieces of an expression, or the <em>abstracted</em> syntax of our source text. Hence, in comparison to concrete syntax tress, these structures are are abstract representations of our code (and in some ways, less exact), which is exactly how they got their name.</p><p>Now that we understand the distinction between these two data structures and the different ways that they can represent our code, it’s worth asking the question: where does an abstract syntax tree fit into the compiler? First, let’s remind ourselves of everything that we know about the compilation process as we know it so far.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2WYz6w470aMymWzmQKYLHQ.jpeg" /><figcaption>Revisiting the events leading up to parsing!</figcaption></figure><p>Let’s say we have a super short and sweet source text, which looks like this: 5 + (1 x 12).</p><p>We’ll recall that the first thing that happens in the compilation process is the <em>scanning</em> of the text, a job performed by the <em>scanner</em>, which results in the text being broken up into its smallest possible parts, which are called <em>lexemes</em>. This part will be language agnostic, and we’ll end up with the stripped-out version of our source text.</p><p>Next, these very lexemes are passed on to the lexer/tokenizer, which turns those small representations of our source text into <em>tokens</em>, which will be specific to our language. Our tokens will look something like this: [5, +, (, 1, x, 12, )]. The joint effort of the scanner and the tokenizer make up the <em>lexical analysis</em> of compilation.</p><p>Then, once our input has been tokenized, its resulting tokens are is passed along to our parser, which then takes the source text and builds a parse tree out of it. The illustration below exemplifies what our tokenized code looks like, in parse tree format.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hy0NjQ4pe44ysbU_eKFaXg.jpeg" /><figcaption>The syntax analysis phase generates the parse tree</figcaption></figure><p>The work of turning tokens into a parse tree is also called parsing, and is known as the <em>syntax analysis</em> phase. The syntax analysis phase depends directly on the lexical analysis phase; thus, lexical analysis must always come first in the compilation process, because our compiler’s parser can only do its job once the tokenizer does it’s job!</p><blockquote>We can think of the parts of the compiler as good friends, who all depend on each other to make sure that our code is correctly transformed from a text or file into a parse tree.</blockquote><p>But back to our original question: where does the abstract syntax tree fit into this friend group? Well, in order to answer that question, it helps to understand the <em>need</em> for an AST in the first place.</p><h3>Condensing one tree into another</h3><p>Okay, so now we have two trees to keep straight in our heads. We already had a parse tree, and how there’s yet another data structure to learn! And apparently, this AST data structure is just a simplified parse tree. So, why do we need it? What even is the point of it?</p><p>Well, let’s take a look at our parse tree, shall we?</p><p>We already know that parse trees represent our program at its most distinct parts; indeed, this was why the scanner and the tokenizer have such important jobs of breaking down our expression into its smallest parts!</p><blockquote>What does it mean to actually represent a program by its most distinct parts?</blockquote><p>As it turns out, sometimes all of the distinct parts of a program actually aren’t all that useful to us all the time.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*NNLKQdokzXab1nrOOs-F_w.jpeg" /><figcaption>Parse tree can often be super verbose.</figcaption></figure><p>Let’s take a look at the illustration shown here, which represents our original expression, 5 + (1 x 12), in parse tree tree format. If we take a close look at this tree with a critical eye, we’ll see that there are a few instances where one node has exactly one child, which are also referred to as <strong><em>single-successor nodes</em></strong>, as they only have one child node stemming from them (or one “successor”).</p><p>In the case of our parse tree example, the single-successor nodes have a parent node of an Expression, or Exp, which have a single successor of some value, such as 5, 1, or 12. However, the Exp parent nodes here aren’t actually adding anything of value to us, are they? We can see that they contain token/terminal child nodes, but we don’t really care about the “expression” parent node; all we really want to know is what<em> is</em> the expression?</p><p>The parent node doesn’t give us any additional information at all once we’ve parsed our tree. Instead, what we’re really concerned with is the single <em>child</em>, single-successor node. Indeed, that is the node that gives us the important information, the part that is significant to us: the number and value itself! Considering the fact that these parent nodes are kind of unnecessary to us, it becomes obvious that this parse tree is a kind of verbose.</p><p>All of these single-successor nodes are pretty superfluous to us, and don’t help us at all. So, let’s get rid of them!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*MeUwZqnExmcsCBmSyr6nRg.jpeg" /><figcaption>Compressing a parse tree allows us to avoid redundancy.</figcaption></figure><p>If we compress the single-successor nodes in our parse tree, we’ll end up with a more compressed version of the same exact structure. Looking at the illustration above, we’ll see that we’re still maintaining the exact same nesting as before, and our nodes/tokens/terminals are still appearing in the correct place within the tree. But, we’ve managed to slim it down a bit.</p><p>And we can trim some more of our tree, too. For example, if we look at our parse tree as it stands at the moment, we’ll see that there’s a mirror structure within it. The sub-expression of (1 x 12) is nested within parentheses (), which are tokens by their own right.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*zKxxgXTGKTcOFogugiSfFw.jpeg" /><figcaption>Superfluous information that is of no use to us can be removed from a parse tree.</figcaption></figure><p>However, these parentheses don’t really help us once we’ve got our tree in place. We already know that 1 and 12 are arguments that will be passed to the multiplication x operation, so the parentheses don’t tell us all that much at this point. In fact, we could compress our parse tree even further and get rid of these superfluous leaf nodes.</p><p>Once we compress and simplify our parse tree and get rid of the extraneous syntactic “dust”, we end up with a structure that looks visibly different at this point. That structure is, in fact, our new and much-anticipated friend: the abstract syntax tree.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*T0Zo8ZLDDm0m0fSmmkj7wA.jpeg" /><figcaption>An AST abstracts away from the concrete syntax.</figcaption></figure><p>The image above illustrates the exact same expression as our parse tree: 5 + (1 x 12). The difference is that it has abstracted away the expression from the concrete syntax. We don’t see any more of the parentheses () in this tree, because they’re not necessary. Similarly, we don’t see non-terminals like Exp, since we’ve already figured out what the “expression” is, and we are able to pull out the <em>value</em> that really matters to us — for example, the number 5.</p><p>This is exactly the distinguishing factor between an AST and a CST. We know that an abstract syntax tree ignores a significant amount of the syntactic information that a parse tree contains, and skips “extra content” that is used in parsing. But now we can see exactly <em>how</em> that happens!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*l-gFDuHOwn8KHm_BHr81nQ.jpeg" /><figcaption>An AST is an abstract representation of a source text.</figcaption></figure><p>Now that we’ve condensed a parse tree of our own, we’ll be much better at picking up on some of the patterns that distinguish an AST from a CST.</p><p>There a few ways that an abstract syntax tree will visually-differ from a parse tree:</p><ol><li>An AST will never contain syntactic details, such as commas, parentheses, and semicolons (depending, of course, upon the language).</li><li>An AST will have collapsed version of what would otherwise appear as single-successor nodes; it will never contain “chains” of nodes with a single child.</li><li>Finally, any operator tokens (such as +, -, x, and /) will become internal (parent) nodes in the tree, rather than the leaves which terminate in a parse tree.</li></ol><p>Visually, an AST will always appear more compact than a parse tree, since it is, by definition, a compressed version of a parse tree, with less syntactic detail.</p><blockquote>It would stand to reason, then, that if an AST is a compacted version of a parse tree, we can only really create an abstract syntax tree if we have the things to build a parse tree to begin with!</blockquote><p>This is, indeed, how the abstract syntax tree fits into the <em>larger</em> compilation process. An AST has a direct connection to <a href="https://medium.com/basecs/grammatically-rooting-oneself-with-parse-trees-ec9daeda7dad">the parse trees</a> that we have already learned about, while simultaneously relying upon <a href="https://medium.com/basecs/reading-code-right-with-some-help-from-the-lexer-63d0be3d21d">the lexer</a> to do <em>its</em> job before an AST can ever be created.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*nSsol-zdKcJnk4X45FkCEw.jpeg" /><figcaption>An AST is always the output of the parser.</figcaption></figure><p>The abstract syntax tree is created as the final result of the syntax analysis phase. The parser, which is front and center as the main “character” during syntax analysis, may or may not always generate a parse tree, or CST. Depending on the compiler itself, and how it was designed, the parser may directly go straight onto constructing a syntax tree, or AST. But the parser will always generate an AST as its output, no matter whether it creates a parse tree in between, or how many passes it might need to take in order to do so.</p><h3>Anatomy of an AST</h3><p>Now that we know that the abstract syntax tree is important (but not necessarily intimidating!), we can start to dissect it a tiny bit more. An interesting aspect about how the AST is constructed has to do with the nodes of this tree.</p><p>The image below exemplifies the anatomy of a single node within an abstract syntax tree.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*NO_p9739sX6Tf-ESRkSKaw.jpeg" /><figcaption>The anatomy of an AST node.</figcaption></figure><p>We’ll notice that this node is similar to others that we’ve seen before in that it contains some data (a token and its value). However, it also contains some very specific pointers. Every node in an AST contains references to its <em>next</em> sibling node, as well as its <em>first</em> child node.</p><p>For example, our simple expression of 5 + (1 x 12) could be constructed into a visualized illustration of an AST, like the one below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0n73V3Ld0e-nTmZKGw3OpQ.jpeg" /><figcaption>A simplified visualization of our AST expression.</figcaption></figure><p>We can imagine that reading, traversing, or “interpreting” this AST might start from the bottom levels of the tree, working its way back up to build up a value or a return result by the end.</p><p>It can also help to see a coded version of the output of a parser to help supplement our visualizations. We can lean on various tools and use preexisting parsers to see a quick example of what our expression might look like when run through a parser. Below is an example of our source text, 5 + (1 * 12), run through <a href="http://esprima.org/">Esprima</a>, an ECMAScript parser, and its resulting abstract syntax tree, followed by a list of its distinct tokens.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a2f9060031c431865efd8e395a4db624/href">https://medium.com/media/a2f9060031c431865efd8e395a4db624/href</a></iframe><p>In this format, we can see the nesting of the tree if we look at the nested objects. We’ll notice that the values containing 1 and 12 are the left and right children, respectively, of a parent operation, *. We’ll also see that the multiplication operation (*) makes up the <em>right subtree</em> of the entire expression itself, which is why it is nested within the larger BinaryExpression object, under the key &quot;right&quot;. Similarly, the value of 5 is the single &quot;left&quot; child of the larger BinaryExpression object.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*uGj9R-TDC5l67oRDGWyNFA.jpeg" /><figcaption>Building an AST can be complex sometimes.</figcaption></figure><p>The most <em>intriguing</em> aspect of the abstract syntax tree is, however, the fact that even though they are so compact and clean, they aren’t always an easy data structure to try and construct. In fact, building an AST can be pretty complex, depending on the language that the parser is dealing with!</p><p>Most parsers will usually either construct a parse tree (CST) and then convert it to an AST format, because that can sometimes be easier — even though it means more steps, and generally speaking, more passes through the source text. Building a CST is actually pretty easy once the parser knows the grammar of the language it’s trying to parse. It doesn’t need to do any complicated work of figuring out if a token is “significant” or not; instead, it just takes exactly what its sees, in the specific order that it sees it, and spits it all out into a tree.</p><p>On the other hand, there are some parsers that will try to do all of this as a single-step process, jumping straight to constructing an abstract syntax tree.</p><blockquote>Building an AST directly can be tricky, since the parser has to not only find the tokens and represent them correctly, but also decide which tokens matter to us, and which ones don’t.</blockquote><p>In compiler design, the AST ends up being super important for more than one reason. Yes, it can be tricky to construct (and probably easy to mess up), but also, it’s the last and final result of the lexical and syntax analysis phases combined! The lexical and syntax analysis phases are often jointly called the <strong><em>analysis phase</em></strong>, or <strong><em>the</em></strong> <strong><em>front-end</em></strong> of the compiler.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FHdVIhCQyY7WDeTSDH5KZg.jpeg" /><figcaption>The inner workings of the front-end of our compiler.</figcaption></figure><p>We can think about the abstract syntax tree as the “final project” of the front-end of the compiler. It’s the most important part, because its the last thing that the front-end has to show for itself. The technical term for this is called the <strong><em>intermediate code representation </em></strong>or the <strong><em>IR</em></strong>, because it becomes the data structure that is ultimately used by the compiler to represent a source text.</p><p>An abstract syntax tree is the most common form of IR, but also, sometimes the most misunderstood. But now that we understand it a little bit better, we can start to change our perception of this scary structure! Hopefully, it’s a little bit less intimidating to us now.</p><h3>Resources</h3><p>There are a whole lot of resources out there on ASTs, in a variety of languages. Knowing where to start can be tricky, especially if you’re looking to learn more. Below are a few beginner-friendly resources that dive into a whole lot more detail without being <em>too</em> overhwelming. Happy asbtracting!</p><ol><li><a href="http://pages.cs.wisc.edu/~fischer/cs536.s06/course.hold/html/NOTES/4.SYNTAX-DIRECTED-TRANSLATION.html#astVsParse">The AST vs the Parse Tree</a>, Professor Charles N. Fischer</li><li><a href="https://stackoverflow.com/questions/5967888/whats-the-difference-between-parse-trees-and-abstract-syntax-trees">What’s the difference between parse trees and abstract syntax trees?</a>, StackOverflow</li><li><a href="https://eli.thegreenplace.net/2009/02/16/abstract-vs-concrete-syntax-trees/">Abstract vs. Concrete Syntax Trees</a>, Eli Bendersky</li><li><a href="http://www1.cs.columbia.edu/~sedwards/classes/2003/w4115f/ast.9up.pdf">Abstract Syntax Trees</a>, Professor Stephen A. Edwards</li><li><a href="http://user.it.uu.se/~kostis/Teaching/KT1-11/Slides/lecture05.pdf">Abstract Syntax Trees &amp; Top-Down Parsing</a>, Professor Konstantinos (Kostis) Sagonas</li><li><a href="http://www.pling.org.uk/cs/lsa.html">Lexical and Syntax Analysis of Programming Languages</a>, Chris Northwood</li><li><a href="https://astexplorer.net">AST Explorer,</a> Felix Kling</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d7a6fc2400ff" width="1" height="1" alt=""><hr><p><a href="https://medium.com/basecs/leveling-up-ones-parsing-game-with-asts-d7a6fc2400ff">Leveling Up One’s Parsing Game With ASTs</a> was originally published in <a href="https://medium.com/basecs">basecs</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Has basecs helped you? I’d love to know how ]]></title>
            <link>https://medium.com/basecs/has-basecs-helped-you-id-love-to-know-how-e98d12e8c1b2?source=rss----9bf4a8406d1d---4</link>
            <guid isPermaLink="false">https://medium.com/p/e98d12e8c1b2</guid>
            <dc:creator><![CDATA[Vaidehi Joshi]]></dc:creator>
            <pubDate>Fri, 01 Dec 2017 03:59:56 GMT</pubDate>
            <atom:updated>2017-12-01T03:59:55.791Z</atom:updated>
            <content:encoded><![CDATA[<p>Dear <em>basecs</em> reader,</p><p>It’s finally here — the last month of the year, and with that, (nearly) the end of this series. Although I have been watching as this project has grown and flourished with old readers and new ones alike, I have no idea who it has impacted.</p><p>That’s why I’m writing to you. If <em>basecs</em> has helped you in any way, if you have found the series informative, or if you have ever shared it with someone, I’d love to know about it!</p><blockquote>If you have a few minutes, I hope you’ll take the time to answer this <a href="https://vaidehi.typeform.com/to/Fhpf5J">short survey</a>.</blockquote><p><strong>Your feedback will help me better understand this project, as well as how to improve and iterate on it in the future.</strong></p><p>Thank you again for your continued readership and support. 💛</p><p>With gratitude,<br>Vaidehi</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e98d12e8c1b2" width="1" height="1" alt=""><hr><p><a href="https://medium.com/basecs/has-basecs-helped-you-id-love-to-know-how-e98d12e8c1b2">Has basecs helped you? I’d love to know how 💛</a> was originally published in <a href="https://medium.com/basecs">basecs</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Reading Code Right, With Some Help From The Lexer]]></title>
            <link>https://medium.com/basecs/reading-code-right-with-some-help-from-the-lexer-63d0be3d21d?source=rss----9bf4a8406d1d---4</link>
            <guid isPermaLink="false">https://medium.com/p/63d0be3d21d</guid>
            <category><![CDATA[code]]></category>
            <category><![CDATA[compilers]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[theory-in-practice]]></category>
            <category><![CDATA[computer-science]]></category>
            <dc:creator><![CDATA[Vaidehi Joshi]]></dc:creator>
            <pubDate>Mon, 27 Nov 2017 13:01:02 GMT</pubDate>
            <atom:updated>2017-11-27T13:01:01.316Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*60jM612MnBJEc0CJrnngvA.jpeg" /><figcaption>Reading code right, with some help from the lexer.</figcaption></figure><p>Software is all about logic. Programming has garnered a reputation of being a field that is heavy on the math and crazy equations. And computer science seems to be at the crux of this misconception.</p><p>Sure, there is some math and there are some formulas — but none of us actually need to have PhDs in calculus in order for us to understand how our machines work! In fact, a lot of the rules and paradigms that we learn in the process of writing code are the same rules and paradigms that apply to complex computer science concepts. And sometimes, those ideas actually <em>stem</em> <em>from</em> computer science, and we just didn’t ever know it.</p><p>Regardless of what programming language we use, when most of us write our code, we aim to encapsulate distinct things into classes, objects, or methods, intentionally separating out what different parts of our code are concerned with. In other words, we know that it’s generally good things to divide up our code so that one class, object, or method is only concerned with and responsible for one single thing. If we didn’t do this, things could get super messy and intertwined into a mess of a web. Sometimes this still happens, even with separation of concerns.</p><p>As it turns out, even the inner workings of our computers follow very similar design paradigms. Our compiler, for example, has different parts to it, and each part is responsible for handling one specific part of the compilation process. We encountered a little bit of this last week, when <a href="https://medium.com/basecs/grammatically-rooting-oneself-with-parse-trees-ec9daeda7dad">we learned about the parser</a>, which is responsible for creating parse trees. But the parser can’t possibly be tasked with everything.</p><p>The parser needs some help from its buddies, and it’s finally time for us to learn who they are!</p><h3>Phasing into compilers</h3><p>When we <a href="https://medium.com/basecs/grammatically-rooting-oneself-with-parse-trees-ec9daeda7dad">learned about parsing</a> recently, we dipped our toes into grammar, syntax, and how the compiler reacts and responds to those things within a programming language. But we never really highlighted what exactly a compiler is! As we get into the inner workings of the compilation process, we’re going to be learning a lot about compiler design, so it’s vital for us to understand what exactly we’re talking about here.</p><p>Compilers can sound kind of scary, but their jobs are actually not too complex to understand — particularly when we break the different parts of a complier down into bite-sized parts.</p><p>But first, let’s start with the simplest definition possible. A <strong><em>compiler</em></strong> is a program that reads our code (or any code, in any programming language), and translates it into another language.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*q0vT9J6ylmIe2t-IvnWdtw.jpeg" /><figcaption>The compiler: a definition.</figcaption></figure><p>Generally speaking, a compiler is really only ever going to translate code from a high-level language into a lower level language. The lower level languages that a compiler translates code into is often referred to as assembly code, machine code, or object code. It’s worth mentioning that most programmers aren’t really dealing with or writing any machine code; rather, we depend on the compiler to take our programs and translate them into machine code, which is what our computer will run as an executable program.</p><p>We can think of compilers as the middleman between us, the programmers, and our computers, which can only run executable programs in lower level languages.</p><blockquote>The compiler does the work of translating what we want to happen in a way that is understandable and executable by our machines.</blockquote><p>Without the compiler, we’d be forced to communicate with our computers by writing machine code, which is incredibly unreadable and hard to decipher. Machine code can often just look like a bunch of 0’s and 1’s to the human eye — it’s all binary, <a href="https://medium.com/basecs/bits-bytes-building-with-binary-13cb4289aafa">remember</a>? — which makes it super hard to read, write, and debug. The compiler abstracted away machine code for us as programmers, because it made it very easy for us to not think about machine code and write programs using far more elegant, clear, and easy-to-read languages.</p><p>We’ll continue to unpack more and more about the mysterious compiler over the next few weeks, which will hopefully make it less of an enigma in the process. But for now, let’s get back to the question at hand: what are the simplest possible parts of a compiler?</p><p>Each compiler, no matter how it might be designed, has distinct phases. These phases are how we can distinguish the unique parts of the compiler.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*AIvVRxpq2OIvE-l_xP-64Q.jpeg" /><figcaption>Syntax analysis: phase one of a compiler</figcaption></figure><p>We’ve already encountered one of the phases in our compilation adventures when we recently learned about <a href="https://medium.com/basecs/grammatically-rooting-oneself-with-parse-trees-ec9daeda7dad">the parser and parse trees</a>. We know that <em>parsing</em> is the process of taking some input and building a <em>parse tree</em> out of it, which is sometimes referred to as the act of <strong><em>parsing</em></strong>. As it turns out, the work of parsing is specific to a phase in the compilation process called <strong><em>syntax analysis</em></strong>.</p><p>However, the parser doesn’t just build a parse tree out of thin air. It has some help! We’ll recall that the parser is given some <em>tokens</em> (also called <em>terminals</em>), and it builds a parse tree from those tokens. But where does it get those tokens from? Lucky for the parser, it doesn’t have to operate in a vacuum; instead, it has some help.</p><p>This brings us to another phase of the compilation process, one that comes before the syntax analysis phase: <strong><em>the lexical analysis phase</em></strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*M4Aajot1rhEZ2ayQeinqww.jpeg" /><figcaption>The initial phases of a compiler</figcaption></figure><p>The term <em>“lexical”</em> refers to the meaning of a word in isolation from the sentence containing it, and regardless of its grammatical context. If we try to guess our own meaning based solely upon this definition, we could posit that the lexical analysis phase has to do with the individual words/terms in the program themselves, and nothing to do with the grammar or the meaning of the sentence that contains the words.</p><blockquote>The lexical analysis phase is the first step in the compilation process. It doesn’t know or care about the grammar of a sentence or the meaning of a text or program; all it knows about are the meaning of the words themselves.</blockquote><p>Lexical analysis must occur before any code from a source program can be parsed. Before it can be read by the parser, a program must first be scanned, split up, and grouped together in certain ways.</p><p>When we started looking at the <a href="https://medium.com/basecs/grammatically-rooting-oneself-with-parse-trees-ec9daeda7dad">syntax analysis phase</a> last week, we learned that the parse tree is built by looking at individual parts of the sentence and breaking down expressions into simpler parts. But during the lexical analysis phase, the compiler doesn’t know or have access to these “individual parts”. Rather, it has to first identify and find them, and then do the work of splitting apart the text into individual pieces.</p><p>For example, when we read a sentence from Shakespeare like To sleep, perchance to dream., we know that the spaces and the punctuation are dividing up the “words” of a sentence. This is, of course, because we’ve been trained to read a sentence, “lex” it, and parse it for grammar.</p><p>But, to a compiler, that same sentence might look like this the first time that it reads it: Tosleepperhachancetodream. When we read <em>this</em> sentence, it’s a little harder for us to determine what the actual “words” are! I’m sure our compiler feels the same way.</p><p>So, how does our machine deal with this problem? Well, during the lexical analysis phase of the compilation process, it always does two important things: it <strong><em>scans</em></strong> the code, and then it <strong><em>evaluates</em></strong> it.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3uLsp6ofW0yb5qW9xKGlYQ.jpeg" /><figcaption>The two steps of the lexical analysis process!</figcaption></figure><p>The work of scanning and evaluating can sometimes be lumped together into one single program, or it could be two separate programs that depend on one another; it’s really just a question of how any one complier happened to be designed. The program within the compiler which is responsible for doing the work of scanning and evaluating is often referred to as the <strong><em>lexer</em></strong> or the <strong><em>tokenizer</em></strong>, and the entire lexical analysis phase is sometimes called the process of <strong><em>lexing</em></strong> or <strong><em>tokenizing</em></strong>.</p><h3>To scan, perchance to read</h3><p>The first of the two core steps in lexical analysis is <strong><em>scanning</em></strong>. We can think of scanning as the work of actually “reading” some input text. Remember that this input text could be a string, sentence, expression, or even an entire program! It doesn’t really matter, because, in this phase of the process, it’s just a giant blob of characters that doesn’t mean anything just yet, and is one contiguous chunk.</p><p>Let’s look at an example to see how exactly this happens. We’ll use our original sentence, To sleep, perchance to dream., which is our <strong><em>source text</em></strong> or <strong><em>source code</em></strong>. To our compiler, this source text will be read as input text that looks like Tosleep,perchancetodream., which is just a string of characters that has yet to be deciphered.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*5Fqzasm9-6PLE9ty545k7Q.jpeg" /><figcaption>The scanning process, step 1.</figcaption></figure><p>The first thing our compiler has to do is actually divide up that blob of text into its smallest possible pieces, which will make it much easier to identify where the words in the blob of text actually are.</p><blockquote>The simplest way of diving up a giant chunk of text is by reading it slowly and systematically, one character at a time. And this is exactly what the compiler does.</blockquote><p>Oftentimes, the scanning process is handled by a separate program called the <strong><em>scanner</em></strong>, whose sole job it is to do the work of reading a source file/text, one character at a time. To our scanner, it doesn’t really matter how big our text is; all it will see when it “reads” our file is one character at a time.</p><p>Here’s what our Shakespearean sentence would be read as by our scanner:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3ZSNBRYAft5myw1KRnwr6Q.jpeg" /><figcaption>The scanning process, step 2.</figcaption></figure><p>We’ll notice that To sleep, perchance to dream. has been split into individual characters by our scanner. Furthermore, even the spaces between the words are being treated as characters, as is the punctuation in our sentence. There’s also a character at the end of this sequence that is particularly interesting: eof. This is the character “end of file”, and it’s similar to tab, space, and newline. Since our source text is just one single sentence, when our scanner gets to the end of the file (in this case, the end of the sentence), it reads the end of file and treats it as a character.</p><p>So, in actuality, when our scanner read our input text, it interpreted it as individual characters which resulted in this: [&quot;T&quot;, &quot;o&quot;, space, &quot;s&quot;, &quot;l&quot;, &quot;e&quot;, &quot;e&quot;, &quot;p&quot;, &quot;,&quot;, space, &quot;p&quot;, &quot;e&quot;, &quot;r&quot;, &quot;c&quot;, &quot;h&quot;, &quot;a&quot;, &quot;n&quot;, &quot;c&quot;, &quot;e&quot;, space, &quot;t&quot;, &quot;o&quot;, space, &quot;d&quot;, &quot;r&quot;, &quot;e&quot;, &quot;a&quot;, &quot;m&quot;, &quot;.&quot;, eof].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*5PLEk4PtvzHIrmbpxsQiAg.jpeg" /><figcaption>The scanning process, step 3.</figcaption></figure><p>Now that our scanner has read and split up our source text into its smallest possible parts, it will have a much easier time of figuring out the “words” in our sentence.</p><p>Next, the scanner needs to look at its split up characters in order, and determine which characters are parts of a word, and which ones are not. For each character that the scanner reads, it marks the line and the position of where that character was found in the source text.</p><p>The image shown here illustrates this process for our Shakespearean sentence. We can see that our scanner is marking the line and the column for each character in our sentence. We can think of the line and column representation as a matrix or array of characters.</p><p>Recall that, since our file has only one single line in it, everything lives at line 0. However, as we work our way through the sentence, the column of each character increments. It’s also worth mentioning that, since our scanner reads spaces, newlines, eof, and all punctuation as characters, those appear in our character table, too!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FcXbL37JCmMQU22HjZuFiQ.jpeg" /><figcaption>The scanning process, step 4.</figcaption></figure><p>Once the source text has been scanned and marked, our compiler is ready to turn these characters into words. Since the scanner knows not just where the spaces, newlines, and eof in the file are, but also where they live in relation to the other characters surrounding them, it can scan through the characters, and divide the them into individual strings as necessary.</p><p>In our example, the scanner will look at the characters T, then o, and then a space. When it finds a space, it will divide To into its own word — the simplest combination of characters possible before the scanner encounters a space.</p><p>It’s a similar story for the next word that it finds, which is sleep. However, in this scenario, it reads s-l-e-e-p, and then reads a ,, a punctuation mark. Since this comma is flanked by a character (p) and a space on either side, the comma is, itself, considered to be a “word”.</p><p>Both the word sleep and the punctuation symbol , are called <strong><em>lexemes</em></strong>, which are substrings the source text. A lexeme is a grouping of the smallest possible sequences of characters in our source code. The lexemes of a source file are considered the individual “words” of the file itself. Once our scanner finishes reading the single characters of our file, it will return a set of lexemes that look like this: [&quot;To&quot;, &quot;sleep&quot;, &quot;,&quot;, &quot;perchance&quot;, &quot;to&quot;, &quot;dream&quot;, &quot;.&quot;].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XyK9-EgmIrrbdGGNMbgLuw.jpeg" /><figcaption>The scanning process, step 5.</figcaption></figure><p>Notice how our scanner took a blob of text as its input, which it couldn’t initially read, and proceeded to scan it once character at a time, simultaneously reading and marking it the content. It then proceeded to divide the string into their smallest possible lexemes by using the spaces and punctuation between characters as delimiters.</p><p>However, despite all of this work, at this point in the lexical analysis phase, our scanner doesn’t know anything about these words. Sure, it split up the text into words of different shapes and sizes, but as far as what those words are the scanner has no idea! The words could be a literal string, or they could be a punctuation mark, or they could be something else entirely!</p><blockquote>The scanner doesn’t know anything about the words themselves, or what “type” of word they are. It just knows where the words end and begin within the text itself.</blockquote><p>This sets us up for the second phase of lexical analysis: evaluation. Once we’ve scanned our text and broken up the source code into individual lexeme units, we must evaluate the words that the scanner returned to us and figure out what types of words we’re dealing with — in particular, we must look for important words that mean something special in the language we’re trying to compile.</p><h3>Evaluating the important parts</h3><p>Once we’ve finished scanning our source text and identified our lexemes, we’ll need to do something <em>with </em>our lexeme “words”. This is the <strong><em>evaluation</em></strong> step of lexical analysis, which is often referred to in complier design as the process of <strong><em>lexing</em></strong> or <strong><em>tokenizing</em></strong> our input.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*GBeKPFlvWhAY8lmt6EenZw.jpeg" /><figcaption>What does it mean to evaluate the scanned code?</figcaption></figure><p>When we evaluate our scanned code, all we’re really doing is taking a closer look at each of the lexemes that our scanner generated. Our compiler will need to look at each lexeme word and decide what <em>kind</em> of word it is. The process of determining what kind of lexeme each “word” in our text is how our compiler turns each individual lexeme into a token, thereby tokenizing our input string.</p><p>We first encountered tokens back when we were learning about parse trees. Tokens are special symbols that are at the crux of each programming language. Tokens, such as (, ), +, -, if, else, then, all help a compiler understand how different parts of an expression and various elements relate to one another. The parser, which is central to the syntax analysis phase, depends on receiving tokens from <em>somewhere</em> and then turns those tokens into a parse tree.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BhXvgX-OXpUtSpsXO7rjXg.jpeg" /><figcaption>Tokens: a definition.</figcaption></figure><p>Well, guess what? We’ve finally figured out the “somewhere”! As it turns out, the tokens that get sent to the parser are generated in the lexical analysis phase by the <strong><em>tokenizer</em></strong>, also called the <strong><em>lexer</em></strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*QTDpT9GfXYbwnU2_h0_3lw.jpeg" /><figcaption>Tokenizing our Shakespearean sentence!</figcaption></figure><p>So what exactly does a token look like? A <strong><em>token</em></strong> is fairly simple, and is usually represented as a pair, consisting of a token name, and some value (which is optional).</p><p>For example, if we tokenize our Shakespearean string, we’d end up with tokens that would be mostly string literals and separators. We could represent the lexeme “dream” as a token like so: &lt;string literal, &quot;dream&quot;&gt;. In a similar vein, we could represent the lexeme . as the token, &lt;separator, .&gt;.</p><p>We’ll notice that each of these tokens aren’t modifying the lexeme at all — they’re simply adding additional information to them. A token is lexeme or lexical unit with more detail; specifically, the added detail tells us what category of token (what type of “word”) we’re dealing with.</p><p>Now that we’ve tokenized our Shakespearean sentence, we can see that there’s not all that much variety in the types of tokens in our source file. Our sentence only had strings and punctuation in it — but that’s just the tip of the token iceberg! There are plenty of other types of “words” that a lexeme could be categorized into.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8DR6f-Z9CzZJDeLmjpNO5Q.jpeg" /><figcaption>Common forms of tokens found within our source code.</figcaption></figure><p>The table shown here illustrates some of the most common tokens that our compiler would see when reading a source file in pretty much any programming language. We saw examples of literals, which can be any string, number, or logic/boolean value, as well as separators, which are any type of punctuation, including braces ({}) and parentheses (()).</p><p>However, there are also keywords, which are terms that are reserved in the language (such as if, var, while, return), as well as operators, which operate on arguments and return some value ( +, -, x, /). We could also encounter lexemes that could be tokenized as identifiers, which are usually variable names or things written by the user/programmer to reference something else, as well as comments, which could be line or block comments written by the user.</p><p>Our original sentence only showed us two examples of tokens. Let’s rewrite our sentence to instead read: var toSleep = &quot;to dream&quot;;. How might our compiler lex this version of Shakespeare?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*05UzHoMpYFIDKV-lHgpTqA.jpeg" /><figcaption>How will our lexer tokenize this sentence?</figcaption></figure><p>Here, we’ll see that we have a larger variety of tokens. We have a keyword in var, where we’re declaring a variable, and an identifier, toSleep, which is the way that we’re naming our variable, or referencing the value to come. Next is our =, which is an operator token, followed by the string literal &quot;to dream&quot;. Our statement ends with a ; separator, indicating the end of a line, and delimitating whitespace.</p><p>An important thing to note about the tokenization process is that we’re neither tokenizing any whitespace (spaces, newlines, tabs, end of line, etc.), nor passing it on to the parser. Remember that only the <em>tokens</em> are given to the parser and will end up in the parse tree.</p><p>It’s also worth mentioning that different languages will have different characters that constitute as whitespace. For example, in some situations, the Python programming language uses indentation — including tabs and spaces — in order to indicate how the scope of a function changes. So, the Python compiler’s tokenizer needs to be aware of the fact that, in certain situations, a tab or space actually does need to be tokenized as a word, because it actually <em>does</em> need to be passed to the parser!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*GcSKg37lnx2z5tLNfjBlvg.jpeg" /><figcaption>Constraints of the lexer vs the scanner.</figcaption></figure><p>This aspect of the tokenizer is a good way of contrasting how a lexer/tokenizer is different from a scanner. While a scanner is ignorant, and only knows how to break up a text into its smaller possible parts (its “words”), a lexer/tokenizer is much more aware and more precise in comparison.</p><p>The tokenizer needs to know the intricacies and specifications of the language that is being compiled. If tabs are important, it needs to know that; if newlines can have certain meanings in the language being compiled, the tokenizer needs to be aware of those details. On the other hand, the scanner doesn’t even know what the words that it divides even are, much less what they mean.</p><blockquote>The scanner of a complier is far more language-agnostic, while a tokenizer must be language-specific by definition.</blockquote><p>These two parts of the lexical analysis process go hand-in-hand, and they are central to the first phase of the compilation process. Of course, different compliers are designed in their own unique ways. Some compilers do the step of scanning and tokenizing in one single process and as a single program, while others will split them up into different classes, in which case the tokenizer will call out to the scanner class when it is run.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cD0IcZisXfPwd9suSlluZw.jpeg" /><figcaption>Lexical analysis: a quick visual summary!</figcaption></figure><p>In either case, the step of lexical analysis is super important to compilation, because the syntax analysis phase directly depends upon it. And even though each part of the compiler has its own specific roles, they lean on one another and depend on each other — just like good friends always do.</p><h3>Resources</h3><p>Since there are many different ways to write and design a compiler, there are also many different ways to teach them. If you do enough research on the basics of compilation, it becomes pretty clear that some explanations go into far more detail than others, which may or may not be helpful. If you find yourself wanting to learn more, below are a variety of resources on compilers — with a focus on the lexical analysis phase.</p><ol><li><a href="http://www.craftinginterpreters.com/scanning.html">Chapter 4 — Crafting Interpreters</a>, Robert Nystrom</li><li><a href="https://cs.nyu.edu/courses/fall06/G22.2130-001/class-notes.html">Compiler Construction</a>, Professor Allan Gottlieb</li><li><a href="http://www.cs.man.ac.uk/~pjj/farrell/comp3.html">Compiler Basics</a>, Professor James Alan Farrell</li><li><a href="https://www.youtube.com/watch?v=TG0qRDrUPpA">Writing a programming language — the Lexer</a>, Andy Balaam</li><li><a href="http://parsingintro.sourceforge.net/#table_of_contents_4">Notes on How Parsers and Compilers Work</a>, Stephen Raymond Ferg</li><li><a href="https://stackoverflow.com/questions/14954721/what-is-the-difference-between-a-token-and-a-lexeme">What is the difference between a token and a lexeme?</a>, StackOverflow</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=63d0be3d21d" width="1" height="1" alt=""><hr><p><a href="https://medium.com/basecs/reading-code-right-with-some-help-from-the-lexer-63d0be3d21d">Reading Code Right, With Some Help From The Lexer</a> was originally published in <a href="https://medium.com/basecs">basecs</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Grammatically Rooting Oneself With Parse Trees]]></title>
            <link>https://medium.com/basecs/grammatically-rooting-oneself-with-parse-trees-ec9daeda7dad?source=rss----9bf4a8406d1d---4</link>
            <guid isPermaLink="false">https://medium.com/p/ec9daeda7dad</guid>
            <category><![CDATA[compilers]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[theory-in-practice]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[data-structures]]></category>
            <dc:creator><![CDATA[Vaidehi Joshi]]></dc:creator>
            <pubDate>Mon, 20 Nov 2017 22:02:23 GMT</pubDate>
            <atom:updated>2017-11-24T03:48:52.284Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*yKjaulmzLsRxN4JBvy5Q2w.jpeg" /><figcaption>Grammatically rooting oneself with parse trees!</figcaption></figure><p>Thinking about all of the abstractions that surround us in the world of technology can sometimes be overwhelming. This is particularly true when you’re trying to wrap your head around a new paradigm or unpack the layers of one or many concepts that you’re struggling to understand.</p><p>In the context of learning computer science, there are simply too many abstractions to know, see, or recognize them all — not to mention being able to comprehend all of them!</p><p>Abstractions are powerful things when you can see beyond them, and being able to understand how something is abstracted away and why can make you a better programmer. However, by the same token, every abstraction was created for a reason: so that none of us would have to worry about them on a day-to-day basis! We’re not meant to think about abstractions all the time, and for the most part, very few of us actually do. Here’s the thing though — some abstractions are more equal than others. The ones that most engineers are probably concerned with are the ones that involve how they communicate with their computer, and the ways in which their computer actually <em>understands</em> them. Even if we none of us ever have to write <a href="https://medium.com/basecs/bubbling-up-with-bubble-sorts-3df5ac88e592">a bubble sort algorithm</a>, if we write code, then we have to communicate with our machines.</p><p>Well, it’s finally time for us to get to the bottom of these mysteries, and understand the abstractions which power our workflows as programmers.</p><h3>Parsing for the meaning of parsing</h3><p>The tree data structure is one that keeps coming up again and again in our computer science adventures. We’ve seen them used <a href="https://medium.com/basecs/how-to-not-be-stumped-by-trees-5f36208f68a7">to store data</a> of all types, we’ve seen ones that <a href="https://medium.com/basecs/busying-oneself-with-b-trees-78bbf10522e7">are self-balancing</a>, while others have been <a href="https://medium.com/basecs/compressing-radix-trees-without-too-many-tears-a2e658adb9a0">optimized for space</a> and handling storage. We’ve even looked at <a href="https://medium.com/basecs/painting-nodes-black-with-red-black-trees-60eacb2be9a5">how to manipulate trees</a> by rotating and recoloring them to ensure that they fit a set of rules.</p><p>But despite all of these different forms of data structure flora, there is one particular iteration of the tree data structure that we have yet to discover. Even if we knew nothing about computer science, how to balance a tree, or what a tree data structure even works, all programmers interact with one type of tree structure on a daily basis, by virtue of the simple fact that every developer who writes code needs to make sure that their code is understood by their machines.</p><p>This data structure is called the parse tree, and it is (one of) the underlying abstractions that allows the code that we write as programmers to become “readable” by our computers.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*RJYEISGZl2qUxAaHselQug.jpeg" /><figcaption>Parse tree: a definition.</figcaption></figure><p>At its very core, a <strong><em>parse tree</em></strong> is an illustrated, pictorial version of the grammatical structure of a sentence. Parse trees are actually rooted in the field of linguistics, but they’re also used in pedagogy, which is the study of teaching. Parse trees are often used to teach students how to identify the parts of a sentence, and are a common way of introducing grammatical concepts. It’s likely that we’ve each interacted with them from the persepctive of sentence diagramming, which some of us might have learned in elementary school.</p><blockquote>A parse tree is a really just a “diagrammed” form of a sentence; that sentence could be written in any language, which means that it could adhere to any set of grammatical rules.</blockquote><p>Sentence diagramming involves breaking up a single sentence into its smallest, most distinct parts. If we think about parse trees from the persepctive of diagramming sentences we’ll begin to quickly realize that, depending on the grammar and language of a sentence, a parse tree could really be constructed in a multitude of different ways!</p><p>But what exactly is a the computer version of a “sentence”? And how do we go about diagramming it, exactly?</p><p>Well, it helps to start with an example of something that we’re already comfortable with, so let’s refresh our memories by diagramming a normal, English sentence.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*zQ_bUppUhjPj3JjJ-uQv0w.jpeg" /><figcaption>Simple sentence diagramming with parse trees.</figcaption></figure><p>In the illustration shown here, we have a simple sentence: &quot;Vaidehi ate the pie&quot;. Since we know that a parse tree is just a diagrammed sentence, we can build a parse tree out of this example sentence. Remember that effectively all we’re trying to do is to determine the different parts of this sentence and break it up into its smallest, most distinct parts.</p><p>We can start by breaking up the sentence into two parts: a <strong><em>noun</em></strong>, &quot;Vaidehi&quot;, and a <strong><em>verb phrase</em></strong>, &quot;ate the pie&quot;. Since a noun cannot be broken down any further, we’ll leave the word &quot;Vaidehi&quot;, as it is. Another way to think about it is the fact that, since we can’t break down a noun any further, there will be no child nodes coming from this word.</p><p>But what about the verb phrase, &quot;ate the pie&quot;? Well, that phrase isn’t broken down into its simplest form yet, is it? We can dissect it down even further. For one thing, the word &quot;ate&quot; is a verb, while &quot;the pie&quot; is more of a noun — in fact, it’s a <strong><em>noun phrase</em></strong> to be completely specific. If we split up &quot;ate the pie&quot;, we can divide it into a verb and a noun phrase. Since a verb cannot be diagrammed with any additional detail, the word &quot;ate&quot; will become a leaf node in our parse tree.</p><p>Alright, so all that’s left now is the noun phrase, &quot;the pie&quot;. We can split this phrase up into two distinct pieces: a noun, &quot;pie&quot;, and its <strong><em>determiner</em></strong>, which is known as any modifying word of a noun. In this case, the determiner is the word &quot;the&quot;.</p><p>Once we divide up our noun phrase, we’re done splitting up our sentence! In other words, we’re done diagramming our parse tree. When we look at our parse tree, we’ll notice that our sentence still reads the same way, and we haven’t actually modified it at all. We just took the sentence we were given, and use the rules of English grammar to split it up into its smallest, most distinct parts.</p><blockquote>In the case of the English language, the smallest “part” of every sentence is a word; words can be combined into phrases, like noun phrases or verb phrases, which can, in turn, be joined with other phrases to create a sentence epression.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*c259fXm_B_Ak2n-9jAtFQg.jpeg" /><figcaption>What does it actually mean to parse something?</figcaption></figure><p>However, this is just one example of how one specific sentence, in one specific language, with its own set of grammatical rules would be diagrammed into a parse tree. This same sentence would look very different in a different language, especially if it had to follow its own set of grammatical rules.</p><p>Ultimately, the <em>grammar</em> and <em>syntax</em> of a language — including the way the sentences of that language are structured — become the rules that dictate how that language is defined, how we write in it, and how those of us who speak the language will end up understanding and interpreting it.</p><p>Interestingly, we knew how to diagram the simple sentence, &quot;Vaidehi ate the pie.&quot; because we were already familiar with the grammar of the English language. Imagine if our sentence was missing a noun or a verb altogether? What would happen? Well, we’d likely read the sentence the first time around and quickly realize that it wasn’t even a sentence at all! Rather, we’d read it, and almost immediately see that we were dealing with a <strong><em>sentence fragment</em></strong>, or an incomplete piece of a sentence.</p><p>However, the only reason that we’d be able to recognize a sentence fragment is if we knew the rules of the English language — namely, that (nearly) every sentence needs a noun and a verb to be considered valid. The grammar of a language is how we can check to see if a sentence is valid in a language; that process of “checking” for validity is referred to as <strong><em>parsing</em></strong> a sentence.</p><p>The process of parsing a sentence to understand it when we read it for the first time involves the same mental steps as diagramming a sentence, and diagramming a sentence involves the same steps as building a parse tree. When we read a sentence for the very first time, we’re doing the work of mentally deconstructing and parsing it.</p><p>As it turns out, computers do the exact same thing with the code that we write!</p><h3>Parsing expressions like it’s our job</h3><p>Okay, so we now know how to diagram and parse an English language sentence. But how does that apply to code? And what even is a “sentence” in our code?</p><p>Well, we can think of a parse tree as an illustrated “picture” of how our code looks. If we imagine our code, our program, or even just the simplest of scripts in the form of a sentence, we’d probably realize pretty quickly that all of the code that we write could really just be simplified into sets of expressions.</p><p>This makes a lot more sense with an example, so let’s look at a super simple calculator program. Using a single expression, we can use the grammatical “rules” of mathematics to create a parse tree from that expression. We’ll need to find the simplest, most distinct units of our expression, which means that we’ll need to break up our expression into smaller segments, as illustrated below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*PfSCFpmeTRe050GvziXgEA.jpeg" /><figcaption>Finding the grammar in mathematical expressions.</figcaption></figure><p>We’ll notice that a single mathematical expression has its own grammar rules to follow; even a simple expression (like two numbers being multiplied together and then added to another number) could be split up into even simpler expressions within themselves.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*pZQeACNRqVdegpDMP4nHfg.jpeg" /><figcaption>Representing mathematical expressions as a parse tree.</figcaption></figure><p>But let’s work with a simple calculation to start. How could we create a parse tree using mathematical grammar for an expression such as 2 x 8?</p><p>If we think about what this expression really looks like, we can see that there are three distinct pieces here: an expression on the left, an expression on the right, and an operation that multiplies the two of them together.</p><p>The image shown here diagrams out the expression 2 x 8 as a parse tree. We’ll see that the operator, x, is one piece of the expression that cannot be simplified any further, so it doesn’t have any child nodes.</p><p>The expression on the left and on the right could be simplified into its specific terms, namely 2 and 8. Much like the English sentence example we looked at earlier, a single mathematical expression could contain <em>internal expressions </em>within it, as well as individual <em>terms</em>, like the phrase 2 x 8, or <em>factors</em>, like the number 2 as an individual expression itself.</p><p>But what happens after we create this parse tree? We’ll notice that the hierarchy of child nodes here is a little less obvious than in our sentence example from before. both 2 and 8 are at the same level, so how could we interpret this?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kbeiQA0pBr--lGGSjdUg6A.jpeg" /><figcaption>The same expression could evaluate to different parse trees.</figcaption></figure><p>Well, we already know that there are various <a href="https://medium.com/basecs/demystifying-depth-first-search-a7c14cccf056">different ways to depth-first traverse</a> through a tree. Depending on how we traverse through this tree, this single mathematical expression, 2 x 8 could be interpreted and read in many ways. For example, if we traversed through this tree using <em>inorder</em> traversal, we’d read the left tree, the root level, and then the right tree, resulting in 2 -&gt; x -&gt; 8.</p><p>But if we chose to walk through this tree using <em>preorder</em> traversal, we’d read the value at the root level first, followed by the left subtree and then the right subtree, which would give us x -&gt; 2 -&gt; 8. And if we used <em>postorder</em> traversal, we’d read the left subtree, the right subtree, and then finally read the root level, which would result in 2 -&gt; 8 -&gt; x.</p><p>Parse trees show us what our expressions<em> look like</em>, revealing the concrete syntax of our expressions, which often means that a single parse tree could express a “sentence” in various different ways. For this reason, parse trees are also often referred to as <strong><em>Concrete Syntax Trees</em></strong>, or <strong><em>CSTs </em></strong>for short. When these trees are interpreted, or “read” by our machines, there need to be strict rules as to how these trees are parsed, so that we end up with the correct expression, with all the terms in the correct order and in the right place!</p><p>But most expressions that we deal with are more complex than just 2 x 8. Even for a calculator program, we will probably need to do more complicated computations. For example, what happens if we wanted to solve for an expression like 5 + 1 x 12? What would our parse tree look like?</p><p>Well, as it turns out, the trouble with parse trees is that sometimes you can end up with more than one.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XxrDw6GoUNu31tBBDAiA5Q.jpeg" /><figcaption>Ambiguous grammar in (parsing) action!</figcaption></figure><p>More specifically, there can be more than a single outcome for one expression that is being parsed. If we assume that parse trees are read from the lowest-level first, we can start to see how the heirarchy of the leaf nodes can cause the same expression to be interpreted in two totally different ways, yielding two totally different values as a result.</p><p>For example, in the illustration above, there are two possible parse trees for the expression 5 + 1 x 12. As we can see in the left parse tree, the heirarchy of the nodes is such that the expression 1 x 12 will be evaluated first, and then the addition will continue: 5 + (1 x 12). On the other hand, the right parse tree is very different; the heirarchy of the nodes forces the addition to happen first (5 + 1), and then moves up the tree to continue with multiplication: (5 + 1) x 12.</p><p>Ambiguous grammar in a language is exactly what causes this kind of situation: when its unclear how a syntax tree should be constructed, it’s possible for it to be built in (at least) more than one way.</p><blockquote>Here’s the rub, though: ambiguous grammar is problematic for a compiler!</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rJgijcOsPQ_0XQVnecxR6A.jpeg" /><figcaption>Combating ambiguous grammar as a compiler</figcaption></figure><p>Based on the rules of mathematics that most of us learned in school, we know inherently that multiplication should always be done before addition. In other words, only the left parse tree in the above example is actually correct based on the grammar of math. Remember: grammar is what defines the syntax and the rules of any language, whether its an English sentence or a mathematical expression.</p><p>But how on earth would the compiler know these rules inherently? Well, there’s just no way that it ever could! A compiler would have no idea which way to read the code that we write if we don’t give it grammatical rules to follow. If a compiler saw that we wrote a mathematical expression, for example, that could result in two different parse trees, it wouldn’t know which of the two parse trees to choose, and thus, it wouldn’t know how to even read or interpret our code.</p><p>Ambiguous grammar is generally avoided in most programming languages for this very reason. In fact, most parsers and programming languages will intentionally deal with problems of ambiguity from the start. A programming language will usually have grammar that enforces <em>precedence</em>, which will force some operations or symbols to have a higher weight/value than others. An example of this is ensuring that, whenever a parse tree is constructed, multiplication is given a higher precedence than addition, so that only one parse tree can ever be constructed.</p><p>Another way to combat problems of ambiguity is by enforcing the way that grammar is interpreted. For example, in mathematics, if we had an expression like 1 + 2 + 3 + 4, we know inherently that we should begin adding from the left and work our way to the right. If we wanted our compiler to understand how to do this with our own code, we’d need to enforce <em>left associativity</em>, which would constrict our compiler so that when it parsed our code, it would create a parse tree that puts the factor of 4 lower down in the parse tree hierarchy than the factor 1.</p><p>These two examples often referred to as <strong><em>disambiguating rules</em></strong> in compiler design, as they create specific syntactical rules ensure that we never end up with ambiguous grammar that our compiler will be very confused by.</p><h3>A token of my affection (for my parser)</h3><p>If ambiguity is the root of all parse tree evil, then clarity is clearly the preferred mode of operation. Sure, we can add disambiguating rules to avoid ambiguous situations that’ll cause our poor little computer to be stumped when it reads our code, but we actually do a whole lot more than that, too. Or rather, it is the programming languages that we use that do the real heavy lifting!</p><p>Let me explain. We can think of it this way: one of the ways that we can add clarity to a mathematical expression is through parenthesis. In fact, that’s what most of us probably would do for the expression we were dealing with earlier: 5 + 1 x 12. We probably would have read that expression and, recalling <a href="http://www.purplemath.com/modules/orderops.htm">the order of operations</a> we learned in school, we would have rewritten it in our heads as: 5 + (1 x 12). The parenthesis () helped us gain clarity about the expression itself, and the two expressions that are inherently <em>within</em> it. Those two symbols are recognizable to us, and if we were putting them in our parse tree, they wouldn’t have any children nodes because they can’t be broken down any further.</p><p>These are what we refer to as <strong><em>terminals</em></strong>, which are also commonly known as <strong><em>tokens</em></strong>. They are crucial to all programming languages, because they help us understand how parts of an expression relate to one another, and the syntactic relationships between individual elements. Some common tokens in programming include the operation signs (+, -, x, /), parenthesis (()), and reserved conditional words (if, then, else, end). Some tokens are used to help clarify expressions because they can specify how different elements relate to one another.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ou3ufTd15lrk1KCnfI_D3Q.jpeg" /><figcaption>Terminal symbols versus non-terminals</figcaption></figure><p>So what are all the other things in our parse tree? We clearly have more than just if&#39;s and + signs in our code! Well, we also usually have to deal with sets of <strong><em>non-terminals</em></strong>, which are expressions, terms, and factors that can potentially be broken down further. These are the phrases/ideas that contain other expressions within them, such as the expression (8 + 1) / 3.</p><p>Both terminals and non-terminals have a specific relationship to where they appear in a parse tree. As their name might suggest, a <em>terminal</em> symbol will always end up as the leaves of a parse tree; this means that not only are operators, parenthesis, and reserved conditionals “terminals”, but so are all the factor values that represent the string, number, or concept that is at every leaf node. Anything that is broken down into its smallest possible piece is effectively always going to be a “terminal”.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xDN2NTHNk9IwWIHLJP1aYw.jpeg" /><figcaption>Identifying the unique parts of a syntax tree.</figcaption></figure><p>On the flip side, the interior nodes of a parse tree — the non-leaf nodes that are parent nodes — are the <em>non-terminal </em>symbols, and they’re the ones that represent the applicaiton of the programming language’s grammar rules.</p><p>A parse tree becomes a lot easier to understand, visualize, and identify once we can wrap our heads around the fact that it is nothing more than a representation of our program, and all of the symbols, concepts, and expressions within it.</p><blockquote>But what is the value of a parse tree, anyways? We don’t think about it as programmers, but it must exist for a reason, right?</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*bepFrz6fuLOJqIvRxVnnyQ.jpeg" /><figcaption>Understanding the role of the parser</figcaption></figure><p>Well, as it turns out, the thing that cares about the parse tree the most is the <strong><em>parser</em></strong>, which is a part of a complier that handles the process of <em>parsing</em> all of the code that we write.</p><p>The process of <strong><em>parsing </em></strong>is really just taking some input and building a parse tree out of it. That input could be many different things, like a string, sentence, expression, or even an entire program.</p><p>Regardless of what input we give it, our parser will parse that input into grammatical phrases and building a parse tree out of it. The parser really has two main roles in the context of our computer and the compilation process:</p><ol><li>When given a valid sequence of tokens, it must be able to generate a corresponding parse tree, following the syntax of the language.</li><li>When given an invalid sequence of tokens, it should be able to detect the syntax error and inform the programmer who wrote the code of the problem in their code.</li></ol><p>And that’s really it! It might sound really simple, but if we start considering how massive and complex some programs can be, we’ll quickly start to realize how well-defined things need to be in order for the parser to actually fulfill these two seemingly easy roles.</p><p>For example, even a simple parser needs to do a lot in order to process the syntax of an expression like 1 + 2 + 3 x 4.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BGT3XX2Q3sIXed-CX4ruQg.jpeg" /><figcaption>Reading like a parser would read.</figcaption></figure><ul><li>First, it needs to build a parse tree out of this expression. The input string that the parser recieves might not show any association between operations, but the parser needs to make a parse tree that does.</li><li>However, in order to do this, it needs to know the syntax of the language, and the grammar rules to follow.</li><li>Once it can actually create a single parse tree (with no ambiguity), it needs to be able to pull out the tokens and non-terminal symbols and arrange them so that the parse tree’s heirarchy is correct.</li><li>Finally, the parser needs to ensure that, when this tree is evaluated, it will be evaluated from left to right, with operators of the same precedence.</li><li>But wait! It also needs to make sure that, when this tree is traversed using the inorder traversal method from the bottom, not a single syntax error ever occurs!</li><li>Of course, if it <em>does</em> break, the parser needs to look at the input, figure out where it will break, and then tell the programmer about it.</li></ul><p>If this feels like an awful lot of work, that’s because it is. But don’t worry too much about doing all of it, because that’s the parser job, and most of it is abstracted away. Luckily, the parser has some help from other parts of the compiler. More on that next week!</p><h3>Resources</h3><p>Lucky for us, compiler design is something that is well-taught in almost every computer science curriculum, and there are a decent number of solid resources out there to help us understand the different parts of a compiler, including a parser and the parse tree. However, as is the case with most CS content, a lot of it can be hard to digest — particularly if you’re not familiar with the concepts or the jargon that’s used. Below are some more beginner-friendly resources that still do a good job of explaining parse trees if you find yourself wanting to learn even more.</p><ol><li><a href="http://interactivepython.org/runestone/static/pythonds/Trees/ParseTree.html">Parse Tree</a>, Interactive Python</li><li><a href="http://www.cs.cornell.edu/courses/cs2110/2014fa/L21-ParsingTrees/cs2110fa14Parsing.pdf">Grammars, Parsing, Tree Traversals</a>, Professors David Gries &amp; Doug James</li><li><a href="https://ruslanspivak.com/lsbasi-part7/">Let’s Build A Simple Interpreter, Part 7</a>, Ruslan Spivak</li><li><a href="https://tomassetti.me/guide-parsing-algorithms-terminology/#parser">A Guide to Parsing: Algorithms and Terminology</a>, Gabriele Tomassetti</li><li><a href="http://www.cse.chalmers.se/edu/year/2011/course/TIN321/lectures/proglang-02.html">Lecture 2: Abstract and Concrete Syntax</a>, Aarne Ranta</li><li><a href="http://flint.cs.yale.edu/cs421/lectureNotes/c04.pdf">Compilers and Interpreters</a>, Professor Zhong Shao</li><li><a href="http://www.cs.man.ac.uk/~pjj/farrell/comp4.html">Compiler Basics — The Parser</a>, James Alan Farrell</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ec9daeda7dad" width="1" height="1" alt=""><hr><p><a href="https://medium.com/basecs/grammatically-rooting-oneself-with-parse-trees-ec9daeda7dad">Grammatically Rooting Oneself With Parse Trees</a> was originally published in <a href="https://medium.com/basecs">basecs</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Speeding Up The Traveling Salesman Using Dynamic Programming]]></title>
            <link>https://medium.com/basecs/speeding-up-the-traveling-salesman-using-dynamic-programming-b76d7552e8dd?source=rss----9bf4a8406d1d---4</link>
            <guid isPermaLink="false">https://medium.com/p/b76d7552e8dd</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[theory-in-practice]]></category>
            <category><![CDATA[dynamic-programming]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Vaidehi Joshi]]></dc:creator>
            <pubDate>Mon, 13 Nov 2017 17:44:01 GMT</pubDate>
            <atom:updated>2017-11-13T17:44:01.437Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*z0bh1NpQOueEW00MaJMj7g.jpeg" /><figcaption>Using dynamic programming to speed up the traveling salesman problem!</figcaption></figure><p>A large part of what makes computer science hard is that it can be hard to know where to start when it comes to solving a difficult, seemingly unsurmountable problem.</p><p>One of the reasons that some things can seem so tricky is that they’re multistep problems, and they involve us first understanding the problem, then considering the simplest solution, then iterating upon that solution to make it better, more efficient, and more elegant. I often think of the phrase that has been <a href="http://wiki.c2.com/?MakeItWorkMakeItRightMakeItFast">attributed to</a> Kent Beck who said, <em>“Make it work, make it right, make it fast.”</em></p><p>Some of the most complex problems in computer science are complex for <em>this</em> very reason: they involve these three distinct parts, and it can feel super overwhelming if we don’t consider these three steps as unique points in our problem-solving strategy. The complex problems are the ones where we are forced to step back, and try to break up our problem-solving process into a segmented process, rather than trying to magically find the perfect solution in one go. To be honest, finding the perfect solution in one go <em>rarely</em> actually ever happens.</p><p>We’ve covered some tricky topics throughout the course of this series, but one of the more complicated topics presented itself more recently when <a href="https://medium.com/basecs/the-trials-and-tribulations-of-the-traveling-salesman-56048d6709d">we encountered</a> the <strong>traveling salesman problem</strong> (<em>TSP</em>). Since we have already taken the first step of trying to find a solution to TSP that just works, we can now concern ourselves with the next steps: making it right (or more elegant), and hopefully a little bit faster.</p><h3>No Fun Factorials</h3><p>When we first <a href="https://medium.com/basecs/the-trials-and-tribulations-of-the-traveling-salesman-56048d6709d">stumbled upon</a> the traveling salesman problem, we were dealing with a salesman who had a fairly easy task: to visit four cities in some order, as long as he visited each city once and ended up at the same city that he started in.</p><p>Now, the reason that this was an “easy” task, so to speak, was simply because of the fact that visiting four cities isn’t really a lot to do. In algorithmic terms, we were able to solve this problem and find the shortest path for our salesman using a brute-force technique, combined with recursion. We <a href="https://medium.com/basecs/the-trials-and-tribulations-of-the-traveling-salesman-56048d6709d">were able to determine</a> that the brute-force approach was, by definion, a factorial algorithm. In our example, we determined that, for a salesman who needs to visit four cities would mean making 3! or “three factorial” function calls, which equals 6.</p><p>We also started realizing that the factorial runtime of the brute-force technique for solving TSP was going to be unscalable over time. In fact, we realized that it was going to be unscalable almost <em>immediately</em>! For example, what would happen when our traveling salesman needed to visit not just <em>four</em> cities, but <em>five</em> cities? When we were dealing with four cities, we made six recursive calls. So, adding one extra city shouldn’t be too difficult, right? After all, it’s just <em>one</em> city.</p><p>Well, not exactly. Here’s how our algorithm scales from just four cities, to five:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*y9dqvqHKYDo6C4u5pLUmtw.jpeg" /><figcaption>How a factorial algorithm scales from an input of 4 elements to 5 elements.</figcaption></figure><p>When our salesman only had to visit four cities, we made six recursive calls. But now, we have literally <em>quadrupled </em>our tree of “potential paths”, which seems really, really, <em>really</em> bad. Solving TSP for five cities means that we need to make 4! or four factorial recursive calls using the brute-force technique. As it turns out, 4! equals 24, which means we have to now make 24 recursive calls in order to accomodate just one additional city in our traveling salesman’s map.</p><p>If we compare the illustrated version of the “tree” of recursive function calls from <a href="https://medium.com/basecs/the-trials-and-tribulations-of-the-traveling-salesman-56048d6709d">our previous example of TSP</a> to the one that is drawn above, we start to get a pretty good idea of just <em>how</em> unsustainable a factorial algorithm really is.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*iEo2Qd3BhZVVkUZQaoHuRA.jpeg" /><figcaption>O(n!) runtime is unsustainable.</figcaption></figure><p>We have seen quite a few different forms of Big O Notation throughout this series, including the good and the bad. So, where do factorial algorithms fit into this narrative?</p><blockquote>If constant, logarithmic, and linear time are good, and quadratic and exponential time are bad, there is only one thing left to explore: the ugly. Factorial algorithms are exactly that: the ugly.</blockquote><p>For an algorithm that runs in <strong><em>factorial</em></strong>, or <strong>O(n!)</strong> time, any operations that need to run will end up taking n! more time in relation to the data that is being operated upon, or the input data set.</p><p>Okay, but what does this <em>actually</em> mean? Well, let’s look at how a factorial algorithm compares to all the other forms of Big O Notation that we’re already familiar with.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*tXDAZzUr_Iijsc1kSTtzxA.jpeg" /><figcaption>Factorial time is super slow and inefficient as input size grows</figcaption></figure><p>We’ll notice almost immediately that algorithms that grow in factorial time are super slow and ineffcient as input size grows. For example, we’ll see that even a slight increase in the number of elements to be operated upon by a factorial algorithm causes it to shoot up in the number of operations required to run. If we compare this to linearithmic, linear, or even just <em>quadratic</em> time algorithms— which are still pretty bad in their own right — we’ll see that factorial algorithms are obsecenely terrible in comparison!</p><p>All of this is to say: our first approach to solving TSP using brute-force recursion is probably not the best solution. Yes, it works, but it’s probably not as “right” as it could be; it could stand to be improved, and surely could be made more elegant. And, of course, it is not fast — at all!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*f77LCDnUvy8apcEvp_K1sA.jpeg" /><figcaption>Using brute-force takes a top-down approach to solving TSP.</figcaption></figure><p>So, how can we improve upon this first attempt that we made?</p><p>Well, if we <a href="https://medium.com/p/43d29830a630">think back to our foray</a> into <strong><em>dynamic programming</em></strong> (<em>DP</em>), we’ll remember that there is more than one approach when it comes to solving a DP problem. In our initial stab at this problem, we attempted to solve TSP using a kind of <strong><em>top down approach</em></strong>: we started with a large, complex problem, and broke it down into smaller parts. Then, when we got down to our base case, and expanded the problem down to its smallest possible parts, we used recursion to build up all the possible paths that our traveling salesman could take, which allowed us to choose the best (the shortest) permutation of all the paths that we had found.</p><p>In the process, we figured out one way to solve the traveling salesman problem. But what if we approached it a different manner? What would happen if we took our top down approach and turned it upside down?</p><p>There’s only one way to find out — we have to try it out!</p><h3>Turning TSP on its head</h3><p>If we look at our top down methodology <a href="https://medium.com/basecs/the-trials-and-tribulations-of-the-traveling-salesman-56048d6709d">from last week</a>, we’ll see that we have enumerated through all of the permutations of paths — that is to say, we have brute-forced our way to determine every single route that our traveling salesman could take.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*c5cw35mBFfgzn_T9LOh3zA.jpeg" /><figcaption>The brute-force approach to solving TSP.</figcaption></figure><p>This methodology isn’t particularly elegant, is kind of messy, and, as we have already determined, will simply never scale as our input size grows. But ignoring all of those issues for a moment, let’s just take a look at this “tree” of recursive function calls once again.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*AfNmG7Pwmgoz5LpZWBehHA.jpeg" /><figcaption>Rethinking the brute-force approach by identifying the simplest problem, or function call.</figcaption></figure><p>On second glance, we’ll notice that there is something interesting going on here: we’re starting with the more complex function call initially, and then, from within that, we are invoking three recursive function calls from <em>within</em> it. Each of those three recursive function calls spins off two more recursive calls of its own, which creates the third level of this function call “tree”. This is, of course, keeping in tune with our working definition of a <em>top down</em> approach: starting with the largest problem first, and breaking it down into its smallest parts. But, now that we can see the smallest parts more obviously, we can change our approach from a top down method to a bottom up method.</p><p>We’ll recall that a <strong><em>bottom up</em></strong> <a href="https://medium.com/basecs/less-repetition-more-dynamic-programming-43d29830a630">dynamic programming approach</a> starts with the smallest possible subproblems, figures out a solution to them, and then slowly builds itself up to solve the larger, more complicated subproblem. In the context of our “function call tree”, the smallest possible subproblem are the smallest possible function calls. We’ll see that the smallest function calls are the simplest ones — the ones that have <em>no recursive calls</em> within them. In our case, these are the function calls at the very bottom of our “function call tree”, which lead back to our starting node, node w, which is the city that our traveling salesman is “starting” from, and will inevitably have to “end” up at.</p><p>Now that we’ve identified the smallest possible subproblems, we can turn TSP on its head. We’ll flip our top down approach to this problem and, instead, use a bottom up approach here. Let’s start with our three simplest function calls.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*dntlyP4aeSTG_esnkc2d3A.jpeg" /><figcaption>Flipping TSP on its head, part 1.</figcaption></figure><p>We’ll see that each of these calls connects back to w, as we would expect. Recall that we’re using <a href="https://medium.com/basecs/the-trials-and-tribulations-of-the-traveling-salesman-56048d6709d">a list notation </a>to keep track of the nodes that we can navigate to. Since we’re dealing with the smallest possible subproblem(s), there is nowhere that we can navigate to from these nodes; instead, all we can do is go back to our starting node, w. This is why each of the lists for these three subproblems is empty ({}).</p><p>However, we do need to keep track of cost and distance here, since inevitably, we’re still going to have to find the shortest path for our traveling salesman, regardless of whether we’re using a<em> top down</em> or <em>bottom up</em> approach. Thus, we’re going to have to keep track of the distance between nodes as we build up our “bottom up” tree. In the image above, we’ll see that we have the values 6, 1, and 3 next to nodes x, y, and z, respectively. These number represent the distance to get from each node back to the origin node, w.</p><p>When we first tried to solve TSP, <a href="https://medium.com/basecs/the-trials-and-tribulations-of-the-traveling-salesman-56048d6709d">we used an adjacency matrix</a> to help us keep track of the distances between nodes in our graph. We’ll lean on our adjacency matrix in this approach yet again.</p><p>However, in our bottom up approach, we’ll use it to enumerate all the function calls that lead to one another. This is strikingly different than our top down approach, when we were using our adjacency matrix to help us enumerate all the possible paths. In our bottom up approach, we’re trying to be a bit more elegant about how we do things, so we’re aiming to not enumerate more than we need to! This will make more sense as we go on, but it’s important to note the difference between enumerating <strong><em>paths</em></strong> versus enumerating <strong><em>function calls</em></strong>.</p><p>So, what would the second level of our function call “tree” look like? Well, the question that we’re trying to answer for each of our smallest possible subproblems here is this:</p><blockquote>If we are at the simplest possible version of this function call and cannot call anything recursively from within this function, what other function could possibly call this one?</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lSe5hl_WEQSri3qMrj4XEQ.jpeg" /><figcaption>Flipping TSP on its head, part 2.</figcaption></figure><p>Another way of thinking about it is in terms of nodes. Ultimately, we’re trying to determine which possible nodes would allow us to get to the node that we’re looking at. So, in the case of node x, the only way to get to node x would potentially be node y or node z. Remember that we’re using a bottom up approach here, so we’re almost retracing our steps backwards, starting at the end, and working our way back through the circle.</p><p>Notice, again, that we’re keeping track of the cost/distance from each of these nodes to the next. We’re going to need them pretty soon!</p><p>Again, we can expand this function call “tree” a bit more to add another level. Remember, we’re trying to answer the question:<em> what other function could possibly call this function that we cannot expand any further?</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*NaFUeDIty0V0uP2kCXXiAA.jpeg" /><figcaption>Flipping TSP on its head, part 3.</figcaption></figure><p>In the drawing depicted here, we’ll see what this actually looks like in practice. For example, looking at the leftmost branch of this function call “tree”, we’ll notice that the only possible function call that will allow us to get to an empty node x is from either node y or node z, where the set contains only a possible “next” node of x, like so: {x}. For both node y and z in the leftmost subtree, we’ll see that the only possible way to get to y is from node z, when the set contains both x and y (or {x, y}). Similarly, the only possible way to get to z is from node y, when the set contains both x and z (or {x, z}).</p><p>This is a visualization exemplifies what we mean when we say that we are enumerating <em>function calls</em> rather than enumerating <em>potential paths</em>. As we continue to determine all the possible function calls that allow us to call other functions from within them, something starts to become very obvious: we have some overlapping subproblems here!</p><p>We’ll notice that there are two function calls that are instances of z when its set contains both x and y (or {x, y}), which is highlighted in yellow. Similarly, there are two function calls that are instances of y when its set contains both x and z (or {x, z}), highlighted in pink. Finally, we’ll see two function calls that are instances of x when its set contains both y and z (or {y, z}), highlighted in green.</p><p>Dynamic programming is all about identifying repeated work and being smarter and more efficient with our approach so that we don’t actually have to repeat ourselves! So, let’s cut out this repetition and use some dynamic programming to make things a little better for our traveling salesman.</p><h3>Dynamic programming to the salesman’s rescue</h3><p>Now that we’ve identified our overlapping and recurring subproblems, there’s only one thing left to do: eliminate the repetition, of course!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3JkCyvTr_kB_k6rNDahtOg.jpeg" /><figcaption>Flipping TSP on its head, part 4.</figcaption></figure><p>Using our function call “tree”, we can rearrange some of our function calls so that we’re not actually repeating ourselves in level three of this tree.</p><p>We can do this by cutting down our repeated subproblems so that they only show up once. Then, we’ll reconfigure the bottom level of our tree so that it is still <em>accurate</em>, but also that we each function call show up <em>once</em>, not twice.</p><p>Now it starts to become apparent how the bottom up approach is different than our top down method from before.</p><p>We’ll see that we no longer need to do the work of generating that entire bottom level of our function call “tree” in order to figure out all o the recursive function calls. Nor do we need to determine all the possible paths that our traveling salesman could take by using brute force. Instead, we’re enumerating through function calls, finding the repeated ones, and condensing our “tree” of function calls as we continue to build it.</p><p>Once we’ve eliminated the repeated subproblems, we can do the work of actually finding the shortest path. Remember that we will need to use our adjacency matrix to figure out the distance between one node to another. But, we’ll also notice that we’re not having to repeat ourselves nearly as much because we won’t see the same numbers appear too many times as we sum them up.</p><p>In the illustration shown below, each of the function calls that allow our salesman to traverse from one node to another has a number (the cost or distance) associated with it. As we continue down this tree, we’ll sum up the cost of each set of function calls. For example, if we choose the function calls that lead from w &lt;- x &lt;- y &lt;- z, we’ll sum up the cost between these nodes, which amounts to 6 + 4 + 2 = 12.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cVce4K1c8rGrYRPZ1pukvg.jpeg" /><figcaption>Flipping TSP on its head, part 5.</figcaption></figure><p>When we get down to the third level of our function call “tree”, we’ll see that we have two numbers that we can choose from. Recall that we had a similar scenario happen to us in <a href="https://medium.com/basecs/the-trials-and-tribulations-of-the-traveling-salesman-56048d6709d">our top down approach</a> last week: we had two different paths with two different costs/distances to choose from. We ended up choosing the smaller of the two cost, since we’re trying to find the shortest path for our salesman. In this case, we have two different function calls, with two different costs/distances to choose from. Again, we’ll choose the smaller of the two costs, since we’re still trying to find the shortest path here, too!</p><p>Eventually, as we continue sum the distances/costs, we’ll see that we ended up witht he exact same results as our <a href="https://medium.com/basecs/the-trials-and-tribulations-of-the-traveling-salesman-56048d6709d">brute-force method</a> from last week. The shortest cost for our traveling salesman is going to be 11, and there are two possible paths that would allow for them to achieve that lowest cost. However, using the bottom up approach, we’ve optimized our TSP algorithm, since we no longer have six recursive calls being made in this method. Furthermore, we’re also not generating as big of a tree structure! If we think back to when we were first <a href="https://medium.com/basecs/less-repetition-more-dynamic-programming-43d29830a630">introduced to dynamic programming</a>, we’ll recall that we could also use <strong><em>memoization</em></strong> and save the results of our function calls as we calculate them, optimizing our solution even further.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*6BeiicyA4WKW0o5xdZNROA.jpeg" /><figcaption>Using dynamic programming makes our 5 city example a little faster.</figcaption></figure><p>Okay, so we started down this path in an effort to take the next step in the adage of “<em>Make it work, make it right, make it fast</em>.”</p><p>We have arguably made our workable solution much better, and certainly more elegant, and far less repetitive. The illustration shown here exemplifies how the bottom up DP approach would scale for a traveling salesman problem where the salesman has to visit five cities instead of four. We’ll see that we’re still making a lot of calls, but our function call “tree” is a bit slimmer and significantly better than before.</p><p>By using dynamic programming, we’ve made our solution for the traveling salesman problem just a little bit better by choosing to smartly enumerate function calls rather than brute-force our way through every single possible path that our salesman could take.</p><p>The only question we have to answer now is, of course, how does the runtime of this method compare to our ugly factorial, O(n!) runtime from earlier?</p><p>Well, as it turns out, the bottom up approach that we’ve been exploring here is really the foundations of something called the <strong><em>Held-Karp algorithm</em></strong>, which is also <a href="https://en.wikipedia.org/wiki/Held–Karp_algorithm">often referred to</a> as the <strong><em>Bellman-Held-Karp algorithm</em></strong>. This algorithm was derived in 1962, by both Michael Held and Richard M. Karp as well as Richard Bellman, who was working independently on his own related research at the time.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*gDVVEwuqs-y0oqztvvo80A.jpeg" /><figcaption>The Held-Karp algorithm uses dynamic programming to approach TSP.</figcaption></figure><p>The Held-Karp algorithm actually proposed the bottom up dynamic programming approach as a solution to improving the brute-force method of solving the traveling salesman problem. Bellman, Held, and Karp’s algorithm was determined to run in <strong><em>exponential</em></strong> time, since it still does a bulk of the work of enumerating through all the potential sets of function calls that are possible. The exponential runtime of the Held-Karp algorithm is still not perfect — it’s far from it, in fact! But, it’s not as ugly as a factorial algorithm, and it’s still an improvement.</p><p>And, to be honest, I’m sure the traveling salesman would be happy to take whatever he could get.</p><h3>Resources</h3><p>The traveling salesman problem has been written about, researched, and taught extensively. As it turns out, there are many different approaches when it comes to attempting to solve it, and the Held-Karp algorithm is just one of them. If you want to dig deeper into this particular topic, here are some good places to start.</p><ol><li><a href="https://www.youtube.com/watch?v=_51ot-Ri0ng">Travelling Salesman Problem</a>, 0612 TV w/ NERDfirst</li><li><a href="https://www.youtube.com/watch?v=-JjA4BLQyqE">Traveling Salesman Problem Dynamic Programming Held-Karp</a>, Tushar Roy</li><li><a href="https://stackoverflow.com/questions/210829/what-is-an-np-complete-in-computer-science">What is an NP-complete in computer science?</a>, StackOverflow</li><li><a href="http://www.kestrelblackmore.com/blog/big-o-notation-complexity">Big O Notation and Complexity</a>, Kestrel Blackmore</li><li><a href="https://www.coursera.org/learn/algorithms-npcomplete/lecture/uVABz/a-dynamic-programming-algorithm-for-tsp">A Dynamic Programming Algorithm for TSP</a>, Coursera</li><li><a href="https://www.intechopen.com/books/traveling-salesman-problem-theory-and-applications/traveling-salesman-problem-an-overview-of-applications-formulations-and-solution-approaches">Traveling Salesman Problem: An Overview of Applications, Formulations, and Solution Approaches</a>, Rajesh Matai, Surya Singh, and Murari Lal Mittal</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b76d7552e8dd" width="1" height="1" alt=""><hr><p><a href="https://medium.com/basecs/speeding-up-the-traveling-salesman-using-dynamic-programming-b76d7552e8dd">Speeding Up The Traveling Salesman Using Dynamic Programming</a> was originally published in <a href="https://medium.com/basecs">basecs</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Announcing the basecs podcast! ]]></title>
            <link>https://medium.com/basecs/announcing-the-basecs-podcast-97c8e4454d7?source=rss----9bf4a8406d1d---4</link>
            <guid isPermaLink="false">https://medium.com/p/97c8e4454d7</guid>
            <dc:creator><![CDATA[Vaidehi Joshi]]></dc:creator>
            <pubDate>Wed, 08 Nov 2017 13:28:24 GMT</pubDate>
            <atom:updated>2017-11-08T13:28:24.367Z</atom:updated>
            <content:encoded><![CDATA[<p>Dear <em>basecs</em> reader,</p><p>As we near this year-long project of trying to unpack and understand the basics of computer science, I waned to share some good and bad news.</p><p>I’ll start with the bad news first: it’s (somehow) already November! There are only a handful of posts left in this series, which is equal parts amazing and bittersweet. Somehow, this entire year flew by. I guess that’s what happens when you’re busy reading about the traveling salesman problem.</p><p>Okay, the good news next: over the past few months, I’ve been working on a few different collaborations to help expand <em>basecs</em> and bring it to even more communities, populations, and people from around the world.</p><blockquote>I’m thrilled to finally get to share one of these exciting new collaborations with you: the basecs podcast.</blockquote><p>The <a href="https://www.codenewbie.org/basecs"><strong>basecs podcast</strong></a> is a project I dreamed up with my dear friend and fellow developer, <a href="https://twitter.com/saronyitbarek">Saron Yitbarek</a>, the creator of the <a href="https://twitter.com/CodeNewbies">Codenewbies community</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/896/1*a7_Dylw_FRjbkoUgnpsIgQ.png" /><figcaption>Subscribe to the <a href="https://www.codenewbie.org/basecs">basecs podcast</a>!</figcaption></figure><p>A large part of the reason I started <em>basecs</em> was in an effort to make computer science a more welcoming, friendly, and approachable world to navigate. I’m so stoked to be teaming up with Saron in to produce a podcast that is educational, interesting, fun to listen to, and <em>always </em>very<em> </em>friendly!</p><p>I hope that this podcast will build upon the foundation and community that <em>basecs</em> has created by opening doors and welcoming more folks into our industry by helping them fall in love with the wonders of computer science.</p><p>You can subscribe to the basecs podcast <a href="https://www.codenewbie.org/basecs">here</a>, and listen to Episode 1 now! If you like what you hear, I hope you’ll consider sharing it with your friends, family, and coworkers — and maybe leave us a review. 😎</p><p>Thank you again for your continued readership and support.</p><p>With gratitude,<br>Vaidehi</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=97c8e4454d7" width="1" height="1" alt=""><hr><p><a href="https://medium.com/basecs/announcing-the-basecs-podcast-97c8e4454d7">Announcing the basecs podcast! 😍</a> was originally published in <a href="https://medium.com/basecs">basecs</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The Trials And Tribulations Of The Traveling Salesman]]></title>
            <link>https://medium.com/basecs/the-trials-and-tribulations-of-the-traveling-salesman-56048d6709d?source=rss----9bf4a8406d1d---4</link>
            <guid isPermaLink="false">https://medium.com/p/56048d6709d</guid>
            <category><![CDATA[tech]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[theory-in-practice]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Vaidehi Joshi]]></dc:creator>
            <pubDate>Mon, 06 Nov 2017 21:07:57 GMT</pubDate>
            <atom:updated>2017-11-13T15:07:55.841Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jMNwKMBZLT4eUb0cGtEamw.jpeg" /><figcaption>The trials and tribulations of the traveling salesman!</figcaption></figure><p>As we dive deeper and deeper into the world of computer science, one thing starts to become very clear, very quickly: some problems seem to show up again and again, in the strangest of forms. In fact, some of the most famous problems in the history of computer science have no specific origin that anyone knows of. Instead, the same problem shows up in different forms and avatars, in different places around the world, at different time periods.</p><p>The hardest problems in software are the most fun to solve — and some of them haven’t even been figured out yet! One of these hard problems is the traveling salesman problem, and depending on whom you ask, it might be the most notorious of them all.</p><p>I first heard about the traveling salesman problem a few years ago, and it seemed super daunting to me at the time. To be totally honest, even coming back to it now, it still feels a little bit daunting, and it might seem scary to you, too. But something is different this time around: we’ve got a whole wealth of knowledge and context to draw from! Throughout this series, we’ve been building upon our foundation core of computer science, and returning to some of the same concepts repeatedly in an effort to understand them on a more technical level — but only when we feel fully equipped to do so. The same goes for this look into the the traveling salesman problem.</p><p>In order to understand why this problem is so notorious, we need to wrap our heads around what it is, how we can solve it, why it is important, and what makes it so hard. It might sound overwhelming, but we’ll get through it together, one step at a time.</p><p>So, let’s hop to it!</p><h3>Geometry, circuits, and a dude named Hamilton</h3><p>The idea behind the <strong><em>traveling salesman problem</em></strong> (<em>TSP</em>) is rooted in a rather realistic problem that many people have probably actually encountered. The thesis is simple: a salesman has to travel to every single city in an area, visiting each city only once. Additionally, he needs to end up in the same city where he starts his journey from.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*by3MgdkmamEAxlCaIH68Xg.jpeg" /><figcaption>The traveling salesman seeks to visit each city once, and end up in the same place he started.</figcaption></figure><p>The actual “problem” within the traveling salesman problem is finding the most <em>efficient</em> route for the salesman to take. There are obviously many different routes to choose from, but finding the best one — the one that will require the least cost or distance of our salesman — is what we’re solving for.</p><p>In more ways than one, the practical aspects of this problem are reminscient of <a href="https://medium.com/basecs/k%C3%B6nigsberg-seven-small-bridges-one-giant-graph-problem-2275d1670a12">The Seven Bridges of Königsberg</a>, a mathematical problem that we’re already familiar with, which was the basis for Euler’s invention of the field called “the geometry of position”, which we now know today as <em>graph theory</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/373/1*qhkJNlAZPzcqhbh08tkLnQ.png" /><figcaption>William Rowan Hamilton, <a href="https://en.wikipedia.org/wiki/William_Rowan_Hamilton#/media/File:William_Rowan_Hamilton_portrait_oval_combined.png">Wikimedia Commons</a></figcaption></figure><p>But graph theory didn’t end with Euler and the city of Königsberg! Indeed, the Seven Bridge problem was just the beginning, and the traveling salesman problem is a prime example of someone building upon the ideas of those who came before him.</p><p>The “someone” in this scenario is none other than <a href="https://en.wikipedia.org/wiki/William_Rowan_Hamilton">William Rowan Hamilton</a>, an Irish physicist and mathematician who was inspired by and subsequently continued the research of mathematicians who came before him in order to create a subset of mathematical problems that are directly tied to the traveling salesman problem that we are familiar with today.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BkKwcorM1hLalRcGbZZGlQ.jpeg" /><figcaption>Comparing Eulerian and Hamiltonian paths.</figcaption></figure><p>In the late 1800’s, both Hamilton and the British mathematician <a href="https://en.wikipedia.org/wiki/Thomas_Kirkman">Thomas Kirkman</a> were working on mathematical problems that were fundamentally similar to TSP. Hamilton’s claim to fame was his work on deriving a something called a <strong><em>Hamiltonian path</em></strong>, which bears resemblance to Euler’s famous <a href="https://medium.com/basecs/königsberg-seven-small-bridges-one-giant-graph-problem-2275d1670a12">Eulerian path</a>.</p><p>While a Eulerian path is a path where every single edge in a graph is visited once, a Hamiltonian path is one where every single <em>vertex</em> is visited exactly once.</p><p>By the same token, a Eulerian circuit is a Eulerian path that ends at the same vertex where it began, touching each <em>edge</em> once. A <strong><em>Hamiltonian circuit</em></strong>, on the other hand, is a Hamiltonian path that ends at the same vertex where it began, and touches each <em>vertex</em> exactly once.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*zEjo3E2FWo02ptzgwermRA.jpeg" /><figcaption>TSP as a Hamiltonian circuit problem.</figcaption></figure><p>A good rule of thumb to determine whether a path through a graph is Hamiltonian or Eulerian is this:</p><blockquote>in a <strong><em>Hamiltonian path</em></strong>, every edge doesn’t need to be visited, but every node must visited — but only once! In comparison, in an <em>Eulerian path</em>, some vertices could be visited multiple times, but every edge can only ever be visited once.</blockquote><p>The reason that Hamilton’s work, which is built upon Euler’s formulations, comes up in the context of the famous traveling salesman problem is that the job of the salesman — traveling to each city exactly once and ending up where he began — is really nothing more than a graph problem!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9TQJJIkru11AQv8ZETrMgw.jpeg" /><figcaption>The icosian game, invented by W.R. Hamilton in the 1800&#39;s.</figcaption></figure><p>Hamilton’s work expanded graph theory to the point where he was actually solving the TSP before it was really a thing. Hamilton invented a game that was similar to the traveling salesman problem, which he called the <strong><em>icosian game</em></strong>, whose objective was to find a path through the points of a dodecahedron, or a polygon with 12 flat faces.</p><p>Hamilton’s game was eventually turned into an actual board game. And, if we think about it, even the icosian game is really just another variation on the traveling salesman problem! Just as as dodecahedron has 20 vertices, we could imagine Hamilton’s game as a map of 20 cities. Using this analogy, our traveling salesman would need to find a way through 20 cities, visiting each city once, and ending up exactly where he started.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*rrK4wDKr3NIaQmgrHkkNoA.jpeg" /><figcaption>Hamilton’s icosian game, © <a href="http://puzzlemuseum.com/month/picm02/200207icosian.htm">Puzzle Museum</a></figcaption></figure><p>Thus, the traveling salesman problem can really just be reformulated to be represented as a graph. Luckily, we have <a href="https://medium.com/basecs/a-gentle-introduction-to-graph-theory-77969829ead8">covered</a> <a href="https://medium.com/basecs/from-theory-to-practice-representing-graphs-cfd782c5be38">a whole</a> <a href="https://medium.com/basecs/spinning-around-in-cycles-with-directed-acyclic-graphs-a233496d4688">lot</a> <a href="https://medium.com/basecs/deep-dive-through-a-graph-dfs-traversal-8177df5d0f13">of different</a> <a href="https://medium.com/basecs/finding-the-shortest-path-with-a-little-help-from-dijkstra-613149fbdc8e">topics</a> when it comes to <a href="https://medium.com/basecs/going-broad-in-a-graph-bfs-traversal-959bd1a09255">complex graphs</a>. We’ve got a solid foundation to build upon, just like Hamilton did!</p><p>Once we’re able to wrap our heads around the fact that the traveling salesman problem is really just a graph traversal problem, we can start getting down to business. In other words, we can start trying to <em>solve</em> this problem. For our purposes, we won’t worry ourselves with trying to get the best solution or using the most efficient approach. Instead, we’ll start by simply trying to get some kind of solution to begin with. Using the old adage <a href="http://wiki.c2.com/?MakeItWorkMakeItRightMakeItFast">attributed to</a> Kent Beck, we must first “Make it work” before we can even begin to think about making it “right” or “fast”.</p><p>So, let’s get to work and get our salesman on the road!</p><h3>Brute-force to begin with</h3><p>The traveling salesman in our example problem has it pretty lucky — he only has to travel between four cities. For simplicity’s sake, we’ll call these four cities w, x, y, and z. Because we know that TSP is a graph problem, we can visualize our salesman’s possible routes in the form of <strong><em>a weighted, undirected graph</em></strong>. We’ll recall that a <em>weighted</em> graph is one whose edges have a cost or distance associated with them, and an <em>undirected</em> graph is one whose edges have a bidirectional flow.</p><p>Looking at an illustrated example of our salesman’s graph, we’ll see that some routes have a greater distance or cost than others. We’ll also notice that our salesman can travel between any two vertices easily.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*JyVtzhhK457Vy-bzqLrasQ.jpeg" /><figcaption>How can we solve for the optimal path starting and ending at node <em>w</em>?</figcaption></figure><p>Let’s say that our salesman lives in city w, so that’s where he’ll start his journey from. Since we’re looking for a Hamiltonian cycle/circuit, we know that this is also where he will need to end up at the end of his adventures. So, how can we solve for the optimal path so that our salesman starts and ends at city (node) w, but also visits every single city (x, y, and z) in the process?</p><p>Remember, we’re not going to think about the most efficient strategy — just one that <em>works</em>. Since we’re going to use the brute-force approach, let’s think about what we’re really trying to solve for here. The brute-force approach effectively means that we’ll solve our problem by figuring out every single possiblity and then picking the best one from the lot. In other words, we want to find every single <strong><em>permutation</em></strong> or <strong><em>possible path</em></strong> that our salesman could take. Every single of one of these potential routes is basically a directed graph in its own right; we know that we’ll start at the node w and end at w, but we just don’t know quite yet which order the nodes x, y, and z will appear in between.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*w-c1ODaPnL0_whMkFJ6VcA.jpeg" /><figcaption>Every permutation is, on its own, a directed graph.</figcaption></figure><p>So, we need to solve every single possible combination to determine the different ways that we could arrange x, y, and z to replace the nodes that are currently filled with ?’s. That doesn’t seem <em>too </em>terrible.</p><p>But how do we actually solve for these ? nodes, exactly? Well, even though we’re using a less-than-ideal brute-force approach, we can lean on <em>recursion</em> to make our strategy a little more elegant.</p><blockquote>The basic idea in the recursive TSP approach is that, for every single node that we visit, we keep track of the nodes that we can navigate to next, and then recursively visit them.</blockquote><p>Eventually, we’ll end up with no more nodes to check, which will be our recursive base case, effectively ending our recursive calls to visit nodes. Don’t worry if this seem complicated and a little confusing at the moment; it will become a lot clearer with an example. So, let’s recursively brute-force our way through these cities and help our salesman get home safe and sound!</p><p>We already know that our salesman is going to start at node w. Thus, this is the node we’ll start with and visit first. There are two things we will need to do for every single node that we visit — we’ll need to remember the fact that we’ve visited it, and we’ll need to keep track of the nodes that we can <em>potentially</em> visit next.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*r5RXUFUftZkZklwlveAmiw.jpeg" /><figcaption>Generating recursive calls for TSP, part 1.</figcaption></figure><p>Here, we’re using a list notation to keep track of the nodes that we can navigate to from node w. At first, we can navigate to three different places: {x, y, z}.</p><p>Recall that recursion is basically the idea that a “function calls itself from within itself”. In other words, as part of solving this problem, we’re going to have to apply the same process and technique to every single node, again and again. So that’s exactly what we’ll do next! For every single node that we can potentially navigate to, we will recursively visit it.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0ozT9ohr3dB3e4gIYSqh_Q.jpeg" /><figcaption>Generating recursive calls for TSP, part 2.</figcaption></figure><p>Notice that we’re starting to create a tree-like structure. For each of the potential nodes to visit from the starting node w, we now have three potential child “paths” that we could take. Again, for each of these three vertices, we’re keeping track of the node itself that we’re visiting as well as any potential nodes that we can visit next, which haven’t already been visited in that path.</p><p>Recursion is about repetition, so we’re going to do the same thing once again! The next step of recursion expands our tree once again.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*EJgeCEQoLtpsCWsQmR_21Q.jpeg" /><figcaption>Generating recursive calls for TSP, part 3.</figcaption></figure><p>We’ll notice that, since each of the three nodes x, y, and z had two nodes that we could potentially visit next, each of them have spawned of two of their own recursive calls. We’ll continue to make recursive calls in the same way and, in the process, we’ll start to see that we’re creating different permutations using the same nodes.</p><p>We’ll notice that we’re now at the third level of recursive calls, and each node has only one possible place to visit next. We can probably guess what happens next — our tree is going to grow again, and each of the bottom-level nodes is going to spawn a single recursive call of its own, since each node has only one unvisited vertex that it can potentially check.</p><p>The image shown below illustrates the next two levels of recursive calls.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*zRPUKxE8zHwD1axNiD0dpA.jpeg" /><figcaption>Generating recursive calls for TSP, part 4.</figcaption></figure><p>Notice that, when we get to the fourth level of child nodes, there is nowhere left to visit; every node has an empty list ({} ) of nodes that it can visit. This means that we’ve finished recursively checking for all permutations of paths.</p><blockquote>However, since we’re solving for a Hamiltonian cycle, we aren’t exactly done with each of these paths just yet. We know we want to end back where we started at node w, so in reality, each of these last recurisvely-determined nodes needs to link back to vertex w.</blockquote><p>Once we add node w to the end of each of the possible paths, we’re done expanding all of our permutations! Hooray! Remember how we determined earlier that every single of one of these potential routes is just a directed graph? All of those directed graphs have now revealed themselves. If we start from the root node, w, and work down each possible branch of this “tree”, we’ll see that there are six distinct paths, which are really just six directed graphs! Pretty cool, right?</p><p>So, what comes next? We’ve expanded all of these paths…but how do we know which one is the shorted one of them all?</p><p>We haven’t really been considering the cost or distance of this weighted graph so far, but that’s all about to change. Now that we’ve expanded this problem and found all of its possible permutations, we need to consider the total cost of each of these paths in order to find the shortest one. This is when an adjacency matrix representation of our original graph will come in handy. Recall that an <strong><em>adjacency matrix</em></strong> is <a href="https://medium.com/basecs/from-theory-to-practice-representing-graphs-cfd782c5be38">a matrix representation</a> of exactly <em>which</em> nodes in a graph contain edges between them. We can tweak our typical adjacency matrix so that, instead of just 1’s and 0’s, we can actually store the weight of each edge.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ftd4VZ4Gs25pXZyOi0bwIw.jpeg" /><figcaption>We can use an adjacency matrix to help us keep track of edge costs/distances.</figcaption></figure><p>Now that we have an adjacency matrix to help us, let’s use it to do some math — some <em>recursive</em> math, that is!</p><h3>Mirror mirror on the wall, which is the shortest path of them all?</h3><p>In order to determine which of these six possible paths is the shortest one — and thus the ideal choice for our salesman — we need to build up the cost of every single one of these paths.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lvnpHMLSdbg_QmVbez9dYQ.jpeg" /><figcaption>Calculating recursive costs using recursion for TSP, part 1.</figcaption></figure><p>Since we’ve used recursion to expand these paths until we hit our base case of “no more nodes left to visit”, we can start to close up these recursive calls, and calculate the cost of each path along the way.</p><p>Once we know the cost between two vertices, we can sum the distance between them, and the remove the node from the tree. This will make more sense with an example, so let’s work our way from the lowest-level of this tree until we have found a solution for the shortest path.</p><p>We know that every single one of these branches — each of which represents a permutation of this particularly problem — ends with the node that we started on: node w. We’ll start with node w, and calculate the cost for our salesman to travel there.</p><p>Well, since our salesman <em>starts at</em> node w, the cost of traveling to node w is actually just 0. This makes sense if we think about it, because our salesman is already <em>at</em> that vertex, so it isn’t going to “cost” him anything to travel there! So, the math for the bottom level is pretty easy — the cost to get from w to w is 0. Next, we’ll apply the same technique again, but this time, we’ll move one level up.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*LowOjtCs8n1RVh9RtioZkA.jpeg" /><figcaption>Understanding the logic behind recursive addition for TSP.</figcaption></figure><p>For example, if we refer to our adjacency matrix from the previous section, we’ll see that the cost of traveling from w to z is 3. Since we’re traveling from w —&gt; w —&gt; z, we can sum the distances between each of these vertices as we go. Traveling from w —&gt; w is 0, and traveling from w —&gt; z is 3, so we are essentially calculating 0 + 3. In a similar vein, the cost from z to y is 2. So, we will need to calculate w —&gt; w —&gt; z -&gt; y, which is 0 + 3 + 2.</p><p>The drawing below illlustrates how this addition slowly works its way up the tree, condensing the recursive calls that built it up in the first place.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*dD5z1tCS4nz36H3-HsbRGw.jpeg" /><figcaption>Calculating recursive costs using recursion for TSP, part 2.</figcaption></figure><p>Through this process, we’re effectively building up the cost or distance of each path, one level at a time, using our tree structure. Each time that we sum the distance between two nodes, we can remove the bottom node (the deeper of the two nodes being added together) from the tree, since we don’t need to use it anymore.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3d9wGCv2i6wUUlN2b8V27A.jpeg" /><figcaption>Calculating recursive costs using recursion for TSP, part 3.</figcaption></figure><p>It is worth mentioning that <strong><em>we need to keep track of each of these paths</em></strong>, even after we finish doing the work of adding up their costs. For the sake of brevity, the paths themselves are not included in the illustrations shown here. However, it is crucial to keep track of which nodes were at the bottom of the tree — otherwise, we’d lose the entire path itself!</p><p>We will continue this process, but at some point, an odd thing is going to happen. In the next iteration of this recursive addition, we’ll notice that we come to an interesting fork in the road — literally! When we reach the third level and have condensed the bottom part of the tree, we have two possible options of how we can proceed with our additon.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*oK6wk5WUGgWiL8CaheTpig.jpeg" /><figcaption>Calculating recursive costs using recursion for TSP, part 4.</figcaption></figure><p>For example, looking at the child paths/branches from node x, we could either sum the distance from x to y, or we could sum the distance from x to z. So, how do we decide which one to choose?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*zKlrzo-c-Nior11lE6KEjw.jpeg" /><figcaption>Calculating recursive costs using recursion for TSP, part 5.</figcaption></figure><p>Our gut instinct would tell us that we’re looking for the <em>shortest path</em>, which probably means that we’ll want to choose the <em>smaller </em>of the two values. And that’s exactly what we’ll do! We’ll choose the path from z leading back to x, since the cost of that path is 6, which is definitely smaller than the path from y leading back to x, which is 9.</p><p>Once we’ve chosen the smallest of the two paths in our “fork in the road”, we are left with just three paths. All that’s left to do is to figure out the total cost of from x to w, y to w, and z to w. Referring to our adjacency matrix, we’ll see that these distances are 6, 1, and 3, respectively.</p><p>We can add these to the total costs of the paths that we’ve been recursively summing this whole time. In the illustration above, we’ll see that the three shortest paths that we’ve determined are actually noted down for convenience. As it turns out, there is one path that costs 12, and two paths that both cost 11. One of those travels from w to y, and takes the route of w -&gt; y -&gt; x -&gt; z -&gt; w, while the other travels from w to z, and takes the route of w -&gt; z-&gt; x -&gt; u -&gt; w.</p><blockquote>Since two of our three paths are equivalently small in size, it doesn’t really matter which one we choose; both of them are the “shortest path” in solving the traveling salesman problem.</blockquote><p>And there we have it! We’ve solved for a Hamiltonian circuit by finding the shortest path, with a distance/cost of 11, that starts and ends at node w.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cYNjGZIwvWtH8cvQDuuPXA.jpeg" /><figcaption>We’ve solved for a Hamiltonian circuit!</figcaption></figure><p>Solving that was pretty awesome, right? It seemed super daunting at first, but as we worked through it, it got easier with each step. But here’s the thing: we had to take a <em>lot</em> of steps to do this. We knew from the beginning that we weren’t going to have the most elegant solution to this problem — we were just trying to get <em>something</em> working. But just how painful is the brute-force method, exactly?</p><p>Well, what if instead of a salesman who has to travel to four cities, we were trying to help out a salesman who had to travel to a whole lot more cities? What if the number of cities that they had to visit was n? How bad would our brute-force technique be?</p><p>Well, in our first example, n = 4. We’ll recall that, since we had already visited our first city (node w), we only had to make three recursive calls. In other words, we had to make 4 — 1, or n — 1 recursive calls.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*tC2-pOQxqooCSkEWmpib7g.jpeg" /><figcaption>Solving for n cities in the TSP.</figcaption></figure><p>But, for each of those recursive calls, we had to spawn off two more recursive calls! That is to say, for each potential city that we <em>could</em> visit from the three nodes x, y, and z, we had 4 — 2 = 2 options of paths to take. In abstract terms, we’d effectively have n — 2 recursive calls at the next level of our tree.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*v3p7WJqal4mvqhG_CKf6Jg.jpeg" /><figcaption>Building up an unscalable “n factorial” problem.</figcaption></figure><p>If we continue figuring out this math, we’ll see that, at each level of the tree, we are basically on the path to finding a number that is going to be a factorial. To be more specific, we’re going to end up with n!, or <strong><em>n factorial</em></strong>.</p><p>Now, when we were dealing with a salesman who needed to visit just four cities, this really wasn’t too terrible of scenario to deal with. But, what happens when n is something much, much larger than 4? Most salesmen and women aren’t going to be traveling just to four cities; in almost every realistic case, n is going to be a much larger number!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*VrIcOkBbzUAowT5U-IThFQ.jpeg" /><figcaption>The traveling salesman is not a fan of factorial algorithms!</figcaption></figure><p>Well, to get a sense of how unscalable a factorial algorithm is, we needn’t increase the value of n by all that much. For example, when n = 4, we made 3! or 6 recursive calls. But if we had increased this only slightly so that n = 5, we would make 4! or 24 recursive calls, which would lead to a much, much larger tree. And what about when n = 10? That would result in 9! recursive calls, which is a really huge number: 362,880 to be exact. We probably can’t even imagine what would happen if our salesman had to travel to every city in the country, or even just 10 cities for that matter!</p><p>Surely, there must be a better way of helping our traveling salesman out so that he’s not traveling forever? Well, there certainly is. But more on that next week. In the meantime, someone should really tell this salesman about eBay — it would probably save him a whole lot of heartache!</p><h3>Resources</h3><p>Unsurprisingly, there are many resources on the traveling salesman problem. However, not all of them are necessarily easy to understand! Some of them dive deep into the theory and mathematics of the problem, and it can be hard to find beginner-friendly content. Here are a few resources that are fairly easy to understand, and a good place to get started if you’re looking to learn more about TSP!</p><ol><li><a href="https://www.youtube.com/watch?v=_51ot-Ri0ng">Travelling Salesman Problem</a>, 0612 TV w/ NERDfirst</li><li><a href="https://www.youtube.com/watch?v=BAejnwN4Ccw">Coding Challenge #35.1: Traveling Salesperson</a>, The Coding Train</li><li><a href="http://www.math.uwaterloo.ca/tsp/history/index.html">History of TSP</a>, University of Waterloo, Department of Mathematics</li><li><a href="http://cs.indstate.edu/~zeeshan/aman.pdf">The Traveling Salesman problem</a>, Professor Amanur Rahman Saiyed</li><li><a href="http://www.theorsociety.com/Pages/ORMethods/Heuristics/articles/HistoryTSP.aspx">A brief History of the Travelling Salesman Problem</a>, Nigel Cummings</li><li><a href="https://books.google.com/books?id=JBK_BAAAQBAJ&amp;pg=PA1&amp;lpg=PA1&amp;dq=karl+menger+messenger&amp;source=bl&amp;ots=kXpnLrQ-0N&amp;sig=A2KptpUYHRStauw4WRN7UcjYb9A&amp;hl=en&amp;sa=X&amp;ved=0ahUKEwi419-si6nXAhUNwWMKHafyDkYQ6AEIPDAC#v=onepage&amp;q=karl%20menger%20messenger&amp;f=false">The Traveling Salesman Problem and Its Variation</a>, Gregory Gutin and Abraham P. Punnen</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=56048d6709d" width="1" height="1" alt=""><hr><p><a href="https://medium.com/basecs/the-trials-and-tribulations-of-the-traveling-salesman-56048d6709d">The Trials And Tribulations Of The Traveling Salesman</a> was originally published in <a href="https://medium.com/basecs">basecs</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Less Repetition, More Dynamic Programming]]></title>
            <link>https://medium.com/basecs/less-repetition-more-dynamic-programming-43d29830a630?source=rss----9bf4a8406d1d---4</link>
            <guid isPermaLink="false">https://medium.com/p/43d29830a630</guid>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[tech]]></category>
            <category><![CDATA[data-structures]]></category>
            <dc:creator><![CDATA[Vaidehi Joshi]]></dc:creator>
            <pubDate>Tue, 24 Oct 2017 16:28:50 GMT</pubDate>
            <atom:updated>2017-10-24T20:26:58.078Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Y1IuqrkoDWLlfz_BSaesGQ.jpeg" /><figcaption>Less repetition, more dynamic programming!</figcaption></figure><p>One of the running themes throughout this series has been the idea of making large, complex problems, which at first may seem super intimidating, feel so much more approachable. If we want to get really meta about it, that’s what the mission of this entire series is, really: to make the complexities of computer science seem fun, friendly, and thus, far more approachable!</p><p>But even on a microcosmic level, we’ve done this in many ways for each topic that we’ve covered. We dissected complex data structures like <a href="https://medium.com/basecs/stacks-and-overflows-dbcf7854dc67">stacks</a> and <a href="https://medium.com/basecs/to-queue-or-not-to-queue-2653bcde5b04">queues</a> and chiseled them down into their <a href="https://medium.com/basecs/whats-a-linked-list-anyway-part-1-d8b7e6508b9d">smaller moving parts</a>. We worked our way up to complex algorithms by understanding and slowly and systematically building upon <a href="https://medium.com/basecs/sorting-out-the-basics-behind-sorting-algorithms-b0a032873add">the little pieces</a> that these larger algorithms are all based upon.</p><p>Well, guess what? This technique is <em>far</em> from unique. In fact, it’s probably one of the most commonly-used approaches to problem solving in the world of computer science! Breaking down a problem into smaller, more bite-sized parts is something that computer scientists and programmers alike have been doing for decades. This method is tried, tested, and repeatedly been proven to be true. It’s so commonplace that it has its own name: <em>dynamic programming</em>. Even if you’ve never heard of this term before, there’s a good chance that you’ve either used dynamic programming or are already somewhat familiar with its core concepts.</p><p>For our purposes, dynamic programming is particularly useful to understand in the context of algorithm design. We’ve dealt with a whole lot of algorithms over the course of this series, from <a href="https://medium.com/basecs/sorting-out-the-basics-behind-sorting-algorithms-b0a032873add">sorting algorithms</a>, to <a href="https://medium.com/basecs/going-broad-in-a-graph-bfs-traversal-959bd1a09255">traversal algorithms</a>, to <a href="https://medium.com/basecs/finding-the-shortest-path-with-a-little-help-from-dijkstra-613149fbdc8e">path-finding algorithms</a>. However, we haven’t really talked about the ways that these algorithms are <em>constructed</em>. Not to worry — all of that changes today. It’s time for us to put our designer hats on for a change, and dive into the delicate intricacies of designing algorithms using the principles of dynamic programming.</p><p>Let’s get to it!</p><h3>Paradigms of algorithm design</h3><p>The term dynamic programming (abbreviated as “DP”)<strong><em> </em></strong>has a reputation for sounding for more intimidating than what it actually<em> </em>is. I think a large part of this has to do with its name, which — to me at least — <em>sounds</em> really complicated. But we’ll come back to the name a bit later. Let’s start with a definition in order to try to wrap our heads around what on earth “dynamic programming” means.</p><p>A helpful way to think about dynamic programming is by remembering that it is always tied to <strong><em>optimization</em></strong>, which is the idea that an algorithm should always choose the best possible element at any given time, regardless of whether it is sorting, searching, traversing through a structure, or finding a path. Because dynamic programming is rooted in optimization, this term is interchangeable with the term <strong><em>dynamic optimization</em></strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*JNku-HwwDHeeh4GFrSIjRA.jpeg" /><figcaption>Dynamic programming: a definition</figcaption></figure><p>But how exactly is dynamic programming or dynamic optimization connected to optimizing an algorithm? In other words, what does this form of algorithm design do to optimize an algorithm?</p><p>Well, at the end of the day, a <strong><em>dynamic programming algorithm</em></strong> solves a complex problem by breaking it down into its smaller parts. After a DP algorithm breaks down a problem into smaller pieces, it stores the results to these subproblems after computing them once.</p><p>This definition might sound really vague and unclear at first, but I promise that it will make a lot more sense if we compare it to other algorithm design paradigms!</p><p>There are two approaches to designing algorithms that we’ve already seen in this series. One of them we know by name: the <strong><em>divide and conquer algorithm</em></strong>. We learned about divide and conquer back when we were first introduced to the <a href="https://medium.com/basecs/making-sense-of-merge-sort-part-1-49649a143478">merge sort algorithm</a>. We’ll recall that a divide &amp; conquer algorithm divides a problem into simpler versions of itself, and then applies the same solution that it use on the smaller, subproblems to the larger problem itself. If we think back to when we learned about <a href="https://medium.com/basecs/making-sense-of-merge-sort-part-2-be8706453209">merge sort</a>, we’ll remember how the algorithm combined the answers to its subproblems and used recursion to merge elements together, while sorting them. This is also a characteristic of d&amp;c algorithms.</p><p>But our knowledge of algorithm design doesn’t just end with the divide and conquer approach. Last week, we learned about <a href="https://medium.com/basecs/finding-the-shortest-path-with-a-little-help-from-dijkstra-613149fbdc8e">Dijkstra’s algorithm</a>, which chooses the best vertex to visit as it searches for the optimal shortest path between two vertices. As it turns out, Dijkstra’s algorithm is an example of a different algorithm design paradigm: <em>the greedy algorithm</em>.</p><p>Algorithms like Dijkstra’s algorithm are considered to be <strong><em>greedy algorithms</em></strong> because they choose the best possible option in the moment, which is often referred to as the “greedy choice”. Greedy algorithms make the optimal choice on a local level — that is to say, the make the most efficient choice at each stage, optimistically hoping that, if they choose the best option at each point, eventually, they’ll arrive at the “global optimal choice”.</p><blockquote>Greedy algorithms make the best choice in the moment, and then solve whatever subproblems arise from the choice that they made. One consequence of making “greedy choices” as an algorithm is that the algorithm chooses the best option it can, and never goes back to reconsider its choice. Ultimately, this means that a greedy algorithm can very well find a solution that is actually not the most optimal choice!</blockquote><p>Dijkstra’s algorithm is a prime example of a greedy algorithm, since it picks which vertex to visit next based on the results that it stores at each step. We’ll recall from<a href="https://medium.com/basecs/finding-the-shortest-path-with-a-little-help-from-dijkstra-613149fbdc8e"> last week’s deep dive</a> into Dijkstra’s algorithm, that the algorithm looks at which vertex has the shortest <em>currently known</em> path based on each vertex’s edge weight, and then visits that vertex next.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7CqabkxWsGCTx0O-dT19Lg.jpeg" /><figcaption>Dijkstra’s algorithm is considered to be greedy!</figcaption></figure><p>Dijkstra’s algorithm never searches through <em>all</em> of the paths. It isn’t exhaustive in its search; it doesn’t reconsider its choices once it makes them, which means that it won’t search through all of the “subproblems” of vertices that it chose not to visit. This can sometimes end up being problematic, because the algorithm could very well not find the most optimal path if it finds a vertex with the shortest path at an early stage, and then proceeds to go down the path of visiting its neighbors.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7K58T11lmYsr1lCbWZwAxw.jpeg" /><figcaption>Different paradigms and approaches to algorithmic design.</figcaption></figure><p>Okay, so we have <em>divide and conquer</em> algorithms, and we have <em>greedy</em> algorithms. But, let’s get back to the problem at hand: understanding how <em>dynamic programming</em> algorithms compare to these two!</p><p>If we compare these three forms of algorithm design to one another, we’ll start to see that there are some obvious similarities (as well as some evident differences) between DP algorithms and its two counterparts.</p><p>Looking at the table illustrated above, we can see that DP algorithms are similar to divide and conquer in one obvious way: they both involve breaking down a large problem into smaller, simpler subproblems.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*n1OiJAzmWqC_Rh-S_LT5Bw.jpeg" /><figcaption>Dynamic programming compared to divide and conquer.</figcaption></figure><p>However, we’ll see one major difference between the dynamic programming approach and the divide and conquer one, too. In the DP paradigm, when we break down the larger problem into its smaller parts, those subproblems actually <em>overlap.</em></p><p>Here’s another way to think about it: the subproblems in a dynamic programming algorithm are recurring, and will repeat themselves. In the DP approach, the larger problem is solved by solving and remember overlapping subproblems. In contrast, overlapping subproblems aren’t a requirement for the divide and conquer approach.</p><p>So, how does dynamic programming compare to the greedy algorithm paradigm?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*e4oXyRfOtSA8xzpfN4yD4A.jpeg" /><figcaption>Dynamic programming compared to the greedy algorithm paradigm.</figcaption></figure><p>Well, for starters, both approaches have to make choices (ideally the optimal choice) at each stage that the two respective algorithms run. This is often referred to as using an <strong><em>optimal substructure</em></strong>, which refers to the idea that the optimal solution that the algorithm finds will, by proxy, contain the best solution(s) for each of the subproblems inside of it.</p><p>However, both of these paradigms approach the problem of “making the best choice possible” in starkly different ways.</p><p>As we’ve already learned, the greedy algorithm makes an initial greedy choice, and then continues to make the best choice at each stage, setting itself up to solve only one subproblem of the larger, more complex problem. Dynamic programming is very different; the DP paradigm finds the optimal solution for <em>every single subproblem</em>, and chooses the best option from all of the subproblems.</p><p>A simpler way to think about how dynamic programming algorithms compare to greedy algorithms is this:</p><blockquote>a DP algorithm will exhaustively search through all of the possible subproblems, and then choose the best solution based on that. Greedy algorithms only search through one subproblem, which means they’re less exhaustive searches by definition.</blockquote><p>This brings us to an important question: how on earth do dynamic programming algorithms do the work of searching so extensively? How exactly do DP algorithms keep track of all of the overlapping subproblems?</p><p>It’s time for us to investigate.</p><h3>Remember to remember</h3><p>We already know that dynamic programming is akin to the divide and conquer in that it involves subproblems and breaking down things into easier to calculate pieces. But, we also know that DP algorithms can calculate every single overlapping subproblem that occurs — in other words, if many subproblems exist, it can calculate all of them, and then pick the best one out of the bunch as its final solution.</p><blockquote>The trick to calculating all of the solutions to the various subproblems (and then choosing the best one) is <em>remembering previous solutions.</em></blockquote><p>Let’s use a simple example to illustrate what I mean. Imagine we had to solve the problem 5 + 5 + 5 + 5. How would we solve that? Well, we’d just add them up, right? We know that 5 + 5 + 5 + 5 = 20. Done.</p><p>But then, what if we just tacked on another 5 at the end of that? 5 + 5 + 5 + 5 + 5 = ?. Mentally, what would we do? Would we add each 5, one after the other, again and again?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Z-7LZACVp_O9HcU0fYWnzA.jpeg" /><figcaption>How to think about dynamic programming!</figcaption></figure><p>No way! We’d probably just think to ourselves, <em>“Oh, I just did that math. I know it was 20 before, and now there’s another 5, so the answer must be 25!”.</em> We remembered the solution for a problem that we had previously solved before, and used it again when we had to solve a problem that <em>built upon </em>it.</p><p>Dynamic programming does something similar to what we just mentally worked through in that simple math problem. It <strong><em>remembers</em> </strong>the subproblems that it has seen and solved before. When it sees the same subproblem again — which is what we call an <strong><em>overlapping subproblem</em></strong> — it knows that it doesn’t need to recalculate the work multiple times. It just pulls from the solution that it figured out previously!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Uiv1z3FSKhH0H46HPKqriA.jpeg" /><figcaption>Dynamic programming allows us to avoid repeating ourselves.</figcaption></figure><p>The power of dynamic programming is that it allows us to avoid repeating ourselves, and thereby avoid repeating bits of work by remembering partial portions of problems that we have already solved along the way. The ability to <em>not repeat ourselves</em> sounds nice, but it really helps to see it in action. There’s a well-known example that’s used again and again to illustrate how powerful DP algorithms are, and we’re going to look at that very example next. The good news is that we’re already familiar with this famous example: it’s our dear old friend, <a href="https://medium.com/basecs/finding-fibonacci-in-golden-trees-1c8967b1f47a">the Fibonacci sequence</a>!</p><p>We’ll recall that the Fibonacci sequence, which is closely tied to the golden ratio, is the sequence of numbers that starts with 0 and 1. In order to derive any number in the Fibonacci sequence, we need to find and sum the two numbers that precede that number.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*vQNNf_dvx5bvtG_4b5uMsA.jpeg" /><figcaption>Returning to solve the Fibonacci problem</figcaption></figure><p>For example, to find the number that comes after 0, 1, 2, 3, 5, we would sum 3 + 5, and know that the next number would be 8. A more abstract way of defining the formula for finding a number in the Fibonacci sequence would be: F[n] = F[n-1] + F[n-2], where n represents the index in an array of Fibonacci numbers. Based on this formula, we also know that Fibonacci can be solved recursively, since we will inevitably find ourselves needing to use recursion to find the previous number in the Fibonacci sequence if we don’t know it already.</p><p>However, looking at the example recursive “tree” of values that are illustrated above, we’ll notice that we’re repeating ourselves. While recursively solving for the Fibonacci number F[6], or the seventh Fibonacci number, we had to calculate F[5] and F[4]. But then, in order to calculate F[5], we again need to solve for F[4], yet again!</p><p>Here’s an example of the same problem of recursive repetition, abstracted out.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*co5kIv5ds-det9Px_8aW8A.jpeg" /><figcaption>Whey are we recalculating the same values so many times?</figcaption></figure><p>It doesn’t really matter what n is when solving for F[n]; if we use recursion, we’re going to end up having to recalculate portions of the Fibonacci sequence more than once. For example, in the tree above, we are calculating F[n-3] twice, and we’re calculating F[n-2] twice, too. This seems super inefficient, and we should be able to do better.</p><p>The good news is: we can! Using dynamic programming, of course.</p><p>We know that dynamic programming allows us to <em>remember</em> solutions to problems that we’ve seen and solved before. The Fibonacci example is a prime example of when we would want to remember solutions to Fibonacci numbers that we’ve already solved for! The method for how a DP algorithm remembers problems that it has already solved is known as <strong><em>memoization</em></strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*G_hKjr5V1dX5GN0lyLTmDQ.jpeg" /><figcaption>Using memoization to remember problems that we’ve already solved!</figcaption></figure><p>Memoization is a lot like taking notes on a memo pad: when we encounter a problem that seems important (and even if it’s not), we write down the answer to it and note it down, memoizing it. Much like the 5 + 5 + 5 + 5 + 5 problem from earlier, if we run into that same problem later, we don’t need to do the mental math of recomputing all of it. We’ve already solved 80% of the problem because we can reuse our solution from earlier and just build upon it, which is much easier to do than resolving it from the ground up!</p><blockquote>Memoization allows us to only run a computation once, and then reuse it later without having to recompute it.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kLRo_yTxgPLSEs4V4ILPYQ.jpeg" /><figcaption>Most recursive algorithms can be easily memoized.</figcaption></figure><p>Earlier, before we were using memoization, we needed to calculate multiple subproblems again and again. However, by employing memoization, we can eliminate entire portions of unnecessary work. The illustration shown here exemplifies this.</p><p>Now, when solving for F[n], we first calculate F[n-1]. As a part of recursively figuring out the solution to F[n-1], we end up solving for F[n-2] and F[n-3]. Each time that we solve for them for the very first time, we <strong><em>memoize</em></strong> their solutions.</p><p>Next, we need to solve for the second part of figuring out F[n]: F[n-2]. When we go to calculate the value of F[n-2], we’ll check to see if we have already solved for it before actually figuring it out. The second time that we see it, we know that we have already solved for it, and we know that we already have its value since we <em>remembered</em> it when we memoized its solution.</p><p>Memoization allowed us to eliminate half of this recursive Fibonacci tree, simply because we remembered the solutions to subproblems that we had already seen! As a rule, recursive algorithms, including the Fibonacci algorithm, can be made into dynamic programming algorithms that use memoization for increased optimization and speed.</p><p>Okay, so now we know <em>how </em>dynamic programming algorithms manage to find the best, most optimal solution: they solve all the potential subproblems. We also know <em>how</em> they manage to solve all the subproblems: they remember the overlapping solutions, and use memoization to avoid unnecessary computation. But how much more efficient is a dynamic programming algorithm that uses memoization?</p><p>Let’s answer that question by looking at the issue of space and time complexity.</p><h3>Memoize all the things</h3><p>Without memoization, the runtime complexity of the algorithm to solve for the nth value in the Fibonacci sequence is…not the pretties sight.</p><p>For any Fibonacci number at an index of n that we need to solve for, we need to recursively call the same Fibonacci algorithm for the values of n-1 and n-2. We already know <a href="https://medium.com/basecs/finding-fibonacci-in-golden-trees-1c8967b1f47a">some of this math</a>. We know that two quantities have a golden ratio if the ratio between the two quantities is the same as the ratio of the two elements summed when compared to the larger of the two quantities. The combined runtime of these two inner algorithms the time T(n-1) and the time the time T(n-2) ends up amounting to <em>phi</em> (<em>φ</em> or <em>ϕ</em>) raised to the power of whatever n is.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*M576x89Qyq3xQBWzh2yVZA.jpeg" /><figcaption>Time complexity of solving Fibonacci recursively, without memoization.</figcaption></figure><p>There is also some constant time O(1) that involves summing the numbers and returning the correct value, but that’s negligible. The important thing — the blaring red alarm that should hopefully be going off in our heads — is that there is an exponent involved here! The golden ratio to the nth power as our running time is <em>not good.</em> In fact, it results in <strong><em>exponential running time</em></strong>, or O(2^n)! We always want to avoid that.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0qBx2NAsplMp7lRZZwundQ.jpeg" /><figcaption>Time complexity of solving Fibonacci with memoization.</figcaption></figure><p>Okay, so without memoization, the recursive form of Fibonacci isn’t too great.</p><p>But what about <em>with</em> memoization? Well, the nice thing about “remembered”, memoized values is that they cost us almost no time to actually look up in the dictionary/hash/array where we’d probably store in. In other words, the actual cost of looking up a memoized value costs us O(1), <strong><em>constant</em></strong> time.</p><p>However, the first time that we encounter a subproblem, we still need to to the work of solving it before we can memoize it. The non-memoized calls to the Fibonacci algorithm will depend upon what n is. If we’re looking for the 10th element, it will take us considerable less calls to calculate the Fibonacci sequence than if we were looking for the 100th element. Thus, the work of running the Fibonacci algorithm the first time for each non-memoized element takes <strong><em>linear</em></strong>, O(n) time.</p><p>Similar to the non-memoized version of this algorithm, here is also some constant time O(1) that involves summing the numbers and returning the correct value, but that’s negligible. This results in O(n) + O(1) + O(1) runtime, which still amounts to <strong><em>linear</em></strong>, O(n) time.</p><p>Linear time is a whole lot better than exponential time! Not bad for a little dynamic programming algorithm, eh?</p><p>So how does the memoized version of Fibonacci compare to the non-memoized version when it comes to space?</p><blockquote>Given the fact that the memoized version of Fibonacci needs to remember old subproblem solutions, the DP paradigm sacrifices some space in order to save time.</blockquote><p>This is part of the tradeoff of using a dynamic programming approach, and depending on how many subproblems we need to solve and how smart we are about the data structure that we use to <em>store</em> those subproblem solutions, sacrificing space for time can often be preferable — particularly if we know we’re going to need to look up many values of Fibonacci, and know that we’ll be reusing our old solutions again and again, later on.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*baaFGzuQ88kx8b9EpNKoPA.jpeg" /><figcaption>Two approaches to dynamic programming.</figcaption></figure><p>The dynamic programming paradigm is powerful not just for its efficiency, but also for its runtime complexity. However it is worth mentioning that there are two main approaches to DP algorithms; we’ve only really dealt with one in this post, but it’s important to be comfortable in recognizing and using both.</p><p>The paradigm of <strong><em>top down dynamic programming</em></strong> is the one that we used in our Fibonacci experiment. In the top down approach, we start with the large, complex problem, and understand how to break it down into smaller subproblems, memoizing the problem into parts.</p><p>The alternative to this is the <strong><em>bottom up dynamic programming </em></strong>approach, which starts with the smallest possible subproblems, figures out a solution to them, and then slowly builds itself up to solve the larger, more complicated subproblem.</p><p>In the case of solving Fibonacci, the bottom up technique would have involved us solving for the first elements in Fibonacci, and then building our way up to finally arrive at the solution for whatever nth value we were trying to determine to begin with. We would still use memoization to help us store values — we’d just be solving the problem from the “opposite end” so to speak. The bottom up approach is probably the one that is more comfortable to most of us when we first learned of Fibonacci. If we think about it, we all start counting Fibonacci with 0, then 1, then 1, then 2, until we count up to the number that we’re looking for.</p><p>There is one large benefit to bottom up dynamic programming algorithms, which is this: we only really need to memoize the last two values. Since we know that we’re working our way <em>up — </em>and not working our way down from the top — we don’t need to work about storing all of the previous values. We really only care about the last two, until we arrive at the value for n. This allows us to eliminate the need for a larger data structure that takes up space for memoized values. Instead, we can just memoize the previous two values, which allows us to achieve <strong><em>constant</em></strong>, or O(1) space.</p><p>Dynamic programming, even with all of its idiosyncrasies, isn’t too terrifying once we break it down into its moving parts!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/220/1*1gGPfHMGGNPBkefveRDSaQ.png" /><figcaption>Richard Bellman, <a href="https://en.wikipedia.org/wiki/Richard_E._Bellman">Wikimedia Foundation</a></figcaption></figure><p>I mentioned earlier that the name “dynamic programming” makes it feel more intimidating than it really is. Here’s a funny fact behind DP’s name: it doesn’t really <em>mean</em> anything.</p><p>Dynamic programming was invented in the 1940s by Richard Bellman, a computer scientist who was working on mathematical research at a company called RAND at the time. As it turns out, RAND was employed by the US Air Force, which meant that they often had to report to the Secretary of Defense, who was named Charles Erwin Wilson.</p><p>In Bellman’s autobiography, <em>Eye of the Hurricane: An Autobiography</em>, he explains how he came up with the name for this paradigm of algorithm design:</p><blockquote>[Wilson] actually had a pathological fear and hatred of the word research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term research in his presence…Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word “programming”. I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying. I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that it’s impossible to use the word dynamic in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities.</blockquote><p>The moral of the story, if there is such a thing, is that sometimes scarily-named things might actually be named for no other reason than the name sounded good. Therefore, in my opinion, scary-sounding things are nothing to be afraid of! Just be sure not to tell Charles Erwin Wilson that.</p><h3>Resources</h3><p>Dynamic programming is a topic that comes up a lot in computer science in the form of difficult problems. Some computer science courses introduce it early on, and then never really come back to address this form of algorithmic design ever again. However, the theory behind dynamic programming comes up again and again, usually in the form of the most complex — and sometimes even unsolvable! — problems. If you’re interested in learning more, here are some great resources to help you get you started.</p><ol><li><a href="https://www.youtube.com/watch?v=OQ5jsbhAv_M">Dynamic Programming — Fibonacci, Shortest Paths</a>, MITOpenCourseWare</li><li><a href="https://www.youtube.com/watch?v=P8Xa2BitN3I">Algorithms: Memoization and Dynamic Programming</a>, HackerRank</li><li><a href="https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/tutorial/">Introduction to Dynamic Programming</a>, Hacker Earth</li><li><a href="http://interactivepython.org/courselib/static/pythonds/Recursion/DynamicProgramming.html">Dynamic Programming</a>, Interactive Python</li><li><a href="http://www.geeksforgeeks.org/dynamic-programming-set-1/">Dynamic Programming (Overlapping Subproblems Property)</a>, GeeksForGeeks</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=43d29830a630" width="1" height="1" alt=""><hr><p><a href="https://medium.com/basecs/less-repetition-more-dynamic-programming-43d29830a630">Less Repetition, More Dynamic Programming</a> was originally published in <a href="https://medium.com/basecs">basecs</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>