Pull to refresh

Comments 47

Товарищи… Кто осилил? О чем статья? Что такое ВКП?

Почти что так :)
Но все же более точная расшифровка в моих предыдущих статьях все на эту же тему — тему автоматного программирования (АП). Но для ленивых не поленюсь повторить — Визуально-Компонентное Программирование (автоматное). Отсюда сокращенно и «родилось» ВКП(а). Хотя имелось в виду и ВКПб :)
К вопросу о чем статья и ее смыслах.
Статья о параллельном программировании
1. Статья о том, как из маленьких кирпичиков — программных объектов сложить прекрасное здание — параллельную программу. А если эти кирпичики «живые», то вдохнуть в него еще и «душу».
2. Статья о том, что даже в случае, когда мы знаем досконально поведение простейших элементов, что при этом выкинет «душа» нам чаще всего не ведомо.
3. Статья о том, что если поведение «души» поначалу совсем не ведомо, это не означает, что оно должно быть совсем непредсказуемым.
4. Статья о том, что неведомое поведение при одних и тех же начальных условиях должно быть повторяемо и в этом и только в этом случае оно поддается изучению и анализу.
5. Статья не о том, как из огромного куска гранита, отсекая лишнее, создать шедевр, а том, как, имея даже неказистые кирпичи или камни, сложить красивое и полезное здание, как, имея ограниченный набор красок, нарисовать картину, как, имея битые кусочки разноцветного стекла, сложить мозаику, как, имея простое поведение, создать сложное.
6. Статья о том, как элементарное поведение отдельных объектов позволяет, не напрягаясь интеллектуально, а лишь простыми структурными методами решить фактически любую сложную проблему.
7. Статья-предупреждение о том, что любая программная формализация не может быть оторвана от жизненных реалий (уравнение типа у=f(x) в корне не верно, т.к. нет (!) мгновенных вычислений). В противном случае не найти простого структурного решения даже для простейших задач/проблем.

Но, правда, чтобы проникнуться ее (статьи) сутью необходимо все же обратиться к истокам, начав с определения АП и далее по списку моих предыдущих публикаций. Дело не простое, но необходимое. Как минимум, что представляет собой классических автомат, автоматная модель вычислений и, тем более, теневая память в них рассказано.

Или, если уж совсем кратко. Данная статья про автоматное программирование (АП), о примерах его реализации в среде Визуально-Компонентного Программирования (автоматного) — ВКП(а). Статья с кратким, почти мимолетным упоминанием других подходов (речь о корутинах и событийных автоматах). С примерами аналогичного их применения и/или призывами аналогичные проблемы решить.

Понятнее не стало...


Я тут философски могу сказать. Если я не могу ребёнку рассказать, чем я занимаюсь, значит я не понимаю того, чем занимаюсь. (Не помню откуда цитата).


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


А тут, даже перечитав статью пару раз, невозможно понять, о чем идёт речь. Об этом говорит отсутствие комментариев и низкий рейтинг. Перфекционизм в этом плане штука полезная, ибо, что толку, если вы разработали офигеннейшую теорию, но не можете внятно объяснить, зачем она нужна и какие проблемы решает. Ваша теория уйдёт вместе с вами.

Не обращайте внимания, эта статья написана для нас, апологетов корутин, с призывом вернуться к корням и писать автоматы руками, а не генерировать компилятором.

И это, действительно, так.
Но, предположим, Вы правы.
Тогда, наверное, теорию автоматов можно заменить на теорию корутин? И начала Кибернетики переписать? Глушков, фон Нейман и иже с ними устарели и формально и морально?
Интересно, а как это будет выглядеть? Я, если честно, не могу это себе представить. От слова — никак.
Хотя, не скрою, было бы любопытно посмотреть, почитать, сравнить и тогда где-то меня даже… «понять и простить» ;)

Хотя бы не пытаться натянуть сову на глобус. А именно, пытаться объяснить с помощью автоматной модели корутины.


Для начала ответьте мне на вопрос — для решения какой задачи понадобились корутины? Почему, внезапно, куча языков их стала поддерживать? Какие альтернативные варианты решения этой есть? Автоматы. А ещё? Какие у всех плюсы, какие минусы?


Думаю, уже в процессе поиска ответа (в сети Интернет, разумеется) на первый вопрос вы поймете ответ на второй. А третий уже покажет вам, что не покрывается автоматной моделью.

Ну и сам Тьюринг ушел в синергетику.
“Компьютеры только тогда будут вести себя интересным способом и проявлять несомненную разумность, когда им позволять совершать ошибки.” А. Тьюринг
Интересным — возможно, но разумность — не совершать ошибки. Ну, как минимум, их исправлять ;)
Код, который содержит ошибку с точки зрения функционирования программы, но легитимен с точки зрения языка, заставляет опасаться за надежность программ на нем. Это мнение, наверное, может быть оспорено знатоками языка Kotlin.

Я готов оспорить это утверждение для (почти) любого языка программирования. Следите за руками:


1/0

И да, замена


var res = listOf(async { a+b }, async{ b+c }).map { it.await() }
c = res[0]
a = res[1]

на


listOf(async { с = a+b }, async{ а = b+c })

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


Разумеется, в том же Расте компилятор не даст вам совершить подобную ошибку, но в плюсах, о которых говорится в статье, такой гарантии тоже нет.


Что я нахожу ироничным, так это то, что вы переизобрели продолжения (continuation), которые были в лиспе с незапамятных времен. Смотрите:


class FSumABC :
    public LFsaAppl
{
public:
    // Эти две функции можно объединить
    LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FSumABC(nameFsa); }
    bool FCreationOfLinksForVariables();
    // Тривиальный конструктор
    FSumABC(string strNam);
    // Сохраненные переменные
    CVar *pVarA;        //
    CVar *pVarB;        //
    CVar *pVarC;        //
    CVar *pVarStrNameA;        //
    CVar *pVarStrNameB;        //
    CVar *pVarStrNameC;        //
protected:
    // Функция вычисления
    void y1();
};

Сравните с тем, что генерирует котлиновский компилятор для suspend лямбды (из внутренней документации по кодогенерации корутин)


1. supertypes: `kotlin/coroutines/jvm/internal/SuspendLambda` and `kotlin/jvm/functions/Function{N}`
1. package-private captured variables
1. private label field of int. Private, since it is used only in the lambda itself.
1. private parameter fields. The reason of visibility is the same, as for `label` field.
1. private fields for spilled variables. Same.
1. public final method `invokeSuspend` of type `(Ljava/lang/Object;)Ljava/lang/Object;`.
It overrides `BaseContinuationImpl`'s `invokeSuspend`.
1. public final `create` of type `(<params>,Lkotlin/coroutines/Continuation)Lkotlin/coroutines/Continuation`.
`<params>` types are erased. In other words, their types are `Ljava/lang/Object;` as long as the number of parameters
is either 0 or 1. This is because the method overrides base class's `create`.
1. public final `invoke` of type `(<params>,Ljava/lang/Object;)Ljava/lang/Object;`. Since it overrides `Function{N}`'s
`invoke`, types of `<params>` are erased.
1. public or package-private constructor: `<init>` of type `(<captured-variables>,Lkotlin/coroutines/Continuation;)V`,
where we call `SuspendLambda`'s constructor with arity and completion and initlialize captured variables.
The arity is known at compile-time, but the completion is provided as argument to the constructor.

Если игнорировать захваченные переменные (или объединить их с аргументами) и поле label, которое нужно для машины состояний, то получим следующее соответсвие


CVar* ... -> захваченные переменные, параметры и сохраненные локальные переменные
LFsaAppl -> SuspendLambda
y1 -> invokeSuspend
Create и FCreationOfLinksForVariables -> create
FSumABC -> <init>, конструктор

Есть ещё функция invoke, которая позволяет вызвать корутину как функцию.


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

Следите за руками

«Наши руки не для скуки...» ;) Это сложно, но попробую.

Рассмотрим семантику, но сначала о… синтаксисе.
Мне совсем не понятен (ну, почти) такой… a+b и b+c. Что это?
И откуда вдруг c = res[0] и a = res[1]? И почему так, а не в другом порядке?
«Руки» так решили?
Конечно, можно гадать и в конце концов догадаться. Что, кстати и произошло ;)
Но на мой взгляд нужно быть, во-первых, честнее, а, во-вторых, не давать возможности рукам «шалить».
В данном случае мне понятно, когда так:
c=a+b
a=b+c
Обращаю внимание на синтаксис и семантику.
Не так: c=a+b; a=b+c; и не наоборот. А именно так, как выше.
Но и в этом не вся правда, а есть некое лукавство.
Мы понимаем, что это два параллельных процесса суммирования и даже согласны с тем, что они имеют общие данные (это следует из их имен).
Но давайте уж до конца добивать… Что это за процесс, например, c=a+b. Как он начинается, как завершается и завешается ли? Гадать и следить за «руками»?

