Hand in this prac sheet before lunch time on your next practical day, correctly packaged in a transparent folder with your solutions and the "cover sheet". Please do NOT come to a practical and spend the first hour printing or completing solutions from the previous week's exercises. Since the practical will have been done on a group basis, please hand in one copy of the cover 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.
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 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 13 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 PRAC15C.ZIP. Copy them and unpack them - the quickest way to do this is to use the COPY and PKUNZIP commands from the command prompt.
Start off by considering the following gem of a Clang program (SEARCH0.CLN)
PROGRAM Search;
(* Read a list of 10 numbers, and then a further list terminated by 99.
Find where the numbers in the second list appear in the first list.
P.D. Terry, Rhodes University, 2001 *)
VAR
List[10], Item, I;
BEGIN
(* First read 10 numbers into List[1] .. List[10] *)
I := 1;
WHILE I <= 10 DO BEGIN
Read(List[I]);
I := I + 1
END;
(* Now start the interrogation loop *)
Read(Item); (* first search item *)
WHILE Item <> 99 DO BEGIN
I := 1;
WHILE List[I] <> Item DO I := I + 1;
Write('Found in position', I);
Read(Item) (* next search item *)
END
END.
You can compile this (CLN SEARCH0.CLN) at your leisure to make quite sure that it works.
Firstly, decide why it is an awful program. If you can't see why, try running it - run it anyway, and see if you can break it. What happens? (By "break" I mean "can you run it with some sort of data that allows it to work, and then run it with some data that makes it bomb out?")
In the prac kit there is a better version of the program in the file SEARCH1.CLN. Compile that one, and see if you can break it. If not, you haven't thought hard enough!
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 the names
STKASM.H and STKASM.CPP a simple assembler
STKMC.H and STKMC.CPP an interpreter/emulator
STACKASM.CPP 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 in section 4.4.3. 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?
To "make" the program from the C++ sources either fire up the monster BC or VC systems, or make use of the "makefiles" supplied in the kit. Either of the commands (from the command line)
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 5 is to produce an equivalent program to that in Task 3, but 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".)
The rest of the tasks in this prac require you to understand the machine emulator, and to extend it to have a few more operations.
Is it possible to accomplish Boolean (NOT, AND and OR) operations using the current instruction set? You might decide that the machine can effectively do this anyway, but, too bad, this is not a democratic course!
Add operations to the machine that will allow you to read and write Boolean values and also allow you to perform the logical operations. We effectively want to be able to add machine opcodes like INB and PRB (read Boolean, write Boolean) and AND, OR and NOT.
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 (even though this technique, when used by the X2C system seemed to cause some students to think that it produced "unreadable code").
You might try out your system by hand-coding the following program into your (extended) machine code (the high-level code is in BOOL1.CLN, but it won't compile with the current version of Clang. Maybe in a few weeks time ... ).
PROGRAM BooleanDemo;
(* This won't compile, but the idea should be obvious
P.D. Terry, Rhodes University, 2001 *)
BOOL
X, Y;
BEGIN
Read(X, Y);
Write(X, Y, NOT X, X AND Y, X OR Y)
END.
And then for something rather more challenging, try hand-coding and running this one which is intended to print out a little truth table to demonstrate De Wossname's law (BOOL2.CLN)
PROGRAM DeMorganDemo;
(* This won't compile, but the idea should be obvious
P.D. Terry, Rhodes University, 2001 *)
BOOL
X, Y;
BEGIN
Write(' X Y (X.Y)'' X'' + Y''');
X := FALSE;
REPEAT
Y := FALSE;
REPEAT
Write(X, Y, NOT (X AND Y), NOT X OR NOT Y);
(* Keen types might also try
Write(X, Y, NOT (X OR Y), NOT X AND NOT Y);
*)
Y := NOT Y;
UNTIL Y = FALSE (* again *);
X := NOT X
UNTIL X = FALSE (* again *)
END.
Finally, have a look at SEARCH2.CLN, which is yet another variation on the searching program given earlier. Would this benefit from the new found ability to use Boolean operations. If so, how; if not, why not? (You might try using them in a slightly modified version of the code you wrote in Task 5, for example, or you might like to discuss why you would not use them in such a translation, but yet still match the algorithm demonstrated in SEARCH2.CLN).
I really do admire our CS students. They somehow manage to learn programming, even though the C family of languages allows them no protection if they try to access array elements that don't really exist. Ah well, it's like trying to learn to drive a motor car with no brakes. Exciting, but often tragic.
The present interpreter provides an array indexing opcode that insists on array bound checks, as you should have realised when you did Task 5. But suppose the machine had an (alternative) opcode that did no such check. No, don't just suppose - go out and extend the machine to give it such an opcode, and then modify your source code to use it. Shorter code, I guess? Faster execution too, probably. Why should it be shorter and faster?
Hopefully you will have realised by now that one great advantage emulators gives one is the freedom to design a machine to match the sort of things you would like it to do. You don't quite have that freedom on "real" hardware, of course.
So here is a fun thought. Most real machines have "condition codes" or "status bits" (like the CPU.Z and CPU.P ones that you learned about in out previous encounters last year). The present machine has no such things. But we could easily add them if we wanted to do so.
No, I don't suppose you want to do so, but as I said earlier, this is not really a democratic course. Suppose you added status flags to the machine and then modified the semantics of the opcode set, or (preferably) added to it, so as to be able to take advantage of them. How would you do this, and what would this buy you when you came to write code for it?
You can try to answer this question without doing any real coding, but then you will have to explain carefully how you come to whatever conclusions you reach. And you will have to think quite hard - but by this stage of your University careers you should be able to do that, and to argue convincingly! (Which is Pat Terry-speak for "please don't think you can write two lines of utter rubbish three minutes after you were supposed to hand the prac in, and try to bluff me that you know what is going on"!).
Have fun, and good luck.