Стандартная библиотека и связывание модулей

Каталог flang/stdlib/ — пять файлов, 1314 строк на самом flang. Читать их полезно не столько ради функций, сколько ради комментариев: каждый модуль открывается объяснением, какое ограничение языка он обходит и какой ценой.

Итого 76 функций, 69 из них тотальные, 151 пример — все проходят; числа сняты прогоном flang check и flang test по каждому файлу, а не переписаны из документации.

Три границы, видные в комментариях

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

Списки — в отсутствие полиморфизма, которого больше нет. lists.flang — это по-прежнему библиотека для список числа. Но шапка модуля теперь начинается так, и её стоит привести дословно:

Здесь стояло «функции не являются значениями» — это БОЛЬШЕ НЕ ПРАВДА про язык: функция стала значением и печатается во все восемь целей. […] Правда — про РЕПОЗИТОРИЙ, и она уже: ни stdlib, ни examples не вправе использовать ни функции-значения, ни параметрические типы, пока их не понимает flang/self/parser.flang.

Разница между «язык не умеет» и «библиотека не вправе» кажется буквоедством, а на деле это разница между тупиком и очередью. Разбор — ниже, в отдельном разделе.

Отдельная мелочь, из которой вырос порядок функций в файле: приписать элемент в начало встроенной формой нельзя, добавить … к … дописывает в конец. Поэтому «Приписать в начало» — первая функция модуля, «без неё не выражаются ни обращение, ни срез, ни сортировка». Реализована она свёрткой:

тотальная функция «Приписать в начало»
  принимает первый: число, элементы: список числа
  возвращает список числа
  свёртка элементы начиная с [первый] как акк и эл → добавить эл к акк

Числа — в отсутствие убывания по мере. Шапка numbers.flang:

Здесь проходит вторая большая граница тотальности. Список убывает: у него есть хвост, и анализ это видит. Число не убывает ни во что: «n минус 1» — это результат арифметики […] Поэтому всё, что считается «пока n больше нуля», — обычная функция. Это не изъян конкретных функций ниже, а свойство языка.

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

Обход есть у тех функций, которые удаётся выразить через «разделить … по …» и свёртку по заранее известному списку букв: такие остаются тотальными. Приём стоит запомнить — он даёт тотальные «Заменить», «Считать символ», «Позиция подстроки» и даже смену регистра.

Суммы типов вместо исключений

optional.flang и result.flang существуют по одной причине: в языке нет исключений, а функция «найди первый подходящий элемент» обязана как-то сообщить, что элемента нет. Возвращать ноль — значит смешивать «нашли ноль» и «не нашли».

тип «Число или ничто»
  вариант «Есть число» содержит значение: число
  вариант «Нет числа»

Но самое поучительное в этих файлах — не типы, а объяснение, почему у половины функций нет примеров:

Значение примера разбирается parseLiteralValue, а тот сворачивает конструктор варианта в запись из его полей и теряет имя варианта. Такой аргумент типы отвергают, а интерпретатор не сопоставляет ни с одним образцом. Поэтому рядом с каждой такой функцией стоит её «скалярная» пара, у которой примеры есть, и она проверяет ту же логику.

То есть каждая функция, принимающая или возвращающая вариант, помечена комментарием // Без примера: … и сопровождается обёрткой со скалярной сигнатурой. Это ограничение реализации, а не дизайна, и оно наверняка исчезнет — но пока формирует структуру двух модулей из пяти.

Связывание модулей

До недавнего времени импорт в flang разбирался, но не действовал. В flang/examples/leetcode/index.json это записано как недостача:

Заголовок «модуль … использует …» разбирается, но связывания между файлами нет: каждое решение переписывает нужные ему «Приписать в начало» и «Соединить списки» заново. Стандартной библиотекой нельзя воспользоваться из решения.

На момент нашей проверки это уже неверно. Модуль flang/src/link.mjs существует и работает. Файл flang/examples/import-check.flang — двенадцать строк, и он этим пользуется:

модуль «Проба импорта»
  использует «Списки» из "../stdlib/lists.flang"

тотальная функция «Сумма пробы»
  принимает элементы: список числа
  возвращает число
  «Сумма» от элементы
  пример «Четыре числа»
    дано элементы равно [1, 2, 3, 40]
    ожидается результат равен 46

$ node flang/bin/flang.mjs test flang/examples/import-check.flang --pretty
{ "valid": true, "total": 46, "passed": 46, "failed": 0, … }

Сорок шесть примеров — один свой и сорок пять пришедших из lists.flang вместе с функциями. Это прямое следствие того, как устроено связывание.

Решения LeetCode при этом действительно дублируют вспомогательные функции — «Приписать в начало» встречается почти в каждом файле. Их писали до появления link.mjs, и переписывать не стали.

Импорт — это слияние, а не пространство имён

Решение объяснено в шапке link.mjs:

Импорт — это слияние объявлений, а не пространство имён. Языку без экспоненциалов и с уникальными именами вариантов пространства имён дали бы больше сложности, чем пользы: пришлось бы решать, как выглядит квалифицированное имя по-русски («Списки.Сумма»? «Сумма из Списки»?), и тащить это решение во все восемь бэкендов.

(«Восемь бэкендов» в цитате — это цели tools/ftsc, проектного компилятора FTS-моделей. У самого flang их теперь тоже восемь, но список другой: js вместо typescript. Разбор путаницы — в главе «flang и FTS».)

