Часть I. Конечные автоматы. Универсальная машина Тьюринга. Интерпретатор Brainfuck

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

(Серия: Сельскому учителю в помощь)

Оглавление

МОТИВАЦИЯ

▒▒▒▒▒▒▒▒▒█▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█
▒▒▒▒▒▒▒█░▒▒▒▒▒▒▒▓▒▒▓▒▒▒▒▒▒▒░█
▒▒▒▒▒▒▒█░▒▒▓▒▒▒▒▒▒▒▒▒▄▄▒▓▒▒░█░▄▄
▒▒▄▀▀▄▄█░▒▒▒▒▒▒▓▒▒▒▒█░░▀▄▄▄▄▄▀░░█
▒▒█░░░░█░▒▒▒▒▒▒▒▒▒▒▒█░░░░░░░░░░░█
▒▒▒▀▀▄▄█░▒▒▒▒▓▒▒▒▓▒█░░░█▒░░░░█▒░░█
▒▒▒▒▒▒▒█░▒▓▒▒▒▒▓▒▒▒█░░░░░░░▀░░░░░█
▒▒▒▒▒▄▄█░▒▒▒▓▒▒▒▒▒▒▒█░░█▄▄█▄▄█░░█
▒▒▒▒█░░░█▄▄▄▄▄▄▄▄▄▄█░█▄▄▄▄▄▄▄▄▄█
▒▒▒▒█▄▄█░░█▄▄█░░░░░░█▄▄█░░█▄▄█

Курс интенсива кратко и ясно даст новичку начала системной и компьютерной инженерии.
У курса 3 взаимосвязанные части: Исполнители программ, Языки и компиляторы, Автоматы и логика. Первая и вторая части – целое, без них программирование не имеет смысла. Третья часть будет интересна тем, кто работает с устройствами логики либо досконально овладевает предметом. Остальным её можно опустить.
Примеры даны в стандарте языка С99. Готовый код в репозитории: https://github.com/myfoundation/EvolutionaryEngineering/book_it_begins/

В паблик телеграмме «Ненормальное программирование», я веду школу и даю ссылки на интересные материалы по системному программированию. Новичкам, учащимся, и профи – добро пожаловать https://t.me/abnormal_programming .

ВСТУПЛЕНИЕ

Я практик и популяризатор языково-ориентированного программирования [1]. В нём задачи решают тройкой: доменная виртуальная машина VM, доменный язык программирования DSL и алгоритмы на нём.
В этом курсе удачными фрагментами разных заметок доступно объясним причины многообразия языков и преимущества их разработки. С теорией, историей и примерами.
Вся наша работа строится вокруг VM, DSL, EBNF, отношений и графов. Мы увидим, как эти объекты соединяют вместе, получая вычислители и программы.
В инженерном деле, как и в науке, ритм должен быть размеренным, а внимание к деталям – исчерпывающим. Строгая преемственность знаний важна не менее дисциплины мысли.

ЧАСТЬ I. КОНЕЧНЫЕ АВТОМАТЫ. УНИВЕРСАЛЬНАЯ МАШИНА ТЬЮРИНГА. ИНТЕРПРЕТАТОР BRAINFUCK.

ВИРТУАЛЬНЫЕ МАШИНЫ

░░░░░░░░░░░░░░░░░░░░░
░▀▄█▀█▀█▄▀░░███████░░
░░▀▀███▀▀░░░██▄█▄██░░
░█▀█████▀█░█▀█████▀█░
░█░█████░█░█░▄███▄░█░
░▀░▀█▀█▀░▀░▀░▀█▀█▀░░░
░░░░░░░░░░░░░░░░░░░░░

Виртуальная машина VM (Virtual Machine) – программная или аппаратная реализация математической модели FSM (Finite State Machine). Исполняет машинный код процессора или машинно-независимый код (байт-код, шитый код, p-код). Имеет цикл выбора и интерпретации команд.
Байт-код (Bytecode) – набор инструкций VM. Каждая занимает 1 байт (отсюда и название), за ней могут идти аргументы. Программу компилируют в промежуточный файл (например, .pyc для Python или .class для Java). VM читает инструкцию и выполняет соответствующую ей подпрограмму.
Программа шитом коде (Threaded Code) – это список адресов функций. Интерпретатор не «разбирает» байт-код через switch, а переходит по адресам функций в памяти, что быстрее байт-кода. Пример: язык Forth, интерпретаторы для ZX Spectrum.
P-код (Pascal Code / Portable Code) исторический предок байт-кода для языка Pascal. Это код для гипотетической стековой машины (P-machine). Идея: скомпилировать программу в P-код, и запускать на любом компьютере, написав для него крошечный эмулятор P-машины. Пример: UCSD Pascal.
VM может эмулировать аппаратное обеспечение (процессор, оперативную память RAM, жёсткий диск, BIOS). Идея VM лежит в основе ряда операционных систем, включая DEC VAX/VMS, IBM VM/CMS и её аналог времён СССР – СВМ [2].

РАЗДЕЛ: ИСТОРИИ И ИДЕИ VM

1. ГДЕ ПОЛЕЗНЫ ВИРТУАЛЬНЫЕ МАШИНЫ

Создание VM плодотворно:

1. Для запуска программ на не совместимом с их кодом оборудовании.

2. Для програмирования без доступа к оборудованию; для разработки и отладки оборудования до его изготовления.

3. Для создания HAL (Hardware Abstraction Level) – программного API независимого от деталей аппаратуры или операционных систем.

4. Для создания узкоспециальных языков и доменных VM.

2. ИСТОРИЯ MICROSOFT И ВИРТУАЛЬНЫЕ МАШИНЫ

История Microsoft начиналась с создания VM и языков программирования…
Ученикам школы Лейксайд в Сиэтле повезло. Это учебное заведение одним из первых ввело в программу компьютерный курс. В 1968 году, в мире доминировали крупногабаритные машины IBM и только появились первые мини-компьютеры. Решение предоставить школьникам возможность осваивать азы программирования было революционным.
Восьмиклассник Гейтс, математические способности которого уже хорошо были известны в школе, погрузился в изучение возможностей DEC PDP-10 (Programmed Data Processor модель 10) и вскоре стал настоящим асом, способным написать и прекрасную программу для автоматизации составления школьного расписания, и взломать систему безопасности компьютера (за что был отлучен от машины почти на год). Пол Аллен был его постоянным компаньоном. На PDP они изучали Fortran, Lisp и другие технологии.
Во время учёбы Билл и Пол разработали систему анализа дорожного трафика Traf-O-Data для продажи местным органам власти и правительствам штатов, чтобы экономить их деньги и время. Поперёк дороги устанавливались резиновые трубки. При проезде автомобиля трубка сжималась и создавала воздушный импульс. Импульсы сохранялись на перфоленте как данные о транспортном потоке. Вначале Аллен написал эмулятор процессора Intel 8008 на DEC, а Билл программу для обработки данных. Затем студент-электрик Пол Гилберт разработал для них компьютер (hardware) на Intel 8008, который обрабатывал перфоленты и формировал отчёты о загруженности дорог.
1974 году на компьютерном рынке появилось нечто небывалое – микрокомпьютер Altair на базе Intel 8080. Мирная жизнь рынка, где царили IBM и DEC, была нарушена маленькой компанией MITS из Альбукерке, предложившей Altair – машину для каждого. Она шла как комплект типа «сделай сам». Из него терпеливый пользователь с помощью паяльника мог получить довольно сложное в эксплуатации устройство.
Аллен, первым узнавший об Altair, понял, что такой шанс упускать нельзя. Он без труда убедил Гейтса начать работу над языком программирования для микрокомпьютера. Компаньоны позвонили главе MITS Эду Робертсу и сообщили, что имеют Бейсик, адаптированный для Altair. Робертс не счел это за розыгрыш. Он ждал подобных звонков, поскольку понимал, что его детище, несмотря на обрушившийся на него успех, настоятельно требует более совершенных инструментов управления, чем утомительное переключение тумблеров.
Итак, о существовании языка было заявлено фактически до начала разработки. Его будущие создатели понимали, что не могут упустить время и дать возможность конкурентам завязать отношения с MITS. Сложность была в том, что у разработчиков не было самого Intel 8080. Зато был опыт эмуляции чипа при работе над Traf-O-Data. Изучив техническое описание микропроцессора Intel и статью в журнале Popular Electronics, Гейтс и Аллен начали работу с создания эмулятора Аltair на PDP-10. После этого они приступили непосредственно к Бейсику, сообщив Робертсу, что реализация языка практически завершена. Разработка программного обеспечения для эмулятора, а не для реальной машины впоследствии будет часто практиковаться в проектах Microsoft.
Зимой 1975 года состоялась личная встреча Эда Робертса и Пола Аллена в Альбукерке. Аллен привез готовый Бейсик для машины, которую не видел в глаза. К удивлению Гейтса и Аллена их разработка сразу запустилась и прошла все испытания. Робертс был готов незамедлительно подписать договор. За интерпретатор BASIC друзья получали лицензионные отчисления.
Успех Бейсика для Altair помог Гейтсу принять окончательное решение: теперь его будущее было связано только с компьютерами. Он оставил Гарвард и отдался развитию собственной компании – Microsoft. Micro означало микрокомпьютеры, а Soft – программное обеспечение [3][4].

3. ИСТОРИЯ ОРИГИНАЛЬНОГО ПРОИГРЫВАТЕЛЯ ЧИПТЮН МУЗЫКИ

░░░░░░░░▄░█▀▀▀▀▀█▀█▀█▀▀▀█▀█▀▀▀█░▄░░░░░░░░
░░░░▄░█░█░█░█▀█░█░█░█▄░▀█░█░███░█░█░▄░░░░
▄░█░█░█░█░█▄█▄█▄█▄▄▄█▄▄▄█▄█▄▄▄█░█░█░█░█░▄
║░█░█░║░█░█░█░║░█░█░║░█░█░█░║░█░█░║░█░█░║
║░█░█░║░█░█░█░║░█░█░║░█░█░█░║░█░█░║░█░█░║
║░║░║░║░║░║░║░║░║░║░║░║░║░║░║░║░║░║░║░║░║
╚═╩═╩═╩═╩═╩═╩═╩═╩═╩═╩═╩═╩═╩═╩═╩═╩═╩═╩═╩═╝

«Физика» – объекты с поведением, обусловленным их внутренним устройством, влияние на которое человеком невозможно либо ограничено. Большинство процессов протекает в мире физики. Звук – один из них.
Чиптюн (chiptune) – музыка, синтезируемая компьютером. Параметры звуковой волны и шумового канала кодируют простыми формулами математики либо трекерами (программами для комбинации музыки из «семплов» – небольших фрагментов оцифрованного инструмента, голоса или иного звука) [5][6].
С 1970-х компьютерные взломщики добавляли в распространяемые ими программы бегущие строки, чиптюн и видеоэффекты называемые «демонстрациями». В своё время были популярны конкурсы по написанию «демок».
AY-3-8910 – микросхема 1978 года от General Instruments для синтеза звука и музыки. Установлена в десятки игровых консолей и домашних компьютеров, включая Sinclair ZX Spectrum 128К с 8 битным микропроцессором Zilog Z80 1976 года выпуска.
Ресурсы ZX Spectrum ограничены: Z80 адресует 64 КБ памяти, его тактовая частота 2,5 МГц. К ней привязаны скорость игр и музыки на Spectrum. Spectrum ценен тем, что не просто даёт азы ассемблера, а учит оформлять программы по образцу FSM и работать с CPU в режиме реального времени.
Стартуя Spectrum загружает из ПЗУ компактную операционную систему с консолью на языке BASIC. Из неё запускают программы на BASIC и в машинном коде.
Чип AY-3-8910 не знает ничего о нотах или мелодии, и получает от процессора последовательности команд: выбрать один из 3-х «каналов», установить на нём громкость и высоту колебаний звука. Программы шлют в чип поток таких команд, и звучит музыка.
Звуковые волны – это физика, и верные тайминги для них критически важны. Музыкальные проигрыватели для Spectrum – алгоритмы реального времени. Их тайминги высчитаны по таблицам команд и привязаны к частоте процессора Z80. Необходимо учесть эту особенность при замене алгоритма проигрывателя или CPU.
Форматы хранения музыки для Spectrum ориентированы на компактное хранение данных и их быстрый разбор. Писать проигрыватели под каждый формат долго и не познавательно. Есть и готовые FSM плееры под Z80.
Плеер Ayfly – это обёртка над доменной VM для проигрывания музыки в форматах PT3, AY, PSC, YM и др. VM эмулирует Z80 и AY-3-8910 и оформлена библиотекой на С. Для каждой загружаемой мелодии создается отдельный контекст со своей областью памяти, процессором Z80 и копией музыкального сопроцессора [7]. Машина перенесена на Windows, Unix, Arduino и её просто адаптировать для других нужд. Например, доработать и грузить в VM бинарный код любых существующих музыкальных плееров на Z80 или генерирующих звук программ.

4. БАЙТКОДОВАЯ VM В ZX SPECTRUM

█████████████▀▀█████▀▀█
█████████████░▄▄░░░▄▄░█
▀████▀█▀████▀▌╚╝░░░╚╝▐█
░╥░░╥░█░╥░░╥░█░┐░▄░┌░██
▌░░▄░▐█▌░░▄░▐▓▓▌═╧═▐▓▓█
└▄└┴┘██└▄└┴┘▓░▒░▒░▒░▒░█

Мы будем возвращаться к ZX Spectum. Это отличная простая система для изучения связки CPU, VM, DSL. Любая операционная система (OS) – это связка, надстройка, связывающая перечисленное воедино.
У Spectum 48 Кб памяти. 16 Кб из них – ПЗУ, где «зашит» использованный в качестве компактной OS интерпретатор BASIC, и байт-кодовая доменная VM.
Стандартные команды Z80 непригодны для задач тригонометрии или логарифмирования. Стековая виртуальная машина FP-VM в ZX Spectrum – элегантное решение, превращающее ограниченный 8-битный процессор в мощный математический инструмент.
FP-VM специализирована для арифметики с плавающей точкой (Floating Point Number). Её байткод размещают прямо в ассемблерном коде Z80 между инструкцией RST 28h и командой возвращения из байткода end-calc.

RST 28h ; Инструкция Z80      ...      ; байткод для FP-VM      ...  end-calc  ... ; Инструкции Z80  

Встретив RST 28h процессор Z80 помещает в стек (SP) адрес следующей за ней инструкции. Это стандартное поведение CALL и RST. Затем переключает выполнение на адрес #0028 – точку входа в интерпретатор байткода. Выполнив его Z80 вернётся к командам после end-calc.
Из байткода можно вызывать внешние подпрограммы на ассемблере Z80; выполнять операции над строками (конкатенация, сравнение). Операция VAL – парсер строковых математических выражений. Строит и обходит AST, учитывая стандартный математический приоритет.
Использование RST 28h вместо CALL продиктовано двумя инженерными факторами: минимизацией объема кода и скоростью его вызова: 1 байт в памяти RST против 3-х байт (код операции + 2 байта адреса) CALL и 11 тактов процессора против 17 соответственно. Использование прерывания подчеркивает, что эта VM – центральный узел системы, а не второстепенная подпрограмма.

ТАБЛИЦА КОМАНД FP-VM

-----+----------------+---------------------------------------------   КОД | МНЕМОНИКА      | ОПЕРАЦИЯ                                      -----+----------------+---------------------------------------------  УПРАВЛЕНИЕ И ПЕРЕХОДЫ  -----+----------------+---------------------------------------------   #00 | JUMP-TRUE      | Переход по смещению, если X != 0   #2D | FP-CALL        | Вызов внешней ассемблерной подпрограммы   #2F | JUMP           | Безусловный переход по смещению   #38 | END-CALC       | ТЕРМИНАТОР: Возврат в нативный режим Z80  -----+----------------+---------------------------------------------  СТЕКОВЫЕ ОПЕРАЦИИ И ДАННЫЕ  -----+----------------+---------------------------------------------   #01 | EXCHANGE       | Перестановка элементов (SWAP)   #02 | DELETE         | Удаление вершины (DROP)   #1A | READ-IN        | Ввод константы из потока данных   #30 | STK-DATA       | Загрузка 5-байтового Float   #31 | DUPLICATE      | Дублирование вершины (DUP)   #32 | N-STORE        | Запись в переменную (1 байт индекса)   #33 | N-RECALL       | Чтение из переменной (1 байт индекса)   #34 | STK-SHORT      | Загрузка 1-байтового целого  -----+----------------+---------------------------------------------  АРИФМЕТИКА И ФУНКЦИИ  -----+----------------+---------------------------------------------   #03 | SUBTRACT       | Вычитание   #04 | MULTIPLY       | Умножение   #05 | DIVISION       | Деление   #06 | TO-POWER       | Возведение в степень   #0F | ADDITION       | Сложение   #1B | NEGATE         | Смена знака (унарный минус)   #20 | ABS            | Модуль числа   #21 | SGN            | Знак числа   #22 | SQR            | Квадратный корень   #23 | INT            | Целая часть   #2E | N-MOD-M        | Остаток от деления  -----+----------------+---------------------------------------------  ТРАНСЦЕНДЕНТНЫЕ ВЫЧИСЛЕНИЯ  -----+----------------+---------------------------------------------   #24 | EXP            | Экспонента   #25 | LN             | Натуральный логарифм   #26 | SIN            | Синус   #27 | COS            | Косинус   #28 | TAN            | Тангенс   #29 | ASN            | Арксинус   #2A | ACS            | Арккосинус   #2B | ATN            | Арктангенс  -----+----------------+---------------------------------------------  ЛОГИКА И СРАВНЕНИЕ (FLOAT)  -----+----------------+---------------------------------------------   #07 | OR             | Логическое ИЛИ   #08 | AND            | Логическое И   #09 | LESS-THAN      | Меньше   #0A | GREATER-THAN   | Больше   #0B | NOT-EQUAL      | Не равно   #0C | LESS-EQUAL     | Меньше или равно   #0D | GREAT-EQUAL    | Больше или равно   #0E | EQUAL          | Равно  -----+----------------+---------------------------------------------  СТРОКОВЫЕ ОПЕРАЦИИ  -----+----------------+---------------------------------------------   #16 | STRS-APPEND    | Конкатенация (слияние) строк   #17 | VAL$           | Число в строку (оценка выражения)   #18 | VAL            | Строка в число (оценка выражения)   #19 | STR$           | Число в текстовый формат   #1C | CODE           | Код первого символа   #1D | CHR$           | Код в символ (строка длины 1)  -----+----------------+---------------------------------------------  СТРОКОВЫЕ СРАВНЕНИЯ  -----+----------------+---------------------------------------------   #10 | STR-LESS       | Меньше   #11 | STR-GREATER    | Больше   #12 | STR-NOT-EQ     | Не равно   #13 | STR-LESS-EQ    | Меньше или равно   #14 | STR-GR-EQ      | Больше или равно   #15 | STR-EQUAL      | Равно  -----+----------------+---------------------------------------------  ПЕРИФЕРИЯ И ПАМЯТЬ  -----+----------------+---------------------------------------------   #1E | PEEK           | Чтение байта из ОЗУ   #1F | IN             | Чтение из порта Z80   #2C | PRINT-FP       | Вывод значения на терминал  -----+----------------+---------------------------------------------  БЫСТРЫЕ КОНСТАНТЫ (ЛИТЕРАЛЫ)  -----+----------------+---------------------------------------------   #A0 | CONST-0        | 0.0   #A1 | CONST-1        | 1.0   #A2 | CONST-0.5      | 0.5   #A3 | CONST-PI/2     | 1.57079...   #A4 | CONST-10       | 10.0  -----+----------------+---------------------------------------------  

