Как я могу выполнить циклический переход между состояниями при использовании Match discinated-unions для представления переходов состояний в C#?
Я экспериментирую с использованием дискриминируемых объединений в C# (в частности, используя отличныеOneOfбиблиотека) в качестве средства представления и выполнения переходов между состояниями, используя преимущества безопасности типов, обеспечиваемые компилятором, и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() означает, что компилятор требует, чтобы программа явно и исчерпывающе обрабатывала все возможные типы значений, не полагаясь при этом на наследование / полиморфизм (как с исходным шаблоном состояния).
Но есть проблемы:
- По сути, это строгая древовидная структура, ориентированная только вперед, даже если граф конечного автомата сходится к линейному переходу состояний в конце, поэтому, если одно состояние может быть введено из нескольких других предыдущих состояний (например, из
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 частей, чтобы компилятор не жаловался на возможные возвраты, но у него есть (единственное) преимущество в том, что выполнение программы полностью находится в пределах Run функция, чтобы избежать изменения состояния экземпляра объекта (в отличие от изменения только локальных переменных в области видимости, что делает его по своей сути потокобезопасным) - это также имеет преимущества в async код как объект, представляющий async конечный автомат остается проще.
Существует альтернатива с использованием switch с типом перечисления (что плохо, потому что я не хочу поддерживать 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 ответ
Хотя верно, что конечный автомат может быть смоделирован состоянием императивной функции, в результате получается код, который трудно читать и который можно обобщить с помощью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
);
}
}
И мы можем заменить волшебство 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.