Specs - Stack Machine
As already explained in the task description, the main goal of this course is to build a robot that is able to read bar code cards containing instructions for a computing machine that operates on a stack.
This so-called stack machine is capable of performing basic arithmetic and executing text-to-speech.
The following section is about the requirements and specifications for such a machine.
As stack machines are Turing-complete per definition, but we don’t want to proof this for the given instruction set, let’s simply assume that stack machine here is an alias for a pushdown automaton.
The stack machine accepts 6-bit machine words as input.
Depending on the most significant bit (MSB)
$m$ of such word, the following five bits either represent an operand, an instruction or a character.
After initialisation, the stack machine starts with an empty stack and an overflow flag set to False.
Example of the difference in the MSB of a received and decoded word
|000010||operand||000010 = |
|010010||instruction||010010 = DEL|
|110010||character||110010 = O|
$i$- First bit (from left)
$j$- Second bit (from left)
$i$ is not set check the second bit
$j$ is also not set simply take the remaining bits as the binary representation of an operand.
A single operand can have a value in the range
$[0\ \dots\ 15]$.
Note that the value read shall be stored in an 8-bit integer internally. Pushing an operand resets the overflow flag to False.
$i$ is not set and
$j$ is set you have to look up the corresponding command from the instruction set and proceed with further processing.
This may include fetching the correct number of operands from memory, performing the action or calculation and in case a result is generated store it back into memory.
In the following we will refer to operands on the stack by
$k$ always stands for the current position of the element on top, i.e. the size of the stack.
Any operation removes the used operand from the stack and pushes the result to it.
|Bit sequence||Abbreviation||Short description||Overflow flag||Operands (popped/pushed)|
|010000||STP||End of execution. Does not change the stack at all.||no change||0/0|
|010001||DUP||Duplicates the last operand.||no change||1/2|
|010010||DEL||Removes the last operand.||no change||1/0|
|010011||SWP||Swaps the last two operands.||no change||2/2|
|010100||ADD||Adds ||True if addition resulted in a carry out of the most-significant bit, False otherwise||2/1|
|010101||SUB||Subtracts ||True if subtraction resulted in a borrow out of the most-significant bit, False otherwise||2/1|
|010110||MUL||Multiplies ||True if product doesn’t fit into data type, False otherwise||2/1|
|011000||EXP||Calculates ||True if product doesn’t fit into data type, False otherwise||2/1|
|011010||SHL||Shifts ||True if a ||2/1|
|011100||HEX||Converts a sequence of hexadecimal into integer (||False||2/1|
|011101||FAC||Calculates factorial of ||True if factorial doesn’t fit into data type, False otherwise||1/1|
|011110||NOT||Forms the ones’ complement of ||False||1/1|
|011111||XOR||Performs the logical XOR operation on ||False||2/1|
$i$ is set the following 5 bits either are a character, SPEAK or a NOP command.
|100001||SPEAK (Execute Text-to-Speech on decoded character list)|
- Pop first item from stack (number,
- Now, pop
- Execute TTS
During the execution of code an exception may break the normal flow of the program.
An exception is defined as every condition that leads to undefined behaviour.
For example, the programmer may ask the machine to perform an ADD instruction although there are no operands on the stack. Obviously, the instruction cannot be executed and the exception
operand mismatch occurs.
Running the program any further would not make sense in most cases, as following calculations can be expected to generate errors as well.
As a consequence, the machine simply is being halted when encountering an exception.
Please distinguish between undefined and other defined conditions carefully. An integer overflow for instance is accurately specified and therefore no exception.