Палеокомпьютинг, часть 3. Две Ады: создаём никогда не существовавшие языки по спекам с тендера Пентагона

Второго мая 1979 года небольшая рабочая группа Министерства обороны США проголосовала за язык, который в тот же вечер получил имя Ада. Сам тендер длился четыре года, заявок на него пришло полтора десятка, но до финала добрались лишь две, и до самого объявления победителя они проходили под кодовыми названиями Green и Red. Победил зелёный, спецификацию которого предложила франко-американская команда Жана Ишбиа, именно GREEN и стал известен под именем Ада. Красный, язык бостонской компании Intermetrics, проиграл, и о нём почти забыли. А ведь у красного уже был работающий транслятор, и, по воспоминаниям авторов, к сроку он был готов. Только по условиям контракта при выборе его не учитывали, а кроме самих авторов его никто никогда и не видел.

Пройти мимо такого тендера в серии о палеокомпьютинге я, конечно, не мог. Мне захотелось раскопать спецификации, поданные на конкурс, наконец создать языки программирования, которых никогда не существовало, написать на каждом компилятор, который компилирует сам себя, и посмотреть, что эти языки умеют. На RED я даже написал небольшую ОС и аналог управляющего слоя Kubernetes. ОС я строил по образцу Tandem NonStop — компьютеров, которые с 1976 года ставили в банки и на биржи, потому что они никогда не останавливались. Один из вариантов моего управляющего слоя устроен так же, как их процессные пары: это основной и резервный процессы без etcd и кворума, и такая пара переживает смерть API-сервера посреди обновления приложения. А самое поучительное нашлось не в коде: победившая Ада потом десятилетиями, медленно и дорого, пыталась реализовать то, что у проигравшего RED было с самого начала.

Это третья часть моей серии о палеокомпьютинге. В первой я запускал процессор Никлауса Вирта в браузере, в QEMU и в Kubernetes, во второй собирал Kubernetes на машинах Оберона, которые обмениваются сигналами по радио. Читать их не обязательно, эта история совершенно самостоятельна.

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

Статья, конечно же, получилась длинной. Сначала коротко разберём, как появился этот тендер и почему победили зелёные, а потом посмотрим, что вообще осталось от проигравших языков. После этого поговорим про оба языка и их компиляторы и о том, как программа 1979 года впервые заработала. Дальше будут операционные системы, Kubernetes, сравнение RED с классической Адой и немного шапочек из фольги и Задорнова с Фоменко: какой могла бы стать наша индустрия, если бы в мае 1979 года эксперты выбрали другого победителя. А в конце будут лабораторные. Отлично задокументированы и два других конкурента, синий и жёлтый, но они выбыли ещё в 1978 году, так что о них будет отдельный материал.

Все исходники, заметки и инструкции лежат в репозитории github.com/tym83/paleocomputing, в каталоге impl/ada-colors, и доступны под лицензией Apache 2.0.

Если заметите ошибки или исторические неточности, пожалуйста, пишите мне в сообщениях или в комментариях, я поправлю. Заранее благодарен.

Как Пентагон выбирал себе язык

В середине семидесятых у Министерства обороны США была проблема, которую сегодня назвали бы зоопарком технологий. Встроенный софт для самолётов, кораблей и систем управления писали на сотнях языков и диалектов, каждый подрядчик приносил свой язык, и сопровождение всего этого хозяйства обходилось в миллиарды долларов. В январе 1975 года появилась рабочая группа по языкам высокого уровня, HOLWG, и её председатель, подполковник ВВС Уильям Уитакер, предложил странную для военного ведомства идею: сначала публично договориться о требованиях к языку, а уже потом искать сам язык.

Требования писали несколько лет, и по именам редакций видно, как они становились всё более чёткими и даже твердели: соломенный человек, Strawman, в апреле 1975 года, потом деревянный Woodenman, жестяной Tinman, железный Ironman и, наконец, стальной Steelman в июне 1978-го. Tinman разослали тысяче человек из промышленности и университетов, а ещё раньше, к версии Strawman, отзывы писали Дейкстра, Хоар и Вирт. Двадцать три существующих языка сверили с требованиями, и ни один не подошёл. Решили, что новый язык надо строить на одном из трёх, которые были ближе других: Паскале, PL/I или Алголе 68. Отдельная забавная деталь из воспоминаний Уитакера: язык C тоже позвали на проверку, но Bell Labs, где его создали, сами попросили не включать C в этот список, и группа эту просьбу уважила.

Весной 1977 года объявили конкурс, получили четырнадцать заявок, а в августе профинансировали четыре команды. Чтобы рецензенты судили по существу, а не по брендам, проекты обезличили цветами: зелёный достался CII-Honeywell-Bull, красный Intermetrics, синий SofTech и жёлтый SRI International. По словам Уитакера, никакого скрытого смысла у цветов не было.

В феврале 1978 года четыре предварительных проекта ушли на оценку, их разбирали около восьмидесяти команд из военных и гражданских организаций. Дейкстра потратил на них целый месяц и написал по рецензии на каждый. Жёлтый он назвал безнадёжной мешаниной, синему поставил в упрёк главу о типах на 160 страниц, ревью на зелёный закончил фразой про «техническую некомпетентность, вероятно, усиленную нечестностью», а в обзоре красного признался, что сбит с толку: проект одновременно и передовой, и отсталый, и как это сочетается, он не понимает. Уитакеру он посоветовал не выбирать ни один из четырёх. Совету не последовали: в апреле 1978 года во второй тур вышли зелёный и красный языки.

Второй тур длился целый год. И тут случилось то, что для этой истории важнее всего. Красная команда выбросила свой первый проект целиком. Главный создатель языка Джон Нестор переписал его с нуля, так что красных языков на самом деле два. Первый, REDL, строился на мониторах Хоара — модулях с общими данными, в которые одновременно может войти только один процесс, — и событиях. Второй, RED, который и дошёл до финала, держался на почтовых ящиках и критических секциях, о которых подробно в экскурсии по RED. Руководил красным проектом Бен Брозгол, а язык проектировал Нестор. Консультантами у красных были Барбара Лисков, Уильям Вульф, Пол Абрахамс и Роберт Дьюар, будущий руководитель проекта GNAT, свободного компилятора Ады. Пятнадцатого марта 1979 года обе команды сдали полную спецификацию, обоснование проекта, решения десяти одинаковых для всех контрольных заданий — небольших упражнений от Минобороны, от кольцевого буфера до планировщика, — и тестовый транслятор.

Транслятор красных работал. Его делала группа Марка Дэвиса, и Мэри Ван Деузен, соавтор руководства по RED, вспоминает об этом как о маленьком подвиге: компилятор языка, который всё время менялся, был готов в срок. Но в контракте второго тура было записано, что транслятор при выборе не учитывается. Уитакер объясняет это иначе: оба транслятора оказались слишком неполными и, возможно, слишком медленными, чтобы влиять на оценку.

Второго мая 1979 года группа выбрала GREEN. Уитакер в тот же день разослал три тысячи зелёных открыток с надписью «Green is Ada!». Решение приняли единогласно, как и все решения этой группы: Уитакер признаётся, что ставил вопрос на голосование, только когда все уже были согласны. Ван Деузен как представитель проигравшей стороны рассказывает историю про молодого представителя ВВС, которому было приказано голосовать за зелёный, ничего не обсуждать и не менять мнения. Подтверждений я не нашёл, так что пусть это останется лишь историческим анекдотом (но в то же время это очень похоже на то, как принимаются решения в подобных случаях).

Почему победил зелёный, в доступных документах написано скорее между строк. Отчёты рецензентов с финала в сети не сохранились. А вот разборы первого тура, как оказалось, сохранились, и о них будет следующая статья. Такер Тафт, который пришёл в Intermetrics в 1980 году и потом руководил созданием Ады 95, говорит, что зелёный раньше других достиг стабильности и полноты, а Ишбиа замечательно умел показывать его рецензентам. Ван Деузен вспоминает, что зелёная команда с первого дня очень тонко чувствовала политику и что её первым проектным решением была длина описания. А в популярной книге о языках программирования, которую Time-Life выпустило в 1986 году, есть, по-моему, самая точная фраза, вложенная в уста одного из участников конкурса: в финале оба языка изменились, красный стал смелее, а зелёный консервативнее.

Дальше была долгая шлифовка. Предварительное руководство по Аде вышло в июне 1979 года в журнале SIGPLAN Notices, его разбирали, переделывали, и только в феврале 1983 года появился стандарт ANSI/MIL-STD-1815A, который мы теперь называем Ада 83. Номер стандарта взят из года рождения Ады Лавлейс. Красный язык Intermetrics похоронила быстро и, по словам Ван Деузен, полностью. Но у этой истории есть продолжение, к которому я ещё вернусь.

Что осталось от проигравших

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

Руководство по RED от 8 марта 1979 года к тридцатилетию конкурса целиком перенесла в HTML Мэри Ван Деузен, одна из его авторов. Там же лежит полное обоснование проекта, Rationale, где разобраны отвергнутые альтернативы, решены десять контрольных заданий и приведён пример библиотечной капсулы, как в RED называется модуль. Ван Деузен пишет, что после конкурса эти документы были недоступны публике. Для 1979–1990 годов это корректно, но в марте 1990 года руководство попало в архив технической информации Минобороны DTIC с пометкой «допущено к открытой публикации», и оно до сих пор лежит там под номером AD-A219453.

Синтаксис RED в руководстве показан не текстом, а диаграммами, и все они в формате картинок. Восемьдесят три диаграммы языка и двенадцать лексических диаграмм пришлось перерисовать (не мне, клоду, конечно), чтобы получить привычную грамматику, а попутно расшифровать 105 примеров кода, которые тоже были в картинках. В процессе обнаружились расхождения внутри самого руководства. Например, на диаграмме после метки перехода стоит точка с запятой, а в таблице спецсимволов и в примерах стоит двоеточие.

С зелёным языком я ожидал обратного: раз Ада (тот самый GREEN) победила, её документация должна быть доступна. Однако везде есть Ада 83, а вот зелёный язык на весну 1979 года, до всех переделок, найти оказалось сложнее. Помогло зеркало DTIC на Internet Archive. Там нашлись «Неформальное введение в язык Green», его формальное определение, решения тех же контрольных заданий и, что особенно ценно, два документа: «Предварительное руководство по Аде» за май 1979 года, к которому приложено письмо заместителя министра обороны от 14 мая с объявлением о выборе языка, а также полное обоснование зелёного проекта от 15 марта 1979 года, то есть в день сдачи финальных материалов. Всё это сканы с плохим распознаванием текста, местами кошмарным, но читаемые.

Контрольные задания заслуживают отдельного слова. Это десять заданий, которые Минобороны раздало всем командам: опрос клавиатур через общий кольцевой буфер, система прерываний с четырьмя приоритетами, файловый пакет, динамическая графика с джойстиками, защита базы данных от одновременного доступа, управление процессом, адаптивная маршрутизация, планировщик реального времени, распределённая рассылка и распаковка битовых заголовков сообщений. Обе команды решали одни и те же задания, и у нас появилась уникальная возможность вновь сравнить их подходы. Тут снова пришлось распознавать все двадцать решений, чтобы получить исходный код. Красная команда уложилась в 815 строк кода без комментариев, зелёная в 1660, то есть вдвое больше, и почему так вышло, я покажу, когда дойду до самих решений.

Синий и жёлтый проекты, судя по переписке в рассылке systemsafety в 2023 году, лежат в огромном томе отчётов первого тура на 4575 страниц в том же DTIC (так и оказалось, о них расскажем в следующей статье). А вот чего найти не удалось, так это транслятора красных. От него остались библиографическая ссылка в статье Ван Деузен 1981 года («M. Davis and D. Levine, RED Translator, Intermetrics, Inc., March 1979»), пара абзацев в обосновании о том, какой ввод-вывод он поддерживал и как через него прогнали синтаксис контрольных заданий, а также воспоминания самой Ван Деузен. Доступных исходников нет. Так что компилятор, который был создан в 1979 году, мы не увидим, но можем написать новый, и это, наверное, первый публично доступный компилятор RED за всю его историю.

Экскурсия по RED

На первый взгляд RED выглядит как Паскаль, который долго посещал качалку. Вот кусок пакета матричной арифметики из приложения к обоснованию, примеры для которого писали Пол Абрахамс, Брюс Кноб, Дэвид Левин и другие. Константы я подставил, а комментарии убрал. Смотрите прежде всего на типы и на заголовок функции:

CAPSULE matrix_vector_package EXPORTS ALL;
CONST maxdim := 100;
ABBREV mvfloat : FLOAT(6, -1.0E99 .. 1.0E99);
ABBREV dim : INT(2 .. maxdim);
TYPE matrix(m : dim, n : dim) : ARRAY INT(1 .. m), INT(1 .. n) OF mvfloat;
TYPE vector(n : dim) : ARRAY INT(1 .. n) OF mvfloat;

FUNC *(READONLY b : matrix, READONLY c : vector) => vector(b.m);
    ASSERT b.n = c.n;
    VAR a : vector(b.m);
    FOR i : INT(1 .. b.m) REPEAT
        a(i) := 0.0;
        FOR j : INT(1 .. b.n) REPEAT
            a(i) := a(i) + b(i,j) * c(j);
        END REPEAT;
    END REPEAT;
    RETURN a;
END FUNC *;

Но если присмотреться, в этих полутора десятках строк уже много того, что придёт в мейнстрим гораздо позже. ABBREV здесь просто даёт подтипу короткое имя, а FLOAT(6, …) задаёт вещественный тип с точностью 6 и заданным диапазоном. Размерности живут прямо в типе: vector(n) — тип с параметром, а b.m и c.n читаются как обычные атрибуты значения. Поэтому и тип результата вычисляется из аргументов, и функция заранее обещает вернуть vector(b.m). Оператор перегружен по типам операндов, так что одним знаком умножают число на вектор, матрицу на число, матрицу на вектор и матрицу на матрицу. А дальше в пакете векторное произведение объявлено как для vector(3), то есть ограничение на размерность записано прямо в типе параметра, и вызов с вектором другой длины поднимет исключение подтипа. В Rust такое ограничение записали бы через const generics, Vector<3>. Кроме того, тут есть ASSERT прямо в теле функции как часть языка.

Дальше я пройдусь по тому, что мне показалось в RED самым интересным. Почти всё это не пересказ руководства, а то, обо что я споткнулся сам, когда писал (не своими руками, да) на RED компилятор, операционную систему и Kubernetes.

Капсулы и абстрактные типы без слова private

Модуль в RED называется капсулой. Капсула экспортирует ровно то, что перечислено после EXPORTS, а тот, кто ею пользуется, явно открывает то, что ему нужно, через EXPOSE:

CAPSULE stackcap EXPORTS stack, init, push, pop;
   TYPE stack : RECORD[top : INT(0 .. 100), elem : ARRAY INT(1 .. 100) OF INT];
   ...
END CAPSULE stackcap;

EXPOSE stack, push, pop FROM stackcap;

В Аде абстрактный тип создаётся секцией private в спецификации пакета. В RED нет никакой секции, зато есть правило, которое я сначала пропустил, а потом сам же на нём споткнулся: когда капсула экспортирует тип, она не экспортирует ни выбор его компонент, ни присваивание. Снаружи переменную типа stack можно объявить и передать в push, но написать s.top := 0 нельзя. Хотите открыть внутренности, проще всего экспортировать всё через EXPORTS ALL. То есть абстрактность типа определяется не тем, как он объявлен, а тем, что из капсулы выпущено наружу. Если подумать, это очень честная модель: тип сам по себе ничего не прячет, прячет граница модуля.

Закрытые области и IMPORTS

Это правило оказалось самым ощутимым в повседневной работе. Процедура в RED — закрытая область: константы, типы и другие процедуры снаружи она видит, а переменные нет, пока явно их не импортирует:

VAR hits : INT := 0;
VAR limit : INT := 3;
PROC hit IMPORTS hits, READONLY limit;
   IF hits < limit THEN
      hits := hits + 1;
   END IF;
END PROC hit;

Переменную можно импортировать и только для чтения, как limit в примере. По сути, это тот же список захвата, что у лямбд в C++, только обязательный и для всех процедур. Для языка, задуманного под сопровождение огромных программ десятилетиями, это разумно: по заголовку процедуры сразу видно, какое состояние она может испортить.

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

Параметры передаются четырьмя способами: CONST копирует, READONLY передаёт по ссылке без права изменения, VAR по ссылке с изменением, а OUT — это локальная переменная, значение которой переходит в фактический параметр, только если процедура завершилась нормально. Если процедура закончилась исключением, переменная вызывающего остаётся такой, какой была. Зачем различать чтение копией и чтение по ссылке, красная команда объясняет отдельно. Оставить способ на усмотрение транслятора нельзя, потому что тогда поведение программы зависит от реализации, а всегда копировать слишком дорого для больших объектов.

Выход из цикла по имени

Мелочь, которая мне очень понравилась. EXIT в RED обязан назвать оператор, из которого выходит:

outer WHILE p /= NIL REPEAT
   ...
   IF found THEN
      EXIT outer;
   END IF;
END REPEAT outer;

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

Почтовые ящики, WAIT и REGION

Главное отличие RED от будущей Ады — параллельность, и тут нужно небольшое отступление для тех, кто на Аде не писал (то есть почти для всех). Задачей (task) в обоих языках называется то, что сегодня назвали бы потоком: кусок программы, который выполняется одновременно с остальными. Вопрос в том, как задачи договариваются между собой. В Аде, а до неё в зелёном языке, единственный способ сделать это — рандеву. У задачи-сервера есть входы, entry, похожие на процедуры. Клиент вызывает вход и ждёт, сервер в своём коде доходит до оператора accept для этого входа и тоже ждёт, и когда оба на месте, выполняется тело accept, после чего каждый идёт дальше своей дорогой. Это встреча, отсюда и название. RED устроен иначе: задачи обмениваются сообщениями через почтовые ящики, то есть очереди сообщений между задачами внутри программы, а общие данные защищают критическими секциями:

VAR m : MAILBOX[msg](3);         % ящик на три сообщения
VAR d : DATA_LOCK;

TASK consumer IMPORTS m;
   VAR data : msg;
   WHILE TRUE REPEAT
      RECEIVE(m, data);
      ...
   END REPEAT;
END TASK consumer;

VAR c : ACT;
CREATE consumer NAMED c;
SEND(m, x);

REGION d DO
   shared := shared + 1;          % замок отпустят, как бы ни закончилось тело
END REGION;

Ящик типизирован и ограничен. Ящик размера ноль — это рандеву: отправитель не может обогнать получателя. Оператор WAIT ждёт первого из нескольких событий, приёма из любого ящика, отправки или тайм-аута:

WAIT
   WHEN RECEIVE(ports(me), m) => handle(m);
   WHEN DELAY(35) => take_over;
END WAIT;

И здесь есть деталь, по которой видно, как тщательно продумывали язык. SEND в ящик нулевого размера внутри WAIT запрещён: такая попытка поднимает исключение X_EMPTY_MAILBOX. Почему? Потому что иначе задачи, которые ждут друг у друга отправки в нулевые ящики, могут встать в круговое ожидание, а предотвратить его можно только глобальным планированием.

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

Задачи запускаются явно, CREATE задача NAMED переменная, и у каждой активации, то есть запущенного экземпляра задачи, есть имя, переменная типа ACT. Через неё можно спросить, жива ли задача, поменять ей приоритет, дождаться её завершения или убить через EXTERMINATE. Встроенный планировщик приоритетный: первой работает задача с более высоким приоритетом, а при равных та, что дольше ждёт.

Свой планировщик

На нижнем уровне языка (это описано в четырнадцатой главе руководства) системный программист может описать собственный планировщик и собственные механизмы синхронизации, потому что язык отдаёт ему операции самого планировщика: приостановить активацию, дождаться сигнала, сделать участок кода критическим, чтобы его не вытеснили и не убили на полпути. Встроенные почтовые ящики, замки и WAIT описаны в той же главе как частные случаи, собранные из этих операций, и руководство показывает это на примерах: планировщик с круговой очередью, мониторы Хоара поверх замков данных и даже сам MAILBOX, определённый средствами языка. В моём компиляторе все эти примеры работают. Сам факт, что язык 1979 года предлагал пользователю писать планировщики, а не только пользоваться инструментарием, для меня очень показателен.

Обобщения, которые создаются сами

Обобщённая процедура в RED выглядит так:

GENERIC t : TYPE NEEDS :=(t, t)
   PROC swap(VAR a, b : t);
      CONST c := a;
      a := b;
      b := c;
   END PROC swap;

swap(i, j);       % i и j целые
swap(s, r);       % s и r строки

Обратите внимание, чего здесь нет. В Аде нужно сначала явно создать экземпляр, procedure SWAP_INT is new SWAP(INTEGER), и только потом вызывать. В RED оператора создания экземпляра нет вообще: каждый вызов сам сообщает транслятору, какие нужны типы, а транслятор создаёт экземпляр или берёт уже созданный. Так потом заработают шаблоны C++, только в RED это было реализовано на одиннадцать лет раньше. А список NEEDS перечисляет, какие операции должны быть у типа-параметра (здесь присваивание). В C++ то же самое появилось лишь в 2020 году под именем концептов. Мой компилятор проверяет этот список в каждой точке вызова: если нужной операции там нет или у неё не тот заголовок, вызов не переводится. Параметрами обобщения могут быть типы, значения, процедуры и даже задачи. В решении контрольного задания о планировщике красная команда передаёт задачу параметром в обобщённую задачу-обёртку, которая запускает её по расписанию.

Строки, которые помнят свою длину

Строковый тип в RED — это STRING[ASCII](n), и длина фиксирована для каждого объекта. Присвоить строку другой длины нельзя, это ошибка подтипа. Для текста переменной длины нужен указательный тип с параметром, и в руководстве есть как раз такой пример, таблица символов:

TYPE sym : PTR (len : INT) STRING[ASCII](len);
ALLOC s.syms(s.top) PTR (val.LEN) := val;

ALLOC создаёт динамическую строку ровно той длины, что у val, и кладёт указатель на неё в таблицу. Компилятор RED, написанный на RED, хранит все имена и куски сгенерированного кода именно так. А символы ASCII в RED — это значения перечисления с именами, и строчная буква a записывается как 'L_A, апостроф как 'APOS, кавычка как 'QUOTE. Кавычку внутри строкового литерала написать нельзя вообще, только склеить строку с символом. В исходнике компилятора, который генерирует C, это выглядит забавно: "rt_str(" & q & "TRUE" & q & ", 4)", где q — функция, возвращающая кавычку.

FREE, который отказывается освобождать

И последнее, что меня впечатлило в руководстве. Динамическая переменная в RED живёт, пока на неё есть ссылки, то есть по умолчанию язык рассчитан на сборку мусора. Но для тех, кто не может себе её позволить, есть процедура FREE. Если на освобождаемую переменную есть другие указатели, FREE не освобождает её, а поднимает исключение X_FREE. Висячий указатель становится невозможен в принципе, а саму проверку, если она слишком дорога, можно отключить прагмой, то есть указанием транслятору прямо в тексте программы: PRAG(SUPPRESS(X_FREE)). И всё это в 1979 году. В моём компиляторе FREE перед освобождением обходит всю достижимую память: глобальные переменные, кадры работающих подпрограмм каждой задачи, динамические переменные и буферы почтовых ящиков. Программа без FREE за это ничего не платит.

GREEN весной 1979 года

Зелёный язык легко принять за раннюю Аду, и это ошибка. Предварительное руководство мая 1979 года описывает язык, синтаксисом похожий на Аду 83, но местами совсем другой. Компилятор зелёного языка на нём самом я писал параллельно с красным, и по дороге этот язык показал характер не хуже соседа.

Как выглядит программа

Вот одна из программ «Неформального введения», подсчёт сдачи:

restricted (TEXT_IO)
procedure COUNT_YOUR_CHANGE is
   use TEXT_IO;
   ...
begin
   ...
      PUT("CHANGE IS $");
      PUT(NUM_DOLLARS);
      PUT(".");
      PUT(NUM_CENTS);
   end if;
end;

Здесь сразу видно несколько отличий от Ады 83. Вместо with TEXT_IO перед процедурой стоит restricted(TEXT_IO): в зелёном языке любая единица компиляции по умолчанию ограничена пустым списком видимости, и библиотеки надо назвать явно. Причём restricted можно поставить перед любым вложенным модулем, а не только перед единицей компиляции, сузив ему видимость внутри программы. Процедуры PUT_LINE нет: перевод строки — это строковая константа NEWLINE, и его выводят как PUT(NEWLINE). В этой программе его, кстати, нет вовсе. А по правилам ввода-вывода 1979 года перед каждым числом, выводимым не с начала строки, ставится пробел. Так что эта программа из введения буквально печатает CHANGE IS $ 2. 53, и, судя по всему, тогда этого никто не заметил.

Мелочей, которые выдают другой язык, много. Символьный литерал в зелёном языке — это просто строка длины один, "A", а апостроф нужен только атрибутам. Позиции в перечислениях считаются с единицы, поэтому CHARACTER'ORD("A") равно 66, а не привычным 65. Операция mod берёт знак левого операнда, то есть ведёт себя как rem в Аде 83. Оператора abs нет, вместо него есть функция ABS, и ветви case пишутся после of, а не после is. В именованной ассоциации режим параметра пишется прямо в месте вызова: F := x передаёт значение внутрь, F =: v забирает результат наружу, F :=: v делает и то и другое. А ещё в языке был оператор assert, который в Аду 83 не попадёт. Подробная таблица отличий от Ады 83 лежит в заметках проекта.

Правила, под которые пришлось строить компилятор

Главное, обо что я споткнулся, — правила чистоты функций в разделе 6.5 руководства. Функция в зелёном языке не имеет права присваивать что-либо нелокальное, менять объекты по указателям, выделять память и, раз уж ввод-вывод и внешние процедуры могут иметь побочные эффекты, вызывать их. Для генераторов вроде «выдай следующий уникальный номер» существуют процедуры, возвращающие значение: procedure NEXT return INTEGER. Им можно менять глобальные переменные, но вызывать их разрешено только в присваивании, инициализации или вызове процедуры, и только там, где эти глобальные переменные вне области видимости.

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

Любопытно, что красный язык решил тот же вопрос противоположным способом. В RED функция по умолчанию нормальная: её результат зависит только от аргументов, а менять она может разве что скрытые переменные своей капсулы. Если ей нужно больше, её помечают ABNORMAL, и тогда ей можно всё. Зелёный язык запрещает, красный требует пометить. Для военного кода зелёный подход, наверное, надёжнее. Для человека, пишущего компилятор, красный удобнее, и я подозреваю, что именно такие места смягчали в 1980–1983 годах.

Задачи без типов задач

Многозадачность зелёного языка строится на рандеву, как и в Аде, но выглядит иначе. Типов задач нет. Задачу объявляют, и она существует, но запускается только оператором initiate. Если задача уже работает, повторный initiate поднимает исключение INITIATE_ERROR, а завершившуюся задачу можно запустить заново, со свежими переменными. Чтобы получить много одинаковых задач, есть семейства: task KUBELET(INTEGER range 1 .. 3) (так в моём Kubernetes называются агенты узлов, до них мы ещё дойдём), и внутри тела задача узнаёт свой номер через KUBELET'INDEX. Бывают и семейства входов.

В select есть охраны, задержки и else, но нет альтернативы terminate, а если все альтернативы закрыты и else нет, поднимается SELECT_ERROR. Вызывающая сторона выбирать между ожиданиями не может вообще: ни вызова с тайм-аутом, ни условного вызова. Исключение, поднятое в теле accept, долетает до обеих сторон рандеву. А единственное исключение, которое можно поднять в чужой задаче, называется FAILURE: raise T.FAILURE. Убить же чужую задачу можно оператором abort. Предопределённых исключений пятнадцать, и каждое прямо называет свою беду: RANGE_ERROR, INDEX_ERROR, ACCESS_ERROR, DIVIDE_ERROR, NO_VALUE_ERROR для чтения неинициализированной переменной или функции, закончившейся без return, и так далее. В Аде 83 вместо них осталось пять более общих: из зелёных имён уцелело только TASKING_ERROR, а остальное слилось в CONSTRAINT_ERROR, NUMERIC_ERROR, PROGRAM_ERROR и STORAGE_ERROR.

Компилятор, который компилирует сам себя

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

Общий рантайм и предсказуемое время

Оба компилятора переводят программу в C и собирают её с общим рантаймом, тоже на C. Это примерно восемь с половиной тысяч строк, и в них живёт всё, что языкам нужно во время работы: строки, исключения, проверяемая арифметика, ввод-вывод, почтовые ящики и замки RED, рандеву зелёного языка и планировщик задач.

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

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

Раскрутка

Компилятор на языке X нельзя собрать, пока нет компилятора языка X. Классический выход — раскрутка. Сначала я сделал маленький транслятор-затравку на Python, около двух с четвертью тысяч строк вместе с разбором, который понимает только то подмножество RED, на котором будет написан настоящий компилятор. Потом на этом подмножестве написал настоящий компилятор, redc, и прогнал его через питоновскую затравку. Получившийся компилятор перевёл собственный исходник, новый компилятор ещё раз перевёл себя, и два файла на C совпали байт в байт. Это и есть неподвижная точка: компилятор воспроизводит сам себя, и затравка больше не нужна.

Дальше начинается самое интересное. С этого момента для сборки нужен только файл на C, который последний компилятор сделал из собственного исходника, и язык растёт внутри самого компилятора. Каждая новая возможность добавляется в redc так, чтобы сам redc её пока не использовал, затем компилятор собирается предыдущей версией, проверяется неподвижная точка, и только после этого новую возможность можно применять в его собственном исходнике. Сначала так появились капсулы, экспорт и вложенные процедуры со статическими ссылками, то есть указателями на кадр объемлющей процедуры, потом многозадачность, потом перегрузка с типами-параметрами, двумерными массивами и множествами, и наконец обобщения. Сейчас компилятор занимает около одиннадцати тысяч строк на RED и переводит себя за пару десятых секунды. В CI на каждом изменении он дважды пересобирает себя из этого C-файла и сравнивает результаты, а отдельная цель сборки повторяет самый первый шаг, от питоновской затравки, чтобы цепочку можно было проверить с нуля.

Что RED сделал со мной

Одиннадцать тысяч строк на языке 1979 года — хорошая проверка не только языка, но и терпения. Вот места, где строптивый RED со мной спорил, и почти всегда, если вдуматься, был прав.

Первым делом компилятор отказался переводить собственный лексер. Функция upper превращала строчную букву в заглавную через POS(c), а компилятор утверждал, что POS — не функция. Оказалось, у меня есть глобальная переменная pos, позиция в потоке лексем, а имена в RED не различают регистр, и встроенные имена вроде POS не зарезервированы. Моя переменная по всем правилам скрыла встроенную функцию. Потом то же самое случилось с полем записи len, которое совпало с атрибутом .LEN, а ещё позже с параметром задачи me, скрывшим встроенную функцию ME, которая возвращает текущую активацию. Каждый раз компилятор делал то, что велят правила областей видимости, и каждый раз я тратил минут пять на то, чтобы в это поверить.

Зарезервированных слов в RED больше полусотни, и среди них есть неожиданные: TO, CAPSULE, EXPOSE, IMPORTS, READONLY, SUBTYPE. Функцию парсера subtype пришлось переименовать, а переменную to в клиенте операционной системы назвать dest.

Пустого оператора в RED нет. Пустое тело пишется пустым местом, так что WHEN DELAY(20) => ; — синтаксическая ошибка. Позже ту же запись, DELAY_UNTIL (next) => ;, я нашёл в решении восьмого контрольного задания, хотя, по словам красной команды, синтаксис всех решений проверил их транслятор. Видимо, транслятор 1979 года был к этому снисходительнее диаграмм.

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

Но самое ценное правило — IMPORTS. Пока компилятор его не проверял, я, естественно, писал как попало. Когда проверка появилась, исходник компилятора пришлось один раз пройти целиком и в каждой подпрограмме объявить, что она импортирует. У небольших функций лексера и таблиц это настоящие списки, а парсеру и генератору, которые трогают почти всё глобальное состояние, я написал IMPORTS ALL, и на такие подпрограммы пришлось четыре пятых кода. И это тоже честно: по заголовку сразу видно, что процедура трогает всё. А в небольших программах, в операционной системе и в Kubernetes, где списки короткие и настоящие, та же проверка дважды поймала мои ошибки. Я впервые понял, зачем авторы требований к языку так настаивали на явных интерфейсах.

И то же самое для зелёного

Компилятор зелёного языка, написанный на нём самом, занимает около четырнадцати тысяч строк, и раскручивался он точно так же: питоновская затравка, первая версия, неподвижная точка, а дальше рост, где каждую версию собирает предыдущая. В нём есть пакеты с приватными типами и перегрузка, которая различает типы параметров, их режимы, имена и тип результата, а операторы можно объявлять как имена функций. Есть все пятнадцать исключений, задачи с initiate, рандеву и select, семейства задач и входов и обобщения с явным созданием экземпляров через is new. Программы из введения 1979 года работают, а в двух из них компилятор нашёл ошибки, которые пропустить не может: сравнение вещественного NET_RISE с целым литералом и восьмеричное число 8#8060, в котором есть цифра 8.

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

Программа 1979 года запускается впервые

Самый трогательный момент всего проекта случился, когда компилятор научился перегрузке и типам с параметрами. Я взял пакет матричной арифметики из обоснования RED, тот самый, кусок которого был в начале главы по этому языку, дописал к нему маленькую главную программу и попробовал перевести.

Не получилось. Компилятор остановился на строке ASSERT b.n : c.m — двоеточие вместо знака равенства. Таких утверждений в пакете оказалось четыре. Потом выяснилось, что капсула открывается под именем matrix_vector_package, а закрывается под именем vector_matrix_package. Далее — что функция транспонирования использует переменные m и n, которые в ней нигде не объявлены, и ещё две процедуры внутри функции обращения матрицы ссылаются на такую же необъявленную m. Ещё нашлись a(p.r), x(k.p) и x(i.p) с точкой вместо запятой. И тип integer, которого в RED нет. А поверх всего лёг шум самой HTML-перепечатки: лишние обратные апострофы, неразрывные пробелы, единица вместо буквы в 1NT, SUBT_1OOP и realmultip1y.

Каждая из этих ошибок — то, что любой транслятор RED отвергнет сразу. Значит, пример в обосновании никогда не компилировался, его просто набрали и отдали в печать (тогда даже клод был не нужен, чтобы совершать глупые ошибки, это смешно). Это неудивительно: транслятор у красных был готов к тому же сроку, что и документы, и гонять через него примеры для приложения, видимо, было некогда (видно было, что к тендеру подошли серьёзно). Все правки я записал в отдельный файл, по строке с объяснением на каждую, чтобы было видно, что исправлено только то, что не пропускает транслятор.

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

005.000 004.000 006.000
000.000 009.000 -006.000
dot = 031.000
det = 008.000
001.000 002.000 003.000

Логические ошибки, которые транслятор пропускает, я оставил как есть, потому что это уже часть истории. В обращении матрицы строки переставляются при условии IF i = j, хотя должно быть IF i /= j, так что выбор главного элемента на самом деле никогда не срабатывает. Определитель не учитывает знак при перестановке строк и перемножает диагональ внутри цикла исключения, а не после него. А вспомогательная функция возведения в степень крутит цикл до внешней переменной k вместо собственного параметра. На моей тестовой матрице все эти ошибки не проявляются, и в 1979 году, скорее всего, тоже не проявились бы.

С примерами самого руководства та же история. В четырнадцатой главе, где планировщик с круговой очередью, мониторы Хоара и сам MAILBOX определены средствами языка, переменная планировщика названа new, а поле записи в мониторе external, и оба слова зарезервированы. В определении почтового ящика стоит SYNCH_SIGNAL вместо SYNC_SIGNAL, а одно условие скопировано из соседней процедуры, и эту ошибку не поймал бы никакой транслятор.

Дальше по плану были контрольные задания. Первым заработало шестое, «управление процессом»: задача a читает перфокарты в двойной буфер, задача b их обрабатывает, задача c печатает результат, а процедура d общается с оператором и по его команде DONE аккуратно останавливает a и b, не потеряв данных. И здесь транслятор снова нашёл в оригинале то, что пропустить не может, причём целую россыпь всяких мелочей. У нового типа без параметров берётся поддиапазон mes('b0..'b1), хотя в RED у такого типа ровно один подтип. Массив буферов объявлен как тип, а используется как переменная, которой нет. Активации объявлены под именами aa, ba и ca, а создаются задачи под именами cc и bb. Задача b отправляет результаты в ящик mc, а импортирует почему-то mr, и даже имя цикла в конце написано с одной буквой t вместо двух. Устройство ввода и обработку, которые по условию «предполагаются присутствующими», я дописал заглушками, а оператор подаёт команды на перфокартах по восемьдесят колонок, как и положено в 1979 году.

Самое интересное началось после того, как всё перевелось. Оператор подаёт DONE, а задача a продолжает читать карты бесконечно. Она ждёт в WAIT сразу двух событий: возвращённого буфера и команды остановки. Буфер возвращается всегда, а мой рантайм из нескольких готовых альтернатив выбирал первую по тексту. Команда остановки просто никогда не получала шанса. Руководство RED на этот счёт говорит, что выбор среди готовых альтернатив не определён, так что решение 1979 года корректно, только если реализация выбирает честно. Я сделал выбор по кругу, и DONE стал срабатывать. А заодно сломался мой собственный RED-Kubernetes, но об этом в отдельной главе. И ещё одно свойство решения 1979 года нашлось само собой: если задача a погибнет, консоль оператора повиснет навсегда на отправке в почтовый ящик нулевого размера, который больше некому читать.

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

Ни одно не перевелось в том виде, в каком его напечатали. Интересно другое: какие именно ошибки у каждой команды. У красных это в основном небрежность. Необъявленные имена, функция OCTAL, которой в языке нет, параметр по имени rep, хотя REP — зарезервированное слово. Но попадаются и ошибки замысла, которые транслятор пропустил бы. В задании про движущиеся объекты позиции хранятся указателями, и проверка столкновения сравнивает указатели, которые никогда не равны: объекты на экране просто не могут столкнуться. В задании о защите базы данных каждая процедура находит запись, меняет её копию и выходит, так что ни одна бронь до базы не доходит.

У зелёных опечаток меньше, зато они чаще нарушают правила собственного языка. Четыре решения запускают задачи, выходят из цикла или возвращаются из процедуры прямо в теле accept, хотя руководство 1979 года это запрещает. Хватает и ошибок замысла. В задании о файлах запись начинается на байт дальше, чем потом читается, поэтому каждая запись читается со сдвигом. В распаковке пакетов под длину отвели восемь бит, хотя длина бывает до 256 и для неё нужно девять. В защите базы данных освобождение принимается только после новой брони, поэтому вызов входа FREE зависает навсегда, а ожидающий исключительного доступа может намертво сцепиться с другим. А в планировщике запрос, срок которого раньше головы списка, просто теряется, и первыми пропадают запросы оператора.

Эти тексты в 1979 году читали десятки команд рецензентов. Читали глазами: красные, по их собственным словам, прогнали через свой транслятор только синтаксис. Правки к ним тоже лежат рядом с решениями, так что разницу между тем, что напечатано и тем, что работает, видно сразу.

По самим текстам понятно и главное отличие двух языков. Красные решения короче вдвое, и три четверти разницы появляются из-за трёх заданий: файловый пакет, защита базы данных и планировщик. Там, где у красных встроенный замок, почтовый ящик или ожидание до заданного времени, зелёным приходится писать отдельную задачу-сервер, которая владеет данными и в порядке очереди обслуживает запросы. В задании про планировщик реального времени красные вообще не пишут планировщика: у них есть DELAY_UNTIL и обобщённая задача-обёртка, параметр которой — другая задача, всего 44 строки. Зелёные строят полноценную задачу-планировщик, которую будит прерывание часов, со списком отложенных запусков и семейством входов, 234 строки. В задании о защите базы данных красные ставят критическую секцию и повторяют попытку в цикле, а зелёные выстраивают пользователей в очереди к входам серверной задачи. Где у красных замок, у зелёных сервер. В этом весь спор 1979 года, о котором пойдёт речь дальше.

Операционная система в духе Tandem

Когда я читал главу RED о многозадачности, я вспомнил про Tandem NonStop (если что, это воспоминания моего клода, а не мои, я про такую машину до этого слыхом не слыхивал). Её операционная система Guardian появилась в 1976 году и была устроена на удивление похожим образом. Процессы не делят память и общаются только сообщениями, а каждый важный сервис работает парой процессов на разных процессорах: основной обслуживает запросы и перед каждым ответом отправляет резервному контрольную точку, то есть описание того, что изменилось. Если процессор основного процесса умирает, резервный узнаёт об этом от системы, которая следит за пульсом процессоров, и продолжает работу с последней контрольной точки. Джоэл Бартлетт описал это ядро в 1981 году на симпозиуме по принципам операционных систем, SOSP, а Джим Грей в 1985-м написал знаменитую статью о том, почему компьютеры останавливаются и что с этим делать.

В RED есть всё, чтобы это повторить. Почтовые ящики почти совпадают с системой сообщений Guardian, WAIT с тайм-аутом работает детектором пропавшего пульса, а EXTERMINATE прекрасно изображает обесточенный процессор. Так появилась маленькая операционная система PAIRS, всего около трёхсот строк.

В ней три процессора, портами процессов служат почтовые ящики, а таблица имён говорит, на каком порту сейчас живёт сервис $BANK. Банк работает процессной парой: основной на процессоре 0, резервный на процессоре 1. Два клиента делают по шесть переводов между счетами. Каждый запрос пронумерован, и если ответ не пришёл за 50 миллисекунд, клиент заново запрашивает таблицу имён и повторяет запрос с тем же номером.

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

[0 ms] $BANK primary on CPU 0 (port 3), backup on CPU 1 (port 4)
[6 ms] $BANK primary checkpointed request 3 of client 2 and has not replied yet
[6 ms] CPU 0 loses power
[41 ms] $BANK backup on CPU 1 hears no heartbeat: takes over as primary
[41 ms] $BANK backup started on CPU 2, port 5
[56 ms] client 2: no reply to request 3, retrying
[56 ms] client 1: no reply to request 3, retrying
[56 ms] $BANK: request 3 of client 2 is a retry, answered from the checkpoint
...
[68 ms] audit: every confirmed transfer is in the books exactly once

Резервный процессор 35 миллисекунд не слышит пульса, забирает имя $BANK, поднимает себе новый резерв на свободном процессоре и пересылает ему всё состояние. Клиенты не получают ответов и повторяют запросы. Запрос первого клиента сгорел в почтовом ящике мёртвого процесса, и новый основной выполняет его впервые. А запрос второго клиента новый основной узнаёт по номеру: контрольная точка до него дошла, так что перевод уже сделан, и клиенту просто возвращают сохранённый ответ. В конце клиенты сдают журнал всего, что им подтвердили, и он сверяется с книгами банка. Каждый подтверждённый перевод учтён ровно один раз.

А теперь самое поучительное. Если в основном процессе поменять местами две строки так, что ответ клиенту уходит раньше, а контрольная точка позже, и процессор умрёт между ними, получится вот что:

[68 ms] account 2: 40   clients were told: 10
[68 ms] account 4: 160   clients were told: 190
[68 ms] total 400
[68 ms] audit: 2 accounts disagree with what the clients were told

Клиенту подтвердили перевод тридцати единиц, а в книгах его нет. И обратите внимание: общая сумма денег по-прежнему 400, так что если смотреть только на неё, никакой ошибки не видно. Правило «контрольная точка до ответа» нужно именно для этого, и его очень легко нарушить из лучших побуждений, ради скорости. Это упражнение легло в основу одной из лабораторок.

THE Дейкстры

Tandem — не единственная система тех лет, которая просилась быть написанной на RED. За десять лет до Guardian, в 1965–1968 годах, группа Дейкстры в Эйндховене построила систему мультипрограммирования THE, и статья о ней стала одной из самых цитируемых в истории операционных систем. Главная её мысль — иерархия. Система в ней — общество последовательных процессов, разложенных по уровням от нулевого до пятого. На нулевом распределяется процессор и живут семафоры, на первом работает контроллер сегментов, который гоняет информацию между памятью и магнитным барабаном, медленной внешней памятью тех лет, на втором интерпретатор сообщений, владеющий единственной консолью, на третьем буферизация ввода и вывода, на четвёртом пользовательские программы, а на пятом сидит оператор. Семафор Дейкстры — это счётчик с двумя операциями: P ждёт, пока счётчик больше нуля, и уменьшает его, V увеличивает счётчик и будит одного ждущего. Процесс обращается только к уровням ниже себя, и Дейкстра утверждал, что благодаря этому правильность системы доказывается заранее, а её тестирование становится полным.

Я собрал THE на RED, и вышло около четырёхсот строк. Семафоры получились почтовыми ящиками с жетонами: P забирает жетон, V кладёт. REGION здесь не годится, потому что в THE один процесс делает V, а другой P, а критическая секция RED умеет только скобку внутри одного процесса. Восемь сегментов живут в трёх страницах памяти, и контроллер выгружает лишнее на свободную страницу барабана с наименьшей задержкой, ровно как написано в статье. Три перфоленточных ввода заполняют буферы, три программы считают суммы квадратов, принтер на третьей строке просит у оператора бумагу, и оператор через сто сорок миллисекунд её заряжает.

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

[20 ms] CONSOLE  reader 1: tape loaded, reading
[30 ms]   segment controller: segment 1 dumped from core page 1 to drum page 6
[40 ms] CONSOLE  reader 2: tape loaded, reading
*** deadlock: every task is waiting (t=400)

Контроллер ждёт консоль, консоль ждёт контроллер, чтобы прочитать словарь. Одна стрелка вверх, и доказательство Дейкстры перестаёт работать.

Для сравнения я написал ядро THE и на GREEN. Там нет ни семафоров, ни почтовых ящиков, поэтому каждый семафор становится задачей-сервером, которая принимает P, только пока счётчик положителен. Работает, но девять строк, напечатанных тремя программами через общий буфер, обходятся в 54 рандеву, по шесть на каждую напечатанную строку. Там, где RED просто забирает жетон из почтового ящика, GREEN на каждую операцию P и V вызывает задачу-сервер и ждёт рандеву с ней.