Автоматы в этом смысле не дают простора «ручкам» (см. автоматную реализацию): есть два процесса (они однозначно представлены автоматными моделями), входы и выход которых связан с определенными переменными. Поскольку эти переменные используются для связи между процессами, то они обязательно имеют «теневой признак» (те, что используются внутри процессов, могут быть обычными).
Таким образом, автоматная реализация однозначна в своей интерпретации и, как бы «ручки» не мечтали, результат работы процессов будет один и только один (см. первый протокол статьи). И здесь можно обсуждать синтаксис, но семантика должна быть именно такая.

С корутинами ситуация иная. И здесь дело даже не в синтаксисе, а именно в семантике, которая достаточно многозначна: можно написать и так и так. И с точки зрения синтаксиса и то и другое будет корректно, но семантика, т.е. смысл, как и результат, будет разный. Как с этим быть? «Умище-то, умище-то куда деть»?
Мне сложно судить, что я переизобрел, но то, что Вы используете схему (подход) для реализации автоматов, которая давно известна в теории синтеза цифровых схем, это для меня очевидно.
Просто корутины к процессу реализации, пардон, процессов заходят, так сказать, с другой стороны. Т.е. используют, насколько можно судить, автоматы для реализации «схемы». А в теории автоматов сначала создается автоматная модель, а «схема» затем используется для их синтеза (сиречь, — реализации). Если бы это было по-другому, то в теории автоматов вообще не было бы смысла. Совсем. Иначе зачем эти странные «яйцеголовые» их рисуют ручками, когда «проще» сразу рисовать «схемы»?
И, кстати, во времена, когда мы еще кроме программирования могли разрабатывать и схемы, у меня были друзья-электронщики, которые напрочь презирали теорию автоматов и синтеза цифровых схем, а божились, что разработают любую схему без какой-либо теории. Но… как потом оказалось, это «проходит» только для случая достаточно простой логики (алгоритма) функционирования схемы.

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


И откуда вдруг c = res[0] и a = res[1]? И почему так, а не в другом порядке?

Давайте я переформулирую задачу, сделав её более абстрактной, и, надеюсь, более понятной для вас. Заменим вычисления a+b и b+c на F(a,b) и G(b,c). Пусть теперь количество тактов, которое занимают F и G неизвестно заранее. Препишите автомат так, чтобы он не зависел от таймингов F и G.


Усложним задачу. Смоделируем теперь соединение по сети. Пусть функция F с очень малой вероятностью кидает исключение (используем встроеный в язык Си++ механизм сообщения об отказе). Так мы смоделировали внезапное отключение от сети. Перепишите теперь весь граф автоматов так, чтобы он аварийно завершил работу. Ах да, забыл, ваша модель предполагает, что мир, в котором исполняется программа — идеален, что исключительных ситуаций не бывает, что "лучше не допускать ошибок".


Кстати, если использовать вашу терминологию, то корутины более "живые", чем ваши автоматы. Почему? Потому что никто не мешает мне их создавать когда мне нужно, во время исполнения, а не только во время компиляции. Никто не мешает мне менять связи между ними по своему усмотрению, опять же, во время исполнения. Они в случае болезни сообщают о ней старшему, заражая его, пока не дойдут старейшины, который объявит карантин и позволит больным тихо умереть, не заражая больше никого.


И, кстати, во времена, когда мы еще кроме программирования могли разрабатывать и схемы, у меня были друзья-электронщики, которые напрочь презирали теорию автоматов и синтеза цифровых схем, а божились, что разработают любую схему без какой-либо теории. Но… как потом оказалось, это «проходит» только для случая достаточно простой логики (алгоритма) функционирования схемы.

Спасибо за пример в пользу моей точки зрения. Я лучше доверюсь компилятору в генерации конечного автомата и объекта продолжения, чем буду писать всё руками, что подходит только для простых случаев.


Ну серьёзно, что это за модель, которая не моделирует реальный мир с его отказами! И автор ещё заявляет о "жизненных реалиях"...

ЕМНИП… ваша модель не покрывает корутины

Могу в ответ ЕМНИП-уть. Я уже говорил, что автоматная модель вычислений, как и модель Тьюринга, «покрывает» любую модель. Это доказано тем же Тьюрингом. А вот про корутины я про какое-то аналогичное доказательство не слышал. Более того, корутины это даже не алгоритмическая модель. Это в меру моего скромного понимания ;)
Препишите автомат так, чтобы он не зависел от таймингов F и G
Ну, во-первых, надо все же говорить о функциях возвращающих значение, т.е. с = F(a,b) и а = G(b,c). А, во-вторых, о каких таймингах идет речь? Автоматы (суммирования) останутся автоматами при любом «тайминге». Тут, если честно, я не понял в чем состоит сама проблема?
… Ах да, забыл, ваша модель предполагает, что мир, в котором исполняется программа — идеален, что исключительных ситуаций не бывает, что «лучше не допускать ошибок».

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

Наоборот, — в пику ;)
Никто не мешает мне менять связи между ними по своему усмотрению, опять же, во время исполнения…
Тоже мне проблемы, напугали… ;) Попробую (только чуть позже) все это продемонстрировать на примере так называемой «задачи о жуках». Есть готовая демка, где они преследуют друг друга, погибают, если их пожирают при этом, рождаются и т.д. и т.п. Нужно только сделать видео.
Ну серьёзно, что это за модель, которая не моделирует реальный мир с его отказами! И автор ещё заявляет о «жизненных реалиях»...
и я серьезно… Если модель универсальна, то она моделирует все, что Вы только можете себе представить. В том числе и любые отказы и откаты. За обоснованием опять же отсылаю к Тьюрингу, который Алан. А на практике что только не приходилось «обрабатывать». И как-то все работало и работает. Без каких-либо «исключений». Отказы обрабатываются, откаты совершаются… Особенно почему-то помнится достала когда-то давно реализация протокола КАМАК. Вот где было накручено с этими самыми отказами! А уж железо глючило — мрак!
  1. "автоматная модель не включает в себя обработку ошибок" (https://habr.com/ru/post/489664/#comment_21319926).
  2. "Если модель универсальна, то она моделирует все, что Вы только можете себе представить. В том числе и любые отказы и откаты."

Их этих двух утверждений следует, что автоматная модель не универсальна. QED. И как бы вы не выкручивались, без кода отмены всего графа автоматов (structured concurrency) ваши слова — пустой звук. Ваши заявления требуют доказательств, тогда как я свои предоставил.


И так как вы, к тому же, не ответили ни на один из моих вопросов, касательно отмены графа автоматов, причины популярности корутин, я, с вашего позволения, исключаю себя из беседы. Продолжайте заниматься теперь уже монологом. Мне, при всём моём терпении, надоело спорить с чат-ботом.

я, с вашего позволения, исключаю себя из беседы

Обидно, досадно, но… я надеюсь, что Вы еще передумаете ;)
Итак, ближе «к телу»…
По поводу жуков см. статью. Обратите внимание на скриншоты. В ней все описано и, даже не знаю, надо ли теперь видно?
Кстати, на сайте SoftCraft в разделе КА-технология много чего на тему того, что теперь я называю ВКП(а) (иногда короче — ВКПа). Есть решение «задачи о стрелках», философы Дейкстры. Все это классика параллельного программирования. Решение подобных задач просто обязательно на «территории» параллельного программирования. Уж коли корутины на нее вступили, то необходимо решение и от них.
Еще в тему. Тему имитационного моделирования систем. Ее реализует среда AnyLogic. На эту тему есть книга Карпова Ю. Имитационное моделирование систем. Введение в моделирование с AnuLogic 5. СПб. 2005. В ней рассматриваются и стрелки и жуки (книгу в Инете можно найти). Все это хорошие примеры применения/приложения автоматов. И именно в практике. Подобных разработок и на корутинах не знаю. Но, может, еще появятся. Ведь автоматы уже, как утверждается, уже «на свалке истории», а задачи-то ни куда не делись? Надеюсь, корутины подхватят упавшее было знамя...;)
Но, про корутины. Вот, честно, — пытаюсь… Ломаю себя, меня корежит :0, но… как бы надо! Народ-то настоятельно требует вникнуть! ;)
Вроде бы нашел, что хотелось бы. Привожу цитату:
Корутины или сопрограммы – это возможность остановить выполнение функции в заранее определённом месте; передать куда-либо всё состояние остановленной функции вместе с локальными переменными; запустить функцию с того же места, где мы её остановили.

