CMSC 433 – Programming LanguageTechnologies and ParadigmsSpring 2003Data Abstraction, Types, andPolymorphismFebruary 25, 2003Project 2• Due Friday, February 28• Clarifications on news group– Don’t need to test handling of erroneous clients• Passing in null as parameter• newVertex twice with same name• Modifying graph during iteration• Using a Vertex after removing it– Do need to test GraphFactory• But can limit to checks of form read(write(g)) = gProject 2• Make sure project 2 compiles!– You won’t get points for code that doesn’t compile• In project 1, we had some weird glitches with line endings, or the lackthereof• Mixes of \n and \r in one file• Lines joined with no line separatorsData Abstraction• Data abstraction = objects + operations– List + { addFirst, addLast, removeFirst, ... }– Set + { add, contains, ...}• Categories of operations– Constructors (creators/producers)– Mutators– ObserversAbstraction Function• Specification for data structure is abstract• Implementation of data structure is concrete• How do you know if implementation meets thespec?• Abstraction function : concrete abstract– Relates implementation to abstractionExampleclass IntSet { int [] elts; ... }– AF(s) = { s.elts[i] | 0 <= i < s.elts.length }• You always need an abstraction function whenyou build a data abstraction– Often it’s implicitRepresentation Invariant(s)• Properties of data structure that must always hold– After the constructor has finished– Before and after each operation– E.g., binary search tree property• Part of the (internal) specification• Be careful of exposing the rep– Dangerous, because rep invariant may be violated– Be wary of returning references to internal mutable structures• e.g., returning a pointer to an internal arrayMethods Inherited from Object• equals– Override with appropriate method• hashCode– Always override if you override equals• two equal objects must have equal hashCodes• toString– Always override; try to provide maximal information• clone– Hard to use correctly; avoid if possibleMutability• Many data abstractions are mutable– Operations can change internal state• Things to watch out for– Mutating shared data– Mutating an object in a container• Benevolent side effects– Side effects that are not visible to client (e.g., cache)– Not “conceptual” mutability• Don’t change abstract valueType Hierarchy• Recall: A class A can extend other classes B andimplement interfaces C– A, B, and C are all types– A is a subtype of B, and A is a subtype of C• Substitution (or subsumption):– If B is a subtype of A, then a B can be used anywherean A is expected.The Meaning of Subtypes• Method signatures must match exactly to override– Parameter and return types– Overriding method can throw fewer exceptions• This is all checked at compile time• Also important: behavior of overriding methodmust matchOverriding/Implementing Methods• Given /** Search array for value */ /** @precondition: d is sorted */ /** @postcondition: returns index i s.t. d[i] == value,or -1 if no such value exists */int find( int [] d, int value);• Can we implement find() witha) A method that accepts any array?b) A method that requires d is sorted and there exists i s.t. d[i] = value?c) A method that either returns -1 or the first index i s.t. d[i] = value?d) A method that it throws "NoSuchElementException" rather than returning -1 whenvalue does not occur in d?• Summary: When implementing a spec, we can have– Weaker preconditions (more possible call states allowed)– Stronger postconditions (fewer possible return states)Polymorphism Using Objectclass IntegerStack { class Entry { Integer elt; Entry next; Entry(Integer i, Entry n) { elt = i; next = n; } } Entry theStack; void push(Integer i) { theStack = new Entry(i, theStack); } Integer pop() throws EmptyStackException { if (theStack == null) throw new EmptyStackException(); else { Integer i = theStack.elt ; theStack = theStack.next; return i; }}}IntegerStack ClientIntegerStack is = new IntegerStack();Integer i;is.push(new Integer(3));is.push(new Integer(4));i = is.pop();• This is OK, but what if we want other kinds of stacks?– Need to make one XStack for each kind of X– Problems: Not pretty, code bloat, maintainability nightmarePolymorphism Using Objectclass Stack { class Entry { Object elt; Entry next; Entry(Object i, Entry n) { elt = i; next = n; } } Entry theStack; void push(Object i) { theStack = new Entry(i, theStack); } Object pop() throws EmptyStackException { if (theStack == null) throw new EmptyStackException(); else { Object i = theStack.elt; theStack = theStack.next; return i; }}}Stack ClientStack is = new Stack();Integer i;is.push(new Integer(3));is.push(new Integer(4));i = (Integer) is.pop();• Now Stacks are reusable– push() works the same– But now pop() returns an Object• Have to downcast back to Integer• Not checked until run-timeGeneral Problem• When we move from an X container to an Objectcontainer– Methods that take X’s as input parameters are OK• If you’re allowed to pass Object in, you can pass any X in– Methods that return X’s as results require downcasts• You only get Objects out, which you need to cast down to X• This is a general feature of subtype polymorphismParametric Polymorphism• Idea: We can parameterize the Stack class by itselement type• Syntax:– Class declaration: class A<T> { ... }• A is the class name, as before• T is a type variable, can be used in body of class (...)– Usage: A<Integer> x;• We instantiate A with the Integer typeParametric Polymorphism for Stackclass Stack<Element> { class Entry { Element elt; Entry next; Entry(Element i, Entry n) { elt = i; next = n; } } Entry theStack; void push(Element i) { theStack = new Entry(i, theStack); } Element pop() throws EmptyStackException { if (theStack == null) throw new EmptyStackException(); else { Element i = theStack.elt; theStack = theStack.next; return i; }}}Stack<Element> ClientStack<Integer> is = new Stack<Integer>();Integer i;is.push(new Integer(3));is.push(new Integer(4));i = is.pop();• No downcasts• Type-checked at compile time• No need to duplicate Stack code for every usageThe Identity Function• Suppose B is a subtype of A1. static A id(A x) {
View Full Document
Unlocking...