在 C# 中使用 discriminated-union 的 Match 表示状态转换时，如何执行循环状态转换？

Question

我正在尝试在 C# 中使用区分联合（具体来说，using the excellent OneOf library）作为表示和执行状态转换的手段，利用编译器强制类型安全和 OneOf Match 方法。

这适用于有向非循环状态转换图，如下所示：

状态转换图：

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

州类型

// 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
}

示例状态机函数：

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
        );
}

.Match() 的使用意味着编译器要求程序明确且详尽地处理所有可能的值类型，而不需要依赖 inheritance/polymorphism（与原始状态模式一样）。

但是有一些问题:

这实际上是一个严格的只向前的有向树结构，即使状态机图最后收敛到线性状态转换，所以如果一个状态可以从多个其他先前状态进入（例如从 D1、D2 和 D3 到 E) 然后进入状态 E 的代码重复 3 次（如 d1.Next()、d2.Next()，和 d3.Next() 个调用站点。
这种方法不适用于循环状态转换图，并且大多数状态机往往是循环的。

状态转换图：

考虑这个显示循环的状态转换图（由重复的节点名称表示 - 我不擅长 ASCII 艺术），如下所示：

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

这些状态类型：

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
}

...如果我使用相同范围的 if 语句和 OneOf.TryPick 而不是 OneOf.Match （这意味着我们失去了编译器强制的详尽检查）并且必须使用 goto（恐怖）：

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();
    }
}

这只是丑陋的 - 从使用 goto 到必要的 else { throw 部分来防止编译器抱怨可能的 returns - 但它有（唯一的）优势将程序流完全保持在 Run 函数内以避免改变对象实例状态（而不是只改变范围内的局部变量，使其本质上是线程安全的）——这在 async 代码中也有优势表示 async 状态机的对象保持简单。

存在一种替代方法，即使用 switch 和枚举类型（这很糟糕，因为我不想维护 enum 来表示状态类我已经定义了） - 或 C# 7.0 模式匹配 switch（代价是需要向下转换为 Object 并使用运行时类型信息来让 switch 工作，事实上编译器赢了' 验证开关是否详尽无遗，因此其他程序员可以添加新状态并且下面的代码仍然可以编译（因为 Match 调用被替换为 Value 因为 Match 的每个成员 lambda 只会return 状态值):

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" );
        }
    }
}

那么 - 有没有一种方法可以逻辑地在状态之间跳转而无需满足编译器的例外情况，default 和 else 情况？

Answer 1

虽然状态机 确实可以 由命令式函数的状态建模，但结果是代码难以阅读，并且可以通过switch( state ) 模式在我最初 post 的最终代码示例中举例说明。

我意识到解决方案是使用 AnyOf 来表示当前状态，使用它的 Match 方法来处理进入特定状态而不管之前的状态 - 以及任何特定的状态转换当它们以类型安全的方式发生时可以被处理。

所以使用上面循环状态机的相同示例：

图表：

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

类型：

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
}

可以安全地实现为：

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  )
        );
    }
}

进一步利用 OneOf 的 implicit 运算符，这可以简化为：

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
        );
    }
}

并且我们可以用扩展方法替换 magic IsT5 来指示终端状态，前提是 OneOf 的最后一个元素用于终端状态:

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

给予：

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
        );
    }
}

这可能会打包为 OneOf 之上的通用状态机扩展。

在 C# 中使用 discriminated-union 的 Match 表示状态转换时，如何执行循环状态转换？

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

c#

design-patterns

state-machine

state-pattern

状态转换图：

州类型

示例状态机函数：

状态转换图：