flang компилятор доказывает, что программа не зациклится 0.6.2 GitHub English

К README · Указатель документации

Известные ограничения

Названы прямо, потому что на проект с необозначенными границами нельзя опереться. Та же граница проведена в docs/overview.ru.md; полные списки — в flang/SPEC.md §10 и в разделах «Долги» контрактов.

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

Три слова — не украшение прозы: ровно ими отвечает отчёт о доказательствах (flang check --proof) и служба для помощника, и эта страница одно вместо другого не употребляет.

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

Язык.

Категорная поверхность. Морфизмы, композиция, цепочки, единицы, функторы, бифункторы, изоморфизмы, моноиды, группы и монады реализованы; у монады есть форма связывания в монаде. Отношения множеств сказаны двумя словами: вложение — подобъект (стрелка, которая ничего не склеивает), пересечение — расслоенное произведение над объемлющим множеством. Устройство обоих доказывается сличением объявлений, инъективность вложения проверяется на значениях автора и при склейке предъявляет контрпример, а непустота общей части подтверждается свидетелем; универсальность общей части остаётся допущением, и следствий из неё компилятор не выводит (flang/cat/SETS.md). Объединение словом НЕ стало: ко-произведение в языке уже есть — это тип … вариант … с исчерпывающим разбором. Стрелка вправе нести закон: даёт называет функцию, закон — примеры, и нарушенный закон валит flang test, называя и стрелку, и закон. Обратимость изоморфизма проверяется там, где обе стрелки названы через даёт, и остаётся допущением автора там, где хотя бы одна — нет. Предусловие (требует) реализовано, и снимает его вызывающий, как в Dafny: внутри тела это известный факт, от которого рассуждает ядро; у каждого вызова — обязательство, отвергаемое по имени (FLANG_PRECONDITION_CALL); на границе программы (--args, примеры) оно вычисляется, потому что доказывать там не из чего. В тело функции проверка не печатается ни у одной цели, и цена названа байтами: программа без единого требует печатается байт в байт как прежде, программа с одним растёт ровно на дверь — 334 байта у Python, 349 у Java, 369 у Elixir, 387 у C#, 452 у Rust, 462 у Go, 477 у C и 1 654 у JavaScript (flang/SPEC.md, «Предусловия функции»). Не реализованы естественные преобразования — они описаны в flang/cat/SPEC.md. Имена категорий в объявлении функтора — пометка для читателя, а не проверяемое утверждение. Монадой сегодня не объявить список и всё рекурсивное, включая ввод-вывод: отображение эндофунктора печатается на месте, поэтому параметр обязан стоять в поле целиком (flang/cat/MONAD.md).

Конкурентность. Планировщик в рантайме C работает в двух режимах. Проверочный — один поток и чередование по семени: он даёт побайтово тот же журнал доставок, что свидетель, и ради этого он и нужен. Второй — пул потоков, он включается полем workers в запросе и измерен прямо: на программе с параллельной работой пул быстрее в 1,85–4,80 раза уже при одном пробеге на передачу, а на программе БЕЗ параллелизма медленнее в 6,7 раза и жжёт при этом пятнадцать ядер (замеры — docs/scheduler-benchmark.md). Процессы печатают ТРИ цели — C, Elixir и JavaScript; остальные пять (Go, Rust, Python, Java, C#) программу с процесс печатать ОТКАЗЫВАЮТСЯ кодом FLANG_CONC_UNSUPPORTED, а не печатают её половину. породить заводит экземпляры объявленных видов на ходу у свидетеля и у цели C; планировщики JavaScript и Elixir отвечают на это действие названной ошибкой. Имя порождённому даёт родитель, потому что описанное действие не может вернуть ничего; адресат сообщения по-прежнему обязан быть литералом, поэтому говорить с порождённым можно только тем, с чем он родился; распределённости нет. Сетка семян проверяет конечный набор чередований — это проверенное утверждение, а не доказанное, и свободы от взаимной блокировки она не даёт. Свободной машины при замерах не было ни разу (нагрузка 125–734 при 256 ядрах, на замерах пула 60–1250), поэтому все числа времени в них — верхние оценки; числа, от нагрузки не зависящие (витки, редукции, байты), названы отдельно и повторяются от прогона к прогону.