Пример программы: взять sin от числа 45 и умножить на (1+2)*(-3/4). Ожидаем на экране -1.60.

ORG #8000    START:      ; КОД ДЛЯ Z80      RST 28h           ; Запуск виртуальной машины      ; КОД ДЛЯ ВИРТУАЛЬНОЙ МАШИНЫ      ; 1. КОНВЕРТИРОВАТЬ: СТРОКА->ЧИСЛО      DEFB #2D          ; FP-CALL: Вызов подпрограммы Z80      DEFW PREP_EXPR_1    ; Адрес подпрограммы (Little-endian)      DEFB #18          ; VAL: "45" -> 45.0        ; 2. ПЕРЕВЕСТИ: УГОЛ->РАДИАНЫ      DEFB #30, #EE, #3E, #22, #4F, #30 ; Константа PI/180 (0.017)      DEFB #04          ; MULTIPLY: 45 * 0.017 -> 0.79      DEFB #26          ; SIN: sin(0.79) -> 0.71            ; 3. ВЫЧИСЛИТЬ: МАТЕМАТИЧЕСКОЕ ВЫРАЖЕНИЕ, ДАННОЕ СТРОКОЙ      DEFB #2D          ; FP-CALL: Вызов подпрограммы Z80      DEFW PREP_EXPR_2    ; Адрес подпрограммы      DEFB #18          ; VAL: "(1+2)*(-3/4)" -> -2.25      ; 4. УМНОЖИТЬ 2 ЧИСЛА НА СТЕКЕ VM      DEFB #04          ; MULTIPLY: 0.71 * -2.25 -> -1.60      ; 5. ВЫВЕСТИ РЕЗУЛЬТАТ НА ЭКРАН      DEFB #31          ; DUPLICATE: копирование результата (если нужен далее)      DEFB #2C          ; PRINT-FP: Вывод на экран числа на стеке VM -> -1.60      DEFB #38          ; END-CALC: Выход        ; КОД ДЛЯ Z80      RET               ; Конец программы    ; --- ПОДПРОГРАММА ПОДГОТОВКИ ПЕРВОГО ДЕСКРИПТОРА СТРОКИ ---  PREP_EXPR_1:      LD DE, STR_ANG    ; "45"      LD BC, 2          ; Длина строки в байтах      CALL #2AB1        ; Дескриптор на стек калькулятора      RET               ; Возврат в VM через RET    ; --- ПОДПРОГРАММА ПОДГОТОВКИ ВТОРОГО ДЕСКРИПТОРА СТРОКИ ---  PREP_EXPR_2:      LD DE, STR_EXPR   ; "(1+2)*(-3/4)"      LD BC, 12         ; Длина строки в байтах      JP #2AB1          ; Прямой переход на STK-STORE и возврат в VM через RET    ; --- БЛОК ДАННЫХ ---  STR_ANG:  DEFB "45"  STR_EXPR: DEFB "(1+2)*(-3/4)"  

5. FORTH: DSL, VM И RTOS ДЛЯ УПРАВЛЕНИЯ РАДИОТЕЛЕСКОПОМ

                                   /\                                /\  //\\                         /\    //\\///\\\        /\                        //\\  ///\////\\\\  /\  //\\           /\          /  ^ \/^ ^/^  ^  ^ \/^ \/  ^ \          / ^\    /\  / ^   /  ^/ ^ ^ ^   ^\ ^/  ^^  \         /^   \  / ^\/ ^ ^   ^ / ^  ^    ^  \/ ^   ^  \       *        /  ^ ^ \/^  ^\ ^ ^ ^   ^  ^   ^   ____  ^   ^  \     /|\       / ^ ^  ^ \ ^  _\___________________|  |_____^ ^  \   /||o\      / ^^  ^ ^ ^\  /______________________________\ ^ ^ \ /|o|||\     /  ^  ^^ ^ ^  /________________________________\  ^  /|||||o|\    /^ ^  ^ ^^  ^    ||___|___||||||||||||___|__|||      /||o||||||\   / ^   ^   ^    ^  ||___|___||||||||||||___|__|||          | |  / ^ ^ ^  ^  ^  ^   ||||||||||||||||||||||||||||||oooooooooo| |ooooooo  

О RTOS

Forth – это не просто язык, это микро-RTOS.
RTOS (Real-Time Operating System) – операционная система, с точно заданным и наперёд рассчитанным временем выполнения алгоритмов. RTOS ставят там, где требуется точно выдерживать биекцию между объектами физической среды и вычислителями. (Промышленные роботы: точность движений требует строгого соблюдения таймингов. Медицинское оборудование: аппараты ИВЛ или кардиостимуляторы. Космические аппараты. Автопилоты и тормоза ABS.) В RTOS точно известно сколько микросекунд займет поворот мотора, реакция на нажатие кнопки или сигнал датчика. При появлении критической задачи, RTOS ставит текущую на паузу и переключает процессор на важную (по приоритетам).
Для задач, где ошибка в 1 миллисекунду означает потерю управления (наведение телескопа, стабилизация спутника), RTOS – безальтернативное решение.

ИСТОРИЯ FORTH

                                                       ..       :                      .                  .               .   .  .        .           .                .               .. .  .  *               *          .                    ..        .                             .             .     . :  .   .    .  .              .                         .   .  .  .   .                                           . .  *:. . .  .                                 .  .   . .. .         .                           .     . .  . ...    .    .         .              .  .  . .    . .  . .                          .    .     . ...   ..   .       .               .                   .  .    . *.   . .      .                   :.  .           .                   .   .    .    .               .  .  .    ./|\              .  .. :.    . |             .               .       .   ... .            |   .    :.  . .   *.        |     .               .     .  *.             You are here.   . .    .               .             *.                         .  

В техническом понимании 1960-х VM – это программно-аппаратная прослойка из системы команд (Instruction Set Architecture), для изоляции логики алгоритма от физики и ограничений железа. VM даёт многобайтную арифметику, обработку динамических строк, управление структурами данных, которых нет в базовом CPU кристалле.
Состав VM: регистр-указатель на текущую инструкцию байт-кода (PC), регистр-указатель на вершину стека (SP), узел выборки и декодирования инструкций (Fetcher), и набор подпрограмм в кодах целевого процессора.
Радиотелескоп требует жесткого временного регламента (Hard Real-Time). Система одновременно: переводит небесные координаты в азимутальные, управляет сервомоторами, регистрирует сигналы с радиометра. 11-метровый радиотелескоп Национальной радиоастрономической обсерватории (NRAO) в Китт-Пике (США, Аризона) был как раз таким телескопом.
У компиляторов 1960-х (FORTRAN, ALGOL) длительный цикл подготовки перфокарт, а у программ – медленное взаимодействие с оборудованием. Они не годятся для задач, критичных к времени.
В 1950-х Чарльз Мур, работая в MIT, затем в Stanford, разрабатывал личную библиотеку для эффективного программирования. В 1968 г. её прототип Forth (или «Версия 4») перенесен на IBM 1130.
В 1971 г. Мур перешел в NRAO. Перед инженером стояла задача управления радиотелескопом. ЭВМ телескопа (DDP-116, Honeywell) имели ничтожный объем ОЗУ. Мур встроил в Forth элементы автономной операционной системы и передал управление телескопом стековой машине.
Вся система управления, включая драйверы и математический аппарат, заняла 8 КБ ОЗУ, скорость реакции на внешние события составила микросекунды. При этом сохранялась читаемость алгоритмов. Успех управления телескопом Forth заложил стандарт для космических технологий. Forth стал инструментом прямого контроля над физической реальностью
В 1973 г. Мур и Элизабет Разер основывали Forth Inc, и внедряли Forth в проекты от автоматизации заводов до миссий NASA. В 1985 г. создан первый процессор Novix NC4016 для Forth. В 1994 г. корпорация Sun Microsystems интегрирует Forth в базовую прошивку (Firmware) для рабочих станций SPARC (Open Boot, IEEE 1275).

FORTH В ЭВМ СПЕЦНАЗНАЧЕНИЯ, ПРОЕКТЫ НАСА [8]

------+-----------------------+-----------------+----------------------------   ДАТА | ПРОЕКТ / ОРГАНИЗАЦИЯ  | АППАРАТНАЯ БАЗА | ЦЕЛЕВАЯ ФУНКЦИЯ  ------+-----------------------+-----------------+----------------------------   1971 | Телескоп Китт-Пик     | DDP-116 (16-bit)| Наведение, сбор радиометрии   1976 | Проект Viking (NASA)  | Custom Logic    | Анализатор грунта (GCMS)   1986 | Миссия Giotto (ESA)   | RCA 1802        | Анализ пылев. хвоста кометы   1989 | Миссия Galileo (NASA) | RCA 1802        | Плазменный спектрометр (PLS)   1994 | Clementine (BMDO)     | RTX 2000        | Навигация, картография Луны   1997 | Cassini (NASA/ESA)    | RTX 2000        | Анализатор космической пыли   1998 | Deep Space 1 (NASA)   | RTX 2000        | Модуль телеметрии и связи   1999 | Mars Polar Lander     | RTX 2000        | Лидар (поиск льда на полюсе)   2004 | Rosetta / Philae      | RTX 2010        | Управл. посадочным модулем  ------+-----------------------+-----------------+-----------------------------  

РЕЕСТР КОРПОРАТИВНЫХ И ВОЕННЫХ ВНЕДРЕНИЙ FORTH [8]

--------+--------------------------+------------------------------------------   ПЕРИОД | ОРГАНИЗАЦИЯ / КОРПОРАЦИЯ | ЦЕЛЕВАЯ ФУНКЦИЯ И ОБЪЕКТ УПРАВЛЕНИЯ  --------+--------------------------+------------------------------------------   1970-е | Mohasco Industries (USA) | Управление инвентаризацией и БД складов   1978   | US Navy (ВМС США)        | Навигационный приемник LONARS (Loran-C)   1980-е | FedEx                    | Ручные терминалы сбора данных (Handhelds)   1980-е | Chrysler Corporation     | Системы диагностики и контроля двигателей   1985   | Lockheed Martin          | Контроллер "умных" антенн (Smart Antenna)   1990   | US Air Force (ВВС США)   | Управление питанием и данными (APEX)   1994   | Sun Microsystems         | Firmware OpenBoot (IEEE 1275) для SPARC   2000-е | GE Digital Energy        | Оптические мультиплексоры связи (SONET)   2002   | Northrop Grumman         | Системы датчиков позиционирования (SBIRS)   2005   | Radeus Labs              | Контроллеры наземных спутниковых станций  --------+--------------------------+------------------------------------------  

6. MAME, CUMM

Multiple Arcade Machine Emulator (MAME) – opesource эмулятор тысяч аркадных автоматов, игровых консолей, старых компьютеров [9].
MAME полезен в исследовании и обучении. В него встроен дизассемблер и отладчик для сотен процессоров и мультипроцессорных систем. Коллекции игр и BIOS с ПЗУ автоматов, дисков и кассет доступны в ROM файлах в Интернет. [mame-1]
CUMM – DSL и доменная VM фирмы LucasArts для управления локациями, предметами, диалогами в графических играх. Авторы: Арик Уилмундер и Рон Гилберт, 1987 год. CUMM перенесена на: 3DO, Apple II, Atari ST, Amiga CDTV, Commodore 64, Macintosh, NES, MS-DOS, Microsoft Windows, Sega Mega CD и др. В 1998 году LucasArts перешла на доменную VM GrimE, сохранив наработки прародителя, и популяризовав встроенный язык Lua [12].

РАЗДЕЛ: КОНЕЧНЫЕ АВТОМАТЫ

1. МАШИНЫ ТЬЮРИНГА

██████████████████████
██▀▀▀▀▀██▌╦═╗╔═╗╔═╗▐██
█▌░▀░▀░▐█░╠═╣║░║║░║░██
█▌░░█░░▐▄░╩═╝╚═╝╚═╝▐██
█▌░░░░░▐██▄▄▄▄▄▄▄▄▄███
██▄█▄█▄███████████████

Эпоха индустриализации, 1930-1940-е. В тиши кабинетов, заваленных черновиками с математическими выкладками, и в грохоте цехов, где реле отбивают такт новой эры, математики и инженеры создают «вычислители» – машины для обсчёта конструкций гигантских строек и промышленных предприятий.
Алан Тьюринг создал первый чертеж CPU (Central Processing Unit). На практике «Машины Тьюринга» нет, а есть множество автоматов, собранных по чертежу этой машины.
Машина Тьюринга (МТ) – не «головка и лента с буквами», а спецификация CPU с памятью – RAM либо стеком [13]. В буквальном смысле это инженерно-математический чертёж процессора Intel 8086, Zilog Z80 или Java VM. Объясним его на оболочковой модели.
Оболочковая модель сочетает: иерархию (надстройка слоя над предыдущим), изоляцию сложности (функционал распределен слоями), и локализацию (ограничение) сложности. Ей описывают строение звёзд, биологических клеток, отношение логики и модулей в автоматах, и так далее.

                     Automata theory+-------------------------------------------------------+| Turing Machine                                        ||   +-----------------------------------------------+   ||   | Pushdown automaton                            |   ||   |   +---------------------------------------+   |   ||   |   | Finite-state machine                  |   |   ||   |   |   +-------------------------------+   |   |   ||   |   |   |                               |   |   |   ||   |   |   |      Combinational logic      |   |   |   ||   |   |   |                               |   |   |   ||   |   |   +-------------------------------+   |   |   ||   |   +---------------------------------------+   |   ||   +-----------------------------------------------+   |+-------------------------------------------------------+

1. Оболочка Вычислительное Ядро (Combinational Logic) реализует доменные математические операции (плюс, умножить, поделить, итд). Ядро расположено в «головке» машины. У ядра нет памяти; оно лишь преобразует входные сигналы в выходные. В CPU это Арифметико-логическое устройство ALU (Arithmetic Logic Unit). В VM это доменные операции (сложение, сравнение) над операндами на вершине стека.

2. Оболочка FSM (Finite-State Machine) – пространство состояний машины, данное отношением [14] над элементарными множествами или эквивалентным графом [15]. FSM или Конечный автомат – этап перевода математики в физику. Это математическое описание пространства состояний объекта пятёркой FSM = (S, X, Y, s0, δ) [16]. Её назначение быть чертёжом (спецификацией) для инженера, стоящего соответствие «объект математики – объект физического мира». Это этап, где частям предмета ставят в соответствие элементы математических конструкций. Можно сказать, после прохождения этого этапа, предмет реализует математику (становится её носителем). В оригинальной машине таблицу переключения состояний задают блоком переключателей (реле), управляющих моторами и головкой машины по жесткому алгоритму. В CPU место этих устройств занял микрокод – внутренние команды процессора, управляющие физикой «логических вентилей» и «сигнальных линий». Каждая ассемблерная инструкция запускает исполнение цепочки микрокоманд, переключающих физические состояния процессора.

3. Оболочка PDA (Pushdown Automaton) или Автомат с магазинной памятью [17] – это третья оболочка вычислителя. Расширяет возможности FSM добавлением внешней стековой памяти LIFO [18]. С ней автомат имеет команды «push/pop» и соответствует автомату со стеком. PDA = (S, X, Y, s0, δ, Γ, Z), где Γ (Stack Alphabet) собственный алфавит для стека (не путать с входным алфавитом), а Z – маркер дна стека. У FSM память хранит только номер состояния. FSM может распознавать регулярные выражения (например, abc*), но не может проверить вложенность. У PDA память = состояние + стек LIFO. В стек можно класть данные наверх и забирать сверху, что уже позволяет реализовать контекстно-свободные языки (например, C).

4. «Лента Тьюринга» – это память с произвольным доступом RAM (Random Access Memory) [19]. Команды «головке» «перейти влево/вправо», «считать/записать в ячейку ленты» аналог команд CPU для доступа к RAM. Линейно-ограниченный автомат LBA (Linear Bounded Automaton) – это машина с конечным объёмом RAM [20]. RAM – элемент машины «архитектуры Фон Неймана» [21] – быстрое и удобное хранилище данных. В теории размер RAM имеет k*n ячеек памяти, где k – константа, заложенная в конструкцию автомата, n – длина входных данных для обсчёта на LBA. На практике RAM ограничена памятью машины. Инженерно любая реальная машина это LBA.

5. Оболочка TM («Turing machine»), означает, что совокупно конструкцию, описанную пунктами 1-4 называют «Машина Тьюринга». Это оболочка локализует («вмещает») все другие, и работа со всей конструкцией идёт через неё. Алгоритмы, которые можно вычислить на конкретной МТ, называют «вычислимыми по Тьюрингу» для данной машины (ибо см. пункт №1 — вычислительные операции у разных машин рознятся). Для запуска алгоритма и аппаратуры необходимо определить и просчитать пространство состояний [22] дискретного автомата. Для этой математической задачи достаточно начал элементарной теории множеств (ввести множества, определить отношение над ними, взять декартово произведение, посчитать мощности множеств). «Время» для FSM разбито на дискретные шаги: состояние автомата меняется не плавно, а мгновенно («скачком»). Переход происходит строго в определенные моменты: по сигналу тактового генератора (в синхронных схемах), либо по наступлению события/ввода символа. Между этими шагами (тактами) система находится в покое, и промежуточных состояний не существует. Тактовый генератор заставляет CPU постоянно проверять вектор входных сигналов и переходить к следующему состоянию. Логические затворы (транзисторы) физически пропускают или блокируют ток в момент прихода тактового импульса: входной вектор сигналов «протекает» через логику в момент такта. Если на входе нет сигналов, CPU выдаёт на выход сигнал «пусто» (физически значения в регистрах остаются прежними) и ожидает следующего импульса от генератора. Этот же генератор заставляет работать сообща все узлы автомата. Без единого ритма сигналы от разных его частей приходили бы в разное время, что вызвало бы хаос и ошибки в вычислениях. Тактовая частота задает момент, когда все части схемы должны одновременно перейти к следующему шагу (состоянию). Можно встретить бесплодные дискуссии и софистику о «полноте языка по Тьюрингу» или «бесконечности ленты». Они не имеют прикладного значения. Машина Тьюринга – это спецификация вычислителя. Она учит нас, что любой вычислитель есть совокупность логического ядра, графа состояний и механизмов доступа к памяти. Понимая эту преемственность инженер видит не нагромождение абстракций, а стройную и лаконичную схему, созданную на заре компьютерной эры.

2. МАТЕМАТИКА КОНЕЧНОГО АВТОМАТА ДЛЯ ИНЖЕНЕРА

