The State pattern and the State monad
source link: https://blog.ploeh.dk/2022/09/05/the-state-pattern-and-the-state-monad/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
The State pattern and the State monad by Mark Seemann
The names are the same. Is there a connection? An article for object-oriented programmers.
This article is part of a series of articles about specific design patterns and their category theory counterparts. In this article I compare the State design pattern to the State monad.
Since the design pattern and the monad share the name State you'd think that they might be isomorphic, but it's not quite that easy. I find it more likely that the name is an example of parallel evolution. Monads were discovered by Eugenio Moggi in the early nineties, and Design Patterns is from 1994. That's close enough in time that I find it more likely that whoever came up with the names found them independently. State, after all, is hardly an exotic word.
Thus, it's possible that the choice of the same name is coincidental. If this is true (which is only my conjecture), does the State pattern have anything in common with the State monad? I find that the answer is a tentative yes. The State design pattern describes an open polymorphic stateful computation. That kind of computation can also be described with the State monad.
This article contains a significant amount of code, and it's all quite abstract. It examines the abstract shape of the pattern, so there's little prior intuition on which to build an understanding. While later articles will show more concrete examples, if you want to follow along, you can use the GitHub repository.
Shape #
Design Patterns is a little vague when it comes to representing the essential form of the pattern. What one can deduce from the diagram in the Structure section describing the pattern, you have an abstract State
class with a Handle
method like this:
public virtual void Handle(Context context) { }
This, however, doesn't capture all scenarios. What if you need to pass more arguments to the method? What if the method returns a result? What if there's more than one method?
Taking into account all those concerns, you might arrive at a more generalised description of the State pattern where an abstract State
class might define methods like these:
public abstract Out1 Handle1(Context context, In1 in1); public abstract Out2 Handle2(Context context, In2 in2);
There might be an arbitrary number of Handle
methods, from Handle1
to HandleN
, each with their own input and return types.
The idea behind the State pattern is that clients don't interact directly with State
objects. Instead, they interact with a Context
object that delegates operations to a State
object, passing itself as an argument:
public Out1 Request1(In1 in1) { return State.Handle1(this, in1); } public Out2 Request2(In2 in2) { return State.Handle2(this, in2); }
Classes that derive from the abstract State
may then mutate context.State
.
public override Out2 Handle2(Context context, In2 in2) { if (in2 == In2.Epsilon) context.State = new ConcreteStateB(); return Out2.Eta; }
Clients interact with the Context
object and aren't aware of this internal machinery:
var actual = ctx.Request2(in2);
With such state mutation going on, is it possible to refactor to a design that uses immutable data and pure functions?
State pair #
When you have a void
method that mutates state, you can refactor it to a pure function by leaving the existing state unchanged and instead returning the new state. What do you do, however, when the method in question already returns a value?
This is the case with the generalised HandleN
methods, above.
One way to resolve this problem is to introduce a more complex type to return. To avoid too much duplication or boilerplate code, you could make it a generic type:
public sealed class StatePair<T> { public StatePair(T value, State state) { Value = value; State = state; } public T Value { get; } public State State { get; } public override bool Equals(object obj) { return obj is StatePair<T> result && EqualityComparer<T>.Default.Equals(Value, result.Value) && EqualityComparer<State>.Default.Equals(State, result.State); } public override int GetHashCode() { return HashCode.Combine(Value, State); } }
This enables you to change the signatures of the Handle
methods:
public abstract StatePair<Out1> Handle1(Context context, In1 in1); public abstract StatePair<Out2> Handle2(Context context, In2 in2);
This refactoring is always possible. Even if the original return type of a method was void
, you can use a unit type as a replacement for void. While redundant but consistent, a method could return StatePair<Unit>
.
Generic pair #
The above StatePair
type is so coupled to a particular State
class that it's not reusable. If you had more than one implementation of the State pattern in your code base, you'd have to duplicate that effort. That seems wasteful, so why not make the type generic in the state dimension as well?
public sealed class StatePair<TState, T> { public StatePair(T value, TState state) { Value = value; State = state; } public T Value { get; } public TState State { get; } public override bool Equals(object obj) { return obj is StatePair<TState, T> pair && EqualityComparer<T>.Default.Equals(Value, pair.Value) && EqualityComparer<TState>.Default.Equals(State, pair.State); } public override int GetHashCode() { return HashCode.Combine(Value, State); } }
When you do that then clearly you'd also need to modify the Handle
methods accordingly:
public abstract StatePair<State, Out1> Handle1(Context context, In1 in1); public abstract StatePair<State, Out2> Handle2(Context context, In2 in2);
Notice that, as is the case with the State functor, the type declares the type with TState
before T
, while the constructor takes T
before TState
. While odd and potentially confusing, I've done this to stay consistent with my previous articles, which again do this to stay consistent with prior art (mainly Haskell).
With StatePair
you can make the methods pure.
Pure functions #
Since Handle
methods can now return a new state instead of mutating objects, they can be pure functions. Here's an example:
public override StatePair<State, Out2> Handle2(Context context, In2 in2) { if (in2 == In2.Epsilon) return new StatePair<State, Out2>(Out2.Eta, new ConcreteStateB()); return new StatePair<State, Out2>(Out2.Eta, this); }
The same is true for Context
:
public StatePair<Context, Out1> Request1(In1 in1) { var pair = State.Handle1(this, in1); return new StatePair<Context, Out1>(pair.Value, new Context(pair.State)); } public StatePair<Context, Out2> Request2(In2 in2) { var pair = State.Handle2(this, in2); return new StatePair<Context, Out2>(pair.Value, new Context(pair.State)); }
Does this begin to look familiar?
Monad #
The StatePair
class is nothing but a glorified tuple. Armed with that knowledge, you can introduce a variation of the IState interface I used to introduce the State functor:
public interface IState<TState, T> { StatePair<TState, T> Run(TState state); }
This variation uses the explicit StatePair
class as the return type of Run
, rather than a more anonymous tuple. These representations are isomorphic. (That might be a good exercise: Write functions that convert from one to the other, and vice versa.)
You can write the usual Select
and SelectMany
implementations to make IState
a functor and monad. Since I have already shown these in previous articles, I'm also going to skip those. (Again, it might be a good exercise to implement them if you're in doubt of how they work.)
You can now, for example, use C# query syntax to run the same computation multiple times:
IState<Context, (Out1 a, Out1 b)> s = from a in in1.Request1() from b in in1.Request1() select (a, b); StatePair<Context, (Out1 a, Out1 b)> t = s.Run(ctx);
This example calls Request1
twice, and collects both return values in a tuple. Running the computation with a Context
will produce both a result (the two outputs a
and b
) as well as the 'current' Context
(state).
Request1
is a State-valued extension method on In1
:
public static IState<Context, Out1> Request1(this In1 in1) { return from ctx in Get<Context>() let p = ctx.Request1(in1) from _ in Put(p.State) select p.Value; }
Notice the abstraction level in play. This extension method doesn't return a StatePair
, but rather an IState
computation, defined by using the State monad's Get and Put functions. Since the computation is running with a Context
state, the computation can Get
a ctx
object and call its Request1
method. This method returns a pair p
. The computation can then Put
the pair's State
(here, a Context
object) and return the pair's Value
.
This stateful computation is composed from the building blocks of the State monad, including query syntax supported by SelectMany
, Get
, and Put
.
This does, however, still feel unsatisfactory. After all, you have to know enough of the details of the State monad to know that ctx.Request1
returns a pair of which you must remember to Put
the State
. Would it be possible to also express the underlying Handle
methods as stateful computations?
StatePair bifunctor #
The StatePair
class is isomorphic to a pair (a two-tuple), and we know that a pair gives rise to a bifunctor:
public StatePair<TState1, T1> SelectBoth<TState1, T1>( Func<T, T1> selectValue, Func<TState, TState1> selectState) { return new StatePair<TState1, T1>( selectValue(Value), selectState(State)); }
You can use SelectBoth
to implement both Select
and SelectState
. In the following we're only going to need SelectState
:
public StatePair<TState1, T> SelectState<TState1>(Func<TState, TState1> selectState) { return SelectBoth(x => x, selectState); }
This enables us to slightly simplify the Context
methods:
public StatePair<Context, Out1> Request1(In1 in1) { return State.Handle1(this, in1).SelectState(s => new Context(s)); } public StatePair<Context, Out2> Request2(In2 in2) { return State.Handle2(this, in2).SelectState(s => new Context(s)); }
Keep in mind that Handle1
returns a StatePair<State, Out1>
, Handle2
returns StatePair<State, Out2>
, and so on. While Request1
calls Handle1
, it must return a StatePair<Context, Out1>
rather than a StatePair<State, Out1>
. Since StatePair
is a bifunctor, the Request1
method can use SelectState
to map the State
to a Context
.
Unfortunately, this doesn't seem to move us much closer to being able to express the underlying functions as stateful computations. It does, however, set up the code so that the next change is a little easier to follow.
State computations #
Is it possible to express the Handle
methods on State
as IState
computations? One option is to write another extension method:
public static IState<State, Out1> Request1S(this In1 in1) { return from s in Get<State>() let ctx = new Context(s) let p = s.Handle1(ctx, in1) from _ in Put(p.State) select p.Value; }
I had to add an S
suffix to the name, since it only differs from the above Request1
extension method on its return type, and C# doesn't allow method overloading on return types.
You can add a similar Request2S
extension method. It feels like boilerplate code, but enables us to express the Context
methods in terms of running stateful computations:
public StatePair<Context, Out1> Request1(In1 in1) { return in1.Request1S().Run(State).SelectState(s => new Context(s)); } public StatePair<Context, Out2> Request2(In2 in2) { return in2.Request2S().Run(State).SelectState(s => new Context(s)); }
This still isn't entirely satisfactory, since the return types of these Request
methods are state pairs, and not IState
values. The above Request1S
function, however, contains a clue about how to proceed. Notice how it can create a Context
object from the underlying State
, and convert that Context
object back to a State
object. That's a generalizable idea.
Invariant functor #
While it's possible to map the TState
dimension of the state pair, it seems harder to do it on IState<TState, T>
. A tuple, after all, is covariant in both dimensions. The State monad, on the other hand, is neither co- nor contravariant in the state dimension. You can deduce this with positional variance analysis (which I've learned from Thinking with Types). In short, this is because TState
appears as both input and output in StatePair<TState, T> Run(TState state)
- it's neither co- nor contravariant, but rather invariant.
What little option is left us, then, is to make IState
an invariant functor in the state dimension:
public static IState<TState1, T> SelectState<TState, TState1, T>( this IState<TState, T> state, Func<TState, TState1> forward, Func<TState1, TState> back) { return from s1 in Get<TState1>() let s = back(s1) let p = state.Run(s) from _ in Put(forward(p.State)) select p.Value; }
Given an IState<TState, T>
the SelectState
function enables us to turn it into a IState<TState1, T>
. This is, however, only possible if you can translate both forward
and back
between two representations. When we have two such translations, we can produce a new computation that runs in TState1
by first using Get
to retrieve a TState1
value from the new environment, translate it back
to TState
, which enables the expression to Run
the state
. Then translate the resulting p.State
forward
and Put
it. Finally, return the Value
.
As Sandy Maguire explains:
"... an invariant type
Sandy Maguire, Thinking with TypesT
allows you to map froma
tob
if and only ifa
andb
are isomorphic. [...] an isomorphism betweena
andb
means they're already the same thing to begin with."
This may seem limiting, but is enough in this case. The Context
class is only a wrapper of a State
object:
public Context(State state) { State = state; } public State State { get; }
If you have a State
object, you can create a Context
object via the Context
constructor. On the other hand, if you have a Context
object, you can get the wrapped State
object by reading the State
property.
The first improvement this offers is simplification of the Request1
extension method:
public static IState<Context, Out1> Request1(this In1 in1) { return in1.Request1S().SelectState(s => new Context(s), ctx => ctx.State); }
Recall that Request1S
returns a IState<State, Out1>
. Since a two-way translation between State
and Context
exists, SelectState
can translate IState<State, Out1>
to IState<Context, Out1>
.
The same applies to the equivalent Request2
extension method.
This, again, enables us to rewrite the Context
methods:
public StatePair<Context, Out1> Request1(In1 in1) { return in1.Request1().Run(this); } public StatePair<Context, Out2> Request2(In2 in2) { return in2.Request2().Run(this); }
While this may seem like an insignificant change, one result has been gained: This last refactoring pushed the Run
call to the right. It's now clear that each expression is a stateful computation, and that the only role that the Request
methods play is to Run
the computations.
This illustrates that the Request
methods can be decomposed into two decoupled steps:
- A stateful computation expression
- Running the expression
The question now becomes: How useful is the Context
wrapper class now?
Eliminating the Context #
A reasonable next refactoring might be to remove the context
parameter from each of the Handle
methods. After all, this parameter is a remnant of the State design pattern. Its original purpose was to enable State
implementers to mutate the context
by changing its State
.
After refactoring to immutable functions, the context
parameter no longer needs to be there - for that reason. Do we need it for other reasons? Does it carry other information that a State
implementer might need?
In the form that the code now has, it doesn't. Even if it did, we could consider moving that data to the other input parameter: In1
, In2
, etcetera.
Therefore, it seems sensible to remove the context
parameter from the State
methods:
public abstract StatePair<State, Out1> Handle1(In1 in1); public abstract StatePair<State, Out2> Handle2(In2 in2);
This also means that a function like Request1S
becomes simpler:
public static IState<State, Out1> Request1S(this In1 in1) { return from s in Get<State>() let p = s.Handle1(in1) from _ in Put(p.State) select p.Value; }
Since Context
and State
are isomorphic, you can rewrite all callers of Context
to instead use State
, like the above example:
IState<State, (Out1 a, Out1 b)> s = from a in in1.Request1() from b in in1.Request1() select (a, b); var t = s.Run(csa);
Do this consistently, and you can eventually delete the Context
class.
Further possible refactorings #
With the Context
class gone, you're left with the abstract State
class and its implementers:
public abstract class State { public abstract StatePair<State, Out1> Handle1(In1 in1); public abstract StatePair<State, Out2> Handle2(In2 in2); }
One further change worth considering might be to change the abstract base class to an interface.
In this article, I've considered the general case where the State
class supports an arbitrary number of independent state transitions, symbolised by the methods Handle1
and Handle2
. With an arbitrary number of such state transitions, you would have additional methods up to HandleN
for N independent state transitions.
At the other extreme, you may have just a single polymorphic state transition function. My intuition tells me that that's more likely to be the case than one would think at first.
Relationship between pattern and monad #
You can view the State design pattern as a combination of two common practices in object-oriented programming: Mutation and polymorphism.
The patterns in Design Patterns rely heavily on mutation of object state. Most other 'good' object-oriented code tends to do likewise.
Proper object-oriented code also makes good use of polymorphism. Again, refer to Design Patterns or a book like Refactoring for copious examples.
I view the State pattern as the intersection of these two common practices. The problem to solve is this:
"Allow an object to alter its behavior when its internal state changes."
Design Patterns
The State pattern achieves that goal by having an inner polymorphic object (State
) wrapped by an container object (Context
). The State
objects can mutate the Context
, which enables them to replace themselves with other states.
While functional programming also has notions of polymorphism, a pure function can't mutate state. Instead, a pure function must return a new state, leaving the old state unmodified. If there's nothing else to return, you can model such state-changing behaviour as an endomorphism. The article From State tennis to endomorphism gives a quite literal example of that.
Sometimes, however, an object-oriented method does more than one thing: It both mutates state and returns a value. (This, by the way, violates the Command Query Separation principle.) The State monad is the functional way of doing that: Return both the result and the new state.
Essentially, you replace mutation with the State monad.
From a functional perspective, then, we can view the State pattern as the intersection of polymorphism and the State monad.
Examples #
This article is both long and abstract. Some examples might be helpful, so I'll give a few in separate articles:
- Refactoring the TCP State pattern example to pure functions
- Refactoring a saga from the State pattern to the State monad
The first one uses the example from Design Patterns. That example is, unfortunately not that illuminating, since none of the book's methods return data. Thus, the endomorphism-based refactoring is enough, and you don't need the State monad. Therefore, another example is warranted.
Conclusion #
You can view the State design pattern as the intersection of polymorphism and mutation. Both are object-oriented staples. The pattern uses polymorphism to model state, and mutation to change from one polymorphic state to another.
In functional programming pure functions can't mutate state. You can often design around that problem, but if all else fails, the State monad offers a general-purpose alternative to both return a value and change object state. Thus, you can view the functional equivalent of the State pattern as the intersection of polymorphism and the State monad.
Next: Refactoring the TCP State pattern example to pure functions.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK