9. Polymorphism
Part of
CS:2820 Object Oriented Software Development Notes, Fall 2017
|
The code we produced last Monday works, but it is vastly oversimplified. A major detail in real road networks is that there are many types of intersections. We have at least the following variants:
Stop lights have several characteristics, but one of the most significant is that the simplest ones turn green in two directions while they are red in the other two directions. This means that, for example, the lights facing both north and south are green when the east and west lights are red, and visa versa. More complex stoplights have turn arrows, but for all varieties of stoplights, roads into or out of that intersection must have labels indicating the direction from which they enter or leave.
Similarly, in the neural net example, we have several kinds of synapses. There are excitatory synapses where an action potential traveling down an axon to that synapse causes a positive change in the receiving neuron, pushing it closer to the threshold that would cause it to fire, and there are inhibitory synapses that cause a negative change in the receiving neuron, making it less likely to fire. there are also axosynaptic interfaces where a secondary synapse transmits signals to a primary synapse, activating or inhibiting the primary synapse.
In a logic simulator, there are several kinds of gates. We typically speak of and, or, and not gates, but there are also nand, nor, and exclusive-or gates, as well as assymetric gates that perform functions such as a and not b. This means that we must document each wire leading to a gate by indicating which input it connects to. In the general case, gates may have multiple outputs, so wires from a gate must also be tagges with which output they connect to.
This has an immediate impact on our road network description. Where we formerly just said:
intersection A intersection B
We can now say things like:
intersection A stoplight intersection B
We've made a decision above, a decision that has several consequences. That is, for specialized types of intersection, we explicitly name the intersection type, but there is also a default where there is no explicit name. We could have reqired intersection B above to be declared as a simple intersection or something like that. The primary problem with this design decision is that it complicates the problem of parsing the input file by forcing us to recognize the end of line.
A second consequence is that for roads, we need to document how the road connects to the intersections it joins, for example, using a notation like this:
road A north B south
This means that there is a road leaving intersection A going north to intersection B where it enters from the south.
Java supports polymorphic classes, that is, classes where there are multiple possible implementations. In fact, polymorphism was added to Simula '67, the original object-oriented programming language, precisely to allow for the kind of variation discussed above.
Specifically Java, C++ and their ancestor Simula '67 all allow us to introduce new classes that extend an existing class. For example, in Java we could have:
/** Intersections with no stop light
* @see Intersection
*/
class NoStop extends Intersection {
}
/** Intersections with a stop light
* @see Intersection
*/
class StopLight extends Intersection {
}
How do these new subclasses differ from the parent class? The simplest place they differ is in the toString method, so we can immediately create new methods for that:
/** Intersections with no stop light
* @see Intersection
*/
class NoStop extends Intersection {
return (
"intersection " +
name
);
}
/** Intersections with a stop light
* @see Intersection
*/
class StopLight extends Intersection {
return (
"intersection " +
name +
" stoplight"
);
}
In the above, we've made the output of the toString() method recreate our input text, unless the input contained tabs or multiple spaces between the words. Information about those details is lost by the scanner we are using.
Note that wherever it is legal to have an Intersection, it is now legal to have either a NoStop or a StopLight. Consider the following declarations in a hypothetical bit of code:
Intersection i; NoStop n; StopLight s;
When you create a new object, you must pick its actual class. Once an object is created, you cannot change its class. So, we must change the code to initialize intersections. Here is the old code for readNetwork()
static void readNetwork( Scanner sc ) {
while (sc.hasNext()) {
// until the input file is finished
String command = sc.next();
if ("intersection".equals( command ))
inters.add( new Intersection( sc, inters ) );
} else if ("road".equals( command ))
roads.add( new Road( sc, inters ) );
} else {
// Bug: Should probably support comments
Errors.warning(
"'"
+ command
+ "' not a road or intersection"
);
// Bug: Should skip to the next line
}
}
}
We need to change the part for initializing intersections. This raises a problem. Our input language is arranged like this:
intersection X stoplight
Here is an alternative syntax:
intersection stoplight X
If we had done the latter, we could have learned that we were about to initialize a member of class StopLight before we knew its name, so we could call the correct constructor and let the constructor pick up the name, as it does in our current version of the code. Now, however, we must scan over the name first before we discover the type. One way to do this would be as follows:
String command = sc.next();
if ("intersection".equals( command ))
// Bug: What if no sc.next?
String name = sc.next();
// Bug: What if no sc.next?
String kind = sc.next();
if (kind == "stoplight") {
inters.add( new StopLight( sc, name ) );
} else {
// Bug: How do we undo sc.next()?
inters.add( new NoStop( sc, name ) );
}
} else if ("road".equals( command ))
...
This solution would force readNetwork() to know about every subclass of Intersection. As a general rule, one way to improve the maintainability of large programs is to limit the need for one part of the program to know anything about internal details of another part. From the top level, all we need to know is that there are intersections. Only within class Intersection is there any reason to know that there are subclasses. Therefore, we will abandon this solution.
We never intend to allow anyone to create an object of class Intersection. There are two ways to do this in Java. One approach is to prevent anyone outside the class from calling its constructor. For example, we could declare the constructor to be private:
// constructor
private Intersection() {}
Declaring the constructor to be private prevents any code from outside class Intersection from creating any objects of this class, but it still allows code within the class to do so. Another approach to solving the problem is to declare the class to be abstract like this:
abstract class Intersection() {
String name;
...
}
Declaring the class to be abstract makes it illegal to call new Intersection() anywhere in the program. The only way to create an instance of an abstract class is to create an instance of one of its subclasses. So, if StopLight is a subclass of Intersection we can call new StopLight(), and the new StopLight will contain all the fields of an Intersection.
It is legal for an abstract class to have a constructor, but that constructor can only be used within the constructor of one of the subclasses. That is, the constructor for StopLight can use the constructor for Intersection to do initialization on the fields that it inherits from Intersection.
However we prevent instances of Intersection from being created, we must add constructors to its subclasses. For example, we can begin with a constructor for NoStop that looks something like this:
public NoStop( Scanner sc, String name ) {
// scan and process one intersection
if (RoadNetwork.findIntersection( name ) != null) {
Errors.warning( "Intersection "
+ name
+ " -- redefined."
);
// Bug: Can we prevent creation of this object?
}
String skip = sc.nextLine();
// Bug: What if more junk at end of line (skip not empty)
}
The code for StopLight is similar. Before we give this, though, note that we have a bug notice that is repeated three times in our code. In class Road and again, in classes NoStop and StopLight, we have repeated the same basic bug notice asking how we detect improper end of line. What we need is a service method to solve this problem in one place, instead of duplicating code everywhere.
Just as error reporting was worthy of a separate class, so is support for common problems encountered in scanning the input. We'll call this class ScanSupport, and we'll begin by developing just one method, lineEnd() that is used to cleanly scan the end of each line and complain about irregularities that might be encountered there.
Since we never intend to create any instances of ScanSupport, we can declare it to be abstract or declare it to be an interface instead of a class. Interfaces are not really intended for this purpose — you cannot create an instance of an interface because all non-static methods in an interface are implicitly abstract -- that is, they define methods that must be implemented in some other class that inherits from the interface. Whether we define it as an interface or a class, what matters is that we only use static methods.
Later, we can add more methods for other problems that occur repeatedly in the code. For example, each time we scan an intersection name, we ought to check that it is a legal name and not, for example, a floating point number or a quoted character string.
Our initial version of the LineEnd() method just preserves the bug notices we found in the three original contexts where we needed to scan over the end of line:
/** Input scanning support methods
*/
class ScanSupport {
/** Force there to be a line end here, complain if not
* @param sc The scanner on which we wish to force a line end
*/
static void lineEnd( Scanner sc ) {
String skip = sc.nextLine();
// Bug: What if more junk at end of line (skip not empty)
}
}
Initially, we needed just one parameter, the scanner we are using to read the input. Once we start doing something about the bug, however, we will need a second parameter, the error message to print if errors are detected in the the line end. While we are at it, we can add the code to detect the most obvious of the errors, a non-empty line end:
/** Force there to be a line end here, complain if not
* @param sc The scanner on which we wish to force a line end
* @param m The prefix on the error message output if failure
*/
static void lineEnd( Scanner sc, String message ) {
String skip = sc.nextLine();
if (!"".equals( skip )) {
// Bug: Do we want to allow comments here?
Errors.warning( message + " -- line end expected." );
}
// Bug: what if sc.nextLine() was illegal (illegal state)
}
We've corrected one bug notice, but we've added to new ones: What if it was illegal to call sc.nextLine() because there was no next line in the input file? This can occur at the end of an ill-formed input file where there is no newline character at the end of the final line of the file. Some text editors, such as vi do not permit you to create such files. Others do, and we ought to handle this gracefully.
This matters in a world where DOS and Unix file formats exist. A properly formed Unix file (and Linux inherits the same rules) always ends with a newline, while in the DOS file format, newlines are used to separate lines, not terminate them, so the final line of a file doesn't end with a newline. Unfortunately, Java's input/output support does not account for this, so while Java programs can be made portable between the Unix and DOS worlds, it is not always trivial to do so.
The other bug notice is a suggested enhancement. We have the option here of supporting a uniform comment notation, for example, we might consider any text at the end of line that starts with two consecutive dashes to be a comment, so this kind of input would be legal:
intersection A -- this is really a traffic circle road A B 12.5 -- this is half of a 2-lane road
Adding support for this is a nice exercise.
It is time to return to the constructors for our subclasses. Here is the constructor for class StopLight augmented to use the above code:
public StopLight( Scanner sc, String name ) {
// scan and process one stop-light intersection
if (RoadNetwork.findIntersection( name ) != null) {
Errors.warning( "Intersection "
+ name
+ " redefined."
);
// Bug: We should prevent creation of this object!
}
// Bug: Excess duplication if all intersections start as above!
// Bug: Missing anything specific to stop lights
ScanSupport.lineEnd(
sc,
"Intersection " + name + " stoplight"
// Bug: We do these concatenations with every call
)
}
This constructor will be the basis of some extended discussion because of the two bug notices: First, in the event that an attempt is made to redefine an intersection that already exists, we need to suppress the definition, and second, it is foolish to do computationally complex things like string concatenation before any need arises. Dynamically creating an error message before every call is foolish if we only need that message occasionally, in those few lines that contain errors.
This constructor still doesn't do anything specifically related to stoplights, and we've added some bug notices since we really don't want to have to write duplicate code at the head of every constructor for subclasses of Intersection. The code at the end of each constructor says what kind of intersection it is, and it is just one method call, so that duplication is not flagged as a bug, even though we write out the code as 4 lines, or 5 if you include the bug notice.