░░░░░░░░░░░░░▄▄██████▄▄▄░░░░░░░░░░░░░░░░
░░░░░░░░░░░▄██▀░░░░░▀▀▀██▄▄░░░░░░░░░░░░░
░░░░░░░░░░▄██░░██░░░▄▄░░░▀██▄░░░░░░░░░░░
░░░░░░░░░░██░▄████▄███░░░░░▀██▄░░░░░░░░░
░░░░░▄▄▄▄██████▄▄█▀▀██░░░░░░░██▄░░░░░░░░
░░▄██████░░░▀▀▀▀██████░░░░░░░░▀██░░░░░░░
░░▀▀▀▀▀█████▄▄░░░░▀▀██▄▄░░░░░░░▀██░░░░░░
░░░░░░░██░░▀▀███▄░░░░░▀██▄░░░░░░▀█▄░░░░░
░░░░░░▄██░██░░░▀▀██▄▄░░░▀██▄░░░░░██▄░░░░
░░▄███▀█████░░░░░▄▄▀▀████████▄░░░░▀▀██▄░
▄██░░░░░░░▀██▄░░▄█▀░░░░░░███▀██░░░░░░▀██
██░░░░░░░░░░░░░░▀▀░░░░░▄▄█▀░░███▄▄░░░░██
▀█▄░░░░░░░░░▄████████░███░░▄██▀▀▀▀██▄▄██
░▀██▄▄░░░░▄▄██░░░░▄██░░█████▀░▄▄▄░░▀██▀░
░░░▀██████▀▀▀░░████▀░░░░░░░░░██▀░░░░██░░
░░░░██░░▄▄░░█▄▄███▄░░░░░░░░░░▀▀░░░░▄██░░
░░░░▀█████████▀▀░██░░░░░░░▄██▄▄▄▄▄██▀░░░
░░░░░░░░░███▀██▄▄██░░░░░▄██▀▀▀▀▀▀▀░░░░░░
░░░░░░░░░░▀██▄▄▀▀▀░░░▄██▀▀░░░░░░░░░░░░░░
░░░░░░░░░░░░░▀▀██████▀▀░░░░░░░░░░░░░░░░░

Математически концепция FSM (Finite State Machine) это способ задания отношения δ (или связей) над элементами трёх элементарных множеств S, X, Y. Рассмотрим их последовательно.
Множества – S, X, Y задают простым перечислением их элементов.
«Входной алфавит» X – перечень всех возможных внешних воздействий. Инженерный эквивалент: список сигналов от всех кнопок и датчиков.
Множество состояний машины S – перечень всех устойчивых положений, в которых может замереть механизм. Начальное состояние s₀ – конкретный элемент из множества S, в котором механизм находится после подачи питания или нажатия кнопки «Сброс».
У автомата могут быть переходы по состояниям S, специфичные для его конструкции, и бесполезные извне. F – это подмножество S, называемое «финалами». В практике по достижении любого состояния из F автомат выдаёт соответствующий ему сигнал из Y внешнему исполнительному механизму. Это способ дополнительной маркировки нужных нам (или «полезных») состояний. Инженерный эквивалент: машина наливает лимонад или загорается лампочка. В стандартной математической модели выходной сигнал y ∈ Y определяют для каждого состояния s∈ S . Если в каких-то состояниях «ничего не происходит», считают, что автомат выдает «пустой сигнал» или «символ ε». В наших реализациях FSM будет такой подход.
Функция переходов (или отображение) δ задана как δ:S×X→S [23]. Декартово произведение × значит, что мы строим все возможные пары из элементов множеств S и X и ставим каждой паре в соответствие элемент из множества S. Инженерно это значит, что каждому текущему состоянию машины и входящему сигналу мы ставим в соответствие новое состояние машины (и выходной сигнал).
Декартово произведение задают таблицей [24]. Пересечение строки с обозначением текущего состояния и столбца с обозначением входного сигнала даст следующее состояние. В примере это (s2,C)->s1.
«Символ» – это знак (буква или цифра) обозначающая сигнал, «алфавит» – конечное множество «сигналов».

                     выбрать входной сигнал                                  |                                  V  +--------------+------+------+------+--------+  | СОСТОЯНИЯ S  | ВХОДНОЙ АЛФАВИТ X (Сигналы) |  +--------------+------+------+- ----+--------+  |              |  A   |  B   | [C]  | D      |  +--------------+------+------+------+--------+  |    s1        |  s2  |  s1  |  s1  | s1     |  +--------------+------+------+------+--------+  |   [s2]       |  s2  |  s3  | [s1] | s1     |  <--- выбрать текущее состояние  +--------------+------+------+------+--------+  |    s3        |  s3  |  s3  |  s4  | s1     |  +--------------+------+------+------+--------+  |    s4        |  s1  |  s1  |  s1  | s1     |  +--------------+------+------+------+--------+  

Математическая запись FSM = (S, X, Y, s0, δ) – это чертеж логических связей. Задача инженера – обеспечить, чтобы ни один сигнал не привел к состоянию, не описанному в таблице δ.
Спидометр – классический пример каскадного соединения конечных автоматов. Каждое цифровое колесо это независимая FSM. Переход в финальное состояние одного автомата служит входным сигналом для следующего.

Множества для FSM «Спидометр»  X (Вход, множество)= { «ПОВОРОТ» (механический толчок колеса) }  Y (Выход, множество) = { «ПУСТО», «ПОВОРОТ» }  S (Состояния, множество) = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}  s0 (Начальное состояние, элемент множества S) = 0  δ = FSM-таблица, где при смене состояний 9->0 автомат генерирует импульс «ПОВОРОТ» для следующего FSM в цепочке, для иных смен состояний генерирует – «ПУСТО».  

3. КОНЕЧНЫЙ АВТОМАТ ГЛАЗАМИ ИНЖЕНЕРА-КОНСТРУКТОРА

_________▄██✿███▄
_______ ▄██▀██████▄
______██▀__███▒████
_____██____███░░ٮ░▀
______██____██░░░░░
_______██____██░░♥ _ (❀✿❀)
________█_____█▒ ___ (✿ ☼ ✿)
_________█___▓▓░▓ ___ (❀▐ ❀)
____█❀ _█_▓▓▓▒░▒▓ __█_▐__▄
_____▀█▀_▓▓_▓▓▒░▒▓ ▀█▐_█
_________▓▓_▓▓▓▓▓▓ ____ ▐▀
_________▓▓_▓▓▓▓▓ ______ ▐
_______▓▓__▓▓▓▓_▓▓ ____ ▐░
______▓▓__▓▓▓▓▓___▓ ___ ▒▒
_____▓▓_▓███❋██▓__▓▓▓
___▒▒___▓██▒███▒▓
___░___▓██▒███▒██▓
______▓██▒███▒███▒▓
_____▓██▒███▒███▒██▓
_____▓█▒███▒███▒███▒▓
▓___▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓________▒░░░▒░░░▒
▓________▒░░░▒░░░▒
▓________▒░░▒_▒░░░▒
▓________▒░░▒__▒░░░▒
▓________▒░░▒__▒░░░▒
▓________▒░░▒__▒░░░▒
▓________▒░░▒▒░░░▒
▓▄▄▄▄▄▄▒░░▒░░▒
▓██████▒░░▒▒
▓_█❤█___███
▓███____███
▓█_______███
▓________██❥█
▓________██▀██▄

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

3.1 Состояние: в математике и в инженерии

В теории конечных автоматов состояние (state) – это абстрактная внутренняя переменная системы, аккумулирующая в себе всю необходимую информацию о прошлом пути устройства для определения его будущего поведения.
Для инженера, состояние – это фиксированная конфигурация исполнительных механизмов, в которой система стабильна и ожидает внешнего воздействия. В электромеханике 1960-х состояние материально: это либо конкретный угол поворота вала шагового искателя, либо специфичная комбинация замкнутых и разомкнутых реле.

3.2 Документирование структуры: Таблица как «отношение»

Для строгого описания логики автомата инженер обязан составить «отношение».
В математике «отношение» – это способ задать связи над элементами множеств. Для нас это означает, что каждому сочетанию «Состояние + Сигнал» мы ставим в однозначное соответствие пару «Новое состояние + Действие».
Можно использовать две эквивалентные формы записи этого отношения:
– табличная форма (матрица): идеальна для проверки полноты (нет ли пропусков или «дыр» в логике)

    ТАБЛИЦА ЛОГИЧЕСКИХ СВЯЗЕЙ "АВТОМАТ-МТ"      +-----------+-----------+-----------+------------+      |  ТЕКУЩЕЕ  |  ВХОДНОЙ  | СЛЕДУЮЩЕЕ |  ВЫХОДНОЙ  |      | СОСТОЯНИЕ |  СИМВОЛ   | СОСТОЯНИЕ |   СИМВОЛ   |      |   (S_n)   |   (In)    |  (S_n+1)  |   (Out)    |      +-----------+-----------+-----------+------------+      |     0     |     М     |     1     |     A0     |      |     1     |     О     |     0     |     A7     |      |    ...    |    ...    |    ...    |    ...     |      +-----------+-----------+-----------+------------+  

далее такие таблицы мы называем «таблица, пакующая FSM» или просто «FSM-таблица»

– графическая форма (граф): наглядна для понимания маршрутов тока.
Узлы графа – это элементы множества состояний (S), ребра (стрелки) – связи, соответствующие входным символам (In). Инженер должен уметь мгновенно конвертировать ребро графа в электрическую цепь и обратно.
Заполнение этой таблицы первично. Пока отношение не зафиксировано на бумаге в 4-х столбцах, приступать к сборке изделия запрещено. Отсутствие формального отношения ведет к хаосу в межагрегатных связях.

3.3 Циклограмма работы

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

state = BEGIN;                  // Установка механики в начальное состояние  while (state !== END)           // Пока не достигнута цель или сбой  {      in = getSignal();           // Ожидание замыкания входного контакта      step = machine[state][in];  // Выбор строки в таблице отношений      execute(step.action);       // Подача тока на исполнитель (Out)      state = step.next;          // Физический переход в новую фазу  }  

Для инженера 1960-х термины «фаза», «позиция» и «состояние» – синонимы. Под «переход в новую фазу» понимают физическое перемещение системы, соответствующее следующей точке пространства состояний, определенного таблицей. Это подчеркивает временной аспект: автомат находится в определенной стадии (фазе) технологического цикла.
Пока «переход в новую фазу» не завершен физически (вал не довернулся, реле не защелкнулось), система находится в состоянии неопределенности. Если в этот момент пропадет питание, автомат «зависнет» между состояниями. Хорошая инженерная подготовка подразумевает умение настраивать механизмы так, чтобы фаза менялась быстро и четко. Для этого время машины разделят на дискретные шаги, а неопределенность исключают конструктивно.

3.4 Физический смысл перехода (S_curr → S_next)

Инженер должен различать и отслеживать два независимых одновременных процесса: математический акт смены индекса S_curr → S_next и соответствующая ему смена физической конфигурации машины.
В логическом объекте происходит перезапись значения переменной state. Старое число стирается, новое записывается. В физическом объекте (машина): мотор перемещает узел агрегата.

    СХЕМА РАЗГРАНИЧЕНИЯ ПЕРЕХОДА (МАТЕМАТИКА И ФИЗИКА)      --------------------------------------------------            МАТЕМАТИЧЕСКИЙ ПЛАН (М):   { S_0 }  --( In )-->  { S_1 }                                   ^                      ^      БИЕКЦИЯ (Перенос):           | [ВЗАИМНО-ОДНОЗНАЧНО] |                                   v                      v      ФИЗИЧЕСКИЙ ПЛАН (P):       [УГОЛ 0] --( Ток )--> [УГОЛ 1]            ОПРЕДЕЛЕНИЕ: "Переход в новое состояние" в металле – это       изменение положения частей механизма  

3.5 Заполнение Таблицы логики переходов и выходов автомата

Чтобы превратить физический объект в цифры таблицы, инженер проводит процедуру дискретизации и индексации.
Шаг 1: Идентификация стабильных фаз (дискретизация). Инженер наблюдает за циклом работы и выделяет моменты, когда машина прекращает движение. Каждая такая фаза – кандидат в «состояние».
Шаг 2: Присвоение индексов (нумерация). В математике нет понятий «гудит» или «горит». Каждой фазе присваивают уникальный целый индекс S ∈ {0,1,2,...}.
Таблицу Шага 1 составляют по правилам:

1. Два разных состояния называют неразличимыми (эквивалентными), если при подаче на вход одинаковых символов автомат выдает одинаковый выходной сигнал и переходит в следующее одинаковое (или признанное эквивалентным) состояние. Неразличимые состояния исключают.

    ПРОТОКОЛ МИНИМИЗАЦИИ      --------------------------------------      ИСХОДНАЯ ТАБЛИЦА:         |    ОПТИМИЗИРОВАННАЯ:      S1 + [In] -> [Sk], [Out]  |          S2 + [In] -> [Sk], [Out]  |    S_new + [In] -> [Sk], [Out]      --------------------------|----------------------------      ВЫВОД: S1 и S2 заменяют одним узлом S_new.  

2. В таблицу вводят неявный входной символ F (Fault – сбой) с высшим приоритетом. Его подают датчики, следящие за целостностью автомата. При появлении символа F автомат блокируется. При старте машина запускает алгоритм самодиагностики, для проверки целостности узлов.

    МАТРИЦА АВАРИЙНЫХ ПЕРЕХОДОВ      +--------+------+--------+--------+      | Текущ. | Вход | След.  | Выход  |      | сост.  | (In) | сост.  | (Out)  |      +--------+------+--------+--------+      |  ANY   |  F   |  ERR   | BLOCK  |      +--------+------+--------+--------+  

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

    СХЕМА АППАРАТНОГО ПРИОРИТЕТА      ----------------------------            [ ИСТОЧНИК ТОКА ]             |      +-----( )----- [ ДАТЧИК "В" (ВЗЛОМ) ] ----> В цепь ERR (Высший приоритет)             |      +-----( )----- [ ДАТЧИК "Т" (ФРОД) ]  ----> В цепь возврата/тревоги             |      +-----( )----- [ ДАТЧИК "М" (МОНЕТА) ] ----> В цепь счета (S1, S2)             |      [ НИЗШИЙ ПРИОРИТЕТ ]  

4. КОНЕЧНЫЙ АВТОМАТ ГЛАЗАМИ ИНЖЕНЕРА-НАЛАДЧИКА

▄█████████▄
▄█████████████▄
██▀■■░■■░░▀█████
░█▀■░■■░■■■■░■████
█░░■■▄▄████▄▄▄■■░███
█■▄████████░███■■░███
█░███▀▒░██░░▄▄██■■░██
█■███▄▄░░█░░░̳.̳̳.̳.̳̳.░█■░██
███▓░̳.̳̳.̳.̳̳.░░░░██▀░░█■██
███▒██▀░░░░▒▒░░░█▒██
██▒▒░░▒▄░░░░░░░▒▒███
███▒▒░░░░░░░░░▒▒████
█■■██▒▒▒█▓▀░░░▒▒▒███
█■██■██▒▒░░░░░▒▒░▒██▄
■███■■███▒▒▒▒▒░░░▒███
█████■█████▒▒░░░░▒██▀
▓███▒▒▒▒▒▓███░▒▒█████
███▒░░░░░▒▓██▒▒██▓██
██▒░░░░░░▒▒▓█▒▒████
██▒░░░░░░▒░▒▓░▒██
█▒░░░░░░░▒░░░█▓▓▓
█▒░░░░░░░▒░░█▓▓▓▓▓
░▒░░░░░░░▒░█▓▓▓▓▓▓▓
░▒░░░░░░▒▒█▓▓▓▓▓▓▓
░▒▒░░░░░▒▒█▓▓▓▓▓▓
░▒▒░░░░▒▒█▓▓▓▓▓▓

4.1 О биекции: Язык согласования

«Биекция» – это математическая конструкция, когда каждому элементу одного множества поставлен в соответствие ровно один элемент другого, и наоборот [25].
Чтобы построить биекцию, количество элементов в множествах должно быть равно, а сами элементы множеств должны быть индивидуальны и различимы.

    МНОЖЕСТВО А (БУКВЫ)           МНОЖЕСТВО B (ЦИФРЫ)      -------------------           -------------------             А <-------------------------> 1             Б <-------------------------> 2             В <-------------------------> 3                            ^                            |     БИЕКТИВНОЕ ОТОБРАЖЕНИЕ МНОЖЕСТВА А НА МНОЖЕСТВО В  

Мы постоянно строим биекции: каждое однозначное название – это биекция с объектом физического мира, 7 нот музыки образуют биекцию с 7-ю звуками разной частоты. Мы имеем два равномощных множества, элементы которых «сшиты» друг с другом.
Отобразим биекцию совокупностью двух множеств и двух функций. «Прямая функция» f сопоставляет каждой цифре из таблицы строго определенное положение механизмов машины. «Обратная функция» f’ – по положению рычагов машины отдаёт из таблицы соответствующее число.

       УСТРОЙСТВО БИЕКЦИИ         ------------------              МНОЖЕСТВО S                     МНОЖЕСТВО P       (Объекты Математики)               (Объекты Физики)                     +-------+                        +-------+            |  "0"  |---- f (Прямая) ------->| Фаза 0|            |       |<--- f' (Обратная) -----|       |            +-------+                        +-------+                        +-------+                        +-------+            |  "1"  |---- f (Прямая) ------->| Фаза 1|            |       |<--- f' (Обратная) -----|       |            +-------+                        +-------+                        +-------+                        +-------+            |  "2"  |---- f (Прямая) ------->| Фаза 2|            |       |<--- f' (Обратная) -----|       |            +-------+                        +-------+  

4.2 Модель

Если между состояниями двух объектов установлена биекция, то каждый из них называют «моделью» другого.
Камень в мешке пастуха – модель быка на лугу, бык на лугу – модель камня в мешке. Стрелка механических часов – модель движения Солнца, но и Солнце – модель движения стрелки. Стрелка манометра – это модель давления пара, обратное – тоже верно.
Цифра и Машина – зеркальное отражение друг друга. Если мы смотрим на цифру в таблице или на индикаторе, мы видим саму Машину, не открывая её кожух. Если стрелка врет – модель испорчена, точное соответствие (биекция) нарушено.

4.3 Сигналы входящие и исходящие

Итак, нам нужно связать математику, то есть цифры, с физикой. Для этого строят две связанные машины: одна Автомат (или Контроллер) отвечает за чередование цифр, и ничего не знает об окружающем мире, другая Механизм меняет мир, ничего не зная о цифрах. Пространство состояний первой машины – множество цифр для её единственного регистра. Пространство состояний второй машины – сумма положений всех её агрегатов (железных частей).
Сигналы поддерживают биекцию между состояниями двух этих машин.
Входящим сигналом (In): Механизм сообщает Автомату: «В моем физическом мире произошло событие, измени свое число в соответствии с таблицей». Исходящим сигналом (Out): Автомат принуждает Механизм: «Я изменил свое число, теперь физически перестрой свои агрегаты, чтобы соответствовать мне».

    СХЕМА СИНХРОНИЗМА (СОГЛАСОВАНИЯ СОСТОЯНИЙ МЕХАНИЗМА И АВТОМАТА ВО ВРЕМЕНИ)      -----------------------------------------------------------------------      МЕХАНИЗМ ---  [ ВХОДНОЙ СИГНАЛ  ] ---> АВТОМАТ (Число)      МЕХАНИЗМ <--- [ ВЫХОДНОЙ СИГНАЛ ] ---  АВТОМАТ (Число)         |                                       |         +--------------( БИЕКЦИЯ )--------------+                 (Полное взаимное согласование состояний)  

