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.

Info

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

MSB	Type	Translation
000010	operand	000010 = $2_{10}$
010010	instruction	010010 = DEL
110010	character	110010 = O

$i$ - First bit (from left)
$j$ - Second bit (from left)

Operands

In case $i$ is not set check the second bit $j$ for $1$ or $0$ . If $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.

Instructions

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

Note

In the following we will refer to operands on the stack by $o_{k}$ . Where $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.

Possible instructions and what to do

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 $o_{k}$ to $o_{k-1}$ .	True if addition resulted in a carry out of the most-significant bit, False otherwise	2/1
010101	SUB	Subtracts $o_{k}$ from $o_{k-1}$ .	True if subtraction resulted in a borrow out of the most-significant bit, False otherwise	2/1
010110	MUL	Multiplies $o_{k}$ with $o_{k-1}$ .	True if product doesn’t fit into data type, False otherwise	2/1
010111	DIV	Divides $o_{k-1}$ by $o_{k}$ .	False	2/1
011000	EXP	Calculates $o_{k-1}$ ^ $o_{k}$ ^.	True if product doesn’t fit into data type, False otherwise	2/1
011001	MOD	Calculates $o_{k-1}$ modulo $o_{k}$ .	False	2/1
011010	SHL	Shifts $o_{k-1}$ by $o_{k}$ places to the left.	True if a `1` is shifted out of the operand, False otherwise	2/1
011011	SHR	Shifts $o_{k-1}$ by $o_{k}$ places to the right.	False	2/1
011100	HEX	Converts a sequence of hexadecimal into integer ( $o_{k}$ to $o_{k-1}$ ).	False	2/1
011101	FAC	Calculates factorial of $o_{k}$ .	True if factorial doesn’t fit into data type, False otherwise	1/1
011110	NOT	Forms the ones’ complement of $o_{k}$ .	False	1/1
011111	XOR	Performs the logical XOR operation on $o_{k}$ and $o_{k-1}$ bit by bit.	False	2/1

Character

If $i$ is set the following 5 bits either are a character, SPEAK or a NOP command.

Possible characters

Bit sequence	Description
100000	NOP
100001	SPEAK (Execute Text-to-Speech on decoded character list) - Pop first item from stack (number, $l$ ) - Now, pop $l$ items from the stack and combine them for TTS processing - Execute TTS
100010	WHITESPACE
100011	NOP
100100	A
100101	B
100110	C
100111	D
101000	E
101001	F
101010	G
101011	H
101100	I
101101	J
101110	K
101111	L
110000	M
110001	N
110010	O
110011	P
110100	Q
110101	R
110110	S
110111	T
111000	U
111001	V
111010	W
111011	X
111100	Y
111101	Z
111110	NOP
111111	NOP

Exceptions

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.

Info

Please distinguish between undefined and other defined conditions carefully. An integer overflow for instance is accurately specified and therefore no exception.