00:03 this is a pretty brief part i believe
00:08 an update from where we left off in the last part this is to implement
00:13 the uh evaluator of the virtual machine
00:21 so we got this factorial function here and what i've done is like i've added a
00:26 reference implementation just to make sure that things works
00:31 in just c and then down here where we were running
00:34 our program yesterday
00:39 i've added a printout from running the uh the reference
00:43 implementation which you know my compiler will produce code for with
00:47 these same inputs and then we just do what we did yesterday
00:53 and so i found a bug yesterday i was running
01:01 this and i got into infinite loop so this is
01:05 the output from uh from running the program so i just
01:09 got into infinitely but i was like what is going on did i get this wrong since i just kind of dried code this so to speak
01:16 right i didn't actually know if this was um this was the correct implementation and i was like how do i even try this
01:23 so i tossed this together looked at the code that was generated from uh
01:30 by my compiler which looked sort of like this lifted over show some debugging from yesterday so this is kind of what my compiler would generate for for the c function
01:43 um and then i just step through it in my head like what would happen right if you
01:49 know i gave it an input of three and i was like what the hell this is you know this is what i'm doing here what's what's going on um and it turned out
01:58 that down here i just had a typo it's had a zero there
02:03 uh where it would subtract from reduced to zero instead of raised to one um so this this was still correct but this
02:10 this was not um oh yeah so once he has to fix the little
02:16 mistake it actually worked and uh the evaluators this first up this
02:21 is just a little function used to development utility
02:25 this is the thing that prints out these numbers if we just remove this and run it you'll see that there's no output but the result from the computation is still correct okay so
02:35 this is just this sort of printout so this is helpful
02:39 to debug what this shows is the state of the first six registers
02:43 um before an instruction so when we start
02:48 this program to do
02:53 down here right we set up our registers and we set up the first register which is the first argument to the number three so that's what we're seeing here is zero it's number three the rest of the zero which is should probably just
03:04 do this just to make that expected so this this means
03:09 that the compiler will zero all of these values of this array rather than in this case it's sort of like yolo you might get some random
03:16 bytes and for debugging purposes actually it might just be why is that oh no that's not going to
03:29 work of course serious special so we get mem set or something like that
03:33 might actually be so let's set it to the size of
03:45 the array so now these are all gonna be huge values so that's gonna be a problem but
03:51 uh oh yeah my proof function does not handle that okay let's just undo what i was was doing here and do
03:57 let's zero them out for now uh get sidetracked okay so this is the state of the registers
04:06 and then this is just a printout of the instruction that we're running
04:10 so calling this format function that we've already written it's in this
04:18 this this little chunk of code used to be us in here is broke that out to a separate function so that we can print just instruction by instruction instead of a whole program
04:28 and that is prints it out and then we see so state of registers before the instruction the instructions we run
04:35 and then here subsequently we have the state of the registers after the instructions is executed right and then we have next instruction and so on so we
04:45 see that we're copying the value of zero this is zero into resistor one
04:51 and yes we have now three here in both places and the next thing we do is that we load
04:59 the constant one into zero and now yes wrist zero has one
05:04 uh the next swing with you uh we will conditionally do a jump here if register one
05:12 is zero but it is not so this does nothing this just continues
05:16 so we just continue here uh the next thing we multiply or is it
05:21 zero at resistor one and zero and store that in raise to zero um
05:28 and since multiplying one by three is the same there is uh there's really no
05:32 difference here but indeed it did change the registers at least theoretically
05:39 next thing we just subtract one from register the value under this one
05:43 and then we store that to register one this is where i had a bug where i had registered zero over here um
05:49 and uh so now that we've subtracted let's see
05:57 yeah so we've multiplied one by three right so that meant we just get three
06:01 essentially a copy and then after we've subtracted one we
06:05 have two here now and uh um
06:11 register one here in our implementation let me let me scroll that up here little function
06:17 um whereas the one is our accumulator that
06:20 is the that is the uh starts with input argument and we're going to keep subtracting that until it's zero and then we're done the function is down when n is zero and we just subtract about one for every loop
06:33 so that's what what this one is doing here and then we we this is the the final like instruction
06:40 here in the program then we check if
06:44 um the value in register one
06:49 is not zero and if it is we do a jump and in this
06:54 case release one is not zero so this will do a jump and we do a jump three
06:58 instructions back so they just means if we look at the the
07:02 implementation of this here so here we have this instruction right
07:05 so if the value of the register uh the register that we're naming
07:13 is not zero then you just alter the program counter by this value so minus three
07:19 and that means that once we get down here right and we're gonna rewind the
07:23 programming counter three that means that we're gonna keep go back and execute this one more time and that's what happens so we see here
07:33 that that these instructions here oops are repeated three times right so it happens here again and it tests as there is the one zero no it's not and it jumps back and
07:43 it does this one more time and then it says is redistribu is released one is
07:47 that zero and yes it is and the function is complete and we return and the return value we've
07:53 uh we've multiplied since this is a zero so
07:58 this is the result of the factorial function um so up here doesn't help there the the correct value we initialize it here
08:07 uh and yeah i guess for input three yeah so if
08:21 argument zero is three i guess that's how we can think about it
08:27 when when this is three like we we were you know going up like this anyhow i shouldn't yeah that's weird uh there's a better way to expand on us but um yeah so that's that it works uh and it's
08:38 you know it's a reasonably compact and
08:43 unpleasant sort of the buying experience and he got to um i got to scratch my head a little bit about about that yesterday
08:51 uh so so that's it for this update i just want to show you that it works again you know all of this code is on getup if it hasn't occurred to you yet
08:58 um you could follow along with us if you wanted to you can you know grab a copy
09:05 of the code and you can sort of uh tinker along here or you just do your
09:09 own kind of thing and check in sometimes or you know just just watch it for the fun of it uh what i'm gonna do next is uh probably a little as a smd parser to be
09:22 able to write this kind of code instead of this um and and probably during that point uh
09:34 adding more instructions will be something that will do so right now the the instruction the set
09:41 of instructions here is is very small right and actually some of these are not being used they should be tested not that they're very
09:51 complicated i mean this is the entire implementation of the virtual machine right now it's very small and this is what we looked at if you're curious how we got to this look at um uh part number four
10:04 of this series uh one thing though one thing i should mention that we talked about in part number four i talked about part number four was uh the the tail call
10:14 table approach that we were trying out so we were trying three approaches we were trying out um a switch statement which
10:21 we ended up using a label jump table approach which turns
10:26 out to essentially be slightly worse code or
10:30 roughly the same code a switch statement for um for more effort and then the third
10:37 approach we tried was to use um functions with with tail call optimization taking so a csp style thing
10:44 and we noticed when we um ran that through the compiler to to ask it to
10:48 give us what the the assembly would be for the target machine the x86 in this case it inserted a lot of uh stack
10:57 manipulation code uh and the prologue and epilogue of each of these functions
11:01 which sort of has a uh
11:05 makes it messy would you know eventually when performance get becomes you know
11:11 a concern it might be a challenge anyhow it just didn't feel right and i was i was looking that up a little bit and doing some research about that
11:19 and those things i guess it would be nice if
11:22 i had a copy of that so i can show you what it was but essentially you can you
11:27 can go back and look at par 4 if you want to have a look at the specifics but
11:32 essentially at the the beginning of each function it would do something like
11:36 uh push first push the uh the stack pointer
11:43 to maybe the stack base pointer i can remember it's called x86 and then it would like you know it would increase the stack pointer actually it's like the frame pointer so that's the point right so it would store the frame pointer at the current stack pointer it will like increment like the stack pointer
11:59 and then you know we have the actual code and then it would be do the opposite so it would restore the frame
12:04 pointer from um so it would sort of um decrement the everyday stack pointer
12:15 um and it turns out that if you call if you what is that f omits
12:23 um frame pointer
12:29 maybe paint pointer so you can give this both gcc incline
12:35 accepts this then it won't generate this unless it it you know unless the function actually uses the stack
12:41 um and this the frame pointer is used for debugging
12:50 um it allows you and in in some languages like c plus plus that has stack unwinding and stuff like that it's i think it's also used for that at least i know it is on windows um and so you know you could you could set this
13:02 and the code generator would be much leaner actually like it would be equivalent to the code of a roughly equivalent code of the switch statement which is super cool with with tail calls
13:11 but uh as as far as i understand that this is a
13:20 entire object or nothing deal so you wouldn't have to enable this for an entire source file uh so there's a
13:27 little bit of uh ergonomic cost there to uh to doing that but i thought it just mentioned that that there is there is a way to get rid of that stuff that we saw
13:36 um so yeah cool that's it uh
13:43 oh yeah one one more thing i've started just doing a little thinking around uh how constants could
13:51 be represented in the actual program it's a little tricky since the
13:56 the instruction coding that we have looks like this um has a fixed size
14:03 and the the address space is you know
14:08 large even a 32-bit machine it would be much larger than even the biggest possible slot which is 24 bits
14:15 and in the case of like loading a constant we we really have just 19 bits
14:19 to deal with since we need a target register number and 19 bits doesn't give us much it gives us about 500 kilobytes of uh addressable
14:32 space if we adjust things and bites um so that that is a challenge
14:39 since you you might want to have more than 500 kilobytes of constants
14:44 imagine that you would embed i don't know a little um a little database
14:51 some images or something like that you might scratch up on against us 500k um
14:57 so you started doing a little bit of thinking this file is in the source
15:01 repository if you want to have a look at it as opposed to the the twitter thread
15:05 which is linked in the in the videos and on the if you're watching this on the webpage at the top of the webpage
15:14 yeah it's it's an interesting it's a really interesting problem
15:19 how to how to squish these together i was thinking about at least three different things i think that there's a there's a fourth here now um so one is just to say you know that's just the limit of this thing i mean it
15:32 is um it is not i'm not hoping to use this for any industry
15:38 strength like huge things you know i'm gonna use this for for smaller programs
15:42 so this could be okay um and for large images and stuff you might be able to sort of just load those
15:48 from a separate file could use some sort of fancy compression
15:56 i tried i tried just playing with some of them in my head yesterday but i don't know it's uh i don't think that there's a there it's just like weird uh trade-offs
16:09 there might be so this option is a possibility like to instead of using the
16:13 um the target register right where you say
16:17 you know load a constant into register whatever could you say load a constant at address
16:24 and then 24 bits is probably enough it'll give us two megabytes
16:28 16 megabytes of addressable space which is probably gonna be enough um but then the reducer must be implicit
16:36 right and then we have to dedicate a register that like you know
16:42 now there there will be implicit um sort of effects or side effects that might not be apparent right so so far
16:47 all of our instructions uh i name a register so they never
16:51 clubber um that's i know that's a weird that's a weird name it's um clubber essentially
17:00 it doesn't taint or overwrite any registers unless you explicitly mention them which is kind of nice so if you look at the um a little program like like that we
17:09 have here uh you will know that like a register that's on the left side here is going to
17:17 be uh or or depends on this one but like you know this is the only one that will be affected if any of the registers right so that's kind of a nice property you can look at this you know what traditions are going to be uh clobbered
17:29 aka sort of you know smashed or edited
17:33 and adding something like an implicit register would remove that and now you
17:37 have to be like you know you have to you have to watch for these little kind of you know
17:47 tricky things i was gonna i was gonna so yeah that's a possibility that also
17:57 has a trick trade-off the fourth one is to use a table like a lookup
18:02 table address constants
18:10 by uh index so could look something like this where
18:14 there is a you know here's like all the the constant data so there will be you know this just compact as possible you
18:21 know shanka shankar data
18:25 and then there is essentially is a level of interaction in between i guess like all problems in computer science can be solved by a level of indirection
18:33 where each constant in a function or a program
18:39 has like just an entry in this table and i guess this would be you know eu
18:43 size or something like that doesn't really matter what this is uh this is just the you know the index into this table the opposite and then
18:53 now we have 500 500 000 constants like the count the
18:58 total number of them not the size of them uh which would be enough
19:03 i think at least for for the majority of cases where you could just say hey
19:09 each of these things has both an offset and a size component and the size might be imaginary but um that would be enough the challenge with that though is that
19:21 you know you'll you'll have again a left limit direction yeah fun fun fun challenge is
19:28 constants are not important to implement now so i got a punt on that but it was just something else they're thinking okay so uh
19:38 that's that's the end of this try try this out if you want to
19:41 and check back for the next part a little
19:45 later see ya