Final State Mashine - Конечный автомат и его реализация на Java

1410

January 12, 2018

Final State Machine - конечный автомат

1. Понятие Конечный автомат

Конечный автомат (машина состояний, state mashine) - это компьютерная программа, которая имеет характерные черты:

  1. В основе лежит модель поведения
  2. Модель поведения имеет несколько последовательных состояний
  3. Состояния связаны между собой в виде цепочки переходов, которая может иметь линейную или ветвистую структуру (обычно представляют в виде графов)
  4. Переходы между состояниями порождают действия
  5. Цепочка состояний имеет одно начальное состояние, ветвление осуществляется за счет условий переходов
  6. Условия переходов должны быть описаны таким образом, чтобы из каждого конкретного состояния модель имела лишь одно следующее состояние

Конечные автоматы обычно используются для организации и представления потока выполнения чего-либо. Это полезно при реализации ИИ в играх или ботов в чатах.

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

2. Самый простой конечный автомат

В самом простом виде конечный автомат может быть представлен в виде обычного переключателя: два положения-состояния (включен/выключен), два направления перехода (вкл->выкл, выкл->вкл).

Два состояния: Включено и Выключено.

Два перехода:

  1. от Включено к Выключено
  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-боте. Примеры можно посмотреть тут:

  1. Диалог проведения викторины
  2. Диалог калькулятора

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 библиотек. Из тех, что мне удалось найти, это были:

  1. Spring StateMashine - Enum-based, все состояния являются перечислением
  2. JState - Enum-based, все состояния являются перечислением
  3. StatefulJ - String-based, состояния определяются строками

Но мне они показались сложно конфигурируемыми, а документация по ним не достаточна для быстрого понимания.