Description
Project Five: List, Stack and Queue
Task 2: Stack Machines
Problem
Most computers are built according to the von Neumann architecture, which consists of a central processing unit (CPU), a memory unit, and I/O devices. This architecture is fast and robust in general. Therefore, many instruction set architectures (ISAs) like ARM, MIPS, and so on, are designed based on it. However, another type of architecture is popular for virtual machines: stack machine. One of its main components is a stack to store operands. All operations can be executed just using this stack. Therefore, this architecture is simple to implement. Java virtual machine (JVM) and WebAssembly (Wasm), which are widely used nowadays, are both based on abstract stack machines. In this part, we plan to use our own Dlist class to implement a simple but powerful stack machine by ourselves.
General Computational Model
Our computational model is based on a simplified stack machine. It contains an operand stack, an instruction queue (or list), and a memory array. The structure is shown below.
To simplify our model, we only have 32-bit integers in the stack and memory. The memory is only 64 bytes (recall a byte = 8 bits), hence, we have 16 addresses where each address corresponds to a 32-bit integer. To compute on this machine, we always pop the first instruction from the queue and execute this instruction accordingly. We now introduce those instructions.
Arithmetic Operations: ADD,NOR
This kind of operations is designed to deal with the operand stack. For example, ADD means popping up two elements from the stack and then pushing the sum of these two elements into the stack. The detail is shown below:
At first, the stack is [n1, n2, …]. And after executing ADD, the stack is [n1+n2, …].
Another operation is the bitwise boolean operator NOR. Its truth table is shown below:
| n1 | n2 | n1 NOR n2 |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
For example, 5 NOR 7 = -8 because 5 is represented in binary by 00000101, 7 by
00000111, and 00000101 NOR 00000111 = 11111000, which is -8 in the 2’s
complement representation. In C++, you may use int result = ~(a|b); to perform the NOR operation. This instruction runs similar to ADD, hence, [n1, n2, …] -> [n1 NOR n2, …].
Control Operations: IFZ,HALT
A control operation is used to control the instruction queue. For example, HALT means to halt the whole machine, hence, stop the program. Another non-trivial instruction is IFZ. It also has an argument n. When the front of the queue is IFZ n, we first pop up the first element in the stack. If this element is zero, we pop up the following n instructions in the queue. If this element is not zero, we continue executing the next instruction. An example is shown below.
Memory Operations: LOAD,STORE
A memory operation is designed for operating with the memory. For example, we want to get a value stored at an address or store a value to an address.
LOAD is to get the value stored in the memory. When executing it, we first pop up an element from the stack. This first element is the address. Then, we find the value stored at this address and push it into the stack. STORE means to store a value in the memory. When executing it, we first pop up two elements. The first element is the address and the second is the value. If we declare the memory as int mem[16];.
This means mem[address] = value. An example is shown below.
Stack Operations: POP, PUSHI
These two operations can control the elements in the stack directly. POP means to pop up an element directly and PUSHI n means to push a constant n into the stack.
Other Operation: NOOP
NOOP does nothing. Just read the operation and skip it.
Setup
As an ideal model, we assume that the stack and queue have an unlimited capacity. At the beginning, the instruction queue, operand stack and memory are initialized. Then, the stack machine starts by executing the instructions from the queue. Further details are provided in the I/O Format section below.
I/O Format
Input
In the first line, there are two numbers n, m where n is the number of elements in the stack, m is the number of elements in the queue. In the second line, there are n numbers divided by a space. You may push them in sequence in the stack. Hence, 1
2 3 4 means that 4 is on the top and 1 is at bottom of the stack. In the next following m lines, there are m instructions. In the header file Instr.h, we provide a data structure Instr to hold values representing instructions. You can use the functions provided in it directly, e.g.,
Instr ins; std::cin >> ins;
In the last line, there are 16 numbers. They are shown as mem[0] mem[1] … mem[15]. Here is a sample input:
5 14
0 1 2 3 4
PUSHI 0
LOAD
PUSHI 1
LOAD
PUSHI 1
LOAD
NOR
PUSHI 1
ADD
ADD
PUSHI 2
STORE
NOOP
HALT
999 888 1 2 0 0 0 0 0 0 0 0 0 0 0 1
You do not need to check for errors. Whenever there is an instruction like ADD, the number of elements in the stack would be enough. Also, when the instruction is LOAD or STORE, the top of the stack is between 0 and 15. The input will ensure the machine will halt.
Output
When there is no argument provided, after executing each instruction, you should print the machine status. It consists of four lines: instruction that executed, stack, queue, memory. A sample is provided below:
PUSHI 1
1 2 3 4 999 1
LOAD PUSHI 1 LOAD NOR PUSHI 1 ADD ADD PUSHI 2 STORE NOOP HALT 999 888 1 2 0 0 0 0 0 0 0 0 0 0 0 1
Similarly, the output for Instr is provided, you can use it by:
Instr ins;
// initialize ins std::cout << ins;
You may also use the operator << overloaded for Dlist<T> to output:
Dlist<int> intList; std::cout << intList;
Argument
When the program gets an argument -s, it doesn’t need to output anything after executing each instruction. You only need to print the machine status when the machine halts. The output consists of two lines: stack and memory. Here is an example for a sample input:
$ ./sam -s < ./sample.in
1 2 3 4
999 888 111 2 0 0 0 0 0 0 0 0 0 0 0 1
