(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.)
1. See if I can catch you out this time (not likely!) What is your name?
2. Write down the stack assembler code that corresponds to this (silly) program
PROGRAM Silly; 0 DSP 9
VAR 2 ADR -1
I, List[5], J, K; 4 ADR -1
BEGIN 6 VAL
I := (I + 1) / List[J - K]; 7 LIT 1
END. 9 ADD
10 ADR -2
12 ADR -8
The only trick here is to arrange 14 VAL
for the operations to be done 15 ADR -9
in the correct order 17 VAL
18 SUB
19 LIT 6
21 IND
22 VAL
23 DVD
24 STO
25 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
};
or, for Pascal speakers, an equivalent declaration:
TYPE (* machine instructions - order important *)
OPCODES = (adr, lit, dsp, brn, bze, prs, add, sub, mul, dvd, eql, neq,
lss, geq, gtr, leq, neg, val, sto, ind, stk, hlt, inn, prn,
nln, nop, 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. 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;
or, in Pascal
brn :
BEGIN CPU.PC := Mem[CPU.PC] END;
bze :
BEGIN
INC(CPU.SP);
IF Mem[CPU.SP - 1] = 0 THEN CPU.PC := Mem[CPU.PC] ELSE INC(CPU.PC)
END;
Why do we not also have a BNZ opcode?
If we wished to add it, what would we have to add to the interpreter?
Most people saw this - of course we don't need BNZ as any test that would be followed by a BNZ could be expressed as the reverse test followed by a BZE, for example
EQL NEQ
BZE BNZ
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 (inbounds(cpu.sp))
{ if (mem[cpu.sp - 1] == 1) cpu.pc = mem[cpu.pc]; else cpu.pc++; }
break;
bnz :
BEGIN
INC(CPU.SP);
IF InBounds(CPU.SP) THEN
IF Mem[CPU.SP - 1] = 1 THEN CPU.PC := Mem[CPU.PC] ELSE INC(CPU.PC)
END;
5. The emulator you have been using as been for a machine that only supports "integer" arithmetic. Outline briefly what you would have to do to develop an emulator for a system that (instead) supported only "real" (floating-point) arithmetic.
This was intended to see who had really gained a proper insight into how emulators work. Nobody had a really good answer, though several students observed astutely that the solution would depend on declaring a memory array to be one of reals (floating point) rather than one of integers. The problem with this is that the memory has to store not only data (on the stack), but also code and string literals, and these are not really best stored as real values.
There are two ways around this, commonly found in such interpreters. The one is to have two separate arrays - one for code/strings and the other for the stack of real values. The other is to declare the memory to be an array of what C programmers call unions and Pascal/Modula programmers call variant records, where the same location can be addressed in the simulator in one of two ways. Actually an array of even simpler structures would suffice - here is one possible set of declarations:
struct WORDS {
int intVal;
float floatVal;
};
WORDS mem[STKMC_memsize]; // The memory array
and then operations like BRN and VAL get coded up like this
case STKMC_brn:
cpu.pc = mem[cpu.pc].intVal; break;
case STKMC_val:
if (inbounds(cpu.sp) && inbounds(mem[cpu.sp].intVal))
mem[cpu.sp].floatVal = mem[mem[cpu.sp].intVal].floatVal;
break;
or, for those who speak Pascal:
TYPE
WORDS = RECORD
IntVal : INTEGER;
RealVal : REAL;
END
VAR
Mem : ARRAY [0 .. MemSize - 1] OF WORDS
BRN:
CPU.PC = Mem[CPU.PC].INTVAL;
VAL:
IF InBounds(CPU.SP) AND InBounds(Mem[CPU.SP].IntVal)
Mem[CPU.SP].RealVal := Mem[Mem[CPU.SP].IntVal].RealVal;
But apart from a lot of changes like this the system is virtually the same (the I/O has to accommodate different calls to I/O primitives, of course).
(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.)
1. See if I can catch you out this time (not likely!) What is your name?
2. Write down the stack assembler code that corresponds to this (silly) program
PROGRAM Silly; 0 DSP 14
VAR 2 ADR -3
I, J, List[10], K; 4 ADR -1
BEGIN 6 VAL
List[I * K] := I + J/K; 7 ADR -14
END. 9 VAL
10 MUL
11 LIT 11
13 IND
The only trick here is to arrange 14 ADR -1
for the operations to be done 16 VAL
in the correct order 17 ADR -2
19 VAL
20 ADR -14
22 VAL
23 DVD
24 ADD
25 STO
26 HLT
3. In the prac you were invited to note that sequences like
ADR -X and ADR -Y
VAL code
STO
occurred frequently, so frequently that it might be worth introducing special opcodes PSH -X and POP -Y instead.
By now you will recognise something of the Terry perversity - maybe the machine is defined to have ADR, VAL and STO opcodes rather than simply having only PSH and POP opcodes for no other reason than that it makes for lots of fun late at night to add these opcodes to the machine. But maybe not? If you have PSH and POP, could you completely remove ADR, VAL and STO from the opcode list, or would you still need to have them available? Justify your answer.
If every VAL was preceded by an ADR one could get away with using PSH instead of ADR + VAL, and if every other use of ADR was followed by a STO one could get away without ADR. But this is not the case. Consider the following code:
Read(I); List[I] := List[J];
which, even if we use every PSH and POP we can, translates to
ADR -I
INN
ADR -List
PSH -I
LIT Size
IND
ADR -List
PSH -J
LIT Size
IND
VAL
STO
4. A BYP (Bright Young Programmer) came up with the following idea for adding an overflow check to the stack machine interpreter multiplication code:
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 this did not work, so the BYP tried it in Pascal as follows:
mul :
BEGIN
INC(CPU.SP);
IF InBounds(CPU.SP) THEN
Mem[CPU.SP] := Mem[CPU.SP] * Mem[CPU.SP - 1];
IF Mem[CPU.SP] > MAXINT THEN PS := Overflow
END;
and found that this did not work either. Be an EBYP (Even Brighter Young Programmer) and show what sort of code we would need to perform this check properly (in either C++ or Pascal, no need to try both)
It was all too obvious who had bothered to do this part of the prac correctly! Here is one possible solution, which does not require the actual machine to have any greater precision available than the toy machine has:
case STKMC_mul:
cpu.sp++;
if (inbounds(cpu.sp)) {
if (abs(mem[cpu.sp]) < maxint / abs(mem[cpu.sp-1]))
mem[cpu.sp] *= mem[cpu.sp - 1];
else ps = overflow;
}
break;
or
mul :
BEGIN
INC(CPU.SP);
IF InBounds(CPU.SP) THEN
IF ABS(Mem[CPU.SP]) < MAXINT / ABS(Mem[CPU.SP-1])
THEN Mem[CPU.SP] := Mem[CPU.SP] * Mem[CPU.SP - 1]
ELSE PS := Overflow
END;
5. Suppose we wish to add to the machine so that detecting overflow does not change the program status PS and cause the emulator to stop immediately, but sets a processor flag which programmers could test if and when they felt the urge to write safe programs (an urge which I hope this course will cause you to experience ever more frequently).
Now suppose for the moment that the code given earlier had tried to reflect this by changing the obvious line to read
if (mem[cpu.sp] > maxint) cpu.ov = true;
or, of course,
IF Mem[CPU.SP] > MAXINT THEN CPU.OV := TRUE
Leaving aside that the test is not reliable, this in itself would not be very helpful. We would also need some way that a programmer could program in a test for overflow. Assume that this is to be done by adding a STKMC_bov (branch if overflow set) opcode. How would this have to be emulated?
Those who seemed to have some clue about what overflow actually means managed to get part way, but I don't think that anyone saw that one would need to be able to unset the overflow flag. The best place to do this might be just after testing it, as below:
case STKMC_bov:
if (cpu.ov) cpu.pc = mem[cpu.pc]; else cpu.pc++;
cpu.ov = false; // reset the flag
break;
or
bov :
BEGIN
IF CPU.OV = THEN CPU.PC := Mem[CPU.PC] ELSE INC(CPU.PC);
CPU.OV := FALSE (* reset the flag *)
END;
Alternatively one might be tempted to clear the overflow flag at the start of attempting each ADD, SUB, MUL or DVD operation, and then set it if overflow was detected during that operation. However, this might be clumsy to use, as, for example, code like
X := VeryBig * VeryBig / 1;
IF (Overflow) THEN begin Write('Overflow occurred'); RETURN END;
might set overflow when the multiplication was attempted, and then unset it when the division occurred, leaving the overflow undetectable at the point where it is finally checked.