Все «ясно как божий день». Дальше — ступор. И не удивительно, что, похоже, не только у меня:
Очень многие до сих пор выступают против корутин. Зачастую жалуются на сложность их освоения, множество точек кастомизации и, возможно, неоптимальной производительности из-за, возможно, недооптимизированного выделения динамической памяти (возможно ;)).

Поясню почему так «корежит» меня. Просто потому, что базовую идею корутин (см. выше первую цитату) реализуют мои автоматы. В них «заранее определенным местом» останова являются состояния автомата. А ВКПа организует переключение между ними, сохраняя и восстанавливая их контекст. Ну, посудите сами, зачем мне корутины, если все на что они способны прекрасно реализуют автоматные сети. И подобное переключение и добавляя при этом много еще чего, о чем корутинам и не снилось.
Ну, а если я покажу код ядра ВКПа, то я, думаю, в ступор впадут уже «апологеты корутин». Но лично я «под капот» заглядываю только тогда, когда мне интересно. :) Я могу конечно ошибаться, но «корутинный двигатель» еще в старом наименовании «сопрограммы» показался мне бесперспективным (выше я уже сказал почему). И пока меня не переубедили в обратном. «Останавливать» я могу (легко!) и автоматами, а вот возможностей автоматов у корутин нет и в помине.
Хотелось-бы чтобы какой-нибудь «чат-бот» меня попробовал переубедить в обратном. Только аргументированно. Желательно на простых и понятных примерах типа «суммы массива», а не на примерах типа клиента GitHub. От подобных примеров мне «по ночам» снятся только кошмары… Уж больно… «долбежу много». Хочется чего-то попроще :)

По поводу кода отмены графа автоматов…
Граф автомата представлен таблицей переходов (ТП) — массив строк LArc (см. исходный код примеров). Что значит «код отмена»? Автоматный процесс в системе представлен заголовком, который содержит указатель на ТП. Когда удаляется автоматный процесс, то удаляется заголовок и соответственно указатель на ТП. Вот и все «удаление графа».
По поводу «философов»…
Я, может, выразился не очень точно. Может, надо пояснить, что решение задачи и код этого решения — разные вещи. Это, как скажем, создание алгоритма нахождения корней уравнения и код реализации этого алгоритма. В моей статье о философах рассматривается поиск решения задачи. Это главное. Код с этим связан лишь косвенно. Например, упоминаемая там модель Хоара процессов фактически вообще отказывается решать эту задачу. Есть модель философов на сетях Петри. И здесь фактически нет решения, т.е. поиска модели и доказательства отсутствия/присутствия в модели тупиков. Модель сопрограмм беднее и модели Хоара и сетей Петри. Вот об этом речь. Потоки и корутины — это средства для реализации того или иного решения, но никак не математические модели.
В статье демонстрируется использование автоматов для реализации корутин. Если это все, на что способен «интеллект» компилятора в смысле генерации автоматов, то это весьма элементарные автоматы. Можно даже утверждать, что это совсем и не автоматы, а в лучшем случае некая имитация их. Но для реализации корутин даже таких возможностей, возможно, и достаточно. Но пока это лишь моя версия «автоматной трактовки» корутин ;)
И, кстати, подобные автоматы я уже, кажется, приводил ранее. И, да, даже их приходится рисовать ручками. Но это требование используемой автоматной технологии. А она должна быть единообразной и в простом и сложном случае. На то она и технология. И автомат в ее рамках фактически другой — классический, настоящий ;) И, более того, не просто автомат, а автоматная модель вычислений.
Давайте я редуцирую ваш комментарий по моему правилу: нет кода отмены графа атвоматов -> пустой звук.
Только для Вас ;)
Листинг. Переход автомата в следующее состояние
void TNetFsa::dispcNewSt (TASK &lst_tsk)
{
// установить новые текущие состояния
    cur_task= lst_tsk.flink;
    while (cur_task != &lst_tsk) {
        cur_wsp = cur_task->w_bl;
        if (!cur_task->bCancel&&!cur_task->pid->stop) {
            if ( (cur_wsp->arc_t&&cur_wsp->arc_b)||cur_wsp->bCall) {
                if (cur_wsp->bCall) {
                    cur_wsp->bCall = cur_wsp->bCall;
                }
                if (cur_task->w_bl->arc_t) {
                    cur_task->state = cur_task->w_bl->arc_t->szSt1;
                    cur_wsp->pFsaAppl->MooreAction();
                }
            }
        }
        // удалить "удаленные" задачи
        if (cur_task->bCancel) {
            while ( static_cast<void*>(cur_task->w_fl) != &cur_task->w_fl) {
                if (cur_wsp->pFsaAppl) {
                    cur_wsp->pFsaAppl->pWSP=nullptr;
                }
                cur_wsp->Clear();
                pStackWsp->Delete(cur_wsp);
                cur_wsp= cur_task->w_bl;
            }
            TASK* del_tsk = cur_task;

            if (cur_task->pFsaAppl->pLFsaHdr) {
                LFsaHdr var;
                var.pLFsaAppl = cur_task->pFsaAppl;
                cur_task->pNetFsa->pCArrayNetFsa->pSetLFsaHdr->Clear(var);
            }

            cur_task= cur_task->GetNextTask();
            del_tsk->Clear();
            pStackTsk->Delete(del_tsk);
        }
        else {
            string strRet;
            // удалить "завершенную" задачу
            if (!cur_wsp->arc_t) {
                strRet = cur_wsp->arc_b->szSt2;		// 
                if (strRet == "XX") {
                }
                else if (strRet == "00") {
                    string strARC;
                }

                cur_wsp->Clear();
                cur_wsp->pFsaAppl->pWSP=nullptr;

                if (cur_wsp->pFsaAppl->pCVarFSA) {
                    if (cur_wsp->pFsaAppl->pCVarFSA->pCurLFsaAppl) {
                        cur_wsp->pFsaAppl->pCVarFSA->pCurLFsaAppl = nullptr;
                    }
                    if (cur_wsp->pFsaAppl->pMainAutomaton) {
                        cur_wsp->pFsaAppl->pMainAutomaton->pNestedAutomaton = nullptr;
                    }
                }
                pStackWsp->Delete(cur_wsp);
                if (static_cast<void*>(cur_task->w_fl) == &cur_task->w_fl ) {
                    TASK* del_tsk = cur_task;
                    if (cur_task->pFsaAppl->pLFsaHdr) {
                        LFsaHdr var;
                        var.pLFsaAppl = cur_task->pFsaAppl;
                        cur_task->pNetFsa->pCArrayNetFsa->pSetLFsaHdr->Clear(var);
                    }
                    cur_task= cur_task->GetNextTask();
                    del_tsk->Clear();
                    pStackTsk->Delete(del_tsk);
                }
                else {
                    if (strRet=="XX") {
                        cur_task->w_bl->arc_b = nullptr;
                        cur_task->pFsaAppl->MooreAction();                    }
                    if (strRet=="00") {
                        cur_task->w_bl->arc_t = &cur_task->w_bl->arc_t->pNextState->ListArc.pRoot->FsaArc;
                    }
                    cur_task->w_bl->bCall=false;
                }
            }
            else {
                cur_task= cur_task->flink;
            }
        }
    }
}


Там, где комменты типа // удалить... и выполняются последующие действия по удалению «автоматных структур».

Вы же понимаете, что вы не ответили на вопрос, а только ушли от ответа? Я вам уже кидал ссылку на постановку задачи: https://vorpus.org/blog/notes-on-structured-concurrency-or-go-statement-considered-harmful/, но вы эту ссылку, как и всё, что не соответствует вашему убеждению "корутины — это автоматы, но беднее", проигнорировали. Я вам также говорил, что генерация автоматов — это только один способ реализации корутин, но вы игнорируете существование корутин, которые реализованы альтернативным способом, потому что это не покрывается вашей моделью "корутины — это автоматы, но беднее".


И нет, отсылки к моделям не подойдут. И вот почему: модель хороша ровно до тех пор, пока она описывает реальный мир с нужной точностью. Как только находится свидетельство, противоречащее модели, модель необходимо дополнить (об этом я тоже вам говорил и был проигнорирован). В реальном мире ошибки случаются. Случаются в неожиданных местах. Если модель не учитывает возможность их возникновения, то она удобна только для доказательства свойств сущностей, описываемых этой моделью (никто, кроме узкого круга теоретиков не пользуется машиной Тьюринга), но неудобна при реальном использовании. Поэтому, например, исключения получили распространение — иначе почти каждую операцию надо было бы проверять, например, при доступе к элементам массива пришлось бы проверять его границы. В языках вроде Java, проверки делаются за программиста, и в случае ошибки кидается исключение. Программист сам решает, что сделать с этим исключением — обработать в этой конкретной функции или передать выше по стеку вызовов.


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


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


