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
In this practical you are to reacquaint yourselves with the Braae Lab, with various languages, editors and compilers, including C++, meet the Clang programming language, and learn to program with "sets". The exercises for this week are not really difficult, although they may take longer than they deserve simply because you may be unfamiliar with the systems.
You will need this prac sheet and two other handouts, one defining the Clang language, and the other summarizing input and output in C/C++ using the stdio library, with which you may not be familiar.
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.
Executable sizes:
TASK 2
Turbo Pascal: SIEVE.PAS SIEVE1.PAS
JPI Modula-2 SIEVE.MOD SIEVE1.MOD
TASK 3
Using cin and cout:
Borland C: SIEVE.CPP SIEVE1.CPP
Microsoft C: SIEVE.CPP SIEVE1.CPP
Using scanf and printf:
Borland C: SIEVE.CPP SIEVE1.CPP
Microsoft C: SIEVE.CPP SIEVE1.CPP
TASK 5
Using scanf and printf after translation from Modula-2 by X2C
Borland C: SIEVE.C SIEVE1.C
Microsoft C: SIEVE.C SIEVE1.C
Remenber to comment on the differences.
TASK 6
How many solutions are there to the N Queens problem? Do you see a trend?
2 3 4 5 6 7 8 9 10 11 12
.------------------------------------------------------.
| | | | | | | | | | | |
`------------------------------------------------------'
How did you measure the differences in speed between the Clang and Pascal
versions of the N Queens program? What result did you obtain?
As explained in an earlier handout, we shall make use of "zipped" prac kits throughout the course; you will typically find sources for each week's prac in a file PRACn.ZIP on the server. Copy PRAC19.ZIP and XTACY.ZIP needed for this week, either directly from the server on I:\CSC301\TRANS, or using the WWW link, and extract the sources when you need them into your own directory by using PKUNZIP.
In the prac kit you will find various versions of a famous program for finding a list of prime numbers using the method known as the Sieve of Eratosthenes (which you might have seen, I hope, at some stage in the last two years).
The sieve in Pascal
You may not be a Pascal expert, but in the kit, for interest, are two equivalent programs, SIEVE.PAS and SIEVE1.PAS, that determine prime numbers, one using a Boolean array, and the other using "sets". Pascal has "sets" as a standard feature of the language. Study and compile these programs - you can do this from the command line quite easily by issuing a command like
TPC SIEVE.PAS
and make a note of the size of the executables in each case (SIEVE.EXE and SIEVE1.EXE).
The Sieve in Modula-2
Nor may you be a Modula-2 expert, but examine, and then compile and run the equivalent Modula-2 code in SIEVE.MOD and SIEVE1.MOD. You can do this quickly using the batch files M2M.BAT (make) or M2C.BAT (compile) and M2L.BAT (link) in the kit, for example:
M2M SIEVE (note that there is no .MOD extension here)
or
M2C SIEVE
M2L SIEVE
Make a note of the size of the executables produced (SIEVE.EXE and SIEVE1.EXE). How do they compare with the Pascal executables? Why do you suppose there is a difference, when the source programs are all so similar?
This exercise is aimed at refreshing your memories and also teaching you a bit more about C++. In the kit you will find equivalent programs to those you have already seen: SIEVE.CPP and SIEVE1.CPP.
These programs have been written using the cin and cout streams that you should remember from earlier courses.
Compile these programs under the environments you know - or, more simply, use QEdit as your editor and then compile from within QEdit, or from the command line by issuing one or other command like
BCC SIEVE.CPP (using Borland C++)
CL SIEVE.CPP (using Microsoft C++)
Once again, make a note of the size of the executables of the programs.
Since Coco/R, the compiler-generator tool that we shall use extensively later on, performs its I/O using scanf and printf, carry on to write slightly modified versions of both programs, using these functions for I/O, rather than cin and cout. Refer to the handout if you have not used these functions before. Incidentally, the header file misc.h is useful in all program in this course. Study it, and also set.h, which has the code for the set template class that we shall used repeatedly.
Once again, make a note of the size of the executables, and in particular, compare them with the earlier versions. Can you think of any reason why the differences are as you find them?
In the handout you will find a description of Clang, a toy language very similar to Pascal, and the language for variations on which we will probably be developing compilers and interpreters later in the course. The main difference between Pascal, Modula-2 and Clang is the absence of "types" in Clang.
Learn the Clang system by reading the handout and trying the system out on the sieve program. While you do this try to get a feel for the differences in speed of using a native code compiler (like that for C++) and an interpreter (CLANG).
There are various ways to compile Clang programs. You can run the free-standing compiler CLN.EXE, or you can run a version that uses QEdit as an Interactive Development Environment (IDE), which may be easier:
To run CLANG free-standing:
Prepare your source program in a file with a .CLN extension, and then issue the command (from a DOS prompt)
CLN XXX.CLN
An error listing appears in the file XXX.LST if the compilation is unsuccessful.
To run CLANG from within QEdit (preferred):
In the prac kit the demonstration program SIEVE.CLN has a few very obvious errors. You might like to try the environment out on this program, correcting the errors until the program runs correctly.
QEdit is the recommended editor for use on this course, as it is also configured to invoke various other compilers when one uses <CTRL-F9> or <CTRL-F10>, depending on the extension. <CTRL-F9>, with an extension of .PAS invokes the Pascal compiler, for example, and for extensions of .C or .CPP should invoke the Microsoft C compiler (provided the DOS paths are correctly set). <CTRL-F10> will invoke the Borland compiler.
It may help amplify the material we are discussing in lectures if you put some simple programs through a high- level translator we have available, and then look at, and compile, the C code to see the sort of thing that happens when one performs automatic translation of a program from one high-level language to another.
We have a demonstration copy of a system (Russian in origin), that runs under DOS and will translate Modula-2 or Oberon-2 source code into C. The system is called Extacy (a poor pun on "X to C", it seems). Whether or not the C one obtains is usable depends, obviously, on having C translations of all of one's Modula-2 libraries as well. In principle all one has to do is convert these libraries using the same system, of course. Some very simple libraries come with the demonstration kit, and we have produced one or two more, but we would have to pay many Roubles and do an awful lot of work to get the system fully operational.
XC =m SOURCE.MOD
will produce all the .H and .C files needed for a "make" of the parent program SOURCE.MOD
Convert the sample programs in this kit (SIEVE.MOD and SIEVE1.MOD and the various support modules to C, and then use whatever C system you are most familiar with to compile and run the resulting code. Or, more simply, run the compilers from the command line:
BCC SIEVE.C EASYIO.C X2C.C
BCC SIEVE.OBJ EASYIO.OBJ X2C.OBJ
(or the equivalent using CL in place of BCC.)
Take note of, and comment on, such things as the kind of C code that is generated (is it readable; is it anything like you might have written yourself?), and of the relative ease or difficulty of using such a system. You might also like to comment on the size of the object code produced by our C and Modula-2 compilers, and on the time it takes to compile and link programs written in C or in Modula-2.
The reason for working in another directory is to ensure that you don't edit, change, or otherwise get corrupted versions of files like EASYIO.DEF which will only cause you problems with other Modula-2 programs in this prac.
Nothing so far should have extended your programming talents very much. To get the brain cells working a little harder, and to learn more about the language we shall often meet again, have a go at solving the following problems using the Clang language:
6 3 10 5 16 8 4 2 1
and in this particular case the length of the sequence is 9. Write a function procedure that, given N, will return the length of the sequence beginning with N. Then continue to write a little program that uses this function to determine the smallest positive integer N that produces a sequence length greater than K, where K is a number used as input data. For example, for K = 12, the result should be N = 7. 7 is the smallest positive integer that generates a sequence with more than 12 members.
This problem can (clearly) be solved by first sorting the long array (or a copy of the long array) and then looking at the last N elements. However that is tedious. Devise a system that does not sort, but simply looks for the largest element, the second largest element and so on.
In the kit you will find a Pascal solution to the N Queens problem discussed in this week's tutorials. This uses a "back-tracking" approach to solve the problem of placing N Queens on an N * N chess board in such a way that no Queen threatens or is threatened by any other Queen - noting that a Queen threatens another Queen if the two pieces lie on a common vertical, horizontal or diagonal line drawn on the board. Here is a solution showing how 4 Queens can be placed on a 4 * 4 board:
.---------------.
| | | Q | |
|---+---+---+---|
| Q | | | |
|---+---+---+---|
| | | | Q |
|---+---+---+---|
| | Q | | |
`---=---=---=---'
Compile this program and try it out. Simply use the commands
TPC QUEENS
QUEENS
Next, modify the program so that it counts the number of solutions for a given N, and complete the little table on page 2 to give this information.
Produce a Clang version of the program and check that it works correctly (I/O in Clang at this stage is a bit perverse; we can fix that in a later practical, perhaps).
You have been told that "interpretive" systems (of which Clang is an example) produce programs that run far more slowly than do "native code" systems. Carry out some tests to see if you can see how much more slowly the Clang version runs than the Pascal one. Fill in this information on page 2, explaining briefly how you come to the figures that you quote.
Later in this course you will see that the idea of a "set" (in the mathematical sense) occurs frequently in compiler and parser theory and practice. Time to get more familiar with these concepts. Here is a nice application to keep you busy for a few hours:
A recurrent problem that students have is to check timetables for clashes. In fact, in the last few weeks Yours Truly has expended much energy in trying to devise a new, improved timetable for next year. You can read all about it at http://www.scifac.ru.ac.za/timetable/. Perhaps you should do so if you will still be an undergraduate next year, as you might well be if you don't do these pracs properly!.
Wouldn't it be nice if we had programs that could do clash checking for us, or find out whether one of those cute curricula that has Economics 1 (with a choice of alternatives), Psycho 1 (with a choice of alternatives), Computer Science 1 (with fixed times) and Management 2 (with fixed lectures and a choice of tut times) can actually be made to work, and if so, how?
Well, let's make a start on developing a system that tries to do just that. It will need to be driven by some sort of data file. In the kit you will find a file DATA with the first lines reading
A 1 3 A5 A6 .
B A2 A4 .
C 1 .
.
The idea here is that subject A has lectures in periods 1 and 3, and a choice of one of two alternatives (tuts?) in period 5 or 6; B has alternatives in periods 2 and 4; C has only one fixed lecture in period 1, and so on. Data for a subject is given one line per subject; the subject is denoted by a single letter, the rest of the line is free format ending with a period, and the last line is marked with a single period only. Assume that the periods are numbered 1 through 9.
The program should read this data, and then invite the user to type a list of subjects, terminated with a period, for example
B C .
and should then explore the curriculum. In this case there are two possibilities: C would be taken in period 1 , but B could be taken in either period 2 or 4. A request to timetable
A C .
should, of course, fail.
If this does not make sense, try running the program CLASHES.EXE from the prac kit and see the effect I am trying to achieve.
So how do we relate all this to sets, C++, compilers, backtracking, and the Meaning of Life? Well, an internal data structure could store two sets of periods for each subject (one for the fixed times, one for the alternative times), and by using a backtracking algorithm (not that different from the one used for the N Queens problem) we could determine how to place the subjects on the "board" (that is, in the 9 periods of the day) in such a way that none of them threaten (clash with) any other subject.
Okay, okay, Pat Terry's problems are reputed to be hard. They only get very hard if you don't think very carefully about what you are trying to do, and they get much easier if you think hard and spend time discussing the solutions with the tutors or even the Tyrant himself. My experience of watching the current generation of students is that you get beguiled by glitzy environments and think that programs just "happen" if you can think of what to click on next. Don't just go in and "hack". It really does not save you any time, it just wastes it!