How to Build a Code Generator

In this drive by code session WaiKai and I show you how to write a code generator: a program that spits out JavaScript code based on the AST (abstract syntax tree) of our small math arithmetic language.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello and welcome to another drive-by
00:02 : code session this is going to continue
00:05 : our series of of the making a
00:10 : programming language series and this
00:12 : time we're going to make a code
00:14 : generator that spits out JavaScript
00:18 : let's review
00:20 : so so this is how a programming language
00:24 : works so this is prog
00:29 : programming language in the first part
00:32 : of the series we build a parser which we
00:35 : did that using nearly Jas and the job of
00:41 : the parser is to take the code that is
00:46 : written by someone using your
00:49 : programming language and spit out an ast
00:53 : which we have done that in a previous
00:56 : episode ast stand for abstract syntax
01:00 : tree and it is a true representation of
01:04 : what your code is but you know format
01:08 : that another program another program I
01:12 : should say can understand so you know in
01:16 : the previous episode we wrote such a
01:19 : program
01:20 : it was the evaluator the evaluator took
01:26 : the ast and generated a result to your
01:30 : program which in our very small math a
01:34 : rhythmic program it was to do some math
01:37 : calculation in this episode we're gonna
01:41 : make a separate thing called the
01:44 : generator which does not give you the
01:49 : result right away but rather it gives
01:52 : you JavaScript code but the JavaScript
01:56 : code in reality is another box which can
01:59 : be executed and then that in turn will
02:03 : give you the result so basically instead
02:05 : of calculating the result directly using
02:09 : our tote our code is actually going to
02:11 : be a generator
02:12 : of some JavaScript which when executed
02:15 : will then yield the result so that's the
02:19 : plan let's see it in practice again why
02:26 : kid real code I'm going to replay what
02:29 : he wrote and explain what he did so
02:32 : let's get into it so first he creates a
02:34 : generate that Reyes script and he's
02:37 : going to use our trusty MZ library and
02:41 : so that we can use async/await style
02:44 : Java Script to deal with the file system
02:48 : and if you're interested in into getting
02:51 : into more detail learning more about how
02:53 : that works I have made a video on using
02:56 : async away with no GS you can go find
03:00 : that on YouTube okay so we're gonna make
03:03 : an async function it's called name and
03:07 : I'm gonna read in the content of the ast
03:11 : file and the ast file looks like this to
03:17 : remind you so this it's the contents of
03:20 : the ast file it's in JSON format and so
03:24 : we're just gonna use the native JSON
03:26 : parser to parse it and then we get our
03:28 : structure here and then we're gonna pass
03:33 : that to a generate function which has
03:36 : yet to be written
03:37 : but it's coming soon the job of this
03:40 : function is gonna be to generate actual
03:43 : JavaScript code which will be written to
03:46 : this file we call program Jas so just
03:50 : like that he's gonna put in a dummy
03:53 : placeholder or generating function for
03:54 : now just so that we can test this piece
03:58 : working so I see he types note generate
04:02 : but I don't think anything happened
04:04 : because he forgot to call the main
04:06 : function so it's try that and also have
04:09 : a little bit of printout to indicate
04:11 : stuff ended happened
04:14 : so no generate and now we have a program
04:19 : that yes and and it will print out hello
04:23 : world and you can even execute it so
04:26 : right no program
04:29 : he actually misspelled program I think
04:32 : that's the replayer the terminal
04:34 : recorder erroring out again but anyway
04:38 : so we have this program just that's
04:41 : generated by this generator yes but
04:44 : obviously that is not what we want it to
04:47 : be we want it to run this program to
04:50 : generate the program to actually compute
04:52 : the this operation that's desired based
04:58 : on what we put in to the parser which
05:01 : was that that was the original input if
05:04 : you look at well that was original input
05:08 : and so we wanted to actually compute the
05:11 : result of this computation so how do we
05:14 : do that
05:14 : well we actually let's start simple
05:18 : yes start simple with just a number one
05:21 : and if we parse that our ast file is
05:26 : gonna be just that representing a number
05:29 : one and so let's try to get that
05:31 : generating into a Java Script so all we
05:34 : need really is a JavaScript program that
05:36 : prints out one so like it extracts a
05:42 : function or maybe not extracts but
05:45 : starts a new function which will be it's
05:48 : called generate expression and it will
05:51 : be utilized inside of this generate
05:53 : function like so so and then the
05:58 : expression that it output will be a
06:01 : JavaScript expression which is suitable
06:04 : for putting it inside as the argument of
06:07 : the console that log
06:08 : ok so now all we have to do is to
06:11 : basically translate this ast note here
06:15 : to the string
06:17 : more or less yeah so that's easily done
06:22 : by saying if the type of the node is a
06:25 : number we're just gonna return its value
06:28 : that guy so the 1 is gonna make its way
06:32 : out here and then the programmer if we
06:37 : generate it again is simply consult that
06:41 : lock 1 we execute it and then we just
06:44 : get one perfect
06:47 : all right now what about 1 plus 2 so if
06:52 : we parse 1 plus 2
06:54 : we'll get this operation which is a
06:56 : composite object it has a left-hand side
06:59 : and the right-hand side each of them are
07:01 : notes number notes and so our generator
07:08 : now has to give a JavaScript expression
07:13 : there's a equivalent to this code here
07:16 : so how we're gonna do this here well
07:18 : first we need to test for the type right
07:21 : so let's test that to see that the type
07:25 : is operation in a case that the node
07:28 : type is operation we're gonna execute
07:32 : this generate expression function
07:34 : recursively on both the left and right
07:38 : hand side because both the left hand and
07:41 : right hand side are probably a number
07:45 : now or even yet another operation node
07:47 : and they will need to be converted to
07:53 : JavaScript so once you execute this
07:56 : generate expression function the result
07:59 : should be already in JavaScript form
08:02 : suitable for concatenating with more
08:07 : JavaScript then we need the operator
08:10 : which in the ast node that's up so we'll
08:15 : just grab that and then we'll put the
08:19 : three things together into JavaScript so
08:21 : assuming this is JavaScript business
08:23 : JavaScript and this is JavaScript we
08:25 : have
08:26 : a operation here in JavaScript
08:29 : let's try generating that and that's
08:33 : exactly what we should get and if you
08:37 : run the program we get three okay what
08:40 : about multiply we have a special
08:43 : multiply symbol in this arithmetic
08:46 : language and I don't think that's gonna
08:50 : work so well so if we did a generate
08:53 : parse and then generate with that we get
08:55 : a invalid JavaScript syntax so that's
08:59 : not gonna work so what we need is a map
09:03 : to convert the operators in the
09:07 : arithmetic language to the operators in
09:10 : JavaScript so we'll do that so this
09:14 : multiplication symbol goes to the star
09:17 : symbol used in JavaScript for
09:19 : multiplication and the divide simple
09:21 : goes to this slash symbol so we generate
09:25 : again now get the correct travel script
09:28 : and is able to run cool I see if
09:33 : composite operations work first so three
09:38 : plus two the result three plus two times
09:42 : well there should be a multiplication
09:44 : symbol I think you forgot to do that all
09:49 : right so what is the resulting
09:54 : JavaScript to match this program well it
09:57 : should look very close to that right it
09:59 : just did the multiplication symbol needs
10:01 : to change okay so let's see if it works
10:07 : we do if we do generate we actually
10:11 : don't preserve the order of operations
10:15 : that the parentheses have ordered so
10:20 : what we need to do is actually in the
10:22 : generate expression if we have an
10:25 : operator like this to be safe we want to
10:28 : put parentheses around them around the
10:31 : whole thing so that so this is an
10:33 : operation we want to put parentheses
10:35 : around it
10:36 : so that if it's combined with yet
10:38 : another operation in this case this one
10:40 : this will be done first and we get
10:46 : another extra set of parentheses here
10:49 : but does not worry about that this works
10:53 : and that's all that matters
10:57 : we have comparative operations working
10:59 : now and the next step is function calls
11:03 : so let's write an expression with a
11:06 : function call here we'll call it a
11:08 : function pal two to the fourth and if we
11:13 : post it then this is the this is the ast
11:17 : that we have so on the right hand side
11:20 : of this multiplication we have a
11:23 : function call expression or ast
11:28 : representation of the expression and
11:30 : we'll need a converter in JavaScript for
11:33 : that as well so again we'll add an else
11:37 : if statement to detect the function call
11:40 : and again we'll have a function name map
11:45 : if you look at our list of functions
11:49 : there are six of them
11:51 : and for most of them there's a direct
11:54 : function in JavaScript that we can
11:58 : translate it to so how is math dot pow
12:02 : square root sine cosine and absolute
12:06 : value all of those have an equivalent
12:08 : function in JavaScript to support that
12:12 : translation the only exception is Square
12:16 : which is we do just as the number of
12:20 : times itself that's a special case we're
12:24 : going to handle that next okay so so
12:28 : we're going to get the function name in
12:30 : JavaScript playing by looking up the
12:33 : function name map and using the fun name
12:36 : in the ast here and this fun name is the
12:41 : name of the function in our language so
12:44 : we're gonna again map that into the
12:47 : function
12:48 : javascript and then we're gonna call the
12:53 : function by that function name in
12:55 : JavaScript but we need the arguments how
12:59 : do we get the argument well for each
13:01 : argument which in this array which
13:05 : argument here is another ast node that's
13:10 : like this right so for each argument
13:14 : this one in this case there are two if
13:18 : we need to send it through the generate
13:21 : expression function to get some
13:32 : JavaScript and we need to do that for
13:35 : both of them so we're gonna use map to
13:40 : do that on all of the members of this
13:42 : array yeah so for each art which was an
13:46 : ast note we're gonna call ourselves Co
13:50 : to generate expression function again to
13:53 : get the JavaScript so this guy yields us
13:58 : JavaScript and then we're gonna the map
14:00 : it's gonna get an array of JavaScript
14:02 : expressions and then at the end we're
14:05 : gonna join them together with a comma in
14:07 : between to generate the argument less
14:10 : suitable for putting inside of these
14:12 : parentheses again in JavaScript land so
14:17 : I see that I'm gonna generate that and
14:19 : now we have there's two and four as the
14:23 : argument list we have math that POW
14:25 : inside of this JavaScript expression
14:28 : which should be runnable okay do we even
14:35 : run this program let's try the program -
14:40 : yes looks like this
14:43 : no probiem - yes yeah eighty is that
14:47 : she's ad correct 16 times 5 is 80 okay
14:55 : all right I'm bad at math okay so next
15:00 : we need to handle this square case so
15:03 : how we're gonna handle this square case
15:05 : with the generator I'm actually gonna
15:07 : post this one as a challenge to you the
15:11 : viewer if you like you can stop the
15:14 : video or pause the video and come up
15:17 : with a solution for what what are we
15:20 : gonna do to come up with a solution for
15:23 : this square function which is not a
15:26 : direct function available in JavaScript
15:29 : I'll give you a couple of seconds to
15:32 : decide to do that or not okay if you did
15:36 : it congratulations you are getting the
15:39 : hang of this or you were just a master
15:43 : at building code generators or if you
15:47 : just want to enjoy the show well there's
15:51 : actually multiple ways to do it the way
15:54 : that like it shows is to just use an if
15:56 : statement in that case so he said if the
16:02 : function happens to be a square if the
16:08 : function name happens to be square he's
16:10 : actually gonna use a different way of
16:13 : generating the output and otherwise
16:17 : he'll use the way that he has programmed
16:20 : so far but if it is a square function
16:23 : it's gonna first because the square
16:27 : function only has one argument so the
16:31 : argument list we expect it only to have
16:33 : one argument so will will generally
16:37 : expression convert that argument to
16:39 : JavaScript and then we're gonna just
16:42 : render the result of the computation as
16:46 : argument x argument so that works let's
16:51 : see that in action
16:54 : I'll go back to the replay terminal and
16:57 : then I generate this code again and we
17:01 : have two times two but we probably want
17:03 : to put parentheses around this
17:05 : expression so do that you know have
17:09 : parentheses so we got square working now
17:13 : okay
17:14 : another possible way to support this is
17:17 : to actually make a function that returns
17:21 : the argument times itself and then at
17:26 : that acts of this custom function in the
17:29 : function name map so that's another
17:31 : possible way to go about it and if you
17:36 : chose that you are also correct so
17:39 : that's where I want to stop this is an
17:41 : example of a code generator and with
17:45 : this we're actually like an end-to-end
17:49 : programming language even though it's a
17:51 : very very small programming language is
17:54 : only able to do some simple math
17:56 : arithmetic but it gives you the
17:59 : end-to-end architecture of how the
18:03 : programming language is implemented and
18:06 : it this serves as an example of that if
18:12 : you like to go further check out the fun
18:15 : programming language which I have have
18:20 : on github and I have done a video on
18:24 : this to give you a more proper
18:28 : introduction to it although there was a
18:30 : sort of a little fumble a little foul-up
18:33 : in the video as you will see if you
18:36 : watch that video okay that is it for now
18:40 : and I hope to see you later I