This prac is due for submission by lunch time on your next practical day, correctly packaged in a transparent folder as usual. Pracs should please be deposited in the hand-in box outside the lab. Only one set of listings is needed for each group, but please enclose as many copies of the cover sheet as are needed, one for each member of the group. These will be returned to you in due course.
This year we shall be experimenting with the scheme used in IS whereby members of a group will help decide how the marks are to be apportioned to each member. More details later!
In this practical you are to acquaint yourselves with some command line utilities, with various editors, interpreters and compilers, and play with various languages including C++, Java, Pascal, Modula, Clang and Parva. 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 the handout summarizing input and output in C/C++ using the stdio library, with which you may not be familiar.
Copies of these handouts, the cover sheet and the Clang and Parva language reports are also available on the web site for the course at http://www.cs.ru.ac.za/CSc301/Translators/trans.htm.
This week you are required to hand in, besides the cover sheet:
Keep the cover 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 outside the laboratory and not given to demonstrators.
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.
In this practical course you will be using a lot of simple utilities, and frequently (usually!) work at the "command line" level rather than in a GUI environment. Note in particular:
Many command line utilities will not work correctly unless you obey the following rules
We shall make use of "zipped" prac kits throughout the course; you will typically find sources for each week's prac in a file pracNN.zip on the server. Copy prac07.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/folder, by using UNZIP.
UNZIP prac19.zip
Use UNZIP or WINZIP and not PKUNZIP, as the file contains files with "long file names" which PKUNZIP cannot handle.
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
for the 16-bit DOS version of Turbo Pascal or
FPC SIEVE.PAS
for the 32-bit Windows version of Free Pascal.
Make a note of the size of the executables in each case (SIEVE.EXE and SIEVE1.EXE). How large a sieve can each program handle (change the CONST declaration to find out)? Why do you suppose this limit exists?
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 command
M2M SIEVE (note that there is no .MOD extension here)
or
M2M SIEVE1
Make a note of the size of the executables produced (SIEVE.EXE and SIEVE1.EXE). How do they compare with the Pascal executables? How big a sieve can each handle? 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, and see how big a sieve you might handle.
To use the Borland 16 bit compiler, issue the command
USEBC31
(once) before editing/compiling. This clobbers the system a bit, and you may like to do this in its own window.
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 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?
You are required to hand in listings of the C++ programs that use the printf/scanf functions for input and output. You might do this with a command like
LPRINT SIEVE3.CPP SIEVE4.CPP
On the WWW you will find a description of Clang, a toy language very similar to Pascal, and the language for variations on which we may (as explained in the book) develop 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 studying the language description where necessary, and trying the system out on the sieve program. There are various ways to compile Clang programs (see the notes at the end of the handout).
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. How big can the sieve become?
On the WWW you will find a description of Parva, a toy language very similar to C++/Java, and a language for variations on which we may be develop a compiler and interpreter later in the course. The main difference between Parva and C++/Java is that Parva is stripped down to bare essentials.
Learn the Parva system by studying the language description where necessary, and trying the system out on the sieve program. There are various ways to compile Parva programs (see the notes at the end of the handout).
In the prac kit the demonstration program SIEVE.PAV 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. Once again, experiment to see how large a sieve you could set up.
Time to do something more constructive. Produce a Java version of the Sieve program. The quickest way to do this will probably be to copy and "hack" at the Parva one:
COPY sieve.pav sieve.java
Simple I/O in Java is a bit of a nuisance - but simplicity is what we are striving for. To help in this regard, the prac kit contains source for a Keyboard class with the following static methods.
public class Keyboard
public static boolean endOfLine()
// Returns true if there are no more tokens to read on the input line.
public static void readln()
// Consumes tokens up to next end of line.
public static String readString()
// Returns a string read from standard input.
public static String readWord()
// Returns a space-delimited substring (a word) read from standard input.
public static boolean readBoolean()
// Returns a boolean read from standard input.
public static char readChar()
// Returns a character read from standard input.
public static int readInt()
// Returns an integer read from standard input.
public static long readLong()
// Returns a long integer read from standard input.
public static float readFloat()
// Returns a float read from standard input.
public static double readDouble()
// Returns a double read from standard input.
public static void prompt (String s)
// Prompt s on standard output.
and a simple demonstration program demo.java showing how easy it is to read an integer, for example
int i = Keyboard.readInt();
You are required to hand in a listing of this program. And you are not required or encouraged to write a "fancy" version of the program with GUI interfaces and the like - just a bare bones equivalent of the others.
There are two Java compilers available for your use. The JDK one is called javac and there is also the (much faster) one called jikes. Both of these are conveniently invoked from within UltraEdit (QEdit is not really suited to Java programming). Try both compilers for yourself.
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 came 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 directly 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.
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 two languages we shall meet again, have a go at solving the following problem:
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 or FPC QUEENS.PAS
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 of the cover sheet to give this information.
Produce Clang, Parva and Java versions of the program and check that they work correctly (I/O in Clang at this stage is a bit perverse; perhaps we shall fix that in a later practical).
You have been told that "interpretive" systems (of which Java, Clang and Parva are all examples) produce programs that run far more slowly than do "machine" or "native" code systems. Carry out some tests to see this effect for yourselves, and how severe it is, by comparing the interpreted versions of the programs you have written with the compiled versions. Summarise your findings on page 2 of the cover sheet, explaining briefly how you come to the figures that you quote.
Hint: the machines in the Hamilton Labs are very fast, so you may have to resort to something like this: modify the programs so that they perform the desired computation not once but a fairly large number of times. Take out the output statements (since you are not interested in seeing the solutions to the N Queens problem a zillion times, or a zillion lists of prime numbers), and then run the programs and time them with a stop watch.
Pat Terry's problems are sometimes 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 some of you get beguiled by glitzy environments and think that programs just "happen" if you can guess what to click on next. Don't just go in and "hack". It really does not save you any time, it just wastes it!
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 PARVA free-standing:
Prepare your source program in a file with a .PAV extension, and then issue the command (from a DOS prompt)
PARVA XXX.PAV
There is a 16-bit version that can be invoked with the command
PARVA16 XXX.PAV
To run CLANG or PARVA from within QEdit (preferred):
For this prac I recommend that you simply work in the Hamilton lab, rather than take copies of a whole host of software for home use. Next term we shall set up kits to take home of the software that will be used repeatedly thereafter.