Time Traveling Debugger

I continue demonstrating the time traveling debugger I built over my vacation. The debugger relies on a history file which contains snapshots of every state of the program’s execution. In this video I demonstrate how the debugger works with heap objects: arrays and dictionaries.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello there this is Toby welcome to part
00:02 : two of my my introduction to the time
00:08 : travelling debugger time-traveling
00:11 : debugger debugger yeah so welcome to
00:25 : part two of of the time traveling
00:30 : debugger which I've been working on and
00:34 : this time the main thing I want to show
00:36 : you is the how it works with objects in
00:42 : the heap so objects on the heap this
00:53 : works sheep what does it mean well for
00:55 : now I'm gonna hand wave over it but
00:59 : sheep the heap is a memory location
01:04 : similar to the stack frame so in in
01:10 : conventional programs we have this stack
01:15 : and heap both of them are a sort of
01:18 : these allocated memory areas and we
01:23 : separate them but in reality both of
01:26 : them live in memory somewhere the stack
01:29 : holds the stack frame which has a number
01:33 : of frames and the number of frames just
01:35 : sort grows and shrinks as the needs of
01:40 : the program arises that's the stack the
01:45 : heap is for storing data structures that
01:49 : will be referenced by the stack but they
01:53 : should not go away just because one
01:56 : frame gets destroyed so they're there
02:00 : for like longer left
02:01 : data structures so stores
02:04 : [Music]
02:07 : of data structures and which will at
02:16 : some point get referenced by the
02:18 : variables on the stack okay and in a
02:22 : present for the fun programming language
02:27 : which really in many design choices
02:29 : follows the design choices of JavaScript
02:32 : and this is no exception here in the fun
02:35 : programming language the only data
02:39 : structures that are stored in the heap
02:42 : I'll say date has structures stored in
02:51 : heap for fun fun meaning fun line those
02:59 : are arrays and dictionaries dictionaries
03:07 : also known as objects because in reality
03:11 : there are objects in JavaScript so don't
03:15 : only arrays and dictionaries belong into
03:17 : the heap and objects and strings being
03:21 : on to dispatch that's how things work
03:24 : for fun fun line okay so let me just
03:30 : show you one example program in action
03:33 : and then I will explain more so at this
03:38 : collect multiples program which will go
03:41 : through the numbers from 1 to 10 it will
03:44 : collect the multiples of 3 into this
03:48 : array which I called multiples so go
03:52 : ahead and run that program play ok and
04:00 : now I'm going to use the debugger on
04:05 : this program
04:09 : so now the moment I execute the first
04:13 : line and see that the value of multiple
04:18 : is actually in number one but it's not
04:22 : meant to represent a number of because
04:24 : is supposed to be our array but this one
04:27 : is actually an ID which references an
04:31 : object in the heap of the same ID so
04:35 : multiples equals 1 means multiples is an
04:38 : array which is visually the array in the
04:43 : heap with the ID 1 which at present is
04:46 : the empty array as is depicted here ok
04:51 : and then now I is 1 and for I that's
04:55 : actually a number now whether we should
04:59 : have some sort of visual indicator that
05:02 : this is an array or a number I think we
05:06 : definitely should have that but this is
05:08 : a very experimental stage of this
05:10 : debugger and at present I don't have
05:13 : anything to tell you whether this is an
05:16 : array or number ok anyway so well I is
05:20 : less than 10 which at present it is
05:23 : it'll do this if statement is it
05:25 : divisible by 3
05:27 : no you know at 1/2 I do it again now
05:31 : it's just visible by 3 it'll push I into
05:37 : multiples and now this array the array
05:41 : number 1 will get the number 3 in it and
05:45 : so forth and then I also get the number
05:47 : 6 in it and it also get the number 9 ok
05:54 : now I want to explain how I chose to use
05:57 : this ID scheme for objects in the heap
06:01 : by the way this is the case for both
06:04 : arrays and dictionaries as I mentioned
06:08 : actually before I explain I'm gonna run
06:10 : in one more example first which would be
06:13 : the word tell yeah that's from the word
06:17 : tally which goes to it counts works
06:21 : from this sentence to be or not to be
06:28 : this is my favorite programming exercise
06:32 : to give to my students one of the
06:35 : favorites okay
06:38 : so let's step through this line by line
06:41 : so first we instantiate sentence to be
06:45 : the string and then this split operation
06:48 : splits the string into an array of
06:51 : strings which is depicted here so this
06:56 : this array has the ID of one and its
07:00 : members are the these bits of strings
07:04 : that you can see here you can also see
07:07 : that the value of words has been set to
07:09 : one which is is a reference to the array
07:13 : number one here Itali is a dictionary
07:17 : and a dictionary is depicted like this
07:21 : currently it's an empty dictionary which
07:25 : is for some reason I chose to depict it
07:28 : like this and again the dictionary has
07:34 : an ID it's two and the variable tally
07:38 : simply contains the ID to this object
07:41 : here in the heap okay so now we're gonna
07:44 : loop through the words which again is
07:48 : array number one so we're looping
07:50 : through array number one and the first
07:52 : word in the array is two so right now
07:55 : word equates to two as we can see in the
07:58 : stack here and then it's basically
08:00 : checking hey is the word two in the
08:04 : tally which is dictionary number two and
08:07 : because it's not it goes into the else
08:11 : clause and it's gonna set the is Korean
08:14 : Korean new entry for the word two and
08:17 : set the value to one so now I have we
08:20 : have an entry in this dictionary is no
08:22 : longer in mp dictionary I move on to the
08:25 : next word or
08:28 : wait what happen to be
08:32 : oh there's B oh it went by too quickly -
08:38 : and then - and then beat okay there's B
08:41 : why did it go by so quickly
08:44 : okay B has won and then we go to or and
08:48 : or has won as well and then not has won
08:52 : as well
08:53 : now we'll get to to where we're actually
08:56 : gonna get a repeat here so because or is
09:00 : already in the dictionary number to
09:03 : tally this we're gonna add one to the
09:07 : existing number which should get us two
09:09 : so you can see two in the entry for -
09:15 : that's a mouthful okay so now and then B
09:20 : is gonna get another increment in the
09:24 : count as well and that that's ends the
09:27 : program here so that's what it looks
09:29 : like when you're working with arrays and
09:32 : dictionaries both of them data
09:34 : structures in the heap now I want to
09:37 : explain why I chose to use this ID
09:42 : scheme for the objects in the heap so
09:46 : the problem that I ran into as I was
09:50 : designing this thing is that okay let's
09:57 : say you had a function let's say you
10:00 : pass an array or dictionary into a
10:03 : function which I actually have an
10:05 : example of this or perhaps I modified
10:09 : this example to maybe I extract these
10:13 : three lines from this collecting
10:16 : multiples example and I make that into a
10:23 : sub procedure I'll say correct
10:28 : I'll say maybe
10:33 : tipo three and it gets the it gets
10:46 : passed in the array here and also the
10:51 : high so instead of ends up doing these
10:56 : three lines directly I'll actually pass
10:58 : in the eye and array and if I ran this
11:06 : it should do exactly the same thing I
11:08 : mean I mean double check that I did this
11:11 : correctly so now if I run the debugger
11:18 : on it so I have another frame in in the
11:26 : stack frame here and this the multiples
11:29 : within this frame is also pointing to
11:32 : one
11:33 : so both the multiples variable in Maine
11:36 : and the multiples variable in maybe
11:38 : collect multiple of three they're both
11:40 : pointing to the D array one and it also
11:46 : has an eye so it's testing I by the time
11:51 : we get to that I equal to 3 it'll go
11:54 : into this go into this if conditional
11:58 : and I'll push the number into the ring
12:01 : as it did here so this works perfectly
12:04 : as it did before
12:07 : and we should get 3 6 & 9 abate with
12:11 : more steps than before because we've had
12:15 : this function call to deal with but so
12:20 : in order to get all this work I had this
12:27 : problem of so if I have because I need
12:35 : to store um or historical states and
12:40 : using of the entire program using the
12:45 : immutable data
12:46 : structures scheme I can't actually be
12:51 : modifying data structures even when I'm
12:54 : modifying data structures so in other
12:56 : words this push operation here
12:59 : it cannot actually be modifying a data
13:02 : structure it this push can't mutate
13:11 : mutate the array in reality instead what
13:19 : it has to do is to create a new version
13:23 : disarray the problem is if I if I create
13:30 : a new version of the array I need to
13:33 : notify all of all references to that
13:38 : array that the version of the array has
13:41 : changed so and that is a problem when
13:44 : you and anytime you have multiple
13:47 : references to that same array so for
13:50 : example in in this case actually this
13:57 : already happens whenever I'll just go
14:02 : back I'll just go back to the first time
14:07 : it's gonna push a number yeah yeah when
14:09 : here happens we already have two
14:12 : references to the same array so so here
14:18 : we have this situation where we have two
14:20 : stack frames and yes we have this one
14:26 : here but without my numbering scheme
14:31 : then this would actually let's pretend
14:34 : this one was not here this would
14:36 : actually be a pointer to this array and
14:39 : this would be a pointer to this array as
14:42 : well and if we're gonna say we're doing
14:45 : this immutable sort of modification of
14:50 : the array which means I have to make a
14:54 : new version of this array with the 3 in
14:58 : it
14:59 : and I'm gonna make this multiples
15:02 : variable not point to the empty one but
15:07 : make it so like sort of erase this but
15:11 : make it point to the new one instead
15:15 : well that's not gonna work because I
15:17 : also have to modify the the outside
15:23 : reference to the same array because the
15:27 : main function is expecting the sub
15:30 : function to be mutating the same array
15:35 : that the main function is expecting to
15:37 : be able to access later so in reality
15:41 : this this scheme basically doesn't work
15:44 : because any time we modify this array we
15:49 : have to make sure and and which means
15:52 : creating a new version of the array we
15:55 : have to make sure all of the existing
15:56 : references to that array have to get
16:00 : updated to refer to the new version of
16:03 : the air right
16:05 : I thought of multiple ways of doing this
16:08 : and at the end I decided the simplest
16:11 : way although less performant way is to
16:16 : come up with these ideas came and this
16:20 : ID scheme allows us to sort it at a
16:27 : global level for the all of the
16:31 : variables within the entire stack and
16:33 : also in fact not just the stack but you
16:36 : can have a race of a race as well so if
16:42 : you have arrays of dictionaries or
16:45 : dictionaries over race the the members
16:49 : of the array is also IDs to other arrays
16:53 : so these are in fact IDs to other arrays
16:57 : if you choose to do an array of array
16:59 : approach and in those cases when you're
17:03 : mutating things things will continue to
17:06 : work as well so
17:09 : now I want to show you how the heap is
17:12 : represented inside a history file so
17:14 : this history file is for this collect
17:17 : multiples program you see that initially
17:21 : the heap is empty it's just represented
17:25 : by an empty object this and this object
17:28 : is supposed to be a dictionary that
17:30 : where its key is the object IDs and the
17:36 : value is the actual object so when we
17:41 : execute at line number two which is this
17:45 : line and instantiate in an empty array
17:48 : what happened is we created a new object
17:52 : in the heap and give you an ID of 1 and
17:55 : the value of the object is as you can
17:58 : see an empty array and then the
18:02 : multiples variable in the stack has the
18:05 : value of 1 which is basically an ID that
18:10 : points to this entry in the heap so
18:13 : that's how it works and anytime an
18:16 : object inside the heap has to change
18:19 : basically the value in the entry gets
18:23 : changed however that doesn't affect the
18:27 : previous version like the historical
18:30 : version of the heap because this this
18:32 : version of the heap this state of the
18:34 : heap has an empty array and nothing will
18:37 : change that so when when the heap
18:39 : actually changes as was the case
18:50 : did he actually change yeah yeah so here
18:55 : this would this happen after line 12
18:59 : which was yeah that makes sense because
19:02 : after line 12 nine twelve is the line
19:05 : that pushes a number into this array
19:10 : here
19:10 : so after line 12 we see that the array
19:17 : number one in the heap has a 3 in it now
19:20 : and and that's how the heap changes
19:24 : because but but the fact that the state
19:28 : of the heap has has a non empty array in
19:35 : it here doesn't change that the previous
19:37 : say of the heap was an empty array and
19:41 : then also because the references to the
19:46 : objects in the heap are simply numbers
19:50 : the references don't they're sort of
19:53 : decoupled from the actual content of the
19:56 : heap and and the heap heap lookup is
20:00 : done at runtime so whenever the program
20:02 : actually tries to get at the actual
20:06 : array it just uses this ID to look up
20:09 : this heap and and everything just works
20:13 : out like that we can look at another
20:16 : example we're gonna get the or tally
20:18 : example so weird how he has a history
20:21 : file and you can see that the sheep see
20:29 : at the beginning the heap is empty and
20:32 : then here the heap has an array this is
20:37 : the result of splitting the sentence
20:39 : into words so so the this is the words
20:44 : array ID 1 and that points to this array
20:48 : with with other words in it
20:50 : and then we're going to loop through and
20:52 : here we generated a tally variable which
20:56 : is a dictionary which is planning to
20:59 : heap object number two which is here and
21:03 : there's
21:03 : initially that's the empty dictionary
21:05 : but over time this differently gets
21:10 : entries in it as we loop through the
21:13 : words etc etc and this dictionary builds
21:17 : up but the fact that this dictionary
21:19 : gets new entries over time is that
21:26 : doesn't doesn't sort of work because
21:28 : we're not militating anything we still
21:30 : get to retain the previous states of the
21:33 : history in this history file and and
21:37 : yeah and that's what I was mostly after
21:40 : so that's how the scheme works so
21:44 : although this way seems like indirect
21:47 : and also it's less performant I chose
21:49 : this way because it solves a whole lot
21:52 : of problems and the performance penalty
21:56 : hit is something that I'm thinking about
21:59 : and I think it can be mitigated in the
22:02 : case when we have pure functions as in
22:05 : fewer functions don't need this because
22:08 : fewer functions are not going to notate
22:11 : anything and so we can do an
22:15 : optimization there to not have to do
22:17 : this ID scheme in the case of pure
22:20 : functions and Empire also perhaps I feel
22:25 : like this ID scheme although there is a
22:28 : penalty hid involved maybe it's not so
22:34 : much it's it's kind of it's just an
22:36 : extra lookup it's not so much that it'll
22:39 : be prohibitive for real-world tasks
22:43 : perhaps and I guess only time will tell
22:46 : about that one okay so so that's how
22:51 : things work and I think in
22:55 : and perhaps another video I will
22:58 : actually show more of the internals of
23:01 : how the the history file and the
23:05 : snapshots within it are actually
23:07 : generated and yeah if you're interested
23:10 : in seeing more then then stay tuned

Time Traveling Debugger - Part 2

Transcript