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.
In this practical you are to
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.
Copies of this handout, the cover sheet, the Parva language report, and descriptions of the library routines for input, output, string handling and set handling in Java and C# are available on the course web site at http://www.cs.ru.ac.za/CSc301/Translators/trans.htm.
When you have completed this practical you should understand
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. You are expected to be familiar with the University Policy on Plagiarism, which you can consult at:
http://www.scifac.ru.ac.za/plag.htm
In this practical course you will be using a lot of simple utilities, and usually work at the "command line" level rather than in a GUI environment. Note in particular:
LPRINT Queens.pav Queens.java
The listings come out in a small font which enables long lines to be read easily and with narrow line spacing (so that you get more listing for your money). Please use this utility to produce all listings submitted on this course, as it makes my job of reading the submissions much easier if they are in a standard format.
For this prac it is recommended that you simply work in the Hamilton lab, rather than begging, borrowing or stealing copies of a whole host of software for home use. In future pracs you will mostly use Java only, and the prac kits will contain nearly all the extras you need.
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 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/folder, by using UNZIP.
copy i:\csc301\trans\prac19.zip
unzip prac19.zip
Use UNZIP or WINZIP and not PKUNZIP, as the file contains files with long file names which PKUNZIP cannot handle.
There is a problem with running applications generated by the C# compiler if these are stored on the network drives. This has not yet been resolved, so for those parts of the practical that involve the use of C#, work from the local D: drive instead. After opening a command window, log onto the D: drive, create a working directory and unpack a copy of the prac kit there:
d:
md d:\G01T1111
cd d:\G01T1111
unzip I:\csc301\trans\prac19.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. You will also find various versions of a program for solving the N Queens problem.
You may not be a Pascal expert, but in the kit is a Pascal program SIEVE.PAS that determines prime numbers using a Boolean array to form the "sieve". Study and compile this program - 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). Approximately how large a sieve can each compiler handle (change the CONST declaration to find out)? What is the significance of this limit?
You can produce a slightly faster version of the program by suppressing the index range checks that Pascal compilers normally include for code that accesses arrays:
TPO SIEVE.PAS
for the 16-bit DOS version of Turbo Pascal or
FPO SIEVE.PAS
for the 32-bit Windows version of Free Pascal. How do the sizes of the executables compare?
You may not be a Modula-2 expert either, but examine, and then compile and run the equivalent Modula-2 code in SIEVE.MOD. You can do this quickly using the command
M2C SIEVE (note that the .MOD extension is not quoted here)
or
M2O SIEVE (for the version that suppresses subscript checks)
Make a note of the size of the executables produced (SIEVE.EXE). How do they compare with the Pascal executables? Approximately how big a sieve can the compiler handle? Why do you suppose there is a difference, when the source programs are all so similar?
The kit also includes C and C++ versions of the sieve program. Compile these and experiment with them in the same way:
BCC SIEVE.C (using the Borland compiler in C mode)
BCC SIEVE.CPP (using the Borland compiler in C++ mode)
CL SIEVE.C (using the Microsoft compiler in C mode)
CL SIEVE.CPP (using the Microsoft compiler in C++ mode)
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?
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. You can also compile a Java program directly from the command line
javac Sieve.java (using the (slow) JDK compiler)
jikes Sieve.java (using the (fast) Jikes compiler)
You can compile the C# version of the sieve program from UltraEdit or from the command line:
csharp Sieve.cs
(You will have to do this on a local drive!) Make a note of the size of the executable produced (SIEVE.EXE). How does it compare with the other executables? How big a sieve can you handle?
On the WWW you will find a description of Parva, a toy language very similar to C, and a language for variations on which we shall develop a compiler and interpreter later in the course. The main difference between Parva and C/Java/C# 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. You may use UltraEdit, or use a command line command:
parva Sieve.pav simple error messages
parva -o Sieve.pav slightly optimized code
parva -l Sieve.pav error messages merged into listing.txt
You will have to do this on the local D: drive.
The demonstration program SIEVE.PAV in the kit has a few fairly obvious errors. Learn Parva by correcting the errors until the program runs correctly. Once again, experiment to see how large a sieve you can set up.
It may help amplify the material we are discussing in lectures if you put some simple Modula-2 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 translates 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 QUEENS.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. Most simply, run the compilers directly from the command line:
BCC SIEVE.C EASYIO.C X2C.C
BCC QUEENS.C EASYIO.C X2C.C
(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.
In the kit you will also find various equivalent programs that solve the famous N Queens problem. These use a back-tracking approach to determine how to place 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 safely on a 4 * 4 board:
.---------------.
| | | Q | |
|---+---+---+---|
| Q | | | |
|---+---+---+---|
| | | | Q |
|---+---+---+---|
| | Q | | |
`---=---=---=---'
Compile one or more of these programs and try them out. For example
FPC QUEENS.PAS
QUEENS
There are two versions written in each of Pascal, Modula-2, Java and C#. One version uses parameters to pass information between the routines, the other version uses global variables. At some stage you could usefully spend a little time trying to work out how the programs come up with the solutions.
Complete the table on the hand-in sheet to determine the number of solutions as a function of N. Do you see a pattern in this?
Different compilers - even for very similar programs - can produce code of very different quality. In particular "interpretive" systems (of which the Parva implementation is one example) produce programs that run far more slowly than do "machine" or "native" code systems. Carry out some tests to see these effects for yourselves, and how severe they are, by comparing the execution times of some of the programs.
Summarise your findings on page 2 of the cover sheet, explaining briefly how you come to the figures that you quote. Do the N Queens programs using parameters perform better/worse than those using global variables? Is Java better/worse than C# (the source code in each case is almost identical)? Do 16-bit compilers fare better or worse than 32-bit compilers?
Hint: the machines in the Hamilton Labs are very fast, so you should try something like this: modify the programs to comment out nearly all 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, or measuring the speed of I/O operations), and then run the programs and time them with a stop watch. Choose sizes for the sieve or chessboard (and a suitable number of iterations) that will produce measurable times.
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 a language we shall meet again, solve the following problem using Parva:
Suppose N is a positive number that starts a sequence defined by the following rules: If a term M is odd, the next term in the sequence is 3M + 1. If a term M is even, the next term is M / 2. The sequence terminates when M = 1. For example, the sequence that starts with N = 6 is as follows:
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 L 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 L 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.
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. His experience of watching the current generation of students suggests 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! This problem and the next one can be solved in just a few lines of code if you think them through carefully before you start to code.
Remember a crucial theme of this course - "Keep it as simple as you can, but no simpler".
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 new sequence
1 3 5 7 9 11 13 15 17 19 21 23 25 27 ...
and now removing every third number generates the new sequence
1 3 7 9 13 15 19 21 25 27 ...
and removing every fourth number from this sequence produces the new 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 generated the sequence 1 3 7 9.
The numbers which survive the culling process indefinitely are deemed to be "lucky".
Write a Parva program to determine the lucky numbers less than some number provided as input data.
Hint: Write a function 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.
A recurrent problem that students have is to check timetables for clashes. Wouldn't it be nice if we had programs that could do this for us?
Well, of course we have, if we are prepared to write them. In the prac kit you will find a data file that describes the Rhodes Timetable, and a program (originally written in C#; you will have to run it from the D: drive) CLASH.EXE that reads this file, and then allows you to type in pairs of subjects, for each of which it will report whether there are any clashes, and when these occur. A session with the program might go something like this
D:>CLASH Subject 1 (or STOP) ? csc 1 Subject 2 (or STOP) ? gog 2 CSC 1 Mon 1 Tue 2 Wed 3 Thu 4 Fri 5 GOG 2 Mon 3 Tue 4 Wed 5 Wed 7 Wed 8 Wed 9 Wed 10 Thu 1 Fri 2 0 clashes Subject 1 (or STOP) ? csc 1 Subject 2 (or STOP) ? gog 1 CSC 1 Mon 1 Tue 2 Wed 3 Thu 4 Fri 5 GOG 1 Tue 2 Wed 3 Thu 4 Fri 5 4 clashes Tue 2 Wed 3 Thu 4 Fri 5 Subject 1 (or STOP) ? stop D:>
Your biggest task this week is to write a Java program that achieves the same effect.
The program involves various aspects of reading and parsing data - that is, recognizing components of data buried in a large input file and extracting them for further processing. Parsing is a fundamental component of programming language translation as well.
Part of the data file is listed out below. You will need to study it before you begin.
This particular problem is neatly solved if you make use of sets - each subject has a set of fixed time table slots (and a possible set of alternative time-table slots, but we can ignore those; you can also ignore any periods out of the range 1 ... 10 in any day). So the program can sensibly make use of an array of suitable records or structures, one field of which is a set of integers.
You will need to become acquainted with various library classes to solve this problem. A simple sample program using some of the library routines can be found in the kit as the program SampleIO.java. Descriptions of these and other library routines can be found on the course website.
Warning - although this exercise is actually quite easy, I suspect that this may be a non-trivial problem for many of you. So make sure you understand what is required before you rush in to writing code. Discuss the approach you will take with the demonstrator team, and with each other.
August 21 2003 ; date of last modification
; data file used by the CLASH program 2003 (all semesters too)
;
; this file should only be edited with a "flat ASCII" editor, not a word processor.
;
; Format is as follows - spacing important before the "periods" start
; First line has the date of modification (special case)
;
; Line starting ; in column 1 is just commentary
;
; Sem Mnemonic Size Venue Name Periods terminated with .
;
; Sem = blank (both) or 1/F (1st) or 2/S (second) or + when used only for venue allocation
;
; Col 2 non blank if you want to highlight changes
;
; Mnemonic of 7 chars is the one that is typed into the program
; Followed by guesstimate of size and 5-letter venue code
; Some Sizes are fudged!
; List of timetabled periods follow (starting column 52), terminated with .
; Period codes are day/period eg 24 means day 2, period 4
; Period 10, 11 ... represented by A, B .. eg 2A means day 2, period 10
;
; 34 - fixed lecture period
; L34 - Alternative lecture period
; P16 - Fixed practical period
; A67 - Alternative prac period
; T34 - Alternative Tutorial period
;
; Mnemonic Size Venue Full Name Cryptic stuff with . at end
; vvvvvvv vvv vvvvv vvvvvvvvvvvvvvvvvvvvvvvvvvvv vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
ACC 1 2 ED/CH Accounting 1 L23 L24 L33 L35 L42 L46 A17 A18 A27 A28 A47 A48 A57 A58 .
ACC 1F 40 Eco38 Accounting 1F 17 18 24 33 46 54 .
ACC 2 180 GLT Accounting 2 12 34 45 51 A27 A28 A37 A38 A47 A48 .
ACC 4 35 Acc Accounting 4 .
AFN 1 3 Afr Afrik/Nederlands 1 14 25 31 42 .
CSC 1 1 CheMA Computer Science 1 11 22 33 44 55 A17 A18 A19 A1A A27 A28 A29 A2A A37 A38 A39 A3A A57 A58 A59 A5A .
CSC 2 120 EdenB Computer Science 2 13 24 35 41 52 37 38 39 3A .
CSC 3 70 Glg11 Computer Science 3 12 23 34 45 51 47 48 49 4A .
DRA 1 100 Eco B Drama 1 22 33 55 A19 A1A A29 A2A A39 A3A A49 A4A .
F EAR 101 3 Gog11 Earth Science 101 22 33 44 55 A17 A18 A19 A1A A57 A58 A59 A5A .
;
; These next are not really "subjects" but are useful in marking special
; periods when fiddling
MON 1 1 11 .
TUE 1 1 21 .
WED 10 1 3A .
THU 10 1 4A .
FRI 10 1 5A .
You may also like to experiment with the program WHEN.EXE in the prac kit, which creates a graphical output of a timeteble for selected subjects and explores whether apparent clashes can be resolved. The file KEY summarizes the mnemonic codes used for choosing subjects in the WHEN and CLASH programs.
import java.util.*;
import Library.*;
class SampleIO {
public static void main(String[] args) {
if (args.length != 2) {
System.out.println("missing args");
System.exit(1);
}
InFile data = new InFile(args[0]);
if (data.openError()) {
System.out.println("cannot open " + args[0]);
System.exit(1);
}
OutFile results = new OutFile(args[1]);
if (results.openError()) {
System.out.println("cannot open " + args[1]);
System.exit(1);
}
int total = 0;
SymSet mySet = new SymSet();
SymSet smallSet = new SymSet(new int[] {1, 2, 3, 4, 5});
String smallSetStr = smallSet.toString();
int item = data.readInt();
while (!data.noMoreData()) {
total = total + item;
if (item > 0) mySet.incl(item);
item = data.readInt();
}
results.write("total = ");
results.writeLine(total, 5);
results.writeLine("unique positive numbers " + mySet.toString());
results.writeLine("union with " + smallSetStr
+ " = " + mySet.union(smallSet).toString());
results.writeLine("intersection with " + smallSetStr
+ " = " + mySet.intersection(smallSet).toString());
}
}