Self Sets

Due Monday, December 8, at the start of class.

In this assignment, you'll develop a set data structure in Self.

API

To make a new, empty set object, one should evaluate setProto clone.  A set object should understand at least the following messages:

• add: arg
  "add arg to the receiver set, if it's not already there (using = to compare elements). return the receiver."
• length
  "return the number of elements in the receiver set"
• isEmpty
  "return whether the receiver set is empty"
• do: aBlock
  "evaluate aBlock on each element in the set"
• test: arg Present: presentBlock Absent: absentBlock
  "if arg is a member of the receiver set, then invoke presentBlock, else invoke absentBlock"
• includes: arg
  "return whether the argument is already an element of the receiver set"
• copy
  "return a (shallow) copy of the receiver set (same elements, different set)"
• isSubsetOf: set
  "return whether the receiver is a subset of the argument set, i.e., whether all the elements of the receiver are also elements of the argument."
• = set
  "return whether the receiver and the argument set have the same elements"
• mapBy: aBlock
  "return a list of the results of evaluating aBlock on each of the elements of the receiver set, in some order"
• printString
  "return a string which is a printable version of the set and its elements"

Define a file named set.self that defines such a set data structure in good Self style.  You should inherit existing code where reasonable.  You should define methods in terms of other, lower-level methods where possible.  In general, avoid code duplication wherever possible.

You can implement your set using the existing list implementation in list.self, or the binary tree implementation from the Self paper, or in any other way you like.  You shouldn't need to modify any existing Self code to complete your implementation, but you may if you wish.

Test code

You should also add to the end of your set.self code a set of tests illustrating that your set implementation works correctly, printing out the results of various tests.  For example, here's a fragment of my testing code:

"some testing code"


'Starting set tests...' printLine.


_AddSlots: (| s1. s2. s3. l1. |).


s1: setProto clone.  "a new, empty set"
s1 add: 'hi'.
s1 add: 'there'.
s1 add: 'hi'.  "a duplicate; should be ignored"
s1 add: 'bob'.
('s1 = ' + s1 printString) printLine.

and here's the result of loading my set.self sample solution:

% self


Welcome to the Self Interpreter!
Enter Self statements to be evaluated.
Enter control-D (control-Z on Windows) to quit.


(Reading stdlib.self.)
Self> 'set.self' includeFile
Starting set tests...
s1 = set{'bob', 'there', 'hi'}
s2 = set{9, 5, 2, 3}
s3 = set{3, 2, 5, 9}
s2 = s3? true
s3 = set{5, 2, 9, 3}
s2 = s3? true
s3 = set{7, 3, 2, 5, 9}
s2 isSubsetOf: s3? true
s3 isSubsetOf: s2? false
s2 = s3? false
s2 = set{11, 9, 5, 2, 3}
s2 isSubsetOf: s3? false
s3 isSubsetOf: s2? false
s2 = s3? false
s2 mapBy: [|:elem| elem+1] = list{12, 10, 6, 3, 4}
Tests completed.
Self> 

You should define your own test suite that exercises your set implementation and demonstrates that it works correctly.

Some questions

Consider the following example use of sets:

_AddSlots: (| s1 |).
s1: setProto clone.
s1 add: 'hi'.
s1 add: 3.

Does this work in your implementation?  It doesn't work in mine; I get the message "Eval error: not a string".  It shouldn't work in yours, either.  Why doesn't this work?  How could the Self standard library code be changed to make it work?  How does Cecil make this kind of change easier?

• Extra credit: Fix the Self standard library code, in a nice, extensible way, to make this code work right.

What to turn in

Turn in your set.self file (plus any other .self files you modified or added) and your answer to these questions, by emailing attachments to andrei@cs.washington.edu. If you're tackling the extra credit problem, then clearly indicate this in your turn-in.