341 : 27 Feb 2002 : Collections and lessons

Abstract sequences

Object subclass: #Sequence
    instanceVariableNames: ''
    classVariableNames: ''
    poolDictionaries: ''
    category: 'CSE341-Exercises'
!
add: anObject
    self subclassResponsibility.
!
do: aBlock
    self subclassResponsibility.
!
first
    self subclassResponsibility.

I have faked up "declaration" delimiters using exclamation points. In fact, this is something like what Squeak will write when you fileOut a code fragment. Of course, in the Squeak environment, you will use the code browser to define your classes instead of writing ! directly.

The message send self subclassResponsibility is the Smalltalk idiom for having a class indicate that its subclasses should implement a given method; in other words, these methods are "abstract". These are hence like pure virtual methods in C++, or like abstract methods in Java. However, Smalltalk is more dynamic than these languages, and hence will not prevent you from instantiating such objects:

x := Sequence new.     "printIt will yield 'a Sequence'"

This is because self subclassResponsibility is an ordinary message send, not a special part of the language. The method implementing this message is defined in Object (the superclass of all classes); when invoked, it will raise a specific exception. Therefore:

x add: 5.

will result in a dialog box titled "Error: My subclass should have overridden one of my methods," and showing a stack trace.

Concrete sequences

In the course of this class, we'll create two concrete classes---i.e., classes that are meant to be instantiated directly---that implement the methods specified in Sequence.

Singly linked list, version 1

1. Define a ListCell class. This will be a singly linked list node with set and get methods for its "value" and "next" fields. Recall the syntax for returning a value from a method: ^ expr.

2. One Smalltalk idiom for object "constructors" is to create a new class method that returns an appropriately initialized instance of the class. (Recall that classes are objects too.) This method will usually send self new to obtain a fresh instance, and then initialize its fields.

   Define a class method, for ListCell, named withValue:andNext: that returns a new instance with appropriate "value" and "next" fields. (You may assume that you have used the code browser to select the appropriate class category, class, and you have clicked on the "class" methods button so that you can enter class methods instead of instance methods.) This method will be invoked as follows:

   ListCell withValue: 5 andNext: nil;     "Returns a fresh ListCell."
   

3. Define a MyList class that subclasses Sequence and implements the three methods required by Sequence. Hint: to implement do:, consider what map looked like in Scheme, and how we evaluate blocks (closures/lambdas) in Smalltalk. Here is what a call to do: looks like:

   Transcript open.                 "Open window for printing."
   alist := List new.               "Create a new List."
   alist add: 5; add: 6; add: 7.    "Recall syntax for sending to same receiver."
   alist do: [ :item |
     Transcript show: item.
   ]
   

Singly linked list 2.0

Next we're going to push more of the behavior of MyList down into the list cells.

1. Define an AbstractListCell class that implements the following methods as "abstract":

     add: anObject
         "Returns a new cell whose tail is the current cell (self),"
         "and whose value is anObject."
     do: aBlock
         "Evaluates block on this cell's value, and its successors."
     first
         "Returns the first element in this list."
   

2. Define two subclasses of AbstractListCell: NilListCell and ConsListCell. What instance variables should these classes have, if any? Implement add:, do:, and first for each of these subclasses.

3. Implement the class ListTwo that uses this new mini-list-cell hierarchy instead of ListCell. You should define a class method initialize for initializing this list (as usual, assume you have used the code browser to get at the class method pane of this new class).

4. What does this code teach you? Do you find this code simpler or more complicated than the code for our first linked list? Ruminate upon this code and its connections to similar code in other languages you have learned. What are the differences in code organization? What are the similarities?