Вы можете возразить, что автоматное программирование — это новая парадигма, и она, очевидно, не поддерживает другие. На что я отвечу, что парадигма, не учитывающая существование других парадигм и кучи кода, с которым необходимо стыковаться, обречена на существование только в узком кругу программистов. Даже структурная конкурентность, без которой я не могу представить асинхронное программирование (напоминаю, что обработка ошибок — это часть реального мира и данная парадигма как раз ответственна за решение задачи обработки ошибок, примерно как исключения решали её для синхронного кода), учитывает существование других парадигм.


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


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


Никто на это не пойдет. В данном случае пропасть между теорией и практикой настолько велика, что мы скорее увидим популяризацию зависимых типов с доказательством корректности программ, чем написание программ на одних автоматах.


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

вы эту ссылку… проигнорировали.

Зря Вы домысливаете… ;). Я, конечно, изучил материал, хотя и «по диагонали». Просто потому, что все эти проблемы с goto давно пройденный этап. Автоматному программированию на уровне модели управления не нужны не только они, но вообще любые другие операторы управления — while, if, switch и т.д. и т.п. Мне почему-то кажется, что для Вас это будет новостью ;). Да, наверное, и не только для Вас. Но в рамках действий они вполне применимы. И даже goto не запрещен. Только за рамки действия он не скакнет и это сводит на нет предполагаемый ущерб от его применения.
И о модели. Исходя из определения корутин (см. приведенные цитаты) их применение это, как ни удивительно, вообще отказ от параллелизма. Декларируется чисто последовательное исполнение: — остановили одно — запустили другое, остановили то, вернулись назад и т.д. и т.п. Или я что-то напутал? ;)

В реальном мире ошибки случаются.

Вы, наверное, путаете реальный мир и мир реального корутинного программирования. В реальном мире, как это не обидно, даже нет математики. Математика, программирование и т.п. «реалии» — это результат творчества человека. Поэтому надо говорить об ошибках человека, а не реального мира. Но это уже философские материи. Перейдем к железу. Нет нужды проверять каждую операцию. На уровне железа это решено давно и достаточно элементарно — введением системы прерываний с реакцией на любые возникающие ошибки. Это все давно известные архитектурные «низкоуровневые решения». Модель фон Неймана (не ней мы сейчас работаем) обработку ошибок не учитывает. И, тем не менее, ее используют все и, как говорится, «не парятся» ;) Ваши исключения — это уровень языка высокого уровня, на ассемблере, насколько я припоминаю, этого фактически нет. Не использую их и я. И, как уже не раз говорил, все работает. Нужно только по максимуму не допускать возникновения таких ситуаций. Автоматные модели весьма компактны и позволяют провести полную их проверку и исключить по максимуму возникновение непредвиденных ситуаций. Конечно, «проколы» могут быть, но это уже проблема качества проектирования. Уровень логики модели — автомата, уровень предикатов и действий — методов объектов позволяют этот процесс провести качественно.
Ну, Вы опять за свое. Это же элементарно ;) Машиной Тьюринга не пользуются в силу бедности ее операций (такая ограниченность — требование теории). Но я показал, как их можно просто расширить и, тем самым, ввести в работу и машину Тьюринга.

не поддерживает другие...

Наоборот. Буду утверждать, что любые парадигмы могут вполне сосуществовать вместе. Если об этом позаботиться, конечно. Есть многопоточность и потоки легко используются в АП (есть ситуации, когда это просто необходимо). Потоки в этом смысле очень удобны. На уровне потоков я могу без каких-либо помех и проблем использовать любой код. Еще раз — любой! Лишь бы был только возможен доступ к нему на уровне того же С++. И, кстати, появятся корутины в С++ и они будут доступны автоматам (может уже и есть — не знаю, не пробовал). А через корутины, или благодаря им, будет учтено и «существование других парадигм». Все продумано :)

Корутины знают...

Так и для автоматов это тоже не новость. Все что доступно на С++. А на этом уровне, думаю, доступно все. Или почти все ;)

Автоматная же модель игнорирует...

Не правда Ваша. Выше я сказал как — через те же потоки можно использовать любой код.

Никто на это не пойдет.

Опять не так. Опять в который раз Вы искажаете ситуацию. Уже не раз упоминался «автоматный MATLAB». У последнего, может, пользователь не меньше, чем у того же Kotlin-а. Но по любому — много, ну, очень много. И их число только множится.

а не только одного из них...

Речь не об одном автомате. Приведенный код удаляет все автоматы, которые так или иначе завершили свою работу (осознанно или по ошибке перешли в свое заключительное состояние).

Вы снова очень остроумно уходите от ответа.


Ваши исключения — это уровень языка высокого уровня, на ассемблере, насколько я припоминаю, этого фактически нет. Не использую их и я.

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


я могу без каких-либо помех и проблем использовать любой код. Еще раз — любой! Лишь бы был только возможен доступ к нему на уровне того же С++.

Пусть теперь этот "доступный" код выкидывает исключение...


Есть многопоточность и потоки легко используются в АП (есть ситуации, когда это просто необходимо). Потоки в этом смысле очень удобны.

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


Зря Вы домысливаете… ;). Я, конечно, изучил материал, хотя и «по диагонали». Просто потому, что все эти проблемы с goto давно пройденный этап.

Что подтверждает, что статью вы не читали. Она названа, на минутку, "Structured concurrency or: go statement considered harmful" в качестве омажа на известные статьи Дейкстры по структурному программированию. Продолжая его логику, автор статьи делает аналогичные выводы по поводу асинхронного программирования и необходимости структуры. Прочтите, всё-таки, статью, а после, жду кода отмены графа автоматов, то есть поддержки структурной конкурентности.


И спасибо, что напомнили


Автоматному программированию на уровне модели управления не нужны не только они, но вообще любые другие операторы управления — while, if, switch и т.д. и т.п.

вы же понимаете, что это означает, что даже структурное программирование не поддерживается АП? И мы возвращаемся во времена до Дейкстры. И нет, это не новость для меня. Я уже говорил, что АП — пройденный этап и его нужно закопать...


Уже не раз упоминался «автоматный MATLAB». У последнего, может, пользователь не меньше, чем у того же Kotlin-а.

У матлаба или у его подмножества, поддерживающего АП?


Кстати, раз уж вы завели разговор про популярность, сложите Python, C#, C++20, JavaScript, Kotlin, Go, Raku, Clojure, различные лиспы (скоро добавятся Java и Rust), чтобы оценить распространённость корутин. И это я перечислил только языки, про которые знаю, что они поддерживают корутины. Наверняка существуют еще сотни языков, которые корутины поддерживают корутины, о которых я даже не слышал.


Отвечая на ваш вопрос:


Декларируется чисто последовательное исполнение: — остановили одно — запустили другое, остановили то, вернулись назад и т.д. и т.п. Или я что-то напутал?

Зависит от вашего определения последовательного исполнения. Инструкции корутины — да, нет возможности запустить паралельно инструкции одной корутины, их надо явно разделять на разный корутины.
Сами корутины — почему бы и нет. Можно их запустить хоть параллельно, хоть последовательно, причем в любом порядке.
Например, если у нас дан код


coroutineScope {
  launch {
    println("1")
    println("11")
    println("111")
  }
  launch {
    println("2")
    println("22")
    println("222")
  }
}
println("3")

то 11 будет распечана всегда после 1, 22 всегда после 2, и так далее. Но! Нет гарантий, что 2 будет всегда распечатан после 1. Последовательность запуска корутин и вообще одновременность их работы не гарантируется. Что гарантируется, так это то, что 3 будет распечатана и после 111, и после 222. Структурная конкурентность гарантирует, что основная корутина ждёт окончания работы обоих дочерних корутин.