Две машины ведут непрерывный диалог сигналами, поддерживая биекцию, установленную над их состояниями: Механизм рапортует Автомату «Шаг сделан! Обнови число в памяти!», Автомат сообщает: «Число сменилось! Приказываю начать движение!» Сигналами одна машина приводит в соответствие своё состояние с состоянием другой машины.
Сигнал – не часть состояния, а способ добиться, чтобы изменение состояния одного автомата немедленно вело к переключению другого.
Автомат «не знает», потек ли лимонад. Он знает, что подал сигнал на выдачу и перешел в следующее состояние. Если лимонад не потек (забилась трубка) – состояние аппаратуры не изменилось, а состояние автомата – изменилось. Это и есть рассинхрон, которой следует устранить инженеру-наладчику.
Инженер не ремонтирует «автомат с газировкой». Он настраивает счислитель (Автомат) и исполнительный агрегат (Механизм) так, чтобы между ними установилась биекция.
Инженер не «чинит налив». Он восстанавливает канал передачи сигналов, который обязан удерживать два работающих устройства в одной и той же точке их пространств состояний.
Контролер состоит из двух ключевых узлов: «Памяти» (или регистра состояния) – устройства, способного физически удерживать одно из N положений. И «комбинационной логики» – электромеханического узла, реализующего таблицу переходов.
Биекция гарантирует, что если мы видим число «2» на индикаторе Контролера, мы можем точно утверждать, что Механизм находится в фазе «Выдача», не заглядывая внутрь бака.

4.4 Наладка

Математическая модель – это графики, знаки и цифры на листе бумаги. В них нет движения и электричества. «Переключателем» в математической модели служит сам человек. Он сам (физически) устанавливает взаимно однозначное соответствие между математической моделью и объектами реального мира.
Наладка устройства заключается в проверке соответствия «Матмодель ↔ Автомат ↔ Механизм»:
Вы пальцем указываете на цифру в таблице (Матмодель), другим пальцем – на положение контактов в Автомате (контроллере), а глазами смотрите на положение рычагов в Механизме. Все три точки должны показать то же.

    СХЕМА ПРОВЕРКИ СИНХРОНИЗМА      --------------------------            [ТАБЛИЦА] <----(ВЗГЛЯД)----> [КОНТРОЛЛЕР] <----(ТОК)----> [МЕХАНИЗМ]      (Цифра 2)             (Положение контактов реле)           (Фаза 2)  

4.5 Памятка инженера-наладчика

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

    ПАМЯТКА ИНЖЕНЕРА-НАЛАДЧИКА      --------------------------      1. Проверить математику (верна ли таблица).      2. Проверить автомат (ходят ли реле).      3. Проверить физику (ходят ли механизмы).      4. Установить (либо проверить) биекцию между тремя объектами из п.1-3.        ПАМЯТКА ИНЖЕНЕРА ПО ЭКСПЛУАТАЦИИ ОБОРУДОВАНИЯ      ------------------      1. Прочесть документацию на устройство. Установить взаимно однозначное соответствие между таблицами документации, панелями контроля и управления машиной.      2. Запустить устройство, дождаться окончания теста проверки целостности.      3. Эксплуатировать по инструкции. Следить за соответствием: Таблица (инструкция) – Индикаторы – Органы управления – Физическое состояние объекта.      4. При обнаружении несоответствий, остановить работу машины, вызвать инженера-наладчика либо инженера по ремонту оборудования.  

ПРАКТИКА

РАЗДЕЛ: АВТОМАТ «ЛИМОНАД-МТ»

┌┘┌┘┌┘┌┘▓▓▒░▒▓▓▒▓█▒──▒▓▓▓█▓▓▓░┌┘┌┘┌┘┌┘┌┘┌
┌┘┌┘┘┌┘▓█▓──▓█▓▓▓▓───▓█▓▓▒▓▒░░┌┘┌┘┌┘┌┘┌┘┌
┌┘┌┘┌┘░█▓▓▒░░▒▒▒▓▓──░▓█▒──▒▒░▒▒░┌┘┌┘┌┘┌┘┌
┌┘┌┘┌┘▒▓▓▓▓░─────░░─▒▓█▓▒▓██▓─▒▓░┘┌┘┌┘┌┘┌
┌┘┌┘┌▓▓▓▒▒──░──────░▒▓▓▓▒░▒▓▓──▓▓┘┌┘┌┘┌┘┌
┌┘┌┘▒█▓▒░────────────────░▒▒▒▒░▒▓┘┌┘┌┘┌┘┌
┌┘┌░█▓▒▒░──────────────░██▒▓██▓▒▒┘┌┘┌┘┌┘┌
┌┘┌▓▓░▒▓▒░───░▒▒░──────▒▓───▓█▓▒┘┌┘┌┘┌┘┌┘
┌┘▒█▓░▒▓▒░─░▓▓▓▓▒░────░░────░▓█▓░┘┌┘┌┘┌┘┌
┌┘▓█▓░░▓▒░▒▓░────░░───▒░──░▓▓▓▓█▓▒┘┌┘┌┘┌┘
┌┘▒▓▓──▒▓▓▒───────░░──░░▓▓▓███▓▓▓█▓┘┌┘┌┘┌
┌┘▒▓▓──░▓▒──░──▓▓▒░░░──▒██████▓▒░▓█▓┘┌┘┌
┌┘▓▓▓░─░▓░─░▓▒▓███░─░───▒▒░▒▒▒▓▓─░▓█▓┘┌┘┌
┌┘░▓▓▓▒─░▒░─▓████▓▒░──░░░▓▒────▒▓▒─▓▓▓▓░
▒░▓▓▒░───░▓██▓▓▒░─░─░▓▒─▒▒────▒▓▓░▓▓░▓▓▓
░─▒▓▓▓──░▒▒▒░░───░░─────░▒▓▒──░▓▓▒▓█░─░▒
┌┘▒▓██▓▓▓▓▒░░░░──░───▓██▓▓██▓░░▒█▓▒█▓░──
░░▒▓▓▓▓▓▓▓▒░▒░░░░░──██▓▒░──▓█▒─░█▓▒▒██▓░
░▒▓▓▒───░▓▒▒░░░▒▒──█▓──────▒▓░─░▓█▒─▒▓█▓
░─░▓░──▒▒▒▒▒▒░░░──▓█░─▒▓████▒──▒▓█▓░───▒
░───▒▒▓▒░──░▒▒░─────▒▓█▓▓▓▓▓▒░─▒▓▓█▓▒──░
▒────░▒────░▒▒░────────────░▒▒▒▓▓▓▓▓▓▒░▒
▓▓░──░░───░▒▓▒░░░──────────░▒▒▒▓▓▓▓▒░░▒▓
█▓▒▒▓▓░─░▒▓▓▓▓▒░░───────────░▒▓▓▓▓▒─░▒▓▒
░░░▒▓▓▒▒▓█████▓▒░░░────────░▒▓▓▓▓▓░░▓▓░─
░░░──▒▓██▓▓█▓▒▒░▒▒▒░░░░░░▒▒▓▓█▓▓▓▓▒▓▓░──
░░░░░░▒▓▓░─░────▓▓▓▓▓▓▓▓▓▓▓▓█▓▓▓▓▓▓▒░───
┌┘┌░▒░─────────▓▓▒░▒▓▓▓▓▓▓▓▓█▓▓▓▓▓▓───░░
┌┘┌┘┌▒▒─────░▒▓█▓────░▒▓▓▒▓▓▓▓▓▒▒▒▒▒──░▓
┌┘┌┘┘░▓▓▒▒▓▓▓▓█▓░──────▒▓▒▓█▓▓▓▒───▒▓▒▒▓
┌┘┌┘┘┌▒▓▓▓▓▓▓▓▓────────░▒▒▓█▓░░────▒▓▓▓▓
┌┘┌┘┘┌┘┌░░▒▒▒▓▒──────────▒█▓░────░▒▓▓▓▓▓
┌┘┌┘┘┌┘┌┌░▒▓░░▒░─────────▓█▒──░░░▒▓██▓▓▓
┌┘┌┘┘┌┘┌┘┌░▓▒─░▒▒░───░───▓█▒░▓▓██▓▓▓▓▒▓▓
┌┘┌┘┘┌┘┌┘┌┌▒▓░──░▒▒▒░───▒██▓▒▓██▒░──░▒▓▓
┌┘┌┘┘┌┘┌┘┌┌░▒░────░▒▒▒──▓█▓▓▓▓▓▓▒░░░▓▓▒▒
┌┘┌┘┘┌┘┌┘┌┌░░▒──────░▒░─▓▓▓▓▓▓▓▓▓██▓▓▓▒░
┌┘┌┘┘┌┘┌┘┌░░░▒░─────░░░▒▒▒▒▒▓▓▓▓▓▓▓▓▒▒▒░
┌┘┌┘┘┌┘┌┘┌░░░▒▒─────░░░░░░░░▒▓▒░┌┘┌┘┘┌┘┌┘

Повторим шаги появления и исторического развития (или «генезис») вычислителей, на примере торгового автомата. Это проиллюстрирует идеи этой части курса.

1. ТАБЛИЧНОЕ ОПРЕДЕЛЕНИЕ АВТОМАТА

Назначение: автомат «Лимонад-МТ» на жетонах для продажи газированных напитков. Работа: автомат ожидает 3 жетона и обслуживает покупателя из очереди. Блокируется при извлечении монеты или взломе.

ТАБЛИЦА 1. FSM-ТАБЛИЦА АВТОМАТА «ЛИМОНАД-МТ»    +--------+------+--------+--------+  | Текущ. | Вход | След.  | Выход  |  | сост.  | (In) | сост.  | (Out)  |  +--------+------+--------+--------+  |   S0   |  М   |   S1   |   A0   |  |   S0   |  В   |  ERR   |   A3   |  |   S0   |  Т   |   S0   |   A4   |  |   S0   |  П   |   S0   |   A2   |  |   S0   |  О   |   S0   |   A4   |  +--------+------+--------+--------+  |   S1   |  М   |   S2   |   A0   |  |   S1   |  В   |  ERR   |   A3   |  |   S1   |  Т   |   S0   |   A1   |  |   S1   |  П   |   S1   |   A2   |  |   S1   |  О   |   S0   |   A7   |  +--------+------+--------+--------+  |   S2   |  М   |   S0   |   A5   |  |   S2   |  В   |  ERR   |   A3   |  |   S2   |  Т   |   S0   |   A1   |  |   S2   |  П   |   S2   |   A2   |  |   S2   |  О   |   S0   |   A7   |  +--------+------+--------+--------+  |  ERR   |  *   |  ERR   |   A6   |  +--------+------+--------+--------+    ТАБЛИЦА 2. РАСШИФРОВКА МНОЖЕСТВА СОСТОЯНИЙ (S)    +--------+--------+-------------------------------------------+  | Идент. | Индекс | Описание                                  |  +--------+--------+-------------------------------------------+  |   S0   |   0    | Ожидание (баланс 0 коп)                   |  |   S1   |   1    | Накопление (баланс 1 коп)                 |  |   S2   |   2    | Предтерминальное (баланс 2 коп)           |  |  ERR   |   3    | Блокировка (взлом или системный сбой)     |  +--------+--------+-------------------------------------------+    ТАБЛИЦА 3. РАСШИФРОВКА МНОЖЕСТВА ВХОДНЫХ СИГНАЛОВ    +--------+------------+---------------------------------------+  | Символ | Название   | Техническое условие                   |  +--------+------------+---------------------------------------+  |   М    | Монета     | Валидный импульс оплаты               |  |   В    | Вскрытие   | Детекция попытки взлома корпуса       |  |   Т    | Противоход | Попытка извлечения монеты (нитка)     |  |   П    | Пусто      | Отсутствие сигналов (режим ожидания)  |  |   О    | Отмена     | Нажатие кнопки возврата средств       |  |   *    | Любой      | Ввод технически блокирован            |  +--------+------------+---------------------------------------+    ТАБЛИЦА 4. РАСШИФРОВКА МНОЖЕСТВА ВЫХОДНЫХ СИГНАЛОВ (A)    +--------+-----------+----------------------------------------+  | Идент. | Название  | Расшифровка действия                   |  +--------+-----------+----------------------------------------+  |   A0   | ACCEPT    | ПРИЕМ: подтверждение зачисления        |  |   A1   | FRAUD     | ФРОД: сигнал тревоги при попытке кражи |  |   A2   | WAIT      | ОЖИДАТЬ: ожидать сигнал                |  |   A3   | TRAP      | ВЗЛОМ: блокировка купюроприемника      |  |   A4   | REJECT    | ОТКАЗ: действие невозможно             |  |   A5   | GIVE      | ВЫДАЧА: активация подачи лимонада      |  |   A6   | SERVICE   | СЕРВИС: вызов мастера                  |  |   A7   | RETURN    | ВОЗВРАТ: выдача накопленных монет      |  +--------+-----------+----------------------------------------+  

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

int state = s0; // Текущий узел (вершина) графа  printf("[%d]", state);  while (in = get_input()) // Получить входной символ  {      state = table[state][in]; // Переход по ребру в следующий узел      printf("->[%d]", state);  }  

2. КОД АВТОМАТА НА С

Задание: пошагово пройти в отладчике код, начиная с main(), понять его работу.

// fsm_1.cpp#include <conio.h>  #include <ctype.h>  #include <locale.h>    #define LOG printf    /* --- Спецификация автомата --- */    /* --- Множество, нумерующее состояния автмата --- */  /* S0 – ожидание (0 жетон), S1 – накопление (1 жетон), S2 – предтерминальное (2 жетона), ERR – блокировка. */  typedef enum { S0, S1, S2, ERR } State;    /* --- Множество, нумерующее Входные символы (или Входной алфавит) --- */  /* М – монета, В – вскрытие, Т – противоход, П – пусто, О – отмена. */  typedef enum { M, V, T, P, O } Input;    /* --- Множество, нумерующее Выходные символы (или Выходной алфавит) --- */  /* ПРИЕМ, ФРОД, ОЖИДАТЬ, ВЗЛОМ, ОТКАЗ, ВЫДАЧА, СЕРВИС, ВОЗВРАТ */  typedef enum { A0, A1, A2, A3, A4, A5, A6, A7 } Action;    /* --- Коды действий --- */  const char* Actions[] = { "ПРИЕМ", "ФРОД", " ОЖИДАТЬ ", "ВЗЛОМ", "ОТКАЗ", "ВЫДАЧА", "СЕРВИС", "ВОЗВРАТ" };  /* --- Коды состояний --- */  const char* States[]  = { "БАЛАНС 0", "БАЛАНС 1", "БАЛАНС 2", "БЛОКИРОВКА" };    /* --- Таблица (или граф) переходов --- */  struct Step  {      State next;    /* S' */      Action action;  /* A  */  };    const Step Machine[4][5] =  {      /*         M          V         T          P         O      */      [S0] = {{S1, A0}, {ERR, A3}, {S0, A4}, {S0, A2}, {S0, A4}},      [S1] = {{S2, A0}, {ERR, A3}, {S0, A1}, {S1, A2}, {S0, A7}},      [S2] = {{S0, A5}, {ERR, A3}, {S0, A1}, {S2, A2}, {S0, A7}},      [ERR]= {{ERR, A6}, {ERR, A6}, {ERR, A6}, {ERR, A6}, {ERR, A6}}  };    int state; // Текущее состояние машины  void machine_loop()// Рабочий цикл машины  {      while (state != ERR)      {          LOG("[%s] > ", States[state]);            /* Ожидание входящего сигнала */          int c = toupper(getche());            /* Декодирование физических сигналов в символы алфавита */          int in = (c=='M') ? M :                     (c=='V') ? V :                     (c=='T') ? T :                     (c=='P') ? P :                     (c=='O') ? O : -1;            if(in == -1) continue;            /* Исполнение шага автомата */          Step step = Machine[state][in];          LOG("\nACTION: %s -> NEXT STATE: %s\n", Actions[step.action], States[step.next]);            state = step.next;      }  }    int main(void)  {      setlocale(LC_ALL, "en_US.UTF-8");        LOG("--- ЛИМОНАД-МТ-1960 ---\nВВЕДИТЕ СИГНАЛ: M - монета, V - вскрытие, T - противоход, P - пусто, O - отмена. \n");        state = S0; // Начальное состояние машины      machine_loop();        LOG("\n--- МАШИНА ОСТАНОВЛЕНА ---\n");        getch();      return 0;  }  

3. БЛИЗКИЙ К ГРАФУ КОД АВТОМАТА НА С

Всякому алгоритму или «программе» соответствует маркированный граф. Оператор switch, приближает структуру кода на С к графу или к коду на Lisp, «распрямляя» и делая его наглядней.
Перепишем нашу матрицу переходов через switch.
Мы имеем 4 состояния State автомата и 5 входных сигналов Input. Любой сигнал может поступить при любом состоянии автомата. Декартово произведение CASES = |Input × State| даст все пары (входящий сигнал, состояние). Их количество N = |CASES| = |Input| * |State| = 4*5=20. В блоке SWITCH-ЛОГИКА мы обработаем все 20 вариантов.

Задание: пошагово пройти в отладчике код, начиная с main(), понять его работу.

// fsm_2.cpp#include <conio.h>  #include <ctype.h>  #include <locale.h>    #define LOG printf    typedef enum { S0, S1, S2, ERR } State;  typedef enum { M, V, T, P, O } Input;  typedef enum { A0, A1, A2, A3, A4, A5, A6, A7 } Action;    const char* Actions[] = { "ПРИЕМ", "ФРОД", "ОЖИДАТЬ", "ВЗЛОМ", "ОТКАЗ", "ВЫДАЧА", "СЕРВИС", "ВОЗВРАТ" };  const char* States[] = { "БАЛАНС 0", "БАЛАНС 1", "БАЛАНС 2", "БЛОКИРОВКА" };    int state;    // Функция-обертка, обработка исходящего сигнала  void process_step(int next_s, int act)  {      LOG("\nACTION: %s -> NEXT STATE: %s\n", Actions[act], States[next_s]);      state = next_s;  }    void machine_loop()  {      while (state != ERR)      {          LOG("[%s] > ", States[state]);            int c = toupper(getche());            Input in;          switch (c)          {              case 'M': in = M; break;              case 'V': in = V; break;              case 'T': in = T; break;              case 'P': in = P; break;              case 'O': in = O; break;              default:  continue;          }            /* ЗАМЕНА ТАБЛИЦЫ НА SWITCH-ЛОГИКУ */  /*        ПЕРЕХОД ПО РЕБРУ ИЗ УЗЛА Sn -> В УЗЕЛ Sn+1                [M] ->[Sn+1] / A            /           /  [V] ->[Sn+1] / A          /  /  [Sn] -------- [T] ->[Sn+1] / A          \  \           \  [P] ->[Sn+1] / A            \              [O] ->[Sn+1] / A  */            switch (state)          {              case S0:                  switch (in)                  {                      case M: process_step(S1, A0); break;                      case V: process_step(ERR, A3); break;                      case T: process_step(S0, A4); break;                      case P: process_step(S0, A2); break;                      case O: process_step(S0, A4); break;                  }                  break;                case S1:                  switch (in)                  {                      case M: process_step(S2, A0); break;                      case V: process_step(ERR, A3); break;                      case T: process_step(S0, A1); break;                      case P: process_step(S1, A2); break;                      case O: process_step(S0, A7); break;                  }                  break;                case S2:                  switch (in)                  {                      case M: process_step(S0, A5); break;                      case V: process_step(ERR, A3); break;                      case T: process_step(S0, A1); break;                      case P: process_step(S2, A2); break;                      case O: process_step(S0, A7); break;                  }                  break;                case ERR:                  switch (in)                  {                      case M: process_step(ERR, A6); break;                      case V: process_step(ERR, A6); break;                      case T: process_step(ERR, A6); break;                      case P: process_step(ERR, A6); break;                      case O: process_step(ERR, A6); break;                  }                  break;          }      }  }    int main(void)  {      setlocale(LC_ALL, "en_US.UTF-8");      LOG("--- ЛИМОНАД-МТ-1960 ---\nВВЕДИТЕ СИГНАЛ: M - монета, V - вскрытие, T - противоход, P - пусто, O - отмена. \n");        state = S0;      machine_loop();        LOG("\n--- МАШИНА ОСТАНОВЛЕНА ---\n");        getch();      return 0;  }  