Раз THE работает, на ней можно запустить и Kubernetes. Но сначала о том, как Kubernetes устроен на почтовых ящиках.

Kubernetes на почтовых ящиках

Для тех, кто с Kubernetes не работал. В Kubernetes вы не командуете «запусти три копии сервиса», а записываете в хранилище желаемое состояние, развёртывание на три реплики, а набор независимых контроллеров раз за разом сравнивает желаемое с действительным и сокращает разницу: создаёт поды, то есть экземпляры приложения, назначает их на узлы, выселяет поды с узлов, которые перестали отвечать, и при обновлении версии выкатывает новые поды вместо старых. Все они читают и пишут через один API-сервер.

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

Вот как компоненты Kubernetes ложатся на RED:

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

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

Управляющий слой как процессная пара

А дальше начинается как раз то сумасшествие, ради которого, собственно, стоило соединять Tandem и Kubernetes. В Kubernetes надёжность управляющего слоя обеспечивает etcd: несколько копий хранилища договариваются друг с другом по протоколу Raft, и пока жив кворум, кластер управляем. А что, если сделать всё по-тандемовски? API-сервер работает парой: основной после каждого изменения, ещё до рассылки событий, отправляет резервному контрольную точку, резервный следит за пульсом и при его пропаже забирает имя. Никакого консенсуса, никакого кворума, просто пара процессов.

Проблема в том, что в отличие от банка здесь никто не повторяет запросы. Контроллер отправил в API-сервер запись и пошёл дальше, ответа он не ждёт. Если основной умер, всё, что лежало в его почтовом ящике, исчезает, и никто об этом не узнает. Я был почти уверен, что это не заработает, и устроил как можно более неприятный сбой: основной API-сервер обесточивается посреди выкатки новой версии, сразу после того как сохранил первый под этой версии. replicaset 10 в логе — набор реплик второй версии, его ведёт контроллер реплик. Смотрите на строки 60 и 95 мс: планировщик дважды привязывает один и тот же под 11, потому что первая привязка утонула вместе с почтовым ящиком мёртвого сервера.

[60 ms] replicaset 10: 0 of 4 pods, creating 4
[60 ms] api server primary loses power right after storing pod 11; the writes still in its mailbox are gone
[60 ms] scheduler: pod 11 -> node 1
[80 ms] replicaset 10: 1 of 4 pods, creating 3
[95 ms] api server backup: no heartbeat, taking over the name API
[95 ms] scheduler: pod 11 -> node 1
[95 ms] kubelet 1: pod 11 (version 2) running
[115 ms] replicaset 10: 1 of 4 pods, creating 3
[115 ms] scheduler: pod 12 -> node 2
...

Вместе с почтовым ящиком мёртвого сервера пропали три запроса на создание пода и одна привязка пода к узлу. На 80-й миллисекунде у контроллера реплик истекают ожидания, и он снова просит поды, но опять в пустоту, потому что имя всё ещё принадлежит мёртвому (а то, что мертво, умереть не может). Через пятнадцать миллисекунд резервный забирает имя и рассылает всем контроллерам полный список объектов. Планировщик видит, что под 11 на самом деле ни к какому узлу не привязан, и привязывает его, а ещё через двадцать миллисекунд, на 115-й миллисекунде, контроллер реплик досоздаёт недостающее. Кластер приходит туда, куда должен, без консенсуса и без участия человека. Работает это потому, что контроллеры Kubernetes сравнивают состояния, а не реагируют на события, и потерянная запись для них всего лишь ещё одно расхождение, которое заметит следующая сверка.

Два настоящих сбоя Kubernetes, найденных случайно

По-настоящему интересно было не то, что в итоге заработало, а то, как оно ломалось по дороге. В первом прогоне пары после переключения API-сервера контроллер узлов объявил неготовыми все три узла сразу и выселил вообще все поды. Пока резервный 35 миллисекунд ждал тишины, kubelet’ы продлевали аренды у мёртвого основного, и после переключения аренды всех узлов выглядели протухшими. Это хорошо известная проблема Kubernetes, и решение у неё тоже известное: если замолчали сразу все узлы, значит, отсутствовал управляющий слой, а не узлы, и выселять никого нельзя. В Kubernetes зона, где замолчали все узлы, переходит в состояние полного сбоя, FullDisruption, и если так со всеми зонами, контроллер выселения останавливается. Я добавил такую же проверку.

Во втором прогоне узлы выселялись по одному. Первым после переключения успел продлить аренду узел 3, условие «молчат все» перестало выполняться, и узлы 1 и 2 выселились. Причин оказалось две, и обе снова совпали с тем, как это устроено в настоящем Kubernetes. Свежесть аренды нельзя мерить временем, записанным в самой аренде, её надо мерить временем, когда контроллер сам увидел изменение. И решать надо не по каждому событию, а по полной картине: сначала выбрать из ящика всё, что там уже накопилось. Настоящий контроллер жизненного цикла узлов устроен близко к этому: он раз в несколько секунд обходит все узлы по своему кэшу, а при выходе из полного сбоя ещё и обнуляет всем узлам отсчёт свежести, чтобы первый продливший аренду узел не подставил остальных. После этих двух правок переключение API-сервера стоит кластеру ровно ноль выселений.

Кстати, сначала я выбирал накопившееся через WAIT с приёмом и нулевой задержкой и рассчитывал, что приём победит. Но когда рантайм стал выбирать готовые альтернативы нормально, нулевая задержка иногда побеждала, и узлы снова выселялись. Правильный способ в RED другой: спросить у ящика FULL_SLOTS, сколько в нём сообщений, и забирать их, пока они есть.

Мне очень нравится, что вариант с парой, около шестисот строк на языке 1979 года, сам, без подсказок, наступил на те же грабли, на которые Kubernetes наступал годами, и что решение оказалось тем же самым. Это хороший признак того, что грабли не случайны, а растут из самой идеи управления через сверку состояний.

То же самое на зелёном языке

Для полноценного сравнения я написал тот же управляющий цикл на зелёном языке. Устроен он аналогично: API-сервер, кэши контроллеров, оптимистическая запись, аренды узлов. По объёму версии почти равны, 522 строки на RED и 517 на GREEN, но спроектированы по-разному, и разница та самая, о которой спорили в 1979 году.

Почтовых ящиков в зелёном языке нет, есть только рандеву. Значит, поток событий для каждого контроллера становится задачей-буфером, семейством INBOX(1 .. 8) с входами PUT_EVENT и GET_EVENT, и около сорока строк уходит на то, что в RED было одним объявлением переменной. Дальше хуже. Контроллеру нужно ждать либо события, либо тайм-аута для периодической сверки, а вызова с тайм-аутом в зелёном языке 1979 года нет. Пришлось перенести тайм-аут внутрь ящика: если 20 миллисекунд ничего не приходит, ящик сам кладёт в очередь пустое событие-тик, и, получив его, контроллер понимает, что пора сделать полную сверку.

И есть ловушка, которую я предсказал заранее, а потом проверил. API-сервер рассылает события, вызывая INBOX(P).PUT_EVENT, и если ящик полон, сервер ждёт. Но владелец ящика в это время может сам ждать сервер, вызвав API.WRITE. Сервер ждёт контроллер, контроллер ждёт сервер. С ящиками на 256 событий этого не случается, а с ящиками на четыре кластер встаёт намертво. Причём рантайм даже не может назвать это взаимной блокировкой, потому что таймеры остальных ящиков продолжают тикать, и виртуальное время бежит вперёд вечно. В RED такая ловушка тоже возможна, но в зелёном мире она встроена в саму форму решения: где у RED ящик, у GREEN серверная задача, а две серверные задачи, вызывающие друг друга, — классический способ повиснуть.

Зелёная версия, к слову, нашла ошибку в моём общем рантайме. Когда узел обесточивается, его kubelet прерывается через abort, а он в этот момент как раз стоит в очереди ко входу своего ящика. Рантайм делал прерванную задачу готовой, но забывал убрать её запись из очереди входа, и через мгновение ящик «принимал» вызов уже завершившейся задачи и будил мертвеца. Руководство 1979 года в разделе 9.10 прямо говорит, что прерванный вызывающий из очереди убирается, так что это была именно моя ошибка, а не баг языка.

Kubernetes на THE

Осталось последнее: запустить тот же цикл управления не на почтовых ящиках, а на THE из предыдущей главы. Правило я поставил жёсткое. Контроллеры живут на четвёртом уровне, как пользовательские программы THE, и пользуются только тем, что THE даёт программам: P и V, сегментами, консолью и часами. Почтовые ящики и WAIT остаются внутри нижних уровней, так как на них построена сама THE.

Kubernetes от этого меняется сильнее, чем я ожидал. API-сервера в такой модели нет вовсе: хранилище — это сегменты, которые контроллер сегментов гоняет между памятью и барабаном, и охраняет их один семафор. Подписка на изменения превращается в семафор пробуждения у каждого контроллера, и тот, кто что-то записал, будит всех. Семафор насыщается на единице, поэтому пробуждение говорит только «посмотри ещё раз», а не «вот что изменилось», и контроллеры получаются управляемыми уровнем, а не событием, просто по устройству. Тайм-аутов у P нет, а ждать двух семафоров сразу процесс не умеет, так что пересинхронизация, пульс узлов и проверка аренды идут от процесса-часов на нулевом уровне, который будит всех раз в десять миллисекунд. Даже команда оператора «увеличь до пяти» доходит до контроллера развёртываний через тот же семафор пробуждения, а сама команда остаётся в сегменте.

