Transcript Be Abstract

NCCUCS 軟工概論
程式（軟體）設計單元，I
Abstract Data Types (ADT)
Prof. Chen, Kung
April 14, 2014
1
補充：Types of Testings
2
Types of Testing
• Unit testing
– An individual class or function is tested thoroughly
– Done as part of coding process
– Done by the programmer him/herself
– Usually by a test harness (or driver) or using a test-class
• Integration (System) testing
– Multiple parts of a system are combined and tested to
see if they work together
• Acceptance testing
– The customer is involved. (Alpha or beta testing)
•Performance test/Load test/Stress test/Security test/Usability te
(3)
Testing Activities
Subsystem
Code
Subsystem
Code
Unit
Test
Unit
Test
Tested
Subsystem
Tested
Subsystem
Requirements
Analysis
Document
System
Design
Document
Integration
Test
Integrated
Subsystems
Tested Subsystem
Subsystem
Code
Unit
Test
System
Test
User
Manual
Functioning
System
+ Regression Test
All tests by developer
(4)
Testing Activities continued
Global
Requirements
Validated
Functioning
System PerformanceSystem
Test
Client’s
Understanding
of Requirements
Accepted
System
Acceptance
Test
Tests by client
Tests by developer
Usability Test,
Platform Test,
Localization Test,
Security Test,
…
User
Environment
Installation
Test
Usable
System
User’s understanding
Tests (?) by user
System in
Use
(5)
Agenda
•
•
•
•
•
•
前言
Fundamental SW Design Principles
Modularity and Modules
Abstract Data Types (ADT)
Class Design (ADT)
Java Review
6
Great Handbooks for Programmers
http://www.cc2e.com/
7
Software development is not
hard, as long as you don’t
have to change code.
8
Legacy Code and
Software Maintenance
• Changing code is the daily work of
software developers.
• So,
Design Goals:
Easy to Read, Easy to Change.
9
Aspects of Code Quality
• Micro view: Coding Styles/Conventions
– 命名原則
– 程式碼排版
– 註解的使用
–…
• Macro view: Program Structure
– 分解與組裝
Software Design
11
Design Occurs at Multiple Levels
Standard Levels of Design
Basic Software Design Principles
• Modularity
– Interface and Implementation
•
•
•
•
Abstraction
Information Hiding
Coupling and Cohesion
…
13
Tackling Design Complexity
Modularization (模組化):
Decomposing a System into modules
Learning from Hardware
14
Tackling Design Complexity
• How: Divide-and-Conquer
• Division unit: modules, being modular
(modularity)
Modularity is one of the important principle of design.
Non-Modular (Monolithic)
Modular
Advantages of
Modularity
16
Tackling Design Complexity
• How: Divide-and-Conquer
• But how to divide? What modules?
疱丁解牛?
17
To divide a system into
meaningful parts (modules)
• A decomposed cow
Body
Head
Front
Leg
18
What is a module?
How to decompose?
Read
Leg
Two Aspects of a Module:
Interface and Implementation
• Interface vs. Implementation
Interface and implementation
Standard interface
Rest of the
System
USB
Interface
Implementation
20
MP3
Digital
Camera
Mobile
Phone
Interface and Implementation
• Interface is an abstraction and a specification,
describing how parts should be joined
• Implementation is the real stuff (the machinery)
• Interface is MORE IMPORTANT than
implementation
– Why?
– Interface, once decided, is hard to change
• e.g. the size of the thread of screws
– Implementation can be easily changed, e.g. the screw
21
The most important principle in (software)
engineering
Separation
of
Interface
and
Implementation
22
Interface – so that parts can be changed
independently
Body
Head
Front
Leg
23
Read
Leg
Interface
To replace a head
As long as the interface is not modified.
New
Head
Body
Easy to change!
Front
Leg
24
Read
Leg
Interface
Key to Interface: Abstraction
• The principles of ignoring those aspects of a
subject that are not relevant to the current
purpose in order to concentrate more fully on
those that are. (去蕪存菁)
Abstraction is a fundamental technique for managing complexity.
interface
Implementation
25
Levels of Abstraction抽象階梯
找(共同)特徵，抓重點：分類
Another Example of Abstraction:
生物的分類 (vs. OO)
• 老虎與貓同屬 貓科
界：動物界
門：脊索動物門
綱：哺乳綱
目：靈長目
科：人科
屬：人屬
種：人種
Abstractions in Programming
• Everywhere
– We’ll talk about this next time
• An example: function/procedure abstraction
• Do you know how “printf”in C
work?
•To use “printf”, you only need to know
•Its name
•Its parameters Interface specification
•Its effects
28
Abstraction in Programming:
Parameterization
• Value parameterization:
– From 1,2,3,… to n
int sum(n) { // return the sum from 1 to n }
• Function parameterization
– Sort an array of integers
– Sort an array of persons
– Sort an array of cars
–…
Sort(int a[], comparisonFunction)
29
Modules in Programming Languages
Modules in general
Versus
Modules in a PL
30
Modules in PL’s
• Functions in C
– printf example
• .h file: interface
• .c file: implementation
• Classes in Java
– Interface: ?
– Implementation:?
• Packages in Java, Namespace in C++
• Modules in Ruby
• …
31
Functions as Module Units
• Maybe too fine-grained
• 以Stack資料結構為例
– 可用靜態或動態方式配置Stack data container
• arrays or linked lists
– Data container的實作方式決定Stack operations
的做法
• push, pop, …
The Stack Example, 1/3
• The data for a stack is shared
by its operations (functions).
Data (for a Stack)
OP_1
OP_2
…
Data Implementation:
an array or a linked list
OP_n
The Stack Example, 2/3
• Claim: Data changes more frequently than logic.
• Change from an array to a linked list
牽一髮而動全身
Data (for a Stack)
change
OP_1
OP_2
change
…
OP_n
change
change
The Stack Example, 3/3
•
•
Modularize the stack:
Information Hiding and Encapsulation
Interface vs. Implementation
Public
Interface
Private Implementation
int top;
int buffer[100];
User
PUSH
POP
TOP
EMPTY
Designer
Void initStack();
Push(int number)
{ …buffer[]… }
int Pop()
{ …buffer[]… }
PUSH
5
10
15
20
20 15
5
TOP
20
10
15
5
10
5
Two
Impl.
Stack as a Type
• A stack module
– Like a stack object
– A data container with LIFO data access
• A stack type
– Like a stack class (interface)
– Abstraction of LIFO data containers
Design Principle: Be Abstract
• Flexible and reusable code
void p( int s[], top)
{
…
}
versus
void p(Stack aStack) //type
{
…
s[top++] = exp;
aStack.push(exp);
…
…
}
•對input parameters假設愈少，重用度愈高
Data Abstraction
Abstract Data Types (ADT)
38
Procedural and data abstractions
Procedural abstraction:
– Abstract from details of procedures (e.g., methods)
– Specification is the abstraction
• Abstraction is the specification
– Satisfy the specification with an implementation
Data abstraction:
– Abstract from details of data representation
– Also a specification mechanism
• A way of thinking about programs and design
– Standard terminology: Abstract Data Type, or ADT
CSE331 Winter 2014
39
Why we need Data Abstractions (ADTs)
Organizing and manipulating data is pervasive
– Inventing and describing algorithms is less common
Start your design by designing data structures
– How will relevant data be organized
– What operations will be permitted on the data by clients
Potential problems with choosing a data abstraction:
– Decisions about data structures often made too early
– Duplication of effort in creating derived data
– Very hard to change key data structures (modularity!)
CSE331 Winter 2014
40
An ADT is a set of operations
• ADT abstracts from the organization to meaning of data
• ADT abstracts from structure to use
• Representation should not matter to the client
– So hide it from the client
class RightTriangle {
float base, altitude;
}
class RightTriangle {
float base, hypot, angle;
}
Instead, think of a type as a set of operations
create, getBase, getAltitude, getBottomAngle, …
Force clients to use operations to access data
CSE331 Winter 2014
41
Are these classes the same?
class Point {
public float x;
public float y;
}
class Point {
public float r;
public float theta;
}
Different: cannot replace one with the other in a program
Same: both classes implement the concept “2-d point”
Goal of ADT methodology is to express the sameness:
– Clients depend only on the concept “2-d point”
CSE331 Winter 2014
42
Benefits of ADTs
If clients “respect” or “are forced to respect” data
abstractions…
– For example, “it’s a 2-D point with these operations…”
• Can delay decisions on how ADT is implemented
• Can fix bugs by changing how ADT is implemented
• Can change algorithms
– For performance
– In general or in specialized situations
• …
We talk about an “abstraction barrier”
– A good thing to have and not cross (also known as
violate)
CSE331 Winter 2014
43
Abstract data type = objects + operations
rest of
program
Point
x
y
r
theta
translate
scale_rot
clients
abstraction
barrier
implementation
• Implementation is hidden
• The only operations on objects of the type are those
provided by the abstraction
CSE331 Winter 2014
44
Concept of 2-d point, as an ADT
class Point {
// A 2-d point exists in the plane, ...
public float x();
public float y();
Observers
public float r();
public float theta();
// ... can be created, ...
public Point(); // new point at (0,0)
public Point centroid(Set<Point> points);
Creators/
Producers
// ... can be moved, ...
public void translate(float delta_x,
float delta_y);
Mutators
public void scaleAndRotate(float delta_r,
float delta_theta);
}
45
CSE331 Winter 2014
CSE331 Winter 2014
Specifying a data abstraction
• A collection of procedural abstractions
– Not a collection of procedures
• An abstract state
– Not the (concrete) representation in terms of fields,
objects, …
– “Does not exist” but used to specify the operations
– Concrete state, not part of the specification,
implements the abstract state
• More later
• Each operation described in terms of “creating”,
“observing”, “producing”, or “mutating”
– No operations other than those in the specification
46
Specifying an ADT
Immutable
Mutable
1.
2.
3.
4.
5.
6.
1.
2.
3.
4.
5.
6.
•
•
•
•
overview
abstract state
creators
observers
producers
mutators
overview
abstract state
creators
observers
producers (rare)
mutators
Creators: return new ADT values (e.g., Java constructors)
Producers: ADT operations that return new values
Mutators: Modify a value of an ADT
Observers: Return information about an ADT
CSE331 Winter 2014
47
Two Example Specifications
1. Polynominals (c0
•
+ c1x + c2x2 + …)
immutable
2. Int Sets
•
mutable
48
Poly, an immutable datatype: overview
/**
* A Poly is an immutable polynomial with
* integer coefficients. A typical Poly is
*
c0 + c1x + c2x2 + ...
**/
class Poly {
Abstract state (specification fields)
Overview:
– State whether mutable or immutable
– Define an abstract model for use in operation specifications
• Difficult and vital!
• Appeal to math if appropriate
• Give an example (reuse it in operation definitions)
– State in specifications is abstract, not concrete
49
CSE331 Winter 2014
Poly: creators
// effects: makes a new Poly = 0
public Poly()
// effects: makes a new Poly = cxn
// throws: NegExponent if n < 0
public Poly(int c, int n)
Creators
– New object, not part of pre-state: in effects, not modifies
– Overloading: distinguish procedures of same name by
parameters (Example: two Poly constructors)
Footnote: slides omit full JavaDoc comments to save space; style might
not be perfect either – focus on main ideas
50
CSE331 Winter 2014
Poly: observers
// returns: the degree of this,
//
i.e., the largest exponent with a
//
non-zero coefficient.
//
Returns 0 if this = 0.
public int degree()
// returns: the coefficient of the term
//
of this whose exponent is d
// throws: NegExponent if d < 0
public int coeff(int d)
CSE331 Winter 2014
51
Notes on observers
Observers
– Used to obtain information about objects of the type
– Return values of other types
– Never modify the abstract value
– Specification uses the abstraction from the overview
this
– The particular Poly object being accessed
– Target of the invocation
– Also known as the receiver
Poly x = new Poly(4, 3);
int c = x.coeff(3);
System.out.println(c);
// prints 4
52
CSE331 Winter 2014
Poly: producers
// returns: this + q (as a Poly)
public Poly add(Poly q)
// returns: the Poly equal to this * q
public Poly mul(Poly q)
// returns: -this
public Poly negate()
CSE331 Winter 2014
53
Notes on producers
• Operations on a type that create other objects of the
type
• Common in immutable types like java.lang.String
– String substring(int offset, int len)
• No side effects
– Cannot change the abstract value of existing objects
CSE331 Winter 2014
54
IntSet, a mutable datatype:
overview and creator
// Overview:
// unbounded
// IntSet is
class IntSet
An IntSet is a mutable,
set of integers. A typical
{ x1, ..., xn }.
{
// effects: makes a new IntSet = {}
public IntSet()
CSE331 Winter 2014
55
IntSet: observers
// returns: true if and only if x  this
public boolean contains(int x)
// returns: the cardinality of this
public int size()
// returns: some element of this
// throws: EmptyException when size()==0
public int choose()
CSE331 Winter 2014
56
IntSet: mutators
// modifies: this
// effects: thispost = thispre  {x}
public void add(int x)
// modifies: this
// effects: thispost = thispre - {x}
public void remove(int x)
CSE331 Winter 2014
57
Notes on mutators
• Operations that modify an element of the type
• Rarely modify anything (available to clients) other than
this
– List this in modifies clause (if appropriate)
• Typically have no return value
– “Do one thing and do it well”
– (Sometimes return “old” value that was replaced)
• Mutable ADTs may have producers too, but that is less
common
CSE331 Winter 2014
58
Implementing an ADT
To implement a data abstraction in Java:
– with a Java class
• The Date class in assignment 1
– With a Java interface and multiple classes
• The Stack ADT
59
Assignment 2:
the Graph ADT
details next
week
60
A Quick Review of Inheritance/OOP
in Java
快速複習
61
Classes: Object
Classification/Generation
A Class as a template (type)
•Color
•Gas
•State …
•Start
•Stop
•Left-turn
•Right-turn …
Class:
John’s car object
Mary’s car object
一個類別描述一群有相似結構與行為的物件。
類別可視為物件的型別(Type)。
實務上, 類別是物件模版 (template), 用以製造物件。
OOP
• Classes implement ADT
• A simplified view:
–OOP = ADT + Inheritance
Inheritance
Class Inheritance
•
This class (B) is like that class (A)
except for these differences …
–
Extend superclass by adding new
variables/operations
–
Specialize superclass behavior by
overriding methods
•
•
A
B
Totally replace a superclass operation
Add pre/post processing before/after
superclass operation
65
Inheritance Example, 1/2
public class Ball {
private Position position;
private double vx, vy; // speed per unit time
private double radius;
public Ball(Position pos, double vx, double vy) {
position = pos;
this.vx = vx;
this.vy = vy;
}
// moves the ball specified number of time units
public void move(int t) {
double newx = position.getX() + vx * t;
double newy= position.getY() + vy * t;
position.setX(newX);
position.setY(newY);
}
Inheritance Example, 2/2
Suppose we need a new Ball class
that shrinks a certain amount every time unit.
ShrinkingBall:
Public class ShrinkingBall extends Ball {
private double shrinkRate; // new property
public void move(int tu) { // method overriding
super.move(tu); // Ball’s move
radius -= tu * shrinkRate;
}
…
}
Why Using Inheritance?
• Avoid duplicate code
– Factor out common code
• Support evolution of code (class changes)
– 替換原則(代父出征)
– Polymorphism and Code reuse
• Declared type versus actual types
• Code reuse: existing code invokes new code
indirectly
Duplicate Code
Code Reuse via Inheritance
Vehicle
…
void speedUp(int)
Bike
Car
Why Using Inheritance?
• Avoid duplicate code
– Factor out common code
• Support evolution of code (class changes)
– 替換原則(代父出征)
– Polymorphism and Code reuse
• Declared type versus actual types
• Code reuse: existing code invokes new code
indirectly
Code Evolution (Modularity)
既有common code 也可有specific code via method overriding
common
code
speedUp(int)
Class Hierarchy
speedUp(int)
Method overriding
Class Inheritance
•
Inheritance establishes a subtyping
relationship with between subclass
and superclass, thus enabling
polymorphism
A
– Subclass instances may be used
anywhere superclass instances
are expected
B
•
替換原則（代父出征）
– Polymorphism = Subtyping +
Dynamic method binding
73
Types and Subtypes
• Type int is a subtype of type float
– float f = 3;
• In languages such as C# and Java,
– A class is a type.
– Subclasses are subtypes of their
super-classes.
–B≤A
– 代父出征：
• A a = new B();
A
B
Inheritance and
Principle of Substitutability
Subtyping
• 代父出征--An object
of a subclass can
always be used in any
context in which an
object of its
superclass was
expected.
//declared type
Vehicle v;
//actual type different
v = new Car();
v.speedUp(10);
v = new Bike();
v.speedUp(5);
Inheritance and Polymorphism
Example: 生物的分類
界：動物界
門：脊索動物門
綱：哺乳綱
目：靈長目
科：人科
屬：人屬
種：人種
凡動物都會move.
狗(貓)是動物，
所以狗(貓)會 move
void moveTwice(Animal anAnimal)
{
anAnimal.move()
anAnimal.move()
} // which move executed?
moveTwice(aDog);
Dynamic Method Binding moveTwice(aCat);
Java Interfaces
• Note that the word “interface”
– Is a specific term for a language construct
– Is not the general word for “communication
boundary”
– Is also a term used in UML (but not in C++)
Defining an Interface
• Java code:
interface Queue {
void add (Object obj);
Object remove();
int size();
}
• Nothing about implementation here!
– Public methods and no fields
– Only static final fields (constants) allowed
Implementing an Interface
class
ArrayList
implements Queue {
void add (Object obj) {
…
}
Object remove() {
…
}
int size() {
…
}
…
}
Using Objects by Interface
• Say we had two implementations of
Queue:
Queue q1 = new CircularArrayQueue(100);
or
Queue q1 = new LinkedListQueue();
q1.add( new Widget() );
Queue q3 = new …
Queue q2 = mergeQueue(q2, q3);
Two Types of Inheritance in Java
• How can inheritance support reuse?
• Implementation Inheritance
– A subclass reuses some implementation from
an ancestor
– In Java, keyword extends
• Interface Inheritance
– A “subclass” shares the interface with an
“ancestor”
– In Java, keyword implements
– I.e. this class will support this set of methods
Programming to an Interface
• Interfaces as Types
– List l = new ArrayList();
• Parameters of interface types
int sumOfAmount( Collection c) {
// compute the total amount of elements
// in the collection
…
}
Interfaces in Other Languages
• A modeling method in UML
• Interfaces in C++: Abstract Base Class
(ABC)
– All methods are pure virtual (=0)
– No data members
– Use multiple inheritance
Interfaces and Abstract Classes
• Abstract classes:
– Cannot create any instances
• Prefer Java interfaces over abstract classes!
– Existing classes can add an interface
– Better support for mix-in classes
• E.g. Comparable interface -- supports compare()
– Do not need a hierarchical framework
– Composition preferred over inheritance
• E.g. wrapper classes
• But, abstract classes have some implementation
– Skeletal implementation classes, e.g. AbstractCollection
• Disadvantage: once released, a public interface
shouldn’t be updated
•Talk about this later.
An example abstract class
• public abstract class Animal {
…
String getName() { return name; }
abstract int eat();
abstract void breathe();
}
• This class cannot be instantiated
• Any non-abstract subclass of Animal must
provide the eat() and breathe() methods
Interfaces can have Multiple
Inheritance
• Classes support single inheritance only
• Interfaces
– Inheritance and Multiple inheritance
Class vs. Interface Hierarchy
Class Hierarchy
Animals
interface Winged
void fly( );
…
Vertebrates
Mammals
Insects
Birds
Dragonflies
Bats
from Head/Lander, 1997
87
Choosing Between
Inheritance and Composition
Relationships Between Classes
• Inter-class relationships
Animal
• Is-A, Is-Kind-A
– Inheritance
DogClass
• Has-A, Part-Of
– Composition
Car
Wheel
Has-A: Composition
• B has an instance(s) of A
as part of its state (fields)
•
public class B {
private A b;
}
• public class B {
private A [] bs;
}
90
B
A
In UML, there are two kinds:
• Aggregation
• Composition
Code reuse via Delegation (Forwarding)
Delegation of client calls to B.m(int) to A.m(int)
A
m(a: int)
B
Client
call
m(a: int)
class A {
…
int m(int a) { … }
}
class B {
private A delegate;
...
public int m(int a) {
return delegate.m(a);
}
}
Choosing between
Composition and Inheritance
• What type of relationship is being modeled?
–
–
–
–
B “has-a” A => composition
B “uses-a” A => composition
B “is-a” A => inheritance (usually)
Don’t make B a subclass of A unless every instance
of B “is-a” A
• Note: Often we have composition and inheritance together (see later
slides for examples)
92
Back to the Stack ADT example
How to implement it?
93
Abstract Data Types (Classes) in Java
• Define a Java class (Abstract Data Type) for
Stack
public class Stack {
Private data
Enforce abstraction
private int top;
private int [] buffer;
private int max_size = 1000;
public void initStack(int size) { … }
public void push(int e) {… }
public int pop() { …}
…
}
Stack s1 = new Stack(); • Class is an implementation of an
Stack s2 = new Stack();
Abstract Data Type.
s1.initStack(100);
s2.initStack(200);
s1.push(10); s1.push(50);
s2.push(s1.pop());
Stack class in JDK Java.util.Stack<E>
(Bad Example of Inheritance)
A stack is NOT a Vector.
95
Alternative Implementations
• Use composition
– Define a Stack class
– A stack has a vector object
• Left as an exercise
• Use Composition and Interface
– Stack as an interface
– Define various stack classes that implement
the Stack interface
96
2. Stack as an Interface in Java
Java Programming Review:
Interfaces vs. Classes
(Like Abstract Base Classes (ABC) in C++)
http://cs.lmu.edu/~ray/notes/stacks/
Source:
http://cs.lmu.edu/~ray/notes/stacks/
97
Stack:
Spec. and Implementation
98
Different Implementations
(Representations) of Stack
99
SimpleStack: The Trivial Wrapper
Implementation
100
Different Implementations of Stack
UML Diagram
Implements
101
Favor Composition Over Inheritance
In terms of code reuse
From “Design Patterns” book