Specification
Ch. 5
1
Outline
• Discussion of the term "specification"
• Types of specifications
– operational
•
•
•
•
Data Flow Diagrams
(Some) UML diagrams
Finite State Machines
Petri Nets
– descriptive
• Entity Relationship Diagrams
• Logic-based notations
• Algebraic notations
• Languages for modular specifications
– Statecharts
–Z
Ch. 5
2
Specification
• A broad term that means definition that emphasizes on
What to do versus How to do it
– In traditional engineering it has precise meaning (i.e., the specific
parameters of the product). In SE this is not the case.
• Used at different stages of software development for
different purposes
• Generally, specification is a statement of agreement
(contract) between producer and consumer of a service:
– implementer and user: requirement spec, non-technical, e.g.,
plain English
– Architect and developer: design spec, technical, e.g., UML
diagrams
• All desirable qualities must be specified
Ch. 5
3
Uses of specification
• Statement of user requirements
– major failures occur because of misunderstandings
between the producer and the user
• Lack of knowledge of computer
– In most cases the owner does not exactly know
what he/she wants to be developed
– "The hardest single part of building a software
system is deciding precisely what to build"
(Frederick Brooks)
Ch. 5
4
Uses of specification (cont.)
• Statement of the interface between the
machine and the controlled environment
– serious undesirable effects can result due to
misunderstandings between software engineers
and domain experts about the phenomena
affecting the control function to be implemented
by software:
• Receiving input signals from sensors and generating
output signals to control the embedded system.
Ch. 5
5
Uses of specification (cont.)
• Statement of requirements for
implementation
– Software Development process is a chain of:
Specification–Implementation–Verification steps
• Requirements specification refers to definition of external
behavior
– design specification must be verified against it
• Design specification refers to definition of the software
architecture
– code must be verified against it
Ch. 5
6
Uses of specification (cont.)
• A reference point during maintenance
– Corrective maintenance only changes
implementation
– Adaptive and Perfective maintenance occur
because of requirements changes
• requirements specification must change
accordingly
Ch. 5
7
Specification qualities
• Precise, clear, unambiguous
• Consistent
• Complete
– internal completeness
– external completeness
• Incremental
Ch. 5
8
Clear, unambiguous,
understandable
• Example: specification fragment of a wordprocessor for “selection” operation.
Selecting is the process of designating
areas of the document that you want to
work on. Most editing and formatting
actions require two steps: first you
select what you want to work on,
such as text or graphics; then you
initiate the appropriate action.
can an area be scattered?
Ch. 5
9
Precise, unambiguous, clear
• Another example (from a real safetycritical system)
The message must be triplicated.
copies must be forwarded through
different physical channels. The
accepts the message on the basis
two-out-of-three voting policy.
The three
three
receiver
of a
can a message be accepted as soon as we receive 2 out of 3
identical copies of message or do we need to wait for
receipt of the 3rd?
Ch. 5
10
Consistent
• Example: specification fragment for a
word-processor
The whole text should be kept in lines
of equal length. The length is specified
by the user. Unless the user gives an
explicit hyphenation command,
a carriage return should occur only
at the end of a word.
What if the length of a word exceeds the length of the line?
Ch. 5
11
Complete
• Internal completeness
– The specification must define any new
concept or terminology that it uses
• glossary of terms is helpful for this purpose
• External completeness
– The specification must document all the
needed requirements
• difficulty: when should one stop?
Ch. 5
12
Incremental
• Referring to the specification process
– start from a sketchy document and
progressively add details
• Referring to the specification document
– document is structured and can be
understood and extended in increments
Ch. 5
13
Classification of
specification styles
• Informal (plain English), semi-formal (DFD,
UML diagrams), formal (languages: Z, Larch,
B-method, Petri-nets, SDL, VHDL, LOTOS)
• Operational
– Behavior specification in terms of some abstract
machine
• Descriptive
– Behavior described in terms of properties and
input/output relation.
Ch. 5
14
Example 1
• Specification of a geometric figure E:
Ellipse can be drawn as follows:
1. Select two points P1 and P2 on a plane
2. Get a string of a certain length and fix its ends
to P1 and P2
3. Position a pencil as shown in next figure
4. Move the pen clockwise, keeping the string
tightly stretched, until you reach the point where
you started drawing
this is an operational specification
Ch. 5
15
P
1
P
2
Ch. 5
16
A descriptive specification
• Ellipse E is described by the following
equation:
ax2 + by2 + c = 0
where a, b, and c are suitable constants.
Given x as input, the resulting pairs in the
form of (x, y1) and (x,y2) would be two points
of the Ellipse in the x-y plane.
this is a descriptive specification
Ch. 5
17
Another example:
Sorting an array of elements
OP
“Let a be an array of n elements. The result of its sorting
is an array b of n elements such that the first element of
b is the minimum of a (if several elements of a have the
same value, any one of them is acceptable); the second
element of b is the minimum of the array of n-1
elements obtained from a by removing its minimum
element; and so on until all n elements of a have been
removed.”
“The result of sorting array a is an array b which is a
DES permutation of a and is sorted.”
Ch. 5
18
How to verify a
specification?
Testing specification against the ideal system:
• “Observe” dynamic behavior of the specified
system (simulation, prototyping).
• “Analyze” properties of the specified system
similar to the traditional engineering:
– physical model of a bridge
– mathematical model of a bridge
Ch. 5
19
Data Flow Diagrams (DFDs)
• A semi-formal operational specification
• System viewed as collection of “data” manipulated by
“functions”
• Data can be persistent
– they are stored in data repositories
• Data can flow
– they are represented by data flows
• DFDs have a graphical notation
Ch. 5
20
Graphical notation
– bubbles represent functions
– arcs represent data flows
– open boxes represent persistent store
– closed boxes represent I/O interaction
The function sym bol
The input device symbol
The data flow symbol
The output device symbol
The data store symbol
Ch. 5
21
Example
b
+
a d
c
*
specifies evaluation of
(a + b) * (c + a * d)
+
*
Ch. 5
22
A construction “method” (1)
1. Start from the “context” diagram
Inpu t 1
Inpu t
Ou tpu t
infor m ati on
2
Inpu t n
.. .
sy st em
Ou tpu t
2
.. .
Ou tpu t
Ch. 5
1
m
23
A construction “method” (2)
2. Proceed by refinements until you reach
“elementary” functions (preserve
balancing)
A
I
H
I
O
A3
J
A4
A1
A6
P
K
Q
M
A2
S
A5
N
A7
R
K
B2
K2
O
M
B1
K3
K1
T
Ag
B4
B3
N
K4
Ch. 5
24
A library example
Boo k
Boo k requ est
by th e u ser
Sh elv es
Title and au th or
of req uested b ook; name
of th e u ser
Auth or
Boo k
List o f A uthors
Get a bo ok
Boo k
reception
Title
Boo k title;
user n ame
List o f titles
List o f b oo ks bo rrowed
Title
Search by
topics
List o f top ics
Top ic
Top ic
List o f titles
referring to the to pic
Disp lay of
the list of titles
Top ic requ est
by th e u ser
Ch. 5
25
Refinement of
“Get a book”
Book
Shelves
Author
Get
the book
Book
List of Authors
<shelf#, book#>
Title
Find
book
position
Book
reception
List of books borrowed
List of titles
Title and author
of requested book;
name of the user
Book title;
user name
Book request
by the user
Ch. 5
26
Patient monitoring systems
The purpose is to monitor the patients’ vital factors--blood,
pressure, temperature, …--reading them at specified frequencies
from analog devices and storing readings in a DB. If readings fall
outside the range specified for patient or device fails, an alarm
must be sent to a nurse. The system also provides reports.
Nu rse
R e por t
R e ques t
P ati en t
C li nica l
Da ta
R e por t
P ati en t
Mon it ori ng
Nu rse
A larm
Recen t da ta
Da ta f or re por t
Ch. 5
P ersiste nt da ta
27
A refinement
P ati en t a rch ive
R e cen t
Da ta
R e por t
R e ques t
Da ta for
R e por t
Nu rse
Gene rate
R e por t
Upda te
arch ive
R e por t
F or ma tte d da ta
C e nt ral
Mon it ori ng
L imits
L imits f or pa ti en t
Nu rse
A lar m
P ati en t d a ta
L oca l
Mon it ori ng
Ch. 5
C li nica l
Da ta
P ati en t
28
More refinement
P re ssure
L imits
P re ssure , pu ls eÉ
P ati en t
da ta
T em per at ure decod e
Ch e ck
limi t
violati ons
P ulse
R e su lt
F or ma t
da ta
Da te
T ime
clock
produce
m essage
F or ma tte d da ta
alarm
Ch. 5
29
An evaluation of DFDs (1)
• Easy to read, but …
• Informal semantics
– How to define leaf functions?
– Inherent ambiguities
A
E
B
• Outputs from A, B, C are
all needed?
• Outputs for E and F are
produced at the same time?
D
F
C
Ch. 5
30
An evaluation of DFDs (2)
• Control information is absent
A
B
Possible interpretations:
(a) A produces datum, waits until B consumes it
(b) B can read the datum many times without
consuming it
(c) a pipe is inserted between A and B
Ch. 5
31
Formalization/extensions
• There have been attempts to formalize
DFDs
• There have been attempts to extend
DFDs (e.g., for real-time systems)
d1
Trigger
d2

