This assignment is the first in a sequence of three. It is not strictly necessary to complete this one in order to do the other two, but the understanding you gain in completing this assignment will make writing the third assignment (a major project) much easier. You will need to complete the second in the sequence in order to do the third.

We start by "peeling open" a computer, look at its internal structure, and introducing machine language (assembler-level) programming. Your assignment is to write a program that simulates a computer, one that is capable of executing machine language programs.

1. Initial Setup

1. Log in to Unix.

2. Run the setup script for Assignment 4 by typing:

    setup 4 

2. Description of the Simplesim Computer

In this assignment you will write a program to simulate a fictional computer that we will call the Simplesim. As its name implies it is a simple machine. All information in the Simplesim is handled in terms of words. A word is a signed four-digit decimal (base 10) number such as +3364, -1293, +0007, -0001, 0000, etc. The Simplesim is equipped with memory and five registers.

• The Simplesim has a 100-word memory and these words are referenced by their location numbers 00, 01, . . . , 99. Each word in the Simplesim's memory (always a single signed four-digit decimal number) may be interpreted as an instruction to be executed, a data value, or may be uninitialized.

• The first register is the accumulator, which is just large enough to hold a single word. Words from memory must be placed into the accumulator in order to perform arithmetic on them or test their values. All arithmetic and branching is done using the accumulator.

• The second register is the instruction counter, which is just large enough to hold a memory location (a two digit number, 00, 01, ... , 99). The instruction counter is used to hold the memory location of the next instruction to be executed.

• The third register is the instruction register, which, like the accumulator, is just large enough to hold a single word. The instruction register is used to hold a copy of the instruction (a word that was pulled out of memory) that is currently being executed.

• The fourth and fifth registers are the operation code and operand, respectively. Each one is just large enough to hold half of a word (a two digit decimal number). The operation code and operand registers are used to "split" the instruction register in half, with the 2 leftmost digits and sign of the instruction register going into the operation code and the 2 rightmost digits going into the operand. For example, if the instruction register had +1009, the operation code would have +10 and the operand would have 09. Likewise, if the instruction register had -1201, the operation code would have -12 and the operand would have 01.

3. The Simplesim Machine Language (SML)

Each instruction written in the Simplesim Machine Language (SML) occupies one word of the Simplesim's memory (and hence instructions are signed four-digit decimal numbers). The two leftmost digits of each SML instruction are the operation code (opcode), which specifies the operation to be performed. The two rightmost digits of an SML instruction are the operand, which is the memory location containing the word to which the operation applies. The complete set of SML instructions is described in the table that follows.

Operation Code	Meaning
Input / Output Operations:
#define READ 11	Read a word into a specific memory location.
#define WRITE 12	Print a word from a specific memory location.
Store / Load Operations:
#define STORE 21	Store the word in the accumulator into a specific memory location.
#define LOAD 22	Load a word from a specific memory location into the accumulator.
Arithmetic Operations:
#define ADD 31	Add a word in a specific memory location to the word in the accumulator (leave result in accumulator).
#define SUBTRACT 32	Subtract a word in a specific memory location from the word in the accumulator (leave result in accumulator).
#define MULTIPLY 33	Multiply a word in a specific memory location by the word in the accumulator (leave result in accumulator).
#define DIVIDE 34	Divide a word in a specific memory location into the word in the accumulator (leave result in accumulator).
Transfer of Control Operations:
#define BRANCH 41	Branch to a specific memory location.
#define BRANCHZERO 42	Branch to a specific memory location if the accumulator is zero.
#define BRANCHNEG 43	Branch to a specific memory location if the accumulator is negative.
#define HALT 44	Halt, i.e., the program has completed its task.

We illustrate how the Simplesim executes SML programs (using the instructions from the table above) with the use of two example SML programs. Consider the following SML program which reads two numbers and computes and prints their sum.

Memory Location	Word	Instruction
00	+1107	(Read A)
01	+1108	(Read B)
02	+2207	(Load A)
03	+3108	(Add B)
04	+2109	(Store C)
05	+1209	(Write C)
06	+4400	(Halt)
07	+0000	(Variable A)
08	+0000	(Variable B)
09	+0000	(Result C)

