An Introduction to Imperative Programming

To develop an intuition for what happens during the execution of a program, it is helpful to write down an execution trace of the program. An execution trace lists the instructions in the order they are executed and shows the effect of each instruction. In imperative programming languages (like our assembly language here), the execution of a program consists of multiple (potentially infinitely many) steps. In every step one instruction is being executed. The effect of an instruction is either a change of the state of the machine (changing the contents of a register or a memory cell) or an external effect which is an interaction with the environment (printing to the console, reading from a file, etc.).

Let us reconsider the factorial program from the introduction and let us assume the first instruction is located at address 0x00400000. This is the typical address at which the operating system loads our MIPS programs. So the first couple of bytes in memory starting from this address contain our program which is indicated by this disassembly:

0x00400000: addiu $v0 $0 1
0x00400004: bgez  $0 2
0x00400008: mul   $v0 $v0 $a0
0x0040000c: addiu $a0 $a0 -1
0x00400010: bgtz  $a0 -3
0x00400014: jr    $ra

We write down an execution trace as a table. Each row is the snapshot of the state before executing an instruction. Each column shows one part of the state that is of interest. Note that the address of the instruction that is to be executed next is also part of the state. The following table shows the execution trace for our example program with a start state in which register $a0 contains the value 3 (of course it contains a bit string of 32 bits whose unsigned and signed interpretation is 3).

To determine the row in the trace, we need to know what effect the instruction at the current position has. To this end, Appendix A summarizes the effects of the MIPS instructions we are going to use.

At the beginning, the program counter contains address 0x00400000. The instruction at this address is addiu $v0 $0 1. This instruction adds the constant 1 to the contents of register $0 and puts the result into register $v0. (Of course, it also increases the program counter by 4.) Therefore, the next instruction to execute is located at address 0x00400004. This instruction, bgez $0 2, branches 2+1 instructions ahead if the content of register $0 equals 0, which it always does. In fact, this instruction is an unconditional jump that sets the program counter 3 instructions ahead and so on and so forth. We'll stop the execution trace for this example when reaching the jr $ra instruction that would return to the caller of this function. (More on functions later in Section 2.8).