Идея «структурного параллелизма», как представляется, явно походит на ярусно-параллельную форму. В которой мы переходим на следующий ярус, выполнив вычисления на текущем.
Но настоящий параллелизм загоняется в какую-то «структурную форму». Он подобен «конвейеру», а не «пошаговому» исполнению ярусов.
Подобным конвейером можно управлять, как на рис. 5 в статье. Но и в этом случае компоненты «параллельной ЯПФ» не прекращают свою работу даже при «переходах» с яруса на ярус, выполняя работу по синхроимпульсам.
Конвейерная модель ближе к реальным условиям, когда параллельные объекты не «умирают», выполнив работу/вычисления, чтобы потом опять «родиться» (при приходе очередного синхроимпульса).
Тем не менее, идея имеет право иметь быть. И тот же Ваш пример я представил бы в автоматной форме так:
s0, s1, -, y1y2
s1, s2, -, y3
где
y1() { println(«1»); println(«11»); println(«111»); }
y2() { println(«2»); println(«22»); println(«222»); }
y3() { println(«3»); }
Здесь y1, y2, y3 — действия. Первый переход соответствует их параллельному исполнению. Второй переход идет за первым. Все так, как Вы описали. Форма другая. Возможно не столь привычная и «элегантная», но (на мой, безусловно, субъективный как бы взгляд) она математически и технологически более выверенная и понятная (если к ней привыкнуть и понять ее прелести ;)). Здесь при все желании исключены какие-то иные трактовки исполнения действий.
Таким образом одним автоматом, используя его свойства, мы описали (и реализовали) параллелизм Вашего примера. Но это, как я сказал параллелизм достаточно ограниченный, связанный с управлением действиями.
Настоящий параллелизм — это множество подобных автоматов. Замечу, автоматов функционирующих постоянно и имеющих устойчивые связи друг с другом. Это как «философы», «стрелки» и т.п. Схема может быть динамической подобно жукам, но их обсуждение оставим на будущее.
На связи объектов при этом не накладывается каких-либо ограничений. Но, что интересно, даже при такой казалось бы анархии и беспорядочности связей (в отличие от упорядоченности ЯПФ), эти объекты приводятся к одному объекту. И это уже то, с чего мы начали разговор — со структурного параллелизма. Проблема в одном — как доказать эквивалентность схемы одному автомату (т.е. соответствии схемы структурному параллелизму). К счастью, это возможно.
Итак. Идея «структурного параллелизма» в чистом виде, похоже, описывается одним автоматом. И в этом есть ее ограничение.
Возможно (и, скорее, всего), она проще с точки зрения обработки ошибок/исключений. Но это не главная здесь проблема, т.к. «действия» оттестировать, чтобы они не выбрасывали исключений, думаю, не такая уж большая проблема (в конце концов, если существует опасность того же деления на ноль, то — проверяйте).
И еще. Отсутствие гарантий — плохо. Очень плохо ;) Недетерминизм потоков — основная их проблема. И с корутинами получается опять та же «байда»? Ну, надо же делать выводы из ранее допущенных ошибок!?
И также по поводу «отмены графов автоматов». Другого кода просто нет. Кстати, действие (одно!) на переходе может создавать «граф» (вложенный автомат). И он удаляется при завершении действия. Даже если это действие порождает рекурсию автоматов (графов).
Ошибки, как Вы уже понимаете ;), исключаются на этапе проектирования автоматов.

Да, о потоках. Реализация на примере простого циклического счетчика типа:

int n = 100000000;
while (n>0) {
n--;
}

Вот код (только не надо пугаться :)):

Создание автоматом потока
#include «lfsaappl.h»
#include class FCount;
class ThCount: public QThread
{
Q_OBJECT
public:
ThCount(FCount *p, QObject *parent);
protected:
bool bIfRun{false};
bool bIfStop{false};
bool bIfExecuteStep{false};
FCount *pFCount;
void run();
friend class FCount;
};

class FCount:
public LFsaAppl
{
public:
void ExecuteThreadStep();
void WaitForThreadToFinish();
LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FCount(nameFsa); }
bool FCreationOfLinksForVariables();
FCount(string strNam);
virtual ~FCount(void);
ThCount *pThCount{nullptr};
CVar *pVarCount;
CVar *pVarExtVarCount;
CVar *pVarStrNameExtVarCount;

protected:
int x1(); int x12();
void y1(); void y2(); void y12();
friend class ThCount;
};

#include «stdafx.h»
#include «FCount.h»
#include static LArc TBL_Count[] = {
LArc(«st», «st»,"^x12",«y12»), //
LArc(«st», «s1»,«x12», «y2»), //
LArc(«s1», «s2»,«x1», «y1»), //
LArc(«s2», «s2»,"^x1", «y2»), //
LArc()
};

FCount::FCount(string strNam):
LFsaAppl(TBL_Count, strNam, nullptr, nullptr)
{ }

FCount::~FCount(void) { }

bool FCount::FCreationOfLinksForVariables() {
pVarCount = CreateLocVar(«n», CLocVar::vtInteger, «local counter»);
pVarExtVarCount = nullptr;
pVarStrNameExtVarCount = CreateLocVar(«strNameExtVarCount», CLocVar::vtString, «external counter name»);;
string str = pVarStrNameExtVarCount->strGetDataSrc();
if (str != "") {
pVarExtVarCount = pTAppCore->GetAddressVar(pVarStrNameExtVarCount->strGetDataSrc().c_str(), this);
}
return true;
}

void FCount::ExecuteThreadStep() {
if (pThCount) pThCount->bIfExecuteStep = true;
}

void FCount::WaitForThreadToFinish() {
if (pThCount) {
// завершить поток
pThCount->bIfRun = false;
pThCount->quit();
pThCount->wait(500);
pThCount->terminate();
}
delete pThCount;
}

int FCount::x1() { return pVarCount->GetDataSrc() > 0; }

int FCount::x12() { return pVarExtVarCount != nullptr; }
// создаем поток
void FCount::y1() {
pThCount = new ThCount(this, pTAppCore->pMainFrame);
}

void FCount::y2() {
pVarCount->SetDataSrc(this, pVarExtVarCount->GetDataSrc());
}

void FCount::y12() { FInit(); }
// поток поток поток поток поток поток поток поток поток поток
ThCount::ThCount(FCount *p, QObject *parent):
QThread(parent)
{
pFCount = p;
bIfRun = true; // установить признак запуска/завершения потока
start(); // запустить поток
}
// цикл исполнения потока
void ThCount::run()
{
bIfStop = false; // сбросить признак останова потока
// исполнять пока установлен признак работы потока
// так не возникает ошибки при закрытии приложения
// (установлено опытным путем)
int n = int(pFCount->pVarCount->GetDataSrc());
while(bIfRun) {
if (bIfExecuteStep || pFCount->pVarCount->GetDataSrc() > 0) {
bIfExecuteStep = false;
n = int(pFCount->pVarCount->GetDataSrc());
while (n>0) {
n = int(pFCount->pVarCount->GetDataSrc());
pFCount->pVarCount->SetDataSrc(pFCount, --n);
pFCount->pVarCount->UpdateVariable();
}
n = int(pFCount->pVarCount->GetDataSrc());
}
}
bIfStop = true; // установить признак останова потока
}

За код потока спасибо!


Однако, я имел в виду наоборот: есть два потока, А и В. автомат сначала работает на потоке А, потом работает на потоке В, потом возвращается на А. Зачем это нужно? Это нужно для вывода чего-нибудь в главное окно программы. В данном случае В — это главный поток и только в нем разрешена отрисовка. На корутинах это делается элементарно:


// Здесь мы в потоке A
withContext(UI) {
  // А здесь уже в потоке В
  window.draw(circle)
}
// И снова в А

Конвейерная модель ближе к реальным условиям, когда параллельные объекты не «умирают», выполнив работу/вычисления, чтобы потом опять «родиться»

Именно поэтому я говорю, что термин "сопрограмма" неудачен, более удачен был бы "сопроцедура": как и обычные процедуры, сопроцедуры запускаются, работают и завершаются. Могут запуститься ещё раз, если например, их вызывают в цикле.


Первый переход соответствует их параллельному исполнению. Второй переход идет за первым.

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


Настоящий параллелизм — это множество подобных автоматов. Замечу, автоматов функционирующих постоянно и имеющих устойчивые связи друг с другом.

То есть, единственное отличие от потоков в наличии синхросигналов. Проще, всё-таки, в кремнии выпекать, чем пытаться синхронизоваться при наличии операций с неопределенным временем исполнения (загрузка файла по сети, как пример).


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


Но это не главная здесь проблема, т.к. «действия» оттестировать, чтобы они не выбрасывали исключений, думаю, не такая уж большая проблема (в конце концов, если существует опасность того же деления на ноль, то — проверяйте).

Возьмём пример с загрузкой файла по сети. На середине передачи связь оборвалась и операция загрузки выкинула ошибку. Как такое можно предотвратить до начала загрузки?


как доказать эквивалентность схемы одному автомату (т.е. соответствии схемы структурному параллелизму).

