Some general hints
While it is possible to implement a set type in Parva by creating set objects on the PVM heap, as we do for arrays, this leads to code rather more complicated than there is time to develop in a day. It is much easier to have the interpreter create a dynamic heap of set objects, using the generic List type familiar to you from earlier practicals, and the IntSet class which should also be familiar from previous practicals. In other words, every time a set is created in a Parva program, another IntSet object is added to this "heap".
So you will need to study the IntSet class quite carefully if you have never done so previously. You have a summary of the relevant members of this class on the last page of this handout, and the full source of the class in the file Library.cs in the exam kit. You should not have to alter the any of the Library.cs code, so don't make life even more difficult by trying to do this.
Remember that a set is a bit like a bag into which you can toss "elements" of the right sort. Into an IntSet object you can only toss integer values, but that is quite enough for the present exercise.
Specific tasks
What follows is a graded set of suggestions for how you should tackle this project if you are to complete it in the time available. There are other operations one can do with sets, but ignore those.
The source code for each example is supplied in the "examples" folder of your Exam Kit
Step one will be to modify the compiler so that it can recognize the declaration of variables of the set type.
Here are two programs that do only that and only need a few changes to the grammar and table handler. Any code they generate will be pretty uninteresting but you should be able to get snapshots of the symbol table easily. Make sure you understand the tables.
$C+ // declare variables of various types - eg00.pav
void main() {
int i, j;
char ch;
set s1, s2;
set[] sets = new set[4];
$ST // display symbol table
} // main
/******************************************
D:\parva eg00.pav -l
Parva compiler 1.2016 November
Symbol table
i int Variable 4
j int Variable 5
ch char Variable 6
s1 set Variable 7
s2 set Variable 8
sets set[] Variable 9
main void Function 4 0
Parsed correctly
*/
___________________________________________________________________________________________
$C+ // declare parameters of set type - eg01.pav
void SetHandler(set formal, set[] lists) {
set local;
$ST // display symbol table
} // SetHandler
void main() {
set actual;
set[] sets = new set[4];
SetHandler(actual, sets);
$ST // display symbol table
} // main
/******************************************
D:\parva eg01.pav -l
Parva compiler 1.2016 November
Symbol table
formal set Variable 4
lists set[] Variable 5
local set Variable 6
SetHandl void Function 4 2
Symbol table
actual set Variable 4
sets set[] Variable 5
SetHandl void Function 4 2
main void Function 7 0
Parsed correctly
____________________________________________________________________________________________
Step two will be to allow the system to construct empty sets and assign them to set variables or array elements. In this case the generated code starts to become of interest, although it will not seem to do anything when you execute it (unless you trace execution step by step).
$C+ // initialize variables of set type - eg02.pav
void main() {
set s = set{};
set[] sets = new set[14];
sets[7] = set{};
$ST // display symbol table
} // main
/******************************************
D:\parva eg02.pav -l
Parva compiler 1.2016 November
s set Variable 4
sets set[] Variable 5
main void Function 4 0
Parsed correctly
ASSEM
BEGIN
{ 0 } FHDR
{ 1 } CALL 4 call main
{ 3 } HALT all done
{ 4 } DSP 2 main starts here
{ 6 } LDA 4 address of s
{ 8 } CSET create empty set
{ 9 } STO s = set{}
{ 10 } LDA 5
{ 12 } LDC 14
{ 14 } ANEW
{ 15 } STO sets = new set[14]
{ 16 } LDA 5
{ 18 } LDV
{ 19 } LDC 7
{ 21 } LDXA
{ 22 } CSET create empty set
{ 23 } STO sets[7] = set{}
{ 24 } RETV
END.
*/
____________________________________________________________________________________________
Step three will be to allow you to display a set using the WriteStatement. The IntSet class has a ToString() method which you should be able to call from the interpreter. The program below is still not very interesting as the sets in question are empty, but aim for generating the sort of code shown, and for executing it correctly.
$C+ // write out an empty set - eg03.pav
void main() {
set s = set{};
writeLine("set s is ", s);
writeLine("empty set is ", set{} );
$ST // display symbol table
$SD
} // main
/******************************************
ASSEM
BEGIN
{ 0 } FHDR
{ 1 } CALL 4
{ 3 } HALT
{ 4 } DSP 1
{ 6 } LDA 4
{ 8 } CSET
{ 9 } STO
{ 10 } PRNS "set s is "
{ 12 } LDA 4
{ 14 } LDV
{ 15 } PRSET
{ 16 } PRNL
{ 17 } PRNS "empty set is "
{ 19 } CSET
{ 20 } PRSET
{ 21 } PRNL
{ 22 } STACK
{ 23 } RETV
END.
*/
____________________________________________________________________________________________
It gets more interesting from here on. Work on being able to add elements into a set. Start simply with an Incl statement:
$C+ // add elements into a variable of set type - eg04.pav
void main() {
set s = set{};
writeLine(s);
s.Incl(5); // set should now be { 5 }
writeLine(s);
$ST // display symbol table
$SD
} // main
____________________________________________________________________________________________
Then slowly get a bit more ambitious:
$C+ // add elements into a variable of set type - eg05.pav
void main() {
set s = set{};
writeLine(s); // set should now contain { }
s.Incl(5); // set should now contain { 5 }
writeLine(s);
s.Incl(8); // set should now contain { 5, 8 }
writeLine(s);
s.Incl(3); // what should the set contain?
writeLine(s);
s.Incl(8); // what should the set contain?
writeLine(s);
$ST // display symbol table
$SD
} // main
____________________________________________________________________________________________
Hmm. The language lawyer interrupts this happy rush to complete the project.
$C+ // add elements into a variable of set type - eg06.pav
void main() {
set s = set{};
writeLine(s);
s.Incl(-4);
writeLine(s); // what should the set contain?
$ST // display symbol table
$SD
} // main
____________________________________________________________________________________________
While you are at it, why not extend the Incl statement?
$C+ // add multiple elements into a variable of set type - eg07.pav
void main() {
set s = set{};
writeLine(s);
s.Incl(1, 5, 7, 9);
writeLine(s); // set should be { 1, 5, 7, 9 }
$ST // display symbol table
$SD
} // main
____________________________________________________________________________________________
And let the language lawyer raise questions again:
$C+ // add multiple elements into a variable of set type - eg08.pav
void main() {
set s = set{};
writeLine(s);
s.Incl(1, 5, 7, 9);
writeLine(s); // set should now contain { 1, 5, 7, 9 )
s.Incl(2, 4);
writeLine(s); // set should now contain { 1, 2, 4, 5, 7, 9 )
s.Incl(2, 4, 1, 5);
writeLine(s); // what should the set now contain?
$ST // display symbol table
$SD
} // main
____________________________________________________________________________________________
Well, inevitably, he'll ask whether you have thought of adding values more general than can be defined by simple integer constants and come up with even more silly questions. Remember to answer them by keeping things general - but as simple as possible and no simpler. Avoid being limited to special cases - which some of these examples are, unfortunately.
$C+ // add multiple values into a variable of set type - eg09.pav
void main() {
int i = 4;
set s = set{};
s.Incl(i, 2 * i, Sqr(i));
writeLine(s); // what should the set now contain?
$ST // display symbol table
$SD
} // main
____________________________________________________________________________________________
$C+ // add multiple elements into a variable of set type - eg10.pav
void main() {
set s = set{};
writeLine(s);
s.Incl(1, 5, 7, 9);
writeLine(s); // set should now contain { 1, 5, 7, 9 }
s.Incl(2, -4);
writeLine(s); // what should the set now contain?
$ST // display symbol table
$SD
} // main
____________________________________________________________________________________________
$C+ // add multiple values into a variable of set type - eg11.pav
void main() {
int i = 4;
set s = set{};
s.Incl(i, Sqr(-i), -2 * i);
writeLine(s); // what should the set now contain?
$ST // display symbol table
$SD
} // main
____________________________________________________________________________________________
Do we always have to use Incl? Why not extend the system so that you can start from rather more interesting sets than an empty one?
$C+ // initialize non empty set - eg12.pav
void main() {
set s = set{1, 3, 5, 7};
writeLine(s); // output should now be { 1, 3, 5, 7 }
$ST // display symbol table
$SD
} // main
____________________________________________________________________________________________
$C+ // initialize non empty set - eg13.pav
void main() {
int i = 10;
set s = set{i, 2 * i, 3 * i, 35};
writeLine(s); // set should now contain { 10, 20, 30, 35 }
$ST // display symbol table
$SD
} // main
____________________________________________________________________________________________
It's useful to be able to see whether a set contains a particular element/value. Rather than do this with a "function" syntax, use the in operator as is done in Pascal and Modula. The in operator is a binary operator, and you might like to think of is as a funny sort of equals operator. Here is an example program
$C+ // test set membership - eg14.pav
void main() {
int i = 9;
set s = set{1, 3, 5, 7, 9};
writeLine(s);
writeLine(1 in s, 2 in s, i in s, 12 in s); // true, false, true, false
$ST // display symbol table
$SD
} // main
____________________________________________________________________________________________
Be on your guard about accepting incorrect code like this:
$C+ // test set membership - eg15.pav
void main() {
int i = 9;
set s = set{1, 3, 5, 7, 9};
set t = set{1, 2, 3};
writeLine(s);
writeLine(1 == s, s in 3, t in s, true in s); // true, false, true, false
$ST // display symbol table
$SD
} // main
____________________________________________________________________________________________
Sometimes it is useful to be able to determine how many elements a set contains, so let's introduce a method Members() to handle this.
$C+ // count the elements in a set - eg16.pav
void main() {
set s = set{1, 3, 5, 7, 9};
set empty = set{};
writeLine(s);
writeLine(Members(s), " elements"); // 5 elements
writeLine(Members(empty), " elements"); // 0 elements
s.Incl(7, 10);
writeLine(Members(s), " elements"); // ? elements
$ST // display symbol table
$SD
} // main
____________________________________________________________________________________________
Forming the union of two sets is a bit like addition, so follow the Pascal/Modula syntax and use the + sign to do this (a feature known as "overloading" the operator):
Union is also a little like "or". An element is in a union of two sets if it appears in either of those sets.
$C+ // form the union of two sets - eg17.pav
void main() {
set s1 = set{1, 3, 7, 9};
writeLine(s1);
set s2 = set{2, 4, 6};
writeLine(s2);
set s3 = s1 + s2;
writeLine(s3); // output is { 1, 2, 3, 4, 6, 7, 9 }
$ST // display symbol table
$SD
} // main
____________________________________________________________________________________________
Of course we should allow unions of unions!
$C+ // form the union of sets - eg18.pav
void main() {
set s1 = set{1, 3, 7, 9};
writeLine(s1);
set s2 = set{2, 4, 6};
writeLine(s2);
writeLine(s1 + s1);
writeLine(s2 + s2);
set s = set{ 2, 4 } + set {9, 7, 0};
writeLine(s); // union is { 0, 2, 4, 7, 9 }
writeLine(set {1, 3, 5} + set{} + set {2, 4} ); // { 1, 2, 3, 4, 5 }
$ST // display symbol table
$SD
} // main
____________________________________________________________________________________________
As we are implementing these ideas, a set is fundamentally an "object" . So we must be careful to understand that the == operator doesn't do what one might at first expect, and that one is going to have to define an Equals() method to do the job. Here is an example program to help you get this all sorted out properly (start by predicting what the output should be!)
$C+ // check sets for equality - eg19.pav
void main() {
set s1 = set{1, 3, 7, 9};
set s2 = set{1, 3, 7, 9};
set s3 = s1;
writeLine(s1 == s2);
writeLine(s1 == s3);
writeLine();
writeLine(Equals(s1, s1));
writeLine(Equals(s1, s2));
writeLine(Equals(s1, s3));
writeLine(Equals(s2, s3));
writeLine();
s1.Incl(10);
writeLine(Equals(s1, s1));
writeLine(Equals(s1, s2));
writeLine(Equals(s1, s3));
writeLine(Equals(s2, s3));
writeLine(Equals(s2, s3) == Equals(s1, s3));
$ST // display symbol table
$SD
} // main
____________________________________________________________________________________________
Similarly, the usual = (assignment) operator doesn't always do what you might at first think, and so we need a Clone() method to be able to make a "proper" copy of a set. Again, think generally; don't get limited by one or two simple examples.
$C+ // check sets for equality - eg20.pav
void main() {
set s1 = set{1, 3, 7, 9};
set s2 = set{1, 3, 7, 9};
set s3 = Clone(s1);
set s4 = Clone(Clone(s2));
set s5 = Clone(Clone(s2)) + s1 + set{9, 8};
writeLine(s1, ' ', s2, ' ', s3, ' ', s4, ' ', s5);
writeLine(s1 == s2);
writeLine(s1 == s3);
writeLine(s2 == s3);
writeLine();
writeLine(Equals(s1, Clone(s1)) );
writeLine(Equals(s1, s2) );
writeLine(Equals(s1, s3) );
writeLine(Equals(s2, s3) );
writeLine(Equals(s2, s4) );
writeLine();
s1.Incl(10);
writeLine(Equals(s1, s1));
writeLine(Equals(s1, s2));
writeLine(Equals(s1, s3));
writeLine(Equals(s2, s3));
$ST // display symbol table
$SD
} // main
____________________________________________________________________________________________
Finally, it is just as well to be check that sets can be passed as parameters. But this should hopefully follow quickly and easily if all the previous programs work correctly.
$C+ // pass sets as parameters - eg21.pav
void SetHandler(set p1, set p2, int i) {
writeLine(p1, " ", p2);
p2 = p1 + p2;
p1 = p1 + p2;
p1.Incl(i);
writeLine(p1, " ", p2);
$ST // display symbol table
}// SetHandler
void main() {
set s1 = set{1, 3, 7, 9};
set s2 = set{2, 4, 6};
SetHandler(s1, s2, 12);
writeLine(s1, " ", s2);
$ST // display symbol table
$SD
} // main
Have fun. There are also some deliberately incorrect versions of these programs with a .BAD extension in the exam kit so that you can check that errors are correctly picked up.
____________________________________________________________________________________________
The following is the specification of the C# set handling class available in the source kit:
class IntSet
// Simple set class P.D. Terry (p.terry@ru.ac.za)
public IntSet()
// Empty set constructor
public IntSet(params int[] members)
// Variable args constructor IntSet(a) IntSet(a,b) etc
public IntSet Clone()
// Value copy
public bool Equals(IntSet s)
// Value comparison of this set with s
public void Incl(int i)
// Includes i in this set
public void Excl(int i)
// Excludes i from this set
public bool Contains(int i)
// Returns true if i is a member of this set
public bool Contains(IntSet s) {
// Returns true if s is a subset of this set
public bool IsEmpty()
// Returns true if this set is empty
public bool IsFull() {
// Returns true if this set is a universe set
public void Fill()
// Creates a full universe set for this set
public void Fill(max)
// Creates a full universe set {0 .. max - 1} for this set
public void Clear() {
// Clear this set
public int Members()
// Returns number of members in this set
public IntSet Union(IntSet s)
// Set union of this set with s
public IntSet Difference(IntSet s)
// Set difference of this set with s
public IntSet Intersection(IntSet s)
// Set intersection of this set with s
public IntSet SymDiff(IntSet s)
// Set symmetric difference of this set with s
public override string ToString()
// Returns string representation of this set as a set of ints
public string ToCharSetString()
// Returns string representation of this set as a set of chars
} // IntSet
Home © P.D. Terry