.
.
.
dn
Ch. 5
32
UML diagrams
• UML (Unified Modeling Language) is a general purpose visual
modeling language that provides different types of diagrammatic
techniques and notations to specify, visualize, analyze, construct,
and document the artifacts of a software system.
• Software artifacts include: SRS, SDS, test cases, source code,
technical/user manual, software architecture, etc.
• UML diagrams are used to understand, design, browse, configure,
maintain, and control information about software system.
• UML is intended for use with all development methods, lifecycle
stages, application domains, and media.
• In this chapter, we cover use-case diagram, sequence diagram, and
collaborative diagram from UML.
Ch. 5
33
UML History
• UML was developed in an effort to unify and simplify the large
number of OO development methods that use popular OO
languages.
• Simula 67 was the first OO language
• Smalltalk was introduced in early 1980s followed by Objective C,
C++, Eiffle, CLOS, Java.
• First OO development method was Shlaer-88, then Yourdon 91,
and Booch 91
• Unification effort:
– UML 1995 by Booch, Rumbaugh, Jacobson
– OMG 1996 proposed a standard for OO modeling
• CORBA
Ch. 5
34
Modeing Software System
• What is model?
– A model captures the important aspects of the artifact being
modeled from a certain point of view, and simplifies or omits
the rest. Data, Function, Behavior, Process, Implementation…
• What are models for?
– To capture and precisely state requirements and domain
knowledge so that all stakeholders may understand and argue
on them.
– To think about the design of a system
– To capture design decisions
– To organize, find, filter, retrieve, examine, and edit information
about large systems.
Ch. 5
35
UML use-case diagrams
• Defines a global view of the actors involved in a system and the
actions that the system performs, which in turn provides an
observable result that is of value to the actors.
• Partitions the overall functionality of the system into
transactions with respect to the actor and illustrates how actors
interact with them.
• Actors define different roles such as: people, computer systems,
environment
borrow
book
return
book
librarian
customer
library
update
Ch. 5
36
Use case diagram notations
•
Association: the communication path between an actor and a use case that the
actor participates in
•
Extend: the insertion of additional behavior into a base use case that extends its
operation.
•
Generalization: relation between a general use case and a more specific use
case that inherits from it.
•
Include: the insertion of additional behavior into a base use case that describes
the details of the base use case.
Actor
Association
Base use case
Place order
<<include>>
Supply
Customer
data
Inclusion use case
<<include>>
<<extent>>
Request
catalog
<<include>>
Arrange
payment
Order
produce
Extension use case
Parent use case
Generalization
Ch. 5
Pay
cash
Child use case
Pay by
credit
37
UML sequence diagram
• Describes how different objects in the system interact
by exchanging messages
• Provides a dynamic and temporal view
• Emphasizes on time sequence of message exchange
Customer
Librarian
Catalogue
member card +
book request
membership
OK
book request
time
book available
book borrowed
Ch. 5
38
Ch. 5
39
UML collaboration diagrams
• Represents object interactions and their order
• Equivalent to sequence diagrams
• Sequence diagram is intended for time ordering
considerations, whereas collaboration is emphasizes
on the structural aspect of the system.
2: membership OK
1: member card +
book request
Customer
3: book request
Librarian
5: book borrowed
Catalogue
4: book available
Ch. 5
40
Ch. 5
41
Finite state machines
(FSMs)
• Can specify control flow aspects
• Defined as
a finite set of states, Q;
a finite set of inputs, I;
a transition function d : Q x I  Q
(d can be a partial function)
a
q1
a
b
q0
q2
c
b
q3
Ch. 5
42
Example: a lamp
Push switch
Off
On
Push switch
Ch. 5
43
Another example:
a plant control system
Hi gh -pre ss u re a la rm
Hi gh -temp eratu re a la rm
On
Off
R e s ta rt
Ch. 5
44
A refinement
Pressure signal
Pressure
Pressure
action
action
Successful
recovery
Temperature signal
Unsuccessful
recovery
Normal
Off
Normal
Off
Successful
recovery
Temperature signal
Unsuccessful
recovery
Temperature
action
Ch. 5
Pressure signal
45
Classes of FSMs
• Deterministic/nondeterministic
• FSMs as recognizers
– introduce final states
• FSMs as transducers
– introduce set of outputs
• ...
Ch. 5
46
FSMs as recognizers
q1
e
g
q2
q3
i
q
4
n
b
q0
qf
e
q5
q6
n
d
qf is a final state
Ch. 5
47
FSMs as recognizers
<letter>
<digit>
q
<letter>
0
q1
_
<letter>
Legend:
<letter>
<d igit>
q2
<digit>
is an abbreviation for a set of arrows
labeled a, b,..., z, A,..., Z,
respectively
is an abbreviation for a set of arrows
labeled 0, 1,..., 9, respectively
Ch. 5
48
Limitations
• Finite memory
• State explosion
– Given a number of FSMs with k1, k2, … kn
states, their composition is a FSM with k1 *
k2 *… * kn. This growth is exponential with
the number of FSMs, not linear (we would
like it to be k1 + k2 +… + kn )
Ch. 5
49
State explosion: an example
p ro d uc e
P r od uce r
p1
p2
d ep osit
get
C on su m er
c1
c2
co n sum e
d ep osit
d ep osit
St or a g e
0
1
gCh.
et
5
2
get
50
The resulting FSM
w rite
w rite
<1, p ,c >
1 1
<0, p ,c >
1 1
consume
consume
produce
consume
produce
<0, p ,c >
2 1
<2, p ,c >
1 1
produce
<1, p ,c>
2 1
<2, p ,c >
2 1
read
<0, p ,c >
1 2
<1, p ,c >
1 2
<2, p ,c >
1 2
read
produce
consume
<0, p , c >
2 2
read
w rite
produce
read
w rite
consume
<1, p ,c >
2 2
Ch. 5
produce
consume
<2, p ,c >
2 2
51
FSM simulator
Ch. 5
52
More Resources on FSM
• Course web page has several examples of finite state
machines in reading questions
• Wikipedia
– http://en.wikipedia.org/wiki/Finite_state_machine
• For more in-depth study refer to the text books for
finite automata theory.
Ch. 5
53
Descargar

Specification