Exercise 5 Introduction to Computer Science, IDC Herzliya, Fall 2010

The exercise has three objectives: (i) Discover how computers work, (ii) Experience low level programming using a machine language, and (iii) Continue building your programming skills by writing a Java program that emulates the Vic computer.

General Guidelines:

         When writing Vic programs, the less commands, the better. You may start by writing a program that solves the problem and then try to make the code tighter.

         Write your Vic programs using a text editor like Notepad. You can then load and run them using the simulator in www.idc.ac.il/vic . If you write programs using Vic's symbolic language, you have to translate them to Vic's native code before running them. The translation can be done using a Vic assembler, also available in http://www.idc.ac.il/vic.

Vic Program 1 (5 points)

Write a program (signum) that reads a number and outputs as follows: if the number is less than 0, the program outputs 0. If the number is greater than or equal to 0, the program outputs 1. Note: this program must be written in Vic's native code, i.e. as a series of 3-digit numbers. Submit the file signum.vic, containing the 3-digit Vic code.

Vic Program 2 (5 points)

Write a program (countPosNeg) that reads a series of numbers that ends with a 0 and outputs how many positive and negative numbers exist in the series. The number 0 at the end of the series is not considered part of the date. For example, when applied to the input -3,2,5,-1,7,0, the program outputs 3,2; when applied to the input -2,-5,-1,0, the program outputs 0,3. This program should also be written in Vic's native code, i.e. as a series of 3-digit numbers. Submit the file countPosNeg.vic, containing the 3-digit Vic code.

Vic Program 3 (5 points)

Write a program (findIndex) that reads a number, followed by a series of numbers that ends with a 0. If the number exists in the series, the program outputs the numbers's location in the series; otherwise the program outputs 0. In this program, for a change, we start counting from 1 rather than 0. For example, when applied to the input 5,12,-3,716,5,12,8,0 the program outputs 4; when applied to the input 7,7,10,-5,0 the program outputs 1. When applied to the input 17,7,10,-5,0 the program outputs 0. Submit the file findIndex.asm, containing the symbolic Vic code.

Vic Program 4 (10 points)

Write a program (memoryDump) that reads three numbers: 300, followed by two numbers, let's call them base and n. Next, the program outputs the n numbers stored in memory locations base to base + n - 1. For example, when applied to the input 300, 90, 4, the program outputs the current contents of memory cells 90, 91, 92, 93. Notes: (1) assume that the inputs are valid, namely that base and n do not cause any overflow, etc. (2) you may wonder why the number 300 is necessary. Well, that's because it's impossible to write this program without it. (3) It is best to think about this program, or at least about parts of it, using Vic's native code, i.e. 3-digit number commands. (4) It is best to write and debug this program away from the computer, on a piece of paper. When you think that the program is working fine, proceed to load and debug it on the computer. Submit the file memoryDump.asm, containing the symbolic Vic code.

 

Building a Vic Computer (75 points)

General Guidelines:

In this project we build a Java implementation of the Vic computer. The computer will operate on programs and inputs stored in text files. To make life simple, you are to assume that the contents of these files – the programs and the data – are always valid. That is, the program file contains a sequence of valid Vic machine language commands, and the input file contains a valid sequence of numbers ranging from -999 to 999. With that in mind, the code that you are asked to write need not test the commands and the inputs validity – it should simply execute and read them, respectively.

There is no need to write Javadoc, since the APIs of all the classes that you have to write are given. At the same time, use comments to document significant code segments or anything else that you think is worth highlighting.

Before working on this project you must familiarize yourself with the Vic computer architecture and fetch-execute logic. In addition, you must write and execute a few programs in the Vic machine language. This can be done by playing with the Vic simulator available in http://www.idc.ac.il/vic.

This is a fun project. Enjoy – Shimon.

The Register class

A register is a container that holds an integer. This is the basic storage unit of the Vic computer. In this program, registers are implemented as objects constructed from a Register class. Here is the Register API.

Implementation: A Register object has a single field: an int variable, holding the register's current value. Write the Register class, following its API.

Testing: Write a test class that creates two or three registers (e.g. Register r1 = new Register();). Next, proceed to test all the Register methods. For example, try sequences of commands like: System.out.println(r1.getValue()); r1.addOne(); System.out.println(r1.getValue()); Write and test similar command sequences for each one of the Register methods, printing relevant values before and after invoking the method.

