Как я могу выполнить циклический переход состояния при использовании Match дискриминируемых союзов для представления переходов состояний в C #? - PullRequest
Новая
       39

Как я могу выполнить циклический переход состояния при использовании Match дискриминируемых союзов для представления переходов состояний в C #?

2 голосов
/ 18 октября 2019

Я экспериментирую с использованием различающихся объединений в C # (в частности, с использованием превосходной библиотеки OneOf ) в качестве средства представления и выполнения переходов состояний, используя преимущества безопасности типов и *, обеспечиваемые компилятором. Метод 1004 * * 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() означает, что компилятор требует, чтобы программа явно и исчерпывающе обрабатывала все возможные типы значений без необходимости полагаться нанаследование / полиморфизм (как с исходным шаблоном State).

Но есть некоторые проблемы:

  • Это фактически строгая древовидная структура, направленная только вперед, даже если граф конечного автоматасходится к линейному переходу состояний в конце, поэтому, если одно состояние может быть введено из множества других предыдущих состояний (например, из D1, D2 и D3 до E), затем код для ввода в состояние E повторяется 3 раза (как видно с d1.Next(), d2.Next() и d3.Next() call-сайтов.
  • Этот подход не работает для циклических графов переходов состояний, и большинство конечных автоматов имеют тенденцию быть циклическими.

граф переходов состояний:

Учтите этографик перехода состояний, который показывает циклы (представленные дублированными именами узлов - я плохо разбираюсь в искусстве 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 частей, чтобы компилятор не жаловался на возможные возвраты - но у него есть (единственное) преимущество, заключающееся в том, что поток программы полностью находится в пределах Runфункция, позволяющая избежать изменения состояния экземпляра объекта (в отличие только от muиспользование локальных локальных областей, что делает его по сути потокобезопасным - это также имеет преимущества в коде async, поскольку объект, представляющий конечный автомат async, упрощается.

Существует альтернативаиспользование switch с типом enum (что плохо, потому что я не хочу поддерживать enum для представления классов состояний, которые я уже определил) - или C # 7.0 сопоставление с шаблоном switch (за счето необходимости понизить значение до Object и использовать информацию о типе времени выполнения для работы switch, а также тот факт, что компилятор не будет проверять, что переключение является исчерпывающим, поэтому новый программист может добавить новые состояния, и приведенный ниже код все равно будет компилироваться(потому что вызовы Match были заменены на Value, потому что лямбды Match для каждого члена просто возвращали бы значение состояния): 

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 случаев?

1 Ответ

1 голос
/ 19 октября 2019

Хотя верно, что конечный автомат может моделироваться состоянием императивной функции, в результате получается код, который больно читать, и который можно обобщить с помощью шаблона switch( state ), приведенного в качестве примера вФинальный пример кода моего исходного сообщения.

Я понял, что решение состоит в том, чтобы использовать 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.

...