Это, к сожалению, не возможно, из-за того, что структурная конкурентность описывает поведение


  1. В конкурентной среде, с недетерминированным временем запуска и завершения
  2. При возникновении ошибки.

Это абсолютно другая модель, которая не покрывается АП, но соответствует тому бардаку, что творится в современных ОС.

На корутинах это делается элементарно

В аналогичных ситуациях удобнее разделять работы. Например, за конкретные действия отвечает один автомат, за отображение и ввод данных — другой. Первый работает с максимальной скоростью, второй — гораздо медленнее (слишком частое отображение все равно не видно). Обычно это разные автоматные пространства. Тот же автомат отображения можно запускать/создавать только тогда, когда это необходимо, чтобы что-то посмотреть. Таким образом каких-то «прыжков» нет.
Даже приведенный код потока нужен только для выполнения определенной работы. Или очень быстрой или, наоборот, очень медленной, тормозящей основной поток.
Корутины умирают и передают ошибку наверх, совсем как процедуры.
Лучше рассчитывать на «жизнь». Безусловно, может случиться что угодно, но… для этого и есть процедура отладки. Ошибки действий фактически не рассматриваются. Появятся — будет, не скрою, скорее всего крах :( Значит, не все отловили на этапе отладки…
Ибо пока один поток работает ..., другой поток может...
Собственно так работают и автоматы разных автоматных пространств. Но, особенно для «чужого кода», можно использовать и потоки (см. мой пример). А недетерминизм, за исключением слабо взаимодействующих процессов, — это очень плохо. Та же теория асинхронных автоматов именно из-за этого так и не сложилась :(
операция загрузки выкинула ошибку. Как такое можно предотвратить до начала загрузки?
Это надо предусматривать при проектировании того же автомата. Например, работая с сетью, я контролирую время ответа. Если превышено — выполняю те или иные действия.
Это абсолютно другая модель, которая не покрывается АП, но соответствует тому бардаку, что творится в современных ОС.

Формально подобная модель покрывается теорией асинхронных автоматов. В АП, чтобы покрыть подобную модель введены независимые автоматные пространства. При необходимости можно использовать обычные потоки. Да, с точки зрения теории, все это плохо и ее от подобных вещей должно корежить. Но практически это часто очень удобно (см. выше рассуждения об автоматах отображения). Так что многопоточность в силу эффективности ее реализации будет существовать еще долго. Как минимум, пока не появятся ей на замену автоматные пространства ;) (собственно они, как и асинхронные автоматы, есть дискретная модель многопоточности).

Извините, а зачем нужны эти ограничения:
нельзя, чтобы совместное поведение процессов было непредсказуемым.
непрерывность ее функционирования, когда любое изменение входных данных приводит к пересчету результата
Насколько я понимаю, достаточны требования к программисту, чтобы входные данные были неизменяемыми, каждая сопрограмма была локальна по данным (SIMD/MIMD), а перед выходом стоял примитив синхронизации. Зачем нам знать в каком порядке выполняются потоки, если они независимы по входным данным?
Первое «ограничение» проистекает из свойства однозначности алгоритма: 2x2 всегда должно быть 4, а не, как в анекдоте, примерно «сэм-восэм»…
Второе — не ограничение. В последовательном программировании 2x2 — оператор, в параллельном это, как в статье, может быть процесс, реализующий операцию умножения над входными данными.
Требование неизменяемости входных данных — нереальное требование. Например, что такое «неизменяемая синусоида» на входе?
В чем смысл синхронизации «перед выходом»? Зачем и с кем синхронизироваться?
Безусловно, результат не должен зависеть от порядка работы потоков. Именно этой теме и посвящен пример в статье. Если он зависит от порядка — это уже не параллельные потоки.
Параллельные потоки, которые не связаны между собой через входные данные, фактически не интересуют теорию параллельных вычислений. Их можно изучать по отдельности в рамках обычной теории последовательных вычислений.
И еще. Параллельное программирование — это переход к проектированию процессов. Последовательное программирование — это реализация операторов, функций, программ. Т.е. это качественно разные уровни проектирования. Обычная программа обязательно заканчивается, параллельная — может работать очень долго и даже бесконечно долго ;)
Требование неизменяемости входных данных — нереальное требование. Например, что такое «неизменяемая синусоида» на входе?
В зависимости от того, что обрабатываем: или конкретный семпл, или весь временной ряд (массив, список) на момент входа в обработчик. Т.е. на обработку уходит копия, а буфер продолжает копить семплы.
В чем смысл синхронизации «перед выходом»? Зачем и с кем синхронизироваться?
Допустим, на определенной стадии мы выполняем суммирование массива и константы, запускаем потоки по числу элементов массива, каждому из которых передаём элемент массива и константу. Чтобы передать результат суммирования дальше, надо дождаться окончания работы всех потоков.

Имхо, параллельность не означает реактивность.
Т.е. на обработку уходит копия, а буфер продолжает копить...
Для определения вычислительной модели (машины) достаточно памяти в форме ленты, т.е. обычной памяти. Далее, если нужно, уже на ее базе организуется любая структура — стек, буфер и т.п. С точки же зрения на динамику работы модели в пределах одного дискретного такта входные данные по определению считаются неизменяемыми. В реальности мы стремимся к минимизации дискретного такта (повышению тактовой частоты процессора).
Чтобы передать результат суммирования дальше, надо дождаться окончания работы всех потоков.
Спасибо за хороший пример для демонстрации возможностей автоматной модели в сравнении с теми же потоками:). Автоматам для решения этой задачи не нужна синхронизация, потокам даже в таком простом случае (!) — нужна.
Имхо, параллельность не означает реактивность.
На мой взгляд так она вообще не имеет отношения к параллелизму.
Где-то на уровне ядра или железа мы всё равно упрёмся в пул потоков и планировщик, зачем упрощать абстракцию в пользу академичности, если для работы придётся держать в голове другую?
в пределах одного дискретного такта входные данные по определению считаются неизменяемыми
А ещё они могут быть недоступны, заняты, в процессе изменения и пр. Спокойнее копирование вызвать :)
Автоматам для решения этой задачи не нужна синхронизация, потокам даже в таком простом случае (!) — нужна
Допустим, следующая операция — усреднение или ещё что, обращающееся к нескольким элементам массива. Как тут без синхронизации, если один из потоков для локальной окрестности не успел завершиться?
На мой взгляд так она вообще не имеет отношения к параллелизму.
Код должно быть проектировать, писать и сопровождать удобно. Зачем у автомата собственная память? Лично меня это сбивает, я бы в явном виде воткнул буфер.
… придётся держать в голове другую?
Мне сложно угадать, что у Вас в голове :) В данном случае я бы сказать — выкиньте из своей голове мысли о потоках и т.п. ;) Они Вам не понадобятся (ни потоки, ни мысли о них).
Спокойнее копирование вызвать
В пределах дискретного такта, Вы не поверите, — делайте с данными все что угодно: анализируйте занятость, копируйте и т.д.
Как тут без синхронизации
. Сложно уловить ход Ваших мыслей… Это уже другой пример. Здесь — никак. В подобных ситуациях автоматы дают механизм синхронизации — через состояния процессов. Которого, кстати, нет у потоков.
Зачем у автомата собственная память? Лично меня это сбивает,
Чтобы не сбивало… У автоматов нет «памяти». У них есть состояния. Это разные вещи. Состояния тем и примечательны, что их не нужно куда-то «втыкивать». Они — свойство автоматной модели ;)
В данном случае я бы сказать — выкиньте из своей голове мысли о потоках и т.п. ;)
Мой мозг измучен микроконтроллерами, если я последую вашему совету, то потеряю в профпригодности :)
В пределах дискретного такта, Вы не поверите, — делайте с данными все что угодно: анализируйте занятость, копируйте и т.д.
Если считать память одноуровневой, а процессор однозадачным и без прерываний — всё отлично. А если ближе к жизни, то память может быть занята, может быть промах кэша, из DMA или прерывания могут изменить читаемый кусок памяти… В общем, появляются состояния «ждать» и «лопатить неверные данные».
автоматы дают механизм синхронизации — через состояния процессов. Которого, кстати, нет у потоков.
Семафоры и мьютексы появились несколько позднее концепции потоков, но состояния у потока есть, пусть оно и «внешнее».
У автоматов нет «памяти».
Вот в этой статье вы писали про теневую память автомата, по описанию это буфер внутри автомата.
За микроконтроллеры — «уважуха» :) Когда-то тоже приложил к этому руку. Так что по поводу потоков смею утверждать — вполне можно без них.
… но состояния у потока есть
Нужно быть точным — нет. «Внешнее» — не считается. Так можно считать, что и автоматы есть. Только «внешние» ;)
Вот в этой статье вы писали про теневую память автомата
Вы немного не поняли. Я рассматриваю модель автомат+память+операции (об этом точнее в статье). «Плюс», а не «внутри». Например, есть такое понятие — магазинные автоматы. Вот там скорее «внутри». Хотя тоже — с определенной натяжкой.
Так что по поводу потоков смею утверждать — вполне можно без них.
Я не буду плакать про планировщик RTOS или NVIC, но объясните — как, если инструкции минимум двухтактные, и между первой и второй может прийти прерывание и испортить память? Тут с «сырыми» volatile данными очень неуютно работать.

