Modularity and Object-Oriented ProgrammingReading AssignmentTopicsStepwise RefinementDijkstra’s Example (1969)Program StructureData RefinementExampleModularity: Basic ConceptsExample: Function ComponentExample: Data TypeUsing Priority Queue Data TypeAbstract Data Types (ADT)ModulesModules and Data AbstractionGeneric AbstractionsC++ TemplatesC++ Standard Template LibraryMain Entities in STLExample of STL ApproachMerge in STLSTL vs. “Raw” C and C++Object-Oriented ProgrammingObjectsDynamic LookupOverloading vs. Dynamic LookupEncapsulationSubtyping and Inheritance Object InterfacesSubtypingExampleObject-Oriented Program StructureExample: Geometry LibraryShapesSubtype HierarchyCode Placed in ClassesUsage Example: Processing LoopSubtyping  Inheritanceslide 1Vitaly ShmatikovCS 345Modularity andObject-Oriented Programmingslide 2Reading AssignmentMitchell, Chapters 9 and 10slide 3TopicsModular program development• Stepwise refinement• Interface, specification, and implementationLanguage support for modularity• Procedural abstraction• Abstract data types• Packages and modules• Generic abstractions– Functions and modules with type parametersslide 4Stepwise Refinement“… program ... gradually developed in a sequence of refinement steps … In each step, instructions … are decomposed into more detailed instructions.”• Niklaus Wirth, 1971slide 5Dijkstra’s Example (1969)beginprint first 1000 primesendbeginvariable table pfill table p with first 1000 primesprint table pendbeginint array p[1:1000]make for k from 1 to 1000p[k] equal to k-th primeprint p[k] for k from 1 to 1000endslide 6Program StructureMain ProgramSub-program Sub-program Sub-programSub-programSub-programslide 7Data Refinement“As tasks are refined, so the data may have to be refined, decomposed, or structured, and it is natural to refine program and data specifications in parallel”• Wirth, 1971slide 8ExampleFor level 2, represent account balance by integer variableFor level 3, need to maintain list of past transactionsBank TransactionsDeposit Withdraw Print StatementPrint transaction historyslide 9Modularity: Basic ConceptsComponent• Meaningful program unit– Function, data structure, module, …Interface• Types and operations defined within a component that are visible outside the componentSpecification• Intended behavior of component, expressed as property observable through interface Implementation• Data structures and functions inside componentslide 10Example: Function ComponentComponent• Function to compute square rootInterface• float sqroot (float x)Specification• If x>1, then sqrt(x)*sqrt(x) ≈ x.Implementationfloat sqroot (float x){float y = x/2; float step=x/4; int i;for (i=0; i<20; i++){if ((y*y)<x) y=y+step; else y=y-step; step = step/2;}return y;}slide 11Example: Data TypeComponent• Priority queue: data structure that returns elements in order of decreasing priorityInterface• Type pq• Operations empty : pqinsert : elt * pq → pqdeletemax : pq → elt * pqSpecification• Insert adds to set of stored elements• Deletemax returns max elt and pq of remaining eltsslide 12Using Priority Queue Data TypePriority queue: structure with three operationsempty : pqinsert : elt * pq → pqdeletemax : pq → elt * pqAlgorithm using priority queue (heap sort)begin create empty pq sinsert each element from array into sremove elts in decreasing order and place in arrayendslide 13Abstract Data Types (ADT)Prominent language development of 1970sIdea 1: Separate interface from implementation• Example: Sets have operations empty, insert, union, is_member?, …Sets are implemented as … linked list … Idea 2: Use type checking to enforce separation• Client program only has access to operations in the interface• Implementation encapsulated inside ADT constructslide 14ModulesGeneral construct for information hiding• Known as modules (Modula), packages (Ada), structures (ML), …Interface:• A set of names and their typesImplementation: • Declaration for every entry in the interface• Additional declarations that are hiddenslide 15Modules and Data Abstractionmodule Setinterfacetype setval empty : setfun insert : elt * set -> set fun union : set * set -> setfun isMember : elt * set -> boolimplementationtype set = elt listval empty = nilfun insert(x, elts) = ... fun union(…) = ... ...end Set Can define ADT• Private type• Public operations Modules are more general• Several related types and operations Some languages separate interface & implementation• One interface can have multiple implementationsslide 16Generic AbstractionsParameterize modules by types, other modulesCreate general implementations • Can be instantiated in many ways• Same implementation for multiple typesLanguage examples:• Ada generic packages, C++ templates (especially STL –Standard Template Library), ML functors, …slide 17C++ TemplatesType parameterization mechanism• template<class T> … indicates type parameter T• C++ has class templates and function templatesInstantiation at link time• Separate copy of template generated for each type• Why code duplication?– Size of local variables in activation record– Link to operations on parameter typeRemember swap function?• See lecture notes on overloading and polymorphismslide 18C++ Standard Template LibraryMany generic abstractions• Polymorphic abstract types and operations• Excellent example of generic programmingEfficient running time(but not always space)Written in C++• Uses template mechanism and overloading• Does not rely on objects – no virtual functions!Architect: Alex Stepanovslide 19Main Entities in STLContainer: Collection of typed objects• Examples: array, list, associative dictionary, ...Iterator: Generalization of pointer or addressAlgorithmAdapter: Convert from one form to another• Example: produce iterator from updatable containerFunction object: Form of closure (“by hand”)Allocator: encapsulation of a memory pool• Example: GC memory, ref count memory, ...slide 20Example of STL ApproachFunction to merge two sorted lists (concept)• merge : range(s) × range(t) × comparison(u) → range(u)• range(s) - ordered “list” of elements of type s, given by pointers to first and last elements• comparison(u) - boolean-valued