Упомянутая в заглавии книга (далее H&H) - это про железо [15]. Я - про программирование, но на базе "железной модели" конечного автомата. И там и там математическая основа одна. Все это, действительно, крутая железная концепция, помогающая поставить не только синтез цифровых схем, но и программирование на совершенно другие рельсы, определяющие его будущее.
Параллелизм у программистов нынче в моде. Но, видимо, они (программисты) совсем не в курсе, что разработчики железа давным-давно погружены в эту тему. А потому им (я все про программистов) есть у кого поучиться. Но, похоже, некие амбиции-заскоки этому мешают. Но, если вы этим не страдаете, то прочитайте книгу H&H и дойдите, ну, хотя бы до 4-й главы. Попробуйте реализовать одно-два упражнения, используя свой, программистский инструментарий - всякие там корутины, потоки и весь сопутствующий этому террариум. Убедитесь в его полном бессилии. И тогда, может, это заставит кое-что пересмотреть, переосмыслить. Только представьте: логический элемент - отдельный процесс, десятки, сотни, тысячи элементов - множество параллельных процессов, и все это в вашей ладошке (это я про смартфон) и даже работает!
Но пришло время исполнять обещанное (см. предыдущую часть темы в [1]). И пусть количество "плюсов" пока не достигло заданной планки, но ... если каждый "минус" считать за два "плюса", то это уже более чем ... ;) Так что спасибо всем, давшим положительную оценку - нет, не автору, а затронутой теме. Области знаний, от которой многое сейчас зависит. Это те слова, которые мы вправе сказать в адрес теории, посвященной синтезу цифровых схем, в адрес тех, кто занимался и занимается ее развитием, становлением и внедрением в практику.
И не надо забывать, что именно наши ученые, особенно советской школы, внесли в ее развитие свой значимый вклад. И, может, следовало бы дополнить книгу хотя бы небольшим обзором, отражающим этот факт. А так может создаться впечатление, что мы к этому имеем лишь косвенное отношение и даже в большей степени, как потребители. Ведь, даже учебник для себя сами написать не можем. Хотя это совсем не так... Были и есть учебники, был и есть вклад... Просто все немного подзабылось.
В основе проектирования цифровых схем лежит теория, базирующаяся на двух моделях цифровых схем - комбинационной и последовательностной. В первой части мы рассмотрели комбинационные схемы, эту же часть посвятим больше последовательностной модели. Эти же две темы определяют основу книги H&H, т.к. именно на них базируется рассмотрение всего остального - от приемов и подходов к реализации схем до языков описания аппаратуры.
Светофор
Комбинационная модель - грубая модель, которая не учитывает временных свойств цифровых элементов. Но она проста и легко аппроксимируема понятиями теории булевых функций [2]. Это позволяет выполнять процедуры оптимизации схем, что достаточно подробно описано в научной литературе. Особенно в советской. И еще давно. А были, ведь, "богатыри"!
Но легкость манипулирования булевыми функциями создает ложное представления о модели логических элементов. Формируются даже определенные мифы. И об одном из них мы ниже подробно поговорим. Ну, а пока перейдем к задаче, которая в книге Н&Н приведена для знакомства со второй моделью цифровых схем - последовательностной. Речь пойдет о задаче проектирования системы управления (СУ) простого светофора.
Создание СУ было поручено уже знакомому нам по книге студенту Бену Битдидлу, которой незамедлительно взялся за дело. Что послужило причиной такого задания подробно описано в разделе 3.4.1 книги H&H. Исходные данные для проектирования, место расположения светофоров и структурная модель системы управления показаны на рис. 1.
В соответствии с заданием Бен установил на перекрестке два датчика - Ta и Tb. Они фиксируют движение по улицам. Управлять сигналами светофоров предполагается двумя сигналами La и Lb. Для формирования пауз между переключениями Бен решил тактировать СУ импульсами раз в 5 сек. По переднему фронту импульса светофоры должны гореть в зависимости от состояния датчиков движения. Не была забыта и кнопка сброса светофора.
Граф модели СУ (в книге он почему-то назван таблицей), который нарисовал Бен, показан на рис. 2. И сразу потекли вопросы. Возьмем форму графа. Если уж мы привлекли теорию автоматов, то желательно использовать описание, отвечающее принятым в ней нормам. Как это может выглядеть показано на рис. 3 и рис. 4. Здесь показана модель в двух классических вариантах - модели автомата Мура (рис.3), которая напрямую соответствует модели на рис. 2, и эквивалентная ей модель автомата Мили (рис. 4).
Разницу между моделями на рис. 2 и рис. 3 можно описать, как разницу между эскизом детали и конструкторским чертежом. Во-первых, что это за стрелка, направленная откуда-то сверху в состояние S0? Во-вторых, где у автомата начальное состояние? Или этой стрелкой обозначено именно оно? Судя по всему, так оно и есть. Но "конструкторская документация" предусматривает для обозначения этого другие средства. Например, используя иное изображение начального состояния. На рис. 3, 4 начальным состоянием является состояние, имеющее двойные границы.
Все выше сказанное можно посчитать за придирку, но в той или иной форме начальное состояние должно быть обязательно, а не обозначать в его качестве некий "прилет из безвоздушного пространства".
Безусловно, модель автомата будет включать в себя те или иные особенности, связанные с реализацией. На рис. 2 это сигнал сброса Reset, устанавливающий автомат в начальное состояние. Но тогда, если следовать теории, такие же стрелки-переходы нужно направить из каждого состояния в состояние сброса - S0. На практике сброс - это фактически обязательная стандартная процедура, которой не следует "захламлять" модель. В схеме, реализующей автомат, это элементарный сигнал сброса регистра состояний модели (см. в [2] рис. 3.26 (с)).
К примеру, в реализации автоматов на ПЛК функция сброса модели реализована программно. В каждом программном модуле она представлена соответствующей цепью (см. в [3] цепь 1 на рис. 5). В рамках среды ВКПа (что это за среда см. [4]) функция сброса возвращает любой автомат в начальное состояние или в состояние, которое указано в методе FResetAction() (см. ниже код реализации автомата на С++ в ВКпа).
Специфику программной реализации включают и модели на рис. 3, 4. Ей соответствует петля в начальном состоянии st, помеченная предикатом x12 и действием y12. Здесь предикат x12 выполняет проверку условий, обеспечивающих работу автомата, а отвечающее за инициализацию действие y12 создает ссылки на входные/выходные переменные автомата, выполняет инициализацию значений и т.п. Автомат покинет начальное состояние st, когда будут выполнены все процедуры инициализации.
Поясним роль сигнала bType в моделях на рис. 3 и рис. 4. В программной реализации автоматы, изображенные отдельно, объединены в один автомат (для этого достаточно "склеить" их начальные состояния), режим работы которого определяется данной переменной: в режиме автомата Мура bType=0, в режиме автомата Мили bType=1.
В книге H&H приведена аппаратная реализация модели. Программная реализация имеет свою специфику, но и она должна быть максимально приближена к формальной модели. При прочих равных условиях программная реализация многие вопросы решает все же гибче и проще. Единственно в чем она проигрывает - в скорости, но это дело наживное. Выше было сказано про объединение двух автоматов в один. Программная реализация показывает насколько просто это можно сделать. Листинг программы светофора на языке С++ в среде ВКПа, объединяющий две модели автоматов Мили и Мура, выглядит следующим образом:
Hidden text
#include "lfsaappl.h"
class FTraficLights :
public LFsaAppl
{
enum {enNone, enRed, enYellow, enGreen};
public:
void MooreAction();
void FResetActions();
LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTraficLights(nameFsa); }
bool FCreationOfLinksForVariables();
FTraficLights(string strNam);
virtual ~FTraficLights(void);
CVar *pVarStrNameTa;// имя входного датчика Ta
CVar *pVarStrNameTb;// имя входного датчика Tb
CVar *pVarTypeOfFSM;// тип автомата
CVar *pVarTa; //
CVar *pVarTb; //
CVar *pVarLa; //
CVar *pVarLb; //
protected:
int x1(); int x2(); int x3(); int x12();
void y1(); void y2(); void y3(); void y4(); void y5(); void y6(); void y7();
void y8(); void y9(); void y10(); void y12();
};
#include "stdafx.h"
#include "FTraficLights.h"
static LArc TBL_TraficLights[] = {
LArc("st", "st","^x12","y12"),
LArc("st", "S0","x12^x3","y9"),
LArc("st", "S00","x12x3","y4y6y10"),
// Moore's automaton
LArc("S0", "S1","^x1", "--"),
LArc("S1", "S2","--", "--"),
LArc("S2", "S3","^x2", "--"),
LArc("S3", "S0","--", "--"),
// Mealy`s automaton
LArc("S00", "S10","^x1","y3"),
LArc("S10", "S20","--", "y2y8"),
LArc("S20", "S30","^x2","y7"),
LArc("S30", "S00","--", "y4y6"),
LArc()
};
FTraficLights::FTraficLights(string strNam): LFsaAppl(TBL_TraficLights, strNam)
{ FSetMoore(); }
FTraficLights::~FTraficLights(void) { }
void FTraficLights::FResetActions() { LFsaAppl::FResetActions(); }
void FTraficLights::MooreAction()
{
string strState = FGetState();
if (strState=="st") { y1(); y5(); } // none, none
else if (strState=="S0"){ y4(); y6(); } // La=green, Lb=red
else if (strState=="S1"){ y3(); } // La=yellow
else if (strState=="S2"){ y2(); y8(); } // La=red, Lb=green
else if (strState=="S3"){ y7(); } // Lb=yellow
}
bool FTraficLights::FCreationOfLinksForVariables() {
CVar *pVar=nullptr;
pVarTypeOfFSM = CreateLocVar("bTypeOfFSM", CLocVar::vtBool, "");
pVarTa = CreateLocVar("bTa", CLocVar::vtBool, "bTa");
pVarTb = CreateLocVar("bTb", CLocVar::vtBool, "bTb");
string str;
pVarStrNameTa = CreateLocVar("strTa", CLocVar::vtString, "Ta");
str = pVarStrNameTa->strGetDataSrc();
if (str != "") { pVar = pTAppCore->GetAddressVar(str.c_str(), this);
if (pVar) pVarTa = pVar;
}
pVarStrNameTb = CreateLocVar("strTb", CLocVar::vtString, "Tb");
str = pVarStrNameTb->strGetDataSrc();
if (str != "") {
pVar = pTAppCore->GetAddressVar(str.c_str(), this);
if (pVar) pVarTb = pVar;
}
pVarLa = CreateLocVar("nLa", CLocVar::vtInteger, "nLa");
pVarLb = CreateLocVar("nLb", CLocVar::vtInteger, "nLb");
return true;
}
int FTraficLights::x1() { return static_cast<int>(pVarTa->GetDataSrc()); }
int FTraficLights::x2() { return static_cast<int>(pVarTb->GetDataSrc()); }
int FTraficLights::x3() { return static_cast<int>(pVarTypeOfFSM->GetDataSrc()); }
int FTraficLights::x12() { return pVarTa != nullptr && pVarTb; }
void FTraficLights::y1() { pVarLa->SetDataSrc(this, enNone); }
void FTraficLights::y2() { pVarLa->SetDataSrc(this, enRed); }
void FTraficLights::y3() { pVarLa->SetDataSrc(this, enYellow); }
void FTraficLights::y4() { pVarLa->SetDataSrc(this, enGreen); }
void FTraficLights::y5() { pVarLb->SetDataSrc(this, enNone); }
void FTraficLights::y6() { pVarLb->SetDataSrc(this, enRed); }
void FTraficLights::y7() { pVarLb->SetDataSrc(this, enYellow); }
void FTraficLights::y8() { pVarLb->SetDataSrc(this, enGreen); }
void FTraficLights::y9() { FSetMoore(true); }
void FTraficLights::y10() { FSetMoore(false); }
void FTraficLights::y12() { FInit(); }
Листинг 1. Программная реализация модели светофора на С++
Миф об автоматах Мили и Мура
Цитата из H&H. "Существует два основных класса конечных автоматов, которые отличаются своими функциональными описаниями. В автомате Мура выходные значения зависят лишь от текущего состояния, в то время как в автомате Мили выход зависит как от текущего состояния, так и от входных данных." С этим можно было бы согласиться, но...
Процитируем другого классика из классиков[3]. "... Для задания функций выходов (обычной или сдвинутой) ребра графа (стрелки) обозначаются не только входными, но и соответствующими им выходными сигналами. Если обозначенная входным сигналом xi стрелка соединяет вершину aj с вершиной ak, то в случае автоматов первого рода ей приписывается выходной сигнал λ1(aj, xi), а в случае автоматов второго рода - выходной сигнал λ2(ak, xi), где λ1 и λ2 - соответственно обычная и сдвинутая функции выходов автомата.
В случае автоматов Мура все стрелки, входящие в одну и ту же вершину aµ, должны быть обозначены одним и тем же выходным сигналом. Поэтому принято обозначать выходными сигналами не стрелки, а вершины, в которые эти ребра входят".
И это уже ближе к истине: сигналы с дуг убираются и приписываются вершине, в которую они направлены. И если посмотреть на рис. 2, то, вроде бы, противоречий-то и нет. Но они есть, т.к. утверждение, что выходной сигнал автомата Мура зависит только от состояния, которым он помечен, не верно. На самом деле зависит, как и любой сигнал, выдаваемый автоматом Мили. Просто, повторимся, одинаковые выходные сигналы всех переходов, ведущих в одно состояние, приписываются этому состоянию, которое станет текущим только на следующем такте. Т.е. мы имеем скрытую зависимость рассматриваемого выходного сигнала автомата Мура от текущего состояния и тех входных ситуаций, которые вызывают соответствующие переходы. Просто мы схитрили, упростив запись функции выходов автомата Мили, "обозвав" его попутно автоматом Мура. А автомат Мура - это лишь упрощенная запись эквивалентного ему автомата Мили.
В силу сказанного выше мы можем "по щелчку" для любого автомата Мура создать эквивалентный автомат Мили, перенеся сигнал с вершины, на ведущие в нее дуги. Но мы наталкиваемся на проблемы, пытаясь найти эквивалентный автомату Мили автомат Мура. Все это объяснить это можно хотя бы тем, что, рассматривая некий автомат, как "черный ящик", в общем случае невозможно дать ответ о форме его внутреннего представления - это автомат Мили или Мура. Тестирование программной реализации на С++ в рамках ВКПа, представленной на листинге 1, в этом также убеждает: результаты абсолютно одинаковы, а тип автомата можно понять только по значению переменной bType.
Аргументом в пользу развенчания мифа может служить и сравнение результатов программного моделирования схемной реализации автомата на рис.2 (представленна в H&H на рис. 3.26, стр. 318), с программной реализацией автоматов в разных формах (см. листинг 1). Опять же (по крайней мере в рамках ВКПа) их функционирование неотличимо.
Рис. 22 в H&H создает "ложное" представление о независимости сигналов автомата Мура от входных сигналов автомата, т.к., как ни крути, переход в то или иное состояние (кроме начального) у автомата Мура определяется только его текущим состоянием и текущей входной ситуацией на входах (смю выше цитату из книги H&H). Не было бы этих переходов не было бы и последующего состояния и соответственно сигналов автомата Мура.
Тем не менее, форма автоматов Мура имеет свои плюсы даже в сравнении со своим прародителем - автоматом Мили. Например у Мура вместо указания сигнала на каждом переходе он обозначается один раз при состоянии. Это повышает надежность проектирования, т.к. вероятность пропустить/забыть сигнал на переходе, особенно когда их достаточно много, гораздо выше, чем при состоянии. А, например для ПЛК использование автоматов Мура дает даже двойную выгоду. Так, привязав выходной сигнал командой OUT к состоянию, мы автоматически устанавливаем его при входе в это состояние и автоматически же сбрасываем при переходе в другое состояние. Удобно, наглядно, надежно.
Плюсы аппаратной реализации автоматов Мура в сравнении с автоматами Мили (см. рис. 3.22(a)) тоже достаточно давно известны и понятны. Это стабильность выходных сигналов, на которые, действительно, не влияет нестабильностm входных сигналов, формируемых, если следовать терминологии H&H, некой "обезьяной" (см. стр. 348). Последняя в неконтролируемые по отношению к фронту тактового сигнала моменты времени с произвольной частотой изменяет входной сигнал, порождая так называемую метастабильность. Но, еще раз, это совсем не означает, что выходные сигналы автомата Мура не зависят от ситуации, вызвавшей его переход в то или иное состояние.
Надуманность разделения автоматов на две форме можно показать и на других примерах. Например, в достаточно объемной монографии Марвина Минского "Вычисления и автоматы" при активном использовании автоматов почему-то эти две формы не упоминаются [6]. При этом, исходя из времени ее издания, сложно предположить, что он о них не знал. Еще навскидку - книга Дж фон Неймана по самовоспроизводящимся автоматам[7]. Или другая - про клеточные автоматы [8]. В них используются просто автоматы в своей единственной, определяемой формальным описанием, форме.
C формальной точки зрения в автоматах Мура необходимости нет. Они всего лишь подмножество автоматов Мили и покрываются последними. А как же быть с их ролью в схемах с обратными связями (см. [3])? Ведь элемент памяти - классический пример автомата Мура. А никак! В них в этом случае нет нужды, т.к. их заменяют эквивалентные им и, кстати, неотличимые от них автоматы Мили. Правда, для этого необходимо изменить закон функционирования последних, убрав мгновенную зависимость выходных сигналов от входных. Или, говоря другими словами, использовать инерционную форму функции переходов автомата (инерционный закон функционирования автоматов подробно рассмотрен в [4]). Кстати в этом случае исчезает во многом необходимость включать автоматы в разрывы обратных связей.
Сама по себе форма автоматов Мура достаточно удобна, т.к. повышает надежность проектирования, чем в определенных ситуациях ее применение оправдано. Но повторимся, это всего лишь модифицированная форма автомата Мили. А общем случае - просто автомата. Автомата, который известен, как совмещенная форма автоматов Мили и Мура. В теории проектирования цифровых схем ее еще часто называют С-автоматом [9]. Для книги H&H это сводится к совмещению двух структурных схем реализации автоматов в одну схему - совмещение схем (a) и (b) на рис. 3.22.
О форме описания автоматов
Если сравнить автоматы Мура на рис. 2 и рис. 3, то внимательный глаз увидит, что у модели на рис. 3 отсутствуют петли. В них просто нет нужды. От слова совсем. Просто на рис. 3 используется минимизированная форма автомата - дизъюнктивная нормальная форма структурных автоматов (ДНФ СКА), описанная в статье [4].
Более того, синтез цифровой схемы по ДНФ СКА может порождать логические функции, требующие меньших шагов для их минимизации. Например, в нашем случае можно построить следующую таблицу переходов (Табл. 1) (подробнее про таблицы переходов см. [5]), по которой затем провести синтез комбинационной схемы.
Табл.1
|
Ta, Tb |
S0 (00) |
S1 (01) |
S2 (10) |
S3 (11) |
^x1^x2 |
S1 (01) |
S2 (10) |
S3 (11) |
S0 (00) |
^x1x2 |
S1 (01) |
S2 (10) |
S3 (11) |
S0 (00) |
x1^x2 |
S0 (00) |
S2 (10) |
S3 (11) |
S0 (00) |
x1x2 |
S0 (00) |
S2 (10) |
S2 (10) |
S0 (00) |
Выражения, построенные по данной таблице, и шаги их минимизации будут выглядеть так:
S0` = ^S1^S0^x1^x2 + ^S1^S0^x1x2 + S1^S0^x1^x2 + S1^S0^x1^x2 = ^S1^S0^x1 + S1^S0^x2
S1` = ^S1S0^x1^x2 + ^S1S0^x1x2 + ^S1S0x1^x2 + ^S1S0x1x2 + S1^S0^x1^x2 + S1^S0^x1x2 +
+ S1^S0x1^x2 + S1^S0x1x2 = ^S1S0^x1 + ^S1S0x1 + S1^S0^x1 + S1^S0x1 = ^S1S0 + S1^S0
Они в точности совпадают с выражениями (3.2) из книги H&H.
На рис. 5 показаны результаты тестирования трех автоматных моделей управления светофоров: в форме автоматов Мура, Мили и цифровой схемы, реализующей автомат Бена. На карте кампуса для каждой модели выделена пара светофоров. Можно видеть, что их поведение синхронно и идентично.
По поводу частоты синхронизации. Возможно, как частное решение, предложенное к тому же студентом, демонстрирующее особенности работы автоматов в дискретном времени, оно и имеет право на жизнь. Но, на мой взгляд, лучшим решением будет выбрать частоту синхронизации максимально возможной, а заданные моменты времени отсчитывать таймером. Это будет ближе к реальной практике, да и гибче с точки зрения развития алгоритма светофора. В свете подобной синхронизации вызывают возражение временные диаграммы сигналов, представленные на рис. 3.27 в H&H. Наклонные фронты сигналов при такой частоте выглядят весьма неправдоподобными.
Декомпозиция автоматов
Синтез цифровой схемы, реализующий автомат - есть декомпозиция на множество взаимодействующих автоматов, каждый из которых представляет модель элементарного логического элемента. При этом простейшая автоматная модель любого логического элемента в рамках модели двоичных сигналов - это автомат с двумя состояниями (по числу состояний выхода). Таким образом, для схемы светофора на рис. 3.26 результат синтеза исходного автомата светофора на рис. 3 - это декомпозиция на девять взаимодействующих автоматов, каждый из которых имеет два состояния.
Обратная операция по отношению к операции декомпозиции - операция композиции автоматов. С ее помощью для некоторого множества автоматов (такое множество в теории автоматов называется сетью автоматов или просто сетью) можно найти эквивалентный однокомпонентный автомат. В нашем случае это должен быть автомат на рис. 3. Немного подробнее о данных операциях (особенно про операцию композиции), которые часто ассоциируются с известными операциями деления и умножения, говорится в статье [4].
Синтез цифровой схемы автомата - это интуитивно найденный подход к декомпозиции исходной модели на некое множество простейших автоматов. Посмотрим, что мы можем получить, если проведем декомпозицию исходного автомата на некое другое множество автоматов, имеющих в общем случае произвольное число состояний.
Во-первых, сразу возникает вопрос - какое минимальное число автоматов может входить в автоматную сеть, представляющую декомпозицию. Их число определяется достаточно просто - пространство состояний такой сети - произведение состояний компонентных автоматов. Оно должно покрывать, т.е. быть равно или больше, числу состояний исходного автомата. Для светофора с его четырьмя состояниями достаточно двух автоматов по два состояния. Но если хотите разобраться в деталях алгебры автоматов, включающих упомянутые операции, то лучших книг (да не обидятся наши бывшие теперь "не-друзья-партнеры") на тему декомпозиции/композиции автоматов, чем книги советских ученых С.И.Баранова[9] и А.Н.Мелихова [10], я не знаю.
Формально декомпозиция может включать любое число автоматов, как в случае сети, эквивалентной схеме автомата светофора - девять автоматов по два состояния. Здесь важно понимать, что взаимодействие компонентных автоматов сети в конечном итоге определит множество состояний, которое содержит эквивалентный сети автомат.
Минуя теоретические препоны, приведем результат декомпозиции автомата на рис. 3 на два автомата. Пусть это будут автоматы A и B и, как уже сказано, содержащие по два состояния. Такая сеть приведена на рис. 6.
Отличие данной декомпозиции от стандартной в том, что последняя использует типовые логические элементы, а здесь компонентные автоматы нужно еще создать. Программно - нет проблем, а с аппаратной - нужно будет попотеть. Фактически это будет проблема, сравнимая по сложности с реализацией исходного автомата. В этом смысле ПЛМ хороши тем, что фактически содержат набор стандартных логических элементов, из которых, путем их соединения, создается сеть/схема, реализующая поставленную задачу.
К чему мы вообще затронули тему декомпозиции/композиции автоматов? Как минимум, для информации. Чтобы на рассматриваемом примере продемонстрировать действия под "автоматным капотом": какие на самом деле с точки зрения теории автоматов решаются проблемы, когда выполняется процедура синтеза цифровой схемы автомата. Другими словами, синтез - синтезом, а об алгебре автоматов, хотя бы общее представление, необходимо иметь. Авторы книги H&H эти вопросы, вольно или нет, пропустили. Для уровня техникума это еще как-то объяснимо и даже где-то оправдано, но когда речь идет о "вышке", то, на мой взгляд, это уже недостаток. Уж упомянуть-то надо было!
Упражнение 3.29
В процессе обсуждения предыдущей части статьи мы вышли на обсуждение упражнения 3.29 из книги. Меня в нем зацепил довольно нестандартная на мой взгляд постановка - синтез автомата по диаграмме сигналов. Я не припомню, чтобы когда-либо я сталкивался с подобным в литературе по автоматам, которую я штудировал когда-то очень давно. Захотелось попробовать свои силы на решении хотя бы этой задачи. Попробовать, так сказать, пройти собеседование... Получилось, прямо скажем, не так чтобы успешно. Как минимум по времени, затраченного на ее решение. Наверное, собеседование я провалил... :(
Неожиданно обсуждение прошло не без пользы и за это спасибо тем, кто в нем участвовал. Не сразу, но мы все же пришли к определенному решению, хотя недоговоренности остались. Но что-то мне подсказывает, что к итогу нас вывело решение, прилагаемое к книге. И было бы хорошо, чтобы "решебник" был доступен, как и книга, хотя бы в оригинале. Но, с другой стороны, если решение было бы известно, то, скорее всего, самого обсуждения не получилось бы. А так ... все прошло, прямо скажем, достаточно живенько.
Напомним упражнение:
Диаграмма, приложенная к нему, следующая:
Для меня просто очевидно, что решение нужно начинать с конца, т.е. с проектирования автомата. Если есть автомат, то ответы на остальные вопросы будут уже очевидны. Для создания такого автомата у нас почти все есть, а то чего нет мы имеем право додумать. А нет явно одного - не оговорено начальное состояние сигнала A. И это сразу вызывает "наивные вопросы" к авторам упражнения...
Начинаем додумывать: мы можем ввести начальное состояние и из него, в зависимости от текущего значения сигнала A, перейти в состояние "1" или "0", чтобы зафиксировать его значение. Далее совсем просто: мы переключаемся из состояния, которое отражает предыдущее значение сигнала A, в состояние, которое соответствует текущему значению сигнала A, а в процессе переходов выдаем сигнал Z в соответствии с логическими уравнениями. Полученный в результате таких размышлений автомат показан на рис. 7.
Автомат создан и, казалось бы, что еще надо? Подаем на входы автомата сигналы A и B и смотрим на выходе сигнал Z. Но не тут-то было...
Какая связь между автоматом на рис. 7, да, и вообще любым другим предполагаемым автоматом, синхросигнала CLK? Да, ни какой (но это только мое мнение)! Но, ведь, зачем-то диаграмма тактового сигнала включена в общую диаграмму. Зачем? И это уже опять вопрос к авторам книги... Но именно диаграмма сигнала CLK осложнила выработку общего решения и внесла диссонанс в процесс обсуждения.
Тем не менее, удалось получить доступ к авторскому решению. Автомат из него приведен на рис. 8. Не станем его комментировать, но зато есть на что обратить внимание. В этом автомате, что примечательно, отсутствует какая-либо привязка к сигналу CLK. Поэтому повторяем вопрос - зачем он присутствует в условии на диаграмме? Думаю, что такое острое внимание к синхросигналу послужило бы причиной отрицательного решения по результату моего собеседования :( А я бы не отстал ;)
Тем не менее, мы можем ввести синхросигнал в автомат и результат такого решения представлен на рис. 9. Диаграммы сигналов, приведенные на рис. 10, показывают его влияние на сигнал Z. Заметим, что "жесткой" установкой сигнала CLK (точнее - предиката x3) в единицу (CLK = 1) мы приводим автомат на рис. 9 к автомату на рис. 7, а значение CLK = YES - к режиму работы автомата на рис. 9.
Нужно также обратить внимание на петли у автоматов на рис. 7 и рис. 9. Они здесь обязательны, т.к. есть переходы с установкой прямо противоположного значения сигнала Z. Это сигнал y2 на переходе в состояние "1" и сигнал y1 на переходе в состояние "0". Если бы их не было, то петли можно было бы без проблем исключить из описания автоматов.
6. Заключение
Может, я ослабил контроль за автоматами, особенно в программировании, но пролистав статьи, в первую очередь на Хабре, обнаружил достаточно заметное число статей на тему автоматов даже за прошедший год. Явно есть большой интерес к данной теме. И мне это понятно, т.к. для меня альтернативы автоматам в программировании давно уже просто нет. Но, на мой взгляд, все или в основном почти все статьи и комментарии к ним отражают весьма простой, если не сказать - примитивный уровень проникновения в автоматы. Но, однако, давайте "полистаем" ...
Вот статьи одного автора [11, 12]. Это вводный материал в тему минимального начального уровня. Чувствуется практический интерес к автоматам. Но... SWICH-технология? Даже много SWICH-технологии. Однако, на дворе 2023 год и вот-вот будет 2024-й, а это совсем не 1998 год - год издания книги А.А.Шалыто. Нынче она (SWITCH-технология) имеет отношение к автоматам, как лето к зиме: времена года, но общего мало. Тем не менее, спасибо А.А.Шалыто за подвижническую деятельность и активную рекламу автоматного программирования. Нынче у SWTCH-технологии общее с автоматным программированием только название (см. подробнее статью [4]). В статье [11], кстати, рассмотрена реализация светофора. Поэтому есть с чем сравнить. А статья [12] содержит включения из книги H&H. Приятная встреча! Правда, без ссылок на первоисточник, но мы этот непорядок исправляем. Есть в ней, кстати, даже ссылка на мою статью. А это еще приятнее, т.к. мой труд, похоже, не пропадает даром :) Но моя критика SWITCH-технологии автором явно не понята. В этом смысле его совет изучить SWICH-технологию только расстраивает...
Статья [13]. Дает краткое представление о применении теории автоматов. Она заточена под оптимизацию цифровых схем, полученных процедурой синтеза автомата. Весьма специфичная тема и, думаю, будет интересна только математикам, занимающихся теми же генетическими алгоритмами. Может ошибаюсь, но полагаться на результаты подобной оптимизации, думаю, будет сложно. По мне так больше интересны комментарии к ней в части обсуждения проблем параллелизма. Какая же каша в головах!
А вот пример большого разговора на тему автоматов на YouTube [14]. Лично я в этом видео мало что понял. Отстал, наверное, или текучка заела. Но как инфа данное видео может кому-то понравится, а что-то (правда, признаюсь, я не знаю что) даже пригодится. Да, чуть не забыл, книга А.А.Шалыто на одном из слайдов доклада все же промелькнула и здесь.
Но в заключение вернем к нашим "баранам"... Посмотрите на рис. 5. Это программный проект, содержащий более 50-ти параллельных процессов. Не однотипных, а весьма разных, взаимодействующих. Из них почти 40 - прикладные. Сюда входят СУ светофора в форме автомата Мили и автомата Мура, логические элементы, объединенные в схему реализации светофора, элементы графического интерфейса и т.д. и т.п. Все это обслуживает с той или иной степенью активности чуть больше десятка процессов ядра ВКПа. И все это - чистые автоматы. Они работают согласованно и дружно решают поставленную задачу/задачи. Это и есть автоматное программирование без изъятий, но здесь ... и близко нет SWITCH-технологии. Подумайте, прочитайте в конце концов, если не читали, статью[4]. Не поняли - перечитайте ее еще раз, еще раз, может, даже еще раз, но включите наконец-то мозги... А то все switch, switch иногда case, if else... Это все и всегда будет про блок-схемы, а не про автоматы...
Литература
1. Не спеши, Маша! Разбор примеров из книги Харрисон Д.М., Хариссон С.Л. Цифровая схемотехника и архитектура компьютера.
2. Проектирование цифровых вычислительных машин. Под ред. С.А. Майорова. Учебное пособие для студентов вузов. - М.: «Высшая школа», 1972. – 344 с.
3. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962.
4. Автоматное программирование: определение, модель, реализация. [Электронный ресурс], Режим доступа: https://habr.com/ru/articles/682422/ свободный. Яз. рус. (дата обращения 21.11.2023).
5. Проектирование цифровых вычислительных машин. Под ред. С.А. Майорова. Учебное пособие для студентов вузов. - М.: «Высшая школа», 1972. – 344 с.
6. Минский М. Вычисления и автоматы. М.: Мир, 1971. – 364 с.
7. Джон фон Нейман. Теория самовоспроизводящихся автоматов. М.: Мир, 1971 – 382с.
8. Тоффоли Т., Марголус Н. Машины клеточных автоматов: Пер. с англ. – М.: Мир, 1991. – 280 с.
9. Баранов С.И. Синтез микропрограммных автоматов. -Л.: Энергия, 1979. -232с.
10. Мелихов А.Н. Ориентированные графы и конечные автоматы. – М.: Наука, 1971. – 416 с.
11. OldFashionedEngineer. На полпути к конечному автомату для Arduino. Однопроходные функции и фиксация событий программы с помощью флагов. https://habr.com/ru/companies/timeweb/articles/719376/
12. OldFashionedEngineer. С чем едят конечный автомат. https://habr.com/ru/companies/timeweb/articles/717628/
13. Efi-fi. Оптимизация цифрового автомата (FSM). https://habr.com/ru/articles/530414/
14. Кирилл Мокевнин, Конечные автоматы как способ значительно упростить логику и понимание кода. https://www.youtube.com/watch?v=knoVv2ncwVI
15. Хэррис Д.М., Хэррис С.М. Цифровая схемотехника и архитектура компьютера. - 2-е изд.
PS
Когда уже практически закончил свой мини-обзор, то на YouTube обнаружил канал - Школа синтеза цифровых схем (https://www.youtube.com/@chipdesignschool). Что сказать? - Молодцы и спасибо за выложенные видео! Есть, что изучать, с чем знакомиться и, возможно, даже ... критиковать :)
Комментарии (30)
Refridgerator
12.12.2023 16:15Статья интересная, плюс, но содержание спорное от начала до конца. И первым делом - ваш код никуда не годится и хорошо показывает ваш уровень как программиста.
Если рассматривать эл. схемы против типичного программирования, то самые главные различия это:
1) в электрических цепях скорость передачи данных ограничена, и это нужно учитывать;
2) даже в схемах с чисто цифровой логикой присутствуют аналоговые эффекты, и это нужно учитывать;
3) программы на электрических схемах строятся по Data Flow концепции, а в типичных языках программировании - Control Flow. Однако никто не мешает на том же с++ написать набор абстракций для Data Flow - в цифровой обработке сигналов это норма.
4) ну и набор инструментов в программировании практически не ограничен. Сделать там 3-значную логику или на кватернионах - плёвое дело. В отличие от схемотехники.
Выяснять принадлежность получившегося КА к Муру, Мили или ещё кому-то - совершенно бессмысленное занятие. Это вопрос чтобы валить студентов на экзамене, а не писать надёжные и работающие программы.
Светофор? Это же задача школьного уровня, и никакого паралельного программирования там нет и в помине. В ООП это будет объект с событием "смена состояния", на которое сможет подписаться любой желающий - например GUI, чтобы картинку на карте обновить, а тактироваться этот светофор будет по статически определённому таймеру.
lws0954 Автор
12.12.2023 16:15Алаверды. Комментарий интересный, но тоже спорный от начала до конца. Можно, конечно, по каждому пункту, но лучше потихоньку. Начнем с главного - "плевка" в самый центр моей "программистской души" :) Вы как-то быстро оценили мой уровень, опустив его сразу ниже некуда (: Возможно Вы и правы, но ...
Что Вас конкретно не устроило в моем коде? Мнение профессионала всегда интересно. Я тут порылся и отыскал две любимые книжки на момент освоения С++. Времени, когда я создавал одновременно код ядра ВКПа (ВКП-ой оно стало позже). Итак, две книжки: 1) Ричард Вайнер, Люис Пинсон С++ изнутри, Киев , НПИФ "ДиаСофт", 1993 2)Стефан Дьюхарст, Кэти Старк. Программирование на С++, Киев , НПИФ "ДиаСофт", 1993. Вот к чему я тогда прикипел... А, ведь, уже 30-ть лет прошло! Жуть! Был это С++ версии 2.0 и, кажется, Borland C++. И вот с тех пор все это работает. Сейчас С++ дорос, кажется, 20.0. По ходу я переносил код в Visual Studio. Дошел до версии 2010. Плюнул - перешел на Qt. Сейчас это версия 5.14 максимум. Все переносилось "по щелчку" Версии С++ я не контролировал в процессе переноса. Проблемы были только с графикой и диалогами. Но это нормально, т.к. разные библиотеки. Но зачем ломать здание (автоматы), которое столько лет стоит. Да и построено, вроде, по канонам С++. Так, что не так, что сразу убивает во мне программиста? Сгораю от любопытства ;)
Refridgerator
12.12.2023 16:15Пожалуйста, не нужно мой комментарий воспринимать как "плевок". Любой код характеризует написавшего его программиста, и если он вдруг не устроил анонима из интернета - ещё не повод его в себе хоронить.
Хороший код - это не тот код, который хорошо работает. Это код, смысл и логика которого понятна даже без комментариев, а также позволяет масштабировать в очевидных направлениях. Ваш же код излишне переусложнён, необходимость использования строковых значений неочевидно, названия методов ни о чём не говорят, в названиях используются префиксы, засоряющих внимание.
мой вариант на c# навскидку
public class TrafficLight { public enum Status { Red, Yellow, Green } private enum InternalStatus { RedYellow, YellowGreen, GreenYellow, YellowRed } public class EventArgs { public Status status; public EventArgs(Status status) { this.status = status; } } public delegate void TrafficLightEventHandler(object sender, EventArgs e); public event TrafficLightEventHandler StatusChanged; private System.Windows.Forms.Timer timer; private InternalStatus status; private int RedSeconds, YellowSeconds, GreenSeconds, SecondCounter; public TrafficLight(int RedSeconds = 2, int YellowSeconds = 1, int GreenSeconds = 3) { this.RedSeconds = RedSeconds; this.YellowSeconds = YellowSeconds; this.GreenSeconds = GreenSeconds; timer = new System.Windows.Forms.Timer(); timer.Interval = 1000; timer.Tick += Timer_Tick; } public void Start() { StatusChanged(this, new EventArgs(Status.Red)); status = InternalStatus.RedYellow; SecondCounter = RedSeconds; timer.Enabled = true; } public void Stop() { timer.Enabled = false; } private void Timer_Tick(object sender, System.EventArgs e) { SecondCounter--; if (SecondCounter > 0) return; switch (status) { case InternalStatus.RedYellow: status = InternalStatus.YellowGreen; SecondCounter = YellowSeconds; StatusChanged(this, new EventArgs(Status.Yellow)); break; case InternalStatus.YellowGreen: status = InternalStatus.GreenYellow; SecondCounter = GreenSeconds; StatusChanged(this, new EventArgs(Status.Green)); break; case InternalStatus.GreenYellow: status = InternalStatus.YellowRed; SecondCounter = YellowSeconds; StatusChanged(this, new EventArgs(Status.Yellow)); break; case InternalStatus.YellowRed: status = InternalStatus.RedYellow; SecondCounter = RedSeconds; StatusChanged(this, new EventArgs(Status.Red)); break; } } }и использование
TrafficLight trafficlight; private void FormMain_Load(object sender, EventArgs e) { trafficlight = new TrafficLight(); trafficlight.StatusChanged += Trafficlight_StatusChanged; trafficlight.Start(); } private void Trafficlight_StatusChanged(object sender, TrafficLight.EventArgs e) { switch (e.status) { case TrafficLight.Status.Red: radioButtonRed.Checked = true; break; case TrafficLight.Status.Yellow: radioButtonYellow.Checked = true; break; case TrafficLight.Status.Green: radioButtonGreen.Checked = true; break; } }Если стояла задача реализации строго в концепции конечного автомата через базовый класс - то у вас получился тоже совершенно недостаточный уровень абстракции, чтобы это было удобно и не менее очевидно для использования по сравнению с реализацией "в лоб".
lws0954 Автор
12.12.2023 16:15Я отвечу Вам, начав новую ветку. Чтобы всем было видно и задать вопросы именно по коду.
Roma1980
12.12.2023 16:15Я считаю программист, должен в любом случае понимать схемотехнику. Писать код не понимая как его будет исполнять машина, это бегать по городу с завязанными глазами и молится чтобы на автобан не выбежать.
GarryC
12.12.2023 16:15Вы тут спросили конкретные претензии к Вашему коду?
Вообще то я не настоящий сварщик, но навскидку - функции с именами y1,y2,y3...y8,y9,y12 и одинаковой сигнатурой, причем 3 последние в явном виде в коде не используются - это по нашему, по-бразильски.
Ну а если учесть, что все это для реализации автомата довольно таки примитивного светофора - то вообще нет слов, что же тогда будет в по-настоящему сложной схеме - y215?lws0954 Автор
12.12.2023 16:15В по-настоящему сложной схеме y215 не будет ни когда! У меня - абсолютно точно. Чтобы было понятно. В текущей реализации максимальные значения предикатов и действий - x32, y32. Кажется так. В больших индексах просто нужды не было.
eao197
12.12.2023 16:15Специфику программной реализации включают и модели на рис. 3, 4. Ей соответствует петля в начальном состоянии st, помеченная предикатом x12 и действием y12. Здесь предикат x12 выполняет проверку условий, обеспечивающих работу автомата, а отвечающее за инициализацию действие y12
Простите, а где на ваших рисунках (рис.3 и рис.4, как я понимаю, подразумевались) определения для предиката x12 и действия y12? Предикаты x1, x2 и x3 есть, а вот предиката x12 нет.
lws0954 Автор
12.12.2023 16:15Вы задали правильный вопрос, но на него уже есть ответ. Цитата из статьи:
Специфику программной реализации включают и модели на рис. 3, 4. Ей соответствует петля в начальном состоянии st, помеченная предикатом x12 и действием y12. Здесь предикат x12 выполняет проверку условий, обеспечивающих работу автомата, а отвечающее за инициализацию действие y12 создает ссылки на входные/выходные переменные автомата, выполняет инициализацию значений и т.п. Автомат покинет начальное состояние st, когда будут выполнены все процедуры инициализации
eao197
12.12.2023 16:15Во-первых, вы думаете, что если еще раз продублировали использованную мной цитату, то это как-то исправляет содержимое ваших рисунков? Серьезно?
Как по мне, так если вы привели схему КА на которой есть x12 и y12, то добавьте в эту же схему и расшифровку x12, y12 наряду с другими расшифровками.
Во-вторых, реализацию этого x12 я в вашем C++ном говнокоде нашел:
int FTraficLights::x12() { return pVarTa != nullptr && pVarTb; }Только вот сдается мне, что
pVarTa!=nullptrне имеет отношения к логике самого КА с рисунков 3 и 4. Это часть вашей C++ной реализации. Получается, что если бы реализация делалась прямыми руками, а не дендро-фекальным методом, то никакой x12 для КА вообще бы не потребовался.lws0954 Автор
12.12.2023 16:15...Серьезно?
Вполне.
...Получается, что если бы реализация делалась прямыми руками, а не дендро-фекальным методом, то никакой x12 для КА вообще бы не потребовался.
Абсолютно в дырочку ;). Есть такие планы - инициализацию поручить ядру, но ... есть еще что обмыслить ;) Так что пока так. Могу лишь сказать, что когда я делаю автоматы, используя визуальные средства среды, то в такой явной инициализации нужды нет. Но на уровне С++ я такую возможность оставил. Вот теперь думаю... "а не дурак ли я" :)
Но пока без этого нельзя. А почему? Ну, например, в этом случае. Я загружаю автомат в среду (на уровне среды у меня нет кода типа и использование (см. пример Refridgerator)) и он становится видимым. Его надо настроить - указать имя переменной - датчика Ta. Я указываю это имя - автома подхватывает, устанавливая ссылку (см. метод FCreationOfLinksForVariables()) и начинает реализовать свою логику.
Я даже могу согласиться с названием - говнокод. Но только пока лучше не придумал. А пока работает - и пусть работает. Пусть "говнокод", но пока он меня не подводил. Пусть подванивает, но, зато, надежно ;)
Да. Может Вы что-то можете предложить более "розОвое" (в смысле запаха, конечно)
eao197
12.12.2023 16:15Вполне.
Ну афигеть. Я думал, что закос под наукообразие в ваших текстах -- это типа привычка из-за работы в академических кругах. Но, видимо, это что-то с психикой.
Вот теперь думаю... "а не дурак ли я" :)
Смайлик здесь лишний.
Пусть "говнокод", но пока он меня не подводил. Пусть подванивает, но, зато, надежно ;)
Т.е. вот этот список публичных членов, никак не проинициализированный в конструкторе -- это надежно?
class FTraficLights : public LFsaAppl { enum {enNone, enRed, enYellow, enGreen}; public: ... CVar *pVarStrNameTa;// имя входного датчика Ta CVar *pVarStrNameTb;// имя входного датчика Tb CVar *pVarTypeOfFSM;// тип автомата CVar *pVarTa; // CVar *pVarTb; // CVar *pVarLa; // CVar *pVarLb; //Да вас не хватило даже на то, чтобы для большей части из них хотя бы примитивное описание написать в комментарии.
А вот это описание переходов между состояниями:
void FTraficLights::MooreAction() { string strState = FGetState(); if (strState=="st") { y1(); y5(); } // none, none else if (strState=="S0"){ y4(); y6(); } // La=green, Lb=red else if (strState=="S1"){ y3(); } // La=yellow else if (strState=="S2"){ y2(); y8(); } // La=red, Lb=green else if (strState=="S3"){ y7(); } // Lb=yellow }Вы предлагаете эту внутреннюю кухню КА программисту вручную через лесенку if-ов описывать?
Может Вы что-то можете предложить более "розОвое" (в смысле запаха, конечно)
Я бы предложил посмотреть на вещи типа Boost.MSM, Boost.Statechart, SML, TinyFSM, но, боюсь, ваши знания C++ из начала 1990-х не позволят разобраться с этими проектами.
lws0954 Автор
12.12.2023 16:15Если Вы увидели вместо науки "наукообразие" - уточните, конкретизируйте. Рассмотрим, разберемся, что к чему. Если же это просто "выплеск желчи", то тут что-то с психикой уже не у меня... Был бы рад ошибиться ;)
По поводу публичных членов. Правильное замечание, но и на него есть ответ. Если Вы пропустили, то обратите внимане на метод FCreationOfLinksForVariables(). В нем происходит основная инициализация. Те указатели, с которыми могут быть проблемы, дополнительно проверяет предикат x12 и если что-то не так (в данном случае не установлены некоторые указатели) то вызывается "до посинения" действие y12, которое может выполнять или специфические действия или вызывать уже упомянутый метод. Так что, как видите, все продумано и отработано практиткой. Да все это описано в статье...
По поводу "переходов". Ну, да - предлагаю именно так. Почему? Отвечаю. Таблица переходов и ядро были изначально заточены только на автоматы Мили. Их все же за глаза хватает. Но в процессе эксплуатации стало понятно, что и от автоматов Мура может быть польза. Ломать описание, лезть в ядро - еще тот геморрой. Делаем просто: создаем метод в котором читаем текущее состояние, к нему привязывает действия автомата. Так получаем автомат Мура (см. код). В ядре определяем место запуска этого метода. Ну, и соотвестввенно создаем признак вызова (чтобы он не занимал время в обычной ситуации - автоматов Мили). "Кухня" Вам показалась сложной? Ну, не знаю... если это не понятно? Мне кажется, что это простой до гениальности выход :)
По поводу ссылок. Спасибо. Даже возьму на заметку. Но... Мои "наукообразные" знания позволяют оценивать идею, заложенную в том или ином проекте. Если она коррелируется с моими идеями - разбираться имеет смысл. Даже не разбираться - просто проверить. (Не люблю копаться в чужом коде, предпочитаю создавать свой). Но если идею не озвучивают, то смысл ее "вытаскивать" за автора самому на поверхность - только тратать свое драгоценное время. Согласны? Я может и дурак, но не до такой же степени, что доверять любому, сказавшему слова "Конечный автомат". Или у Вас другое мнение на сей счет? Все же опыт меня убедил, что не все что называют термином "Конечный автомат" в большинстве случаев им является. Даже если по ходу упоминают "состояния". Ну, тертый я уже... в том числе и академическими кругами, где, к сожалению, наукообразия более чем достаточно... Одна SWICH-технология чего стоит (Извините, - не удержался "пнуть", но, к моему сожалению, есть за что. Уж ей-то я посвятил уйму времени)
Но, правда ведь, не мы такие - жизнь такая. Поэтому я Вас даже понимаю. :)
Refridgerator
12.12.2023 16:15А чем цепочка if-else-if-else-... отличается от switch в лучшую сторону? В практиках хорошего программирования считается наоборот.
eao197
12.12.2023 16:15Если Вы увидели вместо науки "наукообразие" - уточните, конкретизируйте. Рассмотрим, разберемся, что к чему
Мне это зачем? Я увидел вашу статью, попытался прочитать, почерпнуть что-то. Не смог из-за стиля. Почитал комментарии, увидел человека с очень своеобразными взглядами на происходящее. Выводы сделал. Больше постараюсь не вляпываться.
Если Вы пропустили, то обратите внимане на метод (). В нем происходит основная инициализация. Те указатели, с которыми могут быть проблемы, дополнительно проверяет предикат x12 и если что-то не так
facepalm.jpg
Публичные члены означают большой и толстый болт, положенный на инкапсуляцию. Любой желающий может назначить pVarTa все что угодно и когда угодно.
Ваши бубличные члены не имеют никаких вменяемых значений до вызова FCreationOfLinksForVariables и если кто-то их случайно тронет до этого момента, то у вас будет UB.
В том числе и если предикат x12 будет как-то вызван до FCreationOfLinksForVariables.
Это, блин, такие азы программирования на C++, что прямо стыдно их в очередной раз проговаривать.
lws0954 Автор
12.12.2023 16:15Ваши бубличные члены не имеют никаких вменяемых значений до вызова FCreationOfLinksForVariables и если кто-то их случайно тронет до этого момента, то у вас будет UB.
Вы правы. Может быть, конечно, все. Но только давайте будем поспокойнее...
От дурака сложно придумать защиту. Чтобы проблем не было есть определенные правила создания связей между объектами-автоматами. Тут все ок. Работает и уже давно. Проблема в другом - в подвисании ссылок, т.к. автомат может быть удален из среды и все ссылки на него будут недействительны. Вот это актуально.
Я посмотрел Ваши статьи. Точнее не сами статьи, а их тематику. Что-то подобное, как мне кажется, я там узрел. Вы, похоже, тоже работаете со множеством активных взаимодействующих объектов. Может быть, даже их число меняется в динамике. Как Вы решаете эти проблемы, если только решаете? Типа посылки сообщения объекту, с которым была связь, но потом в силу его удаления - пропала. Как объект узнает, что его "друг" исчез? В общем случае - это даже множество объектов.
Скажем так, образно, речь идет о том, чтобы выдернуть логический элемент из схемы в процессе ее работы. Можно, конечно, остановить работу сети и переписать связи при удалении того или иного объекта, но, может, есть более красивое решение?
Выводы сделал. Больше постараюсь не вляпываться.
Это нормально. Это Ваше решение. Не хотите - навязывать что-то не буду. Действительно, кому-то и А.А.Шалыто - это норм. Я свое слово сказал, а Ваше дело или его услышать или проигнорировать.
Refridgerator
12.12.2023 16:15Вы, похоже, тоже работаете со множеством активных взаимодействующих объектов. Может быть, даже их число меняется в динамике. Как Вы решаете эти проблемы, если только решаете? Типа посылки сообщения объекту, с которым была связь, но потом в силу его удаления - пропала. Как объект узнает, что его "друг" исчез?
Такие проблемы решаются через ООП и грамотной архитектурой классов.
1) объекты находятся не в вакууме, а внутри контейнера. Когда объект удаляется, у него из деструктора (базового класса) вызывается метод контейнера, который разруливает все связи, вхождения в коллекции и прочее.
2) для объекта необходимо предусмотреть значения по умолчанию на случай, когда источник данных ещё не подключен или уже отключен. А не проверять ссылки на nullptr!
lws0954 Автор
12.12.2023 16:15Итак, код. На С++. На совершенно ином уровне абстракции ;)
Автомат Мили
class FTraficLightsMealy: public FTraficLights { public: bool FCreationOfLinksForVariables(); FTraficLightsMealy(string strNam); }; static LArc TBL_FTraficLightsMealy[] = { LArc("st", "st","^x12","y12"), // LArc("st", "S00","x12x3","y4y6y10"), // enGreen, enRed, FSetMoore(false); // Mealy`s automaton LArc("S00", "S10","^x1","y3"), // enYellow, - LArc("S10", "S20","--", "y2y8"), // enRed, enGreen LArc("S20", "S30","^x2","y7"), // -, enYellow LArc("S30", "S00","--", "y4y6"), // enGreen, enRed LArc() }; FTraficLightsMealy::FTraficLightsMealy(string strNam): FTraficLights(strNam, TBL_FTraficLightsMealy) { } bool FTraficLightsMealy::FCreationOfLinksForVariables() { FTraficLights::FCreationOfLinksForVariables(); pVarTypeOfFSM->SetDataSrc(this, 1); return true; }Автомат Мура
class FTraficLightsMoore: public FTraficLights { public: void MooreAction(); bool FCreationOfLinksForVariables(); FTraficLightsMoore(string strNam); }; static LArc TBL_FTraficLightsMoore[] = { LArc("st", "st","^x12","y12"), // LArc("st", "S0","x12^x3","y9"), // FSetMoore(true) // Moore's automaton LArc("S0", "S1","^x1", "--"), // LArc("S1", "S2","--", "--"), // LArc("S2", "S3","^x2", "--"), // LArc("S3", "S0","--", "--"), // LArc() }; FTraficLightsMoore::FTraficLightsMoore(string strNam): FTraficLights(strNam, TBL_FTraficLightsMoore) { } bool FTraficLightsMoore::FCreationOfLinksForVariables() { FTraficLights::FCreationOfLinksForVariables(); pVarTypeOfFSM->SetDataSrc(this, 0.0); return true; } void FTraficLightsMoore::MooreAction() { string strState = FGetState(); if (strState=="st") { y1(); y5(); } // none, none else if (strState=="S0"){ y4(); y6(); } // La=green, Lb=red else if (strState=="S1"){ y3(); } // La=yellow else if (strState=="S2"){ y2(); y8(); } // La=red, Lb=green else if (strState=="S3"){ y7(); } // Lb=yellow }Не проверял, но, думаю, работать будет (ведь, создано на базе работающего кода).
Признаюсь честно, я тащусь от возможностей С++. И вообще, у меня рука "тянется к кобуре" когда:
Кто-то утверждает, что С (любой другой подставьте язык) лучше С++
Кто-то говорит, что ООП - это типа отстой
-
Когда называпют "СВИСТ-технологию" А.А.Шалыто автоматным программированием
Вот, затрелил бы! За ... амбициозную тупость! Хотя, может быть, и не прав. Но ни чего с собой поделать не могу. :)
Да, кстати, выше код на C# сделан по типу SWITCH-технологии.
Извините, но процитирую себя:
"... Это и есть автоматное программирование без изъятий, но здесь ... и близко нет SWITCH-технологии. Подумайте, прочитайте в конце концов, если не читали, статью[4]. Не поняли - перечитайте ее еще раз, еще раз, может, даже еще раз, но включите наконец-то мозги... А то все switch, switch иногда case, if else... Это все и всегда будет про блок-схемы, а не про автоматы... "
Делайте выводы...
Refridgerator
12.12.2023 16:15Ссылаться на свои собственные статьи в качестве аргументации собственной правоты обычно считается недостойным учёных мужей. Конечно, не каждый switch реализует КА - зато наоборот, любой КА реализуется через switch вполне естественным образом. А если не нравится вам switch - ну ок, можно ту же самую логику реализовать через массивы с делегатами с доступом по индексу. Причём продвинутые с++ компиляторы с этим справляются самостоятельно уже давно.
lws0954 Автор
12.12.2023 16:15Ссылаться на свои собственные статьи в качестве аргументации собственной правоты обычно считается недостойным учёных мужей.
Ну, что тут Вам ответить. Я с Вами согласен. Но, к сожалению, я не знаю других мужей точно также трактующих автоматное програмирование. Поэтому, извиняйте, но ситуация такая, какая уж есть. Если знаете другого "ученого мужа" - поделитесь. Я мечтаю с таким познакомиться ;)
По поводу switch. Тут, как говорится, к гадалке не ходи: ни один современный компилятор не реализует автоматную модель (КА, если хотите). Все, что Вы перечислили, лишь имитирует автоматы, как комбинационная модель имитирует реальную схему. Улавливаете разницу?
Можно попробовать такую аналогию:
Комбинационная модель <-> продвинутый компилятор С++,
Последовательностная модель <-> реальная схема.
Комбинационная модель != последовательностная модель.
Мысль, идея понятны?
PS. Добавлю еще с некоторым (небольшим) огрублением):
Конечный автомат - модель отдельного объекта реального мира
Сеть взаимосвязанных синхронных конечных автоматов - модель реального мира
Refridgerator
12.12.2023 16:15Если знаете другого "ученого мужа" - поделитесь
Совершенно случайно знаю одного. Профильное образование имеет (отдельно по электронике, отдельно по информатике), 35 лет практики, куча статей на хабре (ну вы понели, о ком речь).
ни один современный компилятор не реализует автоматную модель
Мой первый интерпретатор математических выражений как раз и был реализован на классическом КА.
Все, что Вы перечислили, лишь имитирует автоматы, как комбинационная модель имитирует реальную схему. Улавливаете разницу?
Конечно. Разница в том, что в реальности нет никаких конечных автоматов. Конечный автомат - это математическая абстракция, как и машина Тьюринга, как и нормальные алгорифмы Маркова, как и всякое прочее другое.
lws0954 Автор
12.12.2023 16:15Мой первый интерпретатор математических выражений как раз и был реализован на классическом КА.
Есть один нюанс - в теории проектирования трансляторов фактически другие автомата.Они, ну, очень похожи (особенно на уровне модели абстрактного автомата), но - другие. Когда-то в поисках нужных автомтов я рылся и в них. Книжки Льюис, Зозенкрац Стирнз, Грис, и совсем уж классика - Ахо, Ульман до сих пор перед глазами на моей полке ;) Все это интересно, конечно, но быстро понял, что не то все это, и вернулся автоматам по Глушкову, к его формулировке дискретной кибернетики... Так что такое сравнение авматов - не проходит. Как говортся, "тепло", но не то.. В трансляторах фактически чистые функции отображения, в синтезе - они же, но с привязкой ко времени. А это нюанс. Там - фактически чистые алгоритмы, в синтезе - преобразователи информации (по Глушкову), т.е. процессы. Кратко, трансляторы - это очень интересно, но - не то.
Конечный автомат - это математическая абстракция, как и машина Тьюринга, как и нормальные алгорифмы Маркова, как и всякое прочее другое.
Вы правы, но не совсем ;) Конечный автомат - как дискретный преобразователь, является математической моделью реальных объектов. В них содержится и алгоритм и закон их работы в реальном времени. Тьюринг и все остальное - это модели алгоритмов без привязки ко времени. И в этом их проблемы. Для машин Тьюринга они вылезли в попытках создать многоголовочную машину, как модель параллельных вычислений. Как-то не пошло. Забросили... :( Но понятно почему. Не учли время... Далее. У реальных объектов есть еще инерционность в работе. Где у Тьюринга, Маркова и далее по списку - инерционность? Нет. От слова совсем.
vk6677
Статья не плохая. Но считаю, что Вы зря принижаете программистов. Это просто профессия с очень обобщённым названием. Думаю, что многие программисты разбираться в схемотехнике. И писать: "используя свой, программистский инструментарий - всякие там корутины, потоки и весь сопутствующий этому террариум. Убедитесь в его полном бессилии...". Это немного не корректно.
lws0954 Автор
Речь, конечно, не обо всех программистах, а в первую очередь о тех, которые считают програмирование на потоках, корутинах и т.п. параллельным или, как они любят сейчас его называть - конкурентным программированием. Вот что некорректно, но по отношению к настоящему параллельному програмированию. Вот это надо как-то им, да и всем нам, усвоить. Так, чтобы называть параллельным програмированим програмирование на потоках, корутинах и т.п. стало дурным тоном.
Я не принижаю, а стараюсь говорить открытым текстом. Пусть жестковато, но мягко уже сказано было и не раз. Может, хватит "политесы разводить"? ;)
GarryC
Вообще то потоки, корутины и прочие как раз и предназначены для того, чтобы организовать параллельные вычисления при условии аппаратной поддержки. Именно поэтому в них учитывается возможность конкуренции за ресурсы и применяются разные способы избегать проблем, с ней связаных. А будет ли реализован истинная параллельность - это не вопрос к программистам, это вопрос аппаратуры - иногда будет, иногда нет, но учитывать такую возможность мы обязаны.
lws0954 Автор
Это прежде всего вопрос к программистам и только к ним, т.к. в их силах создать некую виртуальную машину в которой будет "истинная параллельность". Но это будут просто слова, если "истинная параллельность" не будет означать наличие паралдлеьной модели вычислений. Вот что главное - модель вычислений. А как она будет реализована аппаратно - дело сто двадцать пятое. Программисту об этом даже знать не нужно по большому счету ;)
Refridgerator
Истинная паралельнось существует вполне реально, а не виртуально, и называется GPU. Хотя возможностей для синхронизации там конечно маловато.
lws0954 Автор
Истинная параллельность нас окружает. Окружающий нас мир полон этой параллельности. Но нужно представлять, что функционирует этот мир по определенным законам. Чтобы его "обсчитать" нужна модель этого мира и она должна быть параллельной. Предположим Вы создали такую модель. Как понять, что она моделирует окружающий мир. Только экспериментально. Берем какую-то реальную вещь, потом создаем ее технический аналог по канонам Вашей модели и сравниваем их по результатам работы. Лучше реальную модель и технический аналог поместить в закрытые комнаты и по внешним признакам пытаться угадать где какая... Помните тест Тьюринга на способность машины мыслить?
Только здесь ситуация будет попроще. Например. Совсем простой. RS-триггер. Реальный состоит из двух элементов - два параллельных (истинных!) процесса. Берем Ваш GPU. Берем два потока, два ядра и что там еще... истинно параллельное ;) Создаем две модели элемента, связываем их по схеме триггера. Берем два "стаканчика". Под один - реальный триггер, под другой - Вашу модель. Перемешиваем. Да, из стаканчиков выодим контакты - два входа и два выхода RS-триггера. Ну вот - перемешали, премешали, запутали, короче... К входам цепляем кнопки, к выходам лампочки и, чтобы не было вопросов совсем, - осциллограф двухлучевой (лучше четыре) Давим на кнопки, смотрим на выходы - гадаем, чешем репу ;). Где реальный триггер? Сможем угадать, модель ни куда не годится. Не сможем - есть такая модель параллельного мира! Наконец-то мы ее создали, наконец-то создали модель реального мира! Вот, как-то так в первом приближении на примере RS-триггера. Создаем, конечно, еще другие модели и повторяем гадания. Находим реальный объект, который "колет" нашу модель - смотрим в чем дело, корректируем нашу модель.
Вот так "на пальцах" должен протекать научный процесс нахождения формальной модели окружающего нас параллельного (!) по своей сути реального мира. А Вы - "истинный GPU"... Это еще надо доказать, что он "истинный" Как? Я описал...
PS
Вопрос "на засыпку": В реальном мире есть мгновенные вычисления?
И, вообще, есть мгновенные вычисления? :)
Refridgerator
Скорость вычислений ограничены теорией относительности и скоростью света в частности. Но в программировании во многих случаях абстракция мгновенных вычислений допустима в том смысле, что она не влияет на результат. То ли дело схемотехника - неправильно развёл дорожки и вот она уже не работает просто потому, что одна дорожка оказалось короче другой.
lws0954 Автор
ключевое слово - допустима. Пример.
у = !(x1&&x2);
Допустимо? Да в полный рост.. Это модель мгновенного элемента И-НЕ (пример - см. логические элементы в SymInTech).
Смотрим на мгновенный триггер:
Q = !(R&&NQ);
NQ = !(S&&Q);
Допустимо? Почему бы и нет. Компилятор с его автоматами пропустит на ура. Но только все это лажа, т.к. мгновенных вычислений в природе нет. Ну, совсем. И проявится это в резултатах работы такого "триггера".
На все нужно время. На все! Даже на выполнение отдельной команды на уровне ассемблера.
Математики пишут у=а(х); Нормально? Да, в чем вопрос - нормально! Но на самом деле нормально было бы: y(t+1) = f(x(t)); Да, сожнее, да, необычно, но, черт возьми (прошу прощения), только так правильно!