Fun with ASTs

This is a 1-hour lecture and demo I did for Insiten's Algorithm Friyay. I introduce ASTs (Abstraction Syntax Trees), how to get them in JavaScript, and we write code to traverse an AST. Unfortunately I failed to record the audio for the attendees, so you can only hear one side of our conversations.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : trees are actually
00:02 : everywhere um
00:05 : especially in georgia um
00:08 : and it is one of the
00:11 : fundamental structures of life
00:14 : um and uh it's actually no consequence
00:18 : it's no coincidence that it's
00:21 : it's very fundamental to computer
00:24 : science as well
00:29 : um i guess i'll just let you ponder that
00:31 : but um
00:33 : so i wanted to do some more stuff with
00:36 : trees um but in some of my
00:39 : work like i do some stuff with
00:41 : programming languages i do some stuff
00:43 : other stuff
00:45 : um
00:46 : as well
00:47 : and i've been going through the
00:48 : algorithm book a little bit previously
00:53 : you can just see
00:54 : trees of various forms
00:57 : in very different contexts in computer
01:00 : science so we're going to visit one of
01:02 : them here
01:04 : i want to play with asts which is
01:07 : abstract syntax trees
01:10 : so so the problem i would like to uh
01:15 : look at is
01:17 : given a program like this and i i
01:20 : purposefully design a very simple one
01:23 : here
01:24 : um sort of how how can we
01:29 : reason about this code like for example
01:32 : a simple thing we might want to do with
01:35 : a program like this is
01:37 : i want to find the unused variables
01:40 : right like what is an unused variable in
01:43 : this code
01:44 : anyone
01:48 : bueller
01:52 : b
01:53 : yeah b b b is not used
01:56 : uh it was defined but then it was not
01:59 : referenced later in the code um and we
02:02 : have tools that help us do that like you
02:04 : you bring in the linter
02:06 : or you're just you're just ide we'll
02:10 : just find those stuff for you and tell
02:12 : you about it
02:13 : um
02:14 : and so we're lucky in that we have all
02:17 : of these tools available to us
02:20 : we don't always have that what if we had
02:22 : to do it ourselves so that's what we're
02:24 : going to do
02:25 : we're going to write a program to find
02:27 : the unused variables in this code
02:32 : the first thing you need to do in order
02:33 : to reason about code is to parse it
02:37 : and
02:38 : and that's actually the first step
02:41 : of what a computer programming language
02:43 : does
02:44 : so if you um
02:47 : screen brush i want to draw here so
02:51 : uh
02:52 : get any given programming language they
02:54 : will usually have a
02:58 : parse step
03:00 : part or parser like your code goes in to
03:04 : your programming language
03:06 : well i don't know
03:08 : which which can either be a compiler
03:12 : or an interpreter
03:16 : so and maybe this is javascript
03:19 : it's a javascript compiler or javascript
03:22 : interpreter for javascript both of those
03:25 : styles exist
03:28 : so the javascript goes in here which is
03:31 : something that looks like this
03:34 : it goes into the compiler the first
03:36 : box inside the compiler or interpreter
03:40 : is going always going to be the parser
03:42 : the parser is going to spit out
03:45 : a bunch of abstract syntax trees
03:48 : and then
03:50 : and then that's sort of this is sort of
03:52 : the process of how the
03:54 : programming language can reason about
03:56 : the code after it's in this abstract
04:00 : syntax tree form
04:01 : it's more able to
04:04 : reason about this code basically read
04:06 : this code
04:07 : it's going to have to read through this
04:09 : code line by line
04:11 : look at what this code says
04:13 : and then do stuff with it what what is
04:15 : it gonna do with it um it might
04:20 : sorry
04:21 : um
04:22 : in some cases it might need to generate
04:24 : some code to the generator
04:29 : the generator might need to
04:31 : convert it into some machine code
04:39 : and and then
04:40 : the the machine we feed that to the cpu
04:43 : directly
04:45 : or in some cases the ast can go
04:48 : go into directly into an interpreter
04:53 : which which actually
04:55 : executes
04:56 : instruction by instruction
04:58 : but um so this is what a
05:01 : sort of a computer programming language
05:03 : normally has to do
05:05 : but
05:06 : we can sort of yank this parser out
05:10 : we're going to steal this parser
05:13 : out of this picture and say hey can i
05:16 : just have just the parser by itself
05:20 : i yanked it out of your compiler
05:23 : and can i use that as my own module for
05:26 : my own uses and that is basically what a
05:29 : linter does right
05:31 : if i if i'm able to just use the parser
05:34 : out of the javascript engine
05:36 : and get at the ast
05:41 : now i can plug a bunch of tools
05:44 : uh onto this ast and do various stuff
05:48 : with it so that's what we're gonna do
05:50 : i'm gonna show you um
05:53 : if i took this code for example
05:56 : and uh
05:58 : i'm gonna use the um
06:01 : javascript the free and open source
06:03 : javascript parser called s prima
06:06 : it is not the only and this is
06:09 : by the way this is a streamer is one of
06:11 : the first javascript parsers that is
06:14 : also written in javascript itself
06:17 : uh but but since this one existed there
06:20 : have been others like another
06:22 : popular one now is acorn
06:25 : and i have used both of these with
06:27 : success uh
06:29 : in the
06:31 : uh in the browser though the browser is
06:33 : not actually using one of these the
06:35 : browser would have like a c plus plus
06:37 : version
06:38 : that's more performant i would expect
06:41 : but in any case we're going to use this
06:42 : one
06:44 : and
06:46 : um
06:57 : okay
07:01 : yes okay
07:03 : okay uh yeah i can talk about tokenizing
07:06 : just briefly i was gonna
07:08 : skip it but uh but
07:10 : um
07:12 : tokenization is you can okay some people
07:17 : tokenizing
07:22 : some people call that lexing if you use
07:25 : or lecture tokenizer or lecture
07:28 : they meet they mean the same thing
07:31 : um
07:32 : so
07:34 : i look at it more like this okay
07:38 : this whole box is the parser
07:42 : uh
07:45 : okay okay i i i use the name parser
07:48 : twice but uh you know what i mean right
07:51 : there
07:52 : people
07:54 : people break the parser up into two
07:56 : stages the tokenizer and then the parser
07:59 : but i look at it as one larger box but
08:02 : uh the tokenizer
08:05 : can make the parsers drop a little bit
08:07 : easier but basically what the tokenizer
08:09 : does
08:10 : uh and in in today's session we're not
08:13 : gonna bother with any of these we're
08:15 : just gonna
08:16 : uh well i'm not talking about parsing
08:18 : today so
08:19 : we could
08:20 : you know safely be ignorant just for
08:23 : today but um but
08:25 : just a little bit about it what the
08:27 : tokenizer does is basically break
08:29 : because this all of this is a giant
08:31 : string that's all this is and there's
08:33 : some new lines here
08:35 : some new line here new line here etc
08:38 : what that is is a giant string
08:40 : and what the tokenizer does to make the
08:43 : parser's job easier
08:45 : is it groups the bits of strings so it
08:48 : would say hey let
08:50 : let is a token
08:52 : a is a token the equal sign i'm gonna
08:56 : call that the assignment token or
08:58 : something
08:59 : um
09:00 : it breaks each sort of meaningful
09:03 : chunk
09:04 : or group
09:06 : of string
09:07 : as a token
09:09 : and then
09:10 : blah blah blah i'm not going to box the
09:12 : rest of it you can imagine the rest but
09:14 : what ends up happening is
09:16 : the
09:17 : the lectures drop is just to create a
09:20 : stream of these tokens so like
09:23 : let
09:25 : a
09:27 : equals
09:29 : one dot dot dot
09:31 : each one would look like
09:34 : in javascript terms would look like a
09:36 : object that has a particular type this
09:39 : is a let
09:41 : keyword or something type of the thing
09:44 : is a let keyword and then that's
09:46 : actually enough to describe this entire
09:49 : token whereas this one it's it's a
09:52 : number literal and then but you also
09:55 : need some more properties to
09:57 : to say what
09:59 : number it actually is etc so and so you
10:02 : you broke up this uh
10:05 : contiguous string into a smaller number
10:08 : of chunks that are more meaningful and
10:10 : with console.log you probably break it
10:13 : up
10:13 : console is a keyword
10:16 : that is an operator log is another
10:19 : keyword i'm not keyword sorry identifier
10:22 : we call these identifier because they're
10:24 : like
10:25 : variable names or function names
10:28 : uh is that good enough for now i don't
10:31 : want to go into the whole thing about
10:32 : parsers though today
10:36 : okay
10:37 : um
10:39 : okay
10:40 : so
10:42 : i do have
10:43 : videos on my channel too that goes much
10:46 : deeper into the parsing aspect of it if
10:48 : you're interested
10:50 : um okay but what we're gonna do is
10:53 : we're just gonna take the javascript
10:55 : parser as given to us
10:58 : and it's very easy to do because all you
11:01 : have to do is npm install
11:03 : i have already done this npm install as
11:06 : prima or npm install acorn
11:09 : and boom you have a javascript parser
11:11 : i'm not going to do it i already have it
11:13 : and then
11:15 : um
11:16 : also on this as prima website there's a
11:19 : demo
11:20 : online demo
11:22 : so if you don't even want to bother
11:24 : installing anything
11:26 : you can just put it do it here there's a
11:28 : sandbox playground kind of deal
11:30 : uh you you write some javascript
11:33 : javascript code here
11:35 : and it shows you what the ast of that
11:39 : would be
11:40 : and in our case i could copy my little
11:43 : example here
11:47 : and then it shows you oh
11:48 : okay i parsed it and
11:51 : the ast
11:53 : for this program is
11:55 : okay it's a program that the top level
11:57 : is a node that it's the program node
12:01 : the program has a body consisting of an
12:03 : array of statements
12:05 : and then the first step let me do it
12:07 : over here okay
12:09 : uh i i still like to see actually the
12:12 : javascript syntax more but we could look
12:15 : at this and but i also wrote a program
12:18 : like we don't have to do it online i
12:20 : like to to stay in the command line and
12:22 : my text editor so i wrote a little
12:24 : parse.js
12:26 : program to do the equivalent thing
12:30 : which it's a small program i require as
12:33 : prima i i get the file system module
12:36 : from node.js
12:38 : i use the async await syntax so
12:41 : just read in the file
12:43 : get the source code out
12:46 : and then i'm going to use
12:48 : isprima.parse to take the code that is
12:51 : in the string form and parse it and out
12:53 : comes the ast boom uh i'm gonna json
12:57 : stringify that and uh save it to a dot
13:00 : ast file so i'm gonna go ahead and do
13:02 : that now so i'm gonna say no parse.js
13:07 : i'm going to parse the example one
13:10 : and the result of that is we generated
13:12 : an example one
13:14 : ast file
13:15 : go look at that
13:17 : it looks like this and it's the same
13:19 : thing as what you see in the online demo
13:22 : okay there are some options
13:24 : that can control
13:26 : you know
13:27 : uh
13:28 : adding optional properties to
13:31 : stuff to this tree but more or less it's
13:33 : the same thing uh here in my text editor
13:36 : i can like expand
13:38 : collapse things which is helpful
13:40 : sometimes so
13:42 : if we look at i wanna sort of
13:45 : give you a side by side
13:53 : okay
13:55 : so try to reason about this
13:58 : tree structure
14:01 : um well line one is you know the first
14:05 : the first sort of statement
14:08 : within the body of this program right
14:11 : and so this object is a full description
14:14 : of what line one is
14:16 : uh what what is line one it's a variable
14:19 : declaration
14:21 : uh a variable declaration could
14:23 : potentially have multiple declarations
14:26 : so
14:27 : i guess that's why it's an array but in
14:29 : this case we only have one of them
14:31 : uh and and that's this one
14:34 : and you'll see well okay
14:37 : uh a it's called a variable declarator i
14:40 : guess a deck
14:42 : it's a variable declarator whose
14:44 : identifier is a
14:46 : and it's init the initial value of the
14:49 : declaration
14:50 : is a literal and the value of the
14:52 : literal is a one so it all makes sense
14:54 : it's i mean it's it might be a bit
14:56 : verbose
14:58 : but it all makes sense also the
15:01 : the top level variable declaration has
15:03 : the kind of let so you can imagine if it
15:06 : was a const
15:08 : i'll go
15:10 : and i'd parse it again
15:12 : i just change the con kind to cons so
15:15 : this is this is a basically a full
15:17 : description of what your line of code is
15:20 : saying
15:21 : uh again it's a bit verbose but you can
15:24 : make sense of it if you go in and read
15:27 : every single bit and try to reason about
15:30 : it and we have the same thing for each
15:32 : one of these things i'm just going to
15:34 : put this back to let
15:36 : so my question is to you right
15:39 : how given this i have this tree of
15:44 : syntactical element
15:46 : uh which fully describes what this code
15:49 : is there let's actually go through the
15:51 : more complex ones
15:57 : so that i can
15:59 : yeah
16:00 : so like the line 4 example yeah line for
16:04 : example
16:06 : again line four is also a variable
16:08 : declaration
16:10 : um
16:11 : with one declaration the kind is also
16:13 : let
16:15 : and then
16:16 : in
16:18 : oh
16:20 : uh
16:21 : yes thank you thank you john okay i'll
16:24 : make this font smaller so yeah line four
16:26 : is more complex and that's kind of why i
16:29 : wanted to do it so line four okay it's
16:32 : actually this one
16:33 : um
16:35 : yeah so you can see pow here so if we we
16:38 : try to actually go through it
16:40 : um okay it's a it's a variable
16:42 : declaration uh its kind is let still
16:47 : and it's
16:48 : inside of the variable declaration we
16:50 : have one variable declaration
16:52 : declarator whose identifier is answer
16:56 : and then but its initial value is this
16:58 : whole thing this whole thing is kind of
17:00 : complex
17:02 : because it's doing this uh
17:04 : compound expression here and the
17:06 : compound expression is actually
17:10 : firstly it's a call expression like the
17:12 : top level of this guy this is a call
17:14 : expression
17:16 : that makes sense uh it's called e
17:19 : uh the callee is um
17:23 : a member expression
17:26 : uh
17:28 : where the object is math
17:31 : and the property is pal so the callee is
17:35 : this guy
17:36 : and this guy is a member expression i
17:39 : guess this dot expression we're going to
17:41 : call that a member expression
17:44 : so
17:45 : math.pal is the callee
17:47 : and then the argument is these two
17:50 : things uh an identifier c and followed
17:53 : by a literal which is two so all this
17:55 : makes sense
17:57 : uh
18:02 : yeah if we did
18:05 : my fun
18:11 : yeah
18:13 : it this this is still a call expression
18:16 : but the callee is just identifier my fun
18:20 : whereas before
18:22 : whereas before if i change this back
18:27 : if it changes back the is is also a call
18:30 : expression but the callee is the result
18:33 : of a member expression because there's
18:35 : there's more stuff here it's more
18:37 : compounded
18:39 : expression into so so you can actually
18:42 : see this is like um
18:44 : when you write a
18:46 : like a you know a line of javascript
18:49 : with multiple parts in it
18:51 : um
18:53 : it's actually a compounding thing so
18:56 : what's going on here
18:58 : you can see sort of this this coastline
19:01 : of this
19:02 : tree like a beach coastline kind of deal
19:06 : [Music]
19:08 : and that's one visual representation of
19:10 : the tree another visual representation
19:13 : might be hey this is this is an
19:16 : assignment well okay
19:18 : this is uh it's a let expression
19:21 : um
19:23 : and
19:25 : we're
19:27 : i'm
19:28 : this is not not very standard but you
19:32 : know
19:33 : i'm just making this up as i go but i'm
19:36 : gonna try to write this as a tree right
19:40 : this is actually a call
19:44 : and
19:47 : and then this is i'm
19:50 : this is a the member thing
19:54 : i'm i'm doing math.pal here and then
19:59 : uh the call is like hey these are the
20:02 : arguments
20:03 : and then there's c
20:06 : and then two so you can visualize it in
20:09 : a tree that's sort of this this is more
20:10 : or less like just just this condensed
20:13 : way of looking at this whole thing
20:15 : so you can look at it all like this
20:19 : and uh if we wanted to write any code to
20:23 : reason about this source code
20:26 : what we're going to need to do is
20:27 : traverse this tree
20:29 : and uh that's recursion right that's
20:32 : that's like our
20:34 : our good friend
20:36 : uh recursion so what we're gonna we're
20:39 : gonna end up writing some function i'm
20:41 : gonna call it f
20:43 : um
20:45 : f
20:46 : and then initially we're going to say
20:48 : hey f take this whole tree
20:51 : but
20:52 : but then f in order to process the whole
20:54 : tree f is going to say hey okay i need
20:57 : to i need to traverse this
21:00 : maybe this i don't know i and i need to
21:03 : call myself on
21:05 : the sub tree
21:06 : and then the subtree is gonna call
21:08 : myself on it
21:10 : etc etc let me be on this on this
21:15 : on this
21:16 : f is gonna
21:17 : end up touching every single
21:20 : uh node within this tree so that's what
21:22 : we're gonna do uh um we're gonna start
21:25 : with like a reduce like just very simple
21:29 : example for now
21:32 : due to limited time
21:34 : if we had to cover all the different
21:36 : syntax variations of the language
21:39 : that would be more work
21:43 : okay so maybe what we should do
21:46 : does anyone wanna pair with me
21:50 : any takers
21:54 : no
21:56 : come on
21:59 : uh-huh
22:01 : okay let's do it
22:03 : so
22:04 : uh can you ask for um
22:07 : control oh let me see oh yeah
22:11 : okay
22:12 : uh all right so let's do this
22:14 : so
22:15 : oh i should
22:17 : open up
22:19 : dark ast
22:22 : on the side
22:24 : and i think it helps okay so
22:28 : let's go ahead and write a function
22:30 : called traverse
22:38 : okay so we're going to traverse down
22:43 : make the text a little bit larger here
22:47 : okay
22:49 : and i'll i'll let you drive so
22:52 : when we traverse uh this node uh
22:55 : initially it's gonna be this
22:58 : the top level this
23:00 : program node
23:02 : uh
23:03 : but we're gonna we're gonna make this
23:05 : traverse
23:06 : we're going to make it get called
23:08 : on that
23:10 : and that
23:12 : and that probably
23:14 : there might be some stuff we can skip
23:17 : but
23:17 : most of the notes we're going to make it
23:20 : traverse basically so
23:23 : how would you go about doing that
23:34 : exactly
23:35 : yeah
23:40 : and now notice that depends on what type
23:43 : of node it is right
23:45 : like we can sort of assume that if
23:48 : if it's a program node like if it's a
23:51 : type is a program
23:53 : we can assume it has a body for example
23:55 : and if it's type is a variable
23:57 : declaration we can assume it has a
24:00 : declarations which is an array and then
24:02 : once we get the array of children we can
24:05 : drill through them and call traverse on
24:08 : its children again right
24:10 : so so the first thing you need to
24:14 : check is for like what was the type of
24:16 : the node what is the node type right
24:20 : so
24:22 : so so i would actually write either a
24:24 : switch statement and this is extremely
24:27 : common by the way if you're making a
24:29 : programming language or making a linter
24:31 : tools like this
24:33 : you would often write either if if
24:35 : statement
24:37 : like a huge series of if statements or a
24:40 : switch statement
24:41 : just to detect what is the type of this
24:44 : node that you're getting so so why don't
24:46 : you go ahead and do that
24:49 : and and yeah we can restrict ourselves
24:51 : to just the ones that we see in this
24:54 : example
24:55 : because the language is quite large
25:03 : okay
25:12 : let's switch on node.type actually
25:31 : yeah you could
25:33 : we have variable declaration
25:48 : yeah variable declarator
25:55 : i also have a literal and identifier
26:09 : okay uh what else do we have
26:13 : we have binary expressions
26:25 : uh
26:26 : [Music]
26:28 : oh it's yours that's one not mine i
26:31 : think
26:33 : okay
26:35 : uh okay um
26:37 : [Music]
26:39 : we have core expressions and member
26:41 : expressions
26:47 : okay
26:49 : did we get them all
26:53 : uh
26:53 : i think maybe we did
26:56 : and and if we didn't then you throw an
26:59 : error here yeah and we'll it will tell
27:02 : us if we missed something
27:08 : okay
27:09 : um
27:10 : and to start with
27:12 : uh all i want to do
27:14 : is like print
27:16 : the note type maybe so maybe at the at
27:20 : the first line just print the note type
27:24 : and and then
27:25 : and then the purpose of the switch
27:27 : statement is not so much to do something
27:30 : with it as its purpose is really to get
27:33 : at its children and then recurse
27:37 : um
27:38 : so oh another thing i would recommend oh
27:41 : actually let's let's defer that a little
27:44 : bit so right now let's just do we don't
27:46 : have to do everything
27:48 : up front before we start testing it so
27:51 : we could do just a do a little bit and
27:53 : then test and then do a little bit uh
27:55 : that's more fun that way i think so
27:58 : maybe you just just figure out for
28:00 : program
28:01 : for the program node
28:03 : um
28:05 : let's write the code to recurse
28:08 : we know program has a body
28:10 : oh make sure you do a break by the way
28:15 : when you do
28:17 : switch statements make sure you do
28:18 : breaks
28:21 : otherwise you will it might cost you
28:23 : some time debugging later
28:41 : okay
28:57 : oh yeah
29:02 : yeah uh
29:06 : i
29:08 : i don't have a good
29:10 : answer i i think it depends case by case
29:13 : if
29:14 : if you have
29:16 : let me see
29:17 : i don't even know sometimes
29:20 : the programming language will optimize
29:22 : it in
29:24 : unexpected ways
29:27 : such that
29:29 : you like you kind of can't predict which
29:32 : one is best but intuitively speaking i
29:35 : would expect
29:36 : if you do a series of
29:39 : if statements
29:42 : or a series of switch statements
29:46 : it
29:47 : and and if this list gets to be large
29:51 : maybe it would start getting slow i
29:54 : don't know
30:02 : oh
30:07 : the thing though is
30:08 : that that kind of low-level stuff in the
30:11 : cpu is actually pretty fast
30:14 : and if if you go to a
30:17 : dictionary that's like you make a
30:19 : dictionary of a dispatch dictionary that
30:22 : has a bunch of pointers to functions
30:25 : um
30:27 : if you do that
30:29 : um there's there's actually overhead to
30:31 : using a dictionary even though we think
30:34 : dictionaries are the fastest things out
30:36 : there they're actually not because what
30:39 : ends up happening is
30:41 : for example if you if you look up
30:44 : variable declarator in the dictionary
30:46 : that's that's a key in your dictionary
30:49 : well now that the code is actually going
30:51 : to have to calculate
30:53 : a hash
30:55 : uh by iterating the entire string
30:58 : so it actually is
31:00 : you know it has to take in every single
31:03 : character
31:04 : and put it into this hash and then do
31:07 : some a little bit more calculation to
31:09 : calculate where in the dictionary
31:12 : the
31:12 : value actually is
31:14 : and it's got a little bit of other
31:16 : overhead as well so
31:19 : even though the
31:20 : average run time of accessing a
31:23 : dictionary is big of one
31:25 : and
31:26 : and and you know
31:28 : doing a
31:30 : conditional like this well we is we have
31:33 : a lot of conditionals
31:35 : but that that big o of one doesn't mean
31:38 : it's instant big o of one just means
31:40 : it's invariant to the number of things
31:43 : you have here but
31:45 : but but if if one of these conditionals
31:49 : is super fast it doesn't matter that you
31:51 : have a lot of them
31:53 : you know
31:55 : so
31:56 : yeah so like the over overall overhead
31:59 : of the dictionary
32:00 : it's just like it's
32:02 : in my mind it's
32:04 : unclear in my mind it's just unclear
32:06 : that's what i'm gonna so so like
32:08 : um
32:10 : either way
32:12 : either way is probably fine yeah for
32:14 : something like this
32:20 : okay
32:22 : if if performance is really a concern
32:24 : then you really want to like test it
32:29 : like
32:30 : drive it using data like set up some
32:33 : tests benchmarks that are meaningful to
32:35 : your app
32:38 : and go from there and like load a large
32:41 : amount of data through it so that it's
32:43 : you can see it being slow etcetera
32:45 : um
32:47 : okay let's keep going um so if it's a
32:50 : program node how are we gonna recurse
32:54 : through its children
32:56 : in its body
33:23 : let let's assume it is always going to
33:26 : have a body yeah
34:05 : yeah i kind of like regular foods
34:27 : cool
34:28 : um
34:30 : let's go and run this actually i'm gonna
34:33 : throw some
34:34 : glue coat together
35:00 : so i'm just gonna do
35:04 : i guess i'll do this
35:11 : and then i will
35:23 : yeah i i need it to be async yeah
35:27 : i need i need it to be async um i guess
35:30 : i'll just read in
35:33 : i think i would read in the
35:36 : uh ast file so i'm going to read the
35:39 : file
35:41 : this is going to be json and then pst is
35:45 : going to be
35:47 : jsonparse
35:49 : the json and then i'm going to feed it
35:52 : through the traverse function
35:56 : and all right let's see what happens
36:10 : oh this is
36:14 : this is like this
36:15 : more or less
36:18 : uh this this is a
36:20 : promise
36:21 : this is a promise api
36:23 : because a single wave function always
36:26 : returns a promise so i'm just using the
36:28 : catch of the promise api
36:36 : like like this
36:38 : i i don't think
36:40 : uh
36:44 : oh i i see
36:46 : i i see what you're saying um
36:49 : [Music]
36:50 : yeah i could do that but it might
36:53 : complain that i'm not catching
36:56 : maybe yeah you're saying just do this
37:14 : yeah let's do it this way
37:23 : i don't i might have gotten it to
37:25 : complain
37:26 : but let's see
37:28 : callback
37:29 : must be a function
37:33 : traverse
37:34 : line number 10
37:37 : uh line number 10
37:39 : [Music]
37:41 : oh
37:43 : i need to use the promises version of
37:46 : file system okay great we're getting
37:49 : somewhere oh we we did hit the note type
37:51 : not handled so that's interesting
37:54 : uh
37:55 : so like which note type wasn't handled
37:58 : let's see
38:00 : uh expression statement okay we missed
38:03 : the expression statement that's okay but
38:06 : we're getting somewhere um
38:09 : so one thing i recommend when you're
38:12 : doing recursion stuff like this
38:14 : which which you like this is very very
38:16 : common um but
38:18 : yeah it comes up in all sorts of places
38:22 : uh one thing i find that helps it is
38:24 : like a poor man's
38:27 : poor man's sort of recursion stack
38:30 : visualize visualizer i pass a level
38:33 : number in
38:35 : and then every time i recurse i increase
38:38 : the level number so that the first time
38:42 : you pass in zero
38:43 : and then the purpose of doing that is
38:46 : i'm gonna indent
38:48 : in my my log statement
38:50 : uh i'm gonna do like level
38:54 : plus one and then drawing
38:56 : and and that that's my indentation and
38:59 : i'm gonna put my indentation in the
39:00 : console.log and if i do that
39:03 : i get all my statements indented isn't
39:06 : that nice
39:08 : um so so that's really a good debugging
39:11 : aid
39:12 : um so okay
39:16 : so now
39:22 : okay
39:28 : yeah no no now i'm going to
39:31 : you're going to be the navigator for a
39:33 : while and i can type
39:35 : so you you tell me what to do
39:37 : okay john tell me what to do
39:57 : yeah
39:59 : yeah
40:02 : okay
40:17 : yep
40:21 : cool
40:22 : um um
40:25 : yeah that that is actually
40:27 : quite cool
40:29 : um
40:31 : it would
40:32 : be
40:34 : okay let's keep going then um if it's a
40:37 : variable declarator
40:40 : we still have it still has children
40:43 : though
40:44 : right so what should we do with the
40:46 : variable declarator
41:01 : no i would i would still call them child
41:03 : children because the variable declarator
41:07 : is
41:08 : this object and then the
41:10 : this guy is
41:13 : like here it's nested inside of the
41:16 : outer object
41:18 : which is the variable declarator
41:20 : right
41:21 : so i would still call it a child like
41:23 : the id of variable declarator is a child
41:26 : of the variable declarator
41:28 : and the init
41:30 : of the variable declaration is also a
41:33 : child
41:34 : and in in any case we need to
41:37 : visit it we want to traverse it so
41:39 : somebody has to do it
41:45 : yep
41:48 : yeah
41:49 : so how do we do that
42:12 : yeah
42:13 : yeah exactly
42:22 : yeah it looks funny next to this kind of
42:25 : thing but yeah
42:27 : that's it
42:28 : um okay what about literal well a
42:32 : literal is just like a number or a
42:34 : string literal
42:36 : well there's no children there so
42:39 : nothing to do
42:41 : um
42:42 : we we might even
42:45 : well
42:47 : i don't know
42:49 : i kind of
42:50 : part of me wants to print out the
42:52 : literal
43:05 : yeah let's just go ahead and do that
43:10 : um so we printed the type over here so
43:14 : we already have printed the type maybe
43:17 : we print
43:19 : with the same indentation
43:21 : we print a node.value
43:27 : yeah and then for identifier similar
43:29 : thing
43:32 : we print node.name
43:35 : okay let's see that
43:38 : invalid array length oops
43:41 : line 21.
43:44 : oh
43:45 : did i forget to
43:47 : the level
43:49 : i i forgot to
43:52 : pass the level in there
43:55 : okay
43:58 : that's pretty nice
44:01 : maybe do a little bit more indentation
44:03 : here
44:09 : okay we
44:11 : okay we can traverse the tree we haven't
44:13 : done everything um
44:15 : but yeah
44:17 : let's keep going
44:18 : um
44:20 : okay if it's a binary expression
44:24 : um
44:26 : uh does anyone else wanna
44:28 : wanna work with me wanna pair with me
44:30 : maybe
44:31 : rachel maybe
44:33 : andres
44:39 : okay
44:44 : okay all right let's go um so
44:48 : all right we have a binary expression
44:50 : and we're gonna go through its children
44:52 : uh what are we gonna do in this case
44:54 : jonah i'll let you i'll let you drive
44:56 : again
45:08 : uh
45:09 : yeah uh let's
45:11 : well this is a similar to the variable
45:14 : declarator one except we just have to do
45:16 : it left and right
45:19 : and don't don't don't oh let me change
45:22 : the keyboard back okay it's back to
45:25 : yeah
45:26 : through a wreck
45:30 : don't forget to put in the level
45:48 : okay let's test it
45:52 : okay i'll test it
45:57 : do we even
46:01 : oh yeah the binary oh we might wanna
46:05 : yeah yeah it worked but it would have
46:07 : been nice if we printed out the uh can
46:10 : you print out the
46:12 : operator right here
46:17 : similar to how we did the identifier and
46:19 : the literal
46:30 : all right
46:31 : great you see see there's a little
46:34 : operator here
46:35 : yeah so you can read the tree now
46:38 : um
46:40 : i mean if this is
46:42 : maybe you might think oh this is not
46:44 : exciting well i already can see the tree
46:47 : here why are we doing this uh this is
46:49 : the first step to
46:51 : being able to traverse the tree
46:54 : and then uh
46:55 : and then later on what we can do is
46:58 : gather all of the identifiers
47:01 : right and once we once we're able to
47:05 : go through every single node in the tree
47:07 : then we can be certain that if we just
47:12 : add a little bit of logic here that if
47:14 : the type is identifier let's collect
47:16 : that
47:17 : now we have a list of the audio
47:19 : identifiers
47:21 : that were they were referenced
47:23 : or something like that
47:33 : yeah
47:34 : yes
47:42 : yes
47:45 : it's a deep dive i know
47:47 : deep dive with no um
47:51 : what's the word
47:52 : uh
47:55 : no reservations
47:57 : deep dive deep dive with no reservations
48:00 : yeah that's what how i would put it
48:02 : whereas the breath first is like
48:04 : yeah i wanna i'm gonna try it
48:07 : and then come back
48:08 : you know
48:10 : the breath first search is
48:12 : actually more complex to write it
48:14 : involves a queue
48:16 : but yeah but uh okay let's keep going
48:22 : [Music]
48:32 : but
48:33 : no no a call expression oh yeah you're
48:35 : right sorry sorry sorry yeah we don't
48:37 : care about what the caller is we're just
48:39 : going to feed the colleague back into
48:41 : the traverse and the next time we can
48:43 : deal with it then
48:45 : but it also got an argument which is
48:47 : going to be an array of nodes
48:52 : so
48:55 : yep exactly
49:15 : you
49:32 : okay
49:33 : and
49:34 : and then remember
49:37 : oh member is this one
49:41 : oh
49:43 : where is it
49:45 : oops
49:48 : member expression okay
49:49 : [Music]
49:51 : uh
49:52 : all right let's do remember as well uh
49:55 : similar to the binary expression again
49:58 : i guess there's an object and a uh
50:01 : property
50:03 : each one we're gonna traverse it
50:06 : oops switch back to keyboard uh
50:14 : oh
50:16 : okay go ahead
50:17 : oh okay go ahead
50:39 : okay and let's just go ahead and finish
50:41 : it off with the expression
50:45 : expression where are you
50:47 : there you are
50:49 : uh okay an expression
50:54 : oh it just has a child
50:57 : which is its expression
50:59 : okay
51:01 : [Music]
51:02 : that's fine
51:03 : it doesn't seem to do all that much but
51:05 : that's okay so you can just traverse
51:08 : know that expression
51:13 : oh it's because it's an expression all
51:16 : on a line is that why
51:19 : like
51:19 : what was the last line oh yeah
51:26 : it was the console.log yeah this this is
51:29 : saying this whole thing is a statement
51:31 : i'm an expression this whole thing is
51:34 : just as expression
51:36 : as as in a function call is just an
51:38 : expression but i think in their line i
51:40 : mean they could have just put the call
51:43 : expression
51:44 : directly
51:46 : but maybe the javascript language
51:48 : doesn't allow that or
51:50 : or they want it to be more
51:54 : formal about it or strict about it
52:05 : well line 4 would be a variable
52:06 : declaration
52:09 : yeah
52:10 : it's a very
52:25 : yeah that's because this
52:26 : with many languages there's a subtle
52:29 : distinction between a statement versus
52:32 : an expression
52:33 : an expression is that
52:35 : an expression is like a thing that
52:37 : eventually gives you a value after it's
52:40 : computed whereas
52:42 : whereas a statement is a statement that
52:45 : it does something
52:47 : uh and there's that difference and but
52:49 : some of the time
52:51 : an expression can also be a statement
52:53 : but so but this is the thing
52:56 : that
52:57 : sort of
52:58 : glues that together i guess in that case
53:02 : this
53:17 : yeah it's it's a descendant of lisp and
53:19 : that's what lisp was all about yeah so
53:22 : now we have this traversal function that
53:25 : works
53:27 : completely at least on this very limited
53:30 : example
53:32 : but you can imagine if we were to
53:34 : support the entire javascript language
53:36 : then this switch statement would get
53:38 : very large
53:40 : um and uh but in any and there's
53:44 : actually a
53:45 : library that you can use
53:48 : to help you
53:49 : it's called es traverse
53:51 : um so if you use es traverse all the
53:54 : work that you were doing
53:57 : you can skip that
53:59 : you can you can say hey yes traverse
54:02 : and then it'll it'll it'll have this
54:04 : gigantic switch statement inside of es
54:07 : traverse
54:08 : and you can just pass it a function and
54:11 : that is enter or leave
54:14 : um
54:15 : depending on whether
54:16 : you
54:17 : then depends on the order of the
54:20 : traversal whether you use enter or leave
54:22 : you can just use one or both if you want
54:26 : but basically it'll take your function
54:28 : and
54:30 : it will it'll call it
54:33 : at this point of
54:35 : your program
54:37 : for you
54:38 : and we could we could do that too right
54:40 : we could we could say hey i want to pass
54:42 : in a function
54:44 : and then i'm just going to call this
54:46 : function
54:49 : and and tell you what node i visited
54:53 : um and
54:54 : and that's that's a way to extract
54:56 : this
54:57 : this code and
54:59 : let the consumer not have to write this
55:01 : huge statement switch statement all the
55:03 : time
55:04 : and that's quite nice so
55:06 : but we're gonna keep it simple and just
55:09 : do it like this but uh i guess what we
55:11 : could do here is
55:14 : right
55:16 : oh we're at three
55:18 : okay yeah this um
55:21 : yeah maybe this is good to stop
55:25 : now um we can continue this
55:28 : next time uh
55:30 : i think this is a pretty good
55:33 : exercise
55:35 : in my opinion
55:36 : um
55:38 : yeah um
55:39 : what would i say about that i guess
55:42 : i guess
55:43 : um
55:43 : [Music]
55:46 : if if you're interested in like
55:48 : continuing this on your own you're
55:50 : you're welcome to do that uh oh i think
55:52 : i'll post this code
55:54 : on github somewhere if anybody is
55:56 : interested in it or if you want to
55:58 : follow along
55:59 : um
56:01 : the next step after having done this
56:03 : would be
56:05 : you write a little bit code here
56:08 : to see hey if i have
56:10 : basically you want to single out
56:13 : the
56:14 : assignments versus
56:17 : the variable references right
56:20 : if like where where in this code am i
56:23 : referring to a pre-existing
56:26 : variable and how can i tell
56:29 : by looking at this structure i know by
56:32 : looking at it it's
56:34 : here
56:35 : and here
56:36 : and here i'm making a reference to some
56:39 : pre-existing variable and the place i'm
56:41 : defining a variable is here here
56:45 : and here and
56:47 : in both cases i'm going to have to deal
56:49 : with this
56:50 : identifier
56:52 : node here like when i'm referencing
56:54 : something there's going to be an
56:56 : identifier this this is actually console
56:58 : console is also identifier node by the
57:01 : way
57:02 : um
57:03 : but when you're declaring something
57:06 : right with a variable declarator
57:08 : you're also going to have this
57:10 : identifier node but it the identifier
57:12 : node is in this id property of the
57:15 : variable declarator so you think about
57:18 : um think about that like how can i tell
57:22 : when i have an identifier node and i'm
57:25 : actually declaring a variable and then
57:28 : put that in a table somewhere
57:31 : and then how can i tell when i'm
57:32 : referencing an identifier node and it's
57:35 : actually referring to a pre-existing
57:37 : variable and i put that in table
57:39 : somewhere and now i can get like those
57:41 : two things or
57:42 : or just an array somewhere array of the
57:45 : declared variables
57:46 : array of the reference variables and
57:49 : then at the end i can compare and to
57:51 : figure out which declared variables is
57:53 : actually unneeded
57:55 : so that's what we'll do next time i
57:58 : think
58:00 : thanks everyone