The State Design Pattern Readings: OOSC2 Chapter 20
EECS3311 A: Software Design Fall 2019
CHEN-WEI WANG
Motivating Problem
Consider the reservation panel of an online booking system:
2 of 29
State Transition Diagram
Characterize interactive system as: 1) A set of states; and 2) For each state, its list of applicable transitions (i.e., actions). e.g., Above reservation system as a :
finite state machine
3 of 29
(6)
Final
1
(1)
Initial
33
(5) 2 2 (2)
Confirmation Flight Enquiry
32 32 2
(4) (3)
Reservation 3 Seat Enquiry
Design Challenges
1. The state-transition graph may large and sophisticated. A large number N of states has O(N2) transitions
2. The graph structure is subject to extensions/modifications. e.g., To merge “(2) Flight Enquiry” and “(3) Seat Enquiry”:
Delete the state “(3) Seat Enquiry”. Delete its 4 incoming/outgoing transitions.
e.g., Add a new state “Dietary Requirements”
3. A general solution is needed for such interactive systems .
e.g., taobao, eBay, amazon, etc.
4 of 29
A First Attempt
from
Display Seat Enquiry Panel
until
not (wrong answer or wrong choice)
do
Read user’s answer for current panel Read user’s choice for next step if wrong answer or wrong choice then
Output error messages
end end
Process user’s answer
case in
2: goto 2 Flight Enquiry panel 3: goto 4 Reservation panel
end
1 Initial panel:
— Actions for Label 1.
2 Flight Enquiry panel:
— Actions for Label 2.
— Actions for Label 3.
4 Reservation panel:
— Actions for Label 4.
5 Confirmation panel:
— Actions for Label 5.
6 Final panel:
— Actions for Label 6.
3 Seat Enquiry panel:
C
C
5 of 29
3 Seat Enquiry panel:
A First Attempt: Good Design?
● Runtime execution ≈ a “bowl of spaghetti”.
⇒ The system’s behaviour is hard to predict, trace, and debug.
● Transitions hardwired as system’s central control structure. ⇒ The system is vulnerable to changes/additions of
states/transitions.
● All labelled blocks are largely similar in their code structures.
⇒ This design “smells” due to duplicates/repetitions!
● The branching structure of the design exactly corresponds to
that of the specific transition graph.
⇒ The design is application-specific and not reusable for
other interactive systems.
6 of 29
A Top-Down, Hierarchical Solution
●
Separation of Concern Declare the transition table as a feature the system, rather than its central control structure:
transition (src: INTEGER; choice: INTEGER): INTEGER
— Return state by taking transition ’choice’ from ’src’ state.
require valid_source_state: 1 à src à 6 valid_choice: 1 à choice à 3
ensure valid_target_state: 1 à Result à 6
● We may implement transition via a 2-D array.
CHOICE
SRC STATE
1
2
3
1 (Initial)
2 (Flight Enquiry)
3 (Seat Enquiry)
4 (Reservation)
5 (Confirmation)
6 (Final)APPLICATION
6 – – – – –
5 1 2 3 4 –
2 3 4 5 1 –
app
transition: ARRAY2[INTEGER]
7 of 29
app.states
1 2 3
4 5
choice
123 1
2 3
state
4 5 6
6
5
2
1
3
2
3
4
5
4
1
states: ARRAY[STATE]
Hierarchical Solution: Good Design?
● This is a more general solution.
∵ State transitions are separated from the system’s central
control structure.
⇒ Reusable for another interactive system by making
changes only to the transition feature.
● How does the central control structure look like in this design?
8 of 29
Hierarchical Solution:
Top-Down Functional Decomposition
Modules of execute session and execute state are general
enough on their control structures. ⇒ reusable 9 of 29
Hierarchical Solution: System Control
All interactive sessions share the following control pattern:
○ Start with some initial state.
○ Repeatedly make state transitions (based on choices read from
the user) until the state is final (i.e., the user wants to exit).
execute_session
— Execute a full interactive session.
local
current state , choice: INTEGER
do from
current_state := initial until
is final (current_state) do
choice := execute state ( current state )
current_state := transition (current_state, choice) end
end
10 of 29
Hierarchical Solution: State Handling (1) The following control pattern handles all states:
execute_state ( : INTEGER): INTEGER — Handle interaction at the current state. — Return user’s exit choice.
local
answer: ANSWER; valid_answer: BOOLEAN; choice: INTEGER
current state
do from
until
valid_answer
do
display( current state )
answer := read answer( ) choice := read choice( ) valid_answer := correct(
if not valid_answer then message(
end
process( current state , answer)
Result := choice end
, answer)
, answer)
11 of 29
current state current state
current state
current state
Hierarchical Solution: State Handling (2)
FEATURE CALL
display(s) read answer(s) read choice(s)
FUNCTIONALITY
Display screen outputs associated with state s
Read user’s input for answers associated with state s Read user’s input for exit choice associated with state s
correct(s, answer) Is the user’s answer valid w.r.t. state s? process(s, answer) Given that user’s answer is valid w.r.t. state s,
process it accordingly.
message(s, answer) Given that user’s answer is not valid w.r.t. state s,
display an error message accordingly.
Q: How similar are the code structures of the above state-dependant commands or queries?
12 of 29
Hierarchical Solution: State Handling (3)
A: Actions of all such state-dependant features must explicitly discriminate on the input state argument.
display(current_state: INTEGER) require
valid_state: 1 à current_state à 6 do
if current_state = 1 then — Display Initial Panel
elseif current_state = 2 then
— Display Flight Enquiry Panel
…
else
— Display Final Panel
end end
13 of 29
e.g., To add/delete a state Add/delete a branch in all such features.
○ Such design !
∵ Same list of conditional repeats for all state-dependant features.
○ Such design violates the Single Choice Principle .
smells
Hierarchical Solution: Visible Architecture
14 of 29
Hierarchical Solution: Pervasive States
Too much data transmission: current state is passed
○ From execute session (Level 3) to execute state (Level 2)
○ From execute state (Level 2) to all features at Level 1 15 of 29
Law of Inversion
If your routines exchange too many data, then put your routines in your data.
e.g.,
execute state (Level 2) and all features at Level 1: Pass around (as inputs) the notion of current state
Build upon (via discriminations) the notion of current state
s: INTEGER
s: INTEGER
s: INTEGER
s: INTEGER
s: INTEGER
s: INTEGER
s: INTEGER
execute state display
read answer read choice correct process message
( )
( )
( )
( )
( ; answer: ANSWER) ( ; answer: ANSWER) ( ; answer: ANSWER)
⇒
⇒
the notion of state as class STATE. state-related information via a STATE interface.
Modularize
Encapsulate
⇒ Notion of current state becomes implicit: the Current class.
16 of 29
Grouping by Data Abstractions
17 of 29
Architecture of the State Pattern
18 of 29
+* APPLICATION ▶ STATE
execute+ read* display* correct* process* message*
INITIAL
+ HELP
FLIGHT_ENQUIRY
+ SEAT_ENQUIRY
+ RESERVATION
state_implementations
++
++
FINAL CONFIRMATION
The STATE ADT
deferred class STATE read
— Read user’s inputs
— Set ’answer’ and ’choice’ deferred end
answer: ANSWER
— Answer for current state
choice: INTEGER
— Choice for next step
display
— Display current state
deferred end correct: BOOLEAN
deferred end
process
require correct deferred end
message
require not correct deferred end
execute
local
good: BOOLEAN
do from
until
good
loop
display
— set answer and choice
read
good := correct if not good then
message
end end
process
end end
19 of 29
The Template Design Pattern
Consider the following fragment of Eiffel code:
1 2 3 4 5
s: STATE
create {SEAT ENQUIRY} s.make s.execute
create {CONFIRMATION} s.make s.execute
L2 and L4: the same version of effective feature execute (from the deferred class STATE) is called. [ template ]
L2: specific version of effective features display, process, etc., (from the effective descendant class SEAT ENQUIRY) is called. [ template instantiated for SEAT ENQUIRY ] L4: specific version of effective features display, process, etc., (from the effective descendant class CONFIRMATION ) is called. [ template instantiated for CONFIRMATION ]
20 of 29
APPLICATION Class: Array of STATE
APPLICATION
transition: ARRAY2[INTEGER]
app.states
states: ARRAY[STATE]
21 of 29
INITIAL
FLIGHT_ ENQUIRY
SEAT_ ENQUIRY
choice
123 1
2 3
state
6
5
2
1
3
2
4
3
5
4
1
app
4
5
6 123456
RESERVATION
CONFIRMATION
FINAL
APPLICATION Class (1)
class APPLICATION create make
feature {NONE} — Implementation of Transition Graph
transition: ARRAY2[INTEGER]
— State transitions: transition[state, choice]
states: ARRAY[STATE]
— State for each index, constrained by size of ‘transition’
feature
initial: INTEGER number_of_states: INTEGER number_of_choices: INTEGER make(n, m: INTEGER)
do number_of_states := n number_of_choices := m
create transition.make_filled(0, n, m) create states.make_empty
end
invariant
end
transition.height = number of states
transition.width = number of choices
22 of 29
APPLICATION Class (2)
class APPLICATION
feature {NONE} — Implementation of Transition Graph
transition: ARRAY2[INTEGER]
states: ARRAY[STATE] feature
put_state(s: STATE; index: INTEGER) require 1 à index à number_of_states do states.force(s, index) end
choose_initial(index: INTEGER) require 1 à index à number_of_states do initial := index end
put_transition(tar, src, choice: INTEGER) require
1 à src à number_of_states
1 à tar à number_of_states
1 à choice à number_of_choices
do
transition.put(tar, src, choice) end
end
23 of 29
Example Test: Non-Interactive Session
test_application: BOOLEAN local
app: APPLICATION ; current_state: STATE ; index: INTEGER do
create app.make (6, 3)
app.put_state (create {INITIAL}.make, 1)
— Similarly for other 5 states.
app.choose_initial (1)
— Transit to FINAL given current state INITIAL and choice 1. app.put_transition (6, 1, 1)
— Similarly for other 10 transitions.
index := app.initial
current_state := app.states [index]
Result := attached {INITIAL} current_state
check Result end
— Say user’s choice is 3: transit from INITIAL to FLIGHT_STATUS index := app.transition.item (index, 3)
current_state := app.states [index]
Result := attached {FLIGHT_ENQUIRY} current_state
end
24 of 29
APPLICATION Class (3): Interactive Session
class APPLICATION
feature {NONE} — Implementation of Transition Graph
transition: ARRAY2[INTEGER]
states: ARRAY[STATE] feature
execute_session
local
current_state: STATE
index: INTEGER do
from
index := initial until
is_final (index) loop
current state := states[index]
— polymorphism — dynamic binding
current state.execute
index := transition.item (index, current_state.choice) end
end
end
25 of 29
Building an Application
○ Create instances of STATE.
○ Initialize an APPLICATION.
○ Perform polymorphic assignments on app.states.
○ Choose an initial state.
○ Build the transition table.
○ Run the application.
26 of 29
s1: STATE
create {INITIAL} s1.make
create app.make(number_of_states, number_of_choices)
app.put_state(initial, 1)
app.choose_initial(1)
app.put_transition(6, 1, 1)
app.execute_session
Top-Down, Hierarchical vs. OO Solutions
● In the second (top-down, hierarchy) solution, it is required for every state-related feature to explicitly and manually discriminate on the argument value, via a a list of conditionals.
e.g., Given , the
calls and behave differently.
● The third (OO) solution, called the State Pattern, makes such conditional implicit and automatic, by making STATE as a deferred class (whose descendants represent all types of states), and by delegating such conditional actions to
dynamic binding .
e.g., Given , behaviour of the call
depends on the dynamic type of s (such as INITIAL vs.
FLIGHT ENQUIRY). 27 of 29
display(current state: INTEGER)
display(1)
display(2)
s: STATE
s.display
Index (1)
Motivating Problem
State Transition Diagram
Design Challenges
A First Attempt
A First Attempt: Good Design?
A Top-Down, Hierarchical Solution
Hierarchical Solution: Hierarchical Solution: Top-Down Functional Hierarchical Solution: Hierarchical Solution: Hierarchical Solution: Hierarchical Solution:
Hierarchical Solution:
Good Design?
Decomposition System Control State Handling (1) State Handling (2) State Handling (3) Visible Architecture
28 of 29
Index (2)
Hierarchical Solution: Pervasive States
Law of Inversion
Grouping by Data Abstractions
Architecture of the State Pattern
The STATE ADT
The Template Design Pattern
APPLICATION Class: Array of STATE APPLICATION Class (1)
APPLICATION Class (2)
Example Test: Non-Interactive Session APPLICATION Class (3): Interactive Session Building an Application
Top-Down, Hierarchical vs. OO Solutions
29 of 29