Code along video
Learning objectives
In the previous code along, we wrote a multiplication function in X-Toy and saw what it literally means for a function to return. Now it is time to build something real. In this code along, we return to where the course began, with the problem of finding the greatest common divisor (GCD) of two integers, and we implement the trivial GCD algorithm in X-Toy. Along the way, we will see that the same programming principles that we have relied on since the start of the course (a main function, modularity, top-down design, and agreeing on a function’s inputs and outputs) apply even at the level of assembly language. We will write the main program and the TrivialGCD function, deferring the two subroutines that it calls to the next code along.
Code along summary
Setup
We continue in Visual X-TOY from the previous code alongs; there is nothing new to install. Create a new file called trivial_gcd.toy. As before, a program starts at address 10, a word beginning with 0 halts, reading from address FF reads from standard input, and writing to FF prints to standard output.
The trivial GCD algorithm
We call this approach “trivial”, which sounds a little mean, but it just means that it is the first idea that we might come up with if we were solving the problem by hand. We set m equal to the minimum of the two input integers a and b, and then we range an integer p from 1 to m. Every time that we find a p that is a divisor of both a and b, we update our current divisor d to be p. When the loop ends, d is the largest common divisor that we found. Here is the pseudocode, which we place at the top of our file as a comment.
TrivialGCD(a, b)
d = 1
m = Min2(a, b)
for every integer p between 1 and m
if p is a divisor of both a and b
d = p
return d
Writing main
With any program, a natural place to start is writing a main. Visual X-TOY highlights the keyword function, so we label our code function main, in the same way that in Python we write def main(). We think of the code that we are running as a function, and we describe what it does in a comment: read two numbers from standard input, compute their GCD, and write it to standard output. Main always starts at the special memory address 10.
The first thing that we do is read two integers from the user. The instructions 81FF and 82FF read a value from address FF (standard input) into registers R[1] and R[2], respectively. (Remember that there is also a register R[0], which always stores the value zero, because we need the value zero so often that it is a permanent constant.)
The last thing that we want to do is accidentally overwrite one of our two input numbers. So, as a bookkeeping measure, we store a and b into memory addresses that we know we will never change: 9101 stores a in M[01], and 9202 stores b in M[02]. We might overwrite registers, but these two values are now safe. This is a nice consequence of starting programs at 10: any variables that we want to keep around for a while can live at 01, 02, and so on.
Next, we call a function with jump and link, which we learned in the previous code along. The second hex digit says which register stores the bookmark of where to jump back to; we use R[F]. The last two digits say where to jump, and we decide that the TrivialGCD function will start at address 20. So the call is FF20.
If we make it to the next line, the function has finished, and one of the registers presumably stores the GCD that we care about. We need to agree on which one, and we need to remember this agreement when we write the function. There is nothing special about register 6, but that is the one that we choose. So 96FF prints R[6] to the console, and 0000 halts, which is normal behavior for the end of a program.
function main // read two numbers from stdin // compute their GCD, and write to stdout 10: 81FF read R[1] 11: 82FF read R[2] 12: 9101 M[01] <- R[1] // stores a in M[01] 13: 9202 M[02] <- R[2] // stores b in M[02] 14: FF20 R[F] <- PC; goto 20 // call TrivialGCD(a, b) 15: 96FF write R[6] // prints our value 16: 0000 halt // end of program
All that main does is read two values, call a function, print the result, and halt. We have seen this pattern since the start of the course in Python; we are just seeing it reflected in a much lower-level language. The language itself does not really matter, and good programming principles still apply.
Top-down design and the function header
One of those principles is modularity, and with it, top-down design. We will need a function Min2 that takes the minimum of two integers, and that function is probably easier to write. But that is not where we want to start. We want to start with the function that we care about the most, TrivialGCD.
X-Toy does not have function signatures with type hints, so we need to be nice to whoever uses our function and specify its inputs and outputs in a comment. When we called the function from main, R[1] and R[2] stored a and b. The output is the register that we agreed on, R[6]. The return address is R[F], the bookmark that the call left for us. Finally, we list the temp variables: the registers that the function will modify along the way. (Working these out in advance takes some planning; here we just state them.)
function TrivialGCD // Input: R1 = a, R2 = b // Output: R6 = GCD(a, b) // Return address: RF // Temp variables: R4, R5, R6, R7, R8, R9
STOP: Why should we specify a function’s temp variables before we even write any code? Why would it be mean not to?
The temp variables tell the caller which registers are going to be overwritten. If register 5 was storing some value that the caller cared about when it called this function, then the comment is a warning: register 5 will get overwritten, so before calling the function, you need to save that value somewhere in RAM. This is good practice in our make-believe assembly language, and it is still very relevant in real ones.
Setting up the loop
Let us now write the function itself, following the pseudocode line by line. We first set d equal to 1, and since R[6] is what will store the GCD, we write 7601.
Next, we call the Min2 function. We decide that Min2 will live at address 50. We cannot use R[F] for its bookmark, since R[F] is already holding our own return address; we could save it in memory, but that gets tricky. It is much better to use one of our temp variables, so F750 jumps to 50 and stores the bookmark in R[7]. We also agree that Min2 places its output in R[4]. Once we know the minimum, it is good practice to snapshot it into memory: 9403 stores R[4] into M[03], so that memory now contains a, b, and the minimum of a and b.
Now for the loop, in which we range p from 1 to m. We store p in R[5] and set it to 1 with 7501. Every time through the loop, we will need to add 1 to p, and X-Toy has no “add 1” instruction, so we keep a constant: 7801 sets R[8] to 1, and we note that R[8] must never change.
20: 7601 R[6] <- 0001 // d = 1; R6 will store the GCD 21: F750 R[7] <- PC; goto 50 // call Min2(a, b), result in R4 22: 9403 M[03] <- R[4] // snapshot m = min(a, b) in M[03] 23: 7501 R[5] <- 0001 // p = 1 24: 7801 R[8] <- 0001 // R8 is a constant equal to 1
How do we know when the loop is over? A for loop sets p to 1, executes the block, adds 1 to p, and keeps going until p becomes m + 1. At one point in everybody’s programming journey, that is a complicated idea; now we are just seeing it one level lower. The loop is over when p > m, and we need to be a little clever here: p > m means that p - m > 0, and we have a control instruction that checks whether a register is positive. So 2954 sets R[9] to R[5] - R[4], which is p - m, and then branch positive (opcode D) jumps over the loop if R[9] is positive.
But where should we jump? It is not at all clear yet, and if we just entered the right address, it would seem mystifying. So we leave the address as ?? and come back to it once we know.
25: 2954 R[9] <- R[5] - R[4] // R9 = p - m 26: D9?? if (R[9] > 0) goto ?? // jump over the loop if p > m
Checking divisors with a function call
If we did not jump, then at address 27 we are inside the loop, and we need to check whether p is a divisor of both a and b. We cannot check both at the same time, so we check a first, and if p survives that check, we check b.
To check a, we first write 1150. Technically, this sets R[1] equal to R[5] + R[0], but R[0] is always zero, so this is a clever trick for copying one register into another: R[1] now holds p. Our instruction formats do not include a “copy” operation, but our building blocks can construct more operations than might first appear. Then 8201 loads a back from M[01] into R[2]. (We overwrote R[1], which used to store a, but that is fine, since we can grab a from memory whenever we like.)
We could write the divisor check right here, but we are going to need it again for b, so it makes much more sense to write a function IsDivisor that we will place at address 40. Its return address will be R[7]: we already used R[7] for the call to Min2, but we do not need that bookmark anymore. And we agree that IsDivisor returns 1 in R[3] if p divides a, and 0 otherwise. The call is F740. We do not need to worry yet about how to write IsDivisor; we are structuring our procrastination, assuming that the subroutine will give us what we care about.
Once the function returns, if R[3] is zero, then p cannot be a divisor of both a and b, because it is not a divisor of a. So at 2A, branch zero (opcode C) will jump to the “no” part of the loop, wherever that turns out to be. If we did not jump, p divides a, and we check b with exactly the same structure: 1150 sets R[1] to p, 8202 loads b into R[2], F740 calls IsDivisor again (reusing R[7] for the bookmark), and 2E jumps to the same “no” part if R[3] is zero.
// we are now in the loop; first, check if p is a divisor of a 27: 1150 R[1] <- R[5] // R1 = R5 + R0 = p 28: 8201 R[2] <- M[01] // R2 = a 29: F740 R[7] <- PC; goto 40 // call IsDivisor(p, a), result in R3 2A: C3?? if (R[3] == 0) goto ?? // not a divisor of a: jump to "no" part // p is a divisor of a; now check if p is a divisor of b 2B: 1150 R[1] <- R[5] // R1 = p 2C: 8202 R[2] <- M[02] // R2 = b 2D: F740 R[7] <- PC; goto 40 // call IsDivisor(p, b) 2E: C3?? if (R[3] == 0) goto ?? // not a divisor of b: jump to "no" part
STOP: If we make it to address2Fwithout jumping, what can we conclude?
Updating d and closing the loop
If we reach 2F, then we did not jump at 2A, so p divides a, and we did not jump at 2E, so p divides b. It is a divisor of both, and the pseudocode tells us to set d equal to p. Using the same copying trick, 1650 sets R[6] (which is d) equal to R[5] (which is p).
Now we know what the “no” part of the loop should be: it is the very next address, 30, so both C3?? lines become C330. Address 30 is reached in two ways: when p is not a divisor of a or b, and after we set d equal to p. In either case, we take the same action: add 1 to p and restart the loop. Because R[8] is always 1 (and IsDivisor must not overwrite it), 1558 sets R[5] to p + 1.
Then we want to jump back to address 25, where we subtract m from p and perform our check again. But jump register (E) jumps to an address stored in a register, so here is another little trick: branch zero on R[0]. Register 0 is always zero, so C025 always jumps to 25, and Visual X-TOY’s pseudocode for it is just “goto 25”.
If we make it to address 32, the only way that we could be there is if we jumped from somewhere, and we only jump here when the loop is done. So we can finally fill in the jump at 26: it should be D932, which jumps to 32 when p - m is positive, that is, when p is greater than m.
At the end of the loop, 9504 stores the final value of p into M[04]. Looking at it again, this line is not really necessary. The line that is very necessary is EF00, which jumps to the value of R[F] when the function is finished.
Why jump to R[F]? This is what we mean by returning. When we worked with Python, we thought of a function as returning a value; in X-Toy, a function also returns to the bookmark that it was given, which was stored in R[F]. And the value that we want is in R[6], which holds the last value of p for which we set d equal to p. Here is the complete TrivialGCD function.
function TrivialGCD // Input: R1 = a, R2 = b // Output: R6 = GCD(a, b) // Return address: RF // Temp variables: R4, R5, R6, R7, R8, R9 20: 7601 R[6] <- 0001 // d = 1; R6 will store the GCD 21: F750 R[7] <- PC; goto 50 // call Min2(a, b), result in R4 22: 9403 M[03] <- R[4] // snapshot m = min(a, b) in M[03] 23: 7501 R[5] <- 0001 // p = 1 24: 7801 R[8] <- 0001 // R8 is a constant equal to 1 // loop: is p > m? (p - m > 0) 25: 2954 R[9] <- R[5] - R[4] // R9 = p - m 26: D932 if (R[9] > 0) goto 32 // jump over the loop if p > m // we are now in the loop; first, check if p is a divisor of a 27: 1150 R[1] <- R[5] // R1 = R5 + R0 = p 28: 8201 R[2] <- M[01] // R2 = a 29: F740 R[7] <- PC; goto 40 // call IsDivisor(p, a), result in R3 2A: C330 if (R[3] == 0) goto 30 // not a divisor of a: jump to "no" part // p is a divisor of a; now check if p is a divisor of b 2B: 1150 R[1] <- R[5] // R1 = p 2C: 8202 R[2] <- M[02] // R2 = b 2D: F740 R[7] <- PC; goto 40 // call IsDivisor(p, b) 2E: C330 if (R[3] == 0) goto 30 // not a divisor of b: jump to "no" part // p is a divisor of both a and b 2F: 1650 R[6] <- R[5] // d = p // "no" part of the loop (and the part after we set d = p) 30: 1558 R[5] <- R[5] + R[8] // p = p + 1 31: C025 goto 25 // restart loop // the only way to get here is to jump over the loop 32: 9504 M[04] <- R[5] // snapshot final p in M[04] 33: EF00 goto R[F] // function is done; R6 stores our GCD
That is the hardest function that we are going to write. It cannot run yet, because it calls two subroutines that do not exist, but we have notes on both: Min2 goes at address 50, takes R[1] and R[2], returns its output in R[4], and returns to R[7]; and IsDivisor goes at address 40, returns its output in R[3], and returns to R[7].
Check your work
Your TrivialGCD function cannot run until it has its two subroutines, so we will check it at the end of the next code along, with the autograded Trivial GCD exercise in Chapter 7’s Check Your Work on the Programming for Lovers platform. That exercise expects exactly the layout that we used here: main at 10 (reading a and b from standard input, printing one value, and halting at 16), TrivialGCD at 20, IsDivisor at 40, and Min2 at 50.
Looking ahead
In the next code along, we will write the two subroutines Min2 and IsDivisor, which are much shorter than TrivialGCD. Then we will run the whole program and watch the lights of Visual X-TOY flicker as it computes GCDs.
