Time Traveling Debugger

In this video I demonstrate the time traveling debugger I built over my vacation. A time traveling debugger is a debugger that can step backwards in time. I devised a scheme to implement this concept using immutable data structures within the programming language. The Fun Programming Language was used as the test bed for implementing this concept.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello there this is Toby with this video
00:03 : I want to show off some work that I've
00:06 : done during the holidays so we my family
00:12 : went on a vacation and for some of the
00:16 : days I serve due to the jetlag I got up
00:21 : very early in the morning and did some
00:25 : coding and I want you to what I want to
00:28 : show you the stuff that I've been
00:31 : working on that coding serve I did that
00:36 : up until the point I got sick and then I
00:38 : stopped doing that and then but um but
00:42 : anyway I think I did some really
00:45 : exciting stuff so that's what I wanted
00:47 : to share with you I'm not going to share
00:52 : the rest of my holidays with you if you
00:56 : want to know more about that you're
00:58 : gonna have to ask me in person okay so
01:01 : what I have I been working on during my
01:03 : holidays um I've been I've been I had up
01:06 : till that point I had been thinking a
01:10 : long time about a concept and now a
01:16 : concept called the time travel debugger
01:22 : which time-traveling debugger if you
01:26 : will so the trend tab travelling
01:30 : debugger is a debugger that can go back
01:33 : in time essentially where if you have
01:36 : lines of code a normal debugger you know
01:41 : will be able to sort of step through
01:44 : line by line here and then here and then
01:48 : here and so forth a time-traveling
01:51 : debugger is able to walk backwards in
01:54 : time so that's what a time-traveling
01:57 : debugger is and I I thought of a scheme
02:02 : of how this could be implemented and
02:06 : yeah and I did it Eddie's I did a a very
02:11 : early prototype version of this as a
02:15 : proof of concept that this is actually
02:19 : possible so let me show that to you and
02:22 : I used the fun Lang programming language
02:27 : to implement this idea on because well I
02:33 : made this fun Lang recently and it's a
02:37 : very simple and small programming
02:39 : language so that was very good for my
02:43 : purposes of trying this out okay so let
02:47 : me show you how that works so I have in
02:51 : this play directory within this fun Lang
02:55 : language I have a field program I have a
02:59 : few programs written in fun and so this
03:05 : is a hello world program written in fun
03:09 : in and in fun the entry point of every
03:14 : program is a main proc and in fun we
03:19 : have procs and funds so like so like
03:25 : this is a fun when funds are supposed to
03:27 : be pure functions whereas procs can be
03:31 : impure if you want so that there was the
03:34 : main idea of the fun programming
03:36 : language but anyway so let's say you
03:40 : wanted to run this program what you
03:42 : would do is go to the command line and
03:45 : say node scripts run is and then you
03:50 : give it the file path of your program
03:55 : and it runs your program so simple
03:58 : notice that I have to take you run your
04:01 : program this dot history file has been
04:06 : generated and I'll talk more about know
04:08 : what that is after I show you this
04:11 : example so this example is a while loop
04:15 : it discounts from one to
04:17 : let's run that guy so there it is it
04:26 : will count from 1 to 10 and then at the
04:29 : end it says done again it creates this
04:32 : that history file what this that history
04:35 : file does is it enables the
04:38 : time-traveling debugger so let's let's
04:41 : use the time-traveling debugger so you
04:47 : do note and then scripts slash debugger
04:50 : and then again the path to your path to
04:56 : your program like that and the debugger
05:01 : will read in the source code and it'll
05:06 : also read in the dot history file and
05:10 : what it does what the dot history file
05:12 : is actually the dot history file has a
05:16 : snapshot of the entire state of the
05:19 : program at every step of the program
05:21 : which is what allows the debugger to go
05:26 : back and forth like a VCR essentially so
05:29 : at the beginning we're at line one of
05:33 : this program or I should say line two we
05:37 : execute that the next step we can see
05:41 : that on the stack over here that's the
05:43 : middle column so so this guy is the
05:50 : stack incidentally this guy is the heap
05:54 : which I I'm gonna show that off later
05:58 : currently we don't have any objects in
06:01 : the heap because I'm only a race or and
06:05 : dictionaries are stored in the heap and
06:07 : this program doesn't have either of
06:09 : those things ok so but I guess what the
06:14 : stack shows is the is that has a number
06:18 : of frames which I should probably show
06:22 : that but currently there's only one
06:24 : frame the the frame for this main
06:27 : function
06:28 : so this is to me how call this the
06:30 : mainframe perhaps although the word
06:34 : mainframe is kind of overloaded so the
06:39 : mainframe currently has one variable in
06:41 : it count and it's variable is 1 and the
06:44 : value is gonna change as we step through
06:48 : this function so every time I update the
06:51 : value of count you can see the value of
06:54 : the variable update within the frame but
06:57 : because this is a time traveling
06:59 : debugger and can step backwards in time
07:01 : and I'm just using the up and down arrow
07:04 : keys to step forwards and backwards so I
07:07 : can either step forward or backward and
07:09 : it'll sort of display the state of the
07:14 : program at that point in time and now
07:19 : we're at the end of the program so
07:21 : that's the idea of the time-traveling
07:23 : debugger I'll show you another example
07:25 : I'll show you a couple more examples
07:27 : before I actually explain how it works
07:32 : internally I have a zip program which
07:37 : calculates a Fibonacci number or it goes
07:41 : to a Fibonacci sequence I have two
07:43 : versions of actually the fit with a
07:47 : while loop and the fit with recursion
07:49 : let's just see both of those because we
07:54 : are computer science geeks we are very
07:58 : interested in the Fibonacci sequence
08:02 : okay so calculates the fib of 5 is 5
08:08 : doesn't seem very interesting
08:10 : let's go skip of 8 fib of eight is 21 so
08:14 : now let's use the debugger to sort of
08:18 : examine what happened
08:24 : okay so so the beginning we're going to
08:29 : we're here where we call it a sip
08:32 : function and when we when we sort of
08:37 : move to the next line it finds itself in
08:40 : the top of the fit function which makes
08:43 : sense
08:43 : and here is where the stack frame gets
08:46 : another frame Wow so this is and again
08:49 : the center column here that this is the
08:51 : stack frame and currently we have the
08:57 : main frame which again I hesitate to use
09:01 : that word the main frame but I just did
09:05 : but now we have a fib frame frame and a
09:15 : fib frame a frame a new frame is created
09:19 : whenever a function call has been issued
09:23 : and so this records the parameter that
09:27 : went in to that function and then within
09:30 : the frame we have the current state of
09:32 : the local variables of the function so
09:36 : so now you can see the multiple frames
09:40 : in action and now the first thing the
09:43 : SIP function is gonna do is instantiate
09:45 : I to 1 it will also make two more
09:49 : variables this fib I and SEP hi I sip I
09:53 : in this program used to mean the current
09:57 : Fibonacci number whereas fit by I is
10:00 : used to represent the next Fibonacci
10:02 : number after the current one so fit by
10:05 : is fib of 0 at present at least is
10:11 : supposed to be and the PI is supposed to
10:15 : be sub of 1 so loops 2 and we have used
10:18 : this temporary variable to do this swap
10:22 : thing because to generate the mix
10:25 : Fibonacci number after that that should
10:27 : be the sum of Pi and semi I so temps
10:32 : would have been sip III
10:35 : but then we do this swapping thing so
10:37 : that fit I ends up being the value of
10:41 : fit III and Philip III ends up being
10:43 : temp which would have been I and we
10:46 : basically do this thing over and over
10:48 : again
10:49 : and you can see D values change as we
10:53 : step through the code and I mean a
10:57 : normal debugger can do this the
11:00 : time-travelling debugger can also work
11:02 : backwards in time okay so so we're gonna
11:08 : step to the end of this program and at
11:11 : the end our program it shows you the
11:12 : return value when it encounters a return
11:15 : statement and in this case the return
11:17 : value is 2021
11:20 : and it shows the result as 21 and it
11:24 : shall print that result okay so that's
11:26 : let's do the same thing with the
11:28 : recursive version of Fibonacci so we're
11:33 : gonna run fit recursive that fun let's
11:38 : get it to goo no I'm just gonna go with
11:41 : a small number because otherwise the
11:43 : staff room gets a little bit long so now
11:47 : I'm gonna use the debugger on sip
11:52 : recursive and fit recursive works
11:56 : recursively as the name implies so if
12:00 : you call fib 5 it's actually gonna call
12:03 : fit again 4 v 4 and v 3 so I stuck to it
12:09 : to actually see that rather than me
12:11 : telling you so ok so we called fib 5 and
12:15 : you can see the end parameter to fit was
12:19 : 5 in this instance of the call to fit
12:24 : and and this conditional doesn't hit so
12:31 : it skips this if statement and you skip
12:33 : this N equals 1 conditional as well and
12:38 : it lands us here and then this is gonna
12:43 : make another call to fit with n minus
12:48 : one so that's how we got fit and equals
12:53 : four here on top of zip and equals five
12:55 : now we have more stacks
12:58 : that's three stacks at this point in in
13:01 : the stack frame and again n is neither 0
13:05 : or 1 so we have have to make yet another
13:07 : fit call this time with N equals 3 and
13:12 : that happens again for N equals 2 and it
13:16 : happens once more with N equals 1 but
13:19 : this time because N equals 1 is gonna
13:22 : return the 1 and when it returns 1 here
13:27 : we're feeling the N equals 1 version of
13:29 : fib once we return it we pop the stack
13:34 : means this guy will get destroyed
13:37 : because we return from it would
13:39 : terminate at execution of this function
13:41 : and we'll come back to this frame 1/2 so
13:44 : there we go so now we come back to this
13:46 : frame where n is equal to 2 and because
13:52 : this function call just returned with a
13:55 : value and we step through this fit of 1
14:00 : or fit one is gonna receive the value
14:03 : that this function return which was 1
14:06 : and if you don't believe we can just
14:09 : step backwards a couple of steps to see
14:12 : that the return value was 1 so that's
14:15 : how we got the one in fib
14:18 : 1 here and then the next line makes yet
14:21 : another call to fib so and this time we
14:27 : want to get the fib of n minus 2 because
14:30 : n is 2 n minus 2 is 0 so this call is
14:35 : gonna be n type of 0 which because
14:38 : that's 0 if so only returns 0 and we can
14:42 : see the return value is 0 now and we pop
14:45 : that stack off and now we're back to the
14:48 : frame for fit and equals 2 and
14:53 : and this fit underscore two is gonna
14:56 : return the receive the return value of
14:59 : that which if we walk back by one we can
15:04 : see that should be zero and therefore
15:07 : now fit two has zero in it and now we're
15:11 : gonna return the sum of fib 1 and step 2
15:15 : which is 1 and zero which was 1 and this
15:20 : one is gonna come back to the fit n
15:23 : equals 3 frame there here and so the
15:29 : return value goes into here and gets
15:32 : stored into the fib underscore one of
15:35 : this frame and and so forth and so forth
15:38 : so if we step through this entire
15:42 : program unless it goes faster mmm at the
15:49 : end when are we gonna get to the end
15:53 : this is a quite a long running program
15:56 : oh I think we are about at the end now
15:59 : yeah we are the return value of fib 5
16:02 : ended up being five because fib fib this
16:09 : would have been 3 v 3 is 3 and v 4 is 3
16:17 : and 53 would have been 2 and the sum of
16:20 : those is 5 and then we're gonna print it
16:23 : out okay all right so that does
16:27 : basically a run-through of how this
16:30 : debugger works one thing to note about
16:32 : the debugger is that it never the
16:36 : debugger never needs to re-execute this
16:39 : program in order to work because the
16:43 : debugger works entirely off of the
16:46 : history file which essentially contains
16:50 : the snapshot of every single state
16:53 : within the program so how does this work
16:59 : so let's go in and look at one of these
17:02 : history files
17:04 : let's actually start with a simpler one
17:07 : let's start with the this while loop one
17:10 : okay so this history file is in sort of
17:17 : JSON format but it's a JSON format with
17:21 : an extension that I had it and I called
17:27 : it JSON R which stands for JSON with
17:32 : refs what is refs a ref is it's an
17:37 : ability for one section of the JSON file
17:43 : to reference another object or array
17:47 : within the file so there's two syntaxes
17:52 : that JSON our introduces in addition to
17:57 : JSON when syntax is this n and then a
18:01 : number symbol and symbol and then a
18:04 : number and this is saying I'm defining
18:07 : at the number by the way is an ID for
18:10 : this particular object that follows
18:13 : so we're saying this object mmm
18:19 : here this whole object here we're gonna
18:21 : give it an ID of 1 and when you use this
18:25 : + symbol you're saying I'm defining the
18:28 : ID 1 as this object and here the same
18:32 : thing and two means we're defining the
18:37 : ID two to be there's this object that
18:43 : comes right after this ID definition
18:46 : when you see a star and an ID then it's
18:49 : a reference that means like the value of
18:55 : spouse should be referencing the object
19:00 : that was defined as ID 1 so this should
19:03 : point to this whole thing he essentially
19:07 : okay and that's how that works
19:09 : so the the reason I decided to implement
19:14 : this
19:16 : is because I wanted to make use of
19:21 : structural sharing to reduce the file
19:23 : size of the history file and I'll show
19:28 : you how that comes into play and and
19:30 : also that that's an area where there's
19:33 : still work to be done to really optimize
19:36 : the file size because currently it's
19:38 : definitely not optimal yet but anyway so
19:44 : you can think of this as basically a
19:46 : JSON format more or less with the
19:49 : additional addition of this ref thing
19:53 : and in a history file is got a number of
19:59 : entries so it's an array right the
20:02 : top-level object of the history file is
20:05 : an array and it's item in the array is a
20:09 : a snapshot basically so this object is a
20:15 : snapshot this object is a snapshot etc
20:18 : and what what is in the snapshot a
20:21 : snapshot has a line number so that trust
20:28 : banks to the line within the source code
20:31 : so so in other words this guy here it's
20:41 : it's a snapshot taken line two and and
20:55 : this guy is the stack the state of the
20:59 : stack at that point state
21:07 : it's the state of that stack at that
21:10 : point and as of I should say of the
21:13 : stack frame and the stack frame is can
21:18 : have any number of stacks and this one
21:20 : just has one so this this guy here this
21:27 : is the only only frame in fact it's it's
21:32 : the main frame of the stack and it tells
21:40 : you the parameters that the it has the
21:43 : function name the the function call that
21:47 : initiated this stack and it has the
21:51 : parameters that were passed in but this
21:53 : guy is is def the parameters is there
21:57 : are no parameters so this is an empty
22:00 : object so this is an empty object and
22:03 : this and one just defines the empty
22:07 : object as the ID one and variables is
22:10 : pointing to the same empty object so
22:13 : there's no variables at present either
22:16 : so I mean that's that's an example of
22:20 : structural sharing it's just sharing a
22:22 : very small object so it's not buying you
22:24 : very much in this case but it is there
22:28 : when the objects become larger then
22:31 : structure of sharing saves much more
22:33 : space okay so this is basically the
22:37 : first snapshot and then there's the
22:39 : second snapshot and the third snapshot
22:41 : and so forth and we can sort of follow
22:45 : the chain of events just by looking at
22:50 : this file actually you know the debugger
22:53 : helps you do that a lot easier because
22:55 : there's a graphical user interface but
22:58 : you can actually follow it just by
23:01 : looking through this file so we went
23:04 : from line two to line three and when we
23:08 : execute that line two with which one was
23:11 : this oh look at the while loop so when
23:17 : we execute line - we should have created
23:20 : variable called count and put the value
23:22 : one in there right which is exactly what
23:25 : happened we in in the next snapshot
23:28 : inside the stack frame we in the
23:31 : variables section we now have a count
23:34 : entry and whose value is one and then
23:39 : but the next step after that this is
23:43 : very small why is this very small well
23:47 : let's look at this line this line is a
23:49 : is the top of a while loop statement and
23:53 : it actually doesn't make any
23:54 : modification to the state of the program
23:58 : so if we take a snapshot at this line
24:02 : then the the stack frame should be
24:07 : identical to the stack frame in the
24:09 : previous step which is why we don't redo
24:14 : the the file doesn't re-create this part
24:21 : it merely makes a reference to the
24:24 : previous version of the stack so there's
24:28 : no need to we yeah
24:31 : redo this restate this stack frame and
24:37 : the same thing happened with the next
24:39 : line as well because the next line was a
24:41 : print statement which didn't modify the
24:45 : state
24:45 : there's something about side effects
24:48 : that I am planning to do but I haven't
24:51 : done that yet so I'm not gonna talk
24:53 : anything about side effects such as
24:55 : print are and perhaps network requests
24:59 : and stuff like that I have not done
25:01 : anything to handle that yet and so forth
25:05 : and then online for the variable count
25:09 : has been updated to two and you can see
25:12 : that that happens because we had this
25:14 : assignment statement to the count
25:17 : variable again and so forth so so this
25:21 : is how this works um that time-traveling
25:25 : debugger basically works by doing a six
25:28 : or TIF
25:30 : capture of all the states of the entire
25:33 : program and um and if you were watching
25:39 : this I bet you might be thinking that
25:43 : seems like a lot of overhead a ton of
25:48 : overhead is this approach even viable at
25:53 : all and my answer to that is I'm not
25:57 : sure but I am i think the the
26:03 : opportunity for for like the benefit of
26:07 : having something like a time-traveling
26:11 : debugger is so great that I'm willing to
26:13 : try and also with this history file and
26:20 : with all the previous snapshots of the
26:23 : program state there are more things you
26:27 : can do beyond simply implementing a
26:30 : time-traveling debugger and so such as
26:34 : you could answer questions about the
26:37 : program when you're such as like if
26:42 : you're looking at a piece of source code
26:44 : of function or what have you a lot of
26:47 : times like a lot of the time of a
26:50 : programmers workday I would say it's
26:54 : bent on trying to reconstruct how a
26:59 : piece of code works a lot of times if
27:02 : you're looking at code that was written
27:05 : by someone else but even if you're
27:07 : looking at code that was written by
27:09 : yourself chances are you don't remember
27:12 : how you put it together like all that
27:17 : information has been forgotten and you
27:20 : sort of have to reconstruct that and if
27:24 : you have this history of the execution
27:28 : of the entire program you can actually
27:31 : use it to answer questions such as well
27:37 : the code ever go into this branch or or
27:41 : if you had a function
27:43 : say this one you can ask and answer a
27:46 : question such as like was this function
27:50 : ever called with this parameter or yeah
27:54 : or how many times did the function - did
27:58 : the program enter this line all these
28:01 : questions are something you can answer
28:04 : and you can have a program answer that
28:09 : simply by it looking through all the
28:13 : snapshots within the history file and I
28:15 : think that's a very very powerful thing
28:17 : in terms of how can we make this
28:21 : approach performin
28:24 : enough for real world use that's very
28:28 : very much a research question and and
28:32 : I'm kind of hoping that the magic of
28:35 : immutable data structures can can allow
28:40 : us to solve that problem yeah
28:44 : so that's I'm gonna stop here because I
28:47 : feel like I've graham I've been rambling
28:50 : for long enough I I definitely have I
28:54 : definitely will give more progress
28:56 : updates about this in the future so if
29:00 : you're interested in that please stay
29:03 : tuned to this channel or as they say as
29:07 : the youtubers like to say hit subscribe

Time Traveling Debugger - Part 1

Transcript