Make Your Own Language 6: Parsing Lambda Functions

This is the sixth 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 write code to parse lambda functions: the most powerful feature of this language.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello there it's toby welcome back to
00:02 : the series where
00:03 : we make a programming language uh we're
00:05 : making
00:06 : a programming language called smalling
00:08 : it's a very small
00:09 : language to get your hands dirty and
00:13 : your feet wet
00:14 : making programming languages last time
00:17 : we
00:17 : added some runtime functions to have a
00:20 : baseline of functions
00:22 : that users of this programming language
00:25 : can actually use so we were able to
00:28 : allow
00:29 : the user to write very simple programs
00:32 : such as this one this one
00:35 : and this one can do some basic math and
00:37 : basic printing of strings
00:40 : we should probably have added some
00:42 : string concatenation function
00:44 : but there's always time for that this
00:46 : time though we're tackling something
00:48 : big we're gonna implement lambda
00:52 : functions
00:52 : which are functions that look like this
00:56 : in in javascript they call them arrow
00:58 : functions
00:59 : this is the primary mechanism the only
01:01 : mechanism
01:02 : with which the users of the language can
01:04 : define their own functions you would
01:06 : define an arrow function and then just
01:08 : assign it to a variable right
01:10 : and that's a big deal and that's where
01:12 : most of the power of this language
01:14 : is going to come from uh in this episode
01:17 : we're going to build the parser part of
01:19 : the lambda function so let's get started
01:21 : we have an example of lambda functions
01:24 : in their various forms you can have a
01:26 : lambda function here
01:27 : with no parameters it has a just a value
01:31 : on the right hand side
01:33 : of the fat arrow there's this implicit
01:35 : return
01:36 : as is the case with javascript if you
01:39 : need multiple lines
01:41 : within the right hand side you can use a
01:43 : curly bracket
01:44 : to surround the separate statements
01:47 : because this
01:48 : programming language is functional in
01:51 : nature
01:52 : i decided to have implicit returns for
01:55 : the block
01:55 : style as well which means whatever the
01:59 : last statement is within the block the
02:02 : function will return the return value of
02:05 : that statement
02:06 : which deviates from javascript but i
02:08 : think it makes
02:09 : some of the things quite a bit easier in
02:11 : this language
02:12 : it also means that an if statement is
02:15 : actually a function
02:16 : and it's a function that takes a
02:18 : conditional
02:19 : in two functions and it'll call this
02:22 : function if
02:23 : the conditional is true and call the
02:25 : other function if it's false
02:27 : also an if statement because it is
02:29 : function it will return
02:31 : a corresponding value either to the
02:33 : return value of the first block or the
02:35 : return value of the second block
02:38 : it always returns some value in this
02:40 : language which also deviates from
02:42 : javascript
02:43 : okay anyway let's write the parser that
02:45 : can
02:46 : recognize this syntax we're going to say
02:50 : an expression go ahead and add it in
02:52 : there
02:53 : can also be a lambda so what is a lambda
02:56 : well a lambda
02:58 : is going to start off with a parameter
03:01 : list
03:02 : it's going to start off actually with a
03:04 : left print some optional white space
03:07 : and then a parameter list i'm going to
03:09 : stick with my
03:10 : shorthand way of naming things i called
03:14 : it
03:14 : arcless and i'm going to call it
03:16 : parentless in this case
03:18 : it's important that we don't just simply
03:20 : use
03:21 : arc list because whereas with an
03:24 : argument list you can actually put
03:25 : arbitrary
03:26 : expressions like function calls in the
03:28 : argument list
03:29 : in the parameter list you can only put
03:31 : identifiers
03:32 : so there's a param list and some option
03:35 : in white space
03:36 : and then the fat arrow and then some
03:38 : more
03:39 : optional white space and then we have a
03:41 : choice here we can either go for this
03:44 : one singular uh expression or go for
03:47 : this
03:48 : function block i'm actually gonna
03:50 : extract a second
03:52 : symbol to handle that so i'm gonna call
03:55 : that guy a
03:56 : land body i'll handle it
03:59 : separately so i don't have to deal with
04:00 : so much stuff at once
04:02 : now i'm going to have to define what a
04:04 : paramulus and a lambda body is but
04:06 : let me finish this off and write a
04:09 : converter for this guy
04:11 : so i'm going to say i want to represent
04:13 : the ast for a lambda
04:16 : to be something that has a type of
04:18 : lambda
04:20 : and then it's going to have a parameters
04:23 : array which is going to come from our
04:26 : param
04:27 : list and that's going to come from index
04:29 : 0
04:30 : 1 and 2. so data index 2
04:33 : and then the lambda body what index
04:36 : is that one let's count so 0
04:40 : 1 two three
04:43 : four five six seven
04:47 : eight body is gonna come from data index
04:51 : eight
04:51 : so i think we have this rule now uh next
04:54 : we will need to define what a param list
04:57 : and a lambda body is as well um
05:01 : uh one thing about the the the
05:04 : param list is going to look very similar
05:07 : to
05:07 : the way the arg list is defined so i'll
05:10 : do it in a similar style there is a
05:13 : shorter way
05:14 : of doing it which i am going to show
05:16 : that this time
05:17 : i'll do this left recursive way first
05:20 : i'm actually gonna copy this and then
05:23 : just
05:24 : tweak it to save some time so a
05:26 : parameter
05:27 : is not going to be an expression for
05:29 : each frame but instead
05:31 : be an identifier for each param
05:35 : and then the left recursion says we
05:38 : should start with
05:39 : myself on the left and then the right
05:42 : hand side should be this side
05:44 : so if we did this then we have a working
05:47 : param list however i have done this
05:49 : pattern
05:50 : this left recursive pattern three times
05:54 : once for statements another time
05:57 : for our arg list here and
06:00 : yet another time for this new prime list
06:02 : and this is getting a little tedious
06:05 : if you're wondering whether there's a
06:07 : little more convenient way to write this
06:09 : and the answer is yes you can if we if
06:12 : we thought of this
06:13 : identifier as resolving to param list
06:17 : we can think of it as well this part
06:19 : here
06:20 : this mandatory white space followed by
06:22 : another identifier
06:23 : that's the part that can keep repeating
06:26 : and so we can use a repeat operator
06:28 : to do that so we surround these two
06:31 : symbols
06:31 : with parentheses and then we use a colon
06:34 : which activates
06:35 : the repeat operators and we're going to
06:37 : use the star
06:39 : repeat operator here which means zero or
06:42 : more
06:43 : occurrences of that guy so if we did
06:45 : this we actually don't need the first
06:47 : part anymore
06:48 : but we will need to change the converter
06:51 : here
06:51 : because the converter wants to return an
06:53 : array but the first thing is no longer
06:55 : going to be an array
06:56 : so data index 0 is going to be the first
07:00 : identifier and then we have to actually
07:02 : ask what is going to represent this guy
07:05 : well an array
07:06 : because this is a repeating operator so
07:08 : a repeating operator will always give
07:10 : you an array of stuff
07:12 : and it'll give you an array of arrays
07:14 : for example if you have
07:16 : identifier a b c
07:19 : a would go in here and then and then
07:22 : this
07:22 : white space followed by the b is going
07:25 : to be wrapped in the first
07:26 : array and then the white space followed
07:29 : by c
07:30 : is going to be wrapped in the second
07:32 : array however both of these arrays are
07:34 : going to be
07:34 : wrapped in an outer array because this
07:38 : guy has repeated two times this guy
07:41 : repeated two times one time
07:43 : two times and this repeater operator
07:47 : its job is to repeat this guy it
07:49 : repeated it two times
07:51 : and it needs to return you the value
07:53 : it's wrapping it
07:54 : in another array so we end up getting
07:56 : this nested arrays
07:58 : like this and we have to pick that back
08:00 : out okay if you
08:01 : choose to use this pattern it's very
08:03 : important that you understand this
08:05 : nested array situation um so this
08:08 : whole thing is going to be at index 1
08:11 : now
08:12 : and index 1 is actually going to be an
08:15 : array
08:16 : i'll call this repeated uh
08:21 : pieces i don't know and each repeated
08:24 : piece
08:25 : is gonna be an array of two elements
08:27 : i'll use map to go over this
08:29 : to grab second thing within the nested
08:32 : array so i'll call this
08:34 : rest params the rest of the params
08:37 : aside from this one gonna be the result
08:39 : of mapping through this guy
08:45 : and indexing into the index one to get
08:49 : the second one
08:50 : out of the array that has these two
08:52 : things so if we do this
08:54 : and then spread it onto this outer array
08:57 : then that should give us what we need i
09:00 : will need to test this
09:01 : to verify that i did this correctly but
09:03 : before we do that let's
09:05 : make this lambda body okay so what is
09:08 : the lambda body
09:09 : well in the simplest case without the
09:11 : braces
09:12 : a lambda body is simply an expression so
09:14 : we'll do that
09:15 : and we'll use the id converter but in
09:17 : the more complex case we actually have
09:20 : a left curly brace i'll close the right
09:23 : curly brace as well but in between the
09:25 : two curly braces we're actually
09:27 : gonna have statements a number of
09:29 : statements separated by new lines
09:31 : uh we already have a thing that does
09:32 : that so i'm just gonna try to reuse that
09:35 : guy
09:36 : so i hope this works although there's
09:38 : this sort of
09:39 : beginning white space here that we have
09:42 : not accounted for
09:43 : we'll we will need to account for that
09:45 : um
09:46 : but there's also this new line i'm gonna
09:48 : say okay you can have some
09:50 : optional white space a new line and then
09:53 : the statement and then another new line
09:57 : and some optional white space at the end
10:00 : and that's
10:00 : your lambda body actually a lambda body
10:04 : should be an
10:04 : array of statements uh i think i should
10:07 : make it consistent between this one and
10:10 : this one
10:11 : so for that reason i'm going to wrap
10:13 : this
10:14 : one symbol inside of an array okay
10:18 : so lambda body will give you an array
10:20 : which
10:21 : yeah goes into this the body of the
10:24 : lambda
10:25 : and the body of the lambda should be an
10:27 : array so now let's write the converter
10:29 : for the black version of this the thing
10:33 : i want is this
10:34 : statement really so that's going to be
10:36 : it's index
10:37 : 0 1 2
10:40 : 3. okay i'm going to try this i
10:43 : i think there will be problems but we'll
10:45 : fix them if they
10:46 : if they come to be
10:50 : okay there's actually a syntax error in
10:53 : my
10:53 : nearly grammar so let's see
10:56 : line 40.
11:01 : did it mean a different place oh it
11:04 : probably
11:04 : meant line 80. the error reporting of
11:08 : nearly js
11:09 : needs some work uh perhaps i should fix
11:11 : that
11:12 : i'm one of the developers of the project
11:15 : so
11:16 : okay i'm i may want to look into that
11:19 : okay so this guy should be an arrow
11:22 : function
11:22 : instead of a bar because a bar can only
11:24 : come
11:26 : after the arrow function has already
11:28 : been started
11:29 : okay let me try generating the parser
11:31 : again
11:32 : now let me try parsing this
11:36 : example uh
11:39 : oh i think i have an error in my
11:41 : javascript
11:42 : it's showing up on smalljs line 61.
11:46 : it is really corresponds to one of the
11:48 : lines of javascript that i wrote but uh
11:51 : because because this grammar file
11:53 : generates a javascript file the error
11:55 : shows up
11:56 : in this javascript file so i'm going to
11:58 : try to
11:59 : figure out where that is it's line 61.
12:03 : oh i forgot to have a return statement
12:06 : here
12:07 : this needs to be in a return statement
12:09 : and
12:11 : because this is the function body and
12:14 : then this
12:14 : is the actual object literal so
12:18 : i have to regenerate the parser and try
12:20 : that one more time
12:22 : okay we haven't allowed for mt parameter
12:25 : list
12:25 : similarly to the argument list and for
12:28 : the argument list
12:29 : our solution was to use this optional
12:32 : specifier and let's just do that again
12:34 : so we'll use an optional specifier here
12:36 : to say that this
12:38 : param list followed by yet another
12:40 : option on white space
12:41 : that's actually optional and now that we
12:43 : have changed this
12:44 : this index is going to shift because we
12:47 : removed
12:48 : one symbol from this list this can end
12:51 : up being
12:52 : seven and then the way of getting this
12:54 : parameters
12:55 : is going to be different now 0 1 2
12:58 : is still index 2 that we want to look at
13:00 : but
13:01 : the contents of index 2 might be
13:03 : non-existent
13:04 : because this is option let's do a
13:06 : turnaround to see if it exists
13:08 : i'm going to go inside this nested array
13:11 : because
13:11 : it puts these two things inside of a
13:13 : nested array
13:14 : so we're good gonna get the zeroth one
13:17 : from that nested array
13:19 : but if it does not exist we're just
13:21 : going to use an empty array
13:22 : as the parameters so let's try that
13:25 : regenerate the parser
13:27 : and run the parser okay i think we got
13:30 : through this first line now it's
13:32 : complaining about
13:33 : this second line unexpected identifier
13:37 : token a instead i was expecting to see
13:39 : one of the following
13:41 : either a white space a closing plan
13:44 : or an identifier token so this doesn't
13:48 : really make sense because
13:49 : it it says i'm not expecting an
13:52 : identifier but
13:54 : yet later on it says i'm expecting an
13:56 : identifier token so i think this
13:58 : could potentially be a bug in nearly js
14:08 : i guess one thing that i could try is
14:11 : going back to how i did it
14:14 : with the arc list and see if that solves
14:17 : the problem
14:18 : let me save this version though so i can
14:21 : have it for later if i want it i'm going
14:25 : to change this guide to param list
14:27 : change the experts to identifiers
14:29 : regenerate the parser
14:32 : and run that again this time it doesn't
14:35 : like
14:36 : the white space token on line four so i
14:39 : think it actually got
14:41 : through that problem so there's
14:43 : something about this rule
14:45 : that doesn't work which this rule
14:48 : solves i would like to dig into that
14:50 : more
14:51 : like once i get into the get to the
14:53 : bottom of what why that
14:54 : is hey it's
14:58 : toby from a little bit later after
15:00 : having diagnosed the problem
15:01 : with this formulation of the paramulus
15:05 : i i had to do some heavy duty debugging
15:08 : into the nearly js library itself
15:11 : basically
15:12 : what i found was that so with this
15:15 : formulation of the param list
15:17 : [Music]
15:18 : we had this error which i said was
15:20 : extremely weird and seems wrong
15:22 : because it says i'm not expecting a
15:25 : identifier
15:26 : token but then later on it said it is
15:28 : expecting
15:29 : the identifier token um it took me some
15:32 : digging to figure out that i simply
15:34 : misspelled identifier
15:35 : in this instance and there's a missing
15:38 : eye here
15:39 : so that's that one so once i fix that
15:42 : then
15:42 : this formulation of paramlist does work
15:45 : and we're able to write it like this
15:48 : uh it's unfortunate that the um
15:51 : the error message was not helpful enough
15:53 : for me to figure out the problem
15:54 : it's also fortunate that it was not a
15:56 : bug in
15:58 : nearly js i suppose
16:02 : now let's solve the next problem which
16:05 : is this white space here the grammar
16:08 : currently doesn't allow for white space
16:11 : in the beginning or the end of the
16:13 : statement if we remove the white space i
16:15 : think this will parse
16:16 : yes it does but i do want to allow for
16:20 : that white space
16:21 : indentation is pretty nice this does
16:23 : work but let's allow for that white
16:25 : space
16:26 : and a way we could do that is allow for
16:29 : white space in here and here
16:33 : like that here
16:38 : okay so but now if i do this the index
16:41 : is going to be off
16:42 : um and if you retest your
16:46 : if you forget about this you're going to
16:47 : get an error later
16:49 : so i'm gonna add one to the index to
16:52 : grab that guy and
16:53 : here the index is gonna be off for this
16:56 : guy so this
16:57 : index for this is zero one two three now
17:01 : so let me try this regenerate the parser
17:05 : and then parse it and it actually works
17:08 : now
17:10 : it's able to parse this file with the
17:12 : lambda expressions in it
17:14 : let me look at the ast to verify that it
17:17 : is
17:18 : correct so okay so the first statement
17:21 : is a var assign uh we're assigned to f
17:24 : with the value of a lambda function the
17:26 : lambda function has no parameters and it
17:28 : has a body
17:29 : which just has the one expression in it
17:33 : and which is just a number so that makes
17:35 : sense
17:36 : uh the second one is a another variable
17:39 : assignment we're assigning to g
17:41 : with the value of a lambda function with
17:44 : parameters a
17:45 : and b and then a body which has a
17:48 : function call to the function at and
17:52 : which has nested function calls and so
17:55 : so on and so forth
17:56 : let's look at the next one h it's a
18:00 : variable assignment
18:01 : to the identifier h the value is a
18:03 : lambda function
18:04 : with x and y as the parameters and then
18:08 : its body
18:09 : has the body is an array
18:12 : three separate statements in the array
18:15 : um
18:16 : the first one is a function called to
18:18 : print that looks right
18:19 : i think so is the second one
18:23 : and then the third one is actually a
18:25 : function called to g so all that
18:27 : checks out and so i'm confident that
18:30 : this
18:30 : is working at the moment so i'm going to
18:33 : end this episode here
18:35 : see you next time