Делать Алгоритмы Маркова — это весело

    Писать Нормальные Алгоритмы Маркова, это безумно интересно и забавно. Интересно ли узнать о том, как мы делали лучшую в мире IDE для Нормальных Алгоритмов Маркова?





    Кому в голову может прийти писать IDE для языка, на котором не написана ни одна коммерческая программа? И нам такая мысль бы не пришла. Но было задание в университете сделать проект — интерпретатор.

    Если делать, то сразу лучше всех. Нужно сначала посмотреть, что уже сделали другие. Ничего особо интересного мы не нашли, поэтому очень бегло составили список что должно быть в IDE 21 века:

    • Подсветка кода
    • Подсказки ошибок
    • Комментарии к коду
    • Отладчик
    • Точки остановки


    Было решено сделать все. Писать решили на C++ на Qt. Там GUI без проблем и сигналы-слоты есть. (Потом оказалось, что их можно использовать и без Qt, но это совсем другая история).

    Нарисовали маленькую схемку классов




    Придумали киллер-фичи

    • История запусков — сохраняются все входные слова, для удобного перезапуска. + история хранится также и в самом файле, поэтому она не потеряется при переносе с одного компьютера на другой.
    • Пошаговый отладчик. Если поставить точку остановки на любом правиле, то интерпретация остановится, во время выполнения правила, а также покажет, как правило было использовано. После остановки можно продолжить исполнения до следующей точки остановки или начать исполнение пошагово.




    • Редактирование кода не лету — во время отладки можно менять код, который сразу начнет использовать интерпретатор. А также все ошибки и подсказки по их решения появляются сразу при вводе кода.
    • Два режима запуска. Быстрый режим — сразу выдает результат, отладочный режим выводит также лог все правил и подстановок, которые были сделаны.
    • Предотвращения зацикливаний и программ, которые никогда не завершатся.
    • Поддержка дополнительной возможности указать алфавит символов, доступных для написания правил и алфавит символов доступных как входные данные.


    Дальше была написана документация всех классов, нарисованы заготовки интерфейса, и началась самая быстрая фаза разработки — кодинг.



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

    Во время первого пилотирования было сделано более 10 улучшений. Самая интересная из них это поддержка «палочек». Как оказалось в Нормальных Алгоритмах Маркова числа удобней всего представлять в виде палочек: ||| = 3, |||| = 4. Для того, чтобы не было необходимости считать их каждый раз мы добавили маленькие цифры, которые это делают за вас.



    Интересные решения

    Во время разработки мы придумали некоторые интересные решения. Некоторые из них:

    • Нам удалось сделать офлайн документацию в браузере, которая автоматически переходит на ее онлайн версию (которая может обновляться в отличии от офлайн), если у человека есть подключение к интернету. Сделали очень просто — подключили javascript файл, который лежит на сервере и делает редирект на онлайн версию. Нет интернета, нет файла, нет перехода — открывается офлайн документация.
    • Удобная портативная версия, которая автоматически после запуска делает ассоциацию с .yad файлом, после чего ни чем не отличается от установленной через инсталятор.


    Результаты

    На проект было потрачено 10 дней, 4 чтобы придумать и написать документацию, 3 чтобы запрограммировать и еще 2 дня на улучшения, документация, сайт.

    Теперь все желающие могут скачать без регистрации и СМС с GitHub (пока только для Windows), а также все кто захочет так же сможет собрать из исходников.

    Проект мы сделали втроем: dianasi, yuragri и я.

    Вместо заключения

    Статья про Алгоритмы Маркова без алгоритмов это не серьёзно, вот маленькая программа, которая конвертирует двоичные числа в десятичную систему («палочки»).

    //Alphabet
    T = {|, 0, 1}
    I = {0, 1}
    
    //Rules
    |0 -> 0||
    1->0|
    0->$
    


    P.S. а преподавателю проект не понравился, потому что тут не было базы данных, но это тоже другая история.

    Я не уверен, нарушает ли статья правила хабра, про рекламу. Если да, то прошу сообщить или передвинуть в Я пиарюсь.
    Я хочу иметь установочный пакет для

    Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

    Метки:
    Поделиться публикацией
    Комментарии 37
    • +4
      А какой вуз, если не секрет? Порекомендую своему научному руководителю из МАИ, который рассказывает про НАМ на 1-ом курсе в курсе информатики.
      • +14
        Не секрет, Национальный Университет «Киево-Могилянская Академия».
        • +2
          Авдошин, думаю, тоже будет рад.
          • 0
            лучше посоветовать им всем не тратить время зря и не забивать головы бедных студентов ненужной ерундой
            • +1
              Разве конечные автоматы — ненужная ерунда?
              • 0
                на 1-м курсе да с чёрточками? это другое: НАМ
                • 0
                  Эм… Конечные автоматы на то и конечные, что принимают конечное число состояний. Алгорифмы Маркова — это тьюринг-полный язык описания алгоритмов.
            • +4
              Оригинальная идея, молодцы, что совместили полезное с приятным, глядишь и пригодится кому.

              В чем рисовали схему классов?
              Интерфейс кастомизирован через стили, или Qt из коробки так в восьмерке теперь выглядит?
              • +4
                Рисовали в gliffy.com, жаль оказался платным, нам триала на 30 дней хватило. Дизайн через стили QSS.
                • +1
                  Класс, знаю Qt довольно хорошо, но до QSS дела особо не было, даже не знал его возможности, благодаря Вам ознакомился бегло и в очередной раз удивился, что может этот замечательный фреймворк.

                  И продолжая серию вопросов предыдущего оратора — а как подсветку синтаксиса организовали? Потребовался ли семантический анализ или обошлось регулярками?

                  P.S. Если кому-то еще интересно про QSS, то вот QSS
            • +1
              «Предотвращения зацикливаний и программ, которые никогда не завершатся.»

              Аналитически?
              • +1
                Если на некотором шаге строка стала такой же как и на некотором шаге раньше значит программа зациклилась. Если строка становится слишком длинной, то интерпритация останавливается.
                • +2
                  А я понадеялся, что вы как-то решили Проблему Остановки отдельно взятом интерпретаторе.
                  • +4
                    Зря надеялись. Алгоритмы Маркова тьюринг-полны.
                • 0
                  Не многие оценят юмор :)
                • +5
                  Небольшой коммит чтобы собиралось на линуксах: http://bpaste.net/raw/261037/ .
                  Если что, это в гит можно залить сразу с помощью git am patch_file_name.
                  • 0
                    Добавил коммит.
                    • +1
                      Собирается на linux отлично, не хватает какого-нибудь интересного примера для copy/paste и регулировки размера шрифта :)
                  • 0
                    наконец-то еще кого-нибудь, кроме меня, клемонуло на алгоритмы Маркова
                    • +7
                      Не «ubuntu», а «debian». Потому что ubuntu (пока что?) полностью верна debin'вскому репозиторию.
                      • 0
                        Как это она верна денбиановской репе, если у них даже init разный?
                        • 0
                          За вычетом инита. Кстати, после голосования дебиана о присоединении крыма использовании systemd, Шатлворт сказал, что бубунта тоже на systemd переходить будет.
                          • 0
                            По полю Original-Maintainer: 'ubuntu.com' 728 из 85142 пакетов
                      • –1
                        свой вариант — javascript. поиграться в браузере — самое то
                        • +1
                          Вы — молодцы, проект просто великолепный! Тоже когда-то будучи студентом писал интерпретатор НА. Но это было в 19-м веке, под DOS и на Паскале. Результат — трассировка выполнения писалась в файл в формате HTML с указанием правила и выделением изменившихся подстрок. Этот файл можно было распечатать и приложить в качестве ответа на домашнюю работу по теории алгоритмов. Да, в консоли тоже все выводилось с подсветкой.
                          • +4
                            на случай если это была не шутка
                            Может все таки в 20 веке? :)
                            • +2
                              Всё нормально, это был DOS под машину Бэббиджа.
                              • +1
                                Disk Operating System, на перфорированных дисках для музыкальных шкатулок.
                          • +1
                            А я когда-то делал ДЗ по НАМ на языке РЕФАЛ. Очень удобно.
                            Потом еще с другом соревновались, у кого получится программа короче. Например, для возведения a в степень b.
                            • +2
                              Молодцы! Особенно плюсую мысль о том, что из любой унылой курсовой можно сделать себе challenge и самостоятельно поэкспериментировать с интересными технологиями.
                              • +1
                                Это была не курсовая, а просто лабораторная для одного из предметов.
                                • +1
                                  Тем более! :)
                              • 0
                                Когда-то давно я делал аналогичную штуковину для машины Поста: post-machine.appspot.com/ide

                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.