Continuing off the recent parts of this article, I'll be talking about the lack of "states" in the object-oriented paradigm as well as the State design pattern alternative and its flaws. Then I'll suggest an addition to the concept model from the last part in this series that accommodates states.
Objects should have the ability to change their behavior at run-time based on their "state". For example, a shark behaves differently when he's hungry than when he's not. Its behavior changes, but unlike typical OOP, you're not subclassing. You don't want to write a "HungryShark" class and allocate a new one to replace the non-hungry Shark. It's the same Shark. But now he's hungry. Another example is a Stack class that behaves differently depending on whether its empty, full, or other. We'll be looking at this example from three approaches: "state-less" design, the State design pattern, and my proposal.
State-less design
We'll start by looking at some code which serves as a Stack collection class that uses an internal array for storage. For this example, the Stack will have a maximum height which is passed into the constructor during initialization. And we'll show the first two designs in Java here and use my model for the end proposal.
class Stack
{
protected Object[] items;
protected int height;
public Stack(int maxSize)
{
items = new Object[maxSize];
height = 0;
}
public void clear()
{// only clear if not already empty
if(height != 0)
{
// memory wasting solution
items = new object[items.length];
height = 0;
}
}
public boolean empty() { return height == 0; }
public int getHeight() { return height; }
public Object peek()
{
if(height == 0)
throw new Exception("illegal peek: empty stack");
return items[height - 1];
}
public Object pop()
{
if(height == 0)
throw new Exception("illegal pop: empty stack");
object o = items[height - 1];
height--;
return o;
}
public void push(Object o)
{
if(height == items.length)
throw new Exception("illegal push: stack full");
items[height++] = o;
}
}
This is an example of "state-less design". Do you see how often we have to check the height? That's right. In almost every method. That's way too often, but unfortunately, this is a very typical solution to designing this sort of class. This design has a lot of time wasted trying to determine if the stack if empty (or full for push()) which are only the extreme cases.
The State Pattern
One of the fundamental OO design patterns is the State Pattern. The State pattern allows an object-oriented way to change an object's behavior dependent on its "state" as I mentioned in the beginning. For example, in the above Stack class, a call to pop() when the stack is empty is very different from when its not empty.
The solution to this is the State Pattern. Using the state pattern, we would have our Client maintain a "state" variable which kept track of what state it was currently. Then each State would have it own distinct class that inherits a common State interface. And in this example, we'll have a Context class which holds the state so the state classes can modify the Stack's state.
class Stack
{
private StackContext context;
public Stack(int maxSize)
{
context = new StackContext(maxSize);
}
public void clear()
{
context.getState().clear();
}
public boolean empty()
{
return context.getState().empty();
}
public int getHeight()
{
return context.getState().getHeight();
}
public Object peek()
{
return context.getState().peek();
}
public Object pop()
{
return context.getState().pop();
}
public void push(Object o)
{
context.getState().push(o);
}
}
class StackContext
{
public Object[] items;
public int height;
protected StackState state;
public StackContext(int maxSize)
{
items = new Object[maxSize];
height = 0;
state = new EmptyState(this);
}
public void setState(StackState s)
{
state = s;
}
public StackState getState()
{
return state;
}
}
abstract class StackState
{
protected StackContext context;
public StackState(StackState s)
{
this.context = c;
}
public abstract void clear();
public abstract boolean empty();
public abstract int getHeight();
public abstract Object peek();
public abstract Object pop();
public abstract void push(Object o);
}
class EmptyState extends StackState
{
public EmptyState(StackContext context)
{
super(context);
}
public void clear()
{
// already empty. do nothing.
}
public boolean empty() { return true; }
public int getHeight() { return 0; }
public Object peek()
{
throw new Exception("illegal peek: empty stack");
}
public Object pop()
{
throw new Exception("illegal pop: empty stack");
}
public void push(Object o)
{
items[height++] = o;
context.setState(new DefaultState(context));
}
}
// We'll call the state that is non-empty and non-full the "default state"
class DefaultState extends StackState
{
public DefaultState(StackContext context) {
super(context);
}
public void clear()
{
// memory wasting solution
context.items = new object[items.length];
context.height = 0;
context.setState(new EmptyState(context));
}
public boolean empty() { return false; }
public int getHeight() { return context.height; }
public Object peek()
{
return items[context.height - 1];
}
public Object pop()
{
Object o = items[context.height - 1];
context.height--;
if(context.height == 0)
context.setState(new EmptyState(context));
return o;
}
public void push(Object o)
{
items[context.height++] = o;
if(context.height == context.items.length)
context.setState(new FullState(context));
}
}
// inherits some behavior from the "default state"
class FullState extends DefaultState
{
public FullState(StackContext context) {
super(context);
}
public Object pop()
{
Object o = super.pop();
context.setState(new DefaultState(context));
return o;
}
public void push(Object o)
{
throw new Exception("illegal push: stack full");
}
}Wow, that is ugly, isn't it? Almost makes you want to quit programming right now to avoid it. For a pattern that's supposed to simplify dynamic behavior, that's a lot of new classes and code. I had to add an abstract StackState class was inherited by our three state classes EmptyState, DefaultState, and FullState. Also, I needed to create a StackContext class to hold the stack's state as well as move all the stack's private data into the context. This was done so that the state classes could modify the Stack's state and internals without having to them public which would allow anyone to change the Stack's state to anything at any time (and yes, in Java, I could have used inner classes to get around contexts but pretend we don't have inner classes). While some classes may allow their state publicly viewable, others will not. I chose hiding the state for this example because it shows the more complicated side of this pattern.
I like the State pattern and use it when I can but that's a lot of work to get rid of a few if-else/switch statements if you ask me. We have new "if" statements to check in state on push() and pop() but the other methods don't have to check the state too which is nice. While each of the states' methods are simpler, the whole design is a lot more complicated. This design needs six classes to represent essentially one concept that changes its behavior between 3 states. We're definitely clogging up the namespace now and typically classes that use the state pattern have more than 3 states so this isn't very nice easy to maintain if it needs to grow.
Also note that none these states add any data of their own. Each StackState class only needs to hold onto the context but adds no data of its own. And yet, every time we switch states we have to allocate a new state object. So in the State design pattern, you're not really changing your behavior, you're allocating a "behavior object" (so to speak) that's really doing the work for the actual object.
The new "state"
Now its time for the proposal. If you haven't guessed by now, the proposal is about incorporating states into the OO model. Imagine languages with builtin state support based on Cecil's "predicate objects" only simplified. Imagine something like this:
concept Stack
{
interface
{
void clear();
bool empty();
int getHeight();
object peek();
object pop();
void push(object o);
}
implementation
{
protected Object[] items;
protected int height;
public Stack(int maxSize)
{
items = new Object[maxSize];
height = 0;
// Every object has a builtin "state".
// This class starts in the EmptyStack state.
state = EmptyStack;
}
// Basic method implementations of the interface
// are known as the "default state"
// In this example, same as previous "DefaultState" class
// A class will start in the default state if no
// state set in constructor.
public void clear()
{
// memory wasting solution
items = new object[items.length];
height = 0;
state = EmptyStack;
}
public bool empty() { return false; }
public int height() { return height; }
public Object peek()
{
return items[height - 1];
}
public Object pop()
{
object o = items[height - 1];
height--;
if(top == 0)
state = EmptyStack;
return o;
}
public void push(Object o)
{
items[height++] = o;
if(height == items.length)
state = FullStack;
}
// Formal definition of the EmptyStack state.
// states implicitly "inherits" the methods
// from the "default state"
// and can override any it wishes.
state EmptyStack
{
void clear()
{
// already empty. do nothing.
}
bool empty() { return true; }
int getHeight()
{
return 0;
}
object peek()
{
throw new Exception("illegal peek: empty stack");
}
object pop()
{
throw new Exception("illegal pop: empty stack");
}
void push(object o)
{
// Revert to the default state
state = default;
// Calls the default push() instead of
// this push() since state changed back to default
push(o);
}
}
// The stack-full state.
// Only needs to override two methods.
state FullStack
{
void push(object o)
{
throw new Exception("illegal push: stack full");
}
object pop()
{
state = default;
return pop();
}
}
}
}We invented a solution much simpler than using the State Design Pattern by hand but still bigger and more flexible than the original Stack class design.
So how does it do this? Well it's important to note that the states belong to an implementation, therefore they can access the object's internals and state without needing a context or publicly exposing the internals (sort of like inner classes). However, states are not types. You can not declare an EmptyStack variable or call an EmptyStack constructor because they're not types. They don't even exist outside the implementation (except in an implementation that inherits it). If they were types, this:
EmptyStack s = new EmptyStack();
s.push(new Object());would break static typing on the second line because its no longer an EmptyStack and this would cause the world as we know it to implode (or so I've been told).
As of right now in the design, states do not have member variables (aka fields). This allows state switching to occur without any memory allocations at all. However, it would be easy to add fields to be internal to the state which would require an allocation to make room for those fields during a switch or we could follow the Cecil route and have the object size padded on allocation to fit the fields on its largest state (like the C/C++ "union"). The second option requires no memory allocations to switch but may have some unused space depending on the frequency of the state and size of all its fields. If states had fields, they would get their own constructor-esque functions called when switching to that state.
I really wish I had these now.
-Kaja
No comments:
Post a Comment