Ещё такой вопрос: а можно весь автоматный формализм через трансляцию перенести в движок или компилятор? Мне комфортнее писать a[i]+b и не думать, что выдаст компилятор: loop unrolling, векторные инструкции или перенос на видеокарту.
но объясните — как, если инструкции минимум двухтактные, и между первой и второй может прийти прерывание и испортить память
Я настолько не доверяю потокам и планировщикам, что лучше написал бы свой «планировщик». Собственно и в Windows и Linux он есть, как есть и прерывания. Было это давно, но насколько я припоминаю в подобных ситуациях (если это необходимо, конечно) существует маскирование прерываний. Если это необходимо делать тупо постоянно, то все это (маскирование) можно встроить в свой планировщик, отменяя прерывания на время выполнения действий.
Я лично пользовался своим планировщиком. Был он простой «как топор» (но и зато надежный, как он же) и при необходимости я его дополнял.
Потом, как представляется, это не очень типовая ситуация. В большинстве случаев прерывания должны работать прозрачно и не «портить» что-то. Но, еще раз, если такая опасность есть, то на время запрещаем их работу. Как-то так.
а можно весь автоматный формализм через трансляцию перенести в движок или компилятор
Что-то можно. Например, в ВКПа таблица переходов автомата преобразуется как-то похоже в промежуточную (внутреннюю) форму. Это удобно. Но саму таблицу переходов (граф автомата и т.п.), т.е. собственно автомат, нужно создавать самому. Ведь, алгоритмы компьютер (язык и т.п.) не создает за Вас? Так ведь? Или Вы поручаете программы писать искусственному интеллекту (о чем многие все еще мечтают).
Что-то можно, конечно, сделать. Те же нейронные сети, генетические алгоритмы и т.п. вещи генерятся. Но, во-первых, это узкий/специализированный класс задач и работу «головой» ни как не отменяет.
Так что хочу огорчить или, наоборот, обрадовать — труд программиста еще долго ни какие ИИ не заменят. Не ленитесь — пишите алгоритмы. Автоматные, конечно. И испытываете от этой работы такое же удовольствие, как и я… Только так… На обычное программирование я сейчас смотрю как на какой-то давний кошмарный сон. Все автоматами, все — параллельно...;)
Не буду обнадеживать ;) На микроконтроллерах реализация того, что есть в ВКПа и в рамках обычной ОС, будет скорее проблематична. Но, например, свою работу я строил так. На обычном компе я отрабатывал алгоритмы, а потом в рамках достаточно простой процедуры все переносилось на микроконтроллер. Были, конечно, проблемы на уровне тех самых прерываний. Но это все было достаточно типово и, раз решенное, оно работало потом всегда.
Да, запрещение прерываний на входе в обработчик типовое решение, кроме тех редких случаев, когда необходимы вложенные прерывания, например, для обработки нерегулярных, но очень важных событий. Но ещё есть «главный цикл», где часто выпоняется несрочная, но времяёмкая работа, и на входе в который прерывания запрещать неправильно. Так что я предпочитаю налаживать общения между прерываниями через буферы, по максимуму разобщая по изменяемым данным.
Я не спорю, что автоматы удобный инструмент и формализм, но рафинированном, а тем более без внешнего планировщика времени выполнения, виде они как-то не очень ложатся на железо.
Ведь, алгоритмы компьютер (язык и т.п.) не создает за Вас?
Ну иногда создаёт, те же Pinhole оптимизации контролера, когда, например, суммирование или умножение заменяется сдвигом. Если можно разделить AST на независимые по данным ветви, то при AOT-компиляции ветви будут запущены независимо (последовательно или параллельно), чтобы на момент схождения независимые вычисления были завершены. Другие оптимизации могут разделить или изменить цикл, вынеся инвариант наружу, или выкинуть мёртый код, к которому нельзя перейти из основного тела программы. В общем, если дизассемблировать код, компилированный с -о3, то можно легко не узнать свою программу. Другой пример — средства языка, например, реализация «ленивых» вычислений на С заставляет частично переписать компилятор Лиспа для вставки в свою программу.
Так что я предпочитаю налаживать общения между прерываниями через буферы, по максимуму разобщая по изменяемым данным.
В подобной ситуации это, думаю, уже не предпочтения, а необходимость ;)
они как-то не очень ложатся на железо
Предпочитаю работать именно с железом и автоматы здесь, исходя из моего опыта, единственная адекватная модель. Кстати, ее и разработали-то «железячники». Уж они-то не стали бы себе делать «козу» ;)
Ну иногда создаёт
Иногда — это специфические ситуации. Но даже их, если подумать, можно реализовать часто более эффективно. В общем же случае все равно нужно думать самому, создавая алгоритм, как обычный, так и автоматный. Да и зачем лишать себя удовольствия — думать ;) Реализацию модели, да, можно поручить компилятору или кому-то или чему-то другому. Например, тот же Stateflow в MATLAB. Вы рисуете автоматы и он создает их код. В том числе и для микроконтроллеров. Все прекрасно. Для меня в этом только одна проблема — в той модели автомата, которой соответствует пакет. В данном случае она несколько не соответствует оригиналу.
По поводу «ленивости». Не скрою, что по мне это просто «изврат». И вообще функциональное программирование — «формально правильно, но издевательски по существу» ;)
В подобной ситуации это, думаю, уже не предпочтения, а необходимость ;)
Я думаю, что других ситуаций с имеющимися архитектурами не бывает :)
Предпочитаю работать именно с железом и автоматы здесь, исходя из моего опыта, единственная адекватная модель. Кстати, ее и разработали-то «железячники».
А чья теория и реализация? Насколько я знаю, первые «два в одном» были у Глушкова, но помню, что там был общий синхроимпульс. Тут работать всё будет надёжно, но весь «конвеер» встаёт целиком, если на какой-то из стадий затык.
И вообще функциональное программирование — «формально правильно, но издевательски по существу» ;)
Было много статей на хабре про то, как ФП правильно готовить. Конечно, если неправильно приготовить те же ленивые вычисления, то очень просто наесться памяти и уснуть, как и при неправильном динамическом программировании.
других ситуаций… не бывает :)
ну, согласен :) Особенно, если речь о прерываниях.
… был общий синхроимпульс
Был и насколько я понимаю остался. Другие попытки типа асинхронной схемотехники (Варшавский и т.п.), похоже, себя не оправдали. И потом у Глушкова (а также Мелихов, Баранов и др...)больше про синтез автоматов, а не про «конвейеры». С гонками проще всего справляться синхронизацией. Без — одни проблемы, теоретическое решение которых, насколько я в курсе, не найдено. Может, правда, что-то и упустил ;)
По поводу ФП. Базовая его идея — начинать с одной функции теории не противоречит (все можно интерпретировать как один большой «черный ящик»), но для практики, где мир многокомпонентен (много взаимодействующих «ящиков»), не подходит. А неправильно реализовать можно что угодно. Вот и многопоточность — совсем не правильная…
Пока есть синхроимпульс, не совсем верно говорить про «активный КА», я правильно понимаю, что синхроимпульс может быть переменной частоты, генерируемым по мере готовности предшественика? А с асинхронными и самосинхронными автоматами всё ещё грустно.

Если не упарываться по максимально чистому ФП типа языка Lambda, то идеи вполне здравы и могут быть применены к любой парадигме:
— Чистые функции: функция принимает только неизменяемые аргументы, переданные ей в явном виде, и имеет такой же явный выход
— Нет глобальному состоянию и глобальным переменным
— Разделение IO (где может быть внезапное изменение данных, независимое от программиста) и остального потока программы (где есть какие-то гарантии и зависимость от программиста_
Ну и прочие плюшки типа композиции функций и частичного выполнения.
Автоматы всегда «активны». Других в теории попросту нет. Синхроимпульсы отсчитывают такты. У синхронных автоматов длительность такта фиксированная, а асинхронных плавающая. Соответственно синхроимпульс выдает или генератор или специальная схема. Классификация по Глушкову. У других определение асинхронных автоматов другое. Мне ближе и понятнее определение по Глушкову. Если Глушкова читали (или того же Баранова по микропрограммным автоматам), то это должно быть Вам известно и понятно.
И, безусловно, автомат работает с теми данными, которые «схватил» на начало такта, а все что в пределах такта им пропускается. А потому длительностью такта и определяется его полоса пропускания, как прибора. Все эти понятия применимы и к автоматным программам. Но к тем, которые на любом функциональном языке, это будет сделать, как мне кажется, сложно :) Хотя бы потому, что в этой модели отсутствует понятие модели времени.

