Software Construction Assignment: Assignment 2 (Worth 200 Points)
farzadbigz
AbstractDataTypes.pptxNDSU CSCI 717 Software Construction
Abstract Data Types
References
Bertrand Meyer. Object-Oriented Software Construction, 2nd Edition, Prentice-Hall PTR, 1997. Chapter 6.
Steve McConnell. Code Complete: A Practical Handbook of Software Construction. 2nd Edition. Microsoft Press, 2004. Chapter 6
2
Outline
3
The Need for ADTs: An Example
Writing a program to control text output to the screen using a variety of typefaces, point sizes, and font attributes (e.g. bold and italic)
Consider an ad hoc approach to manipulating fonts (suppose pixel is the unit of size)
Change to a 12-point (16 pixel) font size
Set a font to bold
4
Change to a 12-Point Font Size
currentFont.size = 16; // pixels or
currentFont.size = PointsToPixels(12), or
currentFont.sizeInPixels = PointsToPixels(12)
You cannot have both currentFonts.sizeInPixels and currentFont.sizeInPoints,
Otherwise, current.Font won’t have any way to know which of the two it should use.
If you change sizes in several places, you will have similar lines spread throughout your program.
5
Set a Font to Bold
currentFont.attribute = currentFont.attribute || 0x02; or
currentFont.attribute = currentFont.attribute || BOLD; or
current.bold = TRUE;
Similar limitation: the client code is required to control the data members directly, which limits how currentFont can be used
Likely have similar lines in many places.
6
Using an ADT for Font Manipulation
currentFont.setSizeInPoints(sizeInPoints)
currentFont.setSizeInPixels(sizeInPixels)
currentFont.setBoldOn()
currentFont.setBoldOff()
currentFont.setItalicOn()
currentFont.setItalicOff()
currentFont.setFaceType()
…
7
Benefits of the ADT
Hide implementation details
Unless using an ADT, changing the font data type from the first representation of bold to the second would entail changing the program in every place in which bold is set.
Hiding information also protects the rest of the program if you decide to store data in external storage rather than in memory or rewrite all the font-manipulation routines in another language
Changes don’t affect the whole program
If fonts need to become richer and support more operations (e.g. superscripts), it won’t affect the rest of the program.
8
Benefits of the ADT - cont
Make the interface more informative
Code like currentFont.size =16 is ambiguous
Collecting all similar operations into an ADT can define an interface in terms of points or pixels, or clearly differentiate between the two
The program is more obviously correct
currentFont.setBoldOn() is a task easier than
currentFont.attribute = currentFont.attribute || BOLD
The program becomes more self-documenting
currentFont.setBoldOn() is more meaningful
9
Benefits of the ADT - cont
Don’t have to pass data all over your program
The ad hoc approach has to change currentFont directly or pass it to every routine that works with fonts
Able to work with real-world entities rather than with low-level implementation structures
Can define operations dealing with fonts so that most of the program operates solely in terms of fonts rather than array accesses, structure definitions, and True and False.
10
The Need
Need to specify essential properties of objects
It is bad to use a particular representation as specification.
Relying on the physical representation of data structures to guide analysis and design would unlikely yield flexible software.
Specification Criteria
Precise, non-ambiguous
Complete - or at least as complete as we want
Non - over-specifying
Over-specifying: too much information for the clients, e.g., details of representation
11
Completeness: have specified the required behaviour and output for all possible inputs in all possible states under all constraints?
11
What Is an ADT?
ADT
A collection of data and operations on that data
It is a mathematical specification
Describes the properties and behavior of instances of it’s type
Doesn’t describe implementation details (therefore it’s abstract).
Example: STACK
12
STACK – Many implementations
Stack – One data type – many implementations
13
ADTs as class foundations
Understanding ADTs is essential to understanding object-oriented programming
Use ADTs to manipulate real-world entities rather than low-level, implementation entities
Create classes that are easier to implement initially and to modify over time
14
Formalizing ADT Specification
Types
Functions
Axioms
Preconditions
15
Types
A type is a collection of objects characterized by functions, axioms and preconditions.
STACK: set of all possible stacks
Generic ADT: type pattern
STACK [G]: stacks of objects of an arbitrary type G
G: formal generic parameter
Generically derived ADT
STACK [ACCOUNT]
ACCOUNT: actual generic parameter
STACK[STACK [ACCOUNT]]
16
Functions
Functions: operations applicable to instances
Example: STACK
LIFO – Last In and First Out
put yields a new stack with one extra element pushed on top.
remove yields a new stack with the top element, if any, popped;
item yields the value of top element, if any.
empty indicates whether a stack is empty; its result is a boolean value
new yields an empty stack
17
17
Stack is a kind of container!
Function Categories
Creator function - constructor
Creates a new instance of the type
The type being defined appears only to the right of the arrow
new
Query function - accessor
Functions that have a return value and do not change the instance
The type being defined appears only on the left of the arrow
item, empty
Command function – modifier/mutator
Functions without return value that change the instance
Appears on both sides of the arrow
put, remove
18
STACK Functions
19
Axioms
Axioms specify properties that are always true for every possible values
For any x:G, s:STACK [G],
A1 • item (put (s, x)) = x
A2 • remove (put (s, x)) = s
A3 • empty (new) = true
A4 • not empty (put (s, x)) = true
A1 and A2: LIFO property of stacks.
A3 and A4: when a stack is empty / not empty
A stack resulting from new is empty;
Any stack resulting from pushing an element on an existing stack is non-empty.
20
Preconditions
Partial functions: an inescapable fact + a potential source of errors
Given f(e), does it make sense?
f (x: T) require <precondition>
require indicates what conditions f’s arguments must satisfy to belong to f’s domain.
X: dummy name of arguments of type T, can be used in condition
Preconditions
remove (s: STACK [G]) require not empty (s)
item (s: STACK [G]) require not empty (s)
21
Well formed and Correct Terms
Well-formed: all functions get a right number of arguments of right types
Correct: preconditions of all functions are satisfied.
empty (item (put (new, 3))) ill-formed
item (put (new, 3)) 3
item (remove (put (new, 3))) incorrect
empty (remove (put (new, 7))) True
item (put (put (remove (put (new, 4), 3), 3)) 2
22
Complete Spec of Stack ADT
23
Functions/Axioms and Programs
Functions defined in an ADT spec allow to construct possibly complex expressions;
A complex stack expression is the mathematical equivalent of a program
stackexp = item (remove (put (remove (put (put (remove (put (put (put (new, x1), x2), x3)), item (remove (put (put (new, x4), x5)))), x6)), x7)))
Axioms allow to simplify complex expressions to yield a simpler result.
The simplification process is the mathematical equivalent of a computation of executing a program.
24
Stackexp
It is easier to understand Stackexp if we define it in terms of a sequence of auxiliary expressions as below:
s1 = new
s2 = put (put (put (s1, x1), x2), x3)
s3 = remove (s2)
s4 = new
s5 = put (put (s4, x4), x5)
s6 = remove (s5)
y1 = item (s6)
s7 = put (s3, y1)
s8 = put (s7, x6)
s9 = remove (s8)
s10 = put (s9, x7)
s11 = remove (s10)
stackexp = item (s11)
25
Simplification of Stackexp
Applying A2 to simplify s3, remove (put (put (put (s1, x1), x2), x3)), yields put (put (s1, x1), x2)).
Applying A2: s6 is put (s4, x4);
Use A1 to deduce y1, item (put (s4, x4)) is x4,
ADTs provide a purely mathematical model for the notion of program and program execution.
26
From ADTs to Classes
OO construction
Build a collection of interacting ADTs, partially or totally implemented.
At the level of analysis, design or implementation
A class is an ADT equipped with a possibly partial implementation.
Effective class: fully implemented class
Deferred class: class implemented only partially, or not at all
Inheritance?
Covariance and contravariance
http://en.wikipedia.org/wiki/Parameter_covariance
27
Producing an Effective Class: Elements
E1: an ADT specification
E2: a choice of representation.
E3: a mapping from the functions (E1) to the representation (E2)
A set of mechanisms or features
Each mechanism implements one of the functions in terms of the representation
The mechanisms satisfy the axioms and preconds.
28
Stack Implementation
Representation: ARRAY_UP
implement any stack by <array, count>
29
Stack Implementation - cont
Function implementation
put (x: G) is
-- Push x onto stack.
-- No check for possible stack overflow.
do
count := count + 1
array [count] := x
end
30
Role of Deferred Classes
A class is deferred if any of E2 and E3 is missing
Deferred classes are particularly useful for analysis and design
In analysis, no implementation details are needed or desired
In design, many aspects of implementation will be left out
Deferred classes serve to classify groups of related types of objects – abstract classes
Provide some of the most important high-level reusable modules
Capture common behaviors among a set of variants
31
A More Imperative View
Spec of ADTs is applicative or change-free
All features are modeled as mathematical functions
put: STACK [G] STACK [G] returns a new stack, rather than changes an existing stack.
Classes abandon the applicative-only view and reintroduce commands as operations that may change objects.
put takes an argument of type G, and modifies a stack by pushing a new element on top
It may require the corresponding change in the axioms A1 and A4 of the stacks.
32
A More Imperative View - cont
A1 item (put (s, x)) = x A4 not empty (put (s, x))
yield a clause known as a postcondition
put (x: G) is
-- Push x on top of stack
require
The precondition, if any
do
The appropriate implementation, if known
ensure
item = x
not empty
end
33
ADTs and Information Hiding
34
34
How do we select the public and private features of a module — the visible and invisible parts of the iceberg?
How do we select the public and private features of a module — the visible and invisible parts of the iceberg?
If the module is a class coming from an ADT, the answer is clear:
Of the 3 parts involved in the transitions, E1 is public; E2 and E3, the choice of representation and implementation of the ADT functions in terms of this representation should be secret
35
More ADTs Examples
Cruise Control
Set speed,
Get current settings,
Resume former speed
Deactivate
Fuel Tank
Fill tank,
Drain tank
Get tank capacity
Get tank status
36
36
Cruise control: set speed, get current settings, resume former speed, deactivate
Fuel tank: fill tank, drain tank, get tank capacity, get tank status
Menu: start new menu, delete, add item, remove item, deactivate item, hide menu, get menu choice
File: open, read, write, set current file location, close file
Elevator: move up/down one floor, move to specific floor, report current floor, return to home floor
More ADTs Examples - cont
Elevator
Move up/down one floor
Move to specific floor
Report current floor
Return to home floor
File
Open file, close file
Read file, write file
Set current file location
Menu
37
argument
no
ith
function w
:
STACK[G]
:
new
members
all
to
applicable
not
:
function
partial
:
domain
the
of
members
all
to
applicable
:
function
total
:
(Create)
STACK[G]
or
STACK[G]
:
new
(Query)
BOOLEAN
[G]
STACK
:
empty
)
(
[G]
STACK
:
item
(Command)
STACK[G]
[G]
STACK
:
remove
(Command)
STACK[G]
G
[G]
STACK
:
put
®
®
®
®
®
´
a
a
a
Query
G
(s)empty not require [G])STACK :(s item
(s)empty not require [G])STACK :(s remove
ONSPRECONDITI
x))(s,(put empty not A4 (new)empty A3
s x))(s,(put remove A2 x x))(s,(put item A1
[G]STACK :s G, :any xFor :AXIOMS
STACK[G]or STACK[G] :new
BOOLEAN [G]STACK :empty
[G]STACK :item
STACK[G][G]STACK :remove
STACK[G]G [G]STACK :put
FUNCTIONS
[G]STACK :TYPES
G
