Конечные автоматы. Пишем ДКА

[Kolonist]

А есть ли смысл городить огород, если автомат реализуется минимумом синтаксических конструкций при помощи элементарных while-switch или даже while-if?

q = q0; //начальное состояние
while (q != qe) { //пока текущее состояние q не равно конечному состоянию qe
    switch(q) {
        case q0:
            //что-нибудь делаем, если надо - меняем q на какое-нибудь q1 или q2, или qe
        break;

        case q1:
            //что-нибудь делаем
        break;

        case q2:
            //что-нибудь делаем
        break;
    }
}

[divanikus]

Чем больше состояний, тем больше будет уровней вложенности. Будет ооочень глубокая лесенка.

[NYM]

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

[igudym]

Это почему это? Уровней вложенностей будет ровно два: внешний свитч по входному символу, и внутренние свитчи по состоянию автомата (можно наоборот).
По виду это почти не отличается от приведенной в статье таблицы переходов.

[divanikus]

Предлагаю не быть голословным, а написать и показать нам рабочий пример.

[igudym]

Запросто, на питоне. Фактически это таже таблица переходов. Только без излишних сложностей в ее интерпретации, да и работать будет раза в два быстрее.

state = 'INIT'
while state != 'QUIT':
    symbol = read_input()
    if state == 'INIT':
        if symbol == '*':
            doIntroduce()
            state = 'INIT'
        elif symbol == 'LOGIN':
            doLogin()
            state = 'SESSION'
        elif symbol == 'EXIT':
            doQuit()
            state = 'QUIT'
    elif state == 'STORE':
        if symbol == '*':
            doRemember()
            state = 'STORE'
        elif symbol == 'EXIT':
            state = 'SESSION'
    elif state == 'SESSION':
        if symbol == 'SAY':
            doSay()
            state = 'SESSION'
        elif symbol == '*':
            state = 'SESSION'
    elif state == 'MEMORIZE':
        state = 'STORE'
    elif state == 'EXIT':
        state = 'INIT'

[divanikus]

Ну пожалуй соглашусь, ДКА действительно можно так изобразить из-за его довольно простой природы. Только наверное не в while надо засовывать, а в некий метод. Плюс таким образом мы теряем возможность менять конфигурацию автомата в рантайме, например, подгружая список состояний из файла и т.п.

Кстати, последние два elif должны быть над символами и внутри SESSION.

[dlancer]

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

[av0000]

Рискну нарваться, но «всё хорошо, вот если бы ещё не перл»!

А если серьёзно, особенно учитывая теги, хотелось бы каких-то картинок или сильно упрощённого псевдо-кода для демонстрации алгоритма. Ибо продираться сквозь, например, "$self->{STATES}->{$state}->{$symbol}->{ACTION}" несколько утомительно ;) То есть, (заранее) зная, как оно должно работать, вникнуть можно, а вот разобраться «с нуля» — тяжко

Мне несколько проще — я перл просто лет 7 как забыл, а тем, кто его вообще не видел?

[HomoLuden]

Мне тоже показалось сложным читать этот код. Вот было б на Ruby написали, как в Clever Algorithms, стало б совсем замечательно.
Спасибо автору за «normalize» — помогло переосмыслить и понять куда дальще двигаться.

[divanikus]

У меня к сожалению опыта на руби нет, но ради такого дела можно попробовать, например, в следующей статье. Или еще на каком языке :)

[1x1]

Для вас будет больше пользы доработать этот код. Минимальные изменения сильно упростят его понимание, а привычка писать читабельный код поможет и с другими языками.

[divanikus]

Ну я даже не знаю, приведите пример что ли.

[1x1]

my $current_state = $self->{STATES}->{$state};

[divanikus]

Лично мне кажется, что в процедуре на 5 строчек это уже совсем детский сад получается. Хотя если народ просит, могу и сделать.

[1x1]

Не важно количество строк.
— Если что-то [неизменное] вычисляется более одного раза, создавайте переменную.
— Если что-то сложнее 2+2 используется в разных местах — выносите в функцию/метод.
— Если что-то многократно повторяется и можно обойтись без этого — переделывайте.

Ну и, разумеется: если для чего-то уже сделан метод, то использовать его, а не повторять тот же код.

[divanikus]

Мне известны эти правила и я ими стараюсь всегда пользоваться. Но в то же время не стоит излишне плодить сущностей.

[rumkin]

Короче, пишите на псевдокоде с динамической типизацией, но без замыканий и лямбд )))))

А, если серьезно, когда важнее алгоритм, а не готовый код, я рисую схему а-ля UML: наглядно, абстрактно и к коду не дое**ться )

[rumkin]

P.S. Спасибо за интересную статью. Код не разобрал, но принцип понял! В общем респект и прочие почести.

[divanikus]

А тем временем, добавил в статью более подробное описание алгоритма работы, а также чуть более глубокое освещение работы примера :)