Live Code: Making a Programming Language from Scratch

In part 4 of this series, I add arrays to the language, encountered a scenario where we have an ambiguous grammar and found a fix to it, and implemented parameters for code blocks.

Transcript

The following transcript was automatically generated by an algorithm.

00:20 : we're live I think okay we're life this
00:28 : is Toby welcome to the show where we
00:32 : make a programming language on stream
00:35 : this time I plan I don't know about
00:39 : yours but this time my plan is to add a
00:43 : race to the language implement erase
00:49 : this is my little window where I I'm
00:54 : gonna do sub-goal labeling so I'm gonna
00:59 : sort of highlight the current task that
01:03 : I'm on at any given moment
01:06 : hopefully I remember to update my
01:11 : progress here so yeah let's get into it
01:14 : I'm gonna implement erase so that
01:18 : involves first adding the parsing for
01:23 : array literals in the language and then
01:26 : after I have that and have the ast
01:29 : update parser plus generate ast for
01:36 : array literals so after I have that then
01:43 : I'll need to update the code generator
01:46 : in order to translate my array the
01:52 : arrays of the X programming language to
01:55 : the arrays of JavaScript so that the
02:00 : actual generated JavaScript program
02:03 : works as intended
02:06 : after that I think in order for the
02:10 : arrays to be useful in the language then
02:13 : I'm I'm gonna probably add in map filter
02:17 : and reduce built-in functions another
02:20 : idea might be implement
02:23 : for loops but I'm kind of feeling like
02:26 : so far the language has taken a very
02:30 : functional turn it was not necessarily
02:33 : because
02:34 : of philosophical reasons but it's more
02:38 : just because of practical reasons
02:40 : because it's more it's easier to get
02:43 : somewhere where you can do interesting
02:46 : things with the language if you don't
02:48 : have to implement a lot of operators if
02:53 : you just leverage functions sort of use
02:56 : the functions as operators so to speak
02:59 : so I think I'll continue that trend at
03:03 : least for a bit we'll see what happens
03:06 : if we're lucky we might even do
03:09 : dictionaries I don't know okay
03:12 : so let's get into it okay I'm not
03:37 : totally sure about this I'm gonna do it
03:41 : like this okay all right
03:46 : oh yeah if you by the way if you're new
03:50 : to this project you can find the code
03:56 : that's written on this stream on github
04:00 : here github.com slash airport why h /x
04:04 : lang yeah let's get into it so I'm gonna
04:12 : need an array syntax I made a full
04:14 : example while ago now all of this has
04:20 : not been implemented but this is a
04:24 : sketch of some of the ideas about what
04:27 : might go into this programming language
04:28 : and I was thinking arrays are gonna look
04:34 : like this which might be unconventional
04:39 : well actually see and see far do it
04:45 : kind of like this with the curly bracket
04:47 : at the beginning of this series I said I
04:50 : was gonna stay away from curly brackets
04:52 : but last episode I decided to use them
04:56 : for arrays and dictionaries to resolve
05:02 : this conflict I was having between if
05:04 : because I want blocks code blocks to
05:07 : look like this and I'm also gonna make
05:10 : array literals use the square brackets
05:13 : then from the parser perspective
05:16 : perspective there's a very large
05:18 : ambiguity so yeah I'm gonna go with this
05:22 : so okay start and at the moment I'm
05:26 : gonna select the update parser and
05:31 : generate AST for array literals that's
05:33 : what I'm doing now so I'm gonna color
05:35 : that like yeah that's what I'm doing so
05:53 : the grammar of this project is where is
06:00 : the grammar so I'm gonna basically add a
06:03 : ray literal oh let me check the lexer
06:07 : first because first the string goes to
06:12 : the lexer and at the lecture at the
06:14 : moment lecture doesn't know about curly
06:17 : brackets so let's change that I said
06:21 : left bracket I called this guy a bracket
06:29 : may be called the curly one a brace so
06:33 : I'll call this left brace it doesn't
06:36 : actually matter what I call it because I
06:38 : don't actually reference the name this
06:42 : name in the grammar
06:44 : I used the string literal as you will
06:50 : see very soon okay so I have left brain
06:55 : and right brain
06:56 : now the tokenizer will actually be able
06:58 : to
06:59 : next sums of curly braces in the
07:04 : language now I'm gonna add array
07:08 : literals as a as a thing as a symbol in
07:14 : this language where should I put that I
07:18 : have probably at the bottom near near
07:23 : the bottom where my literals are so we
07:28 : have number literals and string literals
07:30 : which were caused by the lexer but the
07:33 : array literal will be parsed by the
07:39 : parser okay so our very little role
07:45 : should look like this
07:47 : they're first going to be an open brace
07:51 : left brace and then we want some
07:57 : mandatory whitespace I believe oh no no
08:03 : some optional ways so I'm looking at
08:05 : parsing this guy right okay I should
08:09 : document this maybe each of these
08:17 : symbols should be documented with like
08:23 : an example well you can't give an
08:29 : example of whitespace
08:31 : yeah I just yeah I'm not gonna change
08:36 : the other ones I'm just gonna do this
08:38 : one okay so the ray literal looks kind
08:40 : of like this there's some optional byte
08:43 : space which is denoted by one underscore
08:47 : mandatory UI spaces you know the guy 200
08:51 : scores I'm considering three underscores
08:57 : to mean mandatory or I don't know like I
09:02 : need the concept of a white space that
09:04 : can contain a can contain a new line in
09:08 : it maybe that's three underscores and
09:11 : then
09:13 : maybe whitespace that is mandatory and
09:18 : has a new line in it can be four
09:24 : underscores I'm not sure let me think
09:30 : about it okay so let's see array literal
09:36 : there's a X so after this optional Y
09:41 : space that's here that I'm gonna have an
09:45 : expression and I'm actually gonna need a
09:54 : delimited list here of things which I
09:58 : believe I've done that before this is
10:00 : kind of what parameter list is the
10:06 : function definition has a parameter list
10:08 : a function call also has a parameter
10:10 : list oh I have a feeling there's a
10:14 : problem here because a parameter list
10:20 : yeah this parameter list for the
10:27 : function call should be distinct from
10:30 : the parameter list of a function
10:31 : definition because a parameter list
10:33 : within the function definition these can
10:36 : only be names whereas this one can be
10:39 : any expression so I'm gonna need to fix
10:44 : that at some point but I'm gonna try to
10:46 : not do it right now because I don't
10:50 : wanna sidetrack myself so let's do this
10:55 : I would like to rename parameter list to
10:59 : argument list and then later I'm gonna
11:03 : recreate parameter list but only use
11:06 : parameter list for the function
11:07 : definition while using argument list for
11:11 : the function call so that's what I'm
11:12 : gonna do now I'm gonna rename all usages
11:16 : of Trender list to argument list replace
11:21 : all I hope that still work
11:25 : I'm gonna regenerate okay so I have
11:47 : argument list now I'm just gonna say an
11:51 : array literal is actually I shouldn't
11:56 : even call this argument list maybe I
11:58 : should call this expressionless okay
12:00 : change my mind calling this expression
12:03 : list because from the prospective of an
12:07 : array literal these are not arguments
12:09 : these are expressions may be depends on
12:13 : how you want to use your nomenclature
12:19 : define your nomenclature I guess but I'm
12:21 : gonna call this an expression list so
12:26 : yeah so within an array literal you can
12:30 : have this in an expression list yeah I
12:34 : think that works then after that we're
12:40 : going to sort of package up the these
12:45 : mattress into I'm going to the thing I
12:56 : want is this expression whatever the
13:22 : expressionless gives you and now we have
13:27 : the array literal symbol and I'm gonna
13:30 : say an array literal is also an
13:33 : expression so an expression can be any
13:37 : of these things
13:39 : an identifier or literal a function
13:41 : called a code block in an array literal
13:44 : think that probably works now let's try
13:48 : this I'm gonna regenerate the parser and
13:54 : then let's make an example program that
13:58 : has an array example array the parse
14:33 : tree generated multiple results that's
14:37 : actually very potentially very
14:40 : instructive because um because recently
14:43 : I got a youtube comment let me see I got
14:51 : you to comment from someone asked asking
14:55 : like she is she's implementing a parser
15:01 : using nearly Jas and she got a ambiguous
15:05 : grammar so and she asked me how to how
15:10 : to solve that problem and since I just
15:13 : got this exact same problem now this
15:17 : could be instructive for her as well as
15:22 : other people that run into this issue
15:23 : okay so I'm gonna look at there's a
15:28 : couple of ways to look at it one is to
15:30 : the first thing probably the easiest
15:32 : thing is to look at both of the parse
15:35 : trees and see if you can get a clue
15:39 : there see if the parse trees are
15:41 : different and this printout doesn't show
15:44 : you all the details
15:46 : so because console dot log when you when
15:50 : you
15:51 : cancel that log - law deeply nested
15:54 : javascript object it will only work for
15:59 : note - yes you only show you certain
16:03 : level of detail but you can change that
16:05 : by using the you - that there's a in in
16:13 : the subtract method in this you to
16:17 : package that comes out of the box you
16:20 : don't have to you don't have to npm
16:22 : install this guys this is part of the
16:26 : standard library in node and you can
16:31 : when you are printing out an object you
16:34 : can actually say u tilde inspect and you
16:38 : can give it a certain so that you can
16:46 : see more detail okay I guess we can try
16:54 : to maybe look at whether these two
17:00 : things are different in some way so in
17:05 : this case I have an assignment whose the
17:09 : value is in the array literal which
17:14 : looks correct to me that's what I was
17:17 : intending it's an array literal that
17:18 : contains these items there's three
17:21 : number and two strings okay and I
17:29 : [Music]
17:31 : there's also a function call oh yeah oh
17:34 : yeah there's a function call with the
17:39 : according the print function with the
17:44 : identifier of ARR yep okay that's the
17:48 : first version of the parse the second
17:51 : version of the parse is this it actually
17:58 : looks quite the same to me
18:03 : so I'm not really getting a hint here
18:08 : about what the problem is okay just the
18:12 : first technique didn't didn't really
18:14 : work out for us unfortunately but well
18:22 : there's another technique well there's
18:24 : more techniques one is just try to
18:26 : figure it out by looking at it and I
18:31 : will do that but that's not as good a
18:33 : better technique is actually use the
18:37 : tools to actually help you visualize
18:38 : what's going on I'm actually gonna do
18:44 : that now so there's it comes with nearly
18:48 : there's a script called nearly test
18:52 : although I don't use this probably as
18:56 : often as I should so I'm gonna do nearly
19:01 : dark to look at how to use merely test
19:12 : tooling I believe it's under yeah nearly
19:16 : test there's also nearly on par but I
19:20 : want to use nearly help so okay so I'm
19:36 : gonna I'm supposed to put in some input
19:39 : I could type input into it as well I
19:43 : think I need to provide it with the
19:54 : grammar dot vs file that was generated
20:12 : Oh windows it's a different but my
20:25 : window it might be different the way you
20:27 : type my file in but I'm just gonna try
20:31 : [Music]
20:33 : or I could let me let me do one more
20:38 : thanks I'm gonna read it I'm gonna
20:40 : remove the second line because chances
20:42 : already ambiguity comes from the first
20:44 : line so I'm gonna see whether whether I
20:52 : still get an ambiguity yep
20:59 : we still have multiple results okay so
21:02 : now that it's on one line I'm not really
21:04 : gonna do it from the command line try to
21:07 : put in this hope come in in the command
21:11 : line because I have double quotes but I
21:22 : will try I may need to escape these
21:26 : double quotes maybe and then but then I
21:36 : still need to give it the grammar file
21:38 : that is and okay it's given me yeah it's
21:44 : giving me these purse results to parse
21:47 : results and I can actually see the parse
21:52 : tables there's actually only one parse
21:56 : table that yielded both of the results
22:00 : and and you can actually with some
22:08 : understanding of the nearly algorithm
22:11 : you can actually make sense of what's
22:13 : going on here I'm gonna
22:51 : whoopsies
22:53 : what all right okay so we're gonna try
23:07 : to make sense of this huge parsing chart
23:15 : let's see if we can so there are two
23:33 : there first of all this I just do a
23:39 : brief explanation of how to read the
23:42 : entries in this chart so by the way
23:46 : chart 17 that is the position of input I
23:57 : actually don't know what the current
24:01 : well the fact that I can kind of guess
24:05 : that we're at the end of the file
24:07 : because with which his position 17 is
24:15 : probably here yeah after so yeah I can
24:19 : count so 1 2 3 4 5 6 7 8 9 10 11 12 13
24:27 : 14 15 16 17
24:30 : oh no but it doesn't work that way it's
24:32 : the position not based on this character
24:35 : they're based on tokens okay so
24:38 : is actually one and then the whitespace
24:40 : count is whatever the lexer gave you so
24:44 : the lexer is going to separate it into
24:45 : that is an identifier that's a white
24:48 : space that's an equal sign that's a
24:50 : white space that's a left braces and so
24:53 : forth so it's actually one two three
24:59 : four five six seven eight nine and
25:07 : eleven twelve thirteen so the whole
25:13 : string literal is one token and then
25:16 : fourteen for the white space 15 16 17
25:20 : and then it does actually add up to
25:23 : position 17 so basically ah
25:25 : after having parsed 17 tokens actually
25:33 : no it's 16 so position 72 we're off by
25:37 : one but at this point
25:40 : beef Oh at the point of at the point of
25:45 : receiving the Seventeen's token which is
25:48 : that one we were previously at this
25:54 : position where we're parsing an array
25:58 : literal and it's like it this dot is the
26:05 : cursor so yeah this guy is the cursor so
26:12 : this is the current position the current
26:18 : position of the parse so because we have
26:22 : successfully sort of matched these
26:26 : things along the way of reading in the
26:29 : tokens and the next thing we're looking
26:33 : for is just that oh wait no no no sorry
26:38 : I read it completely wrong so I should
26:41 : be ignoring this open brace and close
26:44 : brace that's just part of the output of
26:47 : these rules so what I should
26:51 : actually focus on only is the rule
26:55 : that's inside which actually said that
26:59 : we have successfully parsed the entire
27:02 : array literal because the cursor is at
27:04 : after this curly brace literal so yeah
27:10 : we're done there's two cases though
27:13 : where we got done and I suspect that's
27:18 : why we have two separate parses of the
27:21 : tree and then because the array literal
27:25 : was done that also allows the expression
27:28 : to be done parsing and then the
27:32 : expression let's see this was from Step
27:37 : four so what the algorithm does is goes
27:40 : back to the table in step four eight
27:49 : seven six five four this is step four
27:54 : it's basically saying hey we were trying
27:57 : to parse this this expression to match
28:07 : an array literal and and we actually
28:09 : finished it
28:10 : we ended up finishing it but it actually
28:12 : started here and because of that we
28:17 : satisfy an expression now yay but where
28:21 : who asked for an expression in the first
28:24 : place we can look up words in this table
28:30 : for chart for to find who was the
28:34 : instigator of this match on express and
28:39 : we look up we can see it's actually
28:42 : assignment who instigated the search for
28:46 : an expression because it reached this
28:49 : point the cursor reached this point and
28:52 : it says I need an expression next and
28:54 : that's the thing that started all of
28:57 : these these tries to match one of these
29:01 : guys okay so so
29:04 : because this expression completed we
29:06 : that means actually we completed this
29:09 : assignment symbol which came from zero
29:14 : so now we can complete the assignment
29:20 : matching that which started from zero so
29:24 : we go to we go to chart zero that's here
29:32 : in look for the rule that has assignment
29:39 : to the left so that's this one and that
29:44 : that started from zero so we can see
29:47 : that oh now we actually completed this
29:50 : assignment and then we can see who
29:53 : instigated the matching of this
29:55 : assignment is walk back up this table
29:59 : are these entries to see who instigated
30:03 : assignment oh look it was this guy it
30:06 : was statement that did it which means
30:09 : now that we've completed the matching of
30:12 : the assignment we are also completely
30:13 : matching of a statement and then now we
30:16 : can ask who instigated the matching of
30:18 : this statement we go back up and so
30:21 : forth we find that well it was here and
30:31 : here both so a statement try to match a
30:39 : statement and here try to match a
30:43 : statement and then that will allow us to
30:47 : complete this and then if there's like
30:51 : yeah it allows us to complete this and
30:55 : then this can automatically complete
30:57 : because this whitespace is optional so
30:59 : that completes this statements
31:01 : statements plural gets completed and
31:04 : then we look at who instigated
31:06 : statements oh here so now we complete
31:09 : the program which is the starting symbol
31:12 : so we fully part a program okay
31:17 : that was kind of a long explanation but
31:19 : now let's get down to business try to
31:22 : figure out what actually happened to
31:25 : create sort of two separate parses so
31:32 : there's two separate program two
31:37 : statements here that got and when it
31:41 : completes it actually copies that rule
31:44 : back over to here so we can see that
31:47 : there's two paths for which program was
31:52 : fully parsed
31:54 : so how did that happen is what I'm
31:58 : wondering we can see that and I think it
32:08 : might have to do with but I'm not sure
32:14 : but I think maybe it has to do this way
32:20 : that these statements has two different
32:24 : paths a statement can be well not
32:32 : because there are two sets of both of
32:37 : these two sets of both of these these
32:42 : look identical
32:44 : so who instigated these both of them
32:48 : were from zero so how did that happen
33:21 : this is an early version of this where
33:25 : before before this cursor has advanced
33:28 : past this optional white space so and at
33:32 : this point it already there were two
33:34 : versions of this and again this came
33:41 : from zero both of them came from zero
33:52 : although I wonder I think intuitively I
33:56 : think it has something to do with the
33:58 : array literal so I suppose to test that
34:02 : hypothesis we can change this to not on
34:05 : the rail and then oopsies well actually
34:13 : I'm gonna change it in this string and
34:25 : this one didn't create two results when
34:28 : it's not an array literal so I still
34:30 : think it has something to do with your
34:32 : Rea literal the way I did an array
34:34 : literal maybe and I'm wondering whether
34:39 : it has to do with the whitespace
34:41 : handling because when you do optional
34:44 : things like optional white space that
34:48 : has the tendency of causing ambiguity
34:52 : because I'm going to remove the white
34:56 : space and indeed that kind of remove the
35:00 : ambiguity okay so it actually has to do
35:04 : with the white space at the beginning
35:06 : here so now I'm thinking it could be
35:10 : that the expression list already allows
35:15 : for white space maybe although I don't
35:21 : actually see that
35:26 : I'll see optional white space here
35:35 : if I didn't put up in a white space here
35:42 : then I don't think it would allow for
35:46 : optional white space to be here
35:48 : oh no I'll try it it actually works even
35:56 : without me putting optional white space
35:59 : here which actually is quite I can't
36:05 : explain that unless expression
36:26 : alais I didn't read I didn't generate a
36:29 : parser so that was not an accurate test
36:33 : so right now I think it will not parse
36:36 : that's right
36:38 : it didn't parse so I do need that in
36:44 : order to have optional whitespace
36:46 : however I need to regenerate the parser
36:52 : so now this will part however that may
36:56 : give me no this one doesn't have a
37:03 : ambiguous grammar but I guess if I add a
37:07 : white space at the end then it has big
37:10 : use grammar oh that is true oh so what
37:19 : is it about having white space at the
37:22 : end oh because this is um mm okay I
37:32 : think I understand but I would try to
37:38 : look at the the parsing chart in a
37:42 : little bit more detail to actually
37:44 : explain what's happening but I think it
37:47 : has to do with this white space because
37:51 : the way we do we the way we have this no
37:55 : means nothing by the way which can often
38:03 : cause ambiguities so nothing means just
38:08 : like you don't have to match any symbol
38:11 : and and it still matches whatever that
38:15 : is so an expression list is like oh you
38:19 : have an expression such as the number
38:23 : one numeric token and then there's some
38:27 : mandatory whitespace here I'll draw that
38:30 : out like that there's some mandatory
38:33 : white space which is that there's two
38:35 : underscores and then there's another
38:37 : expression
38:38 : well what is an expressionless
38:40 : expressionless can actually be nothing
38:43 : so if we don't receive anything more
38:47 : than that that works this is a valid
38:52 : expression list and I think that's where
38:58 : the ambiguity comes in is well okay I
39:03 : could have person so if you have a if
39:07 : you wanted to Tarzan array literal okay
39:11 : that means I first have an array I have
39:17 : her left brace and then I have a two and
39:19 : then I have a space and I have a close
39:23 : brace there's two separate ways to parse
39:26 : this first is this I perched this and
39:32 : then so this is part of the array
39:37 : literal but then this guy I want to say
39:41 : that is a this is an expression list how
39:52 : is that an expressionless well based on
39:55 : what we did before that there's an
39:57 : expressionless because it's - is an
40:00 : expression is - and then it's got a
40:09 : mandatory white space which matches this
40:15 : space so we can say and and and
40:18 : therefore this whole thing therefore
40:22 : this whole thing is an array literal
40:26 : okay
40:28 : but another way this could have been
40:31 : parsed is different let me make some
40:35 : more black background here so I can draw
40:39 : over here this could be part another way
40:42 : which is that this could be parsed as
40:45 : using utilizing this white space here
40:48 : this white space could actually match
40:51 : this white space
40:52 : it can actually say hey hey this this is
41:05 : an array literal because because this
41:13 : one matches this guy this one matches
41:17 : this guy now this white space is matched
41:20 : as this optional white space over here
41:25 : and then this guy is 2 here that fits as
41:32 : an expression list why does it fit as an
41:40 : expressionless because well an
41:42 : expression list can simply be one
41:44 : expression and that's our two okay so
41:51 : these are two different parses of the
41:53 : same string and therefore there are two
41:57 : ambiguous parses I'm gonna verify what I
42:02 : just said
42:03 : I hope from reading this chart so so the
42:10 : ambiguity came from what based on what I
42:14 : am saying that ambiguity came from the
42:16 : definition of the array literal and how
42:19 : it interacts with the expressionless it
42:23 : would have been nicer if we could sort
42:26 : of understood that simply by reading
42:31 : this table but I understand like this
42:33 : table is a little dense
42:35 : but nevertheless we I want to I want to
42:38 : get into it to try to understand what
42:41 : the parser is actually doing so so here
42:46 : we have sort of two different ways by
42:49 : which we have successfully parse array
42:53 : literal which it matches with agrees
42:59 : with what I was saying
43:01 : now this is coming from for
43:04 : but the previous step like we want to
43:07 : find the rule where the bubble was on
43:09 : this side and this should be in the last
43:11 : I mean last but the previous step so
43:17 : let's find those guys in the previous
43:19 : step and it should be e this one
43:27 : yeah and this one ah yeah that totally
43:31 : agrees with what I was saying
43:33 : see there's one version of the parsing
43:38 : of array literal where this bubble is
43:41 : before the dope no actually not yet no
43:47 : and and then there's another version of
43:49 : it where the dot has events after the
43:52 : after the this optional white space
43:57 : actually this totally doesn't verify
44:00 : what I was saying yet because this
44:02 : advancement of this that can happen
44:05 : immediately because this space is
44:08 : optional and which is why this this
44:11 : update happened it just advanced the dot
44:14 : automatically because you don't have to
44:16 : match anything to advance it if this guy
44:19 : is optional okay so I I think we
44:22 : actually need to go back further so
44:26 : let's go back to there's this one where
44:34 : the dot is has already finished matching
44:40 : the optional white space and then
44:45 : there's a different version where it is
44:50 : before this optional white space okay I
44:53 : think that's where and and both of them
44:58 : come from step 4
45:00 : so we move one back to see I think at
45:07 : this point it was yet I think at step 16
45:11 : that's getting a white space
45:21 : yeah
45:22 : 6:16 is a white space where as step 15
45:26 : was a string it would be nice if we can
45:34 : actually see what token so I can count
45:39 : so token token one is identifier right
45:47 : and then we have white space three four
45:51 : five six seven eight
45:55 : it'd be easier if let me do this
46:00 : I'd be easier if we simply have one
46:04 : thing in it and we still have to
46:07 : separate horses yeah let's go at this
46:10 : one so in this case there's and I'm
46:14 : gonna remove the non East Central West
46:18 : basis so we have even less tokens but
46:22 : still the same ambiguity okay so now
46:25 : we're gonna have token number one token
46:31 : number two token number three four five
46:36 : and six
46:38 : okay and we have six tokens and the
46:46 : sixth token is gonna be this closing
46:51 : curly the fifth one is gonna be the
46:54 : white space so we should have the same
46:56 : exact same situation here where we have
47:01 : two array literals that were completed
47:05 : yes and then we go back one and fifth
47:16 : token is the white space okay so we were
47:20 : able to match the white space in this
47:23 : mandatory white space rule and was match
47:29 : for this option
47:31 : and I guess that allowed us to advance
47:36 : past this guy so we have this array
47:41 : literal parsing that advanced the dot
47:47 : from here to here as the result of
47:50 : reading in this white space here this
47:58 : array the drill is starting a new one so
48:01 : that's not the one we care about but
48:03 : rather I think it's okay it's this one
48:07 : because this one is different
48:09 : this one the dot is still before the
48:12 : optional whitespace and I think that the
48:16 : whitespace was consumed in a different
48:19 : place
48:19 : probably namely Oh name Lee it was
48:35 : consumed by this oh yeah because because
48:42 : we resolved the the mandatory whitespace
48:46 : this the resolving this mandatory
48:50 : whitespace allowed this expression list
48:55 : parsing to advance this dot from here to
48:58 : here and which is exactly what I was
49:02 : saying before so yeah it allowed the
49:05 : advancement of this rule from here to
49:09 : here which is basically taking the
49:13 : whitespace in as a separator within the
49:17 : expression list yep I hope that made
49:23 : sense so in one case the two trailing
49:28 : whitespace and by trailing whitespace
49:30 : I'm in this one the trailing whitespace
49:33 : in one case was used here but in a
49:37 : different case was used here so what can
49:41 : we do about that
49:43 : let me think one way is just not allowed
49:47 : this null I think we're gonna say and I
49:51 : guess the using this null was used in
49:57 : order to allow empty and empty lists so
50:07 : but but the null comes with at the cause
50:10 : of like this white space could the the
50:14 : trailing whitespace could either get
50:16 : matched here versus here that causes an
50:20 : ambiguity so if we were to do it
50:22 : differently
50:24 : maybe we this allowed this null here and
50:28 : then have a separate separate rule or
50:33 : separate sup rule for a literal that
50:36 : allows for just a open bracket an
50:39 : optional white space and a closing brace
50:44 : and and and that's a separate sort of
50:48 : matching rule for the empty array case
50:54 : so let me show you what I mean here so
50:57 : I'm going to remove this guy and then
51:01 : and then this guy cannot be empty
51:06 : anymore it has to have something in it
51:08 : but we have a separate one separate rule
51:14 : for matching array literal that says
51:17 : well I'm never a literal can also just
51:19 : be that and in which case
51:40 : it's gonna return something type array
51:46 : literal items right like that so I think
51:53 : this will avoid the ambiguity let's see
51:56 : oh I need to regenerate the parser I
52:06 : have a syntax error in this code I
52:10 : believe where is it so it's it doesn't
52:13 : like this bar oh that might be the wrong
52:17 : syntax it might be the slash I still
52:23 : have a bar where's my bar oh no here's
52:27 : to the bar is something else that's
52:30 : right
52:31 : what is it on line 40 oh it's on line 40
52:48 : that was not where I was looking at wait
52:54 : a minute
53:00 : syntax error line 40 column 5 I don't
53:12 : see a bar there what are you seeing -
53:16 : mean the early mm-hmm this is kind of
53:22 : strange
53:28 : oh this is a problem maybe it's that but
53:37 : okay it was this it's very confusing
53:42 : that it gave me the wrong line number
53:45 : I'm not sure why that happened but okay
53:50 : okay but anyway that worked and now if
53:57 : we parse the same example we don't have
54:01 : an ambiguous grammar anymore so so
54:06 : that's an example okay of of how do you
54:11 : how do you debug ambiguous grammars just
54:14 : try to rewrite your grammar in a way
54:18 : that cannot be ambiguous that there's in
54:23 : such a way that there isn't a way for it
54:26 : to interpret the same strings in two
54:28 : different ways I guess for that matter I
54:33 : probably should do the same thing for
54:38 : I'm not totally I'm not 100% that this
54:44 : is the best way to do it actually um so
54:50 : it's I'm not totally sure
54:52 : maybe there's a still a better way to do
54:55 : this but I'm not sure yeah I have done
54:57 : this for other projects and this is
54:59 : currently the best way I know how I
55:01 : believe but if I can think of a better
55:04 : way I might switch to a better way and
55:08 : this problem will probably surface again
55:12 : for for function calls and function
55:15 : definitions at some point but uh but
55:19 : let's see let's see what happens because
55:21 : now it's impossible to call a function
55:24 : that takes zero arguments after the
55:28 : change that I made okay all right so
55:39 : now what are we gonna do now
55:43 : I think with this we can probably parse
55:48 : this guy
55:49 : I can probably parse this guy correctly
55:54 : and generate an AST let's see so ours
56:01 : exam ray X and it generated an AST file
56:06 : let's look at it it's here and that
56:14 : looks good to me
56:17 : and then of the next the next step is to
56:23 : generate a JavaScript file based on that
56:26 : ast file so let's do example array X KS
56:31 : T and we're gonna the generator says I
56:37 : don't know what to do with a very
56:38 : literal notes so we'll go change that
56:41 : and make it handle array literals so
56:45 : let's go to the generate script so that
56:52 : is 9 104 yeah that's right here we just
56:56 : add another else cloth and then we'll
57:08 : say well oh map its items
57:11 : I think it's called items through this
57:14 : generate function recursively call
57:18 : ourselves here assuming every item is an
57:24 : ast note that this generate function can
57:27 : also handle this works out and then
57:30 : we're gonna join them with a goals well
57:35 : actually we're converting it into
57:37 : JavaScript so join them with a comma in
57:41 : the space and so all these guys in
57:47 : JavaScript space
57:50 : and then will return a array notation in
57:58 : JavaScript which is using the square
58:01 : brackets so see if that works
58:04 : it wrote example array dr es oh there it
58:13 : is and it looks like this and that looks
58:16 : correct to me so this program example
58:26 : array turns out here right so cool
58:32 : kukuku
58:33 : that works now if we add the map to add
58:38 : some functions for for the language to
58:42 : make use of erase I was oh I did that
58:47 : really quickly but I forgot to update my
58:59 : step so I was okay I was working in the
59:04 : update code generator and I think I just
59:08 : finished let me maybe test one or two
59:12 : things like what if we are let me test
59:15 : it a little couple things more right
59:17 : what if we have nested erase is that
59:20 : support it in the language probably it
59:24 : will work just because of the recursive
59:27 : nature of everything but I'm gonna test
59:30 : it like that so I have a erase nested
59:41 : inside its array we run it would work
59:45 : yeah it works it works just like that
59:48 : okay so we have a race we can have an
59:53 : array literal in this language now we we
59:59 : added the parsing for array literals
1:00:03 : we've updated the code generator to
1:00:06 : generate array notation in JavaScript so
1:00:11 : it kind of translates that code to this
1:00:13 : basically now let's add map filter and
1:00:16 : reduce built-in functions to the
1:00:18 : language in JavaScript these are methods
1:00:23 : the language if the X language currently
1:00:26 : doesn't support method calls only
1:00:29 : supports function calls at the moment
1:00:31 : I'll probably add method calls later but
1:00:35 : it doesn't happen now so we're gonna do
1:00:38 : is do it in the Python style which is
1:00:40 : gonna look like you map an array and
1:00:46 : then you provide a block like like so
1:00:52 : which I guess in this language a block
1:00:55 : looks like this I'd I don't actually
1:00:58 : think we have a way for the block to
1:01:02 : take parameters yet so probably cuz
1:01:08 : because I I'm copying a little liberally
1:01:11 : from small talks so in small top a block
1:01:14 : actually looks like this in Ruby is kind
1:01:19 : of like this - I believe so if if you
1:01:23 : write a block like this this doubles
1:01:31 : every item in the array maybe new array
1:01:35 : gets the result of this map maybe
1:01:39 : something like this
1:01:42 : in order to do this though we'll need to
1:01:47 : support this syntax I did not realize
1:01:50 : that but yeah I actually did not realize
1:02:01 : I have more syntax that I would need to
1:02:04 : support in order before we can do this
1:02:08 : okay should I either do this or just I'm
1:02:14 : just gonna add these built-in functions
1:02:17 : with no way to access them right now
1:02:21 : yeah let me do that although that's kind
1:02:24 : of unsatisfying though so maybe we I'll
1:02:33 : add them and then maybe we'll implement
1:02:35 : this syntax as well maybe it will need
1:02:40 : to be a quick and dirty thing I'm not
1:02:44 : gonna so I'm gonna work on the built-in
1:02:46 : functions which I think that's in the
1:02:49 : generate okay a map function assuming it
1:03:11 : takes in an array you just take the
1:03:14 : function iterator and pass into the
1:03:16 : erase the map method like that so that's
1:03:50 : like that okay very cool we have these
1:03:53 : functions but again we probably have
1:03:57 : trouble using them right now but you
1:03:59 : know what the heck maybe you can do each
1:04:02 : yes do each each at least should work
1:04:15 : should be usable okay so if we did each
1:04:21 : then we can actually print oh we can't
1:04:25 : unfortunately we actually can't
1:04:30 : you can print a constant though there
1:04:42 : isn't supposed to be comma in this
1:04:44 : language yeah we print hollows six times
1:04:48 : because there are six elements in this
1:04:51 : array I make that clear six it'll print
1:05:00 : hollow ones for every element there is
1:05:03 : an D array okay so why don't we
1:05:09 : implement this parameter syntax for
1:05:12 : blocks why not
1:05:15 : so I didn't want to implement it like an
1:05:18 : arrow function because I didn't like the
1:05:23 : fact that there could potentially be
1:05:25 : optional white space here which kind of
1:05:29 : doesn't drive well with us trying to use
1:05:32 : mandatory white space to separate values
1:05:35 : so I am actually gonna bring in some
1:05:40 : inspiration from small talk small talk
1:05:43 : blocks look like this and then Ruby kind
1:05:48 : of copied this thing so let me let me
1:05:50 : look at what Ruby code blocks look like
1:05:55 : as another yet another data point so
1:06:05 : Ruby code blocks they there's two
1:06:08 : different syntaxes for ruby code but you
1:06:11 : can either be delimited with these
1:06:14 : braces and then you put put the
1:06:19 : parameters inside this little delimit
1:06:25 : bit with the bars like this with
1:06:27 : comments like that or you could write do
1:06:33 : do n again with these bars delimiting
1:06:37 : the thing so i could do it like ruby or
1:06:40 : do it like
1:06:42 : small talk small talk doesn't have this
1:06:45 : bar on the left
1:06:46 : whereas Ruby does I think I'm more used
1:06:54 : to Ruby's syntax which is which looks
1:06:58 : like that but the small talk syntax
1:07:03 : looks a little bit small talks in text
1:07:06 : that does it there's a little colon in
1:07:10 : front of it or something I don't
1:07:11 : remember if you go with the Ruby syntax
1:07:17 : so something like this so that there's a
1:07:20 : parameter list to the code block like
1:07:23 : that and that's what the code looks like
1:07:27 : and then within here we can say let's go
1:07:33 : for this why not
1:07:35 : okay so add more syntax so we're gonna
1:07:39 : change the code block
1:07:40 : so the code block can look like this or
1:07:49 : or it can have this optional I'll call
1:07:54 : this code block parameter and yeah which
1:08:14 : which come before that there can be
1:08:18 : auxin all whitespace before okay and
1:08:22 : okay and if we had this then so code
1:08:36 : block can have parameters
1:08:41 : but these indexes have changed so this
1:08:46 : guy is going to be index to zero one two
1:08:53 : but the statements are actually two
1:08:56 : three four five and then we need to
1:09:00 : define what code block parameters are so
1:09:05 : code block parameter is a bar the lexer
1:09:10 : also needs to emit a bar which it
1:09:13 : currently doesn't I just got this bar
1:09:17 : okay okay so you're gonna have a bar and
1:09:25 : then another bar and then within it we
1:09:30 : have expression lists this actually and
1:09:36 : let's just say it's not allowed that you
1:09:39 : have note nothing inside the bars if
1:09:41 : you're gonna have nothing inside the bar
1:09:43 : just don't use the bars at all that that
1:09:46 : way I don't have to do that the this
1:09:51 : approach that I use in the other place
1:09:54 : okay so and okay so so this is what
1:10:02 : block code block parameters are and here
1:10:06 : I'm gonna return I think I'm actually
1:10:15 : going to just return the array that's
1:10:18 : returned by this expression list which
1:10:20 : is at index zero one two okay let's see
1:10:27 : if this works
1:10:28 : I'm gonna let me try parsing this file
1:10:41 : here example array
1:10:51 : it did it so we have a ast file that has
1:10:58 : this function call and then I have a
1:11:05 : code block that has parameters now it is
1:11:10 : an item in this case okay
1:11:13 : code blocks can have parameters this
1:11:16 : will have repercussions though because
1:11:18 : my function definition has a code block
1:11:21 : in it and a function definition actually
1:11:25 : looks more like this so now we're saying
1:11:31 : hey you can actually do parameters like
1:11:33 : this which is kind of weird it seems
1:11:36 : like we should pick one and go with it
1:11:39 : and maybe what I do is just like say you
1:11:43 : know what define the function like that
1:11:47 : or maybe like that or maybe like that I
1:11:54 : know how so we'll figure it out a way I
1:11:57 : might change the language shortly after
1:12:02 : when I change the language or or we I
1:12:05 : don't know I don't know what the best
1:12:07 : solution here but in any case that has
1:12:12 : some negative repercussions but we've
1:12:16 : chose to do here which we'll need to
1:12:19 : clean up later I forgot to update my sub
1:12:26 : goal label sorry
1:12:29 : so I actually completed all of this I
1:12:33 : completed the app mapped over - there's
1:12:38 : an extra step
1:13:00 : sorry about the noise okay so we have
1:13:07 : code box parts now in order to generate
1:13:10 : it again we need to in order to run
1:13:14 : we'll need to update the code generator
1:13:18 : generator singular oh because currently
1:13:32 : it just ignores the parameters currently
1:13:38 : it didn't put item in here so we really
1:13:41 : need to put items in there and we can
1:13:44 : get the generator to do that if we look
1:13:49 : at the code block here and if we say eh
1:14:04 : you
1:14:14 : it's dysfunction so prams so I'm gonna
1:14:18 : get a pram in JavaScript space and say
1:14:30 : and then these Prime's are going side of
1:14:35 : dysfunction at this point I think that
1:14:38 : should work let's look at this example
1:14:43 : array dot J yes and yeah we have the
1:14:47 : item here now yes we can run the example
1:14:58 : array X now it's printing it but we can
1:15:04 : do maps as well let's do map let's do
1:15:09 : this as a map everything is on the
1:15:20 : client oh because we're not returning
1:15:23 : anything
1:15:24 : so that's oh I don't have a return state
1:15:32 : have a way to return things because
1:15:36 : there isn't a return statement in the
1:15:39 : language at the moment and that's
1:15:43 : embarrassing and I also don't have a
1:15:45 : multiplication that's right no operator
1:15:52 : but yeah I can't return because return
1:15:56 : haven't written the parser in a way that
1:16:01 : supports return
1:16:03 : I might support implicit return at that
1:16:08 : possibility so we still can't do Matt
1:16:13 : yes yet perhaps we defer that to the
1:16:17 : next episode so at least we can do
1:16:20 : so we can do something like yeah so in
1:16:29 : order to in order to get map to fully
1:16:32 : work the way it's intended to work we're
1:16:34 : gonna need we're gonna need to either
1:16:40 : implement return statement inside of a
1:16:42 : block or to implement in implicit
1:16:47 : returns which just means like whatever
1:16:49 : is your last line inside the block you
1:16:52 : implicitly return its result so one or
1:16:58 : the one or the other will properly do it
1:17:01 : next time at least we have some
1:17:05 : resemblance of arrays working at this
1:17:08 : point and that's something to be proud
1:17:10 : of and yeah we'll call it a day here and
1:17:15 : I'm going to end this dream and I'll see
1:17:17 : you next time

Live Code: Making a Programming Language from Scratch - Part 4

Transcript