4. УНИВЕРСАЛЬНАЯ МАШИНА ТЬЮРИНГА ДЛЯ ЭМУЛЯЦИИ МТ

░░┌──┐░░░░░░░░░░┌──┐░░
░╔╡▐▐╞╝░░┌──┐░░╔╡▐▐╞╝░
░░└╥╥┘░░╚╡▌▌╞╗░░└╥╥┘░░
░░░╚╚░░░░└╥╥┘░░░░╚╚░░░
░░░░░░░░░░╝╝░░░░░░░░░░

Работа автомата математически соответствует перебору списка из четвёрок чисел:

[ S_текущее , In_входное , S_новое , Action_выходное ]

Универсальная МТ имитирует любую МТ, считав такую таблицу с «ленты». Под ней мы понимаем, перфокарту, дискету, CD-ROM и иной носитель данных.
УМТ не знает об устройстве прибора, а просто находит нужную строку в таблице, меняет в своём регистре номер текущего состояния на табличный, и отдаёт «наружу» номер сигнала для смены состояния механизма:

   FSM-ТАБЛИЦА (СЧИТЫВАЕТСЯ УМТ С ЛЕНТЫ)  

+-----+-----+-----+-----+  |S_тек|I_вх | S_но|A_вых|  +-----+-----+-----+-----+  <-- Строка №1  |  1  |  1  |  2  |  0  |   (Если состояние "1" и пришло "1"  +-----+-----+-----+-----+    измени состояние на "2" и выдай сигнал "0")  |  2  |  1  |  3  |  7  |  <-- Строка №2  +-----+-----+-----+-----+   (Если состояние "2" и пришло "1"  | ... | ... | ... | ... |    измени состояние на "3" и выдай сигнал "7")  +-----+-----+-----+-----+  

УМТ просто переводит входные абстрактные числа в выходные абстрактные числа, следуя застывшему в цифре маршруту. «Интеллектуальность» УМТ заключена не в её деталях, а в последовательности записанных на ленту чисел.
FSM-таблица эквивалентна оцифрованному графу, вершины которого соответствуют номерам состояний, а в рёбра – номерам входящих сигналов. УМТ – это механический обходчик (транслятор) таких графов. При переходе от состояния к состоянию УМТ выдаёт действие («сигнал»), привязанной к ней аппаратуре.

5. VM УМТ НА С

Добавим УМТ в наш код на С. Универсальное логическое «ядро» будет обходить граф по цифровой матрице. Мы загрузим её в виде таблицы чисел, что исключит перепайку схемы обходчика графа при смене алгоритма.
Теперь, чтобы сделать из автомата газировки игровой пинбол, достаточно загрузить в УМТ другой байткод и сделать в металле «обвязку», соответствующую пинболу.
«Обвязка» или оболочка над логическим «ядром» – это физический преобразователь, который кодирует нажатия рычагов во входные цифры для УМТ и дешифрует её выходные цифры в физику команд исполнительных механизмов.

Задание: пошагово пройти в отладчике код, начиная с main(), понять его работу.

// umt.cpp#include <conio.h>#include <ctype.h>#include <locale.h>#define LOG printf//------------------------------------------// УНИВЕРСАЛЬНАЯ МАШИНА ТЬЮРИНГА (УМТ)//------------------------------------------#define ROW(...) (Step[]){ __VA_ARGS__ }struct Step{    int state;    /* S' */    int action;  /* A  */};/* Функция для связи Универсальной Машины Тьюринга с внешним миром */typedef void (*Action_Handler)(int state, int action);Action_Handler action_handler;  // Обработчик исходящих сигналовint state; // Текущее состояние эмулируемой машиныStep **ROM; // Программа для УМТvoid UMT_Run(int in){    Step step = ROM[state][in];    action_handler(step.state, step.action);    state = step.state;}/* --- Загрузчик программы в УМТ (ROM Loader) --- */void Load_ROM(Step **rom, int S0_state, Action_Handler ah){ROM = rom;state = S0_state;action_handler = ah;}//------------------------------------------//------------------------------------------// СПЕЦИАЛИЗИРОВННЫЙ АВТОМАТ (ОБЁРТКА НАД ЛОГИКОЙ УМТ)//------------------------------------------typedef enum { S0, S1, S2, ERR } State;typedef enum { M, V, T, P, O } Input;typedef enum { A0, A1, A2, A3, A4, A5, A6, A7 } Action;const char* Actions[] = { "ПРИЕМ", "ФРОД", "ОЖИДАТЬ", "ВЗЛОМ", "ОТКАЗ", "ВЫДАЧА", "СЕРВИС", "ВОЗВРАТ" };const char* States[] = { "БАЛАНС 0", "БАЛАНС 1", "БАЛАНС 2", "БЛОКИРОВКА" };// Программа для УМТStep *Machine_Limonad[] ={                    /*     M       V      T        P      O    */    /* S0  */ [0] = ROW({1, 0}, {3, 3}, {0, 4}, {0, 2}, {0, 4}),    /* S1  */ [1] = ROW({2, 0}, {3, 3}, {0, 1}, {1, 2}, {0, 7}),    /* S2  */ [2] = ROW({0, 5}, {3, 3}, {0, 1}, {2, 2}, {0, 7}),    /* ERR */ [3] = ROW({3, 6}, {3, 6}, {3, 6}, {3, 6}, {3, 6})};/* Обработчик сигналов: здесь происходят физические действия */void Exec_Action(int state, int action){    LOG("\nACTION: %s -> NEXT STATE: %s\n", Actions[action], States[state]);}void machine_loop()// Рабочий цикл машины{    while (state != ERR)    {        LOG("[%s] > ", States[state]);        int c = toupper(getche());        int in = (c=='M') ? M :                   (c=='V') ? V :                   (c=='T') ? T :                   (c=='P') ? P :                   (c=='O') ? O : -1;        if(in == -1) continue;        /* Исполнение шага автомата на УМТ */        UMT_Run(in);    }}//------------------------------------------int main(void){    setlocale(LC_ALL, "en_US.UTF-8");    LOG("--- ЛИМОНАД-УМТ-1960 ---\nВВЕДИТЕ СИГНАЛ: M - монета, V - вскрытие, T - противоход, P - пусто, O - отмена. \n");    Load_ROM(Machine_Limonad, S0, Exec_Action); // Загрузить программу в УМТ    machine_loop(); // Запустить специализированный автомат    LOG("\n--- МАШИНА ОСТАНОВЛЕНА ---\n");    getch();    return 0;}

Теперь оформим эту УМТ байткодовой виртуальной машиной. Она подгружает байткод (программу) и запускает цикл исполнения machine_loop(). В цикле VM проверяет входящий сигнал в регистре REG_IN и выдаёт команды механизму вызовом функции Out_Action().
Так же мы добавили функцию DISASSEMBLER(), дизассемблирующую байткод в мнемокод.
Функция set_jmps() вычисляет и устанавливает смещения в операциях JMP и JMP_IF перед запуском ассемблерного кода, иначе это нужно делать вручную, что неудобно. На первых итерациях задания её можно опустить.

Задание: пошагово пройти в отладчике код, начиная с main(), понять его работу.

// umt_vm.cpp#include <stdlib.h>  #include <stdarg.h>  #include <conio.h>  #include <string.h>  #include <ctype.h>  #include <locale.h>    #define LOG printf    //------------------------------------------  // УНИВЕРСАЛЬНАЯ МАШИНА ТЬЮРИНГА (УМТ)  //------------------------------------------    //------------------------------------------  // СИСТЕМА КОМАНД VM  //------------------------------------------  /*  ГРАММАТИКА АССЕМБЛЕРА (EBNF):  ------------------------------------------  <program>     ::= { <instruction> }  <instruction> ::= "LD_IN"                  | "JMP" <address>                  | "JMP_IF" <condition> <address>                  | "EXEC" <action_id>                  | "SET_S" <state_id>                  | "LABEL" <label_id>                  | "BREAK"                  | "HALT"  <condition>   ::= <integer>  (* ASCII код символа *)  <address>     ::= <integer>  <action_id>   ::= <integer>  <state_id>    ::= <integer>  <label_id>    ::= <integer>  ------------------------------------------  */    typedef enum  {      // Достаточный набор команд для УМТ      LD_IN,   // Считать входной сигнал в регистр      JMP,     // Безусловный переход. Перейти по адресу Y      JMP_IF,  // Условный переход. Если вход == X, перейти по адресу Y, иначе — к следующей команде      EXEC,    // Выполнить внешнее действие Z      SET_S,   // Сменить номер состояния в регистре состояний      LABEL,   // Маркер метки для JMP_IF      BREAK,   // Точка останова (DEBUG)      HALT,     // Остановка машины        OpCodes_Total  } OpCode;    // Размеры команд (сколько ячеек памяти занимает команда вместе с аргументами)  const int OP_SIZE[] =  {      1, // LD_IN      2, // JMP <метка>      3, // JMP_IF <условие> <метка>      2, // EXEC <номер_действия>      2, // SET_S <номер_состояния>      2, // LABEL <номер_метки>      1, // BREAK      1  // HALT  };    // Названия команд для ассемблера и мониторинга  const char* MNEMONICS[] =  {      "LD_IN", "JMP", "JMP_IF", "EXEC", "SET_S", "LABEL", "BREAK", "HALT"  };  //------------------------------------------    //------------------------------------------  // Виртуальная машина  //------------------------------------------  struct UVM;  typedef void (*Signal_Handler)(UVM &VM);    struct UVM  {      int IP;              // Instruction Pointer (Указатель на текущую команду)      int REG_IN;          // Регистр входного сигнала      int CUR_S;           // Регистр текущего состояния      int REG_OUT;         // Регистр текущего действия (Action)      int *ROM;            // Память машины      int F_IS_RUN;        // Флаг остановки машины        Signal_Handler in_signal_handler;       // Ожидание входящего сигнала. Должен быть записан в REG_IN      Signal_Handler out_signal_handler;      // Генератор исходящих сигналов. Сигнал хранится в регистре REG_OUT      Signal_Handler break_signal_handler;    // Сигнал отладчику  };    int VM_Step(UVM &VM) // Выполнение  команды  {      int opcode = VM.ROM[VM.IP];      int next_IP = VM.IP + OP_SIZE[opcode];        LOG("\n[DBG] IP:%02d    %s", VM.IP, MNEMONICS[opcode]);        switch (opcode)      {          case LD_IN:          case BREAK:          case HALT:          case LABEL:               break;          case SET_S:              VM.CUR_S = VM.ROM[VM.IP+1];              break;          case EXEC:              VM.REG_OUT = VM.ROM[VM.IP+1];              break;          case JMP:                  next_IP = VM.ROM[VM.IP+1];              break;          case JMP_IF:              if (VM.REG_IN == VM.ROM[VM.IP+1]) next_IP = VM.ROM[VM.IP+2];              break;      }        VM.IP = next_IP;        return opcode;  }    void machine_loop(UVM &VM)// Рабочий цикл машины  {      while (VM.F_IS_RUN)      {          int opcode = VM_Step(VM);          switch (opcode)          {              case HALT:                  VM.F_IS_RUN = 0;                  break;              case LD_IN:                  VM.in_signal_handler(VM);                  break;              case EXEC:                  VM.out_signal_handler(VM);                  break;              case BREAK:                  // Точка остановки отладчика (breakpoint). Здесь можно вызвать сервисное меню или дамп памяти                  LOG("\n>>BREAKPOINT<<");                  VM.break_signal_handler(VM);                  break;          }      }  }    //------------------------------------------  // DISASSEMBLER  //------------------------------------------  void DISASSEMBLER(int *MEM, int RANGE_L, int RANGE_R)  {      LOG("\n------- DISASSEMBLY START -------\nMEMBLOCK = [0x%X-0x%X]", RANGE_L, RANGE_R);      int i = RANGE_L;      while (i < RANGE_R)      {          int opcode = MEM[i];          int is_valid = (opcode >= 0 && opcode < OpCodes_Total);          int step = is_valid ? OP_SIZE[opcode] : 1;            // Печать Мнемоники          LOG("\nADR:%02d    %-8s", i, is_valid ? MNEMONICS[opcode] : "DATA");            // Печать Аргументов          for (int a = 1; a < step; a++) LOG(" %d", MEM[i + a]);          if (!is_valid) LOG(" %d", opcode);          i += step;      }      LOG("\n------- DISASSEMBLY END -------");  }  //------------------------------------------    //------------------------------------------  // GENERATE & COMPLILE PROGRAM BY FSM TABLE  //------------------------------------------  // Замена id переходов в байткоде на смещения  void set_jmps(int *base, int *end, int id_count)  {      int *address_tab = (int*)malloc(id_count * sizeof(int));        // Pass 1: Собираем адреса меток      int *p = base;      while (p < end)      {          if (*p == LABEL) address_tab[p[1]] = (int)(p - base);          p += OP_SIZE[*p];      }        // Pass 2: Дизассемблируем код и заменяем id меток на смещения от base      p = base;      while (p < end)      {          OpCode op = (OpCode)*p;          if (op == LABEL)  p[1] = (int)(p - base);          if (op == JMP)    p[1] = address_tab[p[1]];          if (op == JMP_IF) p[2] = address_tab[p[2]];          p += OP_SIZE[op];      }        free(address_tab);  }  //------------------------------------------    //------------------------------------------  // ДОМЕННЫЙ АВТОМАТ (ОБЁРТКА НАД ЛОГИКОЙ УМТ)  //------------------------------------------  /*  ДИСКРЕТНАЯ МОДЕЛЬ (ГРАФ АВТОМАТА):  Множество состояний S = {S0, S1, S2, ERR}  Входной алфавит X = {M, V, T, P, O} (ASCII: 77, 86, 84, 80, 79)  Алфавит действий A = {A0, A1, A2, A3, A4, A5, A6, A7}  Функция переходов δ: S×X -> S  */    /* --- Множество, нумерующее состояния автмата --- */  /* S0 – ожидание (0 жетон), S1 – накопление (1 жетон), S2 – предтерминальное (2 жетона), ERR – блокировка. */  typedef enum { S0, S1, S2, ERR } State;    /* --- Множество, нумерующее Входные символы (или Входной алфавит) --- */  /* М – монета, В – вскрытие, Т – противоход, П – пусто, О – отмена. */  typedef enum { M, V, T, P, O } Input;  typedef enum { _M = 'M', _V = 'V', _T = 'T', _P = 'P', _O = 'O' } _Input;  const char *Inputs = "MVTPO";    /* --- Множество, нумерующее Выходные символы (или Выходной алфавит) --- */  /* ПРИЕМ, ФРОД, ОЖИДАТЬ, ВЗЛОМ, ОТКАЗ, ВЫДАЧА, СЕРВИС, ВОЗВРАТ */  typedef enum { A0, A1, A2, A3, A4, A5, A6, A7 } Action;    const char* Actions[]       = { "ПРИЕМ", "ФРОД", "ОЖИДАТЬ", "ВЗЛОМ", "ОТКАЗ", "ВЫДАЧА", "СЕРВИС", "ВОЗВРАТ" };  const char* States[]        = { "БАЛАНС 0", "БАЛАНС 1", "БАЛАНС 2", "БЛОКИРОВКА" };  const char* In_Actions[]    = { "МОНЕТА", "ВСКРЫТИЕ", " ПРОТИВОХОД ", "ПУСТО", "ОТМЕНА" };    //------------------------------------------  // Программа для УМТ (Bytecode)  //------------------------------------------  /* --- Метки для адресации в ROM --- */  typedef enum  {      LB_S0, LB_S0_BUSY, LB_S0_A2, LB_S0_A4,      LB_S1, LB_S1_BUSY, LB_S1_A1, LB_S1_A2, LB_S1_A7,      LB_S2, LB_S2_BUSY, LB_S2_A1, LB_S2_A2, LB_S2_A5, LB_S2_A7,      LB_ER, LB_ER_LOOP  } Labels;    int ROM_LIMONAD[] =  {      SET_S,  S0,      BREAK,        /* --- Состояние S0 (0 монет) --- */      LABEL,  LB_S0,      SET_S,  S0,      LABEL,  LB_S0_BUSY,      LD_IN,      JMP_IF, _M, LB_S1,      // В S1 (через входную точку с EXEC A0)      JMP_IF, _V, LB_ER,     // Взлом      JMP_IF, _T, LB_S0_A4,      JMP_IF, _P, LB_S0_A2,      JMP_IF, _O, LB_S0_A4,      JMP,  LB_S0_BUSY,      // Рекурсия ожидания        LABEL,  LB_S0_A4, EXEC, A4, JMP, LB_S0_BUSY,      LABEL,  LB_S0_A2, EXEC, A2, JMP, LB_S0_BUSY,        /* --- Состояние S1 (1 монета) --- */      LABEL,  LB_S1,      SET_S,  S1,      EXEC,   A0,              // Прием первой монеты      LABEL,  LB_S1_BUSY,      LD_IN,      JMP_IF, _M, LB_S2,      // В S2 (через входную точку с EXEC A0)      JMP_IF, _V, LB_ER,      JMP_IF, _T, LB_S1_A1,      JMP_IF, _P, LB_S1_A2,      JMP_IF, _O, LB_S1_A7,      JMP,  LB_S1_BUSY,        LABEL,  LB_S1_A1, EXEC, A1, JMP, LB_S0,      LABEL,  LB_S1_A2, EXEC, A2, JMP, LB_S1_BUSY,      LABEL,  LB_S1_A7, EXEC, A7, JMP, LB_S0,        /* --- Состояние S2 (2 монеты) --- */      LABEL,  LB_S2,      SET_S,  S2,      EXEC,   A0,              // Прием второй монеты      LABEL,  LB_S2_BUSY,      LD_IN,      JMP_IF, _M, LB_S2_A5,   // Выдача      JMP_IF, _V, LB_ER,      JMP_IF, _T, LB_S2_A1,      JMP_IF, _P, LB_S2_A2,      JMP_IF, _O, LB_S2_A7,      JMP,  LB_S2_BUSY,        LABEL,  LB_S2_A5, EXEC, A5, JMP, LB_S0,      LABEL,  LB_S2_A1, EXEC, A1, JMP, LB_S0,      LABEL,  LB_S2_A2, EXEC, A2, JMP, LB_S2_BUSY,      LABEL,  LB_S2_A7, EXEC, A7, JMP, LB_S0,        /* --- Состояние ERR --- */      LABEL,  LB_ER,      SET_S,  ERR,      EXEC,   A3,             // Фиксация взлома      EXEC,   A6,             // Сигнал сервиса      HALT                    // Блокировка  };  //------------------------------------------    /* Обработчик сигналов: здесь происходят физические действия */  void Out_Action(UVM &VM)  {      LOG("\nACTION: %s -> NEXT STATE: %s", Actions[VM.REG_OUT], States[VM.CUR_S]);        if(VM.REG_OUT == A6)      {          LOG("\nБЛОКИРУЮ МАШИНУ.");          VM.F_IS_RUN = 0;      }  }    void In_Action(UVM &VM)  {      LOG("\nЖДУ СИГНАЛ. STATE = [%s] > ", States[VM.CUR_S]);      VM.REG_IN = toupper(getche()); // WAIT INPUT...  }    void Break_Action(UVM &VM)  {      LOG("\nSTATE:IN:OUT = [%s] [%s] [%s]\nНажмите любую клавишу для продолжения...", States[VM.CUR_S], In_Actions[VM.REG_IN] , Actions[VM.REG_OUT]);      getch();  }    char* load_bin(const char *fname, int *n)  {      *n = 0;      FILE *f = fopen(fname, "rb");      if (!f) return NULL;      fseek(f, 0, 2); long len = ftell(f); rewind(f);      char *b = (len > 0) ? (char*)malloc(len) : NULL; // Проверка на пустой файл      if (b) *n = fread(b, 1, len, f);      if(*n!=len) { free(b); b = NULL; }      fclose(f);      return b;  }    int main()  {      setlocale(LC_ALL, "en_US.UTF-8");        LOG("--- КЛАССИЧЕСКАЯ VM C ИНЖЕНЕРНЫМ МОНИТОРОМ (1960) ---\n");        //------------------------------------------      // Загрузить программу      //------------------------------------------      LOG("\n------- LOAD ROM -------");      LOG("\nЗАГРУЗИТЬ ROM С ЛЕНТЫ?: Y/N");      int *ROM, ROM_LEN;      if(toupper(getch()) == 'Y')      {          LOG("\nГРУЖУ: machine_limonad.bin");          ROM = (int*)load_bin("machine_limonad.bin", &ROM_LEN);          ROM_LEN = ROM_LEN / sizeof(int);          if(!ROM)          {              LOG("\nERR: ФАЙЛ НЕ НАЙДЕН. КОНЕЦ РАБОТЫ.");              return 0;          }      }      else      {          LOG("\nИСПОЛЬЗУЮ ВСТРОЕННЫЙ ROM");          ROM = ROM_LIMONAD;          ROM_LEN = sizeof(ROM_LIMONAD) / sizeof(int);          // Рассчитать метки переходов          set_jmps(ROM, ROM+ROM_LEN, 1000);      }        DISASSEMBLER(ROM, 0, ROM_LEN); // Вывести программу на экран        LOG("\nВВЕДИТЕ СИГНАЛ: M - монета, V - вскрытие, T - противоход, P - пусто, O - отмена. \n");        //------------------------------------------      // Инициализировать VM      //------------------------------------------        UVM VM;      // Установить обработчики сигналов      VM.out_signal_handler      = Out_Action;      VM.in_signal_handler       = In_Action;      VM.break_signal_handler    = Break_Action;        // Установить начальное состояние      VM.ROM        = ROM;      VM.IP         = 0;      VM.CUR_S      = S0;      VM.REG_IN     = P;      VM.REG_OUT    = A2;      VM.F_IS_RUN   = 1;        // Запустить цикл машины      LOG("\n------- RUN PROGRAM -------");      machine_loop(VM);      LOG("\n--- МАШИНА ОСТАНОВЛЕНА ---\n");        getch();      return 0;  }  

