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.
In this practical you are to reacquaint yourselves with the Braae Lab, working from a command line prompt, 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 the prac sheet, the Clang report, and the cover sheet are also available on the web site for the course, and spare copies of the cover sheet are available on top of the hand-in box.
This week you are required to hand in, besides the cover sheet:
Keep the cover sheets 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.
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 PRAC14.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, as in
PKUNZIP PRAC14.ZIP
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 were written to use 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 UltraEdit and then compile from within UltraEdit, or from the command line by issuing one or other command like
BCC SIEVE.CPP (using Borland C++ 5.5)
CL SIEVE.CPP (using Microsoft C++)
Once again, make a note of the size of the executables of the programs.
You can switch to using Borland C++ 3.1 by issuing the command
USE C:\BC31\BIN;
which will alter the DOS "path" to prefer the 16 bit 3.1 compiler over the 32 bit 5.5 compiler. To switch back again issue the command
UNUSE C:\BC31\BIN;
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 many programs in this course. Study it, and also set.h, which has the code for the set template class that we shall use repeatedly.
Once again, try out all three compilers, and make a note of the size of the executables, and in particular, compare them with the earlier versions. Can you think of any reasons 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 a highly 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.
Experiment with the various versions of the Sieve programs to see how large a data structure is allowed by each compiler system. Even if you are not familiar with all these languages, the source code for each version is so easy to understand (?) that it should be obvious what to change! Comment in your submission on your findings. Why, for example, do you suppose these limits are set, if at all? Would the limits pose problems for serious programmers?
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
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.
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 code you might have written yourself - if not, why not?), 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.
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 probably meet again as we develop a compiler for it, have a go at solving the following problem:
Consider a sequence originally containing the N ordinal numbers
1 2 3 4 5 6 7 8 9 10 11 12 13 14 ... N
Removing every second number produces the sequence
1 3 5 7 9 11 13 15 17 19 21 23 25 27 ...
and now removing every third number generates the sequence
1 3 7 9 13 15 19 21 25 27 ...
and removing every fourth number from this produces the sequence
1 3 7 13 15 19 25 27 ...
This process continues indefinitely, or more exactly, as long as numbers are still there to be removed. For example if N = 12 the process would terminate once we had reduced the sequence to 1 3 7.
The numbers which survive the culling process indefinitely are deemed to be "lucky".
Write a procedure that will generate a list of such numbers in an array parameter when supplied with an upper limit N, and use this in a program that displays such a list.
Solve this problem in either Pascal or C++, and then solve it in Clang as well.
You (should have) learned all about sorting in your advanced programming course last year. But have you forgotten which is better - the infamous "bubble" sort or the infamous "insertion" sort?
Here's a fun way to find out. Write a Clang program that will
So you will need something like the outline below. You should experiment with using semaphores to protect any critical regions or to provide any synchronization required.
PROGRAM CompareSorts;
(* declare global variables if needed *)
PROCEDURE Increment
(* increment the assignment counter safely *)
PROCEDURE BubbleSort (* suitable parameters *)
(* use the bubblesort algorithm *)
PROCEDURE InsertionSort (* suitable parameters *)
(* use the insertion sort algorithm *)
FUNCTION IsOrdered (* suitable parameters *)
(* return true or false *)
BEGIN
(* Read in data and set things up *)
COBEGIN
BubbleSort;
InsertionSort
COEND
(* Write(IsOrdered ...) *)
END.