|
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
|
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.