An Address Held in a Register
A machine has four registers numbered 0 to 3, all starting at 0, a memory of
m cells numbered 0 to m - 1 whose starting values are given, and a program
of n instructions numbered from 0. The counter starts at 0.
LOAD r a copy memory cell a into register r
LOADI r t copy the memory cell whose NUMBER is held in register t
into register r
STOREI t r copy register r into the memory cell whose NUMBER is held in
register t
ADD r v add v to register r
JNZ r v if register r is not 0, move the counter on by v,
otherwise by 1
HLT stop
Every instruction except JNZ and HLT moves the counter on by 1.
The a on a LOAD is guaranteed to be a real cell number. The register
holding the address on a LOADI or a STOREI is NOT: a register is just a
number, so it can hold anything. If the address it holds is below 0 or at
least m, the instruction does not execute, nothing changes, and the run stops
with FAULT.
The machine performs at most s steps, and one step is: if the counter is
outside 0 to n - 1, stop and report FAULT; otherwise execute the
instruction there.
Print two lines. The first is the outcome word, one of HALT, FAULT or
RUNNING. The second is all m memory cells in order, separated by single
spaces.
``` n = 3, m = 4, s = 100, memory 7 8 9 10 LOAD 0 2 / STOREI 1 0 / HLT
LOAD 0 2 puts 9 into register 0. STOREI 1 0 writes register 0 into the cell numbered by register 1, which is still 0, so cell 0 becomes 9. -> HALT 9 8 9 10 ```
``` n = 3, m = 2, s = 100, memory 5 6 ADD 0 -1 / LOADI 1 0 / HLT
register 0 becomes -1, and LOADI 1 0 wants the cell numbered -1. -> FAULT 5 6 ```
## What most people try first
Indexing the memory array with whatever the register holds. In C and C++ a
negative index reads whatever happens to sit before the array, so the program
prints a plausible wrong answer. In Python a negative index silently reads from
the END of the list, which is worse, because it is well defined and still
wrong: on the second worked example memory[-1] is 6, and the run would
continue to a HALT instead of faulting.
So the bound has to be tested before the access, both ends of it, and the
answer to "is this address legal" is 0 <= address < m and nothing looser.
## Why the fault must leave memory alone
A STOREI with a bad address is refused, so the memory printed afterwards is
exactly what the previous instruction left. Checking the bound after writing,
or writing to a clamped address, changes the second line of the output as well
as the first. One declared test is a STOREI that walks its address up through
the whole memory and one cell past the end, so the memory printed shows every
legal write and none beyond.
## Why LOAD and LOADI must be told apart by their whole names
LOAD is a prefix of LOADI. A decoder that compares a fixed number of
characters, or switches on the first letter, treats them as the same
instruction. In this bank a C solution that tested only the first letter of an
opcode silently failed every C test on one problem while passing the other four
languages, because set and sub share an s. Compare whole words.
## Overflow
A register is a sum of up to s operands of magnitude 10^9, with s up to
10^5, so it can reach 10^14, far outside a signed 32 bit integer whose top
is 2147483647. Registers and memory cells must be 64 bit. Note that this
makes an address held in a register potentially enormous, which is another
reason the bound test cannot be a single comparison against m.
## Cost
O(n + m + s) time and O(n + m) memory.