Computer Science 3 - 2001 - Test on Prac 16
(This should take no longer than 20 minutes and is simply intended to probe whether you have understood the
material in the prac questions. You may use your textbook if you think it will help. Answer on the questions
sheet.)
THURSDAY TEST
1. You'd think I'd have learned by now! What is your surname?
2. Write down the stack assembler code that corresponds to this (silly) program
PROGRAM Silly;
VAR
I, List[20], K;
BEGIN
List[3+K] := List[I + K/4]
END.
This was very badly done, which was surprising as you had been doing several
of these in the prac. Puzzle it out! Incidentally, several students tried to
solve this by storing intermediate values in top of K, which would be a
horrible side effect!
DSP 23
ADR -2
LIT 3
ADR -23
VAL
ADD
LIT 21
IND
ADR -2
ADR -1
VAL
ADR -23
VAL
LIT 4
DVD
ADD
LIT 21
IND
VAL
STO
HLT
3. In the header for the stack machine emulator you will find the lines
// machine instructions - order important
enum STKMC_opcodes {
STKMC_adr, STKMC_lit, STKMC_dsp, STKMC_brn, STKMC_bze, STKMC_prs, STKMC_add,
STKMC_sub, STKMC_mul, STKMC_dvd, STKMC_eql, STKMC_neq, STKMC_lss, STKMC_geq,
STKMC_gtr, STKMC_leq, STKMC_neg, STKMC_val, STKMC_sto, STKMC_ind, STKMC_stk,
STKMC_hlt, STKMC_inn, STKMC_prn, STKMC_nln, STKMC_nop, STKMC_nul
};
Why on earth is the "order important"?
Amazingly, very few people got this right, and yet they must surely have known
that the valid opcodes all come before "nul", otherwise the simple search in
the assembler that associated mnemonics with opcodes will fail. Looking
further we see that all the two-word operations are defined ahead of the
one-word operations. Although this is not important in the rest of my code,
it just might be useful to stick with that convention.
The most frequent "wrong" answer was that the order of the enumeration had to
match the order of the labels in the switch/case statement. I am not sure
where this misconception came from. The order of the labels in a switch/case
statement is unimportant. What is important, of course, is that the labels
must be unique - something like
switch (exp) {
case 1: something(); break;
case 2: somethingelse(); break;
case 1: somethingdifferent(); break;
}
should not be allowed.
4. A BYP (Bright Young Programmer), noting that the emulator checked for
division by zero, came up with the following idea for adding another
overflow check, namely for attempting to multiply large numbers whose
product would be too large to store:
case STKMC_mul:
cpu.sp++;
if (inbounds(cpu.sp)) {
mem[cpu.sp] *= mem[cpu.sp - 1];
if (mem[cpu.sp] > maxint) ps = overflow;
}
break;
but found that this did not work. Be an EBYP (Even Brighter Young
Programmer) and show what sort of code we would need to perform this check
properly.
Rather few people saw this. The catch is that the overflow would happen
before it could be detected. There are several possibilities:
(a) Use a variable of LONG type to do the multiplication and then check the
result (remembering that the result could be positive or negative; I don't
think anyone saw that). This sort of trick is only possible if the
interpreter can do arithmetic to greater precision that the machine it is
trying to simulate.
In C++:
case STKMC_mul:
cpu.sp++;
if (inbounds(cpu.sp)) {
long temp = mem[cpu.sp] * mem[cpu.sp - 1];
if (abs(temp) > maxint) ps = overflow; else mem[cpu.sp] = temp;
}
break;
(b) If we do not have extended precision available on the "real" machine we
have to be rather more clever. We can, however, use a check on division rather
than on multiplication. If A * B < C then it also follows that A < C / B,
and of course C/B is <= C if B is an integer. So we can keep within the
bounds of the simulated data type!
We might think we could get away with
case STKMC_mul:
cpu.sp++;
if (inbounds(cpu.sp)) {
if (abs(maxint / mem[cpu.sp]) > abs(mem[cpu.sp - 1]))
ps := overflow;
else mem[cpu.sp] *= mem[cpu.sp - 1];
}
break;
Actually this is inadequate; it would collapse if mem[cpu.sp] = 0. But that
is easily fixed:
case STKMC_mul:
cpu.sp++;
if (inbounds(cpu.sp)) {
if mem[cpu.sp] != 0
if abs(maxint / mem[cpu.sp]) > abs(mem[cpu.sp - 1]))
ps := overflow;
else mem[cpu.sp] *= mem[cpu.sp - 1];
else /* the product would be zero anyway */
}
break;
The point to be noted is that interpretation/simulation has to be very
carefully done if it is not to go wrong at crucial times.
FRIDAY TEST
1. You'd think I'd have learned by now! What is your surname?
2. Write down the stack assembler code that corresponds to this (silly) program
PROGRAM Silly;
VAR
I, List[20], K;
BEGIN
I := List[K+List[K]]
END.
This was very badly done, which was surprising as you had been doing several
of these in the prac. Puzzle it out! Incidentally, several students tried to
solve this by storing intermediate values in top of K, which would be a
horrible side effect!
DSP 23
ADR -1
ADR -2
ADR -23
VAL
ADR -2
ADR -23
VAL
LIT 21
IND
VAL
ADD
LIT 21
IND
VAL
STO
HLT
3. The machine currently supports the input and output of integer data only,
using the INN and PRN opcodes. What changes (additions) would you have to
make to allow for opcodes INC and PRC that would read and write a single
character of data?
Most students had a good idea about how to do this. We have to add two
opcodes to the machine (they would have to be added into various tables too).
The code in the CASE/SWITCH statements would be a simple variation on the
extant code for PRN and INN, for example (note how I have used a MOD 256
operation to make sure that the character to be printed comes from the ASCII
set)
case STKMC_inc:
if (inbounds(cpu.sp) && inbounds(mem[cpu.sp]))
{ char temp;
if (fscanf(data, "%c", &mem[mem[cpu.sp]]) == 0) ps = baddata;
else cpu.sp++;
}
break;
case STKMC_prc:
if (tracing) fputs(BLANKS, results);
cpu.sp++;
if (inbounds(cpu.sp)) fprintf(results, "%c", abs(mem[cpu.sp - 1]) % 256);
if (tracing) putc('\n', results);
break;
4. The stack machine supports two branch instructions BZE and BRN, with
emulation on the lines of
case STKMC_brn:
cpu.pc = mem[cpu.pc]; break;
case STKMC_bze:
cpu.sp++;
if (mem[cpu.sp - 1] == 0) cpu.pc = mem[cpu.pc]; else cpu.pc++;
break;
Why do we not also have a BNZ opcode?
Because, as most people had noticed, we don't need it. Code like
NEQ
BNZ X
is easily rewritten as
EQL
BZE X
Alternatively, code like
BNZ Somewhere
CarryOn
could be written
BZE CarryOn
BRN Somewhere
CarryOn
If we wished to add it, what would we have to add to the interpreter?
A trivial change to the code for bze is all that is needed to be added, plus
of course the changes needed in the lists of opcodes and mnemonics:
case STKMC_bnz:
cpu.sp++;
if (mem[cpu.sp - 1] != 0) cpu.pc = mem[cpu.pc]; else cpu.pc++;
break;