6.005 14. Rep invariants, equality, visitors

MIT OpenCourseWarehttp://ocw.mit.edu 6.005 Elements of Software Construction Fall 2008 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms. 6.005elements ofsoftwareconstruction rep invariants, equality, visitorsDaniel Jackson plan for todayrecall strategy for avoiding bugs ‣ make them impossible ‣ don’t insert them ‣ make them easy to find topics ‣ advice on implementing types ‣ equality and how to code it ‣ rep invariants & how to exploit them patterns ‣ Iterator and Visitor © Daniel Jackson 2008 2 advice on implementing typesstep 1: design a repdesiderata ‣ easy to program (and get right!) ‣ good enough performance usually ‣ a couple of fields of existing types suffices ‣ so before inventing a complex type, check Java collections and your own sometimes ‣ a tricky structure or algorithm is needed ‣ first, see if someone’s done it before (eg, look it up in CLR book) always ‣ write a rep invariant to clarify the design 4 © Daniel Jackson 2008 step 2: write the methodsrequired methods first ‣ from Object class: equals, hashCode, to String more on hashCode in part 3 of course ‣ from any interface the class implements ‣ when overriding, mark with @Override constructors ‣ for an immutable type, some private constructors often help producers (return new values of type) and observers (return other types) ‣ whenever possible, build on each other ‣ separate core methods (eg, size) from those that sit on top (eg. isEmpty) incomplete methods ‣ use UnsupportedOperationException to get it to compile 5 © Daniel Jackson 2008 step 3: rep invariantcode the rep invariant ‣ as a checkRep method ‣ for immutables, call it at the end of all constructors as you write the operations ‣ ask yourself why they preserve the rep invariant 6 © Daniel Jackson 2008 step 4: assertions and testsruntime assertions ‣ are your friend: use them freely ‣ turn on by adding -ea to VM args in Eclipse write JUnit test suite for your class ‣ will help you find bugs earlier, and make debugging easier ‣ take the trouble to write a toString that produces helpful output 7 © Daniel Jackson 2008 equality: basicsfundamentalsobjects often used as keys ‣ need to compare them ‣ eg, Literal used as key in Environment Java convention ‣ the class Object has a method that every class inherits Object.equals: Object -> boolean ‣ by convention, this method is used to compare objects for equality ‣ collections especially assume this: call equals on keys ‣ the inherited method is usually wrong for immutable types ‣ so must override by explicitly declaring a method MyType.equals: Object -> boolean 9 © Daniel Jackson 2008 why inherited equality failsthe problem ‣ Object.equals compares objects with == ‣ this makes any two distinct objects unequal ‣ even if they have the same value example ‣ the “same” pairs are unequal: public class Pair { private int fst, snd; public Pair (int f, int s) {fst=f; snd=s;} public static void main (String[] args) { Pair p1 = new Pair (1, 2); Pair p2 = new Pair (1, 2); System.out.println (p1 == p2 ? "yes" : "no"); System.out.println (p1.equals(p2) ? "yes" : "no"); }}10© Daniel Jackson 2008 standard equals methodcorrect code for Pair.equals ‣ compare the fields @Override public boolean equals (Object that) { if (this == that) return true; if (!(that instanceof Pair)) return false; Pair p = (Pair) that; return p.fst == fst && p.snd == snd; }remember: comparison is with any object reference ‣ need to check type of arg, and whether null ‣ you may be tempted to write this, but don’t: it will just overload equals public boolean equals (Pair that) {...}‣ write @Override and compiler will catch the bug 11 © Daniel Jackson 2008 a design puzzleinterning objects ‣ suppose you have a structure containing objects of type C ‣ you want to intern them: that is, have one object for each value ‣ so you write this code, but it won’t work (why not?) public class C { private String s; public static Map allocated = new ListMap(); public C intern () { C c = allocated.get(this); if (c == null) { allocated = allocated.put(this, this); return this; } return c; }}12 © Daniel Jackson 2008 approaches the problem: one equals method ‣ if it compares references with ==, then lookup won’t find match ‣ it it compares values, then interning is pointless! have collection take equality predicate as argument ‣ can’t use standard Java collections: will have to make your own ‣ but see use of comparator objects in ordered types like java.util.TreeSet use component as key instead of whole object ‣ eg, allocated maps String to C ‣ this is how the factory method of PosLiteral works (previous lecture) for key, make wrapper around C object with its own equals ‣ not terrible, but a bit ugly 13 © Daniel Jackson 2008 rep invariantsR/A[1,1,2][1][1,2][2,1][]{}{1}{1,2}AIntListIntSetRrep invariant R ‣ defines set of legal representation values ‣ documented and implemented as checkRep abstraction function A ‣ interprets legal representation values as abstract values ‣ documented and implemented as toString 15 © Daniel Jackson 2008 how to establish invariantsfor state machines ‣ establish invariant in initial state ‣ ensure that all transitions preserve invariant for mutable types, the same approach ‣ a mutable object is a state machine for immutable types, a similar story ‣ objects can’t change ‣ assume any argument you’re given satisfies the invariant ‣ ensure any result you create satisfies it too who gets to preserve the invariant? ‣ by hiding the rep, can limit to the methods of the ADT itself 16 © Daniel Jackson 2008 implicationsa strong invariant means ‣ methods can assume more about arguments ‣ allows checks to be omitted and optimizations to be applied ‣ but methods must do more to ensure results satisfy invariant rep design = rep invariant ‣ the choice of rep invariant characterizes the design of the rep! 17 © Daniel Jackson 2008 common invariantsthese invariants ‣ are commonly used ‣ provide concrete benefits examples ‣ no nulls: no need to check before calling method ‣ acyclic: no need to worry about looping ‣ ordered: can navigate efficiently; can stop when key value is passed ‣ no duplicates: can stop when find first match ‣ caching: can do fast look up 18 © Daniel Jackson 2008 example: invariant for Clausewriting the invariantrep invariant for Clause written as executable method flag to turn expensive check off public class Clause {private final List literals;static final boolean CHECKREP = true; void checkRep () {checkRep (literals);} void checkRep (List ls) { assert ls != null : "Clause, invariant: literals non-null"; if (!ls.isEmpty()) { Literal first = ls.first(); List rest = ls.rest(); assert first != null : "Clause, invariant: no null elements"; assert !rest.contains(first) : "Clause, invariant: no duplicates"; assert !rest.contains(first.getNegation()) : "Clause, invariant: no literal messages giveinvariant informallyand its negation"; checkRep (rest); } }private Clause(List literals) {this.literals = literals;if (CHECKREP) checkRep(); }...}what’s the computational cost of checkRep? check rep for each constructed value 20 © Daniel Jackson 2008 exploiting the invariantan equals method for Clause @Overridepublic boolean equals (Object that) { if (this == that) return true; if (!(that instanceof Clause)) return false; Clause c = (Clause) that; if (size() != c.size()) return false; for (Literal l: literals) if (!(c.contains(l))) return false; return true;}how invariant is exploited ‣ since literals is non-null, can use in for-loop without null check implicit call to literals.iterator will throw exception if literals is null ‣ since no duplicate literals, can check containment in one direction only that is, given two sets S and T: S = T ⇔ #S = #T ∧ S ⊆ T 21 © Daniel Jackson 2008 preserving the invariant no free lunch ‣ you have to do some work to establish the invariant example: Clause.add /*** Add a literal to this clause; if already contains the literal's negation, return null* Requires: l is non-null* @return the new clause with the literal added, or null*/public Clause add(Literal l) {if (literals.contains(l)) return this;if (literals.contains(l.getNegation())) return null;return new Clause(literals.add(l));}‣ what impact does each part of the invariant have? 22 © Daniel Jackson 2008 exploiting the invariant exercise: how does reduce exploit the invariant? /*** Requires: literal is non-null* @return clause obtained by setting literal to true* or null if the entire clause becomes true*/public Clause reduce(Literal literal) { List reducedLiterals = reduce(literals, literal);if (reducedLiterals == null) return null;else return new Clause(reducedLiterals);}private static List reduce(List literals, Literal l) {if (literals.isEmpty()) return literals; Literal first = literals.first();List rest = literals.rest();if (first.equals(l)) return null;else if (first.equals(l.getNegation())) return rest;else {List restR = reduce(rest, l);if (restR == null) return null;return restR.add(first); }}23 © Daniel Jackson 2008 iterator patterniteration in Javarecall how our solver found a minimal clause‣ iterate over clauses Clause min = null;for (Clause c : clauses) {if (c.isEmpty()) return null;if (min == null || c.size() < min.size()) min = c;} ...how does this work? ‣ hidden iterator at play 25 © Daniel Jackson 2008 the iterator patterna Java shorthand list iterator public class ListIterator implements Iterator {‣ the statement List remaining;for (E e: c) {...} public ListIterator (List list) {remaining = list;‣ is short for } public boolean hasNext () {Iterator i = c.iterator(); return !remaining.isEmpty();while (i.hasNext()) { }E e = i.next(); public E next () { E first = remaining.first (); ... remaining = remaining.rest(); } return first; }}iterator interface iterator method public interface Iterator { public abstract class List implements Iterable boolean hasNext (); public Iterator iterator () {E next (); return new ListIterator(this);} void remove (); } }26 © Daniel Jackson 2008 iterator state machineNONEMPTYgetNextEMPTYhasNext(true)hasNext(false)getNextwhy a stateful object in a side-effect free program? ‣ the only convenient way to do iteration in Java ‣ so long as iterator used only in for loop as shown, no mutability issues arise 27© Daniel Jackson 2008visitor patternlocalizing functions Interpreter pattern: look what we’re doing ‣ declare function over datatype size: List -> int where List = Empty + Cons (first: T, rest: List) ‣ break function into cases, one per variant size (Empty) = 0 size (Cons(first:e, rest: l)) = 1 + size(l) ‣ but then split cases across classes! can’t we keep them together? ‣ in functional language can do exactly this: (in ML, eg) fun size Empty = 0| Cons(e, l) = 1 + size(l)solution: localize function definition in “visitor” ‣ hard to grasp first time, but easy once you know the pattern ‣ a useful and common idiom, esp. for compilers ‣ good check of your understanding of dynamic dispatch & overloading 29 © Daniel Jackson 2008 basic visitor structure‣ visitor public interface ListIntVisitor { int onEmpty (Empty l); int onCons (Cons l);} public class SizeVisitor implements ListIntVisitor{ public int onEmpty(Empty l) {return 0;} public int onCons(Cons l) {return 1 + l.rest().accept(this);} }‣ datatype and variants public abstract class List {public abstract int accept(ListIntVisitor visitor);}public class Empty extends List {public int accept(ListIntVisitor visitor) {return visitor.onEmpty(this);} }public class Cons extends List {public int accept(ListIntVisitor visitor) {return visitor.onCons(this);}}‣ usage int size = myList.accept(new SizeVisitor());30 © Daniel Jackson 2008 the visitor carouselConsEmptyLiteralSizeVisitorlv12345restfirst1:l.accept(v)2:v.onCons(l)3:l.rest().accept(v) + 14:v.onEmpty(e)5: return 0note how ‣ control passes back and forth between visitor and datatype objects ‣ function is computed at visitor (steps 3 and 5) 31© Daniel Jackson 2008going polymorphicaccept methods only work for visitor that returns integer public interface ListIntVisitor { int onEmpty (Empty l); int onCons (Cons l);}so make the visitor polymorphic ‣ new interface public interface ListVisitor { T onEmpty (Empty l); T onCons (Cons l);}‣ new accept methods public T accept(ListVisitor visitor) {return visitor.onEmptyList(this);}‣ new visitor public class SizeVisitor implements ListVisitor{ public Integer onEmpty(Empty l) {return 0;} public Integer onCons(Cons l) {return 1 + l.rest().accept(this);}}32 © Daniel Jackson 2008 !nal re!nementaccept method is almost boilerplate public class Cons extends List {public int accept(ListIntVisitor visitor) {return visitor.onCons(this);}}can make identical by exploiting overloading ‣ new interface public interface ListVisitor { T visit (Empty l); T visit (Cons l);}‣ new accept method: same in all variants public T accept(ListVisitor visitor) {return visitor.visit(this);}‣ new visitor public class SizeVisitor implements ListVisitor{ public Integer visit (Empty l) {return 0;} public Integer visit (Cons l) {return 1 + l.rest().accept(this);}}33 © Daniel Jackson 2008 summaryprinciplesuse rep invariants to prevent bugs ‣ and to make them easier to find ‣ design of type = rep invariant equality is tricky ‣ for immutables, compare contents not object refs ‣ (not covered in lecture) if you override equals, must override hashCode too visitor pattern ‣ some boilerplate code in datatypes ‣ allows one function/class 35 © Daniel Jackson 2008