В феврале 1978 года четыре команды сдали Министерству обороны США предварительные проекты языка, которому через год дадут имя Ада. Проекты обезличили, и вместо названий фирм у них были цвета. Зелёный проект делала франко-американская команда Жана Ишбиа, красный — бостонская фирма Intermetrics, синий — фирма SofTech, а жёлтый — калифорнийский институт SRI International. Весной того же года во второй тур прошли зелёный и красный проекты, синий и жёлтый отправились в архив, а ещё через год зелёный язык победил и стал Адой.
Как выбирали Аду: четыре проекта в феврале 1978 года, два во втором туре, один победитель в мае 1979-го
В статье о финалистах я восстановил красный и зелёный языки по документам 1979 года: написал для каждого компилятор, который компилирует сам себя, и собрал на обоих операционную систему и Kubernetes. Синий и жёлтый языки тогда казались недоступными, потому что их описания лежали в томе на четыре с половиной тысячи страниц, а архив Минобороны как раз перестал его выдавать. Потом в веб-архиве нашлась копия, и с этими двумя языками я сделал то же самое.
Эта статья посвящена двум проектам, которые проиграли зелёному и красному языкам. Синий язык построен вокруг типов настолько последовательно, что даже присваивание в нём определяется как операция типа. Жёлтый же был Паскалем, который переделали под требования военных. Задачи в нём общаются не через рандеву, как в зелёном языке и в Аде, где одна задача ждёт другую у условленного входа, пока они не встретятся, а через мониторы Хоара, то есть модули с общими данными, внутри которых в каждый момент может находиться только один процесс. Для обоих языков я написал компиляторы на них самих, и эти компиляторы впервые запустили программы, которые авторы языков напечатали в своих отчётах в 1978 году и которые с тех пор никто не видел работающими. Кроме того, на обоих языках теперь работают система THE, многозадачная операционная система, которую группа Дейкстры построила в шестидесятых, и Kubernetes поверх неё.
Но интереснее самих языков то, что теперь все четыре проекта можно поставить рядом и сравнивать не по рецензиям, а по работающему коду. Один и тот же пример на четырёх языках ведёт себя по-разному, и эти различия оказались любопытнее, чем я ожидал. Если в синем языке 1978 года одна из параллельных веток завершается с ошибкой, об этом узнаёт тот, кто запустил ветки, а массовые языки научились этому лишь в последние годы. Мьютекс в нём освобождается сам, если ветка, которая его захватила, завершилась аварийно. А в жёлтый язык встроено искусственное время, и часы там идут только тогда, когда этого хочет сама программа.
Статья длинная, поэтому скажу заранее, о чём в ней пойдёт речь. Сначала я расскажу о книге 1978 года, из которой взяты тексты, и о людях, которые делали эти языки, а потом мы по очереди пройдёмся по синему и жёлтому языкам. Дальше разберём одни и те же примеры на всех четырёх языках и сведём различия в таблицу, посмотрим на компиляторы и на программы 1978 года, на THE и Kubernetes и попробуем понять, почему эти проекты проиграли. В конце я расскажу, что из них потом появилось в Аде и как могло бы развиваться программирование, если бы конкурс выиграл синий или жёлтый язык.
Это очередная часть моей серии о палеокомпьютинге. Мне интересно, какие идеи жили в технологиях, которые не выстрелили или так и остались уделом энтузиастов и теоретиков, что мы потеряли вместе с ними и что из потерянного потом вернулось в других технологиях. Статью о финалистах читать не обязательно: там, где это нужно, я коротко напомню, как устроены красный и зелёный языки.
Все исходники, заметки и инструкции лежат в репозитории github.com/tym83/paleocomputing, в каталоге impl/ada-colors, и доступны под лицензией Apache 2.0.
Книга, которую делали для микрофиш
Начну с того, откуда вообще взялись тексты. В 2023 году в рассылке systemsafety, где обсуждают надёжность программ для ответственных систем, промелькнуло любопытное сообщение. По просьбе одного энтузиаста DTIC, архив технической документации Минобороны, отсканировал том «DoD Common High Order Language, Phase 1» на 4575 страниц. В каталоге архива он значится под номером ADB950587, и в нём собраны все четыре проекта первого тура. Пока я возился с красным и зелёным языками, сайт DTIC сначала закрылся на обслуживание, а потом стал отказывать в любых запросах. Выручила Wayback Machine, куда в сентябре 2023 года кто-то сохранил этот PDF целиком. На томе стоит та же пометка, что и на руководстве по красному языку: «допущено к открытой публикации, распространение не ограничено».
Предисловие тома ADB950587
Ключ к цветам на следующей странице: зелёный — CII-Honeywell Bull, красный — Intermetrics, жёлтый — SRI International, синий — SofTech
Предисловие к книге само по себе является ценным историческим документом. Составители пишут, что книгу делали для микрофиш, то есть карточек фотоплёнки с уменьшенными страницами, которые читали через увеличитель, и что переплетённой версии у неё никогда не было: все двести печатных экземпляров сразу ушли рецензентам, так что микрофиши остаются единственным комплектом, который вообще можно распространять. Там же раскрыты все цвета и названо, кто за каким из них стоит. Заканчивается предисловие фразой, которую я перечитал несколько раз. Проигравшие проекты продолжать не будут, интересны они разве что исследователям, цель программы в том, чтобы прийти к одному языку, и поощрять альтернативы Министерство обороны считает неуместным.
Внутри собраны четыре проекта в том виде, в каком их сдали 15 февраля 1978 года. Красный язык там ещё в первой редакции: это тот самый REDL с мониторами, который красная команда потом выбросила и написала фактически заново. За проектами идут разборы, которые прислали восемьдесят команд, от университетов до военных подрядчиков, и отчёт питтсбургской комиссии. Члены комиссии изучили эти разборы, расспросили авторов языков и свели всё в таблицы, по которым в апреле 1978 года решали, кто выйдет в финал.
Распознанный текст местами оказался ужасным: вместо буквы O там стоит ноль, вместо S доллар, вместо знака процента буква l. Поэтому каждую программу я сверял с изображением страницы, а программы на синем языке, в коде которых полно обратных косых черт и решёток, и вовсе перепечатывал с картинок.
Кто делал синий и жёлтый языки
Синий проект вёл Джон Гуденаф из SofTech, и в истории Ады это имя далеко не последнее. В 1975 году он опубликовал в Communications of the ACM одну из первых больших работ об обработке исключений, а после конкурса SofTech под его руководством получила контракт на набор тестов, по которому компиляторы Ады проверяли на соответствие стандарту. Потом Гуденаф возглавлял группу, которая толковала стандарт, и писал требования к Аде 95. Так что синяя команда хоть и проиграла, но ещё два десятилетия занималась Адой.
Жёлтый проект вёл Джей Спитцен из SRI International, исследовательского института в Калифорнии, где в те годы строили SIFT, отказоустойчивый бортовой компьютер для самолётов; к нему мы ещё вернёмся. Популярная книга издательства Time-Life 1986 года и Бертран Мейер пишут, что жёлтую команду консультировали Хоар и Вирт. В самом документе консультанты по именам не названы, но их идеи видны на каждой странице. Описание языка построено так же, как описание Паскаля, которое написал Вирт, модули взяты из его Модулы, мониторы из статьи Хоара 1974 года, а в списке литературы встречаются ссылки «Хоар, частное сообщение» и «Вирт, частное сообщение».
Что об этих языках думал Дейкстра
Дейкстра потратил весь март 1978 года на то, чтобы прочитать все четыре проекта, и о каждом написал рецензию. Синему проекту досталось за главу о типах и операциях, которая, по его словам, «разрослась до 160 (!) страниц». Жёлтый проект он назвал безнадёжной мешаниной и добавил, что сочувствует консультантам, которым не удалось этого предотвратить. Если вспомнить, кого называют консультантами жёлтой команды, фраза звучит едко.
О красном и зелёном проектах он тоже писал без восторга, так что по его рецензиям проигравшие проекты от победивших не отличить. Решали в итоге рецензенты и комиссия экспертов, и к их выводам я вернусь, когда покажу оба языка в работе.
BLUE: язык, построенный вокруг типов
Из четырёх языков синий кажется самым непривычным, поэтому начну с короткой программы из лабораторной работы. Одна и та же процедура меняет в ней местами два целых числа, две строки и два цвета:
TYPE COLOR = ENUM (RED, GREEN, BLUE);VAR I, J: INTEGER;VAR A, B: ASCII_STR (4);VAR K, M: COLOR;...SWAP (# I, J);SWAP (# A, B);SWAP (# K, M);PROCEDURE SWAP (# X, Y: ?T) WHERE T NEEDS (STORE_ (T ## T)); VAR TMP: T; TMP := X; X := Y; Y := TMP;END PROCEDURE SWAP;FUNCTION FRAME (S: ASCII_STR (?L)) RETURNS (ASCII_STR (L + 2)); RETURN '[' !! S !! ']';END FUNCTION FRAME;
Здесь почти каждый значок что-то значит, так что разберём их по порядку.
Так синий язык выглядел в самой спецификации: обобщённый стек, где выводит тип элемента, разделяет группы параметров, перечисляет исключения, а говорит, что требуется от типа
Литералы перечислений пишутся с обратной косой чертой: RED, GREEN. Это не прихоть авторов. Литерал в синем языке не принадлежит какому-то одному типу, так что GREEN может быть одновременно цветом светофора и цветом радуги и в каждом из этих типов стоять на своём месте. Какой из них имеется в виду, решает контекст, а когда контекста не хватает, тип указывают явно: [COLOR]$$(GREEN). Бывают и неупорядоченные перечисления, UNORDERED, у которых определено одно только равенство. Масть карты не бывает больше или меньше другой масти, и язык не позволяет сделать вид, будто бывает.
Параметры процедуры делятся на три группы, входные, изменяемые и выходные, и между группами ставятся решётки. В SWAP (# X, Y) входных параметров нет, и оба параметра изменяемые. В STORE_ (T ## T) один входной параметр типа T, изменяемых нет, и один выходной того же типа: присваивание берёт значение и выдаёт новое значение переменной. Эти группы видны и там, где процедуру вызывают, так что SWAP (# I, J) сразу говорит читателю, что I и J изменятся.
?T обозначает обобщённый тип, который выводится из аргумента. Экземпляр процедуры для каждого типа создаётся сам, в точке вызова, и никому не нужно его называть или объявлять. В красном языке было так же, а в зелёном и в Аде экземпляр приходится создавать явно. Выводить можно не только типы. ASCII_STR (?L) берёт из аргумента длину строки, и функция FRAME обещает вернуть строку длиной L + 2, потому что длина здесь входит в тип и компилятор её знает.
А запись WHERE T NEEDS (STORE_ (T ## T)) задаёт список того, что телу процедуры нужно от типа T, а нужно ему здесь только присваивание. Эти операции берутся там, откуда процедуру вызвали. Если у типа присваивания нет, вызов не скомпилируется, и компилятор выдаст понятную ошибку в месте вызова, а не где-то в глубине экземпляра. Сегодня то же самое называют концептами в C++ и ограничениями трейтов в Rust.
Присваивание — тоже функция
STORE_ в предыдущем примере не опечатка. В синем языке каждая операция, будь то присваивание, сравнение или взятие подстроки, записывается как вызов функции с заранее заданным именем: ADD_, EQUAL_, LESS_THAN_, SUBSTRING_, STORE_. Поэтому абстрактный тип, который экспортирует модуль, определяет себе сложение и присваивание одним и тем же способом, как обычные подпрограммы. В Аде своего присваивания нет до сих пор: контролируемые типы Ады 95 позволяют задать, что делать после копирования и перед уничтожением, но не само присваивание. А в C with Classes, предшественнике C++, присваивание можно было переопределять уже в 1980 году.
Один из рецензентов 1978 года написал, что синий проект ближе всех подошёл к тому, чтобы тип связывал весь язык воедино, и это видно по многим деталям.
Возьмём числа. На ЭВМ семидесятых плавающей точки часто не было, и дробные величины хранили как целые с подразумеваемой запятой, например скорость в сотых долях метра в секунду. Это и есть фиксированная точка, и обычно программисту приходилось самому помнить, где у какой переменной стоит запятая. В синем языке это помнит тип. FIXED (scale, radix, precision) говорит, на сколько разрядов сдвинута запятая, в какой системе счисления и с какой точностью, а компилятор сам выравнивает запятые, когда складывает или сравнивает такие числа. Даже INTEGER здесь устроен как фиксированная точка, у которой запятая стоит в самом конце. Ни один другой проект не описывает фиксированную точку так подробно.
Со строками то же самое. Кодировка входит в тип строки, и в CHAR_STR (L, C) буква L означает длину, а C набор символов, ASCII или, скажем, какой-нибудь шестибитный BCD, которых у машин того времени было великое множество. Поэтому одну функцию можно написать сразу для строк в любой кодировке, а склеить строку в ASCII со строкой в BCD компилятор не даст.
Даже работа с железом в синем языке описывается через типы. Коды, которыми устройство сообщает о своём состоянии, выбирал не программист, а инженер, проектировавший плату. В синем языке такое состояние описывается обычным перечислением, и каждому значению назначается тот код, который выбрало железо:
TYPE STATUS = UNORDERED (IDLE, BUSY, DONE, FAULT) REP ENUM_VAL_REP (4, VALUES (IDLE AS BIN '0000', BUSY AS BIN '0001', DONE AS BIN '1000', FAULT AS BIN '1111'));...SELECT OBJECT_MACHINE FROM PDP_11 --> S := [STATUS]$$(REGISTER); END;END SELECT;
Здесь стоит обратить внимание на две детали. Задать свои коды разрешено только неупорядоченному типу, потому что коды железа могут идти в любом порядке и по ним уже не поймёшь, какое значение больше. Авторы Ады пришли к тому же с другой стороны: в ней коды можно задать любому перечислению, но обязательно по возрастанию. А прочитать код из регистра устройства как значение типа можно только в машинно-зависимой части программы, внутри SELECT OBJECT_MACHINE, где программа явно указывает, на каком железе она это делает.
Закрытые области и объявленные исключения
Как и в красном языке, процедура в синем языке представляет собой закрытую область: внешних переменных она не видит, пока не импортирует их. Только синий язык здесь строже красного. Процедура, которая вызывает другую процедуру, должна импортировать либо её саму, либо все переменные, которые та использует, и поэтому по заголовку любой процедуры видно, до каких данных она может добраться через всю цепочку вызовов. Решётка в списке импорта значит то же, что и в параметрах. В IMPORTS (DATA: (# MUTEX, BALANCE)) всё стоит после решётки, то есть обе переменные импортированы для изменения, а то, что процедура только читает, пишется перед решёткой. Сама же программа на синем языке состоит из сегментов, то есть единиц трансляции, которые в разделе USES перечисляют, что они берут друг у друга.
Исключения в синем языке объявляются в заголовке подпрограммы, например SIGNALS (OVERFLOW, INVALID_FORMAT), и выпустить наружу исключение, которого нет в этом списке, подпрограмма не может. SofTech в обосновании объясняет это тем же, чем и списки импорта: интерфейс процедуры должен быть описан полностью, и то, какие исключения она может возбудить, — такая же его часть, как то, что она может изменить. В 1978 году так делали разве что в языке CLU у Барбары Лисков, а в массовые языки проверяемые исключения, то есть такие, которые компилятор заставляет объявить или обработать, пришли вместе с Java. В Аде их нет и никогда не было.
Обработчик исключений в синем языке привязан не к блоку, а к оператору, и EXCEPT можно поставить после любого оператора. Кажется, что это мелочь, пока не напишешь BLOCK ... EXCEPT ... END BLOCK и не обнаружишь, что обработчик относится только к последнему оператору блока, а не ко всему блоку. Я на этом попался, и в заметках к компилятору это теперь отдельный пункт.
Параллельный блок
В том, что касается параллельности, синий язык строже всех четырёх. Задач в привычном смысле в нём нет. Есть параллельный блок PAR_BLOCK, внутри него параллельные ветки PATH, и блок не заканчивается, пока не закончатся все его ветки. Сам по себе такой блок не нов, это parbegin ... parend Дейкстры 1965 года. Новое в другом: если в какой-то ветке возникло исключение, которое она не обработала, но которое ей разрешено возбуждать, блок дождётся остальных веток и возбудит это исключение у себя, так что сбой ветки становится сбоем блока и его можно обработать снаружи.
Вот пример. В блоке две одинаковые ветки, WORKER 1 и WORKER 2, и каждая прибавляет 10 к общему балансу, который вначале равен 100. Чтобы ветки не мешали друг другу, баланс защищён семафором MUTEX: ветка захватывает его через REQUEST, меняет баланс и освобождает через RELEASE, а подробнее о семафорах я расскажу чуть ниже. В первой ветке я нарочно возбуждаю исключение FAILED в тот момент, когда она держит семафор. Пока смотрите на SIGNALS (FAILED) в заголовке ветки и на EXCEPT после блока:
VAR MUTEX: SEMAPHORE (REGION) := NEW (1);VAR BALANCE: INTEGER := 100;PAR_BLOCK PATH WORKER FOR ID IN [1:2] SIGNALS (FAILED) IMPORTS (DATA: (# MUTEX, BALANCE)); PAUSE (ID); % PAUSE и LOG — мои процедуры: ожидание в миллисекундах REQUEST (# MUTEX); % и строка журнала с отметкой времени PAUSE (5); IF ID = 1 THEN SIGNAL FAILED; END IF; BALANCE := BALANCE + 10; RELEASE (# MUTEX); END PATH WORKER;END PAR_BLOCK;EXCEPT FAILED --> LOG ('the block signals FAILED: worker 1 ended abnormally'); END;END EXCEPT;
Тот же пример в браузере: первая ветка аварийно завершается, не освободив семафор, вторая сразу его получает, а блок возбуждает . Вывод показан с замедлением, на виртуальных часах программа проходит всё за доли секунды.
Сегодня такой подход называют структурной параллельностью. Параллельные ветки вложены в блок программы так же, как обычные операторы: блок не закончится, пока не закончатся они, а если в какой-то ветке случился сбой, о нём узнает тот, кто этот блок запустил. Лет восемь назад эту идею начали заново вводить повсюду: в библиотеке Trio для Python, в группах задач Swift, в StructuredTaskScope в Java. Синий блок устроен проще. Если одна ветка завершилась с ошибкой, соседние продолжают работать, и остановить их нужно самому, через TERMINATE, а если с ошибкой завершились две ветки, наружу выйдет только одно исключение из двух. Причём TERMINATE не обрывает ветку на полуслове. Ветка получает исключение TERMINATED, когда до неё в следующий раз дойдёт очередь работать, и может его перехватить, например чтобы прибраться за собой. Есть у веток и приоритеты: если работать готовы две ветки, процессор достаётся той, у которой приоритет выше.
В Аде 83 блок тоже ждёт свои задачи, но если в задаче возникло исключение и она его не обработала, задача завершается. Исключение дальше никуда не передаётся, и тот, кто её запустил, о сбое не узнаёт. Это одна из самых известных ловушек Ады, и в синем языке 1978 года её нет.
У такой строгости есть и своя цена. Параллельный блок нельзя поставить внутрь подпрограммы, так что запустить пару веток из процедуры не получится, и это ещё аукнется нам, когда дойдёт до Kubernetes на синем языке.
Два вида семафоров
В синем языке нет ни почтовых ящиков, то есть очередей сообщений между задачами, как в красном, ни рандеву, как в зелёном. Ветки договариваются друг с другом через семафоры. Семафор Дейкстры представляет собой счётчик с двумя операциями: P ждёт, пока счётчик станет больше нуля, и уменьшает его на единицу, а V увеличивает счётчик и будит одного из тех, кто ждёт. В синем языке семафоры бывают двух видов, и различие между ними тонкое. SYNCH устроен как классический семафор без владельца: одна ветка ждёт события, а другая сообщает, что оно произошло. REGION же служит блокировкой для общих данных, и у неё есть владелец; сегодня такой семафор назвали бы мьютексом. Если ветка, которая захватила такой семафор, завершилась аварийно, система освобождает его сама.
Раздел 3.11 спецификации SofTech: семафоры и . Семафоры , которые ветка захватила и не освободила, при её аварийном завершении освобождаются автоматически
Вернёмся к примеру выше. Первая ветка завершается аварийно, так и не освободив семафор, но семафор этот вида REGION, и система освобождает его сама. Поэтому вторая ветка тут же его получает и прибавляет свои 10, а программа доходит до конца с балансом 110 и не зависает навсегда в ожидании семафора, который уже некому освободить. Важно, что система освобождает семафор, только если ветка завершилась аварийно, то есть если исключение так никто и не обработал. Если ветка сама обработала исключение и продолжила работу, захваченные семафоры остаются за ней. На этом построена одна из лабораторных работ.
Почему бы не освобождать при аварийном завершении ветки вообще все семафоры? В обосновании SofTech есть ответ и на это. Запомнить, что ветка захватила семафор, можно только внутри самой операции захвата. Если записывать это отдельной командой сразу после захвата, ветка может завершиться в промежутке, когда семафор уже захвачен, а запись о том, кто его захватил, ещё не сделана. Значит, освобождать семафоры аварийно завершившейся ветки должна сама система, а не обработчик исключений в программе. Но если система станет освобождать все семафоры подряд, она освободит заодно и сигнальные, и те, кто их ждёт, получат сигналы о событиях, которых не было. Поэтому семафоров два вида, и автоматически освобождаются только блокировки.
У такого решения есть очевидный недостаток, и SofTech его не скрывает. Ветка могла прерваться на середине записи, и тогда следующая ветка получит семафор вместе с наполовину обновлёнными данными. В SofTech с этим согласились, но рассудили, что для компьютеров в самолётах, кораблях и ракетах, ради которых язык и затевали, это не страшно: данные там обычно приходят с датчиков, и через мгновение их всё равно перезапишут свежими показаниями. Лет через тридцать та же задача встала перед авторами POSIX, стандарта, по которому устроены Unix-системы, и они решили предупреждать следующего владельца. Если поток, владеющий так называемым устойчивым мьютексом, аварийно завершился, тот, кто захватит мьютекс следующим, получает код EOWNERDEAD, который означает, что прежний владелец завершился, не освободив мьютекс, и данные могут быть испорчены. Новый владелец должен проверить данные и объявить, что с ними всё в порядке, иначе мьютексом больше нельзя будет пользоваться. В синем языке такого предупреждения нет, и семафор переходит к следующей ветке молча.
Со временем в синем языке тоже не всё привычно. WAIT (30) усыпляет ветку на тридцать секунд, но секунды здесь хранятся двоичной дробью с фиксированной точкой, и ровно одну миллисекунду в ней не запишешь, так же как ровно одну треть не запишешь десятичной дробью. А CLOCK, насколько я понимаю спецификацию, показывает не время суток, а то, сколько проработала сама ветка. Поэтому время для журналов мои программы берут из часов имитируемой машины.
YELLOW: Паскаль под требования Ironman
Если синий язык начинался с типов, то жёлтый начинался с Паскаля. Министерство обороны писало требования к языку поэтапно, и их редакции назывались Strawman, Woodenman, Tinman, Ironman и Steelman, от соломенного человека до стального, причём каждая была подробнее предыдущей. Проекты первого тура опирались на Ironman 1977 года, и SRI пишет в отчёте, что её целью было спроектировать язык, переделав Паскаль под эти требования. Описание жёлтого языка разбито на разделы с теми же номерами, что и описание Паскаля, составленное Виртом, и один раздел даже оставлен пустым, лишь бы номера совпадали. Программа на нём читается как Паскаль с длинными закрывающими словами:
MODULE Enumerations IMPORT TextIO, StandardImplementationPrelude; REPRESENTATION Phase = ORDERED (Pending, Running, Succeeded); Fruit = UNORDERED (Lemon, Lime, Orange); VAR p: Phase := Pending; PROCEDURE WritePhase (CONST p: Phase) SELECT p CASE Pending => Write("Pending") CASE Running => Write("Running") CASE Succeeded => Write("Succeeded") ENDSELECT; RETURN ENDPROCEDURE WritePhase; FOR q: Phase DO WritePhase(q); Write(" ") ENDFOR; ...ENDMODULE Enumerations
К Паскалю добавлены модули из Модулы, мониторы и сигналы, шаблоны модулей, исключения и перегрузка. Регистр букв различается: зарезервированные слова пишутся заглавными, а имена как угодно. Знака «не равно» в ASCII не нашлось, и его, как в Модуле, пишут решёткой.
Тип и представление
Главным, что SRI придумала сама, стало разделение типа и представления. Представлением здесь называется не формат в памяти машины, как REP в синем языке, а ограничение на значения. INTEGER считается типом, то есть множеством значений вместе с операциями над ними, а INTEGER [1..10] является одним из его представлений, а именно целыми числами от одного до десяти. У чисел с плавающей точкой представление задаёт ещё и точность, а у чисел с фиксированной точкой шаг. Объявить переменную можно только с представлением, одного INTEGER для этого мало. Зато разные представления одного типа совместимы между собой: INTEGER [1..5] и INTEGER [0..9] остаются одним и тем же типом, и при присваивании проверяется только то, что значение попало в диапазон. Перечисления тоже объявляются как представления, в разделе REPRESENTATION, как в примере выше.
Глава VI спецификации жёлтого языка: тип — множество значений, представление — его подмножество или способ хранения. Тип и представление
В Аде то же самое называется подтипами: subtype SMALL is INTEGER range 1 .. 10 не создаёт нового типа, а только сужает старый. Разница в том, что в Аде подтип служит дополнительной возможностью, а в жёлтом языке без представления не обойтись. Чтобы создать новый тип, нужно отдельное объявление, TYPE T = INTEGER, и числа этого типа пишутся вместе с его именем: T 50.
Перечисления бывают упорядоченными и неупорядоченными, как в синем языке, и BOOLEAN здесь неупорядоченный: истина не больше лжи. Перегружать имена можно только явно. Если новая функция называется так же, как уже существующая, её помечают словом EXTENDS, когда она добавляется к старым, или словом REPLACES, когда она их заменяет, а без пометки новое объявление скрывает все старые. Так что случайно перегрузить что-нибудь в жёлтом языке невозможно, а читатель программы сразу видит, где имя получило новый смысл.
Вычитание без скобок и приоритет сравнений
Вычитание в жёлтом языке нельзя записать цепочкой. Сложение и умножение ассоциативны, и a + b + c пишется без скобок, а вот a - b - c считается синтаксической ошибкой, как и a * b DIV c, и порядок приходится указывать скобками: (a - b) - c. Паскаль и почти все остальные языки читают такое выражение слева направо. Это не прихоть SRI, этого требовал Ironman: по пункту 4G скобки обязательны, если подряд идут операции одного приоритета и левая из них неассоциативна. SRI выполнила требование буквально, а SofTech в обосновании синего языка написала, что этот пункт надо отменить, и в следующей редакции требований его смягчили до пожелания.
Второе правило коварнее, и досталось оно от Паскаля. Сравнения в жёлтом языке, как и в Паскале, имеют самый низкий приоритет, ниже, чем у AND и OR. Поэтому x > 0 AND b читается как x > (0 AND b) и не компилируется. Хуже, когда типы сходятся: тогда ошибки нет вовсе, и f = f AND g для логических f и g молча означает f = (f AND g). Чуть позже я покажу, как на этом правиле попались сами авторы языка.
Чистые функции и процедуры со значением
Функции в жёлтом языке чистые: менять свои параметры они не могут, а присваивать значения могут только собственным локальным переменным. Поэтому с одними и теми же аргументами функция всегда возвращает один и тот же результат, где бы её ни вызвали. Ironman этого не требовал, и здесь SRI пошла дальше требований. А для того, что должно менять состояние, вроде «выдай следующий номер», есть процедуры, которые возвращают значение:
FUNCTION Square RETURNS INTEGER64 (CONST x: INTEGER64) RETURN x * xENDFUNCTION Square;PROCEDURE NextTicket RETURNS INTEGER64 () ticket := ticket + 1; RETURN ticketENDPROCEDURE NextTicket;
В зелёном языке 1979 года этот вопрос решили почти так же, а в Аде 83 от такого разделения отказались.
Шаблоны модулей
Обобщённые модули в жёлтом языке устроены проще, чем в остальных трёх. Шаблон модуля, TEMPLATE, представляет собой текст с параметрами. Оператор INSTANCE переписывает этот текст, подставляя вместо параметров то, что ему передали, и только потом транслирует получившийся модуль. Каждый экземпляр становится отдельным модулем со своим состоянием, а ошибка в теле шаблона обнаруживается только при создании экземпляра, как в шаблонах C++ с их сообщениями об ошибках на три экрана. В синем языке всё наоборот: требования к типу записаны в списке NEEDS и проверяются там, где обобщённую процедуру вызывают.
Разделы X.C–D спецификации жёлтого языка: экземпляр шаблона означает то же, что модуль, переписанный заново с подставленными параметрами
Мониторы Хоара
Зато параллельность получилась самой удачной частью жёлтого языка. Процессы в нём общаются только через мониторы. Монитор, который придумали Хоар и Пер Бринч Хансен, представляет собой модуль, процедуры которого выполняются строго по одной, а внутри него есть сигналы, то есть очереди, в которых процесс может уснуть до нужного события. В Java и POSIX такие очереди называют условными переменными. Вот решение классической задачи о читателях и писателях, монитор из статьи Хоара 1974 года, переписанный на жёлтый язык:
MONITOR ReadersAndWriters IMPORT INTEGER64; EXPORT StartRead, EndRead, StartWrite, EndWrite; VAR readers: INTEGER64 := 0; busy: BOOLEAN := FALSE; okToRead, okToWrite: SIGNAL; PROCEDURE StartRead () IF busy OR AWAITED(okToWrite) THEN WAIT(okToRead) ENDIF; readers := readers + 1; SEND(okToRead); RETURN ENDPROCEDURE StartRead; PROCEDURE EndRead () readers := readers - 1; IF readers = 0 THEN SEND(okToWrite) ENDIF; RETURN ENDPROCEDURE EndRead; ...ENDMONITOR ReadersAndWriters;
Сигналы в жёлтом языке работают так, как их описал Хоар. SEND передаёт монитор процессу, которого разбудил сигнал, из рук в руки, а процесс, пославший сигнал, ждёт, пока разбуженный процесс не выйдет из монитора или снова не уснёт. Поэтому разбуженный процесс может проверить условие через IF, а не через WHILE: между сигналом и пробуждением никто не успеет вклиниться и снова всё испортить. В Xerox в 1980 году для языка Mesa выбрали другой вариант, где сигнал служит лишь подсказкой, и процесс, который он разбудил, должен ещё раз проверить условие в цикле. Общепринятым стал второй вариант: так устроены wait и notify в Java и условные переменные POSIX. Про while вокруг wait знает каждый, кто писал на Java, а в жёлтом языке этот цикл не нужен. Платить за это приходится дисциплиной: посылать сигнал можно только тогда, когда условие выполнено. А если завести сторожевой процесс, который по тайм-ауту будит ожидающий процесс, пока условие ещё ложно, то проверять условие после пробуждения придётся и в жёлтом языке.
У ожидания есть ранг: WAIT(s, rank) ставит процесс в очередь по номеру, и SEND будит процесс с наименьшим рангом. AWAITED(s) спрашивает, ждёт ли кто-нибудь этого сигнала. А ещё сигнал можно привязать к адресу прерывания, и тогда его посылает само железо.
Пример из учебника жёлтого языка: монитор часов реального времени, переписанный из Модулы Вирта. Процесс часов ждёт сигнала от таймера и будит всех, кто ждёт следующего тика
Для тех, кому монитор кажется слишком тяжёлым, есть и двоичные семафоры с операциями CLAIM и RELEASE. Но их, как будет видно дальше, лучше не трогать.
Искусственное время
Напоследок о том, что в жёлтом языке меня удивило больше всего. Любой блок BEGIN ... END можно пометить словом SIMULATED_TIME, и тогда процессы внутри этого блока работают не одновременно, а по очереди, как части одной обычной программы. Каждый из них работает, пока не начнёт чего-нибудь ждать, и только тогда процессор переходит к следующему. Внутри блока идёт своё, искусственное время. Любой оператор занимает ноль единиц этого времени, кроме DELAY(n), который занимает ровно n, а часы двигаются вперёд лишь тогда, когда все процессы внутри блока чего-то ждут.
Раздел IX.B.3 спецификации жёлтого языка: перед , и любой оператор занимает ноль единиц времени, кроме
Выходит, что в язык 1978 года встроено моделирование с управляемым временем. Требование дать «часы для моделирования» было в Ironman, и авторы синего проекта ответили на него обещанием написать модуль моделирования, как в Симуле, норвежском языке для моделирования, с которого началось объектно-ориентированное программирование. Жёлтый же сделал из этого конструкцию языка, в которую можно обернуть любой кусок настоящей программы. Сегодня ради того же пишут отдельные системы. Разработчики базы данных FoundationDB построили на таком моделировании всё своё тестирование: программа идёт по искусственным часам, сеть и диски заменены моделями, и любой прогон можно повторить шаг за шагом. Позже из этого выросла отдельная компания, которая продаёт такую среду для чужих программ. Жёлтому языку до этого далеко: в каком порядке пойдут процессы, спецификация не оговаривает, а сбоев железа язык не моделирует. Но часы, которые идут, только когда этого хочет программа, в нём уже есть.
В моём проекте используется тот же приём. Программы на всех четырёх языках работают по виртуальным часам, а планировщик всегда выбирает процессы в одном и том же порядке, поэтому любой сбой повторяется с точностью до миллисекунды. Раз часы у меня и так везде виртуальные, SIMULATED_TIME в моём компиляторе делает то, что сверх этого требует спецификация: внутри такого блока процессы не отбирают процессор друг у друга по истечении кванта времени, а переключаются, только когда кто-то из них начинает ждать.
Одни и те же задачи на четырёх языках
По воспоминаниям красной команды, рецензенты 1978 года делили четыре проекта на две пары: консервативные синий и красный проекты и амбициозные, «академические» жёлтый и зелёный. Во второй тур взяли по одному языку из каждой пары. Теперь, когда работают все четыре, можно убедиться, что такое деление было не случайным, и проще всего это сделать на одном и том же примере.
Две пары 1978 года: консервативные синий и красный, амбициозные жёлтый и зелёный, и у каждого свой способ синхронизации
Пример возьмём тот же, что и в главе о синем языке. Два процесса по очереди прибавляют по 10 к общему балансу и, чтобы не мешать друг другу, захватывают для этого блокировку. Первый захватывает её и аварийно завершается, не успев освободить. Сможет ли второй её получить? Вопрос не академический: в любой системе с блокировками, от ядра операционной системы до базы данных, первым делом спрашивают, что станет с блокировкой, если процесс, который её держит, аварийно завершится. В главе о Kubernetes этот вопрос всплывёт снова.
В красном языке блокировкой служит REGION, и она освобождается, как бы ни закончился блок:
REGION d DO DELAY(5); IF id = 1 THEN RAISE X_RANGE; END IF; balance := balance + 10;END REGION;
В зелёном языке 1979 года, как и в Аде 83, блокировку изображает отдельная задача-сервер с двумя входами, SEIZE и RELEASE. Сервер просто ждёт вызова RELEASE и больше ничего не знает:
task body LOCK isbegin loop accept SEIZE; accept RELEASE; end loop;end LOCK;...LOCK.SEIZE;begin delay 0.005 * SECONDS; if ID = 1 then raise RANGE_ERROR; end if; BALANCE := BALANCE + 10; LOCK.RELEASE;exception when RANGE_ERROR => LOG("worker 1 failed while holding the lock");end;
В синем языке, как мы уже видели, семафор вида REGION освобождается, если ветка завершилась аварийно; программа целиком приведена в главе о синем языке. А у жёлтого языка два ответа, и они противоположны. Монитор освобождается, если в его процедуре возникло исключение и вывело процесс из монитора, а двоичный семафор с операциями CLAIM и RELEASE не освобождается никогда:
MONITOR Account ... PROCEDURE Update (CONST id: INTEGER64) DELAY(5); IF id = 1 THEN PROPAGATE_EXCEPTION OUT_OF_RANGE ENDIF; balance := balance + 10; RETURN ENDPROCEDURE Update; ...ENDMONITOR Account;
Вот что выводят эти программы. Если второй процесс за сто миллисекунд так и не получил блокировку, программа сдаётся и подводит итог. Вот вывод программы на красном языке:
[1 ms] worker 1 holds the lock[6 ms] worker 1 failed inside the region[6 ms] worker 2 holds the lock[11 ms] both workers are through, balance 110: the region released the lock for the failed one
На зелёном языке:
[1 ms] worker 1 holds the lock[6 ms] worker 1 failed while holding the lock[100 ms] 1 of 2 workers through, balance 100: worker 2 still waits on SEIZE, nothing released the lock
На синем языке:
[1 ms] worker 1 holds the semaphore[6 ms] worker 1 fails holding it[6 ms] worker 2 holds the semaphore[11 ms] the block signals FAILED: worker 1 ended abnormally[11 ms] both workers are through, balance 110: the path's end released its REGION semaphore
На жёлтом языке:
[1 ms] worker 1 holds the monitor[6 ms] worker 1 failed inside the monitor[6 ms] worker 2 holds the monitor[11 ms] both workers are through, balance 110: leaving the monitor by an exception gave it up[11 ms] worker 3 claimed the semaphore[16 ms] worker 3 failed between CLAIM and RELEASE[112 ms] worker 4 asked 100 times: no exception gives a semaphore back
Справедливости ради, в программе на зелёном языке процесс мог бы сам вызвать RELEASE в своём обработчике исключений, а в программе на жёлтом языке можно было бы так же поступить с семафором. Но это ручная работа, о которой легко забыть. А главное, она не спасает, если процесс не завершается из-за исключения, а его прерывают снаружи: в зелёном языке и в Аде прерванная задача обработчиков не выполняет, и блокировка остаётся захваченной навсегда. Так что вся разница в том, кто отвечает за освобождение блокировки, программист или язык.
Три языка из четырёх берут эту заботу на себя, и каждый по-своему. Красный язык привязывает освобождение к тексту программы: как только выполнение вышло из REGION, блокировка свободна. Синий язык привязывает его к судьбе ветки: если ветка завершилась аварийно, захваченные ею блокировки освобождаются, а сигнальные семафоры нет. Жёлтый язык привязывает его к границе модуля: если исключение вывело процесс из монитора, монитор свободен. И только в зелёном языке, который и победил в конкурсе, язык сам блокировку не освобождает, потому что отдельного механизма для общих данных в нём нет. Блокировку там изображает такая же задача, как любая другая, и о том, что клиент аварийно завершился, она не знает. Такой механизм, защищённый объект, появился в Аде только в 1995 году.
Есть и ещё одна деталь, которую видно только в программе на синем языке: блок узнал, что первая ветка завершилась аварийно, и сообщил об этом. В остальных языках исключение обработал сам процесс, в котором оно возникло, а если бы не обработал, задача завершилась бы, и об этом никто бы не узнал.
Задача о читателях и писателях
Второй пример посвящён классической задаче о читателях и писателях. Три читателя приходят на нулевой, первой и третьей миллисекунде, писатель на второй, а чтение и запись занимают по десять миллисекунд. В хорошем решении читатели читают одновременно, но читатель, пришедший позже писателя, не может его обогнать, иначе при постоянном потоке читателей писатель так никогда и не дождётся своей очереди.
Решение в репозитории
Читают одновременно
Поздний читатель обгоняет ждущего писателя
Всё закончено к
RED, монопольный REGION
нет
нет, все стоят в одной очереди
40 мс
GREEN, сервер раздаёт копии данных
да, на копиях
третий читатель получает старую копию
13 мс
BLUE, семафоры P и V
да
да
23 мс
YELLOW, монитор Хоара
да
нет
31 мс
Эти цифры не показывают предела возможностей языков, это всего лишь решения, которые выбрал я. На семафорах тоже можно пропустить писателя вперёд, такой вариант описали Куртуа, Хейманс и Парнас ещё в 1971 году, но он длиннее. На мониторе Хоара то же самое умещается в три десятка строк, потому что мониторы для таких задач и придумывали. Но за соблюдение очереди приходится платить временем: третий читатель ждёт писателя и заканчивает на 31-й миллисекунде, а не на 23-й.
Ожидание с тайм-аутом
В третьем примере нужно дождаться ответа, но не дольше заданного времени. Здесь различия оказались самыми болезненными.
Задачи красного языка общаются через почтовые ящики, то есть типизированные очереди сообщений ограниченного размера, а для ожидания в нём есть одна конструкция, WAIT. Она ждёт, какое из нескольких событий наступит первым, и одним из этих событий может быть таймер. В зелёном языке 1979 года ожидание с тайм-аутом доступно только серверу, через select с альтернативой delay, а клиент ограничить своё ожидание не может; такой вызов появился только в Аде. В синем же и жёлтом языках ни один процесс не умеет ждать сразу двух событий, например элемента в очереди или срабатывания таймера, смотря что случится раньше. В синем языке это обходят гонкой двух веток, в жёлтом — сторожевым процессом, который будит ожидающий процесс, или опросом семафора через CONDITIONAL_CLAIM. Подробнее об этом я расскажу в главе о Kubernetes, потому что тайм-аутов там много и во что обходятся эти приёмы, стало видно сразу.
Сводная таблица
А вот чем четыре проекта отличаются друг от друга и от Ады 83. Красный и зелёный языки здесь взяты в редакции 1979 года, синий и жёлтый — в редакции 1978-го.
RED
GREEN
BLUE
YELLOW
Ада 83
Основа
Паскаль, переписан заново
Паскаль
Паскаль, переписан вокруг типов
Паскаль и Модула
GREEN после четырёх лет правок
Модули
капсулы
пакеты
модули и сегменты
модули Модулы
пакеты
Внешние переменные в процедуре
только импортированные
видны
только импортированные, по всей цепочке вызовов
видны внутри модуля
видны
Обобщения
экземпляры создаются сами
явные экземпляры
экземпляры создаются сами, требования к типу в NEEDS
шаблоны модулей переписывают текст
явные экземпляры
Операции
перегрузка
перегрузка
всё, включая присваивание, — функции с фиксированными именами
перегрузка только явная, через EXTENDS и REPLACES
перегрузка, своего присваивания нет
Функции
без побочных эффектов, если не помечены
без побочных эффектов, плюс процедуры со значением
только входные параметры
без побочных эффектов, плюс процедуры со значением
только входные параметры, побочные эффекты можно
Исключения
объявляются как имена
объявляются как имена, 15 стандартных
перечисляются в заголовке подпрограммы
не объявляются
объявляются как имена, 5 стандартных
Параллельность
задачи и почтовые ящики
задачи и рандеву
ветки PATH в параллельном блоке
процессы и мониторы
задачи и рандеву
Блокировка общих данных
REGION
задача-сервер
семафор REGION
монитор
задача-сервер
Ожидание с тайм-аутом
WAIT с таймером
только у сервера
гонка двух веток
сторожевой процесс или опрос
и у сервера, и у клиента
Необработанное исключение в задаче
задача завершается, никто не узнаёт
задача завершается, никто не узнаёт
блок возбуждает исключение
задача завершается, никто не узнаёт
задача завершается, никто не узнаёт
Если читать таблицу по строкам, пары видны сразу. Синий и красный языки требуют импортировать переменные, сами создают экземпляры обобщений и дают отдельную блокировку для данных. Жёлтый и зелёный языки, напротив, требуют функций без побочных эффектов и обходятся одним изящным механизмом параллельности, только авторы жёлтого языка выбрали для этого монитор, а авторы зелёного языка рандеву. А последняя строка показывает, что из пяти языков о необработанном исключении в параллельной ветке сообщает наружу только синий язык.
Компиляторы и первый запуск программ 1978 года
Цель была та же, что и с финалистами из прошлой статьи: у каждого языка должен быть компилятор, написанный на нём самом. Когда пишешь на языке несколько тысяч строк разбора текста, таблиц имён и проверки типов, быстро становится ясно, годится он для настоящей работы или нет.
Путь тоже был тот же. Сначала пишется маленький транслятор на Python, который понимает подмножество языка. На этом подмножестве пишется первая версия компилятора, и питоновский транслятор её собирает. Потом компилятор собирает сам себя, и результат сравнивается с предыдущим. Если второе поколение совпадает с третьим байт в байт, достигнута неподвижная точка: компилятор, собранный самим собой, порождает в точности себя и больше не зависит от питоновского транслятора. С этого момента в репозитории хранится C-код, который компилятор сгенерировал из собственного исходника, и из него компилятор можно собрать без Python. Дальше язык развивается уже с помощью этого компилятора, и каждую новую версию собирает предыдущая. Оба компилятора переводят программу в C и собирают её с той же общей средой выполнения, что и у красного и зелёного языков, с виртуальными часами и детерминированным планировщиком.
Оба компилятора достигли неподвижной точки с первой попытки: третье поколение каждого из них сразу совпало со вторым байт в байт. Компилятор синего языка разросся примерно до шестнадцати тысяч строк, это больше, чем у любого из четырёх, и в полтора раза больше, чем у компилятора красного языка. По-моему, лучшей оценки сложности синего языка не придумать: всё, что в нём завязано на типы, компилятору приходится выводить и проверять. Компилятор жёлтого языка занимает примерно десять тысяч строк. В жёлтом языке нет строк как значений, нет даже их склейки, поэтому все строки, с которыми работает его компилятор, хранятся в одном большом массиве символов, а сама строка представлена номером в этом массиве. Примерно так же были устроены компиляторы Паскаля в те же семидесятые.
Программы из документов 1978 года
С программами на этих двух языках вышла история интереснее, чем с финалистами. В первом туре реализаций не было ни у кого, так что ни одну программу из описаний синего и жёлтого языков никто никогда не компилировал, и мои компиляторы оказались для них первыми.
В описании синего языка напечатано семнадцать программ. Если дописать то, что в оригинале заменено многоточием, семь из них компилируются и работают. Ещё три компилируются, но работают неправильно: в произведении матриц из-за одной буквы первое слагаемое каждого элемента берёт второй множитель из первой матрицы вместо второй, а два примера возбуждают исключение, потому что выходят за собственные диапазоны. Оставшиеся семь компилятор не пропускает из-за ошибок вроде BUFF вместо BUF или аргументов, переданных не в том порядке.
Самой большой программой оказалась стандартная библиотека ввода-вывода из приложения C, тысяча триста с лишним строк с драйверами телетайпов, привязанными к прерываниям PDP-11. Чтобы её скомпилировать, пришлось переименовать процедуру IN, потому что это слово зарезервировано, и перенести в сегмент константу, которую экспортируют два модуля, хотя по правилам модуль экспортирует только типы и подпрограммы. Вместе с опечатками набралось около двух десятков правок, семь из которых исправляют нарушения правил языка, и после них библиотека заработала на имитации PDP-11 с двумя телетайпами LT33, как DEC называла Teletype Model 33. Для тысячи трёхсот строк, которые никто ни разу не компилировал, это хороший результат, и о синей команде он говорит лучше любой рецензии.
Приложение C синего языка в браузере: библиотека ввода-вывода 1978 года печатает на двух имитированных телетайпах LT33. Вывод показан с замедлением, на виртуальных часах программа проходит всё за доли секунды.
В учебнике жёлтого языка программ пятнадцать, и четыре из них компилируются в том виде, в каком напечатаны. В остальных встречаются ошибки, которые копятся в любом тексте, ни разу не побывавшем в трансляторе: ConvexHullFinder закрывается как ComplexHullFinder, а пример сортировки пишет IMPORTS и EXPORTS, словно взятые из какого-то другого языка. Но чаще авторы забывали правила собственного языка, и прежде всего правило о сравнениях, о котором я рассказывал выше. В учебнике есть планировщик задач для SIFT, того самого бортового компьютера, и условие ept > 0 AND enabled[pri] в нём читается как ept > (0 AND enabled[pri]) и значит не то, что задумано.
Три программы и после исправлений работают неправильно. В сортировке обменом сравнение строк считает одну строку больше другой, только если каждая её буква больше соответствующей буквы другой строки, поэтому обычные имена эта сортировка не переставляет никогда. А построение выпуклой оболочки для восьми точек отмечает как вершины только две из них. Сначала я решил, что ошибся мой транслятор, и переписал тот же алгоритм на Python, но Python отметил те же две точки. Ошибка была в самом алгоритме 1978 года, и за сорок восемь лет её никто не заметил, потому что запустить программу было не на чем.
Все исправления лежат в репозитории отдельными файлами, для синего языка и для жёлтого языка, а исходники сохранены в том виде, в каком их напечатали, и к каждой правке приложено объяснение и правило, которое было нарушено.
THE и Kubernetes на синем и жёлтом языках
Компилятор проверяет язык на последовательном коде. Чтобы проверить ещё и параллельность, в статье о финалистах я написал на красном и зелёном языках несколько систем, а теперь повторил их на синем и жёлтом языках.
Первой из них стала THE, система мультипрограммирования, которую группа Дейкстры построила в Эйндховене в 1965–1968 годах. Сам Дейкстра описывал её как набор последовательных процессов, разложенных по уровням. На нулевом уровне реализованы семафоры и распределяется процессор. На первом работает контроллер сегментов, который перегоняет сегменты между памятью и магнитным барабаном, медленной внешней памятью тех лет. На втором стоит единственная консоль оператора, на третьем буферы ввода-вывода, а на четвёртом пользовательские программы. Каждый процесс обращается только к уровням, которые лежат ниже его собственного.
Для тех, кто с Kubernetes не работал, коротко поясню, как он устроен. Вы записываете в хранилище желаемое состояние, например развёртывание на три реплики, а набор контроллеров раз за разом сравнивает его с действительным и сокращает разницу: создаёт поды, то есть экземпляры приложения, назначает их на узлы и переносит с узлов, которые стали недоступны. Всё это вместе называют управляющим слоем.
Второй системой стал Kubernetes поверх THE. Контроллеры Kubernetes работают в ней как пользовательские программы четвёртого уровня, хранилище объектов лежит в сегментах на барабане, а у каждого узла есть kubelet, программа, которая запускает на нём поды.
Третьей стал управляющий слой Kubernetes без THE. В нём есть API-сервер, который сам присылает подписчикам каждое изменение объектов (в Kubernetes это называется watch), контроллеры со своими копиями состояния и аренды, то есть записи, которые узел должен регулярно продлевать, чтобы считаться работающим.
И сразу стало видно, что объединяет синий и жёлтый языки и чем они отличаются от финалистов. Ни в одном из них процессы не обмениваются сообщениями, и, как я уже говорил, ни в одном процесс не может ждать сразу двух событий.
THE на синем языке
THE на синем языке получилась естественной. Семафоры синего языка и есть P и V Дейкстры, и её вывод совпадает с выводом версии на красном языке символ в символ. Каждый уровень системы стал модулем, так что в списке импорта каждого процесса написано, к каким уровням он обращается.
THE на синем языке в браузере: контроллер сегментов перегоняет страницы между памятью и барабаном, а принтер ждёт, пока оператор заправит бумагу. Вывод показан с замедлением, на виртуальных часах программа проходит всё за доли секунды.
А дальше случилось то, ради чего стоило восстанавливать весь синий язык. В Kubernetes на THE есть сценарий отключения питания: узел обесточивают, его kubelet прерывается, а управляющий слой должен заметить пропажу узла и перенести поды на другие узлы. Хранилище в THE, как и всё в этой системе, защищено семафором. В версии на красном языке это обычный семафор Дейкстры с операциями P и V, а не REGION, потому что REGION привязан к куску текста программы: блокировка захватывается на входе в этот кусок и освобождается на выходе. А в THE операцию P часто выполняет один процесс, а V другой, и захват с освобождением оказываются в разных местах программы. Поэтому если kubelet прерывался посреди записи в хранилище, семафор оставался захваченным, и весь управляющий слой останавливался. В статье о финалистах я на этом и попался, и на красном и зелёном языках пришлось перенести отключение питания в промежуток между проходами kubelet’а, когда он ничего не держит.
На синем языке семафор хранилища объявлен как REGION. Это по-прежнему обычный семафор с P и V, только у него есть владелец: его можно захватить в одной процедуре и освободить в другой, а если ветка завершилась аварийно, система освободит его сама. Теперь узел можно обесточить в любой момент, даже когда kubelet пишет в хранилище. Ветка kubelet’а получает TERMINATED, как только до неё снова дойдёт очередь, и аварийно завершается, система освобождает её семафор, и управляющий слой работает дальше. Здесь есть одна тонкость. Kubelet перехватывает TERMINATED, чтобы записать в журнал, что пропало питание, и после этого должен снова возбудить исключение. Если этого не сделать, ветка закончится нормально, а при нормальном завершении захваченные семафоры не освобождаются. Данные, которые защищал семафор, при этом могут остаться записанными наполовину, и на это обоснование SofTech отвечало, что их скоро перезапишут свежие показания датчиков. В Kubernetes ту же роль играет следующий проход контроллера, который заново сравнивает желаемое с действительным. Красный язык освобождал блокировку сам только при выходе из блока REGION, а синий язык делает то же для обычного семафора с владельцем, то есть для того, на чём построена THE.
Kubernetes поверх THE на синем языке: kubelet второго узла прерывается, держа семафор хранилища, система освобождает семафор, и управляющий слой переносит поды. Вывод показан с замедлением, на виртуальных часах программа проходит всё за доли секунды.
Тайм-ауты на синем языке
С тайм-аутами всё сложнее. Захват семафора нельзя ограничить по времени, и на синем языке нельзя сказать «подожди элемента, но не дольше тридцати миллисекунд». Ответ нашёлся в той же книге, у рецензентов. Одна из команд решила на всех четырёх языках пример ввода с тайм-аутом, и вот её вариант для синего:
Разбор команды 126-02, пример A 2.8 «ввод с тайм-аутом», решение на синем языке. Внизу страницы рецензенты предупреждают, что делают допущения о том, как в синем языке устроены исключения
REQUEST (# TTY);WRITES ('FUEL FLOW?' CR LF);PAR_BLOCK PATH PATH1 INPUT (## RATE); TERMINATE (PATH2); END PATH PATH1; PATH PATH2 WAIT (30); TERMINATE (PATH1); WRITES ('5 GALLS/SEC ASSUMED' CR LF); RATE := 5; END PATH PATH2;END PAR_BLOCK;RELEASE (# TTY);
Две ветки бегут наперегонки, и та, что успела первой, останавливает вторую. Если оператор не ответил за тридцать секунд, расход топлива принимается равным пяти галлонам в секунду. Мне нравится, что в этом примере уместилась целая эпоха: военный пульт, телетайп и разумная цифра на случай, если никто не ответил. И уже здесь видно слабое место такого приёма: если таймер сработает между вводом и TERMINATE (PATH2), введённое значение затрётся пятёркой.
В Kubernetes на синем языке так устроены все ожидания, и чего это стоит, видно сразу. Параллельный блок нельзя поставить внутрь подпрограммы, поэтому цикл ожидания не спрячешь в процедуру, и его пришлось написать дважды: для семейства контроллеров и для kubelet’ов. Гонка безопасна, только если у ждущей ветки приоритет выше, чем у таймера. Иначе таймер может остановить её в тот момент, когда семафор уже выдал ей элемент, а она ещё не успела его забрать, и элемент останется в очереди, но получить его будет некому. На этом построена ещё одна лабораторная работа. Приоритет спасает здесь только потому, что процессор один и ветка с более высоким приоритетом всегда работает первой. По-хорошему, отмена должна была бы возвращать то, что ветка уже получила, или же участок «взять элемент и отметить, что взял» должен быть непрерываемым. Так сделано в Аде: там задачу нельзя прервать посреди рандеву или защищённой операции, и прерывание откладывается до их конца.
Есть и вторая беда: остановленная ветка не может понять, кто её остановил, соседняя ветка в гонке или пользователь, который выключил узел. Поэтому kubelet в Kubernetes на синем языке узнаёт об отключении питания из записки, которую пользователь оставляет ему, прежде чем обесточить узел.
THE и Kubernetes на жёлтом языке
THE на жёлтом языке построена на мониторах. Семафоры в этом языке только двоичные, со значениями 0 и 1, поэтому семафоры Дейкстры со счётчиком пришлось сделать мониторами из счётчика и двух сигналов, и получился тот же ограниченный буфер, что в статье Хоара о мониторах. Контроллер сегментов тоже стал монитором, и вышло даже проще, чем у Дейкстры: процесс, которому нужен сегмент, сам выполняет всю работу внутри монитора, а очередь на вход в монитор и служит очередью запросов.
Kubernetes поверх THE на жёлтом языке в браузере. Узел 2 теряет питание, его поды переезжают на другие узлы, оператор масштабирует развёртывание до пяти реплик. Вывод показан с замедлением.
Kubernetes поверх THE на жёлтом языке выводит то же, что и версия на красном языке, байт в байт. Хранилище в нём, как и в версии на красном языке, защищено двоичным семафором, чтобы сохранить P и V из THE, а двоичный семафор при аварийном завершении процесса не освобождается. Поэтому и здесь питание отключается только между проходами kubelet’а. С монитором такой беды не случилось бы: если исключение выводит процесс из монитора, монитор освобождается так же, как REGION в красном языке.
Чего языку не хватает, видно по обходным путям, и для тайм-аутов я перепробовал их несколько. В маленькой сравнительной программе тайм-аут устроен как сторожевой процесс, который будит ожидающий процесс, ничего ему не подсовывая: проснувшись, процесс видит, что условие по-прежнему ложно, и сам решает больше не ждать. В Kubernetes поверх THE процесс watch раз в десять миллисекунд будит все контроллеры. А в отдельном Kubernetes я поступил проще и поставил один процесс watch, который раз в двадцать миллисекунд кладёт в каждый затихший поток событий пустое событие-тик. По сути, это тот же фальшивый элемент, который подбрасывает сторожевой процесс в THE на семафорах.
Массива мониторов быть не может, потому что монитор — это модуль, а не значение. Поэтому восемь потоков событий отдельного Kubernetes, по одному на каждого подписчика, — это восемь именованных экземпляров одного шаблона, и нужный выбирается по номеру в операторе SELECT. Запуская процесс, программа не получает ни его имени, ни номера, и чтобы пользователь мог обесточить второй узел, kubelet сам записывает свой идентификатор туда, где пользователь его найдёт. А ещё программа не может закончиться, пока работают её процессы, так что контроллеры, которые крутятся вечно, приходится останавливать вручную: выставлять флаг остановки и посылать ещё один сигнал, чтобы контроллеры, которые спят в мониторе, проснулись, увидели флаг и завершились.
Что показали эти системы
Обе системы работают, и их вывод совпадает с выводом таких же систем на красном и зелёном языках, местами байт в байт. Синий язык оказался самым удобным для THE и самым неудобным для Kubernetes с его тайм-аутами на каждом шагу. С жёлтым языком вышло наоборот: Kubernetes на мониторах получился естественным, но всё, что связано со временем и с именами процессов, пришлось строить вручную. Общий же вывод для обоих такой: язык с одним механизмом синхронизации справляется с задачей, но каждый недостающий механизм приходится заменять отдельным процессом. В статье о финалистах зелёный язык точно так же заменял почтовый ящик задачей-буфером.
Почему эти языки проиграли
В питтсбургскую комиссию, которая сводила разборы, вошли Дэвид Фишер, Дэвид Грис, Брайан Керниган, Джон Рейнольдс, Филип Уэзеролл и Уильям Вульф. Её отчёт датирован 4 апреля 1978 года. Начинает комиссия с того, что все четыре проекта неполны и сделаны в спешке, а вывод у неё получился простой: лучшим рецензенты считали зелёный проект, худшим синий, а между красным и жёлтым почти не видели разницы. Но если читать сами разборы команд, оценки в них расходятся гораздо сильнее. Одни команды ставили жёлтый первым, другие последним. Одна команда писала, что жёлтый спроектирован хуже всех и продолжать его не нужно, другая считала его надёжным выбором для системного программиста и, судя по всему, самым дешёвым в реализации. А ещё одна закончила свой разбор моим любимым советом: лучшее, что может сделать Минобороны, — это попросить красную команду реализовать жёлтый язык. Что ж, теперь жёлтый язык реализован.
Сводка рекомендаций комиссии от 4 апреля 1978 года: продолжить зелёный, отвергнуть синий, продолжить хотя бы один из красного и жёлтого
О синем проекте комиссия высказалась короче всего и предложила его отвергнуть. По её мнению, проект был проработан тщательно и полно, но оказался перегружен сложностью, которая пронизывала его целиком, а простой и ясной модели, обещанной авторами, в нём не видно. Одна из команд признала, что синему проекту повредила сама манера изложения и что это наверняка сказалось на её оценке, а в её сводной таблице синий и жёлтый проекты получили худший балл за то, насколько легко опечатка меняет смысл программы. Восстановление подтвердило обе половины приговора. Библиотека ввода-вывода с драйверами заработала после десятка опечаток и семи нарушений правил языка, а два вида семафоров оказались точнее всего, что было у финалистов. Но и сложность у него настоящая: транслятор синего языка вышел самым большим из четырёх, а обратные косые черты, решётки и двойные восклицательные знаки читаются хуже, чем у любого из соседей.
Жёлтый проект уступил немного. Комиссия написала, что выбор между красным и жёлтым проектами не очевиден, хотя большинство её членов предпочло красный. Но в разделе о самом жёлтом языке она выразилась довольно жёстко: тип и представление смешаны, работающего способа указать на конкретный процесс нет, мониторы ещё не применялись в серьёзных системах, и вообще попытка построить язык на Паскале и его родственнице Модуле не удалась. С моим опытом это совпадает наполовину. Насчёт процессов комиссия права, я и сам споткнулся там же. А вот мониторы на THE и Kubernetes оказались самой удобной частью жёлтого языка, да и к 1978 году Бринч Хансен уже описал операционную систему Solo, написанную на мониторах Concurrent Pascal. Ирония ещё и в том, что красный проект, который лишь немного обошёл жёлтый, вскоре выбросила сама красная команда, и во втором туре она написала язык заново.
Если поставить четыре языка рядом, становится видно, что это четыре ответа на один вопрос: сколько механизмов синхронизации нужно языку. Авторы зелёного языка выбрали рандеву, авторы синего языка семафоры, авторы жёлтого мониторы, и только в красном языке было несколько механизмов сразу. В трёх проектах из четырёх ставка была сделана на один главный механизм, и ни в одном из этих трёх процесс не может сказать, что будет ждать не дольше стольких-то миллисекунд: в зелёном тайм-аут есть только у сервера, в синем остаётся гонка веток, в жёлтом сторожевой процесс или опрос. А в главе об Аде будет видно, что к монитору авторы Ады позже вернулись сами, назвав его защищённым объектом.
Что из этих проектов потом появилось в Аде
Ада 83 была зелёным языком, прошедшим через четыре года правок, и прямого наследия синего и жёлтого проектов в ней нет. Но если положить рядом проекты 1978 года и всю историю Ады вплоть до Ады 2022, получается та же картина, что и с красным языком. Многое из того, что авторы проигравших проектов предложили сразу, в Аду добавляли десятилетиями, под своими названиями и, как правило, не подозревая, что повторяет кого-то из 1978 года. Пройдусь по главному.
Идеи синего и жёлтого проектов в истории Ады: что совпало сразу и что пришло через десятилетия
Что совпало с Адой 83
Первым совпадением стали подтипы. Представления жёлтого языка соответствуют подтипам Ады, но в Аду подтипы пришли из зелёного языка, так что здесь перед нами сходство, а не заимствование.
Совпало и то, как значения хранятся в машине. Синий язык через REP позволял назначить значениям перечисления коды, понятные железу, и Ада делает то же самое в главе 13 стандарта. Синий язык разрешал это только неупорядоченным типам, Ада разрешает любым, но требует, чтобы коды шли по возрастанию. Обе команды понимали, что порядок значений может разойтись с порядком кодов, и обошли эту трудность с разных сторон.
Совпадает и мысль о скобках там, где читатель может ошибиться. Ironman требовал скобок вокруг неассоциативных операций, авторы жёлтого языка выполнили это требование буквально, авторы синего языка от него отказались, а в Steelman его смягчили до пожелания. В Аде от этой мысли осталось немного, но всё же осталось: and и or нельзя смешивать без скобок, и a b c тоже считается ошибкой.
Что Ада получила позже
Первым вернулся монитор. В Аде 95 появились защищённые объекты, и в обосновании Ады 95 среди их предков названы и мониторы. Защищённый объект является монитором, в котором вместо сигналов стоят барьеры, то есть условия на входах, и когда условие становится истинным, тех, кто его ждал, обслуживают раньше новых вызовов. К монитору в Аде вернулись через семнадцать лет после того, как комиссия отвергла жёлтый язык.
Потом пришла явная перегрузка. Слова EXTENDS и REPLACES в жёлтом языке требовали пометить, добавляет ли новое определение имени ещё один смысл или заменяет старый. Похожая по духу идея появилась в Аде 2005 в виде индикаторов overriding и not overriding, правда, для методов, а не для любых имён, и нужны они затем, чтобы опечатка в имени не превращала замену метода в новый метод. В C++11 появился override, в Java аннотация @Override, и везде к этому пришли после ошибок, которые в жёлтом языке были невозможны по синтаксису.
Дольше всего Ада шла к функциям без побочных эффектов и к спискам импорта. Жёлтый язык требовал, чтобы функция не трогала ничего, кроме своих локальных переменных, а синий язык требовал перечислить в заголовке процедуры каждую внешнюю переменную, которую она читает или меняет, вместе с режимом доступа. В Аде 83 не было ни того, ни другого. Пришло это через SPARK, строгое подмножество Ады для программ, корректность которых можно доказать, а в Аде 2022 стало частью самого языка: аспект Global перечисляет внешние объекты подпрограммы вместе с режимом доступа. Это почти дословно список IMPORTS синего языка из примера с балансом.
Сообщать о сбое в параллельной ветке тому, кто её запустил, Ада тоже научилась, но только для вычислений, а не для задач. В Аде 2005 появился обработчик завершения задачи: с его помощью можно узнать, что задача завершилась из-за необработанного исключения, но к тому, кто её запустил, исключение всё равно не передаётся. В Аде 2022 появились параллельные блоки parallel do ... and ... end do. Такой блок дожидается всех своих ветвей, сбой одной ветви отменяет остальные, и исключение передаётся наружу. Это структурная параллельность в современном смысле, даже строже параллельного блока синего языка, но предназначена она для параллельных вычислений, а задачи Ады с их рандеву по-прежнему завершаются при необработанном исключении так же незаметно, как в 1983 году.
Кто из авторов остался работать над Адой
Джон Гуденаф, руководитель синего проекта, после тендера руководил разработкой набора тестов, по которым компиляторы Ады проверяли на соответствие стандарту, а потом возглавлял группу, которая разбирала спорные места самого стандарта. Аду 95, как я рассказывал в статье о финалистах, спроектировала команда Intermetrics, авторы красного языка. Выходит, что из четырёх команд 1978 года за Аду так или иначе отвечали три, и в стороне осталась только жёлтая команда.
Если бы победил синий или жёлтый язык
В статье о финалистах я пробовал представить мир, где в мае 1979 года победил красный язык. Если коротко, Ада с первого дня разделяла бы сообщения и общие данные, обобщения создавались бы без объявлений, а PL/SQL в каждой базе Oracle был бы написан на языке с почтовыми ящиками. В нашем же мире Ада успела повлиять даже на C++: Страуструп, проектируя его, сравнивал свои параметризованные типы и исключения с адовскими. Здесь развилка случается раньше, в апреле 1978 года, когда во второй тур взяли зелёный и красный. Представим, что комиссия решила иначе.
Сначала о том, что не изменилось бы, какой бы язык ни победил. Как и в статье о финалистах, я исхожу из того, что требование писать для Минобороны только на Аде, действовавшее с 1987 по 1997 год, отменили по экономическим причинам: коммерческие разработчики перешли на C и C++, и победа другого языка в 1978 году этого бы не изменила. Так что любой язык, победивший в конкурсе, стал бы языком авионики, железных дорог и космоса и почти наверняка не стал бы языком всего остального. Поэтому дальше речь пойдёт о том, как изменились бы программы для этих отраслей и что из них раньше попало бы в массовые языки.
Мир, в котором победил синий язык
Прежде всего Ада, выросшая из синего языка, вышла бы позже нашей. Компиляторы Ады опаздывали и в нашем мире: первый, прошедший проверку на соответствие стандарту, появился только в 1983 году. А синий язык был самым трудным в реализации из всех четырёх. Выводить экземпляры обобщений из аргументов, проверять импорт по всей цепочке вызовов, считать масштабы чисел с фиксированной точкой — на всё это ушли бы годы работы, и сильнее было бы искушение урезать язык до подмножеств, которые Минобороны запрещало.
Во-вторых, укрепилась бы культура строгой спецификации. Гуденаф и в нашем мире построил набор тестов для компиляторов Ады, а если бы победил синий язык, та же строгость была бы видна в самом языке: каждая процедура в каждом проекте Минобороны объявляла бы, какие данные она использует и какие исключения может возбудить, и компилятор проверял бы это сам.
В-третьих, иначе развивалось бы обобщённое программирование. Александр Степанов, начинавший со Scheme, в конце восьмидесятых сделал вместе с Дэвидом Мюссером библиотеку обобщённых алгоритмов для Ады и только потом перешёл на C++, где ему не хватало ограничений на параметры шаблонов. Концепты он продвигал много лет, пока они не вошли в C++20. В синем языке ограничения на тип были с самого начала, в WHERE T NEEDS, а экземпляры создавались сами, так что при его победе обобщённые алгоритмы с ограничениями на типы могли бы появиться в военном языке уже в середине восьмидесятых.
В-четвёртых, иначе выглядела бы параллельность. В синем языке параллельные ветки запускаются внутри одного блока, блок не завершается, пока не завершатся все ветки, а исключение, которое возникло в ветке и не было в ней обработано, передаётся тому, кто запустил блок. Такая схема стала бы обычной для бортовых программ лет на сорок раньше, чем её ввели Trio и Swift. Вместе с языком в учебники попали бы и блокировки, которые система сама освобождает, если владевшая ими ветка завершилась аварийно. Обмена сообщениями между процессами в синем языке не было, но и в нашем мире военные программы на Аде строились не на сообщениях, а на общих данных и задачах, а языки, в которых процессы общаются одними сообщениями, например Эрланг и Go, появились независимо от Ады. Так что в этом отношении победа синего языка ничего бы не изменила.
И в-пятых, кое-что изменилось бы в самой обыденной работе программистов. PL/SQL в Oracle во многом построен на Аде потому, что Ада была языком Минобороны. Победи синий язык, и процедуры в каждой базе Oracle начинались бы с PROCEDURE P (# X, Y: ?T), а значения перечислений писались бы с обратной косой чертой. Администраторы баз данных, думаю, были бы в восторге.
Мир, в котором победил жёлтый язык
С жёлтым языком история пошла бы по-другому, потому что он был переделанным Паскалем. В 1979 году Паскаль уже преподавали повсюду, Вирт заканчивал Модулу-2, а через несколько лет Turbo Pascal сделает Паскаль языком персональных компьютеров. Мой компилятор жёлтого языка оказался самым маленьким из четырёх, а настоящий строился бы на готовой основе компиляторов Паскаля, так что Ада, выросшая из жёлтого языка, скорее всего, появилась бы раньше нашей. К этому добавилась бы печать Минобороны, и язык учебников, язык персоналок и язык военных систем оказались бы одной семьёй. Школа Вирта и Хоара, которая в нашем мире проиграла C, получила бы промышленного союзника с огромным бюджетом. Победила бы она C? Вряд ли, ведь у C был Unix. Но в восьмидесятые семейства C и Паскаля соперничали бы на равных, и Паскаль не уступал бы C год за годом, как это случилось в нашем мире.
Мониторы Хоара стали бы стандартом уже в 1980 году, причём в варианте Хоара, где процесс, разбуженный сигналом, сразу получает монитор из рук в руки. В нашем мире мониторы пришли в широкую практику через Mesa и Java, с обязательным циклом вокруг wait. Создатели Mesa выбрали свою семантику из практических соображений, и, возможно, создатели Java выбрали бы то же самое и в этом случае. Но поколение программистов, выученное на военных мониторах, знало бы оба варианта и цену каждого. А Аде 95 не понадобились бы защищённые объекты, потому что монитор в языке уже был бы. Вместо них в Аду, выросшую из жёлтого языка, пришлось бы добавлять то, чего не хватило мне: тайм-аут на ожидании, имена процессов и массивы мониторов. Комиссия ещё в 1978 году писала, что в жёлтом языке нет способа указать на процесс, и во втором туре это исправили бы.
Не обошлось бы и без подводных камней. Сравнения, у которых приоритет ниже, чем у AND, и на которых споткнулись сами авторы языка в планировщике SIFT, оставались бы в программах для самолётов, пока их не исправили бы во втором туре или пока такие ошибки не научились бы находить анализаторы кода.
Но интереснее всего в этом случае сложилась бы судьба SIMULATED_TIME. Любой кусок бортовой системы можно было бы обернуть в блок с искусственным временем и прогонять так, чтобы каждый прогон в точности повторял предыдущий. Всех проблем это не решило бы: перебирать разные порядки процессов, как это делают сегодняшние системы детерминированного моделирования, всё равно пришлось бы самому, а отказов железа язык не моделирует. Но ошибки, связанные со временем, можно было бы воспроизводить у себя в лаборатории уже с 1980 года, а не ловить годами у заказчика. В нашем мире к этому пришли только в 2010-х.
И лекция Хоара была бы другой. В 1980 году он получал премию Тьюринга и в лекции «Старое платье императора» рассказал, что с 1975 года консультировал разработчиков Ады, и предупредил, что язык получился слишком сложным, чтобы писать на нём программы, от которых зависят человеческие жизни. А если бы победил жёлтый язык, Ада выросла бы из проекта, авторов которого, если верить рассказам, консультировал сам Хоар.
Четыре варианта истории
Если свести все четыре варианта вместе, получится вот что.
Победитель
Какими стали бы военные программы
Что раньше пришло бы в массовые языки
GREEN, наш мир
рандеву, явные экземпляры обобщений, позже защищённые объекты
исключения и обобщения, повлиявшие на C++
RED
почтовые ящики, блокировки REGION, свои планировщики
разделение сообщений и общих данных, экземпляры обобщений без объявлений
BLUE
строгие типы, семафоры двух видов, параллельный блок
структурная параллельность, ограничения на параметры обобщений, блокировки с владельцем
YELLOW
Паскаль с мониторами и искусственным временем
моделирование с управляемым временем, мониторы Хоара, функции без побочных эффектов
Самое странное в этой таблице то, что почти всё, что в ней перечислено для красного, синего и жёлтого языков, потом всё равно появилось в других языках, только позже, постепенно и в разные годы. Почти ни одна идея проигравших проектов не пропала. Они вернулись под другими именами: защищённые объекты, концепты, структурная параллельность, детерминированное моделирование. Выбирая в 1978 году между проектами, комиссия решала не то, какие идеи хороши, а какие плохи, а то, какие из них войдут в практику уже в 1980-х, а каким придётся ждать 2020-х.
Лабораторные работы и запуск программ
Как и в прошлых частях, мне хотелось, чтобы читатель мог не только прочитать о языке, но и попрактиковаться в нём: изменить программу, нарочно её сломать и посмотреть, как язык на это ответит. К двенадцати упражнениям на красном языке добавились пятнадцать новых: семь на синем языке и восемь на жёлтом. В каждом из них разбирается какая-то особенность, которой нет ни в красном, ни в зелёном языке. Каждая лабораторная работа устроена одинаково: это небольшая программа и несколько заданий к ней разного уровня. На уровне look программу нужно запустить и прочитать, что она выводит. На уровне change в программу вносится определённая правка, и нужно добиться, чтобы она вывела ожидаемый результат. На уровне break в программу нарочно вносится ошибка, и вы видите, как на неё отвечает компилятор или как ведёт себя программа во время работы. А на уровне build нужно дописать собственный кусок кода. Проверяет всё это скрипт check.sh: ему передают номер лабораторной и уровень, он компилирует вашу версию программы, запускает её и сообщает, выполнено ли задание. Время в программах виртуальное, а планировщик детерминированный, поэтому программа на любой машине и при каждом запуске выводит одно и то же, символ в символ, и её вывод легко сверить с эталонным.
Вот что разбирается в лабораторных на синем языке.
-
В
b1литералGREENпринадлежит сразу двум перечислениям, сигналам светофора и цветам, и в каждом стоит на своём месте. Если сравнить две масти карт через<, компилятор откажется, потому что у неупорядоченного типа есть только равенство. -
В
b2одна процедураSWAPменяет местами целые числа, строки и цвета, хотя ни одного её экземпляра никто не объявлял. Здесь же предлагается написать собственную обобщённую функцию, которая выбирает большее из двух значений и требует от типа операцию сравнения. -
В
b3нужно убрать из списка импорта одну процедуру и посмотреть на ошибку: процедура, которая её вызывает, обязана импортировать либо её саму, либо все переменные, с которыми та работает. -
В
b4коды состояния устройства описаны как неупорядоченный тип, и значение читается прямо из регистра. Если вынести это чтение из машинно-зависимой части программы, компилятор его не пропустит. -
В
b5первая ветка аварийно завершается, не освободив семафорREGION, а вторая всё равно доходит до конца, потому что семафор освобождает система. Если объявить этот семафор сигнальным, программа зависнет. А если обработать исключение внутри ветки и не освободить семафор вручную, ветка завершится нормально, семафор останется за ней, и программа тоже зависнет. -
В
b6работает система THE. Если включить в ней доклады оператору о каждой выгрузке страницы на барабан, нижний уровень системы начнёт обращаться к верхнему, и система остановится во взаимной блокировке. Предвидеть это можно было заранее, потому что такой вызов с самого начала был записан в списке импорта. -
В
b7тайм-аут сделан как гонка двух веток, одна из которых ждёт элемент в очереди, а другая отсчитывает время. Если отнять у ожидающей ветки повышенный приоритет, таймер может остановить её, когда она уже получила право на элемент, но ещё не забрала его, и элемент так и останется в очереди.
Лабораторная b7: тайм-аут из разбора 1978 года, гонка двух веток, и . Два элемента получены, третьего не было тридцать миллисекунд
В лабораторных на жёлтом языке разбирается следующее.
-
В
y1выражениеa - b - cбез скобок компилятор не принимает и требует указать, какое вычитание выполняется первым. -
В
y2разбираются параметрыCONST,VARиOUT. Процедура присваивает значение выходному параметру и после этого завершается с исключением, и оказывается, что значение в вызывающую программу не попадает, потому что выходной параметр передаётся только при нормальном возврате. -
В
y3сравниваются упорядоченные и неупорядоченные перечисления: для первых работаютSUCC,LASTи циклFOR, а вторые нельзя сравнивать через<. -
В
y4из одного шаблона стека создаются два модуля, у каждого из которых своё состояние. Если же создать экземпляр шаблона для типа, у которого нет порядка, ошибка обнаружится только при создании экземпляра, хотя находится она в теле шаблона. -
В
y5два процесса ждут сигнала в мониторе с разными рангами, и первым просыпается тот, у кого ранг меньше. Если убратьSEND, программа остановится во взаимной блокировке: сигнал нигде не запоминается, и без него ожидающие процессы никто не разбудит. -
В
y6функция пытается изменить глобальную переменную, и компилятор этого не позволяет, а процедуре, которая возвращает значение, то же самое разрешено. -
В
y7модуль экспортирует переменную только для чтения и тип, устройство которого снаружи не видно, и обе попытки обойти эти запреты кончаются ошибкой компиляции. -
В
y8работает система THE на мониторах, и ломается она тем же способом, что и вb6: нижний уровень начинает обращаться к верхнему.
Задача о читателях и писателях, решённая с помощью монитора Хоара, в браузере: первые два читателя читают одновременно, а третий, который пришёл уже после писателя, ждёт, пока писатель закончит запись. Вывод показан с замедлением.
Чтобы всё это запустить, нужны только компилятор C и make:
git clone https://github.com/tym83/paleocomputingcd paleocomputing/impl/ada-colorsmake # собирает redc, он нужен для THE и Kubernetes на красномmake -C blue fixpoint # собирает bluec из готового C-файла и проверяет неподвижную точкуmake -C yellow fixpoint # то же для yellowcos/run.sh # THE и все варианты Kubernetes на всех четырёх языкахlabs/check.sh b5 look # лабораторная про семафор REGIONlabs/check.sh y1 break # проверить свою правку в лабораторной про минус
Если под рукой есть Cozystack, открытая платформа для построения облака на Kubernetes, ставить ничего не нужно. В каталоге приложений, который я собрал для этой серии, есть среда для языков, и все четыре языка попали туда в одном образе контейнера. Вы указываете образ ada-colors-run, кладёте исходник, и программа выполняется разовым заданием Kubernetes (Job), а её вывод становится логом этого задания. При сборке образа все четыре компилятора заново собираются из сохранённых C-файлов и заодно проверяют, что по-прежнему собирают сами себя байт в байт.
А проще всего открыть страницу в браузере, где всё происходит на самой странице, без сервера. Все четыре транслятора, собранные в WebAssembly из тех же C-файлов, переводят исходник в C, этот C компилирует clang, тоже собранный в WebAssembly, а каждая задача программы выполняется в своём потоке. Среда выполнения там собрана из того же файла, что и в Linux, и работает с теми же виртуальными часами, поэтому в браузере программы выводят то же, что на обычной машине, байт в байт. Это проверяется автоматически: при каждом изменении все примеры прогоняются в Chrome без окна, и их вывод сравнивается с эталоном. При первом запуске страница скачивает компилятор C, около двадцати мегабайт, а дальше браузер хранит его у себя.
Спецификация 1978 года, запуск 2026-го: первая ветка аварийно завершилась, не освободив семафор , и вторая сразу его получила
Что я забираю с собой
В конце каждой части серии я отвечаю себе на вопрос, что из найденного стоит забрать в сегодняшнюю инфраструктуру.
Во-первых, блокировка должна знать, что её владелец аварийно завершился. Авторы синего языка в 1978 году ради этого и развели семафоры на два вида, и обоснование SofTech в двух абзацах объясняет то, чему в распределённых системах учатся на авариях. Освобождать блокировку аварийно завершившегося владельца должна система, а не его обработчик исключений, и освобождать нужно только блокировки, но не сигнальные семафоры. Поучительна и разница с сегодняшним днём. Внутри одной машины система видит, что ветка завершилась, а в сети этого не видно: узел перестаёт отвечать, и нельзя сказать, остановился он или связь пропала. Поэтому в Kubernetes блокировки устроены как аренды: узел или лидер регулярно продлевает запись, а если перестал продлевать, его блокировка считается свободной. Прежний владелец при этом может продолжать работать и не знать, что блокировка уже перешла к другому, поэтому к ней добавляют номер, который растёт с каждым новым владельцем, и тот, кто принимает запись, отвергает записи со старым номером. Авторы синего языка решили эту задачу для одной машины, где аварийное завершение видно. В сети задача труднее, но первый шаг в ней тот же.
Во-вторых, у параллельной работы должен быть хозяин. Если контроллер запускает горутину, завершения которой никто не ждёт и ошибки которой никто не читает, это то, от чего параллельный блок синего языка защищал ещё в 1978 году.
В-третьих, сначала нужно сделать время управляемым, а уже потом искать ошибки. Вся эта серия построена на виртуальных часах, и жёлтый язык, как выяснилось, предлагал то же самое в синтаксисе.
В-четвёртых, каждый недостающий механизм приходится заменять отдельным процессом. Синий язык, в котором нет тайм-аутов, обходится гонкой веток, жёлтый — сторожевым процессом, а зелёный, в котором нет почтовых ящиков, — задачей-буфером. Когда в платформе не хватает примитива, его всё равно кто-нибудь построит, только каждый по-своему и с ошибками, и это хороший довод в пользу того, чтобы на примитивах не экономить.
И в-пятых, изучать проигравшие проекты полезно, чтобы заранее знать, какие идеи вернутся, и не платить за них второй раз.
Что дальше? Теперь работают все четыре проекта конкурса, но от первого тура осталось ещё кое-что: REDL, первая редакция красного языка с мониторами и событиями, которую красная команда выбросила. А отчёты рецензентов финала 1979 года, по которым выбирали между красным и зелёным языками, до сих пор существуют только на микрофишах. Если у вас есть к ним доступ, напишите мне.
Исходники, тесты, лабораторные работы и все заметки лежат в репозитории github.com/tym83/paleocomputing в каталоге impl/ada-colors. Если обнаружите, что я неправильно понял спецификации 1978 года, напишите, мне правда интересно.
Предыдущие части серии о палеокомпьютинге:
-
Часть 1. Процессор Вирта, Проект Оберон, новая архитектура в QEMU и KubeVirt и запуск в Cozystack и Kubernetes
-
Часть 2. Kubernetes на Обероне, радио Вирта вместо сети и кластер в браузере
-
Часть 3. Две Ады: RED и GREEN, финалисты конкурса 1979 года
Источник: habr.com