Ну а как без функций и рекурсии на их основе? Никак. Вот и в ВКПа есть вложенные автоматы и на их основе функции и даже рекурсия. Думаю и любые «плюшки» на этой базе можно реализовать. Если, конечно, надо и имеет смысл.
Надо бы Глушкова перечитать, там много математики, поэтому и осилил плохо.
Как работает композиция КА, если предыдущий генерирует данные быстрее, чем последующий потребляет?
Мне так больше Баранов нравился — ближе к практике. По теории автоматов (особенно композиции) — Мелихов. Хотя начинал с Майорова. Много про автоматы почерпнул из теории языков. Но все надо фильтровать, т.к. все эти книги про железо. В программировании многие их проблемы просто по барабану. Особенно их специфический синтез. Поэтому отброшу скромность — читайте мои последние статьи. Там выжимка того, что надо. И по определению автомата. Это и вложение и их параллельная композиция. Для программиста важна машина. Про это Вы совсем не прочитаете.Про инерционность не найдете. Пр композицию тоже нюансы. Тот же Мелихов дает прекрасную теорию, но для абстрактных автоматов, а программисту удобнее — структурные. Про «машину» — только у меня. Про инерционность — только у меня. Про «теневую память» — только у меня. Про реализацию сетевой модели — только у меня. Я, я, я — аж неудобно стало :) Но, как в анекдоте, «куда умище-то денешь» :)
Но еще раз. Все мои последние статьи на Хабре — это последовательная попытка изложить того, к чему я пришел. И фактически я все уже и изложил. Дальше пойдут уже детали…
Как работает композиция КА, если предыдущий генерирует данные быстрее, чем последующий потребляет?

Как и положено — будет пропускать данные. Полная аналогия с железом. Есть полоса пропускания (по Котельникову) и это ни кто не отменял. Если хотите, чтобы работало без пропусков. То 1) приведите автоматы к одной скорости 2) объедините их в сеть с единым дискретным временем. И тогда все проблемы взаимной их работы уйдут. Вы просто о них забудете. Это так будет в ВКП(а). «Железячник» введет в схему генератор и засинхронизирует схемы автоматов. Программисту (в ВКПа) этого не надо. Поскольку за это отвечает ядро, в которое вы грузите автоматы, помещая их в общее автоматное пространство. Замечу, что смоделировать Ваш пример можно, поместив автоматы в разные автоматные пространства. Я так поступаю с диалогами. Они — медленный автомат.
Почитаю Баранова и повторно воскурю статьи, спасибо, но хотелось бы чего-то базового, не такого академического, «тех же щей, но пожиже влей». Проблема не в том, что я не понимаю ваши статьи или код в них, проблема в том, что я не понимаю — зачем и почему именно так? Разбить код на блоки, каждый имеющий закрытые входной и выходной словари и ограниченное количество (лучше всего одну) меняющихся переменных внутреннего состояния бывает удобно, но часто кажется недостаточно удобным инструментом, чтобы вывихивать мозги и писать так всегда. Сам я больше всего почерпнул про КА из «Design Patterns for Embedded Systems in C» и мануалов по TLA+, но там написано более «бытово».
Как и положено — будет пропускать данные.
Понятно, что нужно или уравновесить количество консументов и продуцентов, или ввести планировщик. Вопрос в том, что будет без планировщика, если один из КА кинет исключение или иным способом нарушит тайминг. Если не делать ничего, то в «железе» это быдет значить, что на одном из блоков уползла фаза генератора.
проблема в том, что я не понимаю — зачем и почему именно так?
Чем для меня прежде всего интересен Баранов? Он понятно и доступно показывает как от ГСА (граф-схемы алгоритма) перейти к автомату. Должно быть понятно, что современный программист мыслит по типу ГСА. Пусть даже не рисует блок-схемы. Языки программирования именно такие. Они формируют подобное мышление. И Баранов, похоже, это понял. Понял, что так проще в существующей ситуации, когда сложно программиста убедить мыслить автоматами, когда его научили мыслить блок-схемами.
А зачем тогда автоматы? У автоматов в отличие от ГСА есть теория. Для автоматов есть теория и практика синтеза схем, которых нет для ГСА/блок-схем. Т.е. Баранов — это компромисс между существующим мышление и необходимостью перехода от него к мышлению, которое диктуется теорией и практикой проектирования цифровых схем. Как только мы (точнее Баранов) предложил процедуру перехода от ГСА к КА дальше пошло по накатанному тем же Глушковым пути.
Вопрос. Зачем ГСА, если можно было бы сразу создавать автомат? Инерция мышления проектировщика, которого не учили так мыслить. Вывод, если Вы научитесь и/или не хотите мыслить автоматами, то для Вас они не понятны и не интересны будут по определению.
Перейти на другое мышление сложно. Очень сложно. Чтобы это произошло нужно понимание зачем нужны Вам автоматы, в чем их преимущество. Баранову понятно зачем — чтобы провести синтез. А программисту — на фига все эта круговерть? И на это есть ответ. Автомат — модель, которая качественно совершеннее модели блок-схем. У не есть теория и там все на эту тему расписано. Хотя, конечно, есть в ней и пробелы. Но пока не о них речь.
Итак. Предположим Вам стало ясно, что автоматы Вам необходимы (я опускаю обсуждение почему). Без них Вам нет жизни ;) Как теперь их реализовать. Баранов предлагает теорию их реализации (синтеза). А Вам-то что от этого? Да почти ничего. Железо и программа — разные объекты. Как поступает программист — реализует в рамках текущего свое мышления, т.е. используя конструкцию типа switch. На эту тему есть целая технология — «свист-технология» имени Шалыто А.А. Собственно этот же подход и в упомянутой Вами книге. Я просмотрел ее «по диагонали». Все по списку — UML, модель Harel-а, switch-реализация и т.д. и т.п. Вроде автоматы, но и не автоматы. Я, думаю, что любой англичанин отличит любого русскоязычного, говорящего на английском языке. Даже прекрасном. Это тонкости, которые, порой, очень сложно объяснить.
С автоматами, к счастью, — можно. ;) Нужно только мыслить настоящими автоматами, а не автоматами Харела, автоматами UML и держать в голове их «свист-реализацию». А чтобы так мыслить нужна автоматная машина, имеющая автоматный язык. Среда ВКП(а) и ее «автоматный С++» именно это и реализует. Программист рисует автомат в форме таблицы переходов и дальше его процесс реализации не интересует. Он мыслит чистыми автоматами. Не корявыми автоматами Харела, а более простой, но не менее мощной, классической моделью автомата. Именно для этих автоматов есть теория, а не для автоматов Харела или тех же автоматов Шалыто. И именно подобные классические автоматы с необходимыми для современного программиста дополнениями/расширения — «плюшками» типа вложения автоматов и реализации параллелизма описаны в моих статьях.
Но вот как-то так. В своих статьях я фактически не описываю автоматы. Подробно это делаю упомянутые нами авторы. Я описываю то, что из них (их подмножество) нужно, чтобы они были удобны и понятны программисту. А на этом можно уже строить и другие автоматы — абстрактные, структурные (в обычном понимании) и т.д. и т.п.
«Почему люди не летают?...» я бы перефразировал «Почему программисты не мыслят автоматами?...» :) Баранов убедительно показал и доказал как от ГСА-мышления можно перейти КА-мышлению. И тем самым ответил на Ваш вопрос — «зачем и почему именно так?»

Я только несколько подправил язык классических автоматов, которые использует Баранов, Глушков и др. Так, я добавил вложения, инерцию, и параллелизм (см. мою модель управления автоматных программ). Ну и ввел их в «автоматную машину»… ;) Да, а за их «синтез» отвечает ядро ВКП(а).
Уф… Почти статью накатал :)
Да, благодаря Вам я теперь знаю что такое даже редуценты ;)
Был давно асинхронный процессор, без тактовый. Для таких вещей отлично подошел бы.
А существуют ли какая-либо аппаратная оптимизация рекурсий?
Sign up to leave a comment.

Articles