Final State Machine - конечный автомат
1. Понятие Конечный автомат
Конечный автомат (машина состояний, state mashine) - это компьютерная программа, которая имеет характерные черты:
- В основе лежит модель поведения
- Модель поведения имеет несколько последовательных состояний
- Состояния связаны между собой в виде цепочки переходов, которая может иметь линейную или ветвистую структуру (обычно представляют в виде графов)
- Переходы между состояниями порождают действия
- Цепочка состояний имеет одно начальное состояние, ветвление осуществляется за счет условий переходов
- Условия переходов должны быть описаны таким образом, чтобы из каждого конкретного состояния модель имела лишь одно следующее состояние
Конечные автоматы обычно используются для организации и представления потока выполнения чего-либо. Это полезно при реализации ИИ в играх или ботов в чатах.
Конечный автомат можно представить в виде графа, вершины которого являются состояниями, а ребра - переходы между ними. Каждое ребро имеет метку (условие) - информацию о том, когда должен произойти переход.
2. Самый простой конечный автомат
В самом простом виде конечный автомат может быть представлен в виде обычного переключателя: два положения-состояния (включен/выключен), два направления перехода (вкл->выкл, выкл->вкл).
Два состояния: Включено и Выключено.
Два перехода:
- от Включено к Выключено
- от Выключено к Включено
Данный конечный автомат линеен, переходы не содержат условий.
Его реализацию в Java можно предствить в виде:
class Switcher {
public Boolean state = false; //true - is on, false - is off
public void next() {
if (this.state) {
this.state = false;
} else {
this.state = true;
}
}
}
3. Полнофункциональный конечный автомат
Представленный выше пример конечного автомата не отвечает требованиям: он не может ветвиться, программа не может реагировать на изменения состояния конечного автомата.
Для того, чтобы управлять поведением программы и вести ход ее выполнения по заранее заданному "лабирину" состояний, я написал библиотеку Simple FSM.
Ее я использовал для алгоритма диалогов в IRC-боте. Примеры можно посмотреть тут:
4. Работа с Simple FSM
В качестве примера возьму диалог калькулятора. Для расчетов будет использоваться библиотека Exp4J.
4.1. Краткий функционал библиотеки Ext4J
Эта библиотека позволяет вычислять выражения, заданные строкой. Поддерживаются выражения с переменными.
Expression e = new ExpressionBuilder("3 * sin(y) - 2 / (x - 2)") // инициализация выражения
.variables("x", "y") // говорим, что является переменной - их нужно будет задать
.build() // разбираем выражение
.setVariable("x", 2.3) // указываем переменную x
.setVariable("y", 3.14); // указываем переменную y
double result = e.evaluate(); // вычисляем выражение и получаем результат
Из примера видно, какие команды нужно выполнить последовательно, чтобы вычислить выражение.
Именно эти команды и должен будет вводить пользователь, чтобы наш бот посчитал и выдал результат.
4.1. Подготовка, инициализация
Нарисуем дерево диалога.
Для использования библиотеки нужно подключить ее в проект. Если не используется ни одна система сборки, то можно клонировать репозиторий, собрать и положить jar-файл себе в проект. Для Maven можно подключить мой репозиторий и указать зависимость в файле pom.xml:
<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<repositories>
<repository>
<id>FinalStateMachine-mvn-repo</id>
<url>https://raw.github.com/bvn13/FinalStateMachine/mvn-repo/</url>
<snapshots>
<enabled>true</enabled>
<updatePolicy>always</updatePolicy>
</snapshots>
</repository>
</repositories>
<dependencies>
<!--Calculator-->
<dependency>
<groupId>net.objecthunter</groupId>
<artifactId>exp4j</artifactId>
<version>0.4.8</version>
</dependency>
<!--FSM-->
<dependency>
<groupId>ru.bvn13</groupId>
<artifactId>fsm</artifactId>
<version>1.0</version>
</dependency>
</dependencies>
</project>
Создадим класс, унаследованный от FSM, и проинициализируем состояния диалога и переходы между ними.
public class CalculatorDialog extends FSM {
private String command = "";
private String expression;
private ExpressionBuilder expressionBuilder;
private Expression exp = null;
public CalculatorDialog() throws FSMException {
initState(new State("init") {
});
addTransition("init", new State("entering-vars") {
});
addTransition("entering-vars", new State("setting-vars") {
});
addTransition("setting-vars", "setting-vars");
addTransition("setting-vars", new State("calculating") {
});
}
public void processCommand(String command) {
this.command = command;
if (this.getCurrentState()==null || this.getCurrentState().isFinish()) {
try {
this.init();
} catch (NotInitedException e) {
System.out.println("ERROR: "+e.getMessage());
e.printStackTrace();
}
} else {
try {
this.next();
} catch (FSMException e) {
e.printStackTrace();
}
}
}
}
4.2. Процесс запуска
Для общения нам необходимо, чтобы наш класс-диалог принимал сообщения от пользователя, и выводил результаты.
Будем использовать комадную строку.
public class App {
public static void main( String[] args )
{
CalculatorDialog calc = null;
try {
calc = new CalculatorDialog();
} catch (FSMException e) {
e.printStackTrace();
return;
}
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("ENTER EXPRESSION: ");
while(true) {
String command = "";
try {
command = br.readLine();
} catch (IOException e) {
e.printStackTrace();
return;
}
calc.processCommand(command);
if (calc.getCurrentState().isFinish()) {
return;
}
}
}
}
4.3. Инициализация выражением для вычисления
При состоянии "init" нам необходимо объявить переменные.
initState(new State("init") {
@Override
public void process() {
exp = null;
expression = command;
expressionBuilder = new ExpressionBuilder(expression);
System.out.println("ENTER VARS:");
}
});
4.4. Обозначение переменных
Библиотеке Exp4J необходимо сообщить, что является переменной. Для этого пользователь должен написать все переменные через запятую.
Но этот шаг должен выполняться только в том случае, если выражение содержит переменные. Как это определить? Самый простой способ - попробовать скомпилировать его. Если мы не получим ошибки, то переменных нет, их не надо объявлять. Для этого будем использовать метод:
public class CalculatorDialog extends FSM {
//...
public CalculatorDialog() throws FSMException {
//...
}
public boolean checkCalculatingPossibility() {
try {
exp = expressionBuilder.build();
return true;
} catch (Exception e) {
return false;
}
}
//...
}
Теперь обработчик состояния "entering-vars" будет выглядеть так:
addTransition("init", new State("entering-vars") {
@Override
public void process() {
exp = expressionBuilder.variables(command.trim()).build();
System.out.println("SET UP VARS (variable = value) or empty line for calculating:");
}
}, new Condition() {
@Override
public boolean check() {
return !checkCalculatingPossibility();
}
});
4.5. Процесс объявления переменных
Все переменные объявляются по-одной, в формате variable = value.
addTransition("entering-vars", new State("setting-vars") {
public void process() {
String[] variableData = command.trim().split("=", 2);
if (variableData.length < 2 || variableData[0].isEmpty() || variableData[1].isEmpty()) {
System.out.println("FORMAT: variable = value");
} else {
if (exp == null) {
exp = expressionBuilder.build();
} else {
Double value = Double.parseDouble(variableData[1].trim());
exp = exp.setVariable(variableData[0].trim(), value);
System.out.println(String.format("VARIABLE SET: %s = %f", variableData[0].trim(), value));
}
}
System.out.println("SET UP VARS (variable = value) or empty line for calculating:");
}
});
Но если выражение содержит несколько переменных, нам нужно запускать этот шаг до тех пор, пока все переменные не будут объявлены. Для этого служит переход от "setting-vars" к "setting-vars". Поскольку этот переход является по-сути циклом, нам нужно определить условие для него.
addTransition("setting-vars", "setting-vars", new Condition() {
@Override
public boolean check() {
return !command.trim().isEmpty();
}
});
4.6. Вычисление выражения
Когда все переменные объявлены, можно вычислить выражение. Как мы и обозначили, мы выходим из цикла "setting-vars" -> "setting-vars" в том случае, если пользователь оставит пустую строку вместо очередного объявления переменной.
addTransition("setting-vars", new State("calculating", true) {
@Override
public void process() {
if (exp == null) {
try {
exp = expressionBuilder.build();
} catch (Exception e) {
System.out.println("ERROR: "+e.getMessage());
return;
}
}
try {
Double result = exp.evaluate();
System.out.println(String.format("%s = %f", expression, result));
expressionBuilder = null;
exp = null;
} catch (Exception e) {
System.out.println("ERROR: "+e.getMessage());
}
}
}, new Condition() {
@Override
public boolean check() {
return command.trim().isEmpty();
}
});
4.7. Вычислить выражение сразу, если оно не содержит переменных
Для этого необходимо добавить условный переход от "init" к "calculating".
addTransition("init", "calculating", new Condition() {
@Override
public boolean check() {
return checkCalculatingPossibility();
}
});
5. Полный код диалога
public class CalculatorDialog extends FSM {
//...
public CalculatorDialog() throws FSMException {
initState(new State("init") {
@Override
public void process() {
exp = null;
expression = command;
expressionBuilder = new ExpressionBuilder(expression);
if (checkCalculatingPossibility()) {
try {
next();
} catch (FSMException e) {
e.printStackTrace();
}
} else {
System.out.println("ENTER VARS:");
}
}
});
addTransition("init", new State("entering-vars") {
@Override
public void process() {
exp = expressionBuilder.variables(command.trim()).build();
System.out.println("SET UP VARS (variable = value) or empty line for calculating:");
}
}, new Condition() {
@Override
public boolean check() {
return !checkCalculatingPossibility();
}
});
addTransition("entering-vars", new State("setting-vars") {
public void process() {
String[] variableData = command.trim().split("=", 2);
if (variableData.length < 2 || variableData[0].isEmpty() || variableData[1].isEmpty()) {
System.out.println("FORMAT: variable = value");
} else {
if (exp == null) {
exp = expressionBuilder.build();
} else {
Double value = Double.parseDouble(variableData[1].trim());
exp = exp.setVariable(variableData[0].trim(), value);
System.out.println(String.format("VARIABLE SET: %s = %f", variableData[0].trim(), value));
}
}
System.out.println("SET UP VARS (variable = value) or empty line for calculating:");
}
});
addTransition("setting-vars", "setting-vars", new Condition() {
@Override
public boolean check() {
return !command.trim().isEmpty();
}
});
addTransition("setting-vars", new State("calculating", true) {
@Override
public void process() {
if (exp == null) {
try {
exp = expressionBuilder.build();
} catch (Exception e) {
System.out.println("ERROR: "+e.getMessage());
return;
}
}
try {
Double result = exp.evaluate();
System.out.println(String.format("%s = %f", expression, result));
expressionBuilder = null;
exp = null;
} catch (Exception e) {
System.out.println("ERROR: "+e.getMessage());
}
}
}, new Condition() {
@Override
public boolean check() {
return command.trim().isEmpty();
}
});
addTransition("init", "calculating", new Condition() {
@Override
public boolean check() {
return checkCalculatingPossibility();
}
});
}
public boolean checkCalculatingPossibility() {
try {
exp = expressionBuilder.build();
return true;
} catch (Exception e) {
return false;
}
}
//...
}
5. В заключение
На самом деле, для Java есть несколько уже готовых FSM библиотек. Из тех, что мне удалось найти, это были:
- Spring StateMashine - Enum-based, все состояния являются перечислением
- JState - Enum-based, все состояния являются перечислением
- StatefulJ - String-based, состояния определяются строками
Но мне они показались сложно конфигурируемыми, а документация по ним не достаточна для быстрого понимания.