Before we get started, I just wanted to remind you about the lab sessions. While they are optional, they should be extremely helpful to those of you who feel at all confused about the topics covered. This week's lab is on debugging and will be at 10, 11, 2 and 3 this Friday (tomorrow). If you're not an expert debugger already, I encourage you to attend.
In this recitation, we will aim to cover both inheritance and specifications. After this recitation, you should understand:
A specification is a contract between the implementer and the user of a class. The implementer is responsible for meeting the contract and the client is responsible for using the method only as it's specified by the contract and not counting on any other details of implementation.
Teamwork. A team of two people might be able to get along ok without specification, but real teamwork simply can't happen without specifications (and the team of two would be severely hampered in their work). Specifications allow a team to divide up work and then recombine it at some later date with at least some expectation of having everything work. Without specification, there would be no real way to do this.
Correctness. Having a spec to implement against helps ensure the code is correct in a number of ways. It gives the implementer a clear goal for his code -- it must meet the spec to be correct. It gives testers (and implementers) an easy way to see what the expected functionality of the software is so that they can know which tests to run and which results to expect
Documentation. The spec is written as a comment straight into the code. This is a win because it means when someone looks at the source, they can see the spec and not have to read through all the code. Moreover, if you use Javadoc for your comments (as we do in 6.170, and as Sun does in the Java APIs), the spec can be extracted and placed in neat html files for easy viewing and reference. The spec really is the best documentation that someone who wants to use your API can have -- it tells him what to expect and how to use your classes and methods.
Code reuse. When another developer comes along and wishes to write some piece of software with functionality vaguely similar to yours, he would loathe having to read your code to figure out what it does and see if it applies, but if he has the spec, he can simply read that.
Code maintenance. Eventually, you will no longer be the maintainer of your code. When that happens, the spec will prove invaluable to the new maintainer when it comes to understanding how he can improve and fix your code without breaking things.
And so much more. Spec writing is really a big win for all concerned.
There are two main types of specifications: method specifications and class specifications. Method specifications deal with abstracting away the implementation of a method from its interface. Class specifications deal with abstracting away the meaning, or behavior, of a type from its implementations.
Class specifications consist of abstract definitions of a type of data. An example of a specification for an IntSet class, which represents a set of integers is: IntSets are unbounded, mutable sets of integers. A typical IntSet is {x1, ..., xn}. It's just a description of what IntSet represents. It does not describe how it is implemented.
Another part of the class specification is the list of its specfields. Specfields are a very different thing from implementation fields (the member variables you define your class to have when you implement it). Specfields are the various abstract properties of a type. These can be stored in the object as an actual implementation field or they may not -- they may be computed on the fly or simply known all the time. Typically, a data type should have a small set of these types. One thing to note is that when you write your method specifications, you should not reference the implementation fields, but only the specfileds. This is because the spec should be able to stand on its own, separate from the code. A person reading your spec should not need to have any idea how you implemented it to understand it fully.
Now, class specifications by themselves are useful, but to aid implementers we (or more likely, they themselves) can provide some additional guidance in the form of abstraction functions and rep invariants, examples of which you saw in problem set 1.
Abstraction functions define how objects belinging to the type are represented; specifically, abstraction functions provide a mapping from the instance variables that make up the rep of an object to the abstract object being represented. In the case of our IntSet example, the abstraction function might be:
AF(c) = { c.els[i].intValue | 0 <= i < c.els.size }
The notation { x | p(x) } means "the set of all x such that
the predicate p(x) is true". Note that in the abstraction function we use
convenient notational shortcuts for things like getting the ith element of a
vector.
Representation Invariants define some predicate that must always be true for legitimate objects of a type. For our IntSet example, the rep invariant might be:
The rep invariant is: c.els != null && all elements of c.els are Integers && there are no duplicates in c.elsThe preceeding is an example of a rather informal, but still perfectly fine, rep invariant. It aids the implementer in remembering what must always be true for the object to correctly represent the type it is meant to.
Method specifications consist of three clauses: a precondition (requires), a postcondition (effects), and a frame condition (modifies).
The precondition clause is denoted by the word requires, places obligations on the client, and removes some responsibility from the implementer. If the precondition is not true upon entry to a method, the implementer can do anything he wants. He can throw an exception, infinite loop, quit, respond with some random garbage, or anything else -- the user has violated his end of the deal and deserves what he gets. If the precondition is omitted, it has the value true, meaning that every invoking state satisfies it (true is always true, after all) and there is no special obligation on the caller. Methods that omit preconditions are called total (ones with preconditions are partial).
The postcondition clause is denoted by the word effects, places obligations on the implementer, and provides guarantees to the user. If the precondition is true for the state upon invocation of a method, that method is obligated to satisfy the postcondition when it exits.
The frame condition is denoted by the word modifies and is tightly related to the postcondition. It makes possible shorter specifications by restricting the stuff that the postcondition could possibly modify. The frame condition states which objects can be modified and thereby restricts what we need to mention in the postcondition. Anything that is mentioned in it may or may not be modified, but we know that anything that is not mentioned will not be modified. If the frame condition is omitted, it defaults to modifies nothing, meaning no objects will be changed by the method. Something else to keep in mind is that you should write your modifies clause in terms of your specfields and not in terms of any details of the implementation. In general, it's better to say which fields can be modified than the more general 'this' as well.
As was mentioned in lecture, some specifications are stronger than others. But what exactly does it mean for one specification to be stronger than another? Put simply, one specification A is at least as strong as some other specification B if an implementation of A can be used wherever an implementation of B is required. That is, A can substitute for B in all cases. More specifically, specification A is at least as strong as specification B if (1) A's precondition is no stronger than B's and (2) A's postcondition is no weaker than B's, for the states that satisfy B's precondition. These rules imply that you can always weaken the precondition (placing fewer demands on a client will never upset him). You can always strengthen th postcondition (making extra promises will not upset a client).
Problem set 1 had examples of how we want you to document your specifications. Let's take a look at some of the specs from RatPoly.
/** RatPoly represents an immutable single-variate polynomial
* expression. RatPolys have RatNum coefficients and integer
* exponents.
*
*
* Examples of RatPolys include "0", "x-10", and "x^3-2*x^2+5/3*x+3",
* and "NaN".
*/
public class RatPoly {
// Definitions:
// For a RatPoly p, let C(p,i) be "p.terms.get(i).coeff" and
// E(p,i) be "p.terms.get(i).expt"
// length(p) be "p.terms.size()"
// Abstraction Function:
// A RatPoly p is the Sum, from i=0 to length(p), of C(p,i)*x^E(p,i)
// Representation Invariant for every RatPoly p:
// terms != null &&
// forall i such that (0 <= i < length(p), C(p,i) != 0 &&
// forall i such that (0 <= i < length(p), E(p,i) >= 0 &&
// forall i such that (0 <= i < length(p) - 1), E(p,i) > E(p, i+1)
...
/** Returns the degree of this.
* @requires: !this.isNaN()
* @return the largest exponent with a non-zero coefficient, or 0
* if this = "0".
*/
public int degree();
...
/** Scales coefficients within 'vec' by 'scalar' (helper procedure).
* @requires: vec, scalar != null
* @modifies: vec
* @effects: Forall i s.t. 0 <= i < vec.size(),
* if (C . E) = vec.get(i)
* then vec_post.get(i) = (C*scalar . E)
* @see ps1.RatTerm regarding (C . E) notation
*/
private static void scaleCoeff(RatTermVec vec, RatNum scalar);
...
}
The above has examples of the majority of the types of ways we want you to doument your specs. Use javadoc for the class spec and the method specs. The former should go above your class declaration. The latter should go above each corresponding method declaration and should use the special Javadoc tags we've defined for you (e.g., @requires:, @modifies:, @effects:) along with the standard Javadoc tags (e.g., @return).
public final class StringBuffer implements java.io.Serializable {
...
/**
* The character sequence contained in this string buffer is
* replaced by the reverse of the sequence.
*
* @modifies: this
* @effects: Let n be the length of the old character sequence, the one
* contained in the string buffer just prior to execution of the reverse method.
* Then the character at index k in the new character sequence is equal
* to the character at index n-k-1 in the old character sequence.
* @return a reference to this object..
*/
public synchronized StringBuffer reverse();
...
}
/**
* Find the index of the value val in the array a.
*
* @requires: val occurs in a
* @return result such that a[result] == val
*/
static int findA(int[] a, int val) {
for (int i=0; i<a.length; i++) {
if (a[i] == val) return i;
}
return a.length;
}
static int findB(int[] a, int val) {
for (int i=a.length-1; i>0; i--) {
if (a[i] == val) return i;
}
return -1;
}
The final exercise uses the specifications and implementations on the separate Sorters.java handout. We have provided you with some specifications and some implementations of a method that is designed to sort an array of integers. Your job is to perform the following tasks:
Inheritance is the ability, in object-oriented programming, to derive new classes from existing classes (in Java, this includes the ability to derive new interfaces from existing ones). A class so derived (a subclass) inherits the variables and methods of the class it's derived from (its superclass). A subclass can add new methods or variables as well as modify (called overriding) inherited ones.
Some languages (such as C++) have multiple inheritance, which means a single child class can derive from multiple parents. Java sticks with single inheritance for various reasons, not the least of which is that multiple inheritance can be quite confusing. Java does, however, allow a single class to implement multiple interfaces, thus disallowing multiple implementation inheritance, but allowing multiple interface inheritance.
So why do we care that a programming language has inheritance? Why would we ever want to use it? It would certainly be easier to write compilers that didn't have to implement it, so why does Java go to all this trouble? Moreover, inheritance is not without cost. It often adversely affects execution speed, program size, program complexity, and incurs method passing overhead. These disadvantages, however, are more than made up for by the fact that inheritance makes application development much faster and allows us to do quite a few things we couldn't do otherwise.
Inheritance speeds up program development by allowing us to reuse code. When we extend a class someone else has already built, we just need to implement our changes and don't need to recreate everything from scratch. One such use of inheritance is specialization. We may want an extended class to behave like a specialized version of the superclass.
Inheritance aids in keeping more consistent interfaces between types. For example, in the Java api, there is an InputStream class that represents an input stream of bytes. Now, there are a number of different sorts of input streams, including the classes FileInputStream (representing a byte stream of input from a file) and a FilterInputStream (representing an input stream of bytes where some additional operation is performed on the stream as it is read). Since both of these classes inherit from a common superclass, it is straightforward for the implementer of the API to keep the interfaces of the two types consistent with each other. It is also straightforward for a user of the API to use a FilterInputStream (or one of its subclasses, say a BufferedInputStream) in place of a FileInputStream, since they share the common interface of the InputStream class. Thus all the code involved will be written more quickly and correctly.
One of the most important features of inheritance is that an object of a subclass can be used wherever an object of the superclass is required (with some caveats we'll cover in a bit). This capacity is called polymorphism. An object of a single class can have multiple forms: either its own or that of one of the classes it extends.
There are two main types of inheritance in general: inheritance of contract or type and inheritance of implementation. Java doesn't separate these out as such (which is fine, as they're not mutually exclusive), but it does implement them both. Any class can extend another class or implement any number of interfaces. Additionally, an interface can extend other interfaces. With class extension, the inheritance of contract and of implementation always occur together (unless you mess up). You can accomplish inheritance of contract without inheritance of implementation using interfaces.
You already know about Java classes. There is a very similar thing in Java called an interface. It is very much what you'd expect it to be from the name, defining only the interface (the spec) for a type and not any of the implementation for it. Interfaces are typically used rather than classes when you want to define a type that many unrelated things can inherit from (in Java terms you implement an interface).
One very good example of an interface in the Java API is the Comparable interface. Comparable is an interface that specifies only one method: public int compareTo(Object o). The spec describes what compareTo should return when 'this' is less than, equal to, or greater than the argument o. There are any number of various things that would want to implement the Comparable interface, but most of them are not at all related to each other. The benefit of this scheme is that you can write code that works based on the Comparable interface without knowing anything else about the type of the object. The java.util.Collections class has a sort method that relies on just this fact. Without knowing anything about the actual type of the elements in a List, the implementer of sort is able to guarantee that it works correctly, so long as the elements of that list implement the Comparable interface.
A caveat: In Java, you can change the way that a contract works between a subclass and its superclass, but you should never do this. That is, never change the implementation of a method in a way that violates the superclass's contract. You'll be in a world of hurt down the road, as we'll explain in future classes.
In Java, each class can present two different contracts via its access control mechanisms -- one class for users of the class and one for extenders of the class. We'll talk about this more in the section on specification.
One important fact to note: in Java, constructors are not inherited automatically.
Let's dive right into this with some examples and exercises.
Look at the code for the Thing, Building, and Dormitory classes and answer the accompanying questions (the questions are progressively more difficult and involve more knowledge of Java as you go through them).
class Thing {
public Thing() {
System.out.println("Thing()");
}
}
class Building extends Thing {
public Building() {
System.out.println("Building()");
}
}
class Dormitory extends Building {
public Dormitory() {
System.out.println("Dormitory()");
}
}
Building b = (Building) new Thing();are we upcasting or downcasting? Will this code compile? Will it execute successfully? Could we do it without the explicit cast?
Building myHouse = (Building) new Dormitory();are we upcasting or downcasting? Will this code compile? Will it execute successfully? Could we do it without the explicit cast?
Dormitory foo = new Dormitory()
class Foo {
protected String str = "Foo";
public String getStr() {
return str;
}
}
class Bar extends Foo {
protected String str;
public Bar(String str) {
this.str = "Bar" + str;
}
public static void main(String[] args) {
Foo foo = new Bar("foo");
Bar bar = (Bar)foo;
System.out.println(foo.getStr());
System.out.println(bar.getStr());
System.out.println(foo.str);
System.out.println(bar.str);
}
}
public class Lifeform {
private String type;
public Lifeform(String type) {
set this.type = type;
}
public String getType() {
return type;
}
}
public interface Habitable {
public int numberOfInhabitants();
public void addInhabitant(Lifeform l);
}