EECS 280 Programming and Introductory Data Structures Interfaces and Invariants Slides by Andrew DeOrio, Jeff Ringenberg and Brian Noble 1 Abstract Data Type Review Recall the two main advantages of an ADT: 1. Information hiding: we don't need to know the details of how the object is represented, nor do we need to know how the operations on those objects are implemented. 2. Encapsulation: the objects and their operations are defined in the same place; the ADT combines both data and operation in one entity. 2 Abstract Data Type Review To the caller, an ADT is only an interface Here are two definitions: Good Definition: The contract for using things of this type. Better Definition: The set of assumptions that each programmer needs to make about another's code in order to demonstrate the correctness of his/her own code. Once you have an interface, you can pick from among many possible implementations as long as you satisfy the (implied) contract. 3 Interfaces The class mechanism, as we've used it so far, has one shortcoming: It co-mingles details of the implementation with the definition of the interface. Recall that the implementation of a class includes: 1. Data members 2. Method implementations The method implementations can be written separately from the class definition and usually are 4 Interfaces For example, if we were really building an IntSet, we'd split it across two files: IntSet.h : the class IntSet {...} definition IntSet.cpp : the implementation of each method Unfortunately, the data members still must be part of the class definition in IntSet.h Since any programmer using an IntSet must see that definition, those programmers know something about the implementation However, in a well-designed class, any implementation- specific bits must be private. So, client code can't touch those objects. 5 Interfaces Having data objects in the definition has two undesirable effects: 1. It complicates the class definition, making it harder to read and understand. 2. It communicates information to the programmer that s/he isn't supposed to know. The second problem can have very drastic consequences. If a programmer using your class (mistakenly) makes an assumption about a "guarantee" that your implementation provides, but the interface doesn't promise, you're in trouble. What if you change the implementation? 6 Interfaces Question: How can you provide a class definition that carries no implementation details to the client programmer, yet still has interface information? Remember, classes must contain their data members, so this means that the class cannot have an implementation. Answer: Create an "interface-only" class as an abstract base class, from which an implementation can be derived. 7 Interfaces To create an abstract base class, we first provide an interface only definition of IntSet. This class will never be instantiated because there is no implementation Use pure virtual functions to do this 8 IntSet Abstract Class class IntSet { // OVERVIEW: interface for a mutable set of ints // with bounded size public: virtual void insert(int v) = 0; virtual void remove(int v) = 0; virtual bool query(int v) const = 0; virtual int size() const = 0; }; 9 Abstract Class Review A class with any pure virtual function is an abstract class You cannot create an instance of an abstract class, because there can be no implementation int main() { IntSet is; //compile error! } You can create a pointer or reference to an abstract class int main() { IntSet *is_ptr; //OK IntSet &is_ref; //OK } 10 Implementing the Interface Abstract base classes aren't very interesting without some derivative of IntSet to actually provide an implementation This is done with a derived class: class IntSetUnsorted : public IntSet { int elts[ELTS_CAPACITY]; int elts_size; int indexOf() const; public: static const int ELTS_CAPACITY = 100; IntSetUnsorted(); virtual void insert(int v); virtual void remove(int v); virtual bool query(int v) const; virtual int size() const; }; 11 We could implement either the sorted or unsorted version Implementing the Interface Abstract base classes aren't very interesting without some derivative of IntSet to actually provide an implementation This is done with a simple derived class: class IntSetUnsorted : public IntSet { int elts[ELTS_CAPACITY]; int elts_size; int indexOf() const; public: static const int ELTS_CAPACITY = 100; IntSetUnsorted(); virtual void insert(int v); virtual void remove(int v); virtual bool query(int v) const; virtual int size() const; }; 12 The derived class has to implement the constructor because the base class has no implementation to construct! Implementing the Interface We can also create an implementation that is sorted class IntSetSorted : public IntSet { int elts[ELTS_CAPACITY]; int elts_size; int indexOf() const; public: static const int ELTS_CAPACITY = 100; IntSetSorted(); virtual void insert(int v); virtual void remove(int v); virtual bool query(int v) const; virtual int size() const; }; 13 Using the Interface To use our IntSet interface, all we need to know are the public member functions, which would be in IntSet.h class IntSet { // OVERVIEW: interface for a mutable set of ints // with bounded size public: virtual void insert(int v) = 0; virtual void remove(int v) = 0; virtual bool query(int v) const = 0; virtual int size() const = 0; }; 14 Using the Interface Now that we have an interface (IntSet) and two implementations (IntSetUnsorted and IntSetSorted), we can use our interface int main() { IntSetUnsorted is; IntSet *is_ptr = &is; //pointer to implementation is_ptr->insert(7); is_ptr->insert(4); is_ptr->insert(7); is_ptr->insert(1); is_ptr->remove(4); } 15 Using the Interface The cool part: we can switch the implementation and the old code still works! This is an example of a subtype. int main() { IntSetUnsorted IntSetSorted is; IntSet *is_ptr = &is; //pointer to implementation is_ptr->insert(7); is_ptr->insert(4); is_ptr->insert(7); is_ptr->insert(1); is_ptr->remove(4); } 16 Invariants Review An invariant is something that is always true In other words, it is a set of conditions that must always evaluate to true at certain well-defined points in the program, otherwise, the program is incorrect We've seen three kinds of invariants: Recursive invariant Iterative invariant Representation invariant 17 Recursive Invariant Review A recursive invariant applies to the arguments of a recursive function A recursive invariant describes the conditions that must be satisfied by any call to the function For example, in our tail-recursive factorial function, the recursive invariant was n! * result == num! int fact_helper(int n, int result) {/*...*/} int factorial(int num) { return fact_helper(num, 1); } 18 Iterative Invariant Review An iterative invariant applies to each loop variable An iterative invariant must be true before and after each iteration For example, in our iterative factorial function, the iterative invariant was n! * result == num! int factorial(int num) { int n = num; int result = 1; while (n!=0) { result *= n; n -= 1; } return result; } 19 Representation Invariant Review A representation invariant applies to the data members of an ADT Recall that member variables are a class's representation A representation invariant must be true immediately before and immediately after any member function execution Think of it as a "sanity check" for the ADT 20 Representation Invariant Details A representation invariant must be true immediately before and immediately after any member function execution Each method in the class is free to assume that the invariant is true on entry if: The representation invariant holds at the required times, and Each data element is truly private This is true because the only code that can change them belongs to the methods of that class, and those methods always establish the invariant 21 Representation Invariant Details A representation invariant must be true immediately before and immediately after any member function execution Exception: constructors The constructor establishes the representation invariant, so the representation invariant only has to hold at the end Exception: destructors There is one sort of method, called a destructor, where the representation invariant only has to hold at the beginning We won’t see this until later 22 Representation Invariant Example We've seen two examples of representation invariants, both applying to the private members of an IntSet representation: int elts[ELTS_CAPACITY]; int elts_size; For the unsorted version, the invariant is: The first elts_size members of elts contain the integers comprising the set, with no duplicates. For the sorted version, the invariant is: The first elts_size members of elts contain the integers comprising the set, from lowest to highest, with no duplicates. 23 Representation Invariant Example We used these invariants to write the methods of each implementation. For example: insert(int v) // unsorted version if v not in elts // don’t allow duplicates elts[elts_size] = v// this breaks invariant ++elts_size // this restores it insert(int v) // sorted version if v not in elts // don’t allow duplicates make gap in array // this breaks invariant elts[gap] = v // restore elts invariant ++elts_size // restore elts_size invar. 24 Using Representation Invariants The representation invariant plays a crucial role in implementing an abstract data type Before writing a single line of code, write down the rep invariant! That tells you how to write each method Then, for each method you: 1. Do the work of the method (i.e. insert) 2. Repair the invariants you broke 25 Check the Representation Invariant We've seen representation invariants written in English: IntSetSorted: The first elts_size members of elts contain the integers comprising the set, from lowest to highest, with no duplicates. We can also write representation invariants in code For even moderately complicated data structures, it is worth coding the representation invariant before coding anything else Let's add a private member function to IntSetSorted called check_invariant() that checks the representation invariant 26 Exercise class IntSetSorted : public IntSet { //... private: //Represent a set of size N as an sorted set of //integers, with no duplicates, stored in the //first N slots of the array int elts[ELTS_CAPACITY]; //Number of elements currently in the set int elts_size; //EFFECTS: returns true if rep. invariant holds bool check_invariant() const; }; 27 Write this function using a loop Using check_invariant() You can use check functions for defensive programming Add a check to the end of each member function Add a check to the beginning too, if you’re really paranoid assert() is the perfect way to make these checks 29 assert() A programmer’s best friend assert(STATEMENT); Make sure that STATEMENT is true If not, crash the program with a debugging message #include void IntSet::insert(int v) { assert(check_invariant()); //... } 30 a.out: Interfaces_and_Invariants.cpp:146: IntSetUnsorted::insert(): Assertion `check_invariant()' failed. Aborted (core dumped) assert() + check_invariant() Add a check to each member function Check at the end of the constructor IntSetSorted::IntSetSorted() : elts_size(0) { assert(check_invariant()); } Check at the beginning and at the end of other functions void IntSetSorted::insert(int v) { assert(check_invariant()); //... assert(check_invariant()); } 31 assert() + check_invariant() const member functions can't change any member variable, so we only need a check at the beginning int IntSetSorted::size() const { assert(check_invariant()); return elts_size; } 32 Check the Representation Invariant Let's a add a similar private member function called check_invariant() that checks the representation invariant for IntSetUnsorted 33 Exercise class IntSetUnsorted : public IntSet { //... private: //Represent a set of size N as an unsorted set of //integers, with no duplicates, stored in the //first N slots of the array int elts[ELTS_CAPACITY]; //Number of elements currently in the set int elts_size; //EFFECTS: returns true if rep. invariant holds bool check_invariant() const; }; 34 Write this function using nested loops Invariants and assert() The nested loop in check_invariant() might be slow It's worth it during testing, but not in the final product Disable the check by compiling with the NDEBUG preprocessor variable defined There are two ways to do this: 1. Add a line of code #define NDEBUG //disable assert() 2. Specify it on the command line of the compiler: g++ -DNDEBUG ... This way, you can turn it off for production code, but leave it in during development and testing 40 Invariants and assert() #define NDEBUG // disables assert statements! void IntSet::insert(int v) { // ... assert(check_invariant()); } void IntSet::remove(int v) { // ... assert(check_invariant()); } 41