6. ТРАНСПИЛЯЦИЯ: FSM-ТАБЛИЦА -> С

                ──────▄▀▄─────▄▀▄                  ─────▄█░░▀▀▀▀▀░░█▄                  ─▄▄──█░░░░░░░░░░░█──▄▄                  █▄▄█─█░░▀░░┬░░▀░░█─█▄▄█  

У нас есть VM универсальный исполнитель, и FSM-таблицы автоматов. Напрашивается идея сделать компилятор FSM-таблиц в байт-код и исключить ручное кодирование.
Выше мы уже разворачивали данный таблицей граф в С-код.
Функция transpile_C_switch() разворачивает таблицу в наглядный код на С со switch, а transpile_C_goto() – в приближенный к ассемблерному код с goto.

Биекции транспиляции:

ОЦИФРОВАННЫЙ ГРАФ (МАТРИЦА)             ГЕНЕРИРУЕМЫЙ C-КОД (SWITCH)    +---------------------------+           +---------------------------+    | S_curr | In | S_next | Act|           | void machine_logic(int in)|    +--------+----+--------+----+           | {                         |    |   0    | 'M'|   1    |  0 | ------->  |   switch (state)          |    |   0    | 'V'|   3    |  3 |           |   {                       |    +--------+----+--------+----+           |     case S0: // Блок (A)  |                                            |     {                     |         (A) ДИСПЕТЧЕР СОСТОЯНИЙ            |       switch (in)         |         Входим по состоянию (S)            |       {    // Блок (B)    |                                            |         case 'M': // (C)  |         (B) ДИСПЕТЧЕР ВХОДА                |           process(S1, A0);|         Входим по входному символу (X)     |           break;          |                                            |         case 'V': // (D)  |         (C, D) РЕБРА ГРАФА                 |           process(S3, A3);|       Поменять состояние и выдать сигнал   |           break;          |                                            |       }                   |         (E) ШАГ АВТОМАТА ЗАКОНЧЕН          |       break; // (E)       |         Выход                              |     }                     |                                            |     ...                   |                                            |   }                       |    +---------------------------+           +---------------------------+    ОЦИФРОВАННЫЙ ГРАФ (МАТРИЦА)             ГЕНЕРИРУЕМЫЙ C-КОД (GOTO)    +---------------------------+           +---------------------------+    | S_curr | In | S_next | Act|           | void machine_logic(int in)|    +--------+----+--------+----+           | {                         |    |   0    | 'M'|   1    |  0 | --(A)-->  |   if (state == S0) goto L0|    |   0    | 'V'|   3    |  3 | --(A)-->  |   if (state == S1) goto L1|    +--------+----+--------+----+           |   ...                     |                                            |                           |         (A) ДИСПЕТЧЕР ВХОДА                | L0: // Состояние S0       |         Отображение индекса S              | {                         |         в адрес метки L                    |   if (in == 'M') { // (B) |                                            |     process(S1, A0);      |         (B) РЕБРО ГРАФА                    |     return;               |         Отображение пары (S, In)           |   }                       |         в смену состояния и действие       |   if (in == 'V') { // (C) |                                            |     process(S3, A3);      |         (C) ШАГ АВТОМАТА ЗАКОНЧЕН          |     return;               |         Выход из функции                   |   }                       |                                            | }                         |                                            | ...                       |                                            | }                         |    +---------------------------+           +---------------------------+  

7. КОМПИЛЯТОР: FSM-ГРАФ -> БАЙТКОД

Транспиляция в С-код с goto – почти тот же ассемблерный код, только чуть в иной грамматике. После его изучения генерация байт-кода VM в compile() прозрачна:

СТРКУТУРА СУПЕР-БЛОКА (СООТВЕТСТВУЕТ СТРОКЕ FSM-ТАБЛИЦЫ)    ВХОД ИЗ ДРУГИХ БЛОКОВ (JMP STATE_Sn)                 |                 v  +---------------------------------------+  | 1. БЛОК ИНИЦИАЛИЗАЦИИ (Entry)         |  |    LABEL STATE_Sn  <------------------+--- Метка входа в состояние  |    SET_S s      <---------------------+--- Установить состояние в REG_S  +---------------------------------------+                 |                 v  +---------------------------------------+  | 2. БЛОК ОПРОСА (Sensing Loop)         |  |    LABEL IN_Sn  <-----------+         |  |    LD_IN        <-----------+---------+--- Ожидание сигнала (REG_IN)  +---------------------------------------+                 |                 v  +---------------------------------------+  | 3. ДИСПЕТЧЕР (Dispatcher)             |  |    JMP_IF X_1, ID_1 ------------------+---> [К обработчику 1]  |    JMP_IF X_2, ID_2 ------------------+---> [К обработчику 2]  |    ...                                |  |    JMP_IF X_n, ID_n ------------------+---> [К обработчику n]  |    JMP IN_Sn        ------------------+---> [Безусловный переход к LD_IN  +---------------------------------------+      если нет совпадений]                 |                 | (Линейное продолжение кода)                 v  +---------------------------------------+  | 4. ОБРАБОТЧИКИ (Handlers / Edges)     |  |                                       |  |  LABEL ID_1:                          |  |    EXEC Action_1                      |  |    JMP S_next_1 ----------------------+---> [ВЫХОД В СЛЕДУЮЩИЙ СУПЕР-БЛОК]  |                                       |  |  LABEL ID_2:                          |  |    EXEC Action_2                      |  |    JMP S_next_2 ----------------------+---> [ВЫХОД В СЛЕДУЮЩИЙ СУПЕР-БЛОК]  +---------------------------------------+  

Функция emit() – генератор кода, берет размер команды из OP_SIZE и извлекает из стека нужное количество аргументов. Отображает мнемонику в машинный байт-код и в читаемый человеком текст ассемблера.

Задание:
– просмотреть файлы machine_limonad_1.cpp, machine_limonad_2.cpp, machine_limonad.asm, устанвить биекции между кодом в этих файлах
– пошагово пройти в отладчике код, начиная с main(), понять его работу.
– загрузить в VM байткод machine_limonad.bin, проверить его выполнение.

// umt_vm_compiler.cpp#include <stdlib.h>  #include <stdarg.h>  #include <conio.h>  #include <string.h>  #include <ctype.h>  #include <locale.h>    #define LOG printf    //------------------------------------------  // КОМПИЛЯТОР ДЛЯ УНИВЕРСАЛЬНОЙ МАШИНЫ ТЬЮРИНГА (УМТ)  //------------------------------------------    //------------------------------------------  // СИСТЕМА КОМАНД VM  //------------------------------------------  typedef enum  {      // Достаточный набор команд для УМТ      LD_IN,   // Считать входной сигнал в регистр      JMP,     // Безусловный переход. Перейти по адресу Y      JMP_IF,  // Условный переход. Если вход == X, перейти по адресу Y, иначе — к следующей команде      EXEC,    // Выполнить внешнее действие Z      SET_S,   // Сменить номер состояния в регистре состояний      LABEL,   // Маркер метки для JMP_IF      BREAK,   // Точка останова (DEBUG)      HALT,     // Остановка машины        OpCodes_Total  } OpCode;    // Размеры команд (сколько ячеек памяти занимает команда вместе с аргументами)  const int OP_SIZE[] =  {      1, // LD_IN      2, // JMP <метка>      3, // JMP_IF <условие> <метка>      2, // EXEC <номер_действия>      2, // SET_S <номер_состояния>      2, // LABEL <номер_метки>      1, // BREAK      1  // HALT  };    // Названия команд для ассемблера и мониторинга  const char* MNEMONICS[] =  {      "LD_IN", "JMP", "JMP_IF", "EXEC", "SET_S", "LABEL", "BREAK", "HALT"  };  //------------------------------------------    //------------------------------------------  // GENERATE & COMPLILE PROGRAM BY FSM TABLE  //------------------------------------------  typedef struct { int state, action; } Step;  struct Compiler  {      char *ascii;    // Ассемблерный код      int *bin;       // Байткод      int *bin_p;      char *ascii_p;  };    // Замена id переходов в байткоде на смещения  void set_jmps(int *base, int *end, int id_count)  {      int *address_tab = (int*)malloc(id_count * sizeof(int));        // Pass 1: Собираем адреса меток      int *p = base;      while (p < end)      {          if (*p == LABEL) address_tab[p[1]] = (int)(p - base);          p += OP_SIZE[*p];      }        // Pass 2: Дизассемблируем код и заменяем id меток на смещения от base      p = base;      while (p < end)      {          OpCode op = (OpCode)*p;          if (op == LABEL)  p[1] = (int)(p - base);          if (op == JMP)    p[1] = address_tab[p[1]];          if (op == JMP_IF) p[2] = address_tab[p[2]];          p += OP_SIZE[op];      }        free(address_tab);  }    void emit(Compiler &C, OpCode op, ...)  {      va_list ap;      va_start(ap, op);        //------------------------------------------      // Компиляция байткода      *C.bin_p++ = op;      //------------------------------------------        //------------------------------------------      // Компиляция ассемблерного кода      C.ascii_p += sprintf(C.ascii_p, "  %-7s", MNEMONICS[op]);      for (int i = 0; i < OP_SIZE[op] - 1; i++)      {          int val = va_arg(ap, int);          *C.bin_p++ = val;          C.ascii_p += sprintf(C.ascii_p, (i == 0) ? " %-3d" : ", %-3d", val);      }      C.ascii_p += sprintf(C.ascii_p, "\n");      //------------------------------------------        va_end(ap);  }    int compile(Compiler &C, Step **matrix, int n_states, int n_inputs, const char *in_mset)  {  /*      Биекция "Граф -> Код":      Архитектура: Линейный диспетчер с выносом обработчиков.        Каждый узел графа разворчивается в 3 блока ассемблерных комманд        1. Блок опроса (Inputs Handler)      2. Блок диспетчера (Dispatcher): Компактный список JMP_IF для быстрой         проверки входящих символов. Если ни одно не сработало — возврат в Блок опроса.      3. Блок исполнения и перехода (Outputs Handler): Изолированные сегменты EXEC + JMP,   */        C.bin_p = C.bin;      C.ascii_p = C.ascii;        int id = 0;        // "Дерево" на индексах: разметка всех точек входа      int *ls = (int*)malloc(n_states * sizeof(int)); // метки обработки состояний      int *ll = (int*)malloc(n_states * sizeof(int)); // метки блоков с циклом ожидания входящего сигнала      for (int i = 0; i < n_states; i++) { ls[i] = id++; ll[i] = id++; }        for (int s = 0; s < n_states; s++)      {          //------------------------------------------          // 1. Установка текущго состояния и ожидание входящего сигнала          emit(C, LABEL, ls[s]);          emit(C, SET_S, s);          emit(C, LABEL, ll[s]);          emit(C, LD_IN);          //------------------------------------------            int start_br = id; // Запоминаем, с какого ID начинаются обработчики этого состояния. Сами обработчики вынесены за цикл опроса (линейная структура).            //------------------------------------------          // 2. Блок диспетчера: Генерация ребер (переходов)          for (int i = 0; i < n_inputs; i++) emit(C, JMP_IF, in_mset[i], id++);          emit(C, JMP, ll[s]); // Если ни одно условие не сработало, возвращаемся на LD_IN          //------------------------------------------            //------------------------------------------          // 3. Блок генерации исходящих сигналов и перехода в блок Диспетчера следующего состояния          for (int i = 0; i < n_inputs; i++)          {              emit(C, LABEL, start_br + i); // Используем сохраненную метку              emit(C, EXEC, matrix[s][i].action);              emit(C, JMP, ls[matrix[s][i].state]);          }          //------------------------------------------      }        emit(C, HALT);      set_jmps(C.bin, C.bin_p, id); // Расчёт и установка смещений в JMP и JMP_IF        free(ls); free(ll);      return (int)(C.bin_p - C.bin);  }  //------------------------------------------    int save_bin(const char *fname, char *b, size_t n)  {      FILE *f = fopen(fname, "wb");      if (!f) return 0;      size_t r = fwrite(b, 1, n, f);      fclose(f);      return r == n;  }    //------------------------------------------  // FSM ДЛЯ КОМПИЛЯЦИИ  //------------------------------------------  #define ROW(...) (Step[]){ __VA_ARGS__ }  Step *Machine_Limonad[] =  {                      /*     M       V      T        P      O    */      /* S0  */ [0] = ROW({1, 0}, {3, 3}, {0, 4}, {0, 2}, {0, 4}),      /* S1  */ [1] = ROW({2, 0}, {3, 3}, {0, 1}, {1, 2}, {0, 7}),      /* S2  */ [2] = ROW({0, 5}, {3, 3}, {0, 1}, {2, 2}, {0, 7}),      /* ERR */ [3] = ROW({3, 6}, {3, 6}, {3, 6}, {3, 6}, {3, 6})  };  const char *Inputs = "MVTPO";  //------------------------------------------    //------------------------------------------  // FSM -> C TRANSPILLER  //------------------------------------------  // SWITCH VERSION  void transpile_C_switch(char* p, Step **matrix, int n_states, int n_inputs, const char *in_mset)  {      p += sprintf(p, "void machine_logic(int in_signal)\n{\n    switch (state)\n    {\n");        for (int s = 0; s < n_states; s++)      {          p += sprintf(p, "        case S%d:\n        {\n            switch (in_signal)\n            {\n", s);          for (int i = 0; i < n_inputs; i++)          {              // Биекция: Входной символ -> Ветвь Case -> Вызов функции перехода              p += sprintf(p, "                case '%c':\n                {\n", in_mset[i]);              p += sprintf(p, "                    process_step(S%d, A%d);\n", matrix[s][i].state, matrix[s][i].action);              p += sprintf(p, "                    break;\n                }\n");          }          p += sprintf(p, "            }\n            break;\n        }\n");      }      p += sprintf(p, "    }\n}\n");  }    // GOTO VERSION  void transpile_C_goto(char* p, Step **matrix, int n_states, int n_inputs, const char *in_mset)  {      p += sprintf(p, "void machine_logic(int in_signal)\n{\n    /* Диспетчер входа в фазу (State Entry Dispatcher) */\n");        for (int s = 0; s < n_states; s++) p += sprintf(p, "    if (state == S%d) goto L_S%d;\n", s, s);        p += sprintf(p, "    return;\n\n");        for (int s = 0; s < n_states; s++)      {          p += sprintf(p, "L_S%d:\n{\n", s);          for (int i = 0; i < n_inputs; i++)          {              p += sprintf(p, "    if (in_signal == '%c')\n    {\n        process_step(S%d, A%d);\n        return;\n    }\n",                           in_mset[i], matrix[s][i].state, matrix[s][i].action);          }          p += sprintf(p, "    return;\n}\n\n");      }        p += sprintf(p, "}\n");  }    //------------------------------------------      int main()  {      setlocale(LC_ALL, "en_US.UTF-8");        LOG("\n--- КОМПИЛЯТОР FSM ДЛЯ КЛАССИЧЕСКОЙ VM C ИНЖЕНЕРНЫМ МОНИТОРОМ (1960) ---\n");        // Выделение буфера: ~1024 байт на каждое ребро графа      int MEM_LEN = 4 * 5 * 1024 + 1024; // n_states * n_inputs * 1024        char* ASM  = (char*)malloc(MEM_LEN);      char* BIN  = (char*)malloc(MEM_LEN);      char* C_CODE_1  = (char*)malloc(MEM_LEN);      char* C_CODE_2  = (char*)malloc(MEM_LEN);        //------------------------------------------      // КОМПИЛЯЦИЙ В БАЙТКОД VM      //------------------------------------------      Compiler C;      C.bin = (int*)BIN;      C.ascii = ASM;      int len = compile(C, Machine_Limonad, 4, 5, Inputs);      //------------------------------------------        //------------------------------------------      // ТРАНСПИЛЯЦИЯ В С      //------------------------------------------      transpile_C_switch(C_CODE_1, Machine_Limonad, 4, 5, Inputs);      transpile_C_goto(C_CODE_2, Machine_Limonad, 4, 5, Inputs);      //------------------------------------------        if(len)      {          LOG("\nКОМПИЛЯЦИЯ УСПЕШНА. ФАЙЛЫ:\nАССЕМБЛЕР - machine_limonad.asm\nБАЙТКОД FSM - machine_limonad.bin\nC-КОД (SWITCH) - machine_limonad_1.cpp\nC-КОД (GOTO) - machine_limonad_2.cpp");          save_bin("machine_limonad.bin", BIN, len * sizeof(int));          save_bin("machine_limonad.asm", ASM, strlen(ASM));          save_bin("machine_limonad_1.cpp", C_CODE_1, strlen(C_CODE_1));          save_bin("machine_limonad_2.cpp", C_CODE_2, strlen(C_CODE_2));      }      else      {          LOG("\nОШИБКА КОМПИЛЯЦИИ");      }      free(ASM); free(BIN); free(C_CODE_1); free(C_CODE_2);        getch();      return 0;  }  

8. ИСТОРИЯ: МОНЕТОПРИЕМНИКИ

★　★　★　　　　
_____★█████★
__★█████★
_★█████★•★
★█████★•★•★ ★
★█████★•★•★•★
_★█████★•★•★
__★█████★•★
_____★█████ ★
_________★__★
____________★
__________★

Этот исторический очерк демонстрирует степень проработки узлов автоматов и уровень технического развития умов в этой индустрии.
Первый торговый автомат Vending Machine разработан в 1925 г. и запатентован в 1928-м. В 1940-60-е монетоприемники были механическими устройствами. Их называли «slug rejectors» – отсекатели фальшивок. Работали они по принципу «полосы препятствий», где каждая монета проходила через серию физических тестов.

1. Тест на размер и вес. Сначала монета попадала на «колыбель» (cradle) – систему рычагов с противовесом. От слишком легкой монеты рычаг не наклонялся, и она уходила в возврат. Слишком большая монета застревала в калиброванном отверстии. Правильная монета своим весом опрокидывала рычаг и катилась дальше.

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

3. Тест на проводимость. Магнитное торможение был самым продвинутым тестом того времени. Когда монета пролетает мимо магнита, в ней возникали токи. Настоящая монета слегка замедлялась и падала по точно выверенной траектории. У медной или свинцовой фальшивки была другая проводимость. Она пролетала слишком быстро или слишком медленно и промахивалась мимо приемного желоба, падая в отсек возврата.

4. Проверка на отверстия. Многие пытались использовать обычные стальные шайбы. Чтобы их отсечь, в некоторых механизмах стоял крошечный щуп-рычаг. Если он попадал в отверстие посередине, механизм блокировался и отправлял предмет в возврат.

5. Определение номинала. В многомонетных аппаратах были наклонные дорожки с отверстиями разного размера. Сначала шла самая маленькая прорезь (для 10 центов). Затем побольше (для 5 центов). И самая большая в конце (для 25 центов). Монета катилась, пока не находила отверстие своего размера и не проваливалась в нужный накопитель. У современных монетоприемников те же принципы, но вместо рычагов и магнитов там стоят лазерные датчики и катушки индуктивности.

РАЗДЕЛ: ГРАММАТИКА И VM BRAINFUCK

Это усложнённый раздел курса. Его можно пропустить начинающим.
В кодировании на языке Brainfuck [26] нет большой пользы либо смысла. Мы используем его лишь для показа нескольких идей при кодинге автоматов.

1. ИСТОРИЧЕСКАЯ СПРАВКА

░░░░░░░░░░░░░░░░░░░░░▄▄▄░░░░
░░░░░░░░░░░░░░░░░░░▄█████▄░░
░░░░░░░░░░░░░░░░░░░████████▄
░░░░░░░░░░░░░░░░░░░███░░░░░░
░░░░░░░░░░░░░░░░░░░███░░░░░░
░░░░░░░░░░░░░░░░░░░███░░░░░░
░░░░░░░░░░░░░░░░░░░███░░░░░░
░░░░░░░░░░░░░░░░░░░███░░░░░░
░░░░░░░░░░░░░▄▄▄▄▄████░░░░░░
░░░░░░░░▄▄████████████▄░░░░░
░░░░▄▄██████████████████░░░░
▄▄██████████████████████░░░░
░▀▀████████████████████▀░░░░
░░░░▀█████████████████▀░░░░░
░░░░░░▀▀███████████▀▀░░░░░░░
░░░░░░░░░▀███▀▀██▀░░░░░░░░░░
░░░░░░░░░░█░░░░██░░░░░░░░░░░
░░░░░░░░░░█░░░░█░░░░░░░░░░░░
░░░▄▄▄▄███████▄███████▄▄▄▄░░

Под «алгоритмом» понимаем последовательность не делимых далее действий (или «операций») для конкретного исполнителя. При наличии в алгоритме операций перехода (или «ветвления») алгоритму ставят в соответствие граф. «Интерпретатор» – физическая или программная машина, способная выполнять алгоритм, данный в конкретной грамматике.
Интерпретатор Brainfuck создан в 1993 г. швейцарским студентом-физиком Урбаном Мюллером. Доступ к памяти в нём копирует ленту механической машины Тьюринга, а грамматика взята из формальной системы P′′ Бёма.
В 1964 году Бём доказал теорему, что для реализации любой «вычислимой» (то есть гарантированно приводящей к результату за конечное время на данном вычислителе) функции достаточно трёх структур: последовательности (sequence), выбора (if) и цикла (while).
Императивного, то есть пошагово меняющего состояние памяти языка программирования с if и goto, достаточно для реализации Универсальной Машины Тьюринга.
Представим интерпретатор Brainfuck вычислителем из двух FSM: Универсальной Машины Тьюринга (УМТ) и доменной машины – BF Machine.
Пространство состояний УМТ (или Автомата-Контроллера) – это множество целых чисел. Для него нет аппаратуры либо памяти, а есть входящий символ в ячейке REG_IN, номер текущего состояния в ячейке REG_S и таблица переходов. УМТ получает число, выдает число и меняет свое внутреннее число. Эта абстрактная машина загружает с постоянного запоминающего устройства FSM-таблицу доменного автомата BF Machine.
BF Machine (или доменный Автомат-Исполнитель) – это «железное тело». Его пространство состояний определено положениями «головки» и значениями в ячейках оперативной памяти (или «ленты»). Он лишён логики перехода по состояниям, и выполняет команды от Контроллера.

2. АЛФАВИТЫ УМТ

«Алфавиты» в FSM-таблице – это доменные множества: цифры приходящие и уходящие в конкретный механизм и имеющие значение только для него.
По условию, на каждом шаге BF Machine сравнивает значение в ячейке под «головкой» с нулём, и выставляет в REG_IN 0 или 1 соответственно.

1. Входной алфавит УМТ X (сигналы от «датчиков» BF Machine):    +----------+-----------------------------------------------------+  | Входной  | Физика механизма                                    |  | Символ   |                                                     |  +----------+-----------------------------------------------------+  | ZERO     | Значение в ячейке под «головкой» нуль               |  | NZ       | Значение в ячейке под «головкой» не нуль            |  +----------+-----------------------------------------------------+    2. Выходной алфавит УМТ Y (сигналы для подачи на вход BF Machine):    +----------+-----------------------------------------------------+  | Выходной | Физическое действие механизма                       |  | Символ   |                                                     |  +----------+-----------------------------------------------------+  | ACT_ADD  | Инкремент значения в текущей ячейке                 |  | ACT_SUB  | Декремент значения в текущей ячейке                 |  | ACT_RIGHT| Перемещение головки на одну позицию вправо          |  | ACT_LEFT | Перемещение головки на одну позицию влево           |  | ACT_OUT  | Вывод значения текущей ячейки на экран              |  | ACT_IN   | Чтение значения с клавиатуры в текущую ячейку       |  | ACT_NOP  | No Operation. Механизмы неподвижны. Используется    |  |          | при логических переходах (например, на скобках).    |  +----------+-----------------------------------------------------+    3. Команды в грамматике BF и действия интерпретатора:    +--------+-----------+---------------------------------------+--------------+  | КОМАНДА|ИСХ.СИМВОЛ |            ФИЗИЧЕСКОЕ ДЕЙСТВИЕ        |  ОБОЛОЧКА    |  |        |УМТ(Action)|          (Работа узлов BF машины)     |              |  +--------+-----------+---------------------------------------+--------------+  |   +    |  ACT_ADD  | Инкремент значения в ячейке RAM       |  №1 (ALU)    |  |   -    |  ACT_SUB  | Декремент значения в ячейке RAM       |  №1 (ALU)    |  |   >    | ACT_RIGHT | Сдвиг головки RAM вправо              |  №4 (RAM)    |  |   <    | ACT_LEFT  | Сдвиг головки RAM влево               |  №4 (RAM)    |  |   .    |  ACT_OUT  | Вывод символа из памяти на экран      |  №1 (I/O)    |  |   ,    |  ACT_IN   | Ввод символа с клавиатуры в память    |  №1 (I/O)    |  |   [    |  ACT_NOP  | Переход в состояние Sn (JMP_IF_ZERO)  | №2,3(FSM/PDA)|  |   ]    |  ACT_NOP  | Переход в состояние Sn (JMP_IF_NZ)    | №2,3(FSM/PDA)|  +--------+-----------+---------------------------------------+--------------+  

Скобки [ ] соответствуют условным переходам. Прямой аналог в ассемблере CPU: операции JUMP_Z и JUMP_NZ (перейти по метке LABEL если в регистре REG_IN нуль либо не нуль соответственно):

// ЦИКЛ НА ЯЗЫКЕ С  while (REG_IN != 0)  {      ... // КОМАНДЫ ЦИКЛА      ... // (ВЫПОЛНЯЮТ ДЕЙСТВИЯ, МЕНЯЮТ ПЕРЕМЕННУЮ REG_IN ЧТОБЫ ВЫЙТИ ИЗ ЦИКЛА)  }    // ЦИКЛ НА АССЕМБЛЕРЕ, ДАННЫЙ КОМАНДАМИ JUMP_Z, JUMP_NZ И МЕТКАМИ    JUMP_Z REG_IN, SKIP_LOOP  LABEL LOOP      ... // КОМАНДЫ ЦИКЛА      ... // (ВЫПОЛНЯЮТ ДЕЙСТВИЯ, МЕНЯЮТ РЕГИСТР REG_IN ЧТОБЫ ВЫЙТИ ИЗ ЦИКЛА)  JUMP_NZ REG_IN, LOOP  LABEL SKIP_LOOP  

Команда JUMP (переход) для УМТ означает смену состояния на число из таблицы переходов REG_S = ЧИСЛО.

3. СООТВЕТСТВИЕ: КОД BF -> ТАБЛИЦА FSM (АНАЛИЗ)

Ранее мы переводили FSM-таблицу в байт-код для VM. Преобразуем теперь байт-код в FSM-таблицу.
Вычислитель (или «computer») математически эквивалентен одному большому числу, размещённому в ячейках RAM и регистрах CPU. Предназначение каждой команды на BF – менять это число, то есть строить некоторую последовательность чисел, которую можно перенумеровать, начав с нуля.
Из-за такого стечения обстоятельств программа в грамматике BF становится эквивалентом переходов по состояниям компьютера. Общее количество состояний компьютера для конкретного алгоритма равно количеству команд в программе на BF.
В теории автоматов машина останавливается, после перехода в состояние из множества Финальных состояний F. Для остановки машины введём «финальным» состояние численно равным индексу последней команды программы на BF.

4. СООТВЕТСТВИЕ: КОД BF -> ТАБЛИЦА FSM (ПРАВИЛА)

Таблица правил перевода слов грамматики BF в FSM-таблицу:

+---------+-----------+-----------+-------------+------------+  | КОМАНДА | ТЕКУЩЕЕ   | ВХОД (X)  | СЛЕДУЮЩЕЕ   | ВЫХОД (A)  |  |   BF    | СОСТОЯНИЕ | (Датчик)  | СОСТОЯНИЕ   | (Действие) |  +---------+-----------+-----------+-------------+------------+  |    +    |    Sn     |  0 (ZERO) |    Sn + 1   |  ACT_ADD   |  |    +    |    Sn     |  1 (NZ)   |    Sn + 1   |  ACT_ADD   |  +---------+-----------+-----------+-------------+------------+  |    -    |    Sn     |  0 (ZERO) |    Sn + 1   |  ACT_SUB   |  |    -    |    Sn     |  1 (NZ)   |    Sn + 1   |  ACT_SUB   |  +---------+-----------+-----------+-------------+------------+  |    >    |    Sn     |  0 (ZERO) |    Sn + 1   |  ACT_RIGHT |  |    >    |    Sn     |  1 (NZ)   |    Sn + 1   |  ACT_RIGHT |  +---------+-----------+-----------+-------------+------------+  |    <    |    Sn     |  0 (ZERO) |    Sn + 1   |  ACT_LEFT  |  |    <    |    Sn     |  1 (NZ)   |    Sn + 1   |  ACT_LEFT  |  +---------+-----------+-----------+-------------+------------+  |    .    |    Sn     |  0 (ZERO) |    Sn + 1   |  ACT_OUT   |  |    .    |    Sn     |  1 (NZ)   |    Sn + 1   |  ACT_OUT   |  +---------+-----------+-----------+-------------+------------+  |    ,    |    Sn     |  0 (ZERO) |    Sn + 1   |  ACT_IN    |  |    ,    |    Sn     |  1 (NZ)   |    Sn + 1   |  ACT_IN    |  +---------+-----------+-----------+-------------+------------+  |    [    |   S_open  |  0 (ZERO) |  S_close + 1|  ACT_NOP   |  |    [    |   S_open  |  1 (NZ)   |  S_open + 1 |  ACT_NOP   |  +---------+-----------+-----------+-------------+------------+  |    ]    |   S_close |  0 (ZERO) |  S_close + 1|  ACT_NOP   |  |    ]    |   S_close |  1 (NZ)   |  S_open + 1 |  ACT_NOP   |  +---------+-----------+-----------+-------------+------------+  

1. Каждая команда BF порождает две строки в FSM-таблице, что полностью покрывает входной алфавит X = {0, 1}.

2. Сигналу ACT_NOP соответствует отсутствие физического дейсвия. Меняется только номер состояния в регистре УМТ.

3. Финальное состояние S_halt (не указано в таблице). Числено равно индексу последней команды в программе.

4. S_open / S_close: номера состояний, соответствующие открывающей и закрывающей скобкам конкретного цикла. Равны индексам соответствующих скобок [ `] в программе.

5. ИНТЕРПРЕТАТОР BF НА С

«Программа» – это алгоритм, данный в грамматике, понятной человеку и компьютеру. Хорошо составленную программу пишут и читают как технический текст, где комментарии и код равноправны.
Ниже – текст интерпретатора BF в грамматике С. Основные блоки: УМТ, доменная машина BF, транспилятор bf_to_matrix() (отображает BF-код в FSM-таблицу).

// bf.cpp#include <stdlib.h>#include <conio.h>#include <string.h>#include <locale.h>#define LOG printf//------------------------------------------// УНИВЕРСАЛЬНАЯ МАШИНА ТЬЮРИНГА И ИСПОЛНИТЕЛЬ BRAINFUCK//------------------------------------------//------------------------------------------// ОБОЛОЧКА: УМТ//------------------------------------------typedef struct { int state, action; } Step;struct UTM{    int REG_S;   // Регистр текущего состояния (Phase)    int REG_IN;  // Регистр входного сигнала (Input Symbol)    int REG_OUT; // Регистр выходного действия (Action Symbol)    Step** ROM;  // Указатель на таблицу переходов (Оцифрованный граф)};// Математический акт перехода (Чистая функция δ)void UTM_Cycle(struct UTM* machine){    // Выбор строки в таблице отношений по текущему состоянию и входу    Step transition = machine->ROM[machine->REG_S][machine->REG_IN];    // Обновление регистров    machine->REG_S   = transition.state;  // Переход в новую фазу    machine->REG_OUT = transition.action; // Формирование команды для исполнителя}//------------------------------------------//------------------------------------------// ДОМЕННАЯ ОБОЛОЧКА: МАШИНА BRAINFUCK//------------------------------------------// ОПРЕДЕЛЕНИЕ АЛФАВИТОВ (X и A)// Входящий алфавит X (Состояние ячейки ленты)enum BF_IN { IN_ZERO, IN_NZ };const char* IN_NAMES[] = { "ZERO", "NZ" };// Исходящий алфавит A (Действия исполнителя)enum BF_ACTIONS { ACT_ADD, ACT_SUB, ACT_RIGHT, ACT_LEFT, ACT_OUT, ACT_IN, ACT_NOP };const char* ACT_NAMES[] = { "ADD", "SUB", "RIGHT", "LEFT", "OUT", "IN", "NOP" };// Выполняет действия в реальном мире.// Реализует Биекцию между физикой (лентой) и математикой (регистрами УМТ)struct BF_DSM // DSM - Domain-Specific Machine{    unsigned char* RAM;    int head;     // Индекс выбранной ячейки в массиве памяти    int n_states; // Номер последнего состояния (конец программы)};void BF_Physical_Interface(struct UTM* utm, BF_DSM* bfm){    while(utm->REG_S < bfm->n_states - 1)    {        // 1. Физика -> Математика        // Преобразуем состояние ячейки в индекс входного алфавита Σ {0, 1}        utm->REG_IN = (bfm->RAM[bfm->head] == 0) ? 0 : 1;        // 2. Переход по таблице FSM        UTM_Cycle(utm);        // 3. Математика -> Физика        // Дешифруем REG_OUT в физические действия над агрегатами        switch (utm->REG_OUT)        {            //------------------------------------------            // БЛОК ОПЕРАЦИЙ ALU            //------------------------------------------            case ACT_ADD:   bfm->RAM[bfm->head]++; break;            case ACT_SUB:   bfm->RAM[bfm->head]--; break;            //------------------------------------------            // БЛОК ОПЕРАЦИЙ УПРАВЛЕНИЯ RAM (ВЫБОР АКТИВНОЙ ЯЧЕЙКИ)            //------------------------------------------            case ACT_RIGHT: bfm->head++; break;            case ACT_LEFT:  bfm->head--; break;            //------------------------------------------            // БЛОК ДЛЯ ПРИЁМА/ОТПРАВЛЕНИЯ СИГНАЛОВ ИЗ/В АППАРАТУРУ            //------------------------------------------            case ACT_OUT:   putchar(bfm->RAM[bfm->head]); break;            case ACT_IN:    bfm->RAM[bfm->head] = (unsigned char)getchar(); break;            case ACT_NOP:   break; // Состояние покоя исполнителя        }    }}//------------------------------------------//------------------------------------------// ТРАНСПИЛЯТОР//------------------------------------------// Транспилятор  BF-код -> FSM матрица/*Таблица правил для составления Отношения δ:S×X→S×A+---------+-----------+-----------+-------------+------------+| КОМАНДА | ТЕКУЩЕЕ   | ВХОД (X)  | СЛЕДУЮЩЕЕ   | ВЫХОД (A)  ||   BF    | СОСТОЯНИЕ | (Датчик)  | СОСТОЯНИЕ   | (Действие) |+---------+-----------+-----------+-------------+------------+|    +    |    Sn     |  0 (ZERO) |    Sn + 1   |  ACT_ADD   ||    +    |    Sn     |  1 (NZ)   |    Sn + 1   |  ACT_ADD   |+---------+-----------+-----------+-------------+------------+|    -    |    Sn     |  0 (ZERO) |    Sn + 1   |  ACT_SUB   ||    -    |    Sn     |  1 (NZ)   |    Sn + 1   |  ACT_SUB   |+---------+-----------+-----------+-------------+------------+|    >    |    Sn     |  0 (ZERO) |    Sn + 1   |  ACT_RIGHT ||    >    |    Sn     |  1 (NZ)   |    Sn + 1   |  ACT_RIGHT |+---------+-----------+-----------+-------------+------------+|    <    |    Sn     |  0 (ZERO) |    Sn + 1   |  ACT_LEFT  ||    <    |    Sn     |  1 (NZ)   |    Sn + 1   |  ACT_LEFT  |+---------+-----------+-----------+-------------+------------+|    .    |    Sn     |  0 (ZERO) |    Sn + 1   |  ACT_OUT   ||    .    |    Sn     |  1 (NZ)   |    Sn + 1   |  ACT_OUT   |+---------+-----------+-----------+-------------+------------+|    ,    |    Sn     |  0 (ZERO) |    Sn + 1   |  ACT_IN    ||    ,    |    Sn     |  1 (NZ)   |    Sn + 1   |  ACT_IN    |+---------+-----------+-----------+-------------+------------+|    [    |   S_open  |  0 (ZERO) |  S_close + 1|  ACT_NOP   ||    [    |   S_open  |  1 (NZ)   |  S_open + 1 |  ACT_NOP   |+---------+-----------+-----------+-------------+------------+|    ]    |   S_close |  0 (ZERO) |  S_close + 1|  ACT_NOP   ||    ]    |   S_close |  1 (NZ)   |  S_open + 1 |  ACT_NOP   |+---------+-----------+-----------+-------------+------------+*/Step** bf_to_matrix(const char* code, int* n_states_){    int n = (int)strlen(code), sp = -1;    int* stack = (int*)malloc(n * sizeof(int));    *n_states_ = n + 1;    Step** matrix = (Step**)malloc((*n_states_) * sizeof(Step*));    for (int i = 0; i < *n_states_; i++) matrix[i] = (Step*)malloc(2 * sizeof(Step));    for (int i = 0; i < n; i++)    {        int next = i + 1;        switch (code[i])        {            /* Команда | Текущее S | Вход (Σ) | След. S | Выход (A) */            case '+':                matrix[i][IN_ZERO] = (Step){next, ACT_ADD};                matrix[i][IN_NZ]   = (Step){next, ACT_ADD};                break;            case '-':                matrix[i][IN_ZERO] = (Step){next, ACT_SUB};                matrix[i][IN_NZ]   = (Step){next, ACT_SUB};                break;            case '>':                matrix[i][IN_ZERO] = (Step){next, ACT_RIGHT};                matrix[i][IN_NZ]   = (Step){next, ACT_RIGHT};                break;            case '<':                matrix[i][IN_ZERO] = (Step){next, ACT_LEFT};                matrix[i][IN_NZ]   = (Step){next, ACT_LEFT};                break;            case '.':                matrix[i][IN_ZERO] = (Step){next, ACT_OUT};                matrix[i][IN_NZ]   = (Step){next, ACT_OUT};                break;            case ',':                matrix[i][IN_ZERO] = (Step){next, ACT_IN};                matrix[i][IN_NZ]   = (Step){next, ACT_IN};                break;            case '[':                stack[++sp] = i; // Сохраняем адрес в PDA (стек)                matrix[i][IN_NZ]   = (Step){next, ACT_NOP};                /* matrix[i][IN_ZERO] будет прошит при встрече ']' */                break;            case ']':            {                int open = stack[sp--]; // Извлекаем адрес из PDA                matrix[i][IN_ZERO] = (Step){next, ACT_NOP};                matrix[i][IN_NZ]   = (Step){open + 1, ACT_NOP};                /* Back-patching: прошивка выхода для соответствующей '[' */                matrix[open][IN_ZERO] = (Step){next, ACT_NOP};                break;            }        }    }    /* Финальное состояние (HALT) — петля на графе в себя без действия */    matrix[n][IN_ZERO] = matrix[n][IN_NZ] = (Step){n, ACT_NOP};    free(stack);    return matrix;}//  Преобразование FSM матрицы в текстовую таблицуvoid matrix_to_string(Step** matrix, int n_states, char** num_table, char** mnem_table){    char *p_n = *num_table = (char*)malloc(n_states * 64), *p_m = *mnem_table = (char*)malloc(n_states * 128);    for (int i = 0; i < n_states; i++)    {        // Числовая таблица: [S_next_0 Act_0] [S_next_1 Act_1]        p_n += sprintf(p_n, "%3d: [%3d %2d] [%3d %2d]\n", i,            matrix[i][0].state, matrix[i][0].action, matrix[i][1].state, matrix[i][1].action);        // Таблица мнемоник: [IF IN -> NEXT_S, ACTION]        p_m += sprintf(p_m, "S%03d: [%-4s -> S%03d, %-5s] [%-4s -> S%03d, %-5s]\n", i,            IN_NAMES[0], matrix[i][0].state, ACT_NAMES[matrix[i][0].action],            IN_NAMES[1], matrix[i][1].state, ACT_NAMES[matrix[i][1].action]);    }}//------------------------------------------//------------------------------------------// ЗАГРУЗКА И ЗАПУСК ПРОГРАММ ИНТЕРПРЕТАТОРА ЯЗЫКА BRAINFUCK//------------------------------------------unsigned char tape[30000]; // ПАМЯТЬ RAMint main(int argc, char *argv[]){    setlocale(LC_ALL, "en_US.UTF-8");    LOG("ИНТЕРПРЕТАТОР ЯЗЫКА BRAINFUCK. КОД ПОМЕСТИТЬ В КАВЫЧКИ, ПЕРВЫМ ПАРАМЕТРОМ ПРИ ЗАПУСКЕ ПРИГРАММЫ. ПРИМЕР: brainfuck.exe \"++.\"");    char* code = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.";    if (argc > 1) code = argv[1];    //------------------------------------------    // 1. Алгоритм с УМТ    //------------------------------------------    memset(tape, 0, sizeof(tape));    int n_states;    Step** FSM = bf_to_matrix(code, &n_states); // BF code -> FSM table    // Вывод таблицы FSM на экран    char *num_table, *mnem_table;    matrix_to_string(FSM, n_states, &num_table, &mnem_table);    LOG("\nТАБЛИЦА ПЕРЕХОДОВ УМТ:\n%s\n\nFSM:\n%s\n\nFSM МНЕМО-КОД:\n%s", code, num_table, mnem_table);    free(num_table); free(mnem_table);    LOG("\nЗАГРУЖАЮ ТАБЛИЦУ BF FSM В УМТ");    UTM utm;    utm.ROM = FSM;    utm.REG_S = 0;    LOG("\nЗАПУСКАЮ ДОМЕННУЮ МАШИНУ\n");    BF_DSM bfm;    bfm.RAM = tape;    bfm.head = 0;    bfm.n_states = n_states;    BF_Physical_Interface(&utm, &bfm);    //------------------------------------------    getch();    return 0;}//------------------------------------------

6. СВЯЗЬ: CPU, СТЕКИ, ЯЗЫКИ

▄───▄
█▀█▀█
█▄█▄█
─███──▄▄
─████▐█─█
─████───█
─▀▀▀▀▀▀▀

CPU, стеки, языки образуют неразрывную связку, и мы полагаемся на неё, даже не вспоминая об этом.
Так, рекурсия использует LIFO-стек CPU. Её просто заменить циклом и стеком в памяти.
Стеки создают, например, и при обходе деревьев либо при эмуляции вызова функций в языке без такой возможности. Так, в Basic ZX Spectrum нет передачи параметров в функции, как в С. Решение: выделить массив и построить на нём стек самостоятельно. Что чрезвычайно просто: «стек» – это массив и указатель на текущую позицию в этом массиве.

0 REM ПРИМЕР СОЗДАНИЯЕ С-ПОДОБНОГО МЕХАНИЗМА ПЕРДАЧИ ПАРАМЕТРОВ В BASIC  1 REM ФУНКЦИЯ ADD() ПОЛУЧАЕТ 2 ПАРАМЕТРА, СКЛАДЫВАЕТ ИХ И ВОЗВРАЩАЕТ РЕЗУЛЬТАТ    10 DIM s(16): LET  sp = 0: REM Стек на 16 чисел и указатель  20 LET v = 5: GOSUB 500: REM Кладем первое число  30 LET v = 10: GOSUB 500: REM Кладем второе число  40 GOSUB 1000: REM Вызываем функцию сложения  50 GOSUB 600: REM Забираем результат со стека  60 PRINT "Result: "; v  70 STOP     500 REM --- PUSH (положить v на стек) ---  510 LET  sp =  sp + 1: LET s( sp) = v: RETURN     600 REM --- POP (забрать со стека в v) ---  610 LET v = s( sp): LET  sp =  sp - 1: RETURN     1000 REM --- FUNCTION: ADD ---  1010 GOSUB 600: LET a = v: REM Взяли второе  1020 GOSUB 600: LET b = v: REM Взяли первое  1030 LET v = a + b: GOSUB 500: REM Положили результат  1040 RETURN  

7. ПРАКТИКА: ЗАМЕНА РЕКУРСИИ ЦИКЛОМ

Языки высокого уровня скрывают управление памятью. BF возвращает нас к модели магазинной памяти ленточного автомата.
Ниже две реализации интерпретатора BF. Их код не объяснят устройство интерпретатора (оно дано выше). Первая реализация демонстрирует применение стека CPU, вторая – стека в памяти.
Рекурсию или стек в интерпретаторе BF порождает вложение скобок [ [ ] ].

8. РЕКУРСИВНЫЙ СПУСК (RECURSIVE DESCENT)

Алгоритм рекурсии имеет условие с двумя ветками: в одной вызов себя, в другой – возврат из рекурсии.

// Вычисление факториала рекурсией  int factorial(int n) // <- Здесь неявно использован стек CPU   {      if(n > 1) return n * factorial(n - 1); // <- Здесь использован стек CPU       else return 1; // останавливает выполнение, когда n доходит до 1 или 0,                     // что предотвращает бесконечный цикл.  }  

Математика рекурсивной версии интерпретатора interpret_bf_recursive() выглядит как дерево вложенных конечных автоматов, где каждая пара скобок порождает дочерний автомат.
Инженерно: каждая пара [ ] порождает новый фрейм на стеке по стандарту C функций. То есть грамматика языка получает отображение на системный стек вызовов.
Математическая модель: Рекурсивный спуск по дереву (AST). Каждое вхождение в функцию – это переход на уровень ниже в иерархии вложенности автоматов. Наиболее элегантный код с точки зрения теории компиляторов.

9. ИТЕРАЦИЯ С ЯВНЫМ СТЕКОМ (EXPLICIT STACK)

В interpret_bf_stack() на массиве построен LIFO-стек хранящий индексы открывающих скобок.
Математически, это PDA Автомат с магазинной памятью. Инженерно: классическая стековая машина. Промышленный стандарт. Сочетает высокую скорость выполнения с контролем над потреблением памяти (размер стека фиксирован).

Задание: пошагово пройти в отладчике код, начиная с main(), сравнить алгоритмы рекурсии, итерации, понять работу стека.

// bf_2.cpp#include <stdlib.h>#include <conio.h>#include <string.h>#include <locale.h>#define LOG printf//------------------------------------------// РЕКУРСИВНЫЙ АЛГОРИТМ ИНТЕРПРЕТАТОРА BRAINFUCK НА С СТЕКЕ//------------------------------------------void interpret_bf_recursive(char* pc, unsigned char** head) // <- Здесь стек CPU использован неявно{    // char* pc - указатель в "ленте кода"    // char** head - указатель в "ленте памяти", использован **, чтобы сделать "общую головку", которую двигают все автоматы    while (*pc && *pc != ']')    {        switch (*pc++)        {            case '>': ++*head; break; // Инкрмент указателя на активную ячейку памяти            case '<': --*head; break; // Декрмент указателя на активную ячейку памяти            case '+': ++**head;  break; // Инкремент значения в активной ячеке памяти            case '-': --**head;  break; // Декремент значения в активной ячеке памяти            case '.': putchar(**head); break;            case ',': **head = (unsigned char)getchar(); break;            case '[':            {                if (**head)                {                    while (**head) interpret_bf_recursive(pc, head);                }                // Пропуск тела цикла для родительского автомата                for (int l = 1; l; pc++) { l += (*pc == '[') - (*pc == ']'); }                break;            }        }    }}//------------------------------------------//------------------------------------------// ИТЕРАТИВНЫЙ АЛГОРИТМ ИНТЕРПРЕТАТОРА BRAINFUCK//------------------------------------------void interpret_bf_stack(char* in, unsigned char* head_){    unsigned char* head = head_;    int stack[8192], sp = -1;    for (int i = 0; in[i]; i++)    {        switch (in[i])        {            case '>': ++head; break;            case '<': --head; break;            case '+': ++*head; break;            case '-': --*head; break;            case '.': putchar(*head); break;            case ',': *head = getchar(); break;            case '[':                if (*head) stack[++sp] = i;                else for (int l = 1; l; ) { char c = in[++i]; l += (c == '[') - (c == ']'); }                break;            case ']':                if (*head) i = stack[sp];                else sp--;                break;        }    }}//------------------------------------------unsigned char tape[30000]; // ПАМЯТЬ RAMint main(int argc, char *argv[]){    setlocale(LC_ALL, "en_US.UTF-8");    LOG("ИНТЕРПРЕТАТОР ЯЗЫКА BRAINFUCK. КОД ПОМЕСТИТЬ В КАВЫЧКИ, ПЕРВЫМ ПАРАМЕТРОМ ПРИ ЗАПУСКЕ ПРОГРАММЫ. ПРИМЕР: brainfuck.exe \"++.\"\n");    char* code = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.";    if (argc > 1) code = argv[1];    //------------------------------------------    // 1. Алгоритм с рекурсией (С стек)    //------------------------------------------    LOG("\nСТАРТ: interpret_bf_recursive\n");    memset(tape, 0, sizeof(tape));    unsigned char* head = tape; // Отдать ячеку с начальным положением головки    interpret_bf_recursive(code, &head);    //------------------------------------------    //------------------------------------------    // 2. Алгоритм без рекурсии    //------------------------------------------    LOG("\nСТАРТ: interpret_bf_stack\n");    memset(tape, 0, sizeof(tape));    interpret_bf_stack(code, tape);    //------------------------------------------    getch();    return 0;}

10. КОДИРОВАНИЕ НА BF

Негласная философия сообщества Brainfuck: всякий код на BF – это короткая демонстрация концепции (идеи). На BF не пишут программы, это – бессмыслица.
В Readme-файле к языку 1993 г. Мюллер оставил короткую фразу, ставшую девизом BF-программистов: «Who can program anything useful with it? :)» Улыбка в конце – суть этой философии.
Любой символ в коде, не входящий в набор из 8 команд ><+-.,[], считается комментарием. Хорошим стилем считается использовать это для вставки текста объяснения в код, без специальных знаков комментария. Поскольку код BF нечитаем (obfuscated by design), полагается снабжать его визуальными схемами с объяснением происходящего в ячейках памяти.
Кодируя на BF, учитывают три момента:

1. При старте программы во всех ячейках – нули, указатель текущей ячейки выставлен в ноль.

2. Нужно помнить индексы ячеек с данными и постоянно «ездить» к ним и от них алгоритмически, что превращает программирование в «прокладывание путей» и порождает переходы вроде <<<<<. При этом после каждой команды расстояние до ячейки меняется.

3. Встретив [ BF проверяет на равенство нулю текущую ячейку, и входит внутрь блока либо нет после такой проверки. Работа с ] – по аналогии. Примеры: – эхо-печать (Echo) Код бесконечно запрашивает у пользователя символ и тут же выводит его на экран. ,[.,] – обнуление ячейки [-] – рисование на BF

 [ This program prints Sierpinski triangle on 80-column display. ]                                  >                                     + +                                    +   +                                   [ < + +                                  +       +                                 + +     + +                                >   -   ]   >                               + + + + + + + +                              [               >                             + +             + +                            <   -           ]   >                           > + + >         > > + >                          >       >       +       <                         < <     < <     < <     < <                        <   [   -   [   -   >   +   <                       ] > [ - < + > > > . < < ] > > >                      [                               [                     - >                             + +                    +   +                           +   +                   + + [ >                         + + + +                  <       -                       ]       >                 . <     < [                     - >     + <                ]   +   >   [                   -   >   +   +               + + + + + + + +                 < < + > ] > . [              -               ]               >               ]             ] +             < <             < [             - [            -   >           +   <           ]   +           >   [           - < + >         > > - [         - > + <         ] + + >          [       -       <       -       >       ]       <       <         < ]     < <     < <     ] +     + +     + +     + +     + +        +   .   +   +   +   .   [   -   ]   <   ]   +   +   +   +   +       * * * * * M a d e * B y : * N Y Y R I K K I * 2 0 0 2 * * * * *      

Больше документации и примеров смотрите на [26], [27], [28].

ЛИТЕРАТУРА

████████████████████████████████████████
█░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█
█░░░░░░░██░█░░░░░░░░░░░░░░▐█▌░░░░░░░░░░█
█░░░░░░░██▀█▐▀█░█░█▐▀█░░░██▀██░░░░░░░░░█
█░░░░░░░██░█▐▀█░▀▄▀▐█▄░▄██▀▀▀██▄░░░░░░░█
█░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█
█░░░░░░░░░░░░░░░░░██▀▀▀░░░░░░░░█░░░░░░░█
█░░░░░░░░░░░░░░░░░██─▄▄▐▀█▐▀█▐▀█░░░░░░░█
█░░░░░░░░░░░░░░░░░██▄██▐▄█▐▄█▐▄█░░░░░░░█
█░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█
█░░░░░░░░▀██▀▄░░░░░░░░░░░░░░░░░░░░░░░░░█
█░░░░░░░░░██░▐█▐▀█▐▄█░░░░░░░░░░░░░░░░░░█
█░░░░░░░░▄██▄▀░▐▀█░▄█░░░░░░░░░░░░░░░░░░█
█░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█
████████████████████████████████████████