Transcript sigcse99stat - Rice University

Patterns for Decoupling
Data Structures
and Algorithms
Dung “Zung” Nguyen
Pepperdine University/University of Houston
Stephen Wong
Oberlin College
http://exciton.cs.oberlin.edu/research/sigcse99
What’s a “List”?
 So many authors, so many
definitions!
 Java 1.2 Foundation Classes (JFC)
 GoF
 Common ground:
 a minimal and complete set of methods
Teaching Recursion
 Traditional Approach
 Ordered Insert example
 Always having to check for the state of
the system -- what a pain!
 Look-ahead - what a mess!
 Swapping -- how confusing!
 Have my goals been lost in the code
specifics?
Back To Basics...
Linear Recursive Structure
 A linear recursive structure (LRS)
can be empty or non-empty.
 If a LRS is empty, it contains no
element.
 If it is not empty, it contains an
element called first, and a LRS
object called rest.
A LRS is a 2-state object!
State Pattern Implementation
LRStruct
<<context>>
All requests
delegated to
the state.
_state
NullCase
AState
<<abstract state>>
_rest
NonNullCase
NullCase
_first : Object
Requests handled by polymorphism!
Invariants vs. Variants
 Invariant Behaviors:
 Intrinsic to the definition of the data
structure.
 Complete and minimal set.
 Variant Behaviors:
 Extrinsic algorithms operating on the
structure.
 Composed of invariant methods.
Basic Instinct
KISS
“Keep it simple and no simpler.”
Basic behavior of a LRS
Expose the components of its
structure for the client to
manipulate.
Invariant Behaviors
 Functional:
 getFirst: Object // “car”
 insertAsFirst (dat: Object) // “cons”
 getRest: LRStruct // “cdr”
 Imperative:
 setFirst (dat: Object)
 removeFirst: Object
 setRest (tail: LRStruct)
Big Deal!
Added Intelligence
 A LRS should be able to execute any
algorithm, past, present, and future,
that operates on its structure, without
changing any existing code.
 execute(algo: IAlgo, input: Object):Object
an algorithm is an object!
What kind of object is an
algorithm?
Algorithm to insert input into an
Ordered LRS
 LRS is in Null Case
 insert input as first in the LRS
 LRS is in Non-Null Case
 If first element < input
insert input as first in the LRS
 Else
 recurse on the rest of the LRS
