There were some very good solutions submitted, and some very energetic ones too - clearly a lot of students had put in many hours developing their code. This is very encouraging. Do learn to put your names into the introductory comments of programs that you write.
Full source for the solutions summarized here can be found in the ZIP files on the Web pages - PRAC21CA.ZIP (C++ version) or PRAC21PA.ZIP (Pascal version).
Most people had seen at least one improvement that could be made to the palindrome checker to ensure that the loop terminated as quickly as possible. Here are some suggestions (there are even more ways of course):
IsPalindrome := TRUE; (* optimist *)
Low := 0; High := N - 1; (* initial indices *)
WHILE Low < High DO BEGIN (* sweep through the List *)
IF List[Low] <> List[High] THEN IsPalindrome := FALSE; (* bad luck *)
Low := Low + 1; High := High - 1; (* adjust indices *)
END;
IsPalindrome := TRUE; (* optimist *)
Checking := TRUE; (* start search *)
Low := 0; High := N - 1; (* initial indices *)
WHILE Checking = TRUE DO BEGIN (* sweep through the List *)
IF List[Low] <> List[High] THEN BEGIN
IsPalindrome := FALSE; (* bad luck *)
Checking := FALSE (* no need to search further *)
END;
Low := Low + 1; High := High - 1; (* adjust indices *)
IF Low >= High THEN Checking := FALSE (* reached middle *)
END;
IsPalindrome := TRUE; (* optimist *)
Low := 0; High := N - 1; (* initial indices *)
WHILE Low < High DO BEGIN (* sweep through the List *)
IF List[Low] <> List[High] THEN BEGIN
IsPalindrome := FALSE; (* bad luck *)
Low := High (* to abort the loop *)
END;
Low := Low + 1; High := High - 1; (* adjust indices *)
END;
IsPalindrome := TRUE; (* optimist *)
Low := 0; Mid := N/2; (* initial indices *)
WHILE Low < Mid DO BEGIN (* sweep through the List *)
IF List[Low] <> List[N - 1 - Low] THEN BEGIN
IsPalindrome := FALSE; (* bad luck *)
Low := Mid (* to abort the loop *)
END;
Low := Low + 1; (* adjust indices *)
END;
One way that requires a little more coding is to use a function that returns as soon as it can:
FUNCTION IsPalindrome(List[], N);
VAR
Low, High; (* indices of items to be compared *)
BEGIN
Low := 0; High := N - 1; (* initial indices *)
WHILE Low < High DO BEGIN (* sweep through the List *)
IF List[Low] <> List[High] THEN RETURN FALSE; (* bad luck *)
Low := Low + 1; High := High - 1; (* adjust indices *)
END;
RETURN TRUE
END;
BEGIN
IF IsPalindrome(List, N) = TRUE THEN Write('Palindromic sequence');
IF IsPalindrome(List, N) = FALSE THEN Write('Non-palindromic sequence');
END.
Most people seemed to get to a solution, or close to a solution. Here is one that matches the original Clang algorithm (which is actually what you were asked to do!
; comments are allowed on lines starting with ; ; program to check a sequence for being palindromic ; P.D. Terry, Rhodes University, 2000 0 DSP 106 ; BEGIN 73 BZE 121 ; WHILE Low < N - 1 DO BEGIN 2 ADR -1 ; 75 ADR -6 ; 4 LIT 0 ; 77 ADR -2 ; 6 STO ; N := 0 79 VAL ; 7 ADR -4 ; 80 LIT 101 ; 9 INN ; Read(Item) 82 IND ; 10 ADR -4 ; 83 VAL ; 12 VAL ; 84 ADR -6 ; 13 LIT 0 ; 86 ADR -3 ; 15 NEQ ; 88 VAL ; 16 BZE 44 ; WHILE Item <> 0 DO BEGIN 89 LIT 101 ; 18 ADR -6 ; 91 IND ; 20 ADR -1 ; 92 VAL ; 22 VAL ; 93 NEQ ; 23 LIT 101 ; 94 BZE 101 ; IF List[Low} <> List[High] THEN 25 IND ; 96 ADR -5 ; 26 ADR -4 ; 98 LIT 0 ; 28 VAL ; 100 STO ; IsPalindrome := FALSE 29 STO ; List[N] := Item 101 ADR -2 ; 30 ADR -1 ; 103 ADR -2 ; 32 ADR -1 ; 105 VAL ; 34 VAL ; 106 LIT 1 ; 35 LIT 1 ; 108 ADD ; 37 ADD ; 109 STO ; Low := Low + 1 38 STO ; N := N + 1 110 ADR -3 ; 39 ADR -4 ; 112 ADR -3 ; 41 INN ; Read(Item) 114 VAL ; 42 BRN 10 ; END 115 LIT 1 ; 44 ADR -5 ; 117 SUB ; 46 LIT 1 ; 118 STO ; High := High - 1 48 STO ; IsPalindrome := TRUE 119 BRN 63 ; END 49 ADR -2 ; 121 ADR -5 ; 51 LIT 0 ; 123 VAL ; 53 STO ; Low := 0 124 LIT 1 ; 54 ADR -3 ; 126 EQL ; 56 ADR -1 ; 127 BZE 132 ; IF IsPalindrome = TRUE THEN 58 VAL ; 129 PRS 'Palindromic sequence' 59 LIT 1 ; 131 NLN ; 61 SUB ; 132 ADR -5 ; 62 STO ; High := N = 1 134 VAL ; 63 ADR -2 ; 135 LIT 0 ; 65 VAL ; 137 EQL ; 66 ADR -1 ; 138 BZE 143 ; IF IsPalinDrome = FALSE THEN 68 VAL ; 140 PRS 'Non-palindromic sequence' 69 LIT 1 ; 142 NLN ; 71 SUB ; 143 HLT ; END 72 LSS ;
Checking sentences for palindromes can use essentially the same algorithm, but care has to be taken to apply it only to the alphanumeric characters. If one develops simple minded operations for reading and writing characters, as most people successfully did, then one is rather forced to try to write code that corresponds to the following (where, of course, one has to use the magic ASCII numbers for the characters limiting the ends of the valid ranges):
PROGRAM Palindrome;
(* Read a sequence of characters and report whether they form a palindromic
sentence (one that reads the same from either end)
Examples: Madam, I'm Adam. is palindromic
Pat Terry. is non-palindromic
P.D. Terry, Rhodes University, 2000 *)
CONST
TRUE = 1;
FALSE = 0;
VAR
N, (* number of items *)
Low, High, (* indices of items to be compared *)
Item, (* latest item read *)
IsPalindrome, (* Boolean flag *)
List[100]; (* the list of items *)
BEGIN
N := 0;
ReadChar(Item);
WHILE Item <> '.' DO BEGIN
IF Item >= 'A' THEN
IF Item <= 'Z' THEN BEGIN List[N] := Item; N := N + 1 END;
IF Item >= 'a' THEN
IF Item <= 'z' THEN BEGIN List[N] := Item; N := N + 1 END;
IF Item >= '0' THEN
IF Item <= '9' THEN BEGIN List[N] := Item; N := N + 1 END;
ReadChar(Item)
END;
IsPalindrome := TRUE; (* optimist *)
Low := 0; High := N - 1; (* initial indices *)
WHILE Low < High DO BEGIN (* sweep through the List *)
IF List[Low] <> List[High] THEN IsPalindrome := FALSE; (* bad luck *)
Low := Low + 1; High := High - 1; (* adjust indices *)
END;
IF IsPalindrome = TRUE THEN Write('Palindromic sequence');
IF IsPalindrome = FALSE THEN Write('Non-palindromic sequence');
END.
This is all rather tedious to code up, and several people tried to do clever things with the interpreter to cut out having to write all those nasty IF statements out in detail. However, I suspect it is not very clever to restrict the operation for reading characters to handle only letters, or only upper case letters, or to force the characters to be stored in upper case, as some people did. Rather introduce further opcodes for doing this. Although this was not suggested in the prac sheet, the solution below shows how these could have been defined; in terms of them (and other extensions) a rather shorter palindrome checker might be coded as follows:
; comments are allowed on lines starting with ;
; program to check a sentence for being palindromic
; P.D. Terry, Rhodes University, 2000
0 DSP 106 57 POP -3 Low := N - 1;
2 LIT 0 BEGIN 59 PSH -2
4 POP -1 N := 0 61 PSH -3
6 ADR -4 63 LSS
8 INA ReadChar(Item) 64 BZE 97 WHILE Low < High DO BEGIN
9 PSH -4 66 ADR -6
11 LIT 46 68 PSH -2
13 NEQ 70 LIT 101
14 BZE 44 WHILE Item <> '.' DO BEGIN 72 IND
16 PSH -4 73 VAL
18 UPC 74 ADR -6
19 POP -4 Item := UpCase(Item) 76 PSH -3
21 PSH -4 78 LIT 101
23 ALN 80 IND
24 BZE 39 IF AlNum(Item) THEN BEGIN 81 VAL
26 ADR -6 82 NEQ
28 PSH -1 83 BZE 89 IF List[Low] <> List[High] THEN
30 LIT 101 85 LIT 0
32 IND 87 POP -5 IsPalinDrome := FALSE;
33 PSH -4 89 ADR -2
35 STO List[N] := Item; 91 INC Low := Low + 1;
36 ADR -1 92 ADR -3
38 INC N := N + 1 94 DEC High := High - 1;
39 ADR -4 END; 95 BRN 50 END;
41 INA ReadChar(Item); 97 PSH -5
42 BRN 9 END; 99 LIT 1
44 LIT 1 101 EQL IF IsPalindrome THEN
46 POP -5 IsPalindrome := TRUE; 102 BZE 108
48 LIT 0 104 PRS 'Palindromic sequence'
50 POP -2 High := 0; 106 BRN 110 ELSE
52 PSH -1 108 PRS 'Non-palindromic sequence'
54 LIT 1 110 NLN
56 SUB 111 HLT END.
Some people forgot to introduce the PSH and POP references everywhere. They are needed in the switch statements in
void STKMC::listcode(char *filename, STKMC_address codelen)
and in
void STKMC::trace(FILE *results, STKMC_address pcnow)
as well as in the obvious one in the emulator.
Checking for overflow in multiplication was not well done. Here is one way of doing it - note the check to prevent a division by zero. This does not use any precision greater than that of the simulated machine itself.
case STKMC_mul:
cpu.sp++;
if (inbounds(cpu.sp)) {
if (mem[cpu.sp] != 0 && abs(mem[cpu.sp-1]) > maxint / abs(mem[cpu.sp]))
ps = overflow;
else mem[cpu.sp] *= mem[cpu.sp - 1];
}
break;
Some students used an intermediate long variable (most of them forgot that they should use the abs function as well!)
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] *= mem[cpu.sp - 1];
}
break;
Pushing and popping are actually very easy. There were some curious mistakes, showing that no much had been tested properly! Note the form that the inbounds checks take - many people got these wrong:
case STKMC_psh:
cpu.sp--;
if (inbounds(cpu.sp) && inbounds(cpu.bp + mem[cpu.pc]))
{ mem[cpu.sp] = mem[cpu.bp + mem[cpu.pc]]; cpu.pc++; }
break;
case STKMC_pop:
cpu.sp++;
if (inbounds(cpu.sp) && inbounds(cpu.bp + mem[cpu.pc]))
{ mem[cpu.bp + mem[cpu.pc]] = mem[cpu.sp - 1]; cpu.pc++; }
break;
Reading and writing characters was trivially easy, being essentially a simple variation on the cases for numeric input and output. However, the output of numbers was arrranged to have a leading space; this is not as pretty when you see i t a p p l i e d t o c h a r a c t e r s , i s i t ? And note the use of the modulo arithmetic to ensure that only sensible ASCII characters will be printed:
case STKMC_ina:
if (inbounds(cpu.sp) && inbounds(mem[cpu.sp]))
{ if (fscanf(data, "%c", &mem[mem[cpu.sp]]) == 0) ps = baddata;
else cpu.sp++; }
}
break;
case STKMC_pra:
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;
The opcodes for the equivalent of a ++ or -- operation produced interesting answers. There are clearly two approaches that could be used: either increment the value at the top of the stack, or increment the variable whose address is at the top of the stack. I suspect the latter is more useful if you are to have but one of these (one could, of course, provide both versions of the opcodes). Here is my suggestion:
case STKMC_inc:
if (inbounds(cpu.sp) && inbounds(mem[cpu.sp])) mem[mem[cpu.sp]]++;
cpu.sp++;
break;
case STKMC_dec:
if (inbounds(cpu.sp) && inbounds(mem[cpu.sp])) mem[mem[cpu.sp]]--;
cpu.sp++;
break;
With these, one can translate statements like
A++ or List[4]--
into very short sequences
ADR -A ADR -List
INC LIT 4
LIT Size
IND
DEC
The functions for ABS, ODD, IsAlNum and ToUpper are realised by very simple opcodes that do not bump the stack pointer at all:
case STKMC_abs:
if (inbounds(cpu.sp)) mem[cpu.sp] = abs(mem[cpu.sp]);
break;
case STKMC_odd:
if (inbounds(cpu.sp)) mem[cpu.sp] = (mem[cpu.sp] % 2 != 0);
break;
case STKMC_aln:
if (inbounds(cpu.sp)) mem[cpu.sp] = isalnum(mem[cpu.sp]);
break;
case STKMC_upc:
if (inbounds(cpu.sp)) mem[cpu.sp] = toupper(mem[cpu.sp]);
break;
Finally, it is necessary to add the menmonics and the opcodes into the look up tables, but obviously everyone had realised this. It is important to leave STKMC_nul as the last opcode in the enumeration, as most people must have realised (or were just lucky, as the quiz question caught a whole lot of you out!)
In terms of these new opcodes programs can become much shorter. Here are some examples:
; comments are allowed on lines starting with ;
; program to find the smallest and largest of a stream of integers
; P.D. Terry, Rhodes University, 2000 (modified to use pop/psh)
0 DSP 3 A is at BP-1, Largest at BP-2, Smallest at BP-3
2 PRS 'Supply list of numbers terminated with 0 '
4 ADR -1
6 INN read A
7 PSH -1
9 POP -3 SMALLEST := A
11 PSH -1
13 POP -2 LARGEST := A
15 PSH -1
17 LIT 0
19 NEQ
20 BZE 49 while A <> 0
22 PSH -1
24 PSH -2
26 GTR
27 BZE 33 if A > LARGEST
29 PSH -1
31 POP -2 LARGEST := A
33 PSH -1
35 PSH -3
37 LSS
38 BZE 44 if A < SMALLEST
40 PSH -1
42 POP -3 SMALLEST := A
44 ADR -1
46 INN read A
47 BRN 15
49 NLN output answers
50 PSH -3
52 PRN print SMALLEST
53 PRS ' is the smallest and '
55 PSH -2
57 PRN print LARGEST
58 PRS ' is the largest'
60 NLN
61 HLT
; comments are allowed on lines starting with ;
; program to examine the hailstone sequence
; P.D. Terry, Rhodes University, 2000
0 DSP 3 Term is at Mem[BP-1], N is at Mem[BP-2]
2 PRS 'What is the first number? '
4 NLN
5 ADR -1
7 INN Read(Term)
8 PSH -1
10 ABS
11 POP -1 Term := ABS(Term)
13 LIT 1
15 POP -2 N := 1
17 PSH -1
19 PRN Write(Term)
20 NLN WriteLn
21 PSH -1
23 LIT 1
25 GTR
26 BZE 61 WHILE Term > 1 DO BEGIN
28 ADR -2
30 INC N := N + 1;
31 PSH -1
33 ODD
34 BZE 48 IF ODD(Term)
36 LIT 3 THEN
38 PSH -1
40 MUL
41 LIT 1
43 ADD
44 POP -1 Term := 3 * Term + 1
46 BRN 55
48 PSH -1 ELSE
50 LIT 2
52 DVD
53 POP -1 Term := Term / 2;
55 PSH -1
57 PRN Write(Term);
58 NLN WriteLn;
59 BRN 21 END;
61 PSH -2
63 PRN Write(Terms)'
64 PRS ' terms' Write(' terms');
66 NLN WriteLn;
67 HLT END.
Although two groups guessed correctly what MYSTERY.STK did, I am not convinced that they really worked out how it worked. It was none other than that old favourite, the Sieve of Eratosthenes, written to do the same thing over and over again, 200 times in fact.
Several people did the obvious thing - simply knocked out (commented out) the calls to the inbounds function to produce a dangerous, but faster interpreter. One can knock out the calls to the tracing routine, and speed up the IND opcode as well. Note that maximum speed is obtained by knocking out the calls to the function, not by calling a function that simply returns immediately, as one or two groups tried.
Results are quite interesting. On my system (a 200MHz Pentium) I got the following timings. OPTIMUM.STK was a version with PSH/POP operations which resulted in even less code. The times are given in seconds, and one can see that omitting the calls to inbounds speeds things up by about 30%:
C++ versions
Mystery.stk Optimum.stk
1000
full checks 7.37 5.47 0.74
no stack chk 5.09 3.61 0.71
2000
10.14 7.22 0.71
Pascal code (or at least when Paranoid Pat compiles it) incorporates checks that array bounds are not exceeded. It is possible to tune the Pascal compiler to omit these checks (C++ compilers, of course, never build in such checks; they cannot, because arrays in C++ are really just "syntactic sugar" around unguarded pointers). Now here is a thing! When I did this I found the Pascal version of the interpreter to be about 220% faster than the C++ version. Since the source code for the C++ and Pascal versions is actually very similar. This difference is thus almost entirely due to the very high quality of translation to 8086 machine code achieved by Turbo Pascal. The version we use is about 10 years old, but it knocks spots off almost every other DOS based compiler I have ever seen - and it compiles Pascal to this very efficient code very quickly too.
Pascal versions
Mystery.stk Optimum.stk
1000
full checks 16.09 11.49 0.71
no stack chk 9.53 6.67 0.69
fastest 2.40 1.65 0.69
2000
4.54 3.16