Making a ProgLang - Evaluating ASTs

In this drive by session Waikit and I continue our journey of building a baby programming language. Previous we created a parser that generates a AST representation of the code. Now we’ll write an evaluator that takes that AST as input and evaluates the result of the program.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello and welcome to a drive-by code
00:02 : session and this is another one in the
00:06 : series on how to make a programming
00:09 : language and currently where we are is
00:15 : we have written a parser described by
00:19 : this grammar which we've been working
00:22 : out working on throughout the series
00:25 : which at this point it is able to build
00:29 : an AST and what is an AST well an st
00:33 : looks like this st is a description of a
00:37 : piece of code and in this case we have a
00:41 : per script which has been written to
00:44 : parse this expression that that's the
00:47 : code that went in as the input so looks
00:52 : kind of like this so the code in this
00:56 : case is 1+1 we this is a string as
01:00 : evidenced by the double quotes we're
01:05 : going to feed that through our parser
01:08 : which our parser again is sort of
01:12 : specified or written in the form of this
01:15 : nearly GS grammar and if you need to get
01:20 : caught up on all of this by all means
01:23 : please watch the previous videos in this
01:25 : series but after this string is fed
01:31 : through this thread through our parser
01:35 : then what we get is an ast also known as
01:40 : abstract syntax tree and what what does
01:46 : an extraction abstract syntax tree look
01:50 : like well it looks like this guy here we
01:54 : have represented this abstract syntax
01:56 : tree as a JavaScript object in something
02:01 : that's serializable in JSON format in
02:03 : fact and we're basically saying the
02:07 : representation of this piece of code
02:10 : here one plus one is
02:13 : it is a operation it in particular it's
02:16 : a plus operation
02:18 : so we're saying this whole thing here
02:21 : it's a plus operation and which has a
02:26 : left-hand side and a right-hand side I'm
02:32 : basically writing out the visual
02:34 : representation of this where the
02:37 : left-hand side is a number which happens
02:41 : to be a1 and the right-hand side is
02:42 : another number which also happens to be
02:46 : one so this sort of graphical
02:49 : representation of this tree there's what
02:52 : tree abstract syntax tree is represented
02:55 : in this way in JSON format
02:57 : and that's what we have so far if you
03:01 : want to know how we got here
03:03 : watch the previous videos in this video
03:06 : I'm gonna take this ast that comes in in
03:10 : this JavaScript format and we're gonna
03:14 : evaluate the answer so this is and like
03:21 : I mentioned at the previous video there
03:23 : are multiple purposes an ast can surf
03:28 : including you can use it to evaluate the
03:31 : answer but you could use it to check for
03:34 : maybe errors in the code in a linter
03:38 : using a linter or something like that
03:39 : but you can also use it to generate the
03:43 : equivalent code in another language in
03:46 : this episode though we're just gonna
03:48 : write a function that takes this AST
03:52 : structure as the input and it should
03:55 : return a numerical result back so the
03:59 : correct answer for this ast for example
04:01 : should be the number 2 so let's see how
04:04 : we do that again
04:07 : why kit wrote this code I'm just going
04:10 : to replay what he wrote and explain what
04:14 : he did
04:14 : so this get started okay so the first
04:18 : thing he does is he's gonna write an
04:21 : evaluate script which is gonna read in
04:24 : this ast dot JSON file
04:26 : and then it's gonna try to evaluate that
04:30 : I presume again he uses the MZ library
04:34 : to read in the file and I've made a
04:37 : video on using node with async/await to
04:43 : read files using the MZ library so if
04:47 : you want to learn more about that you
04:49 : can check that out
04:50 : okay so first we're gonna use read the
04:54 : file read this st dot JSON file we're
04:57 : gonna use async away to await for the
04:59 : contents of the file and then we'll turn
05:03 : the string buffer to a string which we
05:06 : can then since the content is actually
05:12 : in JSON format we're gonna use JSON dot
05:15 : parse the native JSON that part's not as
05:18 : json dot not the json parser that we
05:21 : wrote in the previous episodes and
05:25 : that's fine maybe in some other other
05:29 : scenario we'll use our own json parser
05:31 : but that's not the point here
05:33 : the point here is we want we already
05:36 : have a AST sort of structure and we're
05:40 : gonna try to evaluate the answer based
05:43 : on that structure so if we evaluate at
05:46 : this guy for example we should expect
05:48 : the result to come out with two and and
05:53 : then we'll print the answer
05:55 : I don't need did this evaluate function
05:58 : so so let's write this evaluate function
06:01 : he's gonna not just as a dummy
06:04 : placeholder return 0 for now to just to
06:08 : be able to debug the rest of this script
06:10 : see if everything is working right so
06:12 : run this evaluate script and the answer
06:15 : is 0 ok now let's do something closer to
06:20 : what we're trying to achieve here so
06:22 : note we in so far in our grammar we have
06:27 : sort of created the grammar the ast
06:33 : grammar contains three types of notes
06:38 : an operation note number notes in in
06:43 : function call notes because that's what
06:46 : the grammar supports at present they're
06:50 : all the places where it has like a type
06:53 : discriminator of like this okay so so if
06:58 : we want to be able to evaluate a note
07:00 : then we need to set up set up handling
07:07 : code for each of these types however if
07:12 : it's not one a type that we know about
07:14 : we just kind of throw an error here okay
07:20 : and we're actually going to start with
07:22 : the simplest possible case which is just
07:25 : a plain number so if you get a plain
07:28 : number in the code and it will parse it
07:32 : so we re parse it and the ast should
07:36 : look just like that it's the code it
07:38 : simply represents a number which is 1
07:40 : and if we evaluated that or how do we
07:45 : get how to evaluate a plain number well
07:47 : if we called evaluate function on this
07:51 : number let me split this up actually so
07:55 : we're gonna have three pain a
07:59 : three-panel situation going on here okay
08:02 : so we feed this object feed this guy in
08:09 : here as no we it's gonna fall into this
08:13 : case here because the type would be
08:15 : number here mattress this and if we want
08:19 : and we want the answer to be the value
08:22 : of the number well easy just return the
08:24 : value of the number so let's go ahead
08:28 : and do that there and we run the script
08:31 : and evaluates to 1 so the answer the
08:36 : answer
08:39 : evaluating the code one is one that
08:43 : seems logical let's do something a
08:45 : little harder it's 5:00 we change the
08:49 : number to 5 then it's 5 that's fine
08:53 : let's go back to 1 plus 1 now so now if
08:57 : we change the code to 1 plus 1 and we
09:00 : parse it again now after they have this
09:03 : AST so given this ast we're gonna need
09:08 : to change the evaluate function to be
09:12 : able to handle this and this time since
09:15 : the node we're feeding into the function
09:20 : is actually a type of operation is gonna
09:25 : land in this this if statement Clause
09:30 : and here so what are we gonna do we have
09:32 : to write some code here to make things
09:35 : happen actually gonna recursively call
09:39 : the reevaluate function on both the
09:42 : left-hand side and the right-hand side
09:45 : of the operation and what that's gonna
09:48 : do is basically so this call evaluate is
09:55 : gonna take note that left which is this
09:57 : guy and sort of feed it back into here
10:02 : in which case it'll return the number 1
10:06 : here and same thing happens for the
10:09 : right hand side so we did the same thing
10:11 : feet and right hand side over here and
10:14 : it's going to return the 1 here so that
10:17 : actually yields oops one in the left
10:26 : variable and one in the right variable
10:28 : as well and then we just have to put
10:31 : left and right together
10:32 : based on what the operator is here okay
10:40 : and we do that with a switch statement
10:43 : so case plus we're gonna add nothing
10:47 : right together if it's - we're gonna
10:49 : if it's the multiplication symbol we're
10:53 : gonna use the star symbol in JavaScript
10:56 : to multiply them together and we also
10:58 : want to support division so but if the
11:02 : operator is not something we support
11:04 : then we're gonna throw an error by the
11:09 : way sort of preemptively throwing errors
11:12 : like this is in general I consider it to
11:14 : be a good practice because it hates
11:17 : debugging in case the logic of your code
11:21 : is wrong it would hit sort of an error
11:24 : if your and and it was sort of like
11:27 : prompt you to fix something about it
11:30 : before before the error sort of goes
11:33 : into a more complex route okay okay so
11:41 : we get one plus one answer of one plus
11:44 : one is equal to two now and that's great
11:47 : and what is also great is now this is
11:50 : actually already able to support more
11:53 : complex statements because if if in the
11:57 : event the left-hand side happened to be
11:59 : another operation this evaluate will
12:03 : also be able to handle it as well
12:04 : because we already have the case to hand
12:08 : the case to handle operations and that
12:11 : really is the beauty of recursion here
12:14 : okay let's keep going
12:17 : so does it handle two plus one so this
12:22 : is the AST now the updated Oh or do we
12:25 : call it two plus three
12:27 : oh yeah we turn it to two plus three and
12:29 : that's the new version of the AST and if
12:33 : we evaluate that answer is five so it
12:35 : seems to handle that just fine all right
12:39 : let's go back to a two pain situation
12:42 : okay so now we want to handle function
12:46 : calls
12:47 : handle the power function take two to
12:50 : the third power for example and that is
12:54 : the ast associated with that power
12:57 : function and call but our evaluate
13:01 : function obviously needs to be modified
13:03 : to handle that case so we'll say okay
13:07 : what is the function name now the
13:10 : function name comes from the court it's
13:12 : called fun name it comes from this ast
13:16 : note so if we're going to assume that if
13:19 : the type of DST know is a function call
13:22 : then it will have a fun name which this
13:25 : example does have and so if it's tau
13:29 : we're gonna take the arguments and sort
13:33 : of spread them on to the math dot pal
13:36 : function so we really we know there's
13:40 : two arguments oh this map evaluate by
13:43 : the way is to we know there's two
13:47 : numbers here we want to send these
13:50 : numbers also into our evaluate function
13:54 : so that we can convert this ast node
13:56 : into a raw number and that's what this
14:00 : Clause of the if statement would have
14:02 : done for us at this point in time we
14:05 : would have had hearts be two and three
14:13 : had here because the arguments the
14:17 : arguments are this array and for each of
14:21 : the things in the array we're sending it
14:24 : over to evaluate so going in here to and
14:31 : it would have hit this this type
14:35 : checking Clause and it would have
14:37 : returned just the value inside that
14:40 : number note so that that's how we're
14:42 : getting this being two and three here
14:45 : and then we just this is equivalent to
14:47 : saying math that POW two comma three
14:50 : here given an array and you spread it
14:52 : over the argument list like
14:54 : and well we add it I we might as well
14:58 : support the other functions as well and
15:02 : these are all the built-in functions
15:04 : that this grammar supports currently I
15:07 : have power square square root sine
15:10 : cosine and absolute value so at this
15:12 : point we can we can support function
15:17 : calls now to two to the power of three
15:19 : is eight and it seems correct let's do
15:22 : something else
15:23 : sine sine of two and two reparse it to
15:29 : get to get this new old version of the
15:31 : AST which represents a sine of 2 and
15:34 : evaluate it and that's the answer I
15:37 : don't know whether that's correct
15:40 : off the top of my head unfortunately
15:42 : maybe I can use my computer's calculator
15:46 : to do it
15:47 : Oh point nine zero nine yeah so that is
15:51 : correct it did the right thing okay
15:54 : we'll do square square of four minus
15:57 : three okay
15:59 : it's just testing out some different
16:01 : cases and now he's actually compounding
16:04 : some function calls with an addition
16:07 : operation and the EST for that operation
16:12 : is this big old mess so if you if you
16:18 : drill into it it actually should make
16:21 : sense that the way that these operations
16:23 : and function calls are combined evaluate
16:28 : it and it gets us an answer so all of
16:30 : this seems to be working yeah yeah and
16:35 : that that's how is how you that's how
16:39 : you take an ast which is recursive in
16:42 : nature and use a recursive function to
16:45 : to handle the ast traversal one thing I
16:50 : want to illustrate a little better is
16:53 : how recursion works so let me let me
16:58 : give another example
17:04 : so let's let's let's use it like a semi
17:07 : complex expression such as 2 times 5
17:14 : minus true let's say we first of all
17:19 : let's parse it and okay so we parsed it
17:24 : and this is the resulting ast which yeah
17:31 : and I mean I can I can depict it
17:34 : visually as something like this so at
17:37 : the top level there's a multiply
17:40 : operation and then on the left hand side
17:42 : is a number two on the right hand side
17:47 : is an yet another operation though it's
17:49 : a minus the left-hand side of the minus
17:52 : is a five and the right hand side of the
17:55 : minus is 2 2 so this is 2 times the
17:59 : result of 5 minus 2 it's our operation
18:03 : and just so you can see it
18:07 : the original was that okay I'm gonna
18:15 : draw the stack frame representation
18:16 : which is the how your program keeps
18:22 : track of its state well is X key well
18:25 : it's executing and every single time you
18:27 : call a function it actually creates a
18:31 : new frame in something called the stack
18:34 : so initially you're actually running in
18:40 : main stack frame I'll call this the
18:44 : stack frame stack frame is where the
18:47 : function stores all of your variables
18:51 : that are present in your function so in
18:54 : the main function we actually have a few
18:57 : variables we have contact result in ast
19:00 : so it will actually look like this
19:05 : content
19:07 : I'll make a little table here
19:14 : content actually is gonna look like
19:18 : exactly this in the form of a string the
19:23 : ast is gonna look like this guy here
19:29 : that is the ast or at least the visual
19:33 : depiction of it but the more literal
19:37 : version is this it's this complex
19:41 : JavaScript object is what a STS and the
19:45 : result is still waiting for an answer or
19:49 : waiting for a value I should say so we
19:53 : created the result
19:57 : on this line but not before the evaluate
20:01 : function call finishes okay so now on
20:06 : this line here evaluate gets called and
20:09 : when that happens
20:12 : javascript is gonna create another stack
20:16 : frame which is something that happens
20:18 : whenever a function is called and
20:21 : evaluate is called with ast as the
20:24 : parameter so the parameter that goes in
20:28 : is actually the same this same structure
20:32 : the same AST structure goes in to
20:35 : evaluate and we're gonna have to sort of
20:37 : create another another table for
20:41 : evaluate to use and so far we don't have
20:47 : any variables to find and but the first
20:50 : thing we're gonna do is do this if
20:51 : statement right so if statement is this
20:54 : guy a number that the entire ast and by
20:58 : entire AST we starting from the root
21:01 : node here right so the root node is
21:04 : actually a multiplication operation so
21:07 : it's not a number it's not gonna go in
21:09 : here it is an operation so this is where
21:12 : it will go and so then it's gonna go
21:17 : it's gonna evaluate this line which
21:19 : creates another evaluate function call
21:22 : by passing into passing note that left
21:26 : into it so JavaScript will actually have
21:31 : to make yet another stack frame and yet
21:33 : another table just to evaluate the left
21:39 : value of this multiplier operation and
21:42 : what goes into here well that's the left
21:45 : of the multiply node which actually is
21:47 : just this guy that goes into here so now
21:53 : we're in the same evaluate code again
21:56 : but only this time is not with the
21:59 : entire AST but with just this two node
22:03 : within the AST so now we're gonna do
22:07 : this test note that type equals number
22:09 : and that is gonna be
22:10 : so it's gonna land in this conditional
22:14 : here it's just gonna return note that
22:16 : value and so I'll say it's gonna end up
22:22 : with the return value of two here okay
22:26 : and when that happens the return value
22:30 : of two comes back this guy can get
22:35 : erased because the job of this previous
22:39 : evaluate left call has done and the
22:42 : return value to it gets assigned to left
22:46 : okay so we're done with this line to
22:49 : evaluate left and we got the value of
22:52 : two the number two for for the evaluate
22:59 : call to this sub note 2 but the next
23:04 : line is yet another is called to the
23:06 : evaluate function now we're trying to
23:08 : get at the value of the right hand side
23:11 : or the numerical value of the right hand
23:13 : side but in order to arrive at that we
23:17 : need evaluate to do its job yet again
23:20 : but this time to note that right what is
23:25 : note again well the note in this case is
23:28 : actually the entire ast tree again so
23:31 : the right hand side of this
23:33 : multiplication operation is that guy so
23:40 : we're feeding that guy into evaluate
23:42 : this time now and what is that guy let
23:47 : me make a cable for this guy this guy is
23:50 : yet another operation so this time
23:52 : around it's going into this operation
23:55 : clause of the if statement yet again and
23:58 : it's gonna need its own left and right
24:01 : so left how do we get the answer for
24:05 : laughs we need yet another evaluate call
24:08 : and you can see we have more and more
24:12 : stacks stacked up and in fact we'll have
24:15 : as many stacks of evaluate calls for the
24:22 : height of the tree because this
24:24 : three is three levels deep one two and
24:27 : three will end up having three levels
24:30 : worth of evaluate costs deep in the
24:34 : stack to handle all the way down so this
24:38 : time evaluate for for the left-hand side
24:42 : of the the subtract operation it's gonna
24:47 : be this five so five is going in here I
24:52 : need another table we're gonna have to
24:54 : like move over here to keep going okay
24:58 : but anyway the five though because
25:03 : that's a number it'll hit this branch
25:05 : here and just return their value five so
25:08 : the return value here would be five
25:11 : actually I get you can actually cross
25:14 : this out because we got a return value
25:16 : return value is five this gets crossed
25:19 : out and we're back here because the
25:22 : previous one was waiting for the left
25:23 : value so 5 goes into the left value of
25:26 : the parent stack so 5 goes into here and
25:30 : let me erase all this stuff now okay so
25:34 : now we're we're here and we have
25:37 : completed this line and the next line is
25:40 : gonna be that so we're gonna make a
25:44 : right variable here our slot for the
25:47 : right variable but in order to get its
25:49 : value we need yet another evaluate call
25:59 : and this time note that right because no
26:01 : we were talking about this sub note here
26:03 : because that's node here the right of
26:08 : this sub note is this number two here so
26:11 : this time it's the number two number
26:13 : node that's going in we're gonna make a
26:15 : table here not because it's a number
26:19 : it's gonna take this branch and it's
26:21 : just gonna simply return to the notes
26:25 : value which is two so the return value
26:28 : is two and because the function returns
26:32 : now or this version of the function call
26:34 : returns this is gonna go away this two
26:37 : will make its way over to here in the
26:41 : parent version of the evaluate call
26:44 : there was this line here and the two
26:47 : goes in here so now at this point we
26:51 : have the numeric value for both the left
26:55 : and right value at this point and
26:59 : associated with this - node and then
27:03 : what this code is going to do is select
27:05 : one of these branches in this case it's
27:08 : gonna select this one because the
27:10 : operator is - and it's gonna perform
27:13 : this subtraction with the ready numeric
27:17 : values here so and it's gonna return
27:20 : that so I'm gonna make a slot for the
27:23 : return value and the result of 5 minus 2
27:28 : is 3 so now because this function is
27:32 : returning now this stack frame can go
27:36 : away while ticking the return value 3
27:40 : and returning it to the parent and in
27:43 : this case this whole operation was done
27:46 : for in the parent version of the
27:50 : function call for for this line because
27:52 : it was calculating the right hand side
27:54 : of this multiplication operation here so
27:58 : the 3 belongs in this right variable
28:04 : here okay let me erase
28:07 : frame now and we have the numeric value
28:11 : of both the left and right hand side of
28:15 : this multiplication operation and so and
28:18 : we just got done with this line
28:21 : basically and again we're gonna select
28:24 : one of these operation paths to go down
28:27 : and this time is gonna select this one
28:29 : because you would have a multiplication
28:31 : symbol and it's gonna return the result
28:35 : of left x right so the return value is
28:41 : gonna be 2 times 3 which is 6 and again
28:45 : because we have returned from this
28:48 : function this guy can go away
28:50 : oops this guy can go away well taking
28:53 : this return value and sticking it back
28:56 : over here over it the main function
29:00 : because the line that actually kicked
29:04 : off this entire series of events with
29:07 : this call to the evaluate function with
29:10 : the entire AST tree and the final answer
29:13 : is 6 and the 6 is gonna it's the return
29:18 : value of the evaluate function gets
29:20 : assigned back to the result variable
29:22 : over here and therefore the final answer
29:25 : final result is 6 and so this is the
29:29 : final state of things and because we
29:32 : console dialogue the answer I'm gonna
29:34 : expect this program to produce on the
29:39 : console the answer is 6 so why don't we
29:44 : actually execute the program now and see
29:47 : if we are correct about that and it is
29:52 : awesome ok so so that's how this
29:54 : evaluate recursive function works I hope
29:58 : you enjoyed it and the next time the
30:03 : what we'll probably do is instead of
30:06 : evaluating the answer or it'll make a
30:08 : code generator that would generate the
30:10 : equivalent JavaScript to to execute or
30:16 : evaluate this expression so if you are
30:19 : interested in
30:20 : that I will see you next time thank you