Note: the difference between r1.getvalue() and r1.toString() (or simply r1) is that the former returns an int and the latter a String. When working with registers, you almost always need to work with their int values.

The Memory class

"Memory" is an indexed sequence of registers. In this program, the memory is implemented as an object derived from a Memory class. Here is the Memory API. The Vic computer will use only one Memory object.

Implementation: The single field of a Memory object is an array of Register objects (more accurately, an array of references to Register objects). The class constructor gets the desired length of the memory as a parameter and proceeds to create an array of so many registers. Write the Memory class according to its API.

Testing: Write a test class that creates a single Memory object and tests all the Memory methods. The test code should look something like this:

Memory m = new Memory(100);

m.setValue(0, 100); // m[0] = 100

m.setValue(1, 200); // m[1] = 200

m.setValue(2, -17); // m[2] = -17

int v = m.getValue(1); // v = m[1]

System.out.println(v);

System.out.println(m); // Display the memory's state

// Etc.

The toString method of the Memory class should generate a string that shows the first and last 10 memory registers. Here is a typical output of the command System.out.println(m);

0 100

1 200

2 -17

3 0

4 0

5 0

6 0

7 0

8 0

9 0

 

90 0

91 0

92 0

93 0

94 0

95 0

96 0

97 0

98 0

99 0

That's precisely the output that your own toString method should generate.

 

Aside: Reading text files in Java

Before going on, you should learn how to handle text files in Java. We need this ability in order to load programs into the computer's memory. There are several popular ways to read and process the contents of text files in Java. We will now show one of them. Once you will write and test this class, you'll be able to cut and paste from it the code that you need in order to implement some of the following methods.

You will notice that the file handling code is rather hairy. That's life. You don't have to understand it fully – just go with the flow and make the code work. Here goes:

import java.io.*;

import java.util.*;

 

// This class reads and writes the entire contents of a text file.

// The name of the text file is assumed to be program.txt.

public class TestScanner {

public static void main (String args[]) {

FileReader reader = null;

Scanner scanner = null;

 

// Initialization code:

try {

reader = new FileReader("program.txt");

scanner = new Scanner (reader);

} catch (FileNotFoundException e) {

System.out.println("The file cannot be found.");

System.exit(0);

}

 

// Read-write code:

while (scanner.hasNextLine()) {

System.out.println(scanner.nextLine().trim());

}

// Closing the file:

scanner.close();

try {

reader.close();

} catch (IOException e) {}

}

}

Take a look at the file program1.txt. If you put this file in your working directory and plug "program1.txt" in the code above instead of "program.txt", the program should generate the following output:

399

900

399

900

Testing: Write and test the TestScanner class on your computer. Make sure it works properly before going on with the project.

 

The Computer class

The Computer class is a Java implementation of the Vic computer. Here is the Computer API.

Stage 1

Implementation: Start by declaring and initializing the three public constants described in the API. Next, declare 10 constants for representing the 10 op-codes of the Vic machine language. For example, the first declaration can be: private final static int READ = 8; From now on, constants like READ should represent the Vic op-codes throughout your class code. Next, declare the four fields (private variables) that characterize a Computer object: a memory, a data register (which is a register), a program counter (also a register), and an input unit. The type of the input unit can be Scanner. More about this, later.

Now write the class constructor, the reset method, and the toString method. Consult the Computer API for details.

Testing: Write a test class that creates a Computer object. Then print the computer's state (that's two lines of code …). The output should look like this:

D register = 0

PC register = 0

Memory state:

0 0

1 0

2 0

3 0

4 0

5 0

6 0

7 0

8 0

9 0

 

90 0

91 0

92 0

93 0

94 0

95 0

96 0

97 0

98 0

99 1

Stage 2

We now turn to write the loadProgram method, which loads a program into the computer's memory. This method reads the contents of a text file containing valid Vic commands and puts the commands in the computer's memory, starting at address 0. The code of this method is similar to that of ScannerTest. The two main differences is that the file name is now a variable, and instead of writing the file's lines to the screen we load them into memory.

Testing: Write a test class that creates a Computer object and loads a program into it. The code will look something like this:

Computer vic = new Computer();

vic.loadProgram("program1.txt");

System.out.println(vic);

Assuming that the file program1.txt is in your working directory, the output of this code should look like this:

D register = 0

PC register = 0