Аргумент про русский язык здесь не декоративный. Квалифицированное имя — это конструкция поверхности, а поверхность у языка русская и английская одновременно; форма, естественная в одной, будет уродливой в другой.

Цена решения названа тут же: конфликт имён становится ошибкой, а не перекрытием. Проверяем — объявляем в своём модуле функцию «Длина», которая уже есть в «Списках»:

{"code":"FLANG_DUPLICATE_NAME",
 "message":"функция «Длина» объявлена в двух модулях:
            …/flang/stdlib/lists.flang и …/probes/conflict.flang"}

Сообщение называет оба файла. Это тоже сделано специально: в link.mjs заведены отдельные карты происхождения имён, «чтобы конфликт назвал оба файла, а не только тот, который загрузился вторым».

Обоснование строгости: «молчаливое перекрытие функции из другого файла — источник ошибок, которые невозможно объяснить, глядя на один файл».

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

Выборочный импорт: только

Отсюда и вторая форма заголовка — перечислить, что именно берём:

модуль «Выборочный импорт»
  использует «Списки» из "../stdlib/lists.flang" только «Длина», «Сумма»

Разница видна не по описанию, а по счётчику примеров. Полный импорт «Списков» приводил с собой сорок пять чужих примеров вдобавок к своему; выборочный приводит только те, что объявлены у взятых функций:

$ node flang/bin/flang.mjs test выборочно.flang
{"valid":true,"total":5,"passed":5,"failed":0, …}

Не взятое остаётся невидимым — и невидимым честно, с обычной диагностикой имени:

$ … «Сумма» от элементы     // при импорте «только «Длина»»
{"code":"FLANG_UNKNOWN_NAME","message":"неизвестная функция «Сумма»",
 "span":{"line":7,"column":3}}

Форма эта не украшение. В каталоге flang/self/, где компилятор языка написан на самом языке (глава «Ядро FTS на flang»), почти каждый заголовок пользуется только: печать в C берёт из core/json.flang девять имён — «Значение», «Экранировать», «Печать строки» и ещё шесть, — а парсер шестнадцать. Взять модуль целиком там нельзя: файлы большие, имена в них общие, и слияние столкнуло бы половину.

Тот же приём решает и задачу переиспользования. Печать AST в JSON в self/ не написана заново — она импортируется из core/json.flang, где уже доказана побайтово. Формулировка контракта прямая: «Если формы расходятся, расширяется она, а не пишется вторая».

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

Настоящая библиотека написана — и лежит не в flang/stdlib/

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

Дублирование в stdlib посчитано, а не оценено на глаз. Девять функций отличаются друг от друга ровно одним подставленным предикатом, сравнением или операцией — «Все не меньше» и «Любой не меньше», «Минимум» и «Максимум», «Сумма» и «Произведение», «Вставить по порядку» и «Сортировать», «Сжать суммами». Ещё 55 функций из 202 в stdlib, examples/leetcode и examples/rosetta — побайтовые копии друг друга.

Замена этому написана целиком и проверена целиком: 36 функций, все тотальные, 55 примеров. Свёртка, отображение, фильтр, поиск, сортировка и композиция принимают функцию аргументом — то, ради чего библиотека ждала функций первого класса. Печатается во все восемь целей, C собирается под -Werror -pedantic, сверена с интерпретатором.

Положить её в flang/stdlib/ нельзя, и это измерено, а не выведено из общего соображения. Тот же модуль, положенный туда, роняет пять тестов: три в self-bootstrap и два в self-parser, с диагностикой flang₁ «FLANG_PARSE: не разобрана конструкция: ожидался тип».

Причина в устройстве проверки, и она стоит того, чтобы её понять. Корпус сверки самоприменения собирается по маске каталога:

self-bootstrap.test.mjs   — globSync("flang/stdlib/*.flang")
self-parser, self-types,
self-totality, self-lexer — каталог flang/stdlib целиком

То есть первый же файл с формой, которой self/parser.flang не знает, роняет неподвижную точку. Не потому, что форма плоха, а потому, что она новая.

Поэтому модуль живёт в тесте — flang/test/stdlib-hof.test.mjs, — а его будущее место названо в комментарии: flang/stdlib/higher-order.flang.

Вывод, который автор языка формулирует сам и который стоит унести из главы: «печатается» не значит «можно писать библиотеку». Печать и разбор самоприменением — разные контракты, и второй строже. Пока компилятор написан на самом языке, каждая новая форма стоит двух работ вместо одной: сначала в эталоне, потом в self/. Это цена самоприменения, и предъявляется она не там, где её ждёшь, — не в сложности компилятора, а в том, что нельзя написать в библиотеке.

Чего в stdlib нет

Ни ввода-вывода, ни времени, ни случайности, ни сети — и вот здесь оговорка изменилась. Раньше её можно было закончить словами «и не появится: язык чистый». Теперь у языка есть ввод-вывод, и он не сделал язык грязным: поручение — обычное значение, исполняет его хозяин (глава «Синтаксис по факту»). В stdlib этого всё равно нет, но по другой причине: словарь поручений вводит сам язык, а не библиотека.

Нет словаря и множества, поэтому подсчёт вхождений везде квадратичный. Нет структур с индексным доступом: «Элемент по номеру» написан рекурсией и стоит O(n). Персистентные структуры — вектор, словарь, очередь, множество, у каждой объявленный моноид — расписаны в контракте flang/cat/SPEC.md как план, и планом остаются.

Дальше — глава «Интерпретатор», про то, что всё это исполняет.