Execution always begins at memory location 00. The word at memory location 00 (+1107) is read and interpreted as an instruction. The leftmost two digits of the word (11) represent the instruction and the rightmost two digits (07) represent the instruction's operand. The first instruction is a READ operation. This reads a single word from the input file (explained in Section 4) and stores it in the memory location defined by the operand, in this case memory location 07. READ and WRITE instructions always operate on memory locations. This completes the execution of the first instruction. Processing continues by executing the next instruction found at memory location 01.

The next instruction (+1108) reads a second word from the input file and stores it in memory location 08. The next instruction (+2207) is a LOAD operation with operand 07. It takes the word found at memory location 07 (the operand) and places it into the accumulator (recall that the accumulator is one of the five registers described in Section 1). All LOAD and STORE operations move data in and out of the accumulator.

The next instruction (+3108) is an ADD instruction with operand 08. All SML arithmetic instructions are performed using the word in the accumulator and the word identified by the operand and the result is always left in the accumulator. This instruction takes the word stored in memory location 08 (the operand), adds it to the value in the accumulator, and leaves the sum in the accumulator.

The next instruction (+2109) is a STORE instruction which, like all STORE instructions, takes the word in the accumulator (the sum of the two input values) and stores it in the memory location identified by the instruction's operand, in this case memory location 09. Then +1209, a WRITE instruction, prints (output is explained in Section 5) the word found in memory location 09, which - again - is the sum of the two input values. Finally instruction +4400, the HALT instruction, is executed which simply terminates the SML program (operand 00 is ignored for this instruction).

Note that a single word in memory can be used to store a single instruction that is to be executed or a single variable that should never be interpreted as an instruction. None of the memory locations after the HALT instruction (memory locations 07-09) were executed; however, they were important in the computation. Those words were used to store the program's variables and temporary results.

All SML programs will "partition" the Simplesim's memory in this way. The first words of memory (always starting at memory location 00) are the "instructions" of the program and following that, after the HALT instruction, is the "data" part of the program. The intention, of course, is that only the "instructions" of the program are to be executed, i.e., each word interpreted as an SML instruction.

Now consider this second SML program that reads two numbers and prints the larger of the two.

Memory Location	Word	Instruction
00	+1109	(Read A)
01	+1110	(Read B)
02	+2209	(Load A)
03	+3210	(Subtract B)
04	+4307	(Branch negative to 07)
05	+1209	(Write A)
06	+4400	(Halt)
07	+1210	(Write B)
08	+4400	(Halt)
09	+0000	(Variable A)
10	+0000	(Variable B)

The first two instructions (+1109 and +1110) read two values and store them in memory locations 09 and 10, respectively. +2209 places the word at memory location 09 (the first input value) into the accumulator. +3210, a SUBTRACT instruction, takes the word at memory location 10 (the second input value), subtracts it from the accumulator, and leaves the result in the accumulator.

+4307 (BRANCHNEG) is a conditional branch instruction, much like an "if" statement in C++. All conditional branch instructions are based on the accumulator. The BRANCH instruction, which acts like a "goto", is the only branch instruction that ignores the accumulator; it is simply an unconditional branch.

If the value in the accumulator is negative, which in this case means the second input value was the largest, then the next instruction that gets executed is the one at memory location 07 (the operand). If the value in the accumulator is 0 or greater, meaning the first input value was greater than or equal to the second, then execution continues with the next statement, i.e., no branching. If the branch was taken, then the value at memory location 10 (the second input value) is printed and the program terminates. Otherwise the value at memory location 09 (the first input value) is printed and the program terminates.

Note how the SML program is written. It "partitions" the Simplesim's memory into two distinct parts; the "program" (locations 00-08) and the "data" (locations 09-10). This SML program, unlike the first, has two HALT instructions. This is okay; only one of them will be executed. The point is that HALT instructions are used to prevent the execution of the program from wandering into the "data" portion of the program.

4. Input

Your program will take as input an SML program followed by any input for that SML program.

The input file will start with the SML program, one instruction per line. Following the last line of the SML program will be the number -99999, which is not part of the SML program. If the SML program expects any input (i.e., if it has any READ instructions) then input for the SML program, one input value per line, immediately follows the -99999 line. For example, below is the input file for the first program from the previous section. It adds -5 and 15.

1107 1108 2207 3108 2109 1209 4400 0000 0000 0000 -99999 -5 15