Building a Tree-Walk Interpreter: AST Evaluation for Arithmetic Operations

[00:00:00]hey what's going on everyone welcome back to my Channel today we're going to resume with part four in our interpretation series and we're actually going to get started with The Interpreter which is really exciting by the end of this episode we'll have our AST be able to do arithmetic operations and yeah but before we can get on to The Interpreter I wanted to add to the lexor a new type and this is going to define a null value so null is going to be just like what it is in JavaScript it's going to be a undefined value so we're going to add the null type to our Luxor and then I also want to add the null type to our keywords list right so to support null we need to be able to support the null keyword when it's encountered in source code as well as inside of the tokenize in here when we check for reserves I also want to change the way this works so instead of just saying if reserved is not undefined I want to do if type of type of Reserves is equal to a number right because the type is token type which is an enum so it'll return an integer so if it's a number watch your turn back and that's really important for how we want to handle this okay so that's actually it for Alexa now we need to add new support for our null type in rast so I'm going to come up here and create a type called null literal so it's an old literal now we're going to need to implement this custom type so I'm going to export an interface called null literal where the value is a string literal of null so we'll change this to null literal like so and there we go now we have our custom null type let's implement it quickly in the parser now if we go on down to the primary expression there we go we can see where we handle identifiers numbers and then open paren Expressions let's also add supports for our null so we're going to do case of token type dot null if we find this what we want to do is we actually want to eat the token first so we're going to do list.eats like so to advance past no keyword and then we're just going to do return the is going to be a null literal with the value being null and we're just going to say this is as a null literal like so so there we go we're just going to Simply return anal literal the reason we're eating is because currently if we were to um do it like this it would be kind of messy with the type since it was a string not of type null so we just eat beforehand so that we could Advance the token so let's just really quickly test this out and we're just going to do a quick dinner run Dash a mean.ts we get our Ripple and we can do null and we can see we get a type of null literal we can also say 10 plus null and so we get the proper binary expression now that we have this working let's actually go ahead and Implement our interpreter so I'm going to exit out of here clear the terminal close the parser close the AST and ratcheting in the creates a runtime folder just like here that's in parallel to the front end folder from this runtime folder we're going to create two new files value dots TS as well as dot TS interpreter.ts and values.ts values is going to Define the types that we're going to be using for our runtime right because at runtime we have no clue if have values a null a Boolean a custom object a function Etc so here we're going to have value types which is just going to basically be another tagged Union very similar to our node type so I'm going to create a value type field here and we're going to support two types null as well as number like so okay and and this is tight knots like that okay so we now have added those let's create these two types so we're going to create a interface called um runtime a runtime value and it's simply going to have a type field which is going to be your type value type like so now we're going to want to create our null type so export interface null value or we'll call it null vowel extends a runtime value right the type is going to be now it's going to be null in the value is going to be no like so and there we go now let's also add two more things let's go ahead and add the number type so a number value is also going to extend a runtime value the type is going to be a number and the value is going to be of type number like so okay so that's actually it currently for our value type in the future we'll add support for custom user-defined functions objects booleans and strings but for now this is fine so now we can get rid of our values and we're actually going to want to Imports um them from our values.ts so we're going to want to import the value type in runtime Val value type and run time Val like so we're also going to want to import our AST node type as well as all these types so we're going to import node type statements Etc from our AST front ends so that we can actually Define our parser okay so we're pretty much done with the types and imports now let's actually get into the fun things and that is importing our actual interpreter now to do this I'm going to create a function which is going to be called export function and it's going to be called um interprets or actually we can call it evaluate like so it's going to take in the AST node in the AST node is going to be of type statements like so in the return type is going to be a runtime value because at this point in time we'll actually be evaluating these nodes and translating them into values like so so what we're going to do is we're going to wants to switch over this AST node dots kinds and we're going to want to handle all of the different types of AST nodes that we can get right we have a whole bunch that we created before and now we want to be able to handle these so let's go ahead and add the case for a simple um let's see let's add the case for the numeric literal so we're going to do case node sorry not node node type oh sorry it's a string yes so case of numeric literal and what we're going to do is we're just going to return actually we can simply just we know the node type here if it's a numeric literal we know a numeric literal is going to contain a value like so so we can actually just do return an object which is going to contain the AST um oh we're going to cast it so AST node as a numeric literal dots value and this will be the value like so let me add this and this and this is as and um vowel like so so it has the value and we also need to do the cons or type of number so there we go this is what we can do if we encounter a numeric literal it looks a bit ugly but it's basically like casting because right we don't know what type an AST node is so we need to it's just a type statement so with this case we can actually Define and say okay we know it's a number now so we can cast it get the numeric value and then return its like so so now we've handled the case where we have our number volume so that's pretty cool let's handle the case where we get a um no literal so actually we'll have this be the default case so we'll do defaults and we're just going to return a null so the value is our type null and you type is of type null I'm just going to say it's as anal value like so so that is actually all we need right now to start interpreting data so to actually show that this works what we can do is we have this evaluate node which will allow us to create a runtime value based on an AST node so let's actually go ahead and inside of our main let's import and let me make sure I exported it yep export function evaluates so we're going to import evaluate from dot slash Randy runtime slash interpreter like so and now instead of just logging the tree what we're going to do is we're going to const results is equal to and we're going to do our evaluates on our program like so because again a program type is of type um result like so now what I want to do because what will happen is is if we just log the AST node we'll notice says it'll never work because a program is never going to be of type numeric literal right so let's just quickly run this and see what happens so we type 10 plus 5 and here's what we get we get our kinds and our body like so let me also log the results and let me just log some space so it's really clear what's happening okay so we do 10 and with the value 10 what you'll notice is the return type is a null program right and it makes sense a program has a body field so it'll never match that case so what we're going to want to do is instead of in the null case doing this what we're going to do is we're going to handle the case where we get a null literal we're going to return like we did before and in the default case we're going to console.error unrecognized or we could also say um this AST node has not yet been set up for interpretation and let's pass in the AST node and then we're just going to do a Deno dots exits of one like so so now if we actually give this a go we can see that if we type in anything we're going to get this AST node has not yet been set up for interpretation right because we haven't supported the kind of a program yet so that's actually really good so I'm also going to get rid of this console log here I'm going to get rid of this console log there and if we end up getting a result we'll actually log it out okay so we've handled two literal cases we won't handle identifiers in today's video because identifiers require scope and variable resolution but let's actually now Implement our support for um binary Expressions so let's go ahead and do that so I'm going to create a function which is going to be called exports actually we don't need to export it we can just call a function called um evaluate binary expression and it's going to take in the expression or what's called binoc which is going to be a type binary expression like so the result is going to be of type runtime value and there we go so what we're going to want to do is actually call this from our evaluate function so let's go ahead and add that so for the case of numeric literal we can lower that we can get rid of that and okay for the case of case of binary expression we're going to want to return the evaluates binary expression and what we're going to do is we're just going to say the AST node is of type binary expression like so okay so now we can handle numeric literals no literals binary expressions and let's add the final type that we'll need to be able to handle with our interpreter for now and that is a type of program right to evaluate a program we're also just going to separate that into its own function eval program which is going to take in a program of type program and it's going to return a runtime value like so so I'm going to change the name from evaluates to eval because I kind of like the shortness of it and we're going to call if it's a case program we're going to return our eval program case and we're going to do AST node as program like so okay so that looks really good now we can actually build out these two functions so we know for evaluating a program right if you imagine this code right here it's going to run top to bottom and return the last result that was evaluated right the last block evaluated so we might want to keep track though last evaluated is of type runtime value and let's just give it a default of being null so let's just say the default kinds or type is null and the default value is no let's do it as a null value like so and what we're going to do is we're just going to return the last evaluated in our program and what we're going to do now is we want to iterate over the program.body so for const Ates mint and what we're going to do is we're going to iterate over the statements of the program dots body and in here we have a statement and what we want to do is we want to set the last evaluated value to the results of evaluates on this statement so we're just going to do last evaluated is equal to evaluates on statement like so and there we go now whatever the last block that executes in our body will actually be executed this will go on to the last evaluated and we'll return it so there we go that looks really good okay now we want to implement the evaluate binary expression so for evaluating a binary expression we want to make sure at first that we're actually dealing with two numeric types so what we're going to do is we're going to do const left hand side is equal to evaluates we're going to evaluate the binop.lefts and we're going to do const rhs I'm going to also rename this to LHS is equal to eval ina.org just like so so now we have the left hand side and the right hand side and what you'll notice is is there of type runtime value now so at this point rhs will have a type and if it's of type number we know we can do binary operations on it however doing binary operations on null values doesn't work doing binary operations on a string like a plus does work so in the future we'll handle complex types like that as well but for now we want to check that both of these types are not null so we'll just check that they're both valid numbers so we'll say if LHS DOT type is equal to number and rhs DOT type is equal to number then we're just going to return a um we're going to evaluate these as binary Expressions so we're going to do eval numeric expression like so and we're going to pass in these two as numeric values so we're going to say LHS as num Ravel rhs as number boom like so and there we go and then else one or both are null then we're just going to return a null value so we're going to do return type is going to be null value is going to be null there we go because right if you try to add or subtract or divide null onto something you're gonna get null so that's what we're going to do we're going to handle null like this so there we go now we just need to implement eval numeric binary expression like so so let's go ahead and implement this I'm going to kind of hide those two and in here we're going to Define our function like so it's going to take in two number values number vowel rhs so type number vowel and it needs to take in an operator before it forgets which is going to be of type string and it returns a type of number vowel like so so let's go ahead and Define the logic for this function as well as pass in the binary operator so we do bun up dot operator to get the operator okay so now we have the left hand side right hand side and the operator and we know these are all numbers so it really is as simple as const um num is equal to or let's just call it results is equal to zero we can actually set this as a let so we can reassign it and then we're just going to do a quick switch over our operator uh actually we'll just do an effects of the cleaner so if operator is equal to a plus results is equal to LHS dot value plus rhs dot value right because that's all it is we're just adding these two values and we're dealing with the raw values at this time then we're going to want to add the else if for the subtraction subtraction like so we're going to add the multiplication multiplication we're going to add the division division like so and we're going to add the we need to add the modulo operator right so the result is going to be the results of a modulus operation like so so now we have this number value in result which is going to be populated with the results of these binary operations addition subtraction multiplication division modulus here you notice um we're not doing any division by zero chicks that's something you'll want to do with your language or handle try catches something like that but for now we're not going to be implementing that just yet and now we have a result type so what we're going to want to do is instead of just defining it to a number like that's we are going to actually now return a value that is going to be a number value so what we're going to do is we're going to return it's going to have a value field of results and a type field of number and there we go we have now evaluated binary Expressions that are in the numeric form so let's kind of quickly take a look at what we just did right so I'm going to open up all these okay so we start off by evaluating any node which in this case is going to be a program coming from our parser we evaluate the program by iterating through all of its children in returning the last evaluated element if there's no elements in the program it'll just return a null value so that's it for that we also evaluate numeric literals by just getting the raw value right so when we do binary operations and such like that it's going to return to a no literal as well as null literals and binary Expressions we evaluate a binary expression by first making sure we actually get the left hand side and right hand side value so we recursively do this and then we make sure that both of these are numeric values in the future we'll make sure that they're numerics then we'll handle oh well what if one's a string and a numeric stuff like that so that is it for our interpreter at least right now I'm going to get rid of this value type Imports and in the main.ts let's actually give this a quick run and see how this all works so I'm going to clear the terminal into deno.run main.ts and now let's try typing in something like 10 plus 5. and what do you know we get a value of 15 and a type of number this is the runtime type however we can try evaluating something like null we get the value of null and the type of null if we evaluate something like 10 minus 5 times 2. what we'll notice is is it'll follow the order of operations so instead of doing 10 minus 5 first giving 5 and then times 2 giving 10 it'll do 10 minus 10. or times two right minus 10 so it'll give zero and we can see that it follows the order of operations properly we can also see that 10 modulus 2 will return the no remainder while 10 modulus 3 is going to return remainder one so that seems about right we can also make sure that we can't add nulls so null plus null is going to be null however null plus 5 is still null and that looks right currently though if we type something like Foo bar we see this AST node has not yet been set up for interpretation and it's because we don't currently support symbols or identifiers like so so we now have a working Rebel at least four binary operations so we can do complex operations any arithmetic with addition multiplication subtraction and division as well as modulus so in the next video we'll continue where we left off and make our language just a little bit better I'll talk to you then bye