base case/non-base case coding pattern!
Algorithm Interface
IAlgo
IAlgo
«Interface»
+nullCase(host:
+nullCase(host:
LRStruct,
LRStruct,
pa ram:
pa ram:
Object)
Object)
: Object
: Object
Null case handler. +nonNullCa
IAlgo
+nonNullCa
se(host:
se(host:
LRStruct,
LRStruct,
pa ram:
pa
ram:
Object)
Object)
: Object
: Object
+nullCa se(host: LRStruct, par am: Object) : Object
+nonNullCa se(host: LRStr uct, para m: Object) : Object
Non-null case handler.
«concrete
«concrete
algorithm»
algorithm»
Algo1
Algo1
«concrete
«concrete
algorithm»
algorithm»
Algo2
Algo2
nullCase(host:
+nullCase(host:
LRStruct,
LRStruct,
param
param
: Object)
: Object)
: Object
: Object
«concrete
algorithm»
nonNullCase(host:
+nonNullCase(host:
LRStruct,
LRStruct,
param
param
: Object)
: Object)
: Object
: Object
+nullCase(host:
+nullCase(host:
LRStruct,
LRStruct,
param
param
: Object)
: Object)
: Object
: Object
«concrete
algorithm»
+nonNullCase(host:
+nonNullCase(host:
LRStruct,
LRStruct,
param
param
: Object)
: Object)
: Object
: Object
Algo1
Algo2
+nullCase(host: LRStruct, param:
Object)
: Object
+nullCase(host:
param: Object) : O
Who
determines
which
methodLRStruct,
is invoked?
+nonNullCas e(host: LRStr uct, param: Object) : Object
+nonNullCas e(host: LRStr uct, param: Objec
Algorithm Interface
Null case handler.
«Interface»
IAlgo
+nullCa se(host: LRStruct, par am: Object) : Object
+nonNullCa se(host: LRStr uct, para m: Object) : Object
Non-null case handler.
«concrete algorithm»
«concrete algorithm»
Algo1
Algo2
+nullCase(host: LRStruct, param:
: Object
+nullCase(host:
param: Object)
WhoObject)
determines
which
method isLRStruct,
invoked?
+nonNullCas e(host: LRStr uct, param: Object) : Object
+nonNullCas e(host: LRStr uct, param: Obje
“Visiting” the State Pattern
returnreturn
_state.execute(algo,
this,
param);
this,
param);
return_state.execute(algo,
_state.execute(algo,
this,
param);
Request delegated to
AState
AState
execute(algo:
IAlgo,
host:
LRStruct,
pa
ram:
ObjObj
ect)ect)
: Obj
ect ect
execute(algo:
IAlgo,
host:
LRStruct,
pa ram:
: Obj
«abstract
state»
«abstract
state»
_state
_state
_state
AState
AState
+e xecute(algo: IAlgo,«host»
par
am: Obje ct) : Object
«host»
LRStruct
LRStruct
+execute(algo:
IAlgo, param:
ect) : Object
+e_rest
xecute(algo: IAlgo,
param :Obj
Object)
: Object
execute(algo:IAlgo,
IAlgo, host: LRStruct,
Object)
: Object
execute(algo:
LRStruct,param:
para m:
Object)
: Object
_rest
_rest
Flow Control via polymorphism
«concrete
state»
«concrete
state»
NonNullCase
NonNullCase
«concretestate»
state»
-Object:
-Object:
_first_first
«concrete
execute(algo:
IAlgo,
host:
LRStruct,
param:
: Obje
execute(algo:
IAlgo,
host:
LRStruct,
param:
ObjeObje
ct) :ct)
Obje
ct ct
NonNullCase
NonNullCase
return algo.nonNullCase(host, param);
return
algo.nonNullCase(host,
param);
return
algo.nonNullCase(host,
param);
«concrete
state»
«concrete
state»
NullCase
NullCase
«concrete
state»
execute(algo:
IAlgo,
host:
LRStruct,
param:
: Obje
execute(algo:
IAlgo,
host:
LRStruct,
param:
ObjeObje
ct) :ct)
Obje
ct ct
NullCase
return algo.nullCase(host, param);
return
algo.nullCase(host,
param);
return
algo.nullCase(host,
param);
Each state calls the appropriate “visiting” method
The Visitor Design Pattern
A system of cooperating objects:
Hosts
Visitors
- Invariant behaviors
- Consistent “hook”
for visitors
-Variant behaviors
- Fixed invocation
interface
- Call only the desired
method in the visitor
- Separate method
for each host
Ordered Insertion Abstraction
 Null Case
 Insert here!
 Non-Null Case
 If local value < input
insert here
 Else
recurse on the rest
Seems simple enough...
The Drive Towards Abstraction
 Key to robust, reusable code.
 Key to solving new problems.
 Key to putting different problems
into proper perspectives.
 Teach students to look for the
abstraction of the problem from the
very start.
Traditional Implementation
 If empty
 Else
• attach next node
as temp’s rest
• attach temp as this
node’s rest.
 make new list with
value
 Else
 If value <input
 put value in temp
 put input in value
 if next node empty
• attach temp as rest
 Else
 if next node empty
• put input in temp
• attach temp as rest
 else
• recurse on the rest
Hey! What happened to my simple abstraction???
Ordered Insertion Abstraction
Let’s try this again...
 Null Case
 Insert here!
 Non-Null Case
 If local value < input
insert here
 Else
recurse on the rest
State+Visitor Implementation
 nullCase(host, input)
 host.insertAsFirst(input)
 nonNullCase(host, input)
 if (host.getFirst() < input)
No Flow Control!
The LRS host
determines what
happens and when.
host.insertAsFirst(input)
 else
(host.getRest()).execute(this, input)
Such magic when the implementation
matches the abstraction!
State+Visitor Lists
 Demonstrate the power of a close
match between an abstraction and
its implementation.
 Enable students to concentrate on
the fundamentals of data and
algorithm abstraction
 Enable students to easily isolate the
key issues in recursion.
Patterns and Pedagogy
 Fundamental thinking tools of CS
 Abstraction
 Recursion
 Software engineering goals
 Reusability
 Extensibility
 Robustness
Conclusions
 The state pattern properly implements
the abstraction of a list.
 The abstraction of the algorithm-list
relationship leads to the visitor pattern.
 Data structures are naturally decoupled
from their algorithms. This can be
expressed using the state+visitor
pattern.
Further Information
 http://exciton.cs.oberlin.edu/research/sigcse99