Time Traveling Debugger

In this video I’ll dig into the internals of the code generator of the Fun language to show you where most of the magic happens to make the time traveling debugger work.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello there welcome to the
00:03 : time-travelling debugger part 3 so this
00:05 : is going to continue off of the first
00:10 : two videos about the time-travelling
00:12 : debugger proof of concept implementation
00:16 : that I have built over the holidays this
00:22 : one I'm gonna focus on the internals or
00:26 : the how it works or just slightly lower
00:32 : level how it works last two videos I
00:36 : sort of gave you the high level how it
00:38 : works but this is gonna be a little bit
00:40 : lower level so let's get right into it
00:45 : okay so with with the fun programming
00:52 : language what you can do with the code
00:55 : is last time I showed you how to run
00:57 : scripts using or in fun line so let's
01:02 : say if I wanted to run this zip dot fun
01:06 : program then I would I use this run that
01:13 : j/s script to execute it like so and it
01:18 : will do it however you can also in order
01:24 : to run a program there there's actually
01:27 : a few steps that happens
01:30 : so the first step so let me draw a
01:33 : diagram here so you got your fun code
01:43 : and so you're gonna write your final
01:46 : code and that's your your zip that fun
01:49 : yeah that's the fun code the first step
01:53 : it goes through is the parse parser okay
02:01 : which I actually regret drawing this as
02:07 : a
02:08 : there's a rectangle now I'm gonna go
02:11 : back and draw this guy as a circle
02:15 : because I want the I want the artifacts
02:19 : to have a different shape than the
02:23 : machinery so the machinery is going to
02:27 : be rectangles so the Funko it goes it's
02:32 : gonna go through the parser which will
02:34 : generate the ast which stands for the
02:38 : abstract syntax tree which if you
02:41 : haven't seen that you will get to see it
02:43 : very soon and if you want a more
02:45 : detailed description about that you can
02:48 : watch the the video series I created
02:53 : about how to make a programming language
02:55 : now after you have an ast you're gonna
02:58 : send that through actually to the
03:02 : checker first we have a checker thing we
03:10 : have a checker which basically checks is
03:13 : for impure anus I've functioned in the
03:18 : case that you have written a fun which
03:20 : is meant to be pure among other things
03:24 : but that's actually kind of insuk
03:28 : inconsequential to what we're doing
03:30 : because it's gonna use the checker to
03:32 : tell you whether it's okay or not so
03:35 : this is like gives you an okay which is
03:41 : which is just a boolean flag and if it's
03:45 : not okay if you it will give you some
03:47 : error messages indicates that it is okay
03:50 : then it'll take this ast and send it
03:53 : through another thing and that's the
03:55 : thing we're gonna be talking about today
03:57 : that is the code generator I'll call it
04:01 : the code generator what code what code
04:05 : is a generating JavaScript this code
04:10 : generator is going to generate
04:11 : JavaScript and then
04:15 : it's gonna generate a JavaScript program
04:18 : essentially based on the ast of the
04:21 : original fun code and then once we have
04:25 : this JavaScript we're just gonna send
04:27 : that guy to an OGS to execute this
04:33 : JavaScript code and that's basically the
04:37 : plan the main thing that had to change
04:41 : in order to support the time-travelling
04:45 : debugger who was the code generator so
04:47 : that's the part we're gonna be focusing
04:49 : on but each of these steps I'm actually
04:51 : gonna skip the checker because that's
04:55 : not all that relevant in our discussion
05:00 : that we're gonna have today so basically
05:03 : we're gonna man the only sort of run the
05:05 : parser and then manually run the code
05:08 : generator and see what we get
05:10 : let's get to that so how do we manually
05:13 : run the parser well there's a parse dr.
05:17 : yes
05:19 : you just run that one instead of run J's
05:22 : and your parse the zip that fun file and
05:26 : generally a fib is T file let's look at
05:29 : that so it looks like this this is a
05:32 : basically a semantic representation of
05:35 : what the code is so it should make sense
05:41 : as in this should be a accurate and
05:45 : meaningful representation of what this
05:48 : code is so what does it says it says the
05:53 : top-level structure of the ast is an
05:56 : array because it's it's a number of
05:59 : different program statements and each
06:02 : program statement has a type and this
06:05 : and represented by an object and you can
06:08 : sort of collapse these if you want but
06:12 : basically the first program salmon is a
06:14 : proc definition which that looks like so
06:18 : that looks to be the case it's a proc
06:21 : statement so it's a proc definition
06:23 : statement
06:24 : whose name is
06:25 : and identifier name is yet another node
06:29 : inside the ast and its type is an
06:32 : identifier the value is main search the
06:35 : name main and then the main does it have
06:40 : any parameters no it does not and then
06:43 : it has a body which contains a code
06:47 : block and then the code block contains
06:49 : more statements and in this one there's
06:53 : two statements so it should see two
06:56 : objects within the statements within the
07:00 : code blocks so this is one which is a
07:04 : VAR assignment to the variable result
07:07 : and I should see another one which is a
07:09 : KO expression to the the defib function
07:15 : oh wait no this is still part of this
07:19 : for assignment it's just the value part
07:22 : of the VAR Simon is a result of a call
07:25 : expression which was this one which
07:28 : we're calling the fifth function with
07:31 : the argument a number literal of eight
07:35 : okay so that all of this was the first
07:39 : statement and then the second statement
07:40 : is a call expression to the print
07:43 : function well it's a proc not really a
07:46 : function but you get the idea so
07:49 : basically that is what the ast is again
07:53 : if you want more detail about that watch
07:54 : the other videos that I made um so then
07:59 : the next part the in more interesting
08:02 : part that I want to get into is the
08:04 : generator how do you run the generator
08:06 : you run the generate script generated
08:10 : script and you need to feed into it the
08:15 : ast file because as we have seen well
08:20 : the B generate step takes in DST so you
08:24 : do that and we generate a fib dot - yes
08:27 : because that's what the generate step
08:30 : thus generates some JavaScript code
08:32 : let's look at this JavaScript okay so
08:35 : this is where the magic happens to allow
08:38 : the
08:39 : the history collection and the
08:43 : snapshotting of every single state of
08:47 : the program so the first thing is
08:51 : there's a history oh by the way I have I
08:54 : have put an dollar sign in front of a
08:59 : lot of these variables these these are
09:02 : global variables and they're global to
09:07 : the entire program but they're only used
09:09 : by this sort of back in time machinery
09:12 : and the fact that they prefix with a
09:16 : dollar character means that it's not
09:21 : possible for the function that the code
09:25 : itself to have name collisions with them
09:27 : because the fun language does not allow
09:30 : dollar characters in the variable names
09:34 : so this kind of protects against that so
09:39 : basically there's a history array which
09:42 : is going to contain every single
09:45 : snapshot so you can think of it as at
09:50 : the beginning of the program we have a
09:52 : state 1 and then the next time the
10:00 : snapshot is captured which will happen
10:05 : if we call this safe function then we
10:10 : have a state number 2 and every time
10:14 : this safe happens we'll have a new state
10:19 : stored where stored in the dollar at
10:22 : history array that's how it works what
10:30 : what is in the history what the inside
10:32 : the history what is a state
10:37 : a state is an object that contains two
10:43 : entries the the newline number so this
10:49 : is just some number let's say six it has
10:55 : a stack something which is an array of
11:00 : something let me write that out the
11:03 : stack is an array of frames which for
11:07 : now I'll write about that and then it
11:09 : has a heap okay so this this guy is a
11:15 : snapshot or state I will use those two
11:20 : terms somewhat interchangeably so this
11:24 : guy is what is called a snapshot and
11:29 : really the stack and the heap of a
11:31 : program sort of represents everything
11:35 : about the state of that program and the
11:37 : line number is just telling you where in
11:40 : the program we work during that snapshot
11:44 : where so you can also see this stack
11:48 : dollar stack variable and this dollar
11:50 : heap variable and those are the
11:53 : representations of the current stack and
11:56 : the current heap and they do need to
12:02 : update as the program executes and and
12:07 : and we talked about in the last video in
12:11 : part two we talked about the fact that
12:14 : and within the heap we have this ID
12:16 : scheme so I if there's an array in the
12:20 : heap we actually give each object in the
12:26 : heap an array a unique ID this unique ID
12:32 : and this this next heap ID is a counter
12:36 : variable that generates the unique ID as
12:40 : we go here
12:43 : all right so but let's I got a whole
12:47 : bunch of this support code here with a
12:50 : bunch of functions and also this safe
12:55 : history function which at the end of the
12:57 : program it writes the history out to a
13:00 : file using the JSON our library that we
13:06 : we briefly talked about last time JSON
13:09 : our yeah JSON with the refs which we
13:15 : talked about which is like JSON but it
13:19 : adds the ability to have references in
13:22 : the file so you can define an ID for an
13:26 : object or an array and then later on
13:28 : reference it using using this star
13:31 : syntax so this and syntax defines the
13:35 : object that follows and this star IDs
13:38 : index refers to the thing that was
13:40 : defined before okay so that's a trick
13:45 : that allows for structural sharing in in
13:50 : this massive history object okay so so
13:56 : let's actually look at the code that
13:58 : sort of crossed bonds to the original
14:02 : source code and that's gonna be this
14:04 : main function and this fib function you
14:09 : can already see it's quite a bit more
14:11 : complicated than the original source
14:13 : code let's do it side-by-side okay okay
14:23 : so so this push frame function and this
14:29 : pop frame function they happen every
14:32 : time a function is called and in the
14:35 : code for that is put immediately inside
14:38 : of the function definition so well not
14:42 : in mere after this variable I'm not
14:45 : gonna explain this for now but basically
14:47 : right inside of each function definition
14:50 : will have a push frame and pop frame and
14:52 : you can also see in the
14:54 : function we have a push frame and pop
14:57 : frame and what that does is essentially
15:00 : maintain a add an entry to the stack
15:04 : frame because if you remember he stack
15:08 : frame is like a queue that where when
15:11 : you call a function let's say we just
15:14 : called mean it's gonna have an entry
15:18 : here and then if inside the main
15:20 : function it calls fib it's gonna add
15:24 : another frame here mmm
15:27 : with a certain I don't know five or
15:31 : something and then if it calls itself
15:33 : it's gonna add even more frames so this
15:38 : push frame and pop frame is are the
15:41 : functions that maintain this creation
15:43 : and and cleanup of these frames so when
15:47 : it reaches the pop frame it's gonna get
15:50 : or not that one but I guess it would be
15:53 : this one this one would be for the main
15:55 : function every time you pop frame the
15:58 : frame gets destroyed every time we call
16:01 : push frame you get a new frame okay and
16:05 : we can take a quick look into the
16:08 : implementation of push frame and pop
16:11 : frame so new frame is gonna contain the
16:16 : function name so that we know what
16:18 : function has been called to generate
16:22 : this frame and then it's got the
16:24 : parameter that this function were called
16:26 : with and as well as the initial
16:28 : variables the initial local variables of
16:31 : the function and then the stack is gonna
16:34 : be basically this is using the spread
16:37 : operator to create a new version of the
16:40 : array that contains the previous content
16:43 : and the new frame and the top frame is
16:47 : just removing one from the end of the
16:51 : stack so that's how the stack frame
16:54 : well the stacks of the stack frame get
16:56 : initiated and then we have the variables
16:59 : so whereas in the normal code you just
17:05 : to do a variable assignment you just
17:07 : have an expression and assign it to a
17:09 : variable in the code that gets generated
17:12 : we're gonna call this set variable
17:14 : function pass in the variable name and
17:18 : then we're gonna sort of execute the
17:23 : expression which was here we have an
17:26 : extra safe here which is to save the
17:32 : state of the program right after that
17:38 : this function returns so there's sort of
17:40 : a go so it really is just so that the
17:43 : debugger will pause after this flip
17:47 : eight has been caught and it returns
17:49 : there's a pause to show that where we're
17:53 : on this line between moving into the
17:57 : next line and perhaps I should show that
18:05 : so I'm gonna execute the debugger and
18:08 : this guy so so I'll show you that um
18:12 : when you call the function step eight
18:16 : yeah so it's this so the fact that the
18:21 : code pauses here after this fit eight
18:27 : returns is due to we have a safe here to
18:31 : add another snapshot do the same line
18:34 : because otherwise it would have skipped
18:36 : over to here maybe that's too low-level
18:41 : but um yeah so anytime you set a
18:45 : variable you have to go through this
18:46 : dollar set variable function and every
18:50 : time you call safe it will snapshot the
18:53 : current state which again it just take
18:55 : this stack and the heap and stick it
18:59 : into the history array and anytime you
19:04 : get a variable you have you can't just
19:06 : reference the variable name we're gonna
19:09 : call this dollar get variable function
19:12 : so everything is very synthetic in a
19:15 : it's that we're not using Rio JavaScript
19:20 : variables I never get a variable we have
19:22 : to look up the current stack the top
19:25 : stack frame so this gets the current
19:30 : stack which is the last element of the
19:32 : stack array and then accesses its
19:36 : variables and then looks up the variable
19:39 : name that's how you get the value of a
19:41 : variable and setting a variable is you
19:45 : can't matter grab the grab the current
19:49 : stack frame and then instead of making a
19:53 : modification to the frame we can't do
19:55 : that because everything has to be done
19:56 : in an immutable way so instead of that
19:58 : we make a new frame with the change that
20:01 : we want which we copy over the contents
20:05 : of the old frame and because we're
20:08 : making a modification to the variables
20:10 : we're going to copy over the old
20:11 : variables and then just make a change to
20:13 : the D variable that we were wanting to
20:16 : change here and then finally we put back
20:20 : together the new version of the stack by
20:23 : first removing the current frame from
20:27 : the stack and then adding a new frame to
20:31 : it okay and saving is simply taking a
20:37 : line number create creating a new
20:41 : snapshot this this object here this
20:45 : inline object here could have been
20:46 : called snapshot and again a snapshot
20:49 : contains a line the stack which were
20:52 : just grabbing the current state of the
20:54 : stack and the heap which were grabbing
20:57 : the current state of the heap there so
21:01 : that's how all of this stuff works and
21:04 : then there's this special return value
21:07 : variable which is handy for just
21:09 : displaying
21:10 : to the developer the return value what
21:14 : the return value of the function is
21:15 : going to be which I have this special
21:19 : renamed variable court ret allow for
21:22 : that at the high level you can simply
21:25 : think of this
21:26 : as in the runtime of this program no
21:32 : longer uses the standard stack and
21:36 : standard heap on their own those
21:44 : facilities of JavaScript instead it
21:47 : creates a synthetic stack for itself to
21:52 : use so that the synthetic stack can be
21:56 : easily persisted into a file essentially
22:00 : that's what's happening and this is
22:02 : synthetic stack is that guy here we have
22:06 : a bunch of built-in functions that are
22:08 : available in the fund language and this
22:13 : heap allocate function is what generates
22:17 : a new ID for the heap so it takes the
22:25 : this next heap ID which started at one
22:28 : but each time it does this it'll add one
22:30 : to that so that will get unique IDs so
22:33 : this is how it generates an ID and then
22:37 : again it doesn't modify the heap but it
22:40 : makes a new version of the heap copies
22:43 : the old one over and then adds this new
22:46 : entry here
22:47 : that's how allocate heap works and
22:50 : allocate heap use anytime program needs
22:53 : to create a new array or tree a new
22:57 : dictionary this actually doesn't happen
22:59 : here collect multiples so when you
23:05 : create a new array it would need to call
23:07 : allocate heap and I can show it to you
23:10 : so I'll need to parse the collect
23:16 : multiples program and then I need to
23:18 : generate
23:24 : all right and it needs to take in an ast
23:27 : so let me so this is collect multiples
23:32 : and this is collect multiples GS okay
23:38 : all right let's see what correct
23:41 : multiples GS looks like so yeah so when
23:45 : a new array is instantiated we have to
23:49 : allocate heap in order to generate a new
23:52 : ID on the heap yep and if we run the
24:00 : debugger that's what gets us this ID one
24:05 : it was an empty array at this point and
24:08 : then the multiples variable points to
24:11 : the ID one and that happens because L he
24:15 : allocate a clear approach the number one
24:18 : he allocate at the same time you know
24:23 : create a new entry in the heap so
24:26 : basically he Bella Kate is gonna say
24:29 : make the heap look like this and then at
24:37 : the same time it'll return this one here
24:39 : and that's what makes one go into the
24:44 : multiples variable has its value okay so
24:49 : this is the code of the generator this
24:51 : is sort of the runtime code or the
24:54 : preamble which has these runtime support
24:58 : functions which I have shown you get and
25:03 : set I haven't talked about them but
25:06 : basically get is to access an index
25:09 : within an array or to access a key in a
25:13 : dictionary and set is the opposite of
25:16 : that to set an index within an array or
25:19 : set a key in the dictionary oh I didn't
25:22 : talk about the save history save history
25:26 : well I did a little bit actually save
25:28 : history takes in a file path and it'll
25:32 : basically take the
25:34 : the history array uses using the JSON
25:37 : our library to serialize it and then
25:41 : save it into that file and that is
25:43 : always done at the end here where we
25:48 : have this finally and this file name has
25:51 : been sort of a figured out by the
25:55 : generator the generator just Hart totes
25:57 : dis file name so that after the program
26:01 : is finished it'll take this history
26:05 : array which has been a key mode in the
26:07 : whole time and serialize it and save it
26:11 : into this file that's how that works
26:15 : okay so generate code how does it work
26:19 : all the various places where it's either
26:21 : accessing variables or setting variables
26:24 : we have to use these special functions
26:27 : so it VAR assignment has to generate
26:30 : code like this and every line of code
26:34 : that needs to snapshot the state of the
26:37 : program you just have to call this save
26:40 : function with the line number and the
26:43 : line numbers are actually easily
26:45 : retrieved from the AST because of the
26:48 : ast s have attached with them the line
26:51 : numbers of the beginning of and the end
26:54 : of each node so that's actually easy to
26:57 : get so so if we have statements like we
27:04 : have a proc main let's say and we have
27:13 : statement one statement to statement
27:17 : three really the general goal is to have
27:21 : stick a dollar safe in front of each one
27:29 : of these with some exceptions but most
27:33 : most of the time this is the case we're
27:36 : gonna stick a safe in front of each of
27:39 : these statements
27:42 : and that allows us to snapchat the state
27:45 : of the program at every single step
27:47 : basically all of the all of the
27:50 : generated code have to be infiltrated
27:52 : and this special machinery has to has to
27:57 : kick in so I hope that gives you a good
28:01 : enough idea of how this stuff works if
28:04 : you want to take in deeper you can check
28:06 : out the code is I've merged into master
28:12 : of fun Lang so if you go to fun Lang
28:14 : check out the code you should be able to
28:16 : run this code from the debugger etc it's
28:21 : by no means production ready or even
28:25 : complete at this point so you might
28:28 : encounter books some of which I'm
28:31 : working to fix as we speak okay so I
28:37 : hope you enjoyed that and I and I hope
28:40 : to have another update for you about the
28:44 : work I'm doing with this programming
28:45 : language soon see you then

Time Traveling Debugger - Part 3

Transcript