МАРСианский стиль программирования

[Leo B.]

Взялся я, наконец, перепереть /полечку на язык родных осин/ МАРС с дизассемблированного БЕМШа на С(++ для удобства): https://github.com/leobru/re-mars/blob/main/mars.cc - разумеется. с помощью indirect goto,  а то было бы муторно:

#define MERGE_(a,b)  a##b
#define LABEL_(a) MERGE_(ret_, a)
#define ret LABEL_(__LINE__)
#define call(addr,link) do { link.p = &&ret; goto addr; ret:; } while (0)

Таким образом, ПВ А12345(М6) превращается в call(a12345,m6);

А ПБ (М6) - в goto *m6.p;

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

Пришлось для удобства сравнения результатов с вызовом МАРСа из Паскаля  под эмулятором Диспака подменять это дело словами с магическим значением 1234567007654321, означающим "неважно". 

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

Для отлавливания блох была сделана трассировка записей в "память" с трассировкой оригинального МАРСа на эмуляторе. Таким образом нашлось несколько опечаток (в частности, в номере бита при проверке условия перехода после СЛЦ 😒) и пропущенных зависимостей от содержимого сумматора после записи выражений в упрощенном виде.

Многие тесты стали проходить с "полным" совпадением содержимого зон БД: создание каталога областей, области длиной несколько зон, записи в неё массива, помещающегося в одну зону; массива, требующего фрагментации; замены содержимого массива на данные большей длины, и пр.

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

Однако, создание большого количества мелких записей и последующего их удаления с помощью итератора после успешного удаления примерно половиных из них привело к потере управления и бессмысленной ошибке "ШАГЗ.ВЕЛИК" - при полном совпадении содержимого памяти с оригинальным запуском вплоть до момента потери управления.

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

Также были замечены следующие ошибки (которые вообще-то видны и в БЕМШе):
- процедура поиска "слова-конца" в памяти (упрощённо):
fnendw уи М16        сюда входят с "-length" на См
сч base
слц length
зп work
мод work       <--- переход в цикле должен быть сюда
сч (М16)
нтж endwrd
по found
цикл fnendw(М16)

Маловероятно, что ровно два битика на диске побились (00473/00475), скорее всего в метке в команде цикла была опечатка, а встроенным поиском слова-конца для вычисления длины массива или не пользовались, или, обнаружив ошибку, просто писали собственную процедуру.

Вторая ошибка заключается в следующем: имеется переменная, используемая на манер указателя на функцию, но хранится в ней разность указателей. Грубо говоря, возможные присваиваемые значения - 0, =А(ВБАЗУ-ИЗБАЗЫ), =А(СРАВН-ИЗБАЗЫ), =А(А00317-ИЗБАЗЫ). Для перехода делается МОД эта переменная, ПБ  ИЗБАЗЫ. Ради каких-то целей в одном месте делается сравнение этой переменной со значением =А(ГОТОВО-ИЗБАЗЫ), какое никогда не присваивается. 

В чём же дело? А вот 

ГОТОВО СЧ    USRLОС
       СЛЦ   curpos(M13)
       ЗП    USRLОС
А00317 ...

Возможно, когда-то инкремент usrloc += curpos делался в другом месте, и метка ГОТОВО (на которую есть явные переходы в нескольких местах) смотрела туда же, куда сейчас А00317. Потом сделали рефакторинг, метки разнеслись, и в одном месте, где упомянута разность, метку исправили, а в другом - упустили. Будущим исследователям предстоит выяснить, что же тут имелось в виду.  Трудность в том, что это происходит в коде, назначение которого неясно  (как нетрудно видеть, раз метка А00317 не переименована во что-нибудь осмысленное). 

Leo

[Leo B.]

За отчетный период многое в   https://github.com/leobru/re-mars/ изменилось: во-первых, код приобрел более человеческий процедурный вид почти всюду; во-вторых, была понята структура данных (B+tree16/32) и назначение всех микро-операций. 

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

| 48 - 40 |  39 - 21  | 20 - 11  | 10 - 1 | 

|---------|-----------|----------|--------|

| Номер   | Следующий | Длина    |Смещение|

| экстента| экстент в | (слов)   |экстента|

| в зоне  | элементе  |          | в зоне |

|(1-0777) |10рр - зона|          |        |

|         |9рр - номер|          |        |

(нулевые 39-21 рр. означают, что этот экстент в элементе данных последний)

Номер экстента в зоне - 9-разрядный, потому что экстентов нулевой длины не бывает, т. е. каждый экстент вместе с описателем занимает как минимум 2 слова.

Итого выходит, что база может быть длиной не более 2000(8) зон, что идеально подходит для 7.25 Мб диска.

Впрочем, на самом деле максимальная длина базы была даже чуть меньше, чем 1744 зоны, т. к. в 0-й зоне базы находилась и таблица свободных, и корневой блок Btree. Но из-за недосмотра автора создать базу длиннее 753 зон штатными средствами было невозможно.

В наборе микро-операций имеются:

• возможности работать с частями элементов данных (seek вперед на указанное число слов, прочитать указанное число слов с текущего места элемента в память пользователя, записать указанное число слов с текущего места элемента из памяти пользователя), а также вспомогательные средства для scatter/gather.
• возможности создавать иерархические Btrees и работать с ними (аналоги mkdir, chdir, cd .., cd /).
• возможности модифицировать описатели данных в Btrees - например, можно написать макрос обмена полями данных между двумя ключами.
• возможности работать со словами элементов данных как с описателями данных, т. е. фактически строить произвольные графы.

Удивительно, что возможность удлинить элемент данных, не прибегая к его полной перезаписи, предусмотрена не была.  Так что файловой системы с интерфейсом, близким к POSIX, из МАРСа сделать не получится. :(

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


Leo

[Leo B.]

On Tuesday, January 14, 2025 at 12:41:49 AM UTC-8 Leo B. wrote:

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

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

LDNEXT 1 0 CHAIN 
адрес перехода по выполнению условия
MATCH NOP ASSIGN 0 1 CHAIN
продолжение программы по невыполнению условия

Работает это так:
Виртуальный "регистр 0" (слово со смещением 0 в common-блоке BDVECT) используется в качестве счетчика адреса.

Каждое непоследнее в программе командное слово заканчивается микрокомандой CHAIN (c неявным операндом 0, если CHAIN - последняя микрокоманда в слове), которая выполняется как "загрузить слово по адресу в регистре 0 в регистр команды, инкрементировать регистр 0 и начать обработку только что загруженного регистра команды".

Команда LDNEXT dst src  выполняется как "загрузить слово по адресу в регистре  src в регистр dst, инкрементировать src если dst != src". 
ASSIGN dst src - присваивание одного регистра другому. 
MATCH сравнивает искомый ключ с найденным (были и другие микрокоманды, вырабатывающие условия).
Если за MATCH стоит NOP и еще команды, то при неуспешном сравнении 3 команды после NOP  пропускаются; при успешном - выполняются (а если не NOP, то неуспешное сравнение вызывает ошибку).  Таким образом при успешном MATCH в регистр 0 попадет адрес, который был загружен в регистр 1, и CHAIN вызовет переход туда; а при неуспешном регистр 0 сохранит своё значение (адрес "продолжения программы..."), и CHAIN продолжит линейное выполнение. Если кто-то придумает, как это могло записываться короче (я не придумал), тот будет молодец.

Также LDNEXT могла использоваться для чтения из других заготовленных массивов адресов или констант, адреса которых могли быть установлены в других "регистрах". 

Написание микропрограмм для реализации интерфейса ассоциативного контейнера (массив слов) -> (массив слов) оставляется в качестве упражнения для читателей.

Leo

[Serge Vakulenko]

Во как. Интересно, Филиппов сначала придумал такое микропрограммирование и потом уже приспособил его к реализации базы данных, или уже в процессе работы над Марс пришёл к этому решению. Потому как идея неочевидная.

--Сергей

[Leo B.]

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

Но пока мы не разыщем литературу, посвященную конкретно деталям реализации нижнего уровня МАРСа, достоверно не узнаем.  

[Leo B.]

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

IFEQ LDNEXT LDNEXT 0 0 CHAIN

адрес перехода при неудаче сравнения
продолжение работы при успехе

Здесь при успехе сравнения после IFEQ выполняется LDNEXT LDNEXT 0, т. е. очередное слово, содержащее адрес перехода, читается в некий рабочий регистр (т. е. пропускается), дальше выполняется 0 (NOP) и CHAIN - считывается и выполняется слово с "продолжением работы при успехе".

При неудаче сравнения первый LDNEXT пропускается, выполняется LDNEXT 0 0, т. е. адрес перехода считывается в счетчик адреса, и CHAIN  читает и выполняет слово по этому адресу.

Браво Филиппову! Жалко, он сам этого не помнил пару лет назад.

On Tuesday, January 21, 2025 at 5:05:15 PM UTC-8 Leo B. wrote:

[Leo B.]

А вот пример МАРСианского стиля написания статей:  https://mailcom.com/besm6/docs/Database_implementation.pdf

Это я, найдя на гуглобуксах по ключевым словам оцифрованную статью Филиппова с названием "Методика реализации сетевой СУБД на базе архивной системы МАРС-6" из журнала 

Upravli͡ai͡ushchie sistemy i mashiny : USiM : organ Kiberneticheskogo t͡sentra Akademii nauk Ukrainskoĭ SSR  (1980)

но, благодаря радетелям бессмысленных копирайтов, не имея возможности ничего прочесть, кроме пары цитат длиной в пару строчек, заказал годовую подшивку из хранилища библиотеке Стэнфордского ун-та и вчера ездил на неё смотреть. От статьи длиной 3 страницы многого не ожидалось, но полное отсутствие конкретики несколько разочаровало. Хоть выяснил, что это была Микромодульная АРхивная Система. В библиографии, на которую была слабая надежда, упоминается всё тот же нигде не существующий 5-й выпуск издания ВЦ АН СССР "Обработка символьной информации". 

Leo

PS. Если не ограничивать поиск гуглобуксами, "Филиппов Марс" приносит некоторое количество карнавальной ночи. 

[Василий Долматов]

PS. Если не ограничивать поиск гуглобуксами, "Филиппов Марс" приносит некоторое количество карнавальной ночи. 

«Лучше всего, конечно, пять звёздочек» (с) :)