Hand in this prac sheet on your next practical day, correctly packaged in a transparent folder and with your solutions. This prac sheet forms the "cover sheet". Since the practical will have been done on a group basis, please hand in one copy of the prac sheet for each member of the group. These will be returned to you in due course, signed by the marker, and you will be asked to sign to acknowledge that you have received your own copy.
Your surname: (PRINT CLEARLY) Your prac day: Your student number: (PRINT CLEARLY) Your signature: Your group partners: Other people with whom you collaborated (you need not give tutors' names): Mark awarded: Tutor's signature
The objectives of this practical are to familiarize you with the workings of a simple machine emulator for the pseudo-machine we shall use again later in the course, and to let you gain some experience with the machine and with writing machine code for it. You may work in Pascal or C++.
You will need this prac sheet, your text book, and (probably) the handout defining the Clang language.
Copies of this prac sheet and of the Clang report are also available on the web site for the course.
This week you are required to hand in, besides this cover sheet:
Keep the prac sheet and your solutions until the end of the semester. Check carefully that your mark has been entered into the Departmental Records.
You are referred to the rules for practical submission which are clearly stated on page 10 of our Departmental Handbook. However, for this course pracs must be posted in the "hand-in" box in the secretary's office for collection by Pat Terry.
A rule not stated there, but which should be obvious, is that you are not allowed to hand in another student's work as your own. Attempts to do this will result in (at best) a mark of zero and (at worst) severe disciplinary action and the loss of your DP. You are allowed - even encouraged - to work and study with other students, but if you do this you are asked to acknowledge that you have done so.
There are several files that you need, zipped up this week as they will be in future, in two versions one in PRAC21C.ZIP (C++ version) and the other in PRAC21P.ZIP (Turbo Pascal version). Copy them and unpack them - the quickest way to do this is to use the COPY and PKUNZIP commands from the command prompt.
Now consider the following gem of a Clang program (PALIN.CLN)
PROGRAM Palindrome;
(* Read a sequence of numbers and report whether they form a palindromic
sequence (one that reads the same from either end)
Examples: 1 2 3 4 3 2 1 is palindromic
1 2 3 4 4 3 2 is non-palindromic
P.D. Terry, Rhodes University, 2000 *)
CONST
TRUE = 1;
FALSE = 0;
VAR
List[100], (* the list of items *)
N, (* number of items *)
Low, High, (* indices of items to be compared *)
Item, (* latest item read *)
IsPalindrome; (* Boolean flag *)
BEGIN
N := 0;
Read(Item);
WHILE Item <> 0 DO BEGIN
List[N] := Item;
N := N + 1;
Read(Item)
END;
IsPalindrome := TRUE; (* optimist *)
Low := 0; High := N - 1; (* initial indices *)
WHILE Low < N - 1 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.
You can compile this (CLN PALIN.CLN) at your leisure to make quite sure that it works.
You will observe that it is not very efficient - it makes more comparisons than are needed to establish whether the sequence is palindromic. So see whether you can improve it. Of course you can! See how much better you can make it.
In the prac kit you will find files that give you the minimal assembler and emulator for the stack machine described in chapter 4.4. The files have names like
STKASM.xxx and STKASM.xxx - a simple assembler
STKMC.xxx and STKMC.xxx - an interpreter/emulator
STACKASM.xxx - a driver program
If you compile and make this assembler/interpreter program, it takes as input a "code file" in the sort of format shown in the examples on pages 41 and 42. There are two example programs in the kit, so make up the minimal assembler/interpreter and try to run them. Wow! Isn't Science wonderful?
The easiest way to "make" the Turbo Pascal version is to give the command
TPC /M STACKASM
To make the C++ version either fire up the BC or VC systems, or make use of the "makefiles" supplied in the kit. Either of the commands
MAKE -f BORL.MAK (for the Borland C++ compiler)
NMAKE /f MICRO.MAK (for the Visual C++ compiler)
will compile the various pieces and link them together. We shall probably make considerable use of the "makefile" way of compiling later in the course, so get to know it early on.
Time to do a little more creative work again. Task 4 is to produce an equivalent program to that in Task 2, written directly in the stack-machine language of chapter 4. You may find this a bit of a challenge, but it really is not too hard, just a little tedious, perhaps.
Health warning: if you get the logic of your program badly wrong, it may load happily, but then go beserk when you try to interpret it. You may discover that the interpreter is not so "user friendly" as all the encouraging remarks in the book might have led you to believe interpreters all to be. The supplied emulators will catch some horrors, but not all. You may need to improve them a bit. (Of course, if your machine-code programs are correct you won't need to; after all, "Any fool can write a translator for source programs that are 100% correct".)
Now extend the machine emulator, and the rudimentary assembler on the lines suggested in exercise 4.24, namely to allow for the reading and writing of single character data. This is actually almost trivially easy when you think about it for a minute or two. Modify your simple stack-machine-code program used in task 4 to allow you to do a palindrome analysis of a sentence - that is, a sequence of characters terminated by a period (which does not form part of the sentence; ignore spaces and other punctuation too). Examples of palindromic sentences are
The famous chat up phrase in the Garden of Eden: "Madam, I'm Adam"
The deep religious/philosophical question: "Do Geese see God"
The plaintive cry of the midsummer owl: "Too hot to hoot"
Hint: Adding "instructions" to the pseudo-machine is easy enough, but you must be careful to make sure you modify all the parts of the system that need to be modified. Before you begin, study the code in the definition of the stack machine carefully to see where and how the opcodes are defined, how they are mapped to the mnemonics, and in which switch/case statements they are used. Another trap to beware of is trying to introduce mnemonics or opcodes whose spelling happens to match that of a keyword (like "and" or "int") in the implementation language. You will see that the identifiers used in my code are often of the form CLASS_ident; this is done deliberately to make the code ultimately easier to understand.
(a) The interpreter checks for division by zero, but does no other checking that arithmetic operations will stay within bounds. Improve it to the point where it checks that multiplication will not go out of bounds, bearing in mind that one has to predict overflow, rather than wait for it to occur!
(b) If you examine the code in EG1.STK and EG2.STK - and maybe in your solution to Task 4 - you should observe that the sequences
ADR x
VAL
and
ADR x
(calculations)
STO
are very common. Introduce, implement, and use the two new operations (in modified versions of EG1.STK etc)
PSH A Push Mem[CPU.BP + A] onto stack to form new TOS
POP A Pop TOS and assign Mem[CPU.BP + A] := TOS
(c) If you look at the Clang code above - or indeed at a great many programs - you will see that statements like X := X + 1 or X := X - 1 are very common. C++ even has special operators for doing this (one naive student once told me that this was the reason C++ was far superior to Pascal!) Introduce two special machine operations that could be used to implement this sort of code efficiently.
Hint: Be careful. Don't limit your solution to cases whre it can handle only statements like X++. You might want to have statements like List[N+6]++.
(d) In an earlier prac you wrote a program to explore the Hailstone sequence. Here is a simple version of such a program which, unfortunately, is not syntactically correct Clang, although it is easy enough to see what the author intended.
PROGRAM Hailstone;
(* The simple hailstone series - display the sequence starting from a
given number.
--- extended Clang - this will not compile directly
P.D. Terry, Rhodes University, 2000 *)
VAR
Term, N, Next;
BEGIN
Write('What is the first number? '); Read(Term);
Term := ABS(Term) (* ensure that it is positive *);
N := 1;
Write(Term);
WHILE Term > 1 DO BEGIN
N := N + 1;
IF ODD(Term) THEN Term := 3 * Term + 1 ELSE Term := Term / 2;
Write(Term);
END;
Write(N, ' terms')
END.
Add to your stack machine special operations that could be used to implement the ABS and ODD functions, and translate the above code into a form that your machine can accept, where possible also making full use of the enhanced operations introduced in the earlier parts of this Task.
As is mentioned in the text, the interpreter in the stack machine emulator spends quite a lot of energy in checking that things will not go wrong. Presumably if we wished to live dangerously and in defiance of Mr Murphy, we could speed up the system by removing these checks.
As an experiment, write an alternative stack-machine emulator that omits the checks, and link this into your system and try to measure the increased efficiency, if any. Hint: First copy the STKMC.CPP or STKMC.PAS file to a file of another name so that you do not destroy the fruits of your earlier labours. Then make the changes, and remake the assembler/interpreter system.
To measure the differences might be difficult with small programs, so in the kit you will find a bit of a number cruncher in the file MYSTERY.STK. If you assemble and run this it will ask you for a "limit", which you might supply as, say, 1000, whereafter it runs a number-cruncher which should take a measurable time to complete. Assemble and run this for various values of Limit on the original and modified emulator, and report on your findings.
The more curious among you might wonder what MYSTERY.STK actually does. Like most student programs it is devoid of comments. There is a cash prize of R10 to the first group or person who correctly identifies what the program does - e-mail your guesses to p.terry@ru.ac.za together with an explanation and justification of how you arrived at the solution. Incidentally, you should be able to get even more impressive timings out of the system if you modify MYSTERY.STK to take advantage of the extended opcode set of the new machine.
Something to think about: (you should be thinking about lots of things in this course) What properties of this "machine" have made writing a program of this complexity particularly easy, or particularly difficult?
Have fun, and good luck.