Topics
. Modular program development
. Step-wise refinement
. Interface, specification, and implementation
. language support for modularity
. Procedural abstraction
. Abstract data types
. Packages and modules
. Generic abstractions
. Functions and modules with type parameters
. Stepwise Refinement
. Wirth, 1971
. "program gradually developed in a sequence of refinement steps"
. In each step, instructions .. are decomposed into more detailed instructinos.
. Historical reading on web
. N.wirth, program development by stepwise refinement, Communications of the ACM, 1971
. D. Parnas, On the criteria to be used in decomposing systems into modules, Comm ACM, 1972
. Both ACM Classics of the Month
. Dijkstra's Example
. 간단하게 주석처럼 쓰고 점점 코드에 가깝게 만들어 감.
. Program Structure
. Main program - 밑에 여러개의 sub-program의 tree로 hierarchical하게 구성됨.
. Data Refinement
. Wirth, 1971 again:
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.
. Example
. Bank Transactions - Deposit, Withdraw, Print Statement, Print transaction history
. For level 2, represent account balance by integer variable
. For level 3, need to maintain list of past transactions
. Modularity : 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 component
ex) Function Component
. Component : Function to compute square root
. Interface : float sqroot(float x)
. Specification : If x>1, then sqrt(x)*sqrt(x) = x
. Impelmentation
. Bisection method를 구현한 코드를 C로 적음.(길어서 생략)
Ex) Data Type
. component : Priority queue : data structure that returns elements in order of decreasing priority
. Interface
. Type : pq
. Operations :
empty : pq
insert : elt * pq -> pq
deletemax : pq -> elt * pq
. Specification
. Insert add to set of stored elements
. Deletemax returns max elt and pq of remaining elts
. Problem with writing large programs
. Wulf and Shaw : Global Variables Considered Harmful
1. side effects - accesses hidden in functions
2. Indiscriminant access - can't control access
3. Screening - may lose access via new declaration of variable
4. Aliasing
. Characteristics of solution:
1. No implicit inheritance of variables
2. Right to access by mutual consent(담합)
3. Access to structure does not imply access to substructure
4. Provide different types of access
5. Decouple declaration, name access, and allocation of space
. ADT : Abstract Data Types
. Prominent(유명한, 중요한, 탁월한, 현저한) language development of 1970's
. Main ideas:
. Separate interface from implementation
. Sets have empty, insert, union, is_member?
. Sets implemented as .. linked list ..
. Use type checking to enforce separation
. client program only has access to operations in interface
. Implementation encapsulated inside ADT construct
. Abstract Data Types
. Package data structure and its operations in same module
. Data type consists of set of objects plus set of operations on the objects of the type
(constructor, operatos, observers)
. Want mechanism to build new data types(extensible types)
. Should be treated same way as built-in types
. Representation should be hidden from users(abstraction)
. Users only have access via operations provided by the ADT(encapsulation)
. Distinguish between specification and implementation
. ADT Specification
. ADT specification declares data type and operations without implementation details, but possibly with semantics of operations
. Provides information needed to use ADT in programs
. Typically includes
1. Data strcutures : constants, types, and variables accessible to user
(although details may be hidden)
2. Declarations of functions and procedures accessible to user(bodies not provided)
. ADT specification
. May also specify behavioral obligation of an implementation
. As an example, an algebraic specification of behavior of a stack might look like
. Formal specification of ADTs uses universal algebras
. Data + Operations + Equations = Algebra
. ADT impelmentation (Representation)
. Definition of the implementation details of an ADT collected in one location
. Usually not accessible to user - some form of access control
. Provides details on all data structures (including some hidden to users) and
bodies of all operations
. Representation in language
. Three predominant concerns in language design
. Simplicity of design
. Application of formal techniques to specification and verification
. Keep down lifetime costs
. Reusable modules to represent ADTs quite important
. Separate (but not independent) compilation
. Want to maintain type checking
. Control over export and import of names (scope)
. ML Abstype
. ADT supported in very straightforward way in ML
. Provides for encapsulation and information hiding
. Generic stack ADT in ML
. Cannot get at representation of stack
. Reference to mkstack(1) will generate an error message
. Only access through constants and operations
. Module more sophisticated support with separate compilation
. Clu(1974)
. Cluster is basis of support for abstrat data types
. Provides both packaging and hiding of representation
(cvt used to go back and forth between external abstract type and internal representation)
. May have parameterized clusters where specify needed properties of type parameter
. Modules
. General construct for information hiding
. Two parts
. Interface : A set of names and their types
. Impelmentation :
Declaration for every entry in the interface
Additional declarations that are hidden
. Ex) Modula modules, Ada packages, ML structures
. Modules and Data abstraction
. Can define ADT
. Private type
. Public operations
. More general
. Several related types and operations
. some languages
. Separate inferface and implementation
. One interface can have multiple implementations
. Ada (approx 1979)
. Designed via a U.S. DoD competition
. Packages used to define abstract data types
. Package together type, operations (and state) and hide representation
. Provides support for parameterized packages(polymorphism)
. Modula-2
. Modula (modular language) designed by Wirth in 1975 for programming small real-time control systems(no files, sets, or pointers)
. Modula-2 is 1980 revision (influenced by Mesa at Xerox PARC)
intended to synthesize systems programming with general purpose language supporting modern software engineering
. Operating system for Lilith microomputer written in Modula 2
. Minor changes to Pascal to simplify programming (reliability) and improve program readability and efficiency
. Upward extension of Pascal to support large system design projects
(Separately compiled and type checked modules)
. Downward extension to allow machine-level programming and supports coroutines
. Modula-2
. Opaque types (thos declared but undefined in Definition module) must be pointers or take no more space than pointers.
. Compare and contrast Modula-2 and Ada on supporting abstract data types
. Both can import from other units(modules or packages) and export items to other units
. For external representations not mush difference
. Private types in Ada force recompilation if implementation changes, but opaque types in Modula-2 do not.
(구현이 바뀌었을 때 recompile여부가 다름.)
. Internal representations almost identical
. Generics make Ada more flexible - can use to create new instances of packages
. Generic Abstractions
. Parameterize modules by types, other modules
. Create general implementations
. Can be instantiated in many ways
. Language examples
. Ada generic packages, C++ templates, ML functors
. ML geometry modules in book
. C++ Standard Template Library(STL) provides extensive examples
. ADA generic stack example
. Stack represented internally in package
. Data structure of stack is entirely hidden from user - there is no object of type stack available to user.
. C++ 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
. ex)
. Monomorphic swap function
. Polymorphic function template
. STL(Standard Template Library) for C++
. Many generic abstractions
. Polymorphic abstract types and operations
. Useful for many purposes
. 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
. Main 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
. ex) produce iterator from updatable container
. function object : Form of closure("by hand")
. Allocator : encapsulation of a memory pool
. ex) GC memory, ref count memory
. Example of STL approach
. function to merge two sorted lists
. merge : range(s) x range(t) x comparison(u) -> range(u)
. This is conceptually right, but not STL syntax.
. Basic concepts used
. range(s) - ordered "list" of elements of type s, given by pointers to first and last elements
. comparison(u) - boolean-valued function on type u
. subtyping - s and t mush be subtypes of u
. How merge appears in STL
. Ranges represented by iterators
. iterator is generalization of pointer
. supports ++ (move to next element)
. Comparison operator is object of class Compare
. Polymorphism expressed using template
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator1 last2,
OutputIterator result, Compare comp)
. Comparing STL with other libraries
. C : qsort((void*)v, N, sizeof(v[0]), compare_int);
. C++, using raw C arrays
int v[N]
sort(v, V+N);
. C++, using a vector class;
vector v(N);
sort(v.begin(), v.end());
. Efficiency of STL
. C나 C++ raw arrys qhek dhglfu Qkfmek.
. Main point
. Generic abstractions can be convenient and efficient
. But watch out for code size if using C++ templates
