CODEWITHSUNDEEP
c#design-patternsstate-machinestate-pattern
Dai
Dai

Reputation: 155578

How can I perform a cyclic state transition when using discriminated-unions's Match to represent state transitions in C#?

I'm experimenting with using discriminated unions in C# (specifically, using the excellent OneOf library) as means of representing and performing state transitions, taking advantage of compiler-enforced type-safety and OneOf's Match method.

This works fine for directed acyclic state transition graphs, like so:

State transition graph:

A -> B -> C1 -> D1 -> E
             -> D2
       -> C2 -> D3

State types

// state-specific constructors, fields and methods removed for brevity:

class A {
    public B Next();
}
class B {
    public OneOf<C1,C2> Next();
}
class C1 {
    public OneOf<D1,D2> Next();
}
class C2 {
    public D3 Next();
}
class D1 {
    public E Next();
}
class D2 {
    public E Next();
}
class D3 {
    public E Next();
}
class E {
    // Terminal state
}

Example state machine function:

public E Run( A initialState )
{
    A a = initialState;
    B b = a.Next();
    return b.Next().Match(
        ( C1 c1 ) =>
        {
            return c1.Match(
                d1 => d1.Next(),
                d2 => d2.Next()
            )
        },
        ( C2 c2 ) =>
        {
            D3 d3 = c2.Next();
            return d3.Next();
        }
    );
}

// or, more succinctly:

public E Run( A initialState )
{
    return initialState
        .Next()                  // A -> B
        .Next()                  // B -> C1 | C2
        .Match(
            c1 => c1.Match(      // C1 -> D1 | D2
                d1 => d1.Next(), // D1 -> E
                d2 => d2.Next()  // D2 -> E
            ),
            c2 => c2
                .Next()          // C2 -> D3
                .Next()          // D3 -> E
        );
}

The use of .Match() means the compiler requires the program to explicitly and exhaustively handle all possible types of values without also needing to rely on inheritance/polymorphism (as with the original State pattern).

But there's some problems:

State transition graph:

Consider this state transition graph that shows cycles (represented by duplicate node names - I'm not good at ASCII art), like so:

A -> B -> C1 -> D -> E
             -> A
       -> C2 -> B

And these state types:

class A {
    public B Next();
}
class B {
    public OneOf<C1,C2> Next();
}
class C1 {
    public OneOf<D,A> Next();
}
class C2 {
    public B Next();
}
class D {
    public E Next();
}
class E {
    // Terminal state
}

...and if I used same-scope if statements with OneOf.TryPick instead of OneOf.Match (which means we lose compiler-enforced exhaustive checks) and have to use goto (the horror):

public E Run( A initialState )
{
    A a;
stateA:
    a = initialState;
stateB:
    B b;
    b = a.Next();
    OneOf<C1,C2> bNext = b.Next();
    if( bNext.TryPickT0( out C1 c1, out _ ) )
    {
        OneOf<D,A> c1Next = c1.Next();
        if( c1Next.TryPickT0( out D d, out _ ) )
        {
            return d.Next();
        }
        else if( c1Next.TryPickT1( out a, out _ ) )
        {
            goto stateA;
        }
        else
        {
            throw new InvalidOperationException();
        }
    }
    else if( b.Next.TryPickT1( out C2 c2, out _ ) )
    {
        b = c2.Next();
        goto stateB;
    } 
    else
    {
        throw new InvalidOperationException();
    }
}

This is just ugly - from the use of goto to the necessary else { throw parts to prevent the compiler complaining about possible returns - but it has the (only) advantage of keeping program flow entirely within the Run function to avoid mutating object instance state (as opposed to only mutating in-scoped locals, making it inherently thread-safe) - this also has advantages in async code as the object that represents the async state-machine is kept simpler.

There exists an alternative by using switch with an enum type (which is bad, because I don't want to have to maintain an enum to represent the state classes I already defined) - or C# 7.0 pattern-matching switch (at the cost of requiring to downcast to Object and use runtime type information for the switch to work and the fact the compiler won't verify the switch is exhaustive, so new states could be added by another programmer and the code below would still compile (because the Match calls were replaced with Value because the Match's per-member lambdas would just return the state value):

public E Run( A initialState )
{
    Object state = initialState;
    while( true )
    {
        switch( state )
        {
        case A a:
            state = a.Next();
            break;
        case B b:
            state = b.Next().Value;
            break;
        case C1 c1:
            state = c1.Next().Value;
            break;
        case C2 c2:
            state = c2.Next().Value;
            break;
        case D d:
            state = d.Next().Value;
            break;
        case E e:
            return e;
        default:
            throw new InvalidOperationException( "Unknown state: " + state?.ToString() ?? "null" );
        }
    }
}

So - is there a way to logically jump between states without needing to satisfy the compiler with exceptions, default and else cases?

Upvotes: 2

Views: 299

Answers (1)

Dai
Dai

Reputation: 155578

While it's true that a state-machine can be modeled by the state of an imperative function, the result is code that is painful to read, and can be generalized by the switch( state ) pattern exemplified in my initial post's final code sample.

I realized that the solution is to use AnyOf to also represent the present state, using its Match method to handle entering a specific state regardless of the previous state - and any specific state transitions can be handled when they happen in a type-safe manner.

So using the same example of a cyclic state machine from above:

Graph:

A -> B -> C1 -> D -> E
             -> A
       -> C2 -> B

Types:

class A {
    public B Next();
}
class B {
    public OneOf<C1,C2> Next();
}
class C1 {
    public OneOf<D,A> Next();
}
class C2 {
    public B Next();
}
class D {
    public E Next();
}
class E {
    // Terminal state
}

Can be safely implemented as:

using AnyState = OneOf<A,B,C1,C2,D,E>; // for brevity

public E Run( A initialState )
{
    AnyState state = initialState;
    E terminal = null;
    while( terminal == null ) )
    {
        state = state.Match(
            a  => AnyState.FromT0( a .Next() ), // B
            b  => b.Next().Match(
                    c1 => AnyState.FromT2( c1 ),
                    c2 => AnyState.FromT3( c2 )
                )
            }
            c1 => c1.Next().Match(
                    d => AnyState.FromT4( d ),
                    a => AnyState.FromT1( a )
                )
            }
            c2 => AnyState.FromT2( c2.Next() ), // B
            d  => AnyState.FromT4( d .Next() ), // E
            e  => AnyState.FromT5( terminal = e  )
        );
    }
}

Taking further advantage of OneOf's implicit operator, this can be simplified to:

using AnyState = OneOf<A,B,C1,C2,D,E>; // for brevity

public E Run( A initialState )
{
    AnyState state = initialState;
    while( !( state.IsT5 ) ) )
    {
        state = state.Match<AnyState>(
            a  => a .Next(),    // B
            b  => b .Next()     // C1 | C2
                .Match<AnyState>(
                    c1 => c1,
                    c2 => c2
                ),    
            c1 => c1.Next()      // D | A
                .Match<AnyState>(
                    d => d,
                    a => a
                )
            c2 => c2.Next(), // B
            d  => d .Next(), // E
            e  => e
        );
    }
}

And we can replace the magic IsT5 with an extension method to indicate terminal state, provided the last element of OneOf is used for terminal states:

static Boolean IsTerminal<T0,T1,T2,T3,T4,T5>( this OneOf<T0,T1,T2,T3,T4,T5> state )
{
    return state.IsT5;
}

Giving:

using AnyState = OneOf<A,B,C1,C2,D,E>; // for brevity

public E Run( A initialState )
{
    AnyState state = initialState;
    while( !state.IsTerminal() ) ) )
    {
        state = state.Match<AnyState>(
            a  => a .Next(),    // B
            b  => b .Next()     // C1 | C2
                .Match<AnyState>(
                    c1 => c1,
                    c2 => c2
                ),    
            c1 => c1.Next()    // D | A
                .Match<AnyState>(
                    d => d,
                    a => e
                )
            c2 => c2.Next(), // B
            d  => d .Next(), // E
            e  => e
        );
    }
}

And this can probably be packed-up as a universal state-machine extension on-top of OneOf.

Upvotes: 1

Related Questions