Memory state:

0 399

1 900

2 399

3 900

4 0

5 0

6 0

7 0

8 0

9 0

 

90 0

91 0

92 0

93 0

94 0

95 0

96 0

97 0

98 0

99 1

Stage 3

Moving along. We now turn to implement the run method -- the workhorse of this program. Start by reading the run method API. The method simulates the fetch-execute cycle by fetching the current command from memory and parsing it into an op-code and an address, which are kept in local variables (you may want to use private methods for the parsing). If the op-code is STOP, the method prints the text "Program terminated normally" and terminates. Otherwise, the method turns to execute the command, according to its op-code. There are 9 commands, and thus 9 execution possibilities. We propose implementing the execution of each command by a separate private method. For example, the following method implements the execution of the LOAD command:

 

// Assumes that the data register, program counter, and memory fields are named dReg, pc, and m, respectively.

private void execLoad (int addr) {

dReg.setValue(m.getValue(addr)); // dReg = m[addr]

pc.addOne(); // PC++

}

 

Note that the execLoad method advances the program counter. This is very important – otherwise in the next cycle (loop iteration) the run method will fail to fetch the correct command from the memory. Also note that some commands (like LOAD) simply increment the program counter, while other commands – the branching ones – require a more delicate handling of the program counter. The important thing to remember is that the program counter must be handled as a side-effect of handling the respective commands.

 

Testing: We recommend implementing and testing the commands in stages, and in the following order:

 

Implement and test the LOAD and WRITE commands: use program1.txt

Implement and test the ADD command: use program2.txt

Implement and test the SUB command: use program3.txt

Implement and test the STORE command: use program4.txt

 

Start by writing the main loop of the run method. Next, for each of the commands listed above, implement its private method and test your work by running a test class that looks like this:

 

Computer vic = new Computer();

vic.loadProgram("program1.txt"); // or some other program file

vic.run();

System.out.println(vic);

 

The output should look like this:

 

1

1

Run terminated normally

D register = 1

PC register = 4

Memory state:

0 399

1 900

2 399

3 900

4 0

5 0

6 0

7 0

8 0

9 0

 

90 0

91 0

92 0

93 0

94 0

95 0

96 0

97 0

98 0

99 1

 

The first two lines – the two 1's – are the program's output. The text "Run terminated normally" is printed by the run method (your implementation should print it also). The rest of the output is generated by the System.out.println(vic) command.

Stage 4

We now turn to implement the READ command. Recall that the input field of this Computer is implemented as a Scanner object. In order to read inputs, we initialize this Scanner by associating it with a given text file that contains the program's inputs. This is done by the method loadInput. The code of this method is quite similar to the initialization code of the TestScanner class, which was shown above. So, go ahead and implement this method by adopting code from TestScanner and changing it to fit the specification of loadInput.

Next, implement the READ command. Basically, you need a private execRead method that gets the next line from the input (a Scanner object) and puts it in the data register. (don’t forget to advance the program counter …).

Testing: To test the loadInput and execRead methods, use something like this code:

Computer vic = new Computer();

vic.loadProgram("program5.txt");

vic.loadInput("input1.txt");

vic.run();

System.out.println(vic);

 

If your working directory includes the files program5.txt and input1.txt, this code should produce the following output:

 

10

20

30

Run terminated normally

D register = 30

PC register = 6

Memory state:

0 800

1 900

2 800

3 900

4 800

5 900

6 0

7 0

8 0

9 0

 

90 0

91 0

92 0

93 0

94 0

95 0

96 0

97 0

98 0

99 1

 

The first three lines are the program's output.

Stage 5

We now turn to implement the GOTO, GOTOZ, and GOTOP commands. As usual, each command should be implemented by a separate private method. We recommend doing it in stages, as follows:

 

Implement and test the GOTO and GOTOZ commands: use program6.txt and input2.txt

Implement and test the GOTOP command: use max2.txt (a program the prints the maximum of two given numbers) and input3.txt (a file containing two numbers).

 

Stage 6

Mazeltov! You are the proud owner of a Vic computer that you've built with your ten fingers. You can now test it on the four Vic programs that you were asked to write in this homework. For each program you will need a program file (the vic program that you already wrote) and an input file designed to test it.

 

Submission

Hand in the files Register.java, Memory.java, and Computer.java, in both soft and paper versions. The deadline is November 25, 10 am.