Комментарии 80
И выкладывать в опенсоурс исходники для СиБилдера6 «с торрентов» это как то за гранью разумного поведения.
Билдер в данном случае нужен для демонстрации работы модуля на ПК, сам модуль никак не завязан на Билдер, и использовался с другими IDE поэтому ваша критика как будто отчасти имеет почву но она немного мимо.
В дальнейшем я планирую давать примеры в Qt но этот пример было быстрее сделать так.
— куча кода, не относящихся к теме статьи (напомню, она про FSA, а не про битовые сдвиги)
— было бы перед изобретением веслосипеда (я сделяль) неплохо ознакомиться с готовыми наработками. Гуглим C++ finite state machine lib
— весь код непосредственно иллюстрирует применение автоматного программирования для проектирования программ, а битовые сдвиги это неотъемлемая часть операционного автомата. И операционный автомат напрямую определяет то, каким будет управляющий автомат. Я верю что вы разбираетесь в автоматах состояний, но субъективно ощущается что знания у вас несколько из другой сферы, попробую объяснить. Судя по комментарию, для вас автомат это только то что непосредственно попадает под формальное определение по запросу C++ finite state machine lib, и до что вы никогда не сталкивались на деление автоматов на операционные и управляющие (может я ошибаюсь, не примите близко к сердцу) и таким образом ваше знание становится камнем преткновения: вы видите то что этот текст не повторяет то что вы привыкли слышать по этому вопросу и это вызывает подсознательную реакцию «что-то не то». Но поймите, автоматы более комплексная сфера знаний чем кажется на первый взгляд. Автоматы могут использоваться в частности для анализа символьных последовательностей и это тоже FSM, но автоматы это также и способ проектирования цифровых логических устройств, и это тоже автоматы, но акцент здесь на другое, и с этой точки зрения автомат это ряд технологических подходов. В статье я рассматриваю автомат именно с этой позиции, т.е. проектирование программного обьекта как цифрового устройства.
С чего я и начал
От практики бесконечно далеко.
Не будем далеко ходить. Вы пишете:
битовые сдвиги это неотъемлемая часть операционного автоматаНо операционный автомат — это логические устройство (алгоритм), а битовый сдвиг — это технический прием формирования выходных данных на аппаратную часть. Соответственно — по теории он относится к управляющему автомату. Путаница как она есть.
Грубо говоря, управляющий автомат в софтвере — это драйвер устройства.
Но операционный автомат — это логические устройство (алгоритм)
всё верно, логическое устройство выполняет ряд преобразований и функция Out_symbol выполняет те же преобразования которые у нас бы делали пара сдвиговых регистров в железе. Причём активно используются самые простые типы операций, и, или сдвиги, целочисленные операции, много однотипных вычислений, что оптимально для запуска на видео
процессорах на сколько я понимаю суть вопроса.
Грубо говоря, управляющий автомат в софтвере — это драйвер устройства.да это верно, вы прекрасно поняли суть. И драйвер много работает именно с битами и байтами, именно на таком уровне как это показано в примере. Микроконтроллер содержит огромное количество готовых встроенных устройств — таймеры цап-ацп, приёмопередатчики, и там такой подход совершенно естественен.
Программирование микроконтроллеров специфическая сфера
Может быть в этом и есть основная проблема? Я честно пытался въехать в статью, но после прочтения, у меня создалось ощущения оторванности теории от показанного примера. Вероятно потому что в пример тяжело въехать из-за специфики. Получается, что абстракция вроде понятна, но за кучей низкоуровневого кода её не видно.
Вначале вы пишите:
Эта статья – попытка взглянуть на программаты глазами прагматика, на примере задачи, взятой из реальной практики программирования микроконтроллеров. Однако она может заинтересовать не только embedderов, поскольку автоматный подход может эффективно использоваться для создания и драйверов и интерактивных приложений в системах основанных на обработке событий, как например Windows.
На мой взгляд, чтобы статья заинтересовала «не только embedderов», нужно как раз показать в качестве примера что-то вроде «интерактивных приложений в системах основанных на обработке событий, как например Windows».
Или же это было сказано «для красного словца», и в реальности, автоматы для прикладных программ неактуальны?
З.Ы. С++ builder 6, goto… Какая же это «новая веха»? В таком виде это даже не миф, а скорее страшилка.
Идиосинкразия к goto развилась из-за того, что этот оператор резко понижает читаемость кода, однако, в случае конечного автомата картина обратная — здесь безусловный переход практически равноценен вызову процедуры с хвостовой оптимизацией.
Вероятно потому что в пример тяжело въехать из-за специфики. Получается, что абстракция вроде понятна, но за кучей низкоуровневого кода её не видно.если описание, диаграммы состояний и чертежи перечислить отдельно а код поместить в конце это будет более понятно, я верно уловил?
Если на АП смотреть с точки зрения теории Тьюринга, то его машина, наглядно подтверждает уникальность АП.Недавно мне на глаза попалась лекция бакалавра сиднейского технологического университета, причем в такой лаконичной подаче, что мне захотелось перевести материал и с удовольствием представить его в тематических сообществах.
К слову, я целиком и полностью разделяю и даже частично цитирую Ваш текст в своих материалах относительно причин слабой популяризации.
проведём обзор преимуществ автоматного подхода
По-моему, это должно было быть в начале первой статьи, а не в конце второй. А то на протяжении чтения неизменно сопровождает мысль «ну и зачем всё это?»
А почему для реализации был выбран древний C++ Builder 6, а не свежий C++ Builder 10 Starter Edition Free?
При наличии ресурсов, значительно более понятное решение можно построить в два шага:
— преобразовать входную строку в структуру данных, описывающую, что и куда рисовать
— передать эту структуру данных в рендер, который занимается отрисовкой
Дополнительный уровень абстракции (FSM/FSA-либы, ну или просто переменные кодирующие состояния) нужен только в случае асинхронных потоку исполнения входных данных т.е. ввода от пользователя, из сети, из другого потока и абстрагированному, а значит в общем случае не-синхронному, вводу от других компонент в составе того же потока.
Растеризация текстов обычно к таким не относится, поэтому ожидать здесь наличие таблицы состояний странно.
ответьте пожалуйста на вопрос это важно для меня, если бы у вас перед глазами была диаграмма состояний рис 18 и соответствующий ей код,(и выкладки по сдвигам и прочее — это тоже рисуется до разработки исходника и хранится с ним) вам было бы сложно разобраться в нём и, например, внести дополнения, или чего-то не хватает ещё?
Человеческий разум устроен так, что ему проще понимать алгоритмы, которым скармливают данные на входе и получают данные на выходе, и результат зависит только от входа, но не от внутреннего состояния. Такие «чистые функции» проще понимать, тестировать и использовать повторно. Также их легче использовать в многопоточном окружении, что актуально для современных многоядерных серверов.
Программа, спроектированная как автомат, будет, конечно же, наиболее эффективной по цпу и памяти, но и наиболее сложной для понимания, так что, имхо, это только техника оптимизации, но не общая техника программирования:
— код, который невозможно понимать и дорабатывать без документации (к тому же, графической документации!) — это слишком дорого для большинства применений
— модификация такого кода может привести к пересмотру хранимого состояния, т.е. придется держать в уме весь код, который этим состоянием пользуется
— состояние перед началом работы нужно инициализировать — этот код тоже «хрупкий» и потребует частых доработок при внесении изменений в логику. А ошибки в нем приведут к сложным багам.
Реализация графа состояний подозрительно напоминает генеренный код — быть может, её и правда можно генерировать по графу состояний? Правда, ни один графический язык пока не взлетел, ну кроме BPML.
такую схему непросто переложить в код без внутреннего состояния
это в точку, но когда я написал
на самом деле Out_text_block реализована как обычный алгоритм
я немного слукавил. На самом деле в этой программе есть явно выделенные состояния. Они заданы метками Type_1 и т.д. Взгляните на этот вопрос математически, программа находится на участке между Type_1 и Type_2 только когда автомат в состоянии Тип 1, и так далее. Это однозначное соответствие. Представьте что вместо метки Type_1, у нас определена функция Type_1 и в программе есть указатель на функцию Current_state (переменная текущего состояния), а вместо операторов goto Type_2 используется конструкция Current_state = Type_2. Я обязательно рассмотрю этот аспект, он изначально заложен в замысел статьи.
Человеческий разум устроен так, что ему проще понимать алгоритмы, которым скармливают данные на входе и получают данные на выходев точку, во второй статье важное место уделено именно этому аспекту, надеюсь, вам будет действительно интересно,
код, невозможно понимать и дорабатывать без документации (к тому же, графической документации!) —.
Дело в том что при таком подходе графическая документация в виде диаграммы состояний предшествует созданию программы, считайте что у вас всегда под рукой. Скажите а функция Out_text_block когда у вас есть диаграмма состояний, насколько понятна?
модификация такого кода может привести к пересмотру хранимого состояния, т.е. придется держать в уме весь код, который этим состоянием пользуетсяя буду рассматривать модификацию этого кода и вы сможете оценить этот процесс
состояние перед началом работы нужно инициализировать — этот код тоже «хрупкий» и потребует частых доработок при внесении изменений в логику. А ошибки в нем приведут к сложным багам.
Такое опасение имеет право на существование, но так получилось что я использую автоматы много лет и во многих проектах, и могу вас уверить, что такая проблема в общем не стоит остро. Автоматный подход не просто требует более внимательного отношения к проектированию программы, он и является элементом внимательного проектирования программы.
Всё что вы пишите это важно, я постараюсь освещать эти моменты подробно, сейчас конечно в коментах это вкратце поэтому если что-то не понятно пожалуйста пишите, я отвечу развёрнуто второй статьёй.
Реализация графа состояний подозрительно напоминает генеренный код — быть может, её и правда можно генерировать по графу состояний?
Многолетняя практика. Автоматическая генерация не самоцель. Она требует слишком детальной проработки диаграммы состояний. Диаграмма состояний должна быть ясной и без излишеств, диаграмма состояний не блок-схема, чем понятней диаграмма состояний тем проще и совершенней код. То что моя программа напоминает генеренный код прямое следствие автоматного подхода — иначе просто и не сделать, автоматный подход сам наталкивает на такую реализацию. Но обратите внимание — схемы со сдвигами это тоже немаловажная часть. Повторюсь, такой подход сам наталкивает на такие реализации.
Программа, спроектированная как автомат, будет, конечно же, наиболее эффективной по цпу и памяти, но и наиболее сложной для понимания, так что, имхо, это только техника оптимизации, но не общая техника программированияесли я смогу своими статьями раскрыть внутреннюю простоту этого подхода я окажу огромную услугу программистам будущего )), все ваши вопросы закономерны, это твердыни которые словно какое то кривое зеркало искажает красоту и естественность автоматного подхода
— преобразовать входную строку в структуру данных, описывающую, что и куда рисовать
— передать эту структуру данных в рендер, который занимается отрисовкой
пожалуйста про входную строку в структуру данных, описывающую, что и куда рисовать подробнее, я кажется понимаю о чём вы пишите, но не уверен что не думаю о другом.
Есть бесплатная триальная версия.
Я бы рекомендовал в ней вам создавать свои автоматы.
Тогда их можно было бы скачать и оценить трудоемкость и эффективность такого подхода.
А также быстро перепроверить насколько ваша реализация отклоняется от проекта.
А рисовать на бумаге диаграммы — это, извините, анахронизм и трата времени.
совсем не понимаю.
каким местом это относится к автоматам?
классически должны были бы быть описания алфавитов входного, внутреннего и выходного алфавитов. Плюс матрицы переходов-выходов, в зависимости от милимура. И собственно вся прелесть автоматного подхода именно в этом: алгоритм меняется простой сменой матрицы. А еще можно приляпать вероятности (и это еще один плюс подхода — нахрен монтекарло), можно приляпать даже интервальные вероятности (с некоторыми ограничениями).
Но вот в статье я таки не увидел ни матриц, ни единого алгоритма.
Какую бы программу вы не написали все это можно будет интерпретировать как автомат.
Поэтому если хотите показать настоящее автоматное программирование, то программируйте сразу машину Тьюринга.
Весь фокус применения этого способа — в выборе удобного разбиения происходящего процесса на состояния, чтобы это было и удобно описывать и удобно менять детализацию при дроблении состояний.
Но почему-то именно вопрос удобства и не рассматривается.
По сути автор предлагает всегда сопровождать текстовую нотацию графической.
Это удобство?
Это нужно только начинающим программистам, у которых мозг не сформировал областей нужных паттернов мышления.
Присутствие оператора switch в программе на языке C-и тоже не маркер автоматного программирования.
В принципе автоматное программирование это такой спекулятивный термин, что даже Миро Самек от него отошел.
Это нужно только начинающим программистам, у которых мозг не сформировал областей нужных паттернов мышления.
это ваше субъективное мнение,
Присутствие оператора switch в программе на языке C-и тоже не маркер автоматного программирования.
Всё верно, маркер автоматного программирования — набор явно выделенных состояний, плюс текущее состояние задаётся конретной переменной. У меня есть хороший пример.
Какой-то слишком сложный алгоритм у вас. Попробовал реализовать, основная отрисовка занимает 100 строк.
Проверки границ только внутри функций отрисовки символа в буфер строки и буфера строки в видеопамять.
Маску наложения байтов можно вычислять на лету при выводе.
Автомат нужен разве что в разборе escape-последовательностей, как и для любой грамматики. Для остального обычный императивный код будет понятнее.
jsfiddle
Что касается вашего кода в целом. Много глобальных переменных и goto. Поддерживать такой код будет очень сложно. Поэтому программирование на автоматах редко применяется. В основном там, где много однотипных состояний и вариантов перехода между ними — например, в компиляторах.
Я так понимаю, в автомате главное это состояние, а состояние в каждой задаче разное. В тех же компиляторах задачи схожие, для них есть библиотеки (ANTLR, Bison), там есть формат описания автоматов. Там и программный код можно дописывать, так что думаю можно применить и для каких-то других задач. Просто никому это не надо, потому что сложно разбираться.
Вот только написана она не с использованием автоматного подхода, поэтому возникают неучтённые комбинации параметров и состояний, и всё глючит.
Если бы был некий стандарт записи автомата в какой-нибудь xml, позволяющий обмен автоматными алгоритмами, плюс некая «стандартная библиотека», возможно, все бы было иначе;согласен с вами. Если вы так понимаете суть проблемы вам будет интересно продолжение, потому что то о чем дальше пойдёт речь находится как раз в том тренде о котором вы пишите
Какой-то слишком сложный алгоритм у вас…приведите, если не сложно, что у вас получилось.
Попробовал реализовать
Маску наложения байтов можно вычислять на лету при выводе.напишите подробнее пожалуйста, о какой маске идёт речь
Много глобальных переменных и goto. Поддерживать такой код будет очень сложно.Это не глобальные переменные, это члены класса Display, они общедоступны для функций членов и сокрыты для доступа извне.
о какой маске идёт речь
Я про эти маски: "существуют пересекающиеся байты — байты которые содержат как старые данные из видеопамяти, так и новые данные из строчного буфера".
это члены класса Display
Да, не заметил. Но это мало что меняет. Они глобальны для всего кода отображения и меняются в разных функциях. В сочетании с goto это становится малоподдерживаемым.
Я считаю что статью нужно переписать.
Почему?
Вы очень быстро перешли от общего к частному, ко всем этим битовым сдвигам. Честно говоря — от этого голова болит. Вроде как хочешь почитать про FSA, а приходится следить за мыслью, что мы там делаем на битовом уровне.
Это все равно что я буду писать статью про устройство map-reduce системы, но где-то после 1/3 статьи перейду к подробностям оптимизации обмена с диском на некоторых файловых системах с учетом древних косяков API ядра под OpenBSD :) И остальные 2/3 статьи будут об этом, с примерами кода и т.п.
А хотелось бы в целом законченную статью про автоматы. С примером разработки автомата. Структурными схемами, и схемой работы каждого автомата.
Ну и краткое рассмотрение реализации автомата. Какие для этого есть библиотеки, подходы, методы. Хотя наверное это лучше в отдельной статье бы.
А хотелось бы в целом законченную статью про автоматы. С примером разработки автомата. Структурными схемами, и схемой работы каждого автомата.но у меня же там про разработку ))). Вы просто ставите меня в тупик этой фразой, если можно то более конкретно.
Во вторых, сам пример для статьи лучше бы взять попроще. Тот который вы рассмотрели конечно удачен в плане того что тут автомат в автомате в автомате и в автомате. Но опять таки… повышать сложность нужно постепенно. Вам может и не заметно, потому что вы уже прекрасно разбираетесь в теме. Но со стороны ты только вроде что-то начинаешь понимать, и тут всё опять усложняется.
Начните с одного автомата. С проектирования его операционной части, затем управляющей.
Потом покажите как этим автоматом может пользоваться другой автомат. И так далее.
При этом сама реализация в коде не нужна. Достаточно будет диаграммы состояний.
А про реализацию в коде отдельную статью сделайте лучше. Где уже разбираются приемы при помощи которых диаграмма воплощается в код.
Про реализацию в коде скорее соглашусь с вами, может её под спойлер лучше?
Тема автоматного программирования ( AP, АП) уже много лет занимает заметное место в научно-популярных СМИ. Однако, несмотря на это, АП не стало магистральным трендом. Главная причина здесь — недостаточный опыт использования, и как следствие, отсутствие популяризаторов. Нельзя сказать, что недостаточно статей посвященных АП, но круг обсуждаемых в статьях вопросов по большому счёту сводится к описанию UML Statechart, т.е. инструменту описания автоматов, либо к вопросу «Как реализуются программные автоматы?». Это печально но факт, отсутствует обсуждение того, какие перспективы для программистов-профессионалов открываются при использовании данной технологии.
Несколько моих публикаций на эту тему были встречены в штыки несколькими злобными, постоянными минусаторами, а моя работа - ПО с демонстрацией в работе, не прошли цензуру администрации.
Лекция для студентов третьего курса по автоматному программированию
Конечно же, заминусовали вас минусаторы потому что были злые, а вовсе не потому что вы пишете что-то странное. Можете продолжать так думать, только не удивляйтесь дальнейшим минусам: злые минусаторы-то никуда не делись!
Вот даже на картинке выше уже написана чушь — автоматное программирование преподносится как нечто новое и противопоставляется традиционному, хотя на самом деле оно не то ровесник "традиционного" программирования, не то даже древнее. Но минус я вам поставил не потому что я не люблю искажения фактов, а потому что я злой минусатор, конечно же.
Вот даже на картинке выше уже написана чушь — автоматное программирование преподносится как нечто новое и противопоставляется
В таком случае Вы поставили свой жирный минус всему высшему образованию кафедры ИТМО, т.к. этот скриншот взят с лекции профессора Анатолия Шатыло, написавшего книгу "Автоматное программирование".
В нижней части картинки ее автор)
Все учебные программы в области ИТ в российских универах живут в прошлом, это давно известно. Особенно когда лекции читает 75-летний профессор.
А уж если этот профессор — специалист по промавтоматике, которая сама по себе консервативная отрасль — полученное комбо позволяет полностью оторваться от реальности.
Нет, поймите меня правильно, я вовсе не хочу принижать достижения профессора. Вполне возможно, что он строил эту самую автоматную парадигму и даже сейчас его наработки косвенно помогают мне налаживать межпланетную логистику в Factorio. Однако, утверждения о том, что эта парадигма якобы "новая" и игнорирование последних десятилетий развития отрасли не заслуживают ничего кроме минуса.
... Особенно когда лекции читает 75-летний профессор.
Ну и при чем здесь возраст? В мире есть тьма примеров, когда люди в возрасте совершали открытия во многих областях, начиная от А.Эинштейна, дожившего до 76 лет, забрав с собой тайну теории единого поля, которая должна была совершить прорыв в понимании пространства и времени, при том что он посчитав, что человечество не готово к этому, сжёг свои рукописи и дневники.
Что касается Анатолия Шатыло, его студенты в свое время занимали первое место на международных соревнованиях по программированию.
Функция минусования без обоснований, это саБЛЯ, подаренная хабря в руках мартышки. Принципиально здесь не в дискуссиях
Оно конечно дело личное, больше отвечаю для тех кто этот пост читает не по диагонали, не поленитесь и пройдитесь по ссылкам, которые я дал выше в своем комменте.
Да, совершенно верно, в мире есть много примеров учёных которые совершали открытия в возрасте. А ещё есть много примеров профессоров, которые застряли в прошлом и рассказывают об открытиях своей юности как о чём-то принципиально новом. В данном случае я наблюдаю второй вариант.
Что касается Анатолия Шатыло, его студенты в свое время занимали первое место на международных соревнованиях по программированию.
Вот только благодаря или вопреки?
К олимпиадам школьником и студентов готовили Станкевич, Лопатин и компания. Шалыто (да, он Шалыто, а не Шатыло!) среди них я не помню.
Удалено по инициативе автора.
Автоматное программирование – новая веха или миф? Часть 1. Введение