Первая версия дала больше всего полезной информации. Отказ узла я изобразил так же, как в PAIRS: EXTERMINATE по задаче kubelet посреди работы. Kubelet в этот момент держал семафор хранилища. V так и не случилось, и весь управляющий слой залип намертво: ни планировщик, ни контроллер узлов, который как раз должен был заметить пропажу, больше не могли войти в хранилище. В Kubernetes на RED этого не было, потому что там хранилищем владеет один процесс и kubelet с ним только переписывается. В THE данные общие, и процесс, умерший посреди критической секции, забирает с собой всех. Дейкстра честно писал, что первой большой ошибкой его группы было проектировать «идеальную установку» и они слишком поздно задумались об отказах. Я повторил их ошибку в первые пять минут:) Теперь узел гаснет между двумя проходами своего цикла, и кластер переносит его поды на живые узлы. На GREEN та же схема работает, но семафоры там снова задачи-серверы, и один прогон стоит 1168 рандеву.

Ада 83 и то, что вернулось потом

Победившая Ада не сразу стала той Адой, которую все знают. Между зелёным языком весны 1979 года и стандартом 1983 года прошло четыре года правок, поэтому с красным я сравниваю обе версии.

Чтобы сравнение было не просто на словах, я взял три примера из лабораторок по RED и написал их на Аде 83, а CI проекта собирает эти программы компилятором GNAT в режиме Ады 83 и сверяет вывод.

Первый пример — ограниченный буфер между производителем и потребителем. В RED это одна строка, VAR m : MAILBOX[INT](3), и вызовы SEND и RECEIVE. В Аде 83 почтовых ящиков нет, поэтому буфер — это серверная задача с двумя входами, которая в цикле выбирает, какой вход сейчас можно принять: PUT, пока есть место, и GET, пока есть что отдать. Получается около тридцати строк, которые любой, кто программировал на Аде, набирал сотни раз.

Второй — ожидание ответа с тайм-аутом на стороне вызывающего. В RED это WAIT с двумя ветками. В Аде 83 для этого есть вызов входа с ограничением по времени, select ... or delay ... end select. А вот у зелёного языка 1979 года его не было вовсе: ни такого вызова, ни условного вызова. В обосновании зелёного проекта за этим стоит принцип: задача может стоять только в одной очереди, а значит, вызывающий не выбирает между несколькими ожиданиями. Через четыре года Ада от этого принципа частично отказалась.

Третий — критическая секция. В RED это REGION, который отпускает замок, как бы ни закончилось тело. В Аде 83 замок делается задачей с входами SEIZE и RELEASE, и если между ними случилось исключение, замок не отпустит никто. Надо не забыть сделать это в обработчике, и строчка LOCK.RELEASE; -- forget this line and the next SEIZE waits forever в моей программе — именно про это.

Рядом лежат ещё три маленьких примера, и каждый написан трижды: на RED, на GREEN 1979 года и на одних семафорах THE.

Первый пример про тайм-аут: производитель замолкает, и потребитель должен это заметить. В RED потребитель сам ждёт элемента, но не дольше тридцати миллисекунд. В GREEN 1979 года вызова входа с тайм-аутом нет, поэтому сдаётся не потребитель, а сервер буфера: его select с альтернативой delay отвечает ждущему, что ничего нет. А в THE у P тайм-аута нет вообще, и сторож на часах подбрасывает в буфер фальшивый элемент, чтобы разбудить потребителя.

Второй пример про отказ под замком. REGION в RED отпускает замок при исключении, а задача-замок в GREEN и семафор в THE остаются захваченными, и второй работник ждёт вечно.

Третий — читатели и писатель. В RED исключительный REGION выстраивает всех в очередь, и работа занимает сорок миллисекунд. В GREEN данными владеет сервер, он раздаёт копии, и чтение идёт внахлёст, за тринадцать миллисекунд. На семафорах THE, по решению Куртуа, Хейманса и Парнаса 1971 года, читатели читают вместе, но опоздавший читатель проходит раньше уже ждущего писателя.

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

Что Ада вернула со временем

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

Утверждения были у обоих финалистов, этого требовал Steelman. В Аде 83 оператор assert выбросили, слова «assert» в стандарте 1983 года нет вообще. Прагма Assert вернулась только в Аде 2005, через двадцать шесть лет.

Рандеву оказалось слишком тяжёлым для защиты общих данных. В обосновании Ады 95 так и написано: сама универсальность рандеву означает относительно большие накладные расходы, поэтому вводятся защищённые объекты, лёгкий механизм синхронизации, ориентированный на данные. По сути это та самая отдельная примитивная конструкция для общих данных, которую предлагал RED. Важная оговорка: в обосновании Ады 95 предками защищённых объектов названы условные критические секции Хоара, мониторы и язык Orca, а RED не упомянут ни разу. Так что это не заимствование, а сходимость. Но сходимость показательная.

Насколько тяжёлым было рандеву, я проверил там, где оно было дешевле всего: на Rational R1000, машине, которую строили под Аду и у которой задачи жили прямо в микрокоде. Датский музей компьютеров вернул её к жизни и написал эмулятор, который исполняет настоящий микрокод такт за тактом. Я загрузил в нём Rational Environment с музейных дисков, через консоль оператора скомпилировал маленький тест на Аде 83 и посчитал такты. Вызов процедуры обходился машине в 2,75 микросекунды, рандеву в 55, то есть примерно в двадцать вызовов. Тот же текст, собранный GNAT на сегодняшнем сервере, вызывает процедуру за наносекунду с небольшим, а рандеву проходит за 13,5 микросекунды: это уже десять тысяч вызовов. Вызов за эти годы подешевел в две тысячи раз, рандеву вчетверо. Защищённые объекты Ады 95 появились в мире, где задачи живут уже не в микрокоде, а в потоках операционной системы.

Дальше больше. Профиль Ravenscar для систем высокой надёжности запрещает входы задач совсем, Max_Task_Entries => 0, то есть в самой ответственной Аде рандеву просто нет. В Аде 2012 в стандартную библиотеку добавили ограниченные синхронизированные очереди, функционально это типизированный ограниченный почтовый ящик.

Следующая линия ещё нагляднее. В тринадцатой главе руководства по RED описаны пользовательские определения для специальных форм языка: своё присваивание, автоматическая инициализация и финализация, свои операции выбора компонент и индексации, свой цикл по пользовательскому типу и свои литералы. Пользовательское присваивание и финализация пришли в Аду в 1995 году, пользовательская индексация и итераторы в 2012-м, пользовательские литералы в 2022-м. Не хватает только пользовательского case.

И последнее, что меня по-настоящему удивило. Пересмотр Ады начался в 1988 году, а конкурс проектировщиков около 1990 года выиграла команда Intermetrics, которая обошла даже команду того самого Ишбиа, который руководил проектом GREEN. Техническим руководителем стал Такер Тафт, а среди консультантов оказался Бен Брозгол, руководитель красного проекта 1979 года. Ишбиа участвовал в качестве рецензента и в итоге ушёл из проекта, не согласившись с объектной моделью. То есть Аду 95 спроектировали люди из компании, проигравшей в 1979 году. Сам Тафт пришёл в Intermetrics в сентябре 1980-го и в красной команде не был, так что прямой наследственности тут нет. Но компания, культура и часть людей были теми же.

What if… голосование прошло бы по-другому

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

Мир, где победил RED

Начнём с того, что точно не изменилось бы. Обязательное использование Ады в Минобороне длилось с 1987 по 1997 год, сначала как директива, потом даже как строка в законе, и отменили его не из-за рандеву или почтовых ящиков, а потому, что коммерческий рынок ушёл в сторону C и C++, а требование использовать Аду начинало стоить дороже той выгоды, которую оно давало. Эта экономика не зависела от цвета языка. Так что красная Ада, скорее всего, точно так же стала бы языком авионики, железных дорог и космоса и точно так же не стала бы языком для всего остального.

А вот внутри этой ниши изменилось бы многое.

Первое и главное — параллельность. В красном мире с первого дня есть два разных механизма: сообщения для общения задач и критические секции для общих данных. Ада потратила шестнадцать лет, чтобы прийти к тому же разделению, и ещё десять, чтобы в самой надёжной своей версии отказаться от рандеву совсем. В красном мире книга Бёрнса, Листера и Уэллингса 1987 года «A Review of Ada Tasking», разбор многозадачности Ады, была бы про совсем другое. Взамен пришла бы другая беда, о которой предупреждал ещё Пер Бринч Хансен, вместе с Хоаром придумавший мониторы. Критические секции можно поставить где угодно, и в большой программе они расползаются по всему коду: каждая процедура сама захватывает замок вокруг общих данных, и уже не видно, кто и когда эти данные трогает. Монитор лечит это тем, что собирает все операции над общими данными в одном месте. Думаю, к середине восьмидесятых красная Ада получила бы свой вариант защищённых объектов, только с другой стороны, как способ собрать разбросанные регионы в модуль.

Второе — обобщения. Неявное создание экземпляров в точке вызова, как в RED, оказалось очень удобным, когда я писал на нём компилятор. Но у него есть известная цена, которую мир узнал на шаблонах C++: ошибки, которые всплывают глубоко внутри экземпляра, и раздувание кода. В красном мире эти проблемы появились бы на десятилетие раньше, в военных проектах с их требованиями к сертификации, и, возможно, именно там впервые додумались бы до того, что потом стало концептами. Тем более что список NEEDS уже был готовым черновиком концептов.

Третье — сама индустрия языков. Страуструп в своей истории C++ прямо пишет, что после 1985 года на C++ влияли идеи Ады, CLU (языка Барбары Лисков из MIT середины семидесятых, где впервые появились абстрактные типы данных, обобщения и исключения) и ML, что параметризованные типы и исключения он сравнивал с Адой, а часть вдохновения для потоков ввода-вывода взял с последних полутора страниц обоснования Ады 1979 года, где доказывалось, что типобезопасный и краткий ввод-вывод невозможен. Это было обоснование зелёного проекта, его напечатали в SIGPLAN Notices. В красном мире там лежало бы обоснование RED, и шаблоны C++ сравнивались бы с языком, где экземпляры создаются сами. Возможно, шаблоны C++ вообще стали бы проще, потому что не надо было бы спорить с явным new из Ады.

Четвёртое — Oracle. Документация Oracle до сих пор прямо говорит, что PL/SQL основан на Аде и хранит в базе программы в виде деревьев DIANA, промежуточного представления Ады. DIANA придумали в январе 1981 года на встрече, где среди участников были Нестор и Брозгол из красной команды. В красном мире PL/SQL был бы построен на RED, и в каждой базе Oracle сегодня лежали бы процедуры с капсулами и EXPOSE. А может быть, и с DATA_LOCK для блокировок строк, кто знает.

Пятое — VHDL. Язык описания аппаратуры ВВС заказали в 1983 году консорциуму Intermetrics, TI и IBM, и экспертом по языку там была Intermetrics. VHDL в итоге сильно похож на Аду. Ирония в том, что компания проигравших сделала аппаратный язык по образцу победившего зелёного. В красном мире они копировали бы собственный язык, и процессы в VHDL, возможно, общались бы через почтовые ящики, а не через сигналы.

И шестое, самое неожиданное для меня. Эрланг. Ericsson в середине восьмидесятых сравнивал языки для телефонных станций, и в списке была Ада. Джо Армстронг пишет, что сначала попробовал конвейеры, pipes, выбросил их и сделал почтовые ящики. Соблазнительно сказать, что в красном мире Эрланг не понадобился бы. Но это неправда: Эрланг держится на изоляции процессов, асинхронной копирующей передаче и обработке отказов, а в RED есть общие переменные, ящики ограничены и блокирующие. Так что скажу скромнее: красная Ада была бы ближе к Эрлангу, чем зелёная, и, возможно, раньше показала бы военным и железнодорожникам, что системы на сообщениях живут дольше систем на общей памяти. Моя операционная система PAIRS на трёхстах строках как раз об этом.

Мир, где зелёный язык заморозили в 1979 году

Второй сценарий скромнее, но интереснее, чем кажется. Представим, что после выбора не было четырёх лет шлифовки, и Ада 83 — это просто предварительная Ада весны 1979 года.

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

Не было бы типов задач. Нельзя было бы сделать массив задач или задачу внутри записи, только семейства задач и обобщённые задачи. Не было бы вызова с тайм-аутом. Не было бы альтернативы terminate, так что серверные задачи пришлось бы останавливать явно. Думаю, это первое, что потребовали бы исправить пользователи, и правильно.

Что мне кажется главным

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

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

Лабораторки

Как и в прошлых частях, мне хотелось, чтобы читатель мог не только прочитать про язык, но и сломать что-нибудь своими руками. В каталоге impl/ada-colors/labs лежат двенадцать упражнений на RED и скрипт check.sh, который переводит вашу версию программы, запускает её и говорит, выполнено ли упражнение. У каждой лабораторной есть номер и несколько уровней: look — посмотреть, change — изменить, break — сломать, build — построить. Номер и уровень передаются check.sh аргументами, например labs/check.sh 03 look. И поскольку время в программах виртуальное, а планировщик детерминированный, ваш вывод можно сравнить с чужим символ в символ.

Вот что там есть:

• 01 — капсула со стеком: добавить экспортируемую функцию peek, а потом попробовать залезть в поле top снаружи и посмотреть, как компилятор объясняет, что тип экспортирован, а его компоненты нет;

• 02 — закрытая область: убрать переменную из IMPORTS и получить отказ, а потом попробовать присвоить переменной, импортированной только для чтения;

• 03 — почтовый ящик: сделать его размер нулевым и увидеть, что отправитель больше не может забегать вперёд, это рандеву;

• 04 — WAIT: проиграть гонку тайм-ауту, а потом попытаться ждать отправки в нулевой ящик и узнать, почему RED это запрещает;

• 05 — REGION: убрать обработчик исключения и посмотреть, как рантайм сообщает, что все задачи стоят;

• 06 — приоритеты: дать задачам равные приоритеты и увидеть порядок «первым пришёл — первым обслужен»;

• 07 — обобщения: написать свой max для чисел и строк, не создавая экземпляров вручную;

• 08 — процессная пара: перенести смерть основного процесса на другой запрос, а потом поменять местами отправку ответа и контрольной точки и поймать аудитом пропавший перевод;

• 09 — Kubernetes с управляющим слоем-парой: убрать выборку очереди в контроллере узлов и получить выселение здоровых узлов после переключения;

• 10 — сам компилятор: добавить в redc встроенную функцию MAX, пересобрать его и убедиться, что неподвижная точка сохранилась;

• 11 — программа 1979 года: выбросить одну правку из списка и посмотреть, на какой ошибке оригинала остановится транслятор;

• 12 — система THE Дейкстры: разрешить контроллеру сегментов докладывать оператору о каждой выгрузке на барабан и посмотреть, как вся система встаёт, потому что консоли нужен тот самый контроллер, который её ждёт.

Чтобы всё это запустить, нужен только компилятор C и make:

git clone https://github.com/tym83/paleocomputing
cd paleocomputing/impl/ada-colors
make                     # собирает redc из готового C-файла и проверяет неподвижную точку
red/tests/run.sh         # тесты языка
os/run.sh                # операционные системы и все варианты Kubernetes на всех языках
labs/check.sh 03 look    # лабораторная про почтовые ящики

Программу на RED можно перевести и запустить и без лабораторных:

build/redc < программа.red > программа.c
cc -std=gnu11 -Irt программа.c rt/paleo.c -lpthread -lm -o программа
./программа

Если под рукой есть Cozystack — открытая платформа для построения облака на Kubernetes, — ставить ничего не нужно. В каталоге приложений, который я собрал для этой серии, есть среда для языков, и языки попали туда в виде отдельного образа контейнера: указываете образ ada-colors-run, кладёте исходник, и программа выполняется разовым заданием Kubernetes (Job), а её вывод становится логом. Внутри образа компиляторы при сборке заново проходят путь от сохранённого C-файла и проверяют, что воспроизводят себя.

А проще всего открыть страницу в браузере. Там всё происходит прямо на странице, без сервера. Трансляторы, собранные в WebAssembly из тех же C-файлов, переводят исходник в C. Дальше этот C компилирует clang, тоже собранный в WebAssembly, а программа выполняется так, что каждая задача получает свой поток и все потоки работают на общей памяти. Рантайм там тот же файл, что и в Linux, с теми же виртуальными часами, поэтому лабораторные, ядро PAIRS, Kubernetes на RED и на GREEN, управляющий слой-пара и примеры из четырнадцатой главы руководства печатают в браузере то же самое, что на обычной машине, байт в байт. Это проверяет CI: прогоняет каждый пример в Chrome без окна и сравнивает вывод. Первый запуск скачивает компилятор C, около двадцати мегабайт, дальше браузер держит его у себя.

Что я забираю с собой

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

Первое — разделение механизмов. Сообщения служат для общения, замки для общих данных, и ни один механизм не мимикрирует под другой. Ада потратила шестнадцать лет, чтобы прийти к тому же, а в мире Kubernetes мы постоянно видим, как одним механизмом пытаются закрыть всё: то очередь используют как базу, то базу как очередь. Красная команда в 1979 году хорошо понимала, почему так делать нельзя.

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

Третье — процессные пары. Это, пожалуй, самый неожиданный для меня результат. Управляющий слой Kubernetes в виде тандемовской пары без консенсуса пережил смерть API-сервера посреди выкатки, потому что контроллеры сравнивают состояния, а не реагируют на события. Для одной площадки, где кворум из трёх узлов etcd часто просто негде взять, это серьёзная альтернатива, и я хочу проверить её не на модели, а на настоящем кластере.

Четвёртое — детерминированное время. Почти всё интересное в этой статье нашлось потому, что любой сбой воспроизводится до миллисекунды. Так нашлись и нечестный выбор в WAIT, и ошибка с прерванным вызовом входа, и обе ловушки контроллера узлов. На настоящих потоках и настоящих часах половину этого я бы искал неделями, а другую половину не нашёл бы вовсе. Для тестирования распределённой инфраструктуры это, по-моему, главный урок: сначала сделать время управляемым, потом искать ошибки.

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

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

Исходники, тесты, лабораторные и все заметки лежат в репозитории github.com/tym83/paleocomputing в каталоге impl/ada-colors. Если найдёте ошибку в моём прочтении руководств 1979 года, напишите, мне правда интересно.

Предыдущие части серии о палеокомпьютинге:

• Часть 1. Процессор Вирта, Проект Оберон, новая архитектура в QEMU и KubeVirt и запуск в Cozystack и Kubernetes

• Часть 2. Kubernetes на Обероне, радио Вирта вместо сети и кластер в браузере