10. A solution to MP1
Part of
CS:2820 Object Oriented Software Development Notes, Fall 2015
|
In solving MP1 by adapting the code from the lectures to the domain of logic circuits, several problems came up.
The error handling method in the code from the lectures calls System.exit(), causing the program to terminate with a bang. The assignment for MP1 asked for the program to report all the errors it encountered and then output that part of the logic circuit that was not in error.
There is still at least one fatal error if the input file cannot be opened, so we need to keep the ability to report a fatal error but also add the ability to report a non-fatal error. As in any programming problem, there are an infinite number of ways of doing this. Here is the way it's done in the posted solution:
class Errors {
/** Error reporting framework
*/
static void fatal( String message ) {
/** Report a fatal error with the given message
*/
System.err.println( "Error: " + message );
System.exit( 1 );
}
static void warn( String message ) {
/** Report a nonfatal error with the given message
*/
System.err.println( "Error: " + message );
}
}
For an example of an alternative, consider adding a parameter to a single reporting method, so you would call Errors.report(true,...) for fatal errors and Errors.report(false,...) for regular errors. The one disadvantage of this is that it makes the code to report an error more verbose.
Introducing non-fatal errors means that we need some way to allow an initializer to fail. There are many alternatives. The initializer could throw an exception. In this case each call to the initializer must wrap the initialization in a try-catch block with an empty handler, since the initializer puts out the error messages, as follows.
try {
wires.add( new Wire( sc ) );
} catch (SomeKindOfException e) {
}
Alternatively, the initializer could return null if the input contains an error. In this case, a call to the initializer might look like the following:
Wire w = Wire.scan( sc ); if (w != null) wires.add( w );
The second alternative is easier to read, so it is the one we used in the posted solution to the problem.
There is a second reason to favor not using an exception handler. Many style guidelines for programming with exceptions urge programmers not to use exceptions for the normal flow of control. We are writing a language processor -- admittedly for a rather crappy language for describing logic circuits, but it is a language. When you run a language processor normally, you get errors. The unusual case is that your input is error free. So, exceptions for "normal" errors go against the common advice. Personally, I disagree with the style guidelines that discourage exceptions, but many language designers and implementers have taken this advice to heart and designed and built languages that have relatively slow exception handlers, discouraging their use except in exceptional circumstances.
Note that, Java initializers cannot return null! Calling new Gate() to scan the description of a gate from the input file worked in the version above that threw an exception to report errors, but this will not work in other contexts. This is unfortunate, because, the implementation of a Java initializer, for example, for the class Gate is mostly equivalent to:
public static Gate Gate( ... ) { ...
Within the initializer, self refers to the newly allocated object being initialized, and at the end, the new object is returned from the initializer. Unfortunately Java works to guarantee that, if an initializer returns, the newly initialized object is not null. So, we must change the code to not use the built-in initializer mechanism, but instead, use a new method. This is called scan() here. The framework for the Gate.scan() is given here:
// initializer -- note: No outside code uses the default initializer!
public static Gate scan( Scanner sc, String kind,
List <String> inputs ) {
/** Initialize a gate scanning its description from sc.
* Returns null if the description contains errors.
*/
Gate g = new Gate();
Gate returnValue = g;
... code deleted ...
g.name = sc.next();
if (LogicCircuit.findGate( g.name ) != null) {
Errors.warn( "gate '" + g.name + "' redefined" );
returnValue = null;
}
... code deleted ...
return returnValue;
}
In the body of this code, note that g and returnValue initially refer to the same newly allocated uninitialized gate object. All the initialization is done to g, while if, at any point, there is an error in the input file, returnValue is set to null. This way, if there was no error, returning returnValue at the end of the method returns the initialized object, while if there was an error, it returns null. With the full initializer present, this may be a bit hard to follow if you just dive into the middle.
The next problem involves supporting the different kinds of gates. The best solution to this would be to create subclasses, one for each kind. Eventually, we'll need to do this, because the subclasses will be needed for the different behavior of each gate type in the logic circuit simulation. If we did this, the gate initialization part of readCircuit routine would look something like this:
while (sc.hasNext()) {
// until the input file is finished
String command = sc.next();
if ("gate".equals( command )) {
String kind = sc.next();
Gate g = null;
if ("and".equals( kind )) {
g = AndGate.scan( sc );
} else if ("or".equals( kind )) {
g = OrGate.scan( sc );
} else if ("not".equals( kind )) {
g = NotGate( sc );
} else {
Errors.warn( "gate '" + kind
+ "' type not supported" );
sc.nextLine();
}
if (g != null) gates.add( g );
In our preliminary code, where our goal is simply to build the data structure representing the circuit and then print it, we don't really need these subclasses because the only thing that distinguishes, for example, and gates from not gates is the fact that they have different names and different lists of allowed inputs. Therefore, we can simply pass the name and list of inputs as parameters to the generic initializer for Gate, as follows:
if ("and".equals( kind )) {
g = Gate.scan( sc, "and", in1in2 );
} else if ("or".equals( kind )) {
g = Gate.scan( sc, "or", in1in2 );
} else if ("not".equals( kind )) {
g = Gate.scan( sc, "not", in );
This is a bit ugly, adding a bunch of odd parameters to the initializer, but it works well enough for this step in our program development. The initializer Gate.scan() simply copies these fields into the gateType and inputList fields of the newly allocated gate object.
The rules for using a gate state that each input may be used exactly once. Later, when we start adding behavior, we'll have to add the rule that each input must be used exactly once -- that is, all inputs must be connected to something.
To enforce this rule, we need to remember which inputs of a gate have been used. Only previously unused input names may be used. In the initializer for wires, we check this as follows:
if (w.driven == null) {
Errors.warn( ... );
returnValue = null;
} else if (!w.driven.checkInput( w.input )){
Errors.warn( ... );
returnValue = null;
}
In the above, the checkInput() method of the driven gate must determine if it is legal to use the given input string, returning true if it is legal and fales if not. As a side effect, checkInput() also records that the input has been used in order to prevent reuse.
In the current version of the code, the lists of inputs are all declared in the readCircuit() method, but later, these lists might each be declared in a different subclass of Gate. Regardless of where they are declared, the problem we face here is how to do so. I googled around for different ways of declaring and initializing lists of strings in Java. There are, of course, plenty of ways of doing this, but by far the nicest is to use the asList() method of the Arrays package. This creates an ArrayList object, a different class from the LinkedList class we have been using, but both of these classes are subclasses of List. So, we need to add two lines to our list of imports:
import java.util.Arrays; import java.util.List; import java.util.LinkedList; ...
Having done this, we can now initialize our lists of legal input names in readCircuit():
private static void readCircuit( Scanner sc ) {
/** Read a logic circuit, scanning its description from sc.
*/
// the different input name sets for different gates
List <String> in1in2 = Arrays.asList( "in1", "in2" );
List <String> in = Arrays.asList( "in" );
// Bug: Above is the wrong way to do this
Note that we have a bug notice here, because we do want this code moved, later, into the right subclasses of the gate class. Ignoring this, in1in2 is now a two element list containing the strings "in1" and "in2" and in is now a one element list containing just the string "in".
The scan() method in the gate class contains receives this list of input names as follows:
public static Gate scan( Scanner sc, String kind,
List <String> inputs ) {
/** Initialize a gate scanning its description from sc.
* Returns null if the description contains errors.
* Bug: kind is the wrong way to pass the kind of gate.
* Bug: inputs should be a function of kind.
*/
Gate g = new Gate();
Gate returnValue = g;
g.gateType = kind;
g.inputList = new LinkedList <String> ( inputs );
// Bug: above is the wrong way to handle gate types
Note that the third parameter to scan(), named inputs is declared as a generic list of strings, not specifically an array list or a linked list. That allows parameters of either type to be passed. It happens that we are passing an array list. Note also that the assignment to the inputList field of the new gate is not a direct assignment.
Direct assignment, that is, code like inputList=inputs would be illegal because, in this case, inputs is a generic list and might be an array list, while inputList is declared to be a linked list. This creates a type error.
Even if we did not fact this type error, the assignment inputList=inputs would be wrong because, in checking to see if an input is in the input list, we are going to delete it. When we edit the input list of a gate we do not want this to change the input lists of other gates. Therefore, we make a copy. One of the initializers provided for each subclass of the class List is one that takes any list and makes a copy as the new value of the newly created list. This copy operation also translates between list representations, in this case, converting an array list to a linked list.
With all this foundation in place, the checkInput() method of the gate class becomes trivial. Searching through the methods of the List class, I found (as I expected) a remove() method that searches a list for the first occurance of an item and removes that list element. To my pleasant surprise, it also returns a boolean value, true if the element was removed, and false if there was no match. As a result, we get the following code:
public boolean checkInput( String in ) {
/** Check if in is a permitted input for this gate
* and also check off the fact that it has been used.
* Bug: this may not be the right way to do this.
*/
return inputList.remove( in );
}
Again, we have a bug notice here, because we may need to reconsider everything about the input list when we refine our data structures on the way to implementing a logic simulator.