Make Your Own Language 8: Code Generator for Lambda

This is the eighth episode of a series where you build your first programming language, using these videos as a guide. We’ve setup the syntax for a small programming language. You can clone this project and start getting to work. The project repository is https://github.com/airportyh/smallang. In this episode, we make the code generator for lambda functions and actually get the fibonacci series program to work!

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello this is toby coming to you from
00:03 : the evening
00:04 : and uh welcome back to the series where
00:06 : we make a programming language
00:08 : so we're making this programming
00:09 : language called smalling is a very small
00:11 : programming language and hopefully you
00:13 : can follow along
00:15 : with me uh in building this in getting
00:18 : your hands
00:19 : dirty and your feet wet in building your
00:21 : first programming language
00:23 : please feel free to make it your own
00:25 : that's what makes it fun
00:26 : and also makes it a better learning
00:29 : experience
00:30 : so last time we took a step back
00:33 : and did some maintenance work we made
00:36 : the
00:37 : multi-line white space handling better
00:41 : so now we can put blank lines
00:44 : anywhere in our source code and the
00:46 : parser is going to be okay
00:48 : we support lambda functions and we can
00:52 : sort of space out our code these pseudo
00:54 : if statements which are in reality
00:56 : implemented
00:57 : as function calls we can format them in
01:00 : this
01:00 : multi-line kind of way as i had
01:03 : envisioned it
01:04 : so now that lambda functions can be
01:07 : parsed
01:07 : we're gonna actually write the code
01:09 : generator to translate
01:11 : our lambda functions into javascript
01:13 : functions okay
01:14 : so we already have this ast
01:18 : format for lambda functions uh let's
01:21 : open up
01:22 : the generator file the generator file is
01:25 : at the moment
01:26 : it's only 51 lines small
01:29 : so if we try to generate javascript
01:32 : based on the ast file that was generated
01:36 : let's go ahead and try and see what
01:38 : happens
01:40 : uh we'll get this error saying unhandled
01:43 : ast note type
01:44 : lambda which makes sense because that's
01:47 : a new
01:48 : ast note type that we introduced and we
01:51 : have not written
01:52 : the code in the generator to handle that
01:54 : node type
01:55 : which is precisely what we're here to do
01:58 : so we're going to add this
01:59 : if statement to say basically what we're
02:01 : going to do
02:02 : if we encounter a lambda in the ast
02:06 : and that's going to look like this a
02:08 : lambda has
02:09 : a list of parameters and it has a body
02:12 : which is a list of statements
02:16 : in this language so what we want to do
02:18 : is given
02:19 : a lambda which looks something like this
02:22 : basically translate it into an anonymous
02:24 : javascript function
02:26 : so code is probably going to look
02:27 : something like function
02:29 : and then the param list and then
02:32 : we're going to have like the javascript
02:34 : body here
02:36 : call this js body you're kind of
02:39 : probably gonna
02:40 : end up returning something like this
02:42 : here and we just need to figure out what
02:44 : the parameters
02:45 : is and what the js body is primeless
02:48 : should be easy because the parameters is
02:51 : this array of parameters and we already
02:53 : know
02:54 : the only things that can be in the
02:56 : parameter list are tokens of the
02:58 : identifier type we can just write a map
03:01 : over that
03:02 : so note that parameters dot map ram
03:06 : dot value let me call this guy pram list
03:10 : i know that the result of this map is
03:12 : going to be an array
03:13 : so i'm going to join it together with a
03:16 : comma
03:17 : that should give us our parameters now
03:19 : we need the js body
03:21 : how do we get the javascript body uh
03:23 : again let's loop through this
03:25 : body the body is an array of statements
03:27 : and for each statement we can
03:29 : recursively call the function that we're
03:32 : already in
03:32 : which is generate.js for statement
03:36 : or expert so i'm gonna use mac very
03:39 : similar to this actually
03:46 : and so this guy gonna give us an array
03:49 : of
03:49 : javascript we're gonna join them
03:52 : together
03:53 : with let's say a semicolon and a new
03:56 : line and that's the js body
03:58 : that might be it that might even work so
03:59 : let me call generate one more time
04:02 : no okay let's debug this so generate.js
04:06 : line 29 has a problem let's go to that
04:09 : line
04:10 : saying we've got a node that is null the
04:14 : note is somehow
04:15 : not i'm not sure how that could have
04:17 : happened suppose what i could do
04:19 : is i mean it must have arised from
04:22 : here so maybe one of these arcs is null
04:25 : so i'm going to
04:25 : write an if statement say if r is null
04:29 : count to the log arc is known for
04:33 : this index i or node
04:36 : and print out the node see if that works
04:39 : no
04:40 : we actually didn't hit this it could be
04:42 : coming from a different place
04:46 : let me look for no values in this file
04:49 : oh
04:50 : found it in the ast file we have some
04:52 : null
04:53 : values at the bottom so this might be a
04:56 : place in the grammar we have to fix
04:58 : actually so let's go back to the grammar
05:01 : i think the problem
05:02 : is this index is off i actually have
05:06 : only three statements in this program
05:09 : yeah the very first statement
05:11 : is this fib line but that is so complex
05:14 : that is taken most of our attention here
05:18 : but the next two statements ended up
05:20 : being
05:21 : null because uh this index is off
05:24 : because this index supposed to index
05:27 : into this
05:28 : sub array which after some changes we
05:31 : made
05:31 : this only has two elements therefore
05:34 : this guy should be one
05:35 : not two let me regenerate the parser
05:39 : i need to re-parse the file and
05:42 : yeah there's our call to print and then
05:46 : there's our call to fit
05:48 : now let's code generate again
05:51 : and that works okay great let's take a
05:54 : look at that
05:55 : javascript file that was printed out
05:57 : okay i think there's a problem
05:59 : first of all which is we can't really
06:02 : use
06:02 : if as a function name because in
06:05 : javascript
06:06 : if is actually a keyword the second
06:08 : problem
06:09 : is the indentation and the third problem
06:12 : is we actually want
06:13 : these functions to implicitly return
06:16 : the last statement so let's fix one
06:20 : at a time here whenever we have a
06:22 : function called to the
06:23 : if function in javascript we're going to
06:25 : output
06:26 : dollar f like so and then later on we'll
06:29 : add a runtime function called
06:31 : dollar if to support the
06:34 : if functionality so let's first do that
06:37 : so we're going to change the
06:39 : output here to whenever you have a
06:41 : function call and the function name is
06:43 : f i'm just going to make this a
06:45 : non-const i'll say if the function name
06:48 : happens to be if we're actually going to
06:51 : change it
06:52 : to the dollar if now
06:55 : if we generate it calls to the if
06:58 : function become dollar f
06:59 : okay so that's good the second problem
07:02 : is that
07:02 : i would like some indentation let me get
07:05 : rid of this
07:06 : debug here i like some indentation
07:09 : in this body of code so i'm gonna make
07:12 : an indent function
07:14 : i've written this many times so a simple
07:17 : indentation
07:18 : a one-liner would be you split
07:22 : the string by the new line character and
07:24 : then you map over it
07:27 : and then in front of each line you put
07:30 : some extra white space
07:33 : and then after that you join it back
07:34 : again with the new line
07:36 : so i'm going to use this indent function
07:38 : on the js
07:40 : body and then should that should give us
07:42 : some indentation i believe
07:44 : yes that totally worked that's looking
07:46 : good actually
07:47 : the last problem is i would like to have
07:50 : this implicit return
07:51 : so for the last statement within a
07:55 : lambda function i would like to return
07:57 : its value
07:58 : so in javascript land we're going to
08:00 : need to slap this return statement in
08:02 : front of
08:04 : here here and here the way i'm going to
08:06 : do that is
08:07 : within this map loop here that we're
08:10 : doing
08:10 : we ask the index is this the last
08:14 : index yes or no and if it is then we
08:16 : slap the return statement in front of it
08:19 : let's try that so we'll say i'll just
08:22 : code this js code here
08:24 : and then now we're gonna ask hey is i
08:27 : equals
08:28 : to know that body length minus one
08:32 : if it is that means it's the last
08:33 : statement of this
08:35 : bunch we're gonna slap the word return
08:38 : in front of it but if it isn't we're
08:41 : just gonna return
08:42 : that js code as is see if that works
08:46 : that seemed to work and i think that's
08:48 : probably runnable
08:53 : ah there's a problem here oh
08:56 : dollar if is not defined let's define it
08:59 : let's write the dollar if
09:00 : function in the runtime dollar if is a
09:03 : function it takes a conditional
09:05 : in a consequent block and an alternate
09:08 : block
09:09 : those two blocks are functions so if
09:12 : conditional is true
09:13 : then i'm going to return the result of
09:15 : calling the consequent
09:17 : block else we're going to do the same
09:20 : but for the alternate block instead so
09:23 : let's
09:23 : try this generate the code now run the
09:26 : code
09:27 : uh eq is not defined let's define eq
09:31 : we might actually be able to get the
09:33 : fibonacci working
09:34 : if we just had eq i think that would be
09:37 : exciting
09:38 : okay eq between two things is
09:41 : just the triple equal operator in
09:44 : javascript so let's try to regenerate
09:46 : and then run
09:47 : answer is two fib of three the answer is
09:50 : two
09:50 : that's actually correct trip of four i
09:53 : need to
09:54 : run the user run.js to execute it
10:00 : answer is three it's like one one
10:04 : two three and then the next one would be
10:07 : five and then the next one
10:11 : would be eight
10:15 : yes we don't need this white space here
10:17 : evidently
10:18 : next one after that would be 13.
10:23 : yes we have the fibonacci series
10:26 : implemented in the small language
10:28 : wonderful uh i'm quite happy with this
10:32 : so i'm gonna leave you on this happy
10:34 : note
10:35 : in the next episode what we're gonna do
10:37 : is implement
10:39 : comments which will be the last probably
10:41 : major feature of the language
10:43 : and after that we probably gonna do a
10:46 : code challenge or two
10:48 : on code wars that is something i usually
10:51 : do to find
10:51 : holes in the programming language so
10:53 : that's what's coming up next
10:55 : and i hope to see you there