Writing an Interpreter in Go: Crafting Interpreters Book Review and Implementation Series Introduction

[00:00:00]hello and welcome to a new series of videos in this series we are going to read the book called crafty interpreters written by Robert nrom I'm sorry if I don't pronounce his name correctly but uh I'm not American and uh in this book uh walks The Reader through a process of writing an interpreter the first part of the book uh Builds an as interpreter uh like a uh Tre walking interpreter which is a a very high level concept and relatively slow and in this book uh the as the three walk interpreter is written in Java and the uh second part of the book is a bite code virtual machine and that virtual machine part is written in C and if you have watched any of my previous carnigan en Richie videos you you may have seen a quote parts of this book because it's a very good book and I actually did did go through the first part the three walking interpreter part about two years ago and I wrote the Tre walking interpreter in Rust and this time we are going to write it in go because that was the result of a a half a day long poll on my on my YouTube YouTube wall uh so if you're hoping to see some uh rust or Zig or or or Swift or whatever you you probably should go and watch another video but anyway the uh the uh I'm going to quickly walk through chapters one and two of this book uh because nobody really likes reading introductions and I am pretty sure everybody wants to see at least some code being written in this video and uh if uh you don't have this book yet you can just read it for for free with no strings attached on Crafting interpreters tocom and uh maybe before we start I'm going to show you some of the some of the things you can do with uh when you finish this book The Language you're going to write to implement is called locks and uh it's kind of it looks like a a family language kind of like JavaScript it has closures it is interpreted and it's very simple it basically only has the whole standard library for locks only uh consists of a print function basically and uh I'm going to demo The Interpreter I wrote two years ago uh this is the source code for the main function written in Rust and uh I'm going to show you that it can indeed run the script that I downloaded from this website so when we run this script it also presents a Fibonacci Sequence and uh I know this may look kind of kind of uh underwhelming but believe me it's actually a lot of fun and you can learn a lot about programming languages in the process also I do realize that some people may hate me for doing this in in a light mode so I'm going to turn on dark reader great so without further Ado let's open the Web format and I'm going to I'm probably going to skim over chapter one okay introduction fairy tales are more than true not because they tell us that dragons exist but because they tell us that dragons can be beaten JK Chesterton by way of nil G gayman Coraline uh [Music] okay yes so this is a lot of text and none of this is directly related to programming uh maybe I'll jump here why learn this stuff every introduction to every compiler book seems to have this section I don't know what it is about programming languages that causes such existential doubt I don't think Ornithology books worry about justifying their existence they assume the reader loves birds and start teaching but programming languages are a little different I suppose it is true that the odds of anys creating a broadly successful general purpose programming language are slim the designers of the world's widely used languages could fit into a Volkswagen bus even without putting with poptop camper app if joining that Elite group was the only reason to learn languages it would be hard to justify fortunately it isn't little languages are everywhere for every successful general purpose language there are a thousand successful Niche ones we used to call them little languages but inflation in the jargon economy led to the name domain specific languages these are pigeons tailor buil to a specific task think application scripting languages template engines markup formats and configuration ation files um almost every large software project needs a handful of these when you can it's good to reuse an existing one instead of rolling your own once you factor in documentation debuggers editors support syntax highlighting and all the other trappings doing it yourself becomes a tall order but there is still a good chance you'll find yourself needing to whip up a parser or other tool when there isn't an existing library that fits your needs even when you are reusing some existing implementation you'll inevitably end up needing to debug and maintain it and poke around in its guts languages are great exercise longdistance Runners sometimes strain with weights strapped to their ankles or at high altitudes where the atmosphere is thin when they later unburden themselves the new relative ease of light Limbs and oxygen reach air enables them to run faster and fast farther and faster implementing a language is a real test of programming skill the code is complex and performance critical you must Master recursion Dynamic arrays trees graphs and hash tables you probably use hash tables at least in your day-to-day programming but do you really understand them well after we've crafted our own from scratch I guarantee you will while I intend to show you that an interpreter isn't as dating as you might believe implementing one well is still a challenge rise to it and you'll come away a stronger programmer and smarter about how you use data structures and algorithms in your daily job one more reason the last reason is hard for me to admit because it's so close to my heart ever since I learned to program as a kid I felt there was something magical about languages when I first stopped out basic programs one key at a time I couldn't conceive how basic itself was made later the mixture of all and Terror on my college friends faces when talking about their compilers class was enough to convince me language hackers were a different breed of human some sort of wizards rant privilege privileged access to Arcane Arts it's a Charming image but it has a darker side I don't it didn't feel like a wizard wizard so I was left thinking I lacked some inborn quality necessary to join the cabal though I've been fascinated by languages ever since I had doodled made up keywords in my school notebook it took me decades to master the courage to try to really learn them but magical quality but sense of exclusivity excluded me side note and its practitioners don't hesitate to play up this image two of the seminal texts on programming languages feature a dragon and a wizard on covers and these seminal Works would be uh this one compilers principles techniques and tools and the second one is a 404 uh when I did finally start cobbling together my own little interpreters I quickly learned that of course there is no magic at all it's just code and the people who hack on languages are just people there are a few techniques you don't often encounter outside of languages and some parts are a little difficult but not more difficult than other obstacles you've overcome my hope is that if you've ever if you've felt in intimidated by languages and this book helps you overcome that fear maybe I'll leave you just a tiny bit braver than you were before and who knows maybe you will make the next great language someone has to how the book is organized this book is broken into three parts you're reading the first one now it's a couple of chapters to get you oriented teach you some of the lingo that language hackers use and introduce you to to Locks the language we we will be implementing each of the other two parts uh builds one complete locks interpreter within those parts each chapter is structured the same way the chapter takes a single language feature teaches you the concepts behind it and walks you through an implementation it took a good bit of trial and error on my part but I managed to carve up the two interpreters into chapters size trunks but build on the previous chapters but require nothing from later ones from the very first chapter you'll have a working program you can run and play with with each passing chapter it grows increasingly full featured until you eventually have a complete language aside from copious culating English Pros chapters have a few other delightful facets okay I can't hear it uh facet facet facets facet facet chapters have a few other delightful facets the code we about crafting interpreters so this book contains real code every single line of code needed is included and each snippet tells you where to inserted in your ever growing implementation uh many other language books and language implementations use tools like Lex and Yak so so-called compiler compilers that automatically generate some of the source files for an implementation from some higher level description there are pros and cons to tools like those and strong opinions some might say religious convictions on both sides side note Yak is a tool that takes in a grammar file and produces a source file for a compiler so it's sort of like a compiler that outputs a compiler which is where we get the term compiler compiler Yak wasn't the first of its ilk which is why it's named Yak yet another compiler compiler a similar tool is Pyon Pon what's how do you pronounce Pon bon bon bison a later simulator is bison named as a p on the pronunciation of yak like Yak which is if you find all these little self self- references and pans charming and fan you'll fit right right in here if not well maybe language nerd sense of humor is an acquired taste okay back to the main text we will abstain from using them here I want to ensure there are no dark Corners where magic and confusion can hide so we'll write everything by hand as you'll see it's not as bad as it sounds and it means you will really understand each line of code and how both interpreters work a book has different con constraints from The Real World and so the coding style here might not always reflect the best way to write maintainable production software if I seem a little Cavalier about say ating private or declaring a global variable understand I do so to keep the code easier on your eyes the pages here aren't as wide as your IDE and every character counts also the code doesn't have many comments that because each handful of lines is surrounded by several paragraphs of honest to good Pros explaining it when you write a book to accompany your program you are welcome to ammit comments too otherwise you should probably use SL slash a little more than I [Music] do while the book contains every line of code and teaches what each means it does not describe the machinery needed Co to compile and run The Interpreter I assume you can slap together a make file or a project in your IDE of choice in order to get the code to run those kinds of instructions get out of date quickly and I want this book to age like XO Brandy not backyard Hooch what's what's Hooch okay strong alcohol especially whiskey Snippets since the book contains literally every line of code needed for the implementations the Snippets are quite precise also because I try to keep the program in runnable state even when major features are missing sometimes we add temporary code that gets replaced in later Snippets a snippet with all the balls and whistles looks like this uh like this in this Center you have the new Cod to add it may have a few faded outlines above or below to show where it goes in the exist L okay yeah I'm going to snip this part skip this part asides uh challenges each chapter ends with a few exercises unlike textbook problem sets which tend to review material uh you already covered these are to help you learn more than what's in the chapter they force you to step out the guided path and explore on your own they will make you research other languages figure out how to implement features or otherwise get you out of your comfort zone Vanquish the challenges and you'll come away with a broader understanding and possibly a few bumps and scrapes or skip them into if you want to stay inside the comy confines of the tour bus it's your book a word of warning the challenges often ask you to make changes to The Interpreter you are building you want to implement those in a copy of your code the later chapters as assume your interpreter is in a pristine and challenged State Design note um most programming language books are strictly programming language implementation books they rarely discuss how one might happen to design the language being implemented implementation is fun because it is so precisely defined we programmers seem to have an affinity for things that are black and white ones and zeros personally I think the world needs only so many implementations of 477 at some point you find yourself designing a new language once you start playing that game then the software human side of the equation becomes permanent things like which features are easy to learn how to balance Innovation and familiarity what syntax is more readable and to whom uh yeah okay we'll write our first interpreter jogs in Java actually we will write it in go but the source code of the book is going to be written in Java and I'm going to to attempt to translate it into Java into goal on stream on a video i' I'm not even going to try to to run the Java code I didn't do it the last time and I don't intend to do it this time I don't write any Java the focus is on Concepts we will write the simplest cleanest code we can to correctly implement the semantics of the language this will get us comfortable with the basic techniques and also hone our understanding of exactly how the language is supposed to behave mhm yeah this second interpreter so in the next part we start all over again but this time in C C is the perfect language for understanding how an implementation really works all the way down to the b in memory and the code flowing through the CPU a big reason that we are using C is so I can show you how show things C is particularly good at but that does mean you'll need to be pretty comfortable with it you don't have to be The Reincarnation of Dennis Richie but you shouldn't be spooked by pointers either mhm okay great design notes okay next chapter chapter two a map of the territory you must have a map no matter how rough otherwise you wonder all over replac and the Lord of the Rings I never made anyone go farther than he could on a given day we don't want to wander all over the place so before we set off let's scan the territory charged by previous language implementers it will help us understand where we are going and the alternate routes others have taken first let me esta Lish a Shand much of this book is about a language's implementation which is distinct from the language itself in some sort of platonic ideal form things like stock bite code and recursive descent or nuts and bolts one particular implementation might use from the user's perspective as long as the resulting Contraption Faithfully follows the language's specification it's all implementation detail we you're going to spend a lot of time on those details so if I have to write language implementation every single time I mention them I'll wear my fingers off instead I'll use language to refer to either a language or an implementation of it or both unless this the distinction matters the parts of the language Engineers have been building programming languages since the dark ages of computing as soon as we could talk to computers we discovered doing so was too hard and we unlisted their help I find it fascinating that even though today's machines are literally a million times faster and and have orders of magnitude more storage the way we build programming languages is virtually unchanged while the area explored by by language designers is vast the trails they've curved through it are few not every language takes the exact same path some take a shortcut or two but otherwise they are reassuringly similar from real Admiral Grace Hoppers first cobal compiler all the way to some hot new transpile to JavaScript uh language whose documentation consists entirely of a single poorly edited rme in a g repository somewhere side note there are certainly dead ends sad little cexx of Cs papers with zero citations and now forgotten optimizations but only made sense when memory was measured in individual bytes I visual back to the main text eventually reach the PE okay so this is the map of of the path this book is going to take and I'm okay maybe I'll read the explanation I visualize the network of PS and implementation may choose as climbing a mountain you start off at the bottom with the program as row Source text literally just a string of characters each phase analyzes the program and transforms it to some higher level representation where the semantics what the author wants the computer to do become more apparent eventually we reach the peak we have a bird bird's eye view of the users program and can see what their code means we begin our descent down the other side of the mountain we transform this highest level representation down to successively lower level forms to get closer and closer to something we know how to make the CPU actually execute let's Trace through each of those trails and points of interest Our Journey Begins on the left with the vertex of the user source code V average equals Min plus Max divided by two the first step is scanning also known as Lexing or if you are trying to impress someone lexical analysis they all mean pretty much the same thing I like Lexing because it sounds sounds like something an evil super villain would do but I'll use scanning because it seems to be marginally more common place a scanner or lexer takes in the linear stream of characters and chunks them together into a series of something more akin to words in programming languages each of these words is called a token some tokens are single characters like left bracket and comma others may be several characters long like numbers 1 to three string literals and identifiers lexical comes from the Greek root Lex meaning word some characters in a source file don't actually have mean anything white space is often insignificant and comment by definition are ignored by the language the scanner usually discards these leaving a clean sequence of meaningful tokens uh yes sorry where was I some characters in a source file don't actually mean anything wh space is often insignificant and common by definition are ignored by the language the scanner usually discards these leaving a clean sequence of meaningful tokens far average equals left bracket Min plus Max right bracket SL to semicolon the next step is parsing this is where our syntax gets a grammar the ability to compose larger expressions and statements out of smaller Parts did you ever diagram sentences in English class if so you've done what a parser does except that English has thousands and thousands of keywords and an overflowing Cornucopia of ambiguity programming languages are much simpler a parser takes the flat sequence of tokens and builds a tree structure but mirrors the nested nature of the grammar these trees have have a couple of different names pars three or abstract syntax tree depending on how close to the be syntactic structure of the source language they are in practice language hackers usually call them syntax trees as ests or often just trees so in this case the VAR is equal to the division the result of a division by two of the sum of minim mar part saying has a long R history in computer science blah blah blah static analysis uh the first two stages are pretty similar across all implementations now the individual characteristics of each language start coming into play at this point we know the syntactic structure of the code things like which expressions are necess in which but we don't know much more than that in an expression like a plus b we know we are adding A and B but we don't know what those names refer to are local variables Global where are they defined the first bit of analysis that most languages do is called findinding resolution for each identifier we find out where that name is defined and why are the two together this is where scope comes into play the region of source code where a certain name can be used refers to a certain declaration if a language is statically typed this is when we type check once we know where A and B are declared declared we can also figure out types then if those types don't support being added to each other we report a type error side note the language will build in this book is dynamically typed so it will do it typ checking later at run time take a deep breath we have attained the summit of the mountain and a sweeping view of the users program all the semantic Insight that is visible to us from analysis needs to be stored somewhere there are a few places we can squirel it away often it gets stored right back as attributes and the syntax 3E itself extra fields in the not that aren't initialized during parsing but get filled in later other times we may store data in a lookup table off to the side typically the keys to this table are identifiers names of variables and declarations in that case we call it a symbol table and the values it Associates with it Associates with with each key tell us what that identifier refers to the most powerful bookkeeping tool is to transform the tree into an entirely new data structure but more directly expresses the semantics of the code that's the next section everything up to this point is considered the front end of the implementation you might guess everything after this is the back end but no back in the days of your when front end and back end were coined compilers were much simpler later researchers invented new faces to to stuff between the two halves rather than discard the old terms William wolf and Company lamped William wolf and Company lamped those new faces into the Charming but spatially paradoxical name middle end okay intermediate representations uh you can think of the compiler as a pipeline where each stage's job is to organize the data representing the user's code in a way that makes the next stage simpler to implement the front end of the pipeline is specific to the source language the program is written in the back end is concerned with the final architecture where the program will run in the middle the code may be stored in some intermediate representation IR but isn't tightly tied to either resource or destination forms hence intermediate instead the IR acts as an interface between these two languages side note there are a few wellestablished styles of IRS out there hit your search engine of choice and look for control flow graph static single assignment continuation passing style and free address code I am not going to do the research on stream back to the main text this lets you support multiple source languages and Target platforms with less effort say you want to implement Pascal C and for compilers and you want to Target x86 arm and I don't know spark normally that means you're signing up to write nine full compilers Pascal to8 x86 C2 arm and every other combination a shared intermediate representation reduces that dramatically you write one front and for for each Source language that produces the intermediate representation then one back end for each Target architecture now you can mix and match those to get every combination side note if you've ever wondered how GCC supports so many crazy languages and architectures like modula 3 on motor Motorola 68,000 what's modula 3 uh uh okay now we know language frontends uh Target one of a handful of IRS mainly gimple and RTL these Target backend like the one for 68k then takes those IRS and produce native code uh there's another big reason we might want to transform the code into a form that makes the semantics more apparent optimization once we understand what the program means we are free to swap it out with a different program that has the same semantics but implements them more efficiently you can optimize it a simple example is constant folding if some expression always evaluates to the same to the exact same value we can do the evaluation at compile time and replace the code for the expression with its result if the user typed in this we could do all of that arithmetic in the compiler and change the code to this optimization is a huge part of the programming language business many language hackers spend their entire entire careers here squeezing every drop of performance they can run they can out of their compilers to get their benchmarks a fraction of a percent faster it can become a sort of [Music] obsession yeah I'm going to skip this uh but if you if you are interested in optimizations you you might want to read this uh side note we're mostly going to hop over what rle in this book many sucessful languages have surprisingly few compile time optimization for example Lua and C generate relatively unoptimized code and focus most of their performance effort on the runtime code generation okay we have applied all of the optimizations we can think of to the users program the last step is converting it to a form the machine can actually run in other words generating code or code gen where code here usually refers to the kind of primitive assembly like instruction as CPU runs and not the kind of source code a human might might want to read finally we we are in the back end descending The Other Side of the Mountain from here and out our representation of the code becomes more and more primitive like Evolution run in Reverse as we get closer to something or a simpleminded machine can understand hang on I want to make my cursor bigger if I can uh okay I don't know how to do it but uh yeah in on Windows I have like a bigger cursor uh we have a decision to make do we generate instructions for a real CPU or a virtual one if we generate real machine code we can get an executable that the OS can load directly onto the chip uh native code is lighning fast but generating it is a lot of work today's architectures have piles of instructions complex pipelines and enough historical baggage to fill a 747s luggage Bay side note for example the a a aski adjust a x before division instruction lets you perform division which sounds useful except that instruction takes as operant two binary code and decimal digits packed into a single uh binary coded decimal digits packed into a single 16bit register when was the last time you needed BCD on a 16bit machine okay yeah well speaking the chips language also means your compiler is tied to a specific architecture if your compiler targets at x86 machine code it's not going to run on an ARM device all the way back into the 60s during the Cambrian explosion of computer architectures that lack of portability was a real obstacle to get around that hackers like Martin Richards and Nicholas V of bcpl and Pascal Fame respectively made their compilers produce virtual machine code instead of instruction for some real Chip they produce code for a hypothetical idealized machine vert called this P code for portable but today we generally call it bite code because each instruction is often a single bite longan these synthetic instruct are designed to map a little more more closer to the languages semantics and not be so tied to the pecularities of any one computer architecture and its accumulated historical craft you can think of it like a dense binary encoding of a languages low level operations uh side note the basic principle here is that the farther down the pipeline you push the architecture specific work the more of the earlier phases you can share across architectures there is a tension though many optimizations like register allocation and instruction selection work best when they know the strengths strengths and capabilities of a specific chip figuring out which parts of your compiler can be Shar shared and which should be targeted specific is an art okay next section virtual machine if your compiler produces bite code your work isn't over once that's done since there is no chip that speaks at bite code it is your job to translate again you have two options you can write a little mini compiler for each Target architecture that converts the bite code bite code to native code for that machine you still have to do work for each ship you support but this last stage is pretty simple and you get to reuse the rest of the compiler pipeline across all of the machines you support you're basically using your bite code as an intermediate representation or you can write a virtual machine a program that emulates a hypothetical chip supporting your virtual architecture at runtime uh running bod in a VM is slower than translating it to native code ahead of time because every instructure must be simulated at run time each time it executes in return you get Simplicity and portability Implement your VM in say C and now you can run your language on any platform that has a c compiler this is how the second interpreter we build in this book Works uh yeah run time we have finally hammered the user us program into a form that we can execute the last step is running it if we compile to it to machine code we simply tell the operating system to load the execut table and off it goes if we compile it to bite code we need to start start up the the VM and load the program into that in both cases we all body basist of lowlevel languages we usually need some services that our language provides while the program is running for example if a language automatically manages memory we need a garbage collector going in order to reclaim unused bits if our Pro if our language supports instance of tests so we can see what kind of object you have when we need some representation to keep track of a type of each object during execution all of this stuff is going at runtime so it's called appropriately the runtime in a fully compiled language the code implementing the rant gets inserted directly into the resulting executable in say go each compiled application has its own copy of Go's runtime directly embedded in it if the language is run inside an interpreter or VM then the runtime leaves there this is how most implementations of languages like Java pyone and JavaScript work section 2 two shortcuts and alternate alternate routes but the long path covering every possible phase you might Implement many languages do work the entire route but there are a few shortcuts and Alternate paths single path comp path compilers some simple compilers inter Le parsing analysis and and code generation so that they produce output code directly in the parser without ever allocating any syntax trees or other IRS this single pass compilers restrict the design of the language you have no intermediate data structures to store Global Information about the program and you don't revisit any previously passed part of the code this means as soon as you see some expression you need to know enough to correctly compile it side note syntax directed translation is a structured technique for building these all Advan compilers you associate an action with each piece of of the grammar usually one that generates output code then whenever the parer matches that chunk of syntax it executes the action building up the target code one rule at a time Pascal and C were designed around this limitation at the time memory was so precious that the compiler might not even be able to hold an entire source file in memory much less the whole program this is why Pascal's grammar requires type declarations to appear first in a block it's why in C you can't call a function above the code but defines it unless you have an explicit forward declaration that tells the compiler what it needs no to generate code for a call to the later function okay three walk interpreters some programming languages begin executing code right after paring it to an a with maybe a bit of syntax static analysis applied to run the program The Interpreter traverses the syntax 3 one branch and leave at a time evaluating each node as it goes this implement mation style is common for student projects in little languages but is not widely used for general purpose languages since it tends to be slow some people use interpreter to mean only these kinds of implementations but others Define that word more generally so I use the inarguably explicit three walk interpreter to refer to these our first interpreter rolls this way Yep this is is going to say that the first interpreter we are going to write in probably in the following videos is going to be a treew interpreter a notable exception is early versions of Ruby which were three walkers at 1.9 the canonical implementation of Ruby switched from the original MRI mat's Ruby interpreter to koichi sasada Yar yet another Ruby VM yarv is a bite code virtual machine transpilers okay yeah uh writing a complete back end yeah so uh this is a longer section about transpilers I don't think this is exactly relevant to to the topic of this video so I'm going to skip this section and probably I'm also going to skip just in time compilation uh I'm I'm going to skip to section 2.3 compilers and interpreters now that I stuffed your head with a dictionaries worth of programming language jargon we can finally address a question FPL coders since time in Memorial what's the difference between a compiler and an interpreter uh it turns out that this is like asking the difference between a fruit and a vegetable there's that seem like a binary either or choice but actually fruit is a Botanical term and vegetable is culinary which means it is related to cooking one does not strict to apply V negation of the other there are fruits that are in vegetables like apples and vegetables that AR in fruits like carrots but also edible plants that are both fruits and vegetables like tomatoes peas and eggplants side note peanuts which are not even nuts and cereals like wheat are actually fruit but I got this drawing wrong what can I say I'm a software engineer not a botanist I should probably erase the little peanut guy but he's so cute that I can bar to now pine nuts on the other hand are plantbased foods that are neither fruits nor vegetables at least as far as I can tell so back to languages compiling is an implementation technique that involves translating a source language to some other usually lower level form when you generate bite code or machine code you are compiling when you transpile to another high level language you are compiling to when we say a language implementation is a compiler we mean it translate source code to some other form but doesn't execute it the user has to take the resulting output and run it themselves conversely when we say an implementation is an interpreter we mean it takes inser source code and executes it immediately it runs programs from Source like apples and oranges some implementations are clearly compilers and not interpreters GCC and clang take your Co C code and compile it to machine code an end user runs that exe executable directly and may never even know which tool was used to compile it so those are compilers for C in older versions of mat's canonical implementation of Ruby the user run Ruby from Source the implementation pared it and executed it directly by traversing the synx tree no other translation occurred either internally or in any user visible form so this was definitely an interpreter for Ruby but what of cpython when you run your Python program using it the code is pared and converted to an internal bite code format which is then executed inside the VM from the user's perspective this is clearly an interpreter they run their program from Source but if you look under cpython scaly skin you'll see that there is definitely some compiling going on the answer is that it is both cpython is an interpreter and it has a compiler in practice most script languages work this way as you can see uh [Music] mhm the go tool is even more of a Horticultural curiosity if you run go build it compiles your go source code to machine code and stops if you type go run it does that then immediately exec the generated executable so go is a compiler you can use it as a tool to compile code without running it is an interpreter you can invoke it to immediately run a program from source and also has a compiler when you use it as an interpreter it is still compiling internally the overlapping region in this Center is where our second interpreter lives to since it internally compiles to bite code so while this book is nominally about interpreters we'll cover some compilation too section 2.4 our journey that's a lot to take in all at once don't worry this isn't the chapter where you're expected to understand all of these pieces and parts I just want you to know what they are out there and roughly how they fit together this map should serve you well as you explore the territory beyond the guided path we take in this book I want to leave you yearning to strike out on your own and wander all over that mountain but for now it's time for your own journey to begin tighten your bootlaces cinch up your pack and come along from here on out all you need to focus on is the path in front of you side note henceforth I promise to tone down the whole Mountain metaphor thing mhm okay next chapter okay so the next chapter contains a description of the locks language which is the language we are going to implement in this series and uh and here we're finally going to get some code but unfortunately we are I don't think we're we're even going to start having uh writing the actual implementation of the of uh The Interpreter but anyway uh that's why this video is probably going to have the number zero because it precedes the actual chapter one when we start writing the com The Interpreter code quote what what nicer thing can you do for somebody than make them breakfast Anthony B B sorry there are so many so many foreign names in this book we'll spend the rest of this book Illuminating every dark and Sandry corner of the Lo language but it seems cruel to have you immediately start grinding out code for The Interpreter without at least a glimpse of what we are going to end up with at the same time I don't want to drag you through Rams of language lawyering and specification is before you get to touch your text editor so this will be a gentle friendly introduction to Locks it will leave out a lot of details and edge cases we've got plenty of time for those later uh side note a tutorial isn't very fun if you can try the code out yourself alas alas you don't have a lock interpreter yet since you haven't built one if you're not you can use mine or we can use uh we can use the one I wrote two years ago like so so uh a comment and print hello world great as that SL line comment and the trailing semicolon imply lus syntax is a member of the C family there are no parentheses around the string because print is a built-in statement and not a library function uh now I won't claim that c has a great syntax if we wanted something elegant we'd probably mimic Pascal or small talk if you wanted to go full Scandinavian furniture minimalism we do a scheme those all have her virtues uh side note I'm surely biased but I think Lo's syntax is pretty clean C's most egregious grammar problems are around types Dennis Richie had this idea called declaration reflects use where variable declarations mirror the operations you would have to perform on the variable to get a value of the base type uh variable uh clever idea but I don't think it worked out great in practice back to the text what select syntax has instead is something you'll often find more VAR valuable in in a language familiarity I know you are already comfortable with that style because the two languages will be using to implement locks Java and C also inherited using a similar Syntax for logs gives you one less thing to learn a high level language while this book ended up bigger than I was hoping it's still not big enough to fit a huge language like Java in it in order to fit fit two complete implementations of locks in these Pages locks itself has to be pretty compact when I think of languages that are small but useful what comes to mind are high level scripting languages like JavaScript scheme and Lua although spr logs looks most like JavaScript mainly because most C text languages do as we learn later Lo's approach to scoping Hues closely to scheme the C flavor of logs will build in part three is heavily indepted to Lu's clean efficient implementation side note now what JavaScript has taken over the world and is used to build ginormous applications it's hard to think of it as a little scripting language but Brendan Ike hacked the first JS interpreter internet skape Navigator in 10 days to make buttons animate and web pages JavaScript has grown up since then but it was once a cute little language because Ike shaped JS together with roughly the same raw materials and time as an episode of mcgyver it has some weird semantic Corners where the duct tape and paper clips show through things like variable hoisting dynamically bound this holes in arrays and implicit conversions I had the luxury of taking my time on locks so it should be a little cleaner after all the two languages will be using to implement locks are both statically typed uh okay Dynamic typing logs is dynamically typed variables can store various values of any type and a single variable can even store values of different types at different times if you try to perform an operation on values of the wrong type say dividing a number by a string then the error is detected and reported at run time there are plenty of reasons to like static types but they don't outweigh the pragmatic reasons to pick Dynamic types for logs a static type system is a ton of work to learn and Implement skipping it gives you a simpler language and a shorter book we'll get our interpreter up and executing bits of code sooner if we defer our type check into to runtime automatic memory management yeah this this is going to be a a JC language data types in lox's little Universe the atoms that make up all matter are are the built-in data types there are only a few booleans numbers uh strings and nil which is going to be the same as in uh languages like Lua I think or maybe what in languages like lisp and Ruby and elixir and [Music] go okay Expressions if built-in data types and their literals are atoms then Expressions May must be the molecules excuse me arithmetic logs features the basic arithmetic operators you know and love from C and other languages addition substraction multiplication division these sub Expressions on either side of the operator are operand because there are two of them they are called binary operators it has nothing to do with the ones and zeros use of binary because the operator is fixed in the middle of the operant there they are also called infix operators as opposed to prefix operators where the operator comes before the operant in postfix where it comes after one arithmetic operator is actually both an infix in a prefix one the minus operator can also be used to NE to negate a number there are also some operators that have more than two operants and The Operators are interl uh between them the only one in wide use Mage is the conditional orary operator of of c and its friends uh as condition question mark then arm colon else arm semicolon some call these mix fix operators a few languages let you define your own operators and control how they are positioned for fixity all of these operators work on numbers and it's an error to pass any other types to them the exception is the plus operator you can pass also pass it to strings to two strings to concatenate them comparison and equality moving along we have a few more operators that always return a bullant result we can compare numbers and only numbers using year old comparison operators we can test two values of any kind for equal equality or inequality even different types values of different types are never equivalent I'm generally against implicit conversions then we have logical operators the not operator a prefix exclamation mark returns false if its operant is true and vice versa the other two logical operators are control flow contracts const racts in the guise of expression Expressions an end expression determines if two values are both true it Returns the left oper end if it's false or the right oper end otherwise side note I used and and or for this instead of erson erson and pipe pipe because locks doesn't use erson and pipe for bitwise operators it felt weird to introduce the double character forms without the Single Character ones I also kind of like using words for these since they are really control flow structures and not simple operators back to the text and an or expression determines if either of two values or both are true it Returns the left operant if it is true and the right operant otherwise the reason and or or are like control flow structures is that they short circuit not only does end return the left operand if it is false it doesn't even evaluate the right one in that case conversely Contra positively if the left operant of an or is true the right is skipped 344 pre precedence and grouping all of these operators have the samee pre precedence and associativity that you'd expect coming from C when we get to parsing we'll get way more precise about that in cases where the Precedence isn't what you want you can use uh parentheses to group staff since they aren't Tech very technically interesting I've cut the remainders of a typical operator managerie out of our little language also I can uh we can try to execute this uh example from earlier on so if VAR minimal equals 1 and VAR maximum equals 8 then our average equals Min plus Max ided by two print average nice since they aren't technically interesting I've cut the remainder of the typical operator manager out of our little language no bitwise shift modulo or conditional operators I'm not grading you but you will get bonus points in my heart if you augment your own implementation of logs with them those are the expression forms except for a couple related to specific features that we'll get to later so let's move up a level statements now we are at statements where an expression's main job is to produce a value a statement's job is to produce an effect Since By definition statements statements don't evaluate to Value to be useful they have to otherwise change the world in some way usually modifying some state reading input or producing output you've seen a couple of kinds of statements already the first one was print hello world a print statement uses evaluates a single expression and displays the result to the user you've also seen some statements like some expression side note making print into a language instead of just making it a core Library function is a hack but it's a useful hack for us it means our in progress interpreter can start producing output before we've implemented all of the Machinery required to Define functions look them up by name and call them an expression Follow by a semicolon promotes the expression to statement Hood this is called imaginatively imagina imaginatively enough an expression statement if you want to pack a series of statements where a single one is expected you can rob them up in a block blocks also affect scoping which leads as to the next section variables you declare variables using VAR statements if you omit the initializer the variables value defaults to new okay side note this one this is one of those cases where not having nil and forcing every variable to be initialized to some value would be more annoying than dealing with nil itself okay let's see V variable no uh a variable equals to variable can be assigned to a new value and then it now equals to Great once declared you can naturally access and assign a variable using its name VAR breakfast bre breakfast equals Bagels PR breakfast what's benets B bits bits bits how is it pronounced b b Ben Ben v v ban ban Bane be breakfast equals be Bring breakfast be side note can you tell that I tend to work on this book in the morning before I've had anything to eat I won get into the rules for variable scope here because we're going to spend a surprising amount of time in later chapters mapping every square inch of the rules in most cases it works like you would expect coming from C or Java control flow it's hard to write useful programs if you can skip some code or execute some more than once yeah so an if statement a while loop all of these work exactly like in C except that uh you cannot use A++ because this potic operator is not implemented functions a function call expression looks in uh the same as it does in C make breakfast bacon eggs toast you can also call a function without passing anything to it un like in say Ruby the parentheses are mandatory in this case if you leave them off the name doesn't call the function it just refers to it a language isn't very fun if you can Define your own functions in locks you do that with fun side note I've seen language that side note I've used Lang I've seen languages that use FN fun Funk and function I'm still hoping to discover a fun funy or funo somewhere now is a good time to clarify some terminology some people from around parameter and argument like they're interchangeable and to many they are while we're going to spend a lot of time split split in the finest of Downy hers around semantics so let's sharpen our words from here on out an argument is an actual value you pass to a function when you call it so a function call has an argument list sometimes you hear actual parameter used for these hang on I'm going to check how how I'm going to check how much is left of this chapter classes prototypes classes in logs okay okay so basically I'm tired so I assume the the viewers are also tired uh so I'm going to to to skip the rest of this chapter for the purposes of this video I probably probably will uh also read it if this video is successful at all and uh I'm hoping to make the actual video when we start writing The Interpreter tomorrow and uh if you have enjoyed this video please consider liking and subscribing and or telling your friends about at least this amazing book and and uh if you if you did not enjoy it please roast me in the comments uh this is also very helpful for the YouTube algorithm also I actually wanted to make something more ambitious but it turns up turns out that the YouTube algorithm wants me to to spit out a lot of a lot of content it doesn't have to defin it doesn't necessarily have to be high high quality content so I'm just going to spit out a lot of content and uh also it turns out that the most successful part of my channel have been the carigan en Richie videos so I'm also hoping that if we have a nice book like this one and if we just read it and do the exercises on screen somebody may like it and uh my name is Carol moros and you have been watching make programming fun again bye