Статьи

Автоматическая реализация в Java

Этот пост будет посвящен проблеме внедрения машин с конечным состоянием в Java. Если вы не знаете, что такое FSM или где его можно использовать, вы можете прочитать это , это и это .

Если вы когда-либо оказывались в ситуации использования FSM в своем проекте, вы, вероятно, начали писать классы для каждого состояния, в котором реализован один и тот же интерфейс. Хороший дизайн мог бы быть:

1
2
3
4
interface State { }
class State_1 implements State {}
class State_2 implements State {}
...

И у вас, вероятно, был класс, который управлял этими состояниями и переходами между ними, и другой, который реализовывал Контекст FSM (полоса входных полос) и другой интерфейс для начальных состояний и еще один для конечных состояний и так далее. Множество классов разбросано по множеству файлов, что позволяет быстро их потерять.

Есть еще один способ: использование перечислений.

Перечисления по сути представляют собой список классов, и каждый член перечисления может иметь различную реализацию. Предположим, у нас есть следующий конечный автомат, который мы хотим реализовать:

Init — (‘a’) -> A
Init — (остальное) -> Fail
A — (‘b’) -> B
A — (‘c’) -> C
A — (‘a’) -> A
A — (”) -> Конец
A — (остальное) -> Fail
B — (‘c’) -> C
B — (‘b’) -> B
B — (”) -> Конец
B — (остальное) -> Fail
C — (‘c’) -> C
C — (”) -> Конец
C — (остальное) -> Fail

Этот FSM проверит следующее регулярное выражение: ^ (a +) (b *) (c *) $. Мы можем записать состояния как элементы перечисления State следующим образом:

1
2
3
interface State {
    public State next();
}
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Input {
    private String input;
    private int current;
    public Input(String input) {this.input = input;}
    char read() { return input.charAt(current++); }
}
  
enum States implements State {
    Init {
        @Override
        public State next(Input word) {
            switch(word.read()) {
                case 'a': return A;
                default: return Fail;
            }
        }
    },
    A {
        @Override
        public State next(Input word) {
            switch(word.read()) {
                case 'a': return A;
                case 'b': return B;
                case 'c': return C;
                case '': return null;
                default: return Fail;
            }
        }
    },
    B {
        @Override
        public State next(Input word) {
            switch(word.read()) {
                case 'b': return B;
                case 'c': return C;
                case '': return null;
                default: return Fail;
            }
        }
    },
    C {
        @Override
        public State next(Input word) {
            switch(word.read()) {
                case 'c': return C;
                case '': return null;
                default: return Fail;
            }
        }
    },
    Fail {
        @Override
        public State next(Input word) {
               return Fail;
        }
    };
  
    public abstract State next(Input word);
}

То, что мы сделали, мы определили переходы каждого состояния внутри каждого перечисления. Каждый переход возвращает новое состояние, и поэтому мы можем циклически проходить через них:

1
2
3
4
5
6
State s;
Input in = new Input("aabbbc");
for(s = States.Init; s != null || s != States.Fail; s = s.next(in)) {}
  
if(s == null) {System.out.printlin("Valid!");}
else {System.out.println("Failed");}

На данный момент мы либо проверили строку, либо не удалось. Это простой и элегантный дизайн.

Мы могли бы дополнительно улучшить реализацию, отделив конечные состояния от основных, чтобы упростить условие выхода из обхода. Мы определим другой интерфейс с именем FinalState и второе перечисление, которое будет содержать желаемые состояния выхода (соответственно изменяя перечисление States):

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
interface FinalState extends State {}
enum FinalStates implements FinalState {
    Fail {
        @Override
        public State next(Input word) {
               return Fail;
        }
    },
    Ok {
        @Override
        public State next(Input word) {
               return End;
        }
    }
}

Таким образом, обход будет несколько упрощен:

1
2
3
4
5
6
for(s = States.Init; !(s instanceof FinalState); s = s.next(in)) {}
switch(s) {
    case Fail: System.out.printlin("Failed"); break;
    case Ok: System.out.println("Valid!"); break;
    default: System.out.println("Undefined"); break;
}

Преимущество состоит в том, что (кроме более простого обхода) мы можем указать более двух конечных состояний. В большинстве случаев FSM будет иметь более одной точки выхода, поэтому это последнее улучшение рекомендуется на длительный срок. Вы также можете поместить все эти перечисления и интерфейсы в один и тот же исходный файл и располагать всю логику в одном месте, а не просматривать несколько вкладок, чтобы понять, как работает поток.

В заключение, использование перечислений делает более компактную и содержательную реализацию FSM. У вас есть вся логика в одном файле, и все обходы безболезненны. У вас также будет гораздо более простой опыт отладки, так как имена состояний, в которые вы перевели, будут отображаться в отладчике (переменная s изменит свое значение соответствующим образом, имея имя нового состояния), скорее всего придется выяснить в какой класс вы только что прыгнули. В общем, я думаю, что это хорошая техника, чтобы иметь в виду.

Ссылка: Автоматизация реализации на Java от нашего партнера JCG Аттилы-Михали Балаза в блоге JUG в Трансильвании .