Functional decomposition, abstraction, encapsulation P.J. Drongowski 11 September 2004 Scaling up * Complexity grows very fast and must be managed + Example: design of very large scale integrated (VLSI) systems - 40,000,000+ transistors in modern microprocessor - Cannot possibly hand draw every transistor or subsystem * Implications + Design is beyond the intellectual capability of any single engineer + Development must be a team effort + Interpersonal communication is essential - It's difficult to agree on the meaning of common terms - "Massive semantic by-pass" * Better tools and techniques are needed + Must increase productivity to meet time-to-market demands + Must assure correctness and performance (quality) + Must be able to support a product throughout a lengthy lifecycle + Need techniques and processes that are repeatable in order to forecast staffing and delivery schedule * VLSI system design is a good "role model" + Uniformity and consistency: Same design principles and style is used everywhere, e.g., intercommunication between components, clock scheme + Regularity: A few basic structures are replicated many times; interconnection by abutment * Yo-yo design + Capture and decompose functionality (top-down) + Assess and assure adequate performance (bottom-up) + Need a "crystal ball" during top-down design to guide decisions or frequent prototyping to identify performance issues + Poor choices during system-level design mean expensive fixes later, especially if interfaces need to be ripped up Two major principles governing functional decomposition * Abstraction * Encapsulation What is abstraction? * We touched on abstraction when discussion iTunes -- what were the real-world objects modelled by iTunes? * What are the aspects of a description or model that are important? * What aspects of description or model are unimportant and can be ignored? * What aspects of a real world problem should we represent? * Example of abstraction: Different kinds of maps + Road map + Time and distance travel map + Topographic map + Aeronautical + Airline route map * iTunes example again + Did iTunes' developers care about the weight of an Album's CD? + Did iTunes' developers care about album art? - Tricky question: Initially, no - Customers eventually wanted this feature - Systems must be extensible - Beware of changes! Plan for evolution! Encapsulation * Encapsulation partitions behavior into modules * Is also called "information hiding" or "transparency" + "What" versus "how" + Inner implementation (algorithm, data structure) is invisible + Only public or visible behavior is exposed + Other modules use and rely upon visible behavior + Hide design decisions such that the decision can be changed later without disturbing either the interface or any module using the interface * Encapsulation is very important + Improves maintainability through isolation of design decisions + Assists testing by quickly isolating errors to individual modules + Introduces problem of integration and integration testing + Errors at interfaces are very costly and more difficult to fix since they involve one or more modules at the interface * Classic papers + A technique for software module specification with examples, David L. Parnas, CACM, Vol. 15, No. 5, May 1972, pg. 330-336 + On the criteria to be used in decomposing systems into modules, David L. Parnas, CACM, Vol. 15, No. 12, Dec 1972, pg. 1053-1058 Vending machine model of computation / behavior * What are externally visible parts of a vending machine? + Buttons (to select a product, to return coins) + Coin slot (to accept money) + Lights (to ask for more money, to indicate an empty machine) + Delivery chute (to get snacks, to return a bottle of pop) * Typical customer scenario + Customer deposits coins in the coin slot + Pushes a button to select the product to buy + Machine delivers the product via the delivery chute + Customer removes the product * Other customer scenarios are possible + Not enough money has been paid (turn on "more money" light) + Too much money has been paid (return change after purchase) + No more product is available (turn on "machine is empty" light) * There are agreements between the customer and the machine vendor + The machine will return aire value (all coins if sale is cancelled, can of soda plus change, etc.) + The machine returns the correct product when a button is pushed (Diet Pepsi and not Sierra Mist) * What happens when agreement is not kept (satisfied?) + When wrong product is returned? + When coins are not returned? + When non-US coins are inserted or returned? * The vending machine company makes many machines, all the same + It doesn't make sense to build just one machine + It doesn't make sense to make all machines different + The factory uses a plan to make the vending machines * Does the customer know how the machine works inside? * Does the customer care as long as the agreements are kept and the machine works correctly? Encapsulation in practice -- how to implement an ADT in C++ using a class * A class is a plan for making objects; an object is an instance of a class (an individual vending machine) * Inheritance + Vending machines that all serve the same function (e.g., vending machine for soda, vending machine for snacks) + Differentiation through paint, product, price, button labels * Public method functions (buttons) + Function arguments (coins and other inputs) + Return values (signal lights, snacks and other outputs) * Private method functions and data + Hidden from the outside world + Can only be manipulated via the public method methods -- the published public interface (sometimes called an "Application Program Interface") Specification of module interfaces is very important * "Build to" and "test to" specification * Specification should be precise, unambiguous, explicit * Two examples of specification language (both are "model-based" and use "this state - next state semantics") + SPECIAL - SRI International - Kind of old, but style has appeal for practical software developers - Used to specify operating system software (PJD and Tom Berson specified v6 UNIX using SPECIAL) + Z (pronounced "zed") Notation - First developed at Oxford University in the 70's - Became popular in the 90's - Based on set theory and first order predicate calculus - Specification only, not much tooling (LaTeX macros) + URLs - Z user's group: http://vl.zuser.org/ - "Using Z" by Jim Woodcock and Jim Davies: http://www.usingz.com/ These design principles apply to both software and hardware development * The main differences are: + Implementation technology and related performance characteristics (speed, space and power) + Communication mechanisms/conventions that are enforced by the compiler, synthesis tool or hardware design style/rules * Software communications conventions + Subroutine call - Save working registers - Put arguments on stack (or in procedure display) - Call subroutine and save the return address - Return result on stack or in general register - Restore working registers - Examples: C, C++ + Message passing - Receiving object has a dictionary of methods - Invoking object sends a message with the method name and arguments - The receiving object invokes the method - Receiver may replay to sender with a result message - Examples: Smalltalk, Actors * Hardware communications conventions + Synchronous - Sender and receiver both step to a common clock - Sender and reciever agree to exchange data within a time window - Sender must produce results to be consumed by the receiver within the prearranged period -- late data is missed - Examples: Single-phase clock, two-phase non-overlapping clock + Asynchronous - Similar to vending machine model - Supply arguments and make request - Produce results and signal completion - Computation can take as long as it needs ("self-timed") - Examples: Two cycle handshaking, four cycle handshaking /* * A fun C++ example using inheritance ("one from the crypt" :-) */ #include using namespace std ; class Register { private: unsigned int value ; public: Register() { value = 0 ; } void clear() { value = 0 ; } void load(int newValue) { value = newValue ; } unsigned int read() { return(value) ; } } ; class Counter : public Register { public: void increment() { load(read() + 1) ; } void decrement() { load(read() - 1) ; } } ; class ShiftRegister : public Register { public: void left() { load(read() << 1) ; } void right() { load(read() >> 1) ; } } ; int main(int argc, char *argv[]) { Register ir ; Counter pc ; ShiftRegister ac ; pc.clear() ; pc.increment() ; pc.increment() ; ac.load(0x80) ; ac.right() ; cout << "pc: " << pc.read() << endl ; cout << "ac: " << hex << ac.read() << endl ; }