FTS & flang · открытый исходный код · BSD-2
Справа — работающий файл: двадцать строк без единой скобки, из которых состоит почти всё, что пишут на языке в первый день. Вот что делает каждая конструкция.
категория «Продажи»
Предметная область и первая строка файла. Всё остальное лежит внутри неё отступом: скобок и точек с запятой в языке нет.
объект Покупка
Данные и их типы. Встроенных типов пять — строка, число, дата, деньги, признак; иногда является делает поле необязательным.
утилита «Рассчитать скидку»
Расчёт. Вход, тип результата и стартовое значение обязательны: пропустите начинает с — компилятор откажет с FTS_UTILITY_INITIAL, а не подставит ноль сам.
правило «Большая покупка»
Условие и одно действие. Срабатывают все правила, чьи условия истинны, и складываются: это не цепочка if / else if.
свойство «Скидка ограничена»
Постусловие: проверяется после всех правил. Нарушено — остановка с FTS_UTILITY_PROPERTY, а не тихая подрезка до «безопасного» числа.
пример «Двадцать тысяч»
Тест внутри спецификации: те же две строки читает человек и выполняет fts test — отсюда подпись под кодом.
категория «Продажи»
объект Покупка
сумма является деньгами
утилита «Рассчитать скидку»
принимает Покупка
возвращает деньги
начинает с 0
правило «Большая покупка»
если сумма не меньше 10000
то добавить 10 процентов от поля сумма
свойство «Скидка ограничена»
результат не больше 15000
пример «Двадцать тысяч»
дано сумма равна 20000
ожидается результат равен 2000
category "Sales"
object Purchase
amount is money
utility "Calculate discount"
accepts Purchase
returns money
starts with 0
rule "Large purchase"
if amount is at least 10000
then add 10 percent of field amount
property "Discount is capped"
result is at most 15000
example "Twenty thousand purchase"
given amount equals 20000
expected result equals 2000
Как читать код на этой странице девять видов лексем, один словарь цветов на все языки
утилитаобъявлениепринимаетключевое слово«Рассчитать скидку»предметное имяденьгитипне меньшесравнениедалитерал"постоянный"строка20000число// пояснениекомментарийРаскраска FTS снята настоящим лексером языка при сборке (npm run fts:highlight), напечатанный JavaScript, C, Go, Rust, Python и файлы проектов красит Chroma, встроенный в Hugo. Ни то, ни другое не ходит в сеть и не грузит библиотек в браузер: страница остаётся раскрашенной с выключенным JavaScript и в оффлайн-поставке.
От правила к модели
Четыре ступени на одном и том же примере. Первые три — куски файла из первого экрана, четвёртая — из модели «Отгрузка заказа», её можно открыть в песочнице на шаге 3.
правило «Большая покупка»
если сумма не меньше 10000
то добавить 10 процентов от поля сумма
Сравнений в языке ровно шесть: равен, не равен, больше, меньше, не больше, не меньше. Седьмое даст FTS_UTILITY_COMPARISON с номером строки. Правил может быть сколько угодно, и работают они не как if / else if: выполняются все, чьи условия истинны, и складываются.
утилита «Рассчитать скидку»
принимает Покупка
возвращает деньги
начинает с 0
Три строки обязательны — вход, тип результата и стартовое значение. Ноль в начинает с написал автор модели, а не подставил рантайм: без строки компилятор откажет с FTS_UTILITY_INITIAL. С ней fts run считает утилиту на JSON, а flang emit печатает её в пять языков.
свойство «Скидка ограничена»
результат не больше 15000
пример «Двадцать тысяч»
дано сумма равна 20000
ожидается результат равен 2000
Свойство — постусловие: проверяется после всех правил, и нарушенное останавливает выполнение с FTS_UTILITY_PROPERTY, а не подрезает результат до «безопасного» числа втихую. Пример — тест, лежащий внутри спецификации: те же строки читает человек и выполняет fts test. Разойтись документации и коду здесь нечем — файл один.
морфизм «Готовый заказ можно отгрузить»
если «Готов к отгрузке»
то «Отгрузить заказ разрешено»
теорема «Заказ ЗК-7781 можно отгрузить»
дано Заказ имеет «готов к отгрузке» равное да
в данных заказы найти где номер равен «ЗК-7781»
по морфизму «Готовый заказ можно отгрузить»
следовательно «Отгрузить заказ разрешено»
Объекты категории — типы: структура Заказ и именованные состояния. Морфизм — стрелка A → B с именем и объявленным законом; он не выполняет переход, а утверждает его допустимость. Композиция разрешена ровно тогда, когда кодомен предыдущей стрелки совпал с доменом следующей, а равенство типов номинальное — по имени. Строка в данных — самая важная: она превращает рассуждение в проверяемое утверждение, называя, где искать свидетельство.
тотальная компилятор принял доказательство структурного убывания: она не может зациклиться. Анализ консервативен и отвергает часть действительно завершающихся программ — FLANG_NOT_TOTAL.Одна модель · пять языков
Печатает flang — полный язык, выросший из FTS. Любая модель FTS остаётся его валидной программой, а напечатанный модуль самодостаточен: рантайм едет в тот же каталог. Ниже одно правило и его свойство в пяти целевых языках.
правило «Очень крупная покупка»
если сумма больше 100000
то добавить 15000
свойство «Скидка ограничена»
результат не больше 15000
let $t6
if ($cond($gt($field(vhod, "сумма"), 100000))) {
$t6 = $add(rezultat2, 15000)
} else {
$t6 = rezultat2
}
const rezultat3 = $t6
// постусловие «Скидка ограничена»
if (!$post($lte(rezultat3, 15000), "Скидка ограничена", "Рассчитать скидку")) {
$fail("FTS_UTILITY_PROPERTY", "нарушено свойство «Скидка ограничена» утилиты «Рассчитать скидку»")
}
return rezultat3
} fl_value fl_t26 = fl_nothing();
FL_TRY(fl_field_get(ctx, vhod, "сумма", &fl_t26, error));
fl_value fl_t27 = fl_nothing();
FL_TRY(fl_gt(ctx, fl_t26, fl_number(100000.0), &fl_t27, error));
bool fl_t28 = false;
FL_TRY(fl_cond(ctx, fl_t27, &fl_t28, error));
fl_value fl_t29 = fl_nothing();
if (fl_t28) {
fl_value fl_t30 = fl_nothing();
FL_TRY(fl_add(ctx, rezultat2, fl_number(15000.0), &fl_t30, error));
fl_t29 = fl_t30;
} else {
fl_t29 = rezultat2;
}
const fl_value rezultat3 = fl_t29; /* пусть «результат3» */
(void)rezultat3;
const fl_value fl_t31 = rezultat3;
fl_value fl_t32 = fl_nothing();
FL_TRY(fl_lte(ctx, fl_t31, fl_number(15000.0), &fl_t32, error));
/* постусловие «Скидка ограничена» */
bool fl_t33 = false;
FL_TRY(fl_post(ctx, fl_t32, "Скидка ограничена", "Рассчитать скидку", &fl_t33, error));
if (!fl_t33) {
return fl_fail(ctx, error, "FTS_UTILITY_PROPERTY", "%s", "нарушено свойство «Скидка ограничена» утилиты «Рассчитать скидку»");
}
*result = fl_t31;
return FL_OK;
} t46, e47 := rt.FieldGet(ctx, vhod, "сумма")
if e47 != nil {
return rt.Value{}, e47
}
t48, e49 := rt.Gt(ctx, t46, rt.Number(100000.0))
if e49 != nil {
return rt.Value{}, e49
}
t50, e51 := rt.Cond(ctx, t48)
if e51 != nil {
return rt.Value{}, e51
}
var t52 rt.Value
if t50 {
t53, e54 := rt.Add(ctx, rezultat2, rt.Number(15000.0))
if e54 != nil {
return rt.Value{}, e54
}
t52 = t53
} else {
t52 = rezultat2
}
// пусть «результат3»
rezultat3 := t52
_ = rezultat3
t55 := rezultat3
t56, e57 := rt.Lte(ctx, t55, rt.Number(15000.0))
if e57 != nil {
return rt.Value{}, e57
}
// постусловие «Скидка ограничена»
t58, e59 := rt.Post(ctx, t56, "Скидка ограничена", "Рассчитать скидку")
if e59 != nil {
return rt.Value{}, e59
}
if !t58 {
return rt.Value{}, rt.Fail("FTS_UTILITY_PROPERTY", "%s", "нарушено свойство «Скидка ограничена» утилиты «Рассчитать скидку»")
}
return t55, nil
} let t26 = rt::field_get(ctx, vhod.clone(), "сумма")?;
let t27 = rt::gt(ctx, t26, rt::number(100000.0))?;
let t28 = rt::cond(ctx, t27)?;
let t29 = if t28 {
let t30 = rt::add(ctx, rezultat2.clone(), rt::number(15000.0))?;
t30
} else {
rezultat2.clone()
};
// пусть «результат3»
let rezultat3 = t29;
let t31 = rezultat3.clone();
// постусловие «Скидка ограничена»
let t32 = rt::lte(ctx, t31.clone(), rt::number(15000.0))?;
let t33 = rt::post(ctx, t32, "Скидка ограничена", "Рассчитать скидку")?;
if !t33 {
return Err(rt::fail("FTS_UTILITY_PROPERTY", "нарушено свойство «Скидка ограничена» утилиты «Рассчитать скидку»".to_string()));
}
Ok(t31)
} if rt.cond(ctx, rt.gt(ctx, rt.field_get(ctx, vhod, "сумма"), rt.number(100000.0))):
_t6 = rt.add(ctx, rezultat2, rt.number(15000.0))
else:
_t6 = rezultat2
# пусть «результат3»
rezultat3 = _t6
_t7 = rezultat3
# постусловие «Скидка ограничена»
if not rt.post(ctx, rt.lte(ctx, _t7, rt.number(15000.0)), "Скидка ограничена", "Рассчитать скидку"):
raise rt.fail("FTS_UTILITY_PROPERTY", "нарушено свойство «Скидка ограничена» утилиты «Рассчитать скидку»")
return _t7FTS_UTILITY_PROPERTY, а не комментарий рядом.3000 — столько же, сколько песочница на шаге 3.cc -Werror -pedantic; в зависимостях только libc и libm.Быстрый старт
Пакета в npm пока нет, поэтому CLI собирается из исходников. У ядра нет рантайм-зависимостей, а flang запускается прямо из клона, без сборки. Чтобы просто посмотреть, ставить ничего не нужно: песочница ниже считает тем же компилятором прямо во вкладке.
git clone https://github.com/digitable-lol/flang.git
cd flang
npm ci
npm run build# типы, ссылки, композиция
node dist/src/cli.js check examples/utilities/discount.fts --pretty
# примеры, записанные внутри правила
node dist/src/cli.js test examples/utilities/discount.fts --pretty
# напечатать в код: c | go | rust | python | js
node flang/bin/flang.mjs emit examples/utilities/discount.fts \
--target go --out ./out-goКаждая команда печатает JSON в stdout, диагностику в stderr и возвращает ненулевой код на провале — один контракт для CI, редактора и агента.
Живая песочница
Тот же компилятор @digitable-lol/fts@0.4.0, что и в Node.js: всё считается локально, без единого запроса на сервер. Вкладки справа — это команды CLI: «Проверка» — fts check, «Примеры» — fts test, «Выполнить» — fts run, «Доказательство» — fts prove.
Что песочница не делает. prove — символьный вывод: он показывает, что цепочка морфизмов типизируется, но данные при этом не проверяет и даёт тот же ответ с контекстом и без него. Проверенный сертификат выпускает fts certify и пересчитывает fts verify — они считают дайджесты через node:crypto и живут на серверной стороне. Чем символьный вывод отличается от проверенного.
Компилятор загрузится, когда секция появится на экране.
Компилятор загружается…
На чём это уже написано
Алгоритмическая задача не даёт предметной опоры — это проверка языка на чужой территории. Файлы читаются из репозитория языка при сборке страницы, числа сняты запуском flang check и flang test.
пример — часть исходника.запись и вариант и почему их не приходится объявлять дважды.списки
6/6 примеров
3/3 функций тотальны
65 строк
Вместо словаря «значение → номер» — вложенный проход: для каждой головы ищем дополнение в хвосте. O(n²) как прямая цена отсутствия хеш-таблиц.
модуль «Две суммы»
// LeetCode 1. Two Sum.
// Дан список чисел и цель. Найти два разных элемента, дающих в сумме цель,
// и вернуть их номера. Номера — с нуля, как в условии задачи; язык нумерует
// строки с единицы, поэтому пересчёт делается один раз, в конце.
//
// Тотальная. Хеш-таблиц в языке нет, поэтому вместо словаря «значение → номер»
// работает вложенный проход: для каждой головы ищем дополнение в хвосте.
// Это O(n²) вместо O(n) — прямая цена отсутствия ассоциативного массива.
тотальная функция «Позиция значения»
принимает элементы: список числа, нужное: число
возвращает число
пример «Найдено вторым»
дано элементы равно [5, 7]
дано нужное равно 7
ожидается 2
пример «Не найдено»
дано элементы равно [5, 7]
дано нужное равно 9
ожидается 0
разбор элементов
случай пусто
то 0
случай голова и хвост
если голова равен нужное
то 1
иначе
пусть дальше равно «Позиция значения» от хвост и нужное
если дальше равен 0 то 0 иначе дальше плюс 1
тотальная функция «Поиск пары с позиции»
принимает элементы: список числа, цель: число, позиция: число
возвращает список числа
пример «Пара в начале»
дано элементы равно [2, 7, 11]
дано цель равно 9
дано позиция равно 0
ожидается [0, 1]
разбор элементов
случай пусто
то пустой список
случай голова и хвост
пусть смещение равно «Позиция значения» от хвост и (цель минус голова)
если смещение больше 0
то [позиция, позиция плюс смещение]
иначе «Поиск пары с позиции» от хвост и цель и (позиция плюс 1)
тотальная функция «Две суммы»
принимает элементы: список числа, цель: число
возвращает список числа
пример «Пример 1 из условия»
дано элементы равно [2, 7, 11, 15]
дано цель равно 9
ожидается [0, 1]
пример «Пример 2 из условия»
дано элементы равно [3, 2, 4]
дано цель равно 6
ожидается [1, 2]
пример «Пример 3 из условия»
дано элементы равно [3, 3]
дано цель равно 6
ожидается [0, 1]
«Поиск пары с позиции» от элементы и цель и 0
деревья
3/3 примеров
4/4 функций тотальны
61 строк
Поле варианта — часть значения, поэтому рекурсия по поддеревьям доказывается сразу. Дерево в примерах строится из списка: вариант в «дано» не записать.
модуль «Глубина дерева»
// LeetCode 104. Maximum Depth of Binary Tree.
// Найти длину самого длинного пути от корня до листа.
//
// Тотальная. Дерево — сумма типов, а поле варианта анализ завершаемости
// считает частью значения, поэтому рекурсия по поддеревьям доказывается
// сразу и без ухищрений. Деревья язык принимает лучше, чем строки и числа.
//
// Дерево в примерах строится из списка: значение варианта нельзя записать
// в «дано» (парсер теряет имя конструктора), поэтому вход задаётся списком,
// а «Дерево из списка» превращает его в дерево поиска.
тип «Дерево»
вариант Лист
вариант Узел содержит значение: число, левое: «Дерево», правое: «Дерево»
тотальная функция «Вставить в дерево»
принимает дерево: «Дерево», число: число
возвращает «Дерево»
разбор дерева
случай Лист
то Узел с значение равным число и левое равным вариант Лист и правое равным вариант Лист
случай вариант Узел с значение как зн и левое как л и правое как п
если число меньше зн
то
пусть новое равно «Вставить в дерево» от л и число
Узел с значение равным зн и левое равным новое и правое равным п
иначе
пусть новое равно «Вставить в дерево» от п и число
Узел с значение равным зн и левое равным л и правое равным новое
тотальная функция «Дерево из списка»
принимает элементы: список числа
возвращает «Дерево»
свёртка элементы начиная с вариант Лист как акк и эл → «Вставить в дерево» от акк и эл
тотальная функция «Глубина»
принимает дерево: «Дерево»
возвращает число
разбор дерева
случай Лист
то 0
случай вариант Узел с левое как л и правое как п
пусть слева равно «Глубина» от л
пусть справа равно «Глубина» от п
1 плюс (если слева больше справа то слева иначе справа)
тотальная функция «Глубина из списка»
принимает элементы: список числа
возвращает число
пример «Сбалансированное дерево»
дано элементы равно [2, 1, 3]
ожидается 2
пример «Цепочка»
дано элементы равно [1, 2, 3, 4]
ожидается 4
пример «Пустое дерево»
дано элементы равно пустой список
ожидается 0
«Глубина» от («Дерево из списка» от элементы)
поиск
3/3 примеров
1/1 функций тотальны
27 строк
Одна свёртка: счёт элементов меньше цели. O(n) вместо требуемого O(log n) — двоичный поиск в тотальном классе требует приёма с топливом.
модуль «Место вставки»
// LeetCode 35. Search Insert Position.
// В отсортированном списке найти номер цели, а если её нет — номер, куда её
// следовало бы вставить. Номера с нуля, как в условии.
//
// Тотальная. Условие требует O(log n), здесь же один линейный проход:
// двоичный поиск в тотальном классе требует особого приёма (см. 704), а
// линейная свёртка доказывается сама. Ответ тот же, сложность хуже —
// и это честная цена, а не недосмотр.
тотальная функция «Место вставки»
принимает элементы: список числа, цель: число
возвращает число
пример «Пример 1 из условия»
дано элементы равно [1, 3, 5, 6]
дано цель равно 5
ожидается 2
пример «Пример 2 из условия»
дано элементы равно [1, 3, 5, 6]
дано цель равно 2
ожидается 1
пример «Пример 3 из условия»
дано элементы равно [1, 3, 5, 6]
дано цель равно 7
ожидается 4
свёртка элементы начиная с 0 как акк и эл → если эл меньше цель то акк плюс 1 иначе акк
числа
6/6 примеров
0/2 функций тотальны
42 строк
Линейный вариант с двумя накопителями. Нетотальна ровно из-за счётчика: убывания по числу анализ не знает.
модуль «Фибоначчи»
// LeetCode 509. Fibonacci Number.
// F(0) = 0, F(1) = 1, дальше сумма двух предыдущих.
//
// Обычная. Прямое определение F(n) = F(n−1) + F(n−2) не проходит анализ
// завершаемости по той же причине, что и всё остальное на числах: убывания
// по числовому аргументу он не знает. Здесь взят линейный вариант с двумя
// накопителями — он и работает быстрее, и делает нетотальность заметной:
// единственное, что мешает доказать конец, — счётчик.
функция «Фибоначчи шагом»
принимает осталось: число, предыдущее: число, текущее: число
возвращает число
пример «Ноль шагов»
дано осталось равно 0
дано предыдущее равно 7
дано текущее равно 9
ожидается 7
если осталось не больше 0
то предыдущее
иначе «Фибоначчи шагом» от (осталось минус 1) и текущее и (предыдущее плюс текущее)
функция «Фибоначчи»
принимает н: число
возвращает число
пример «Пример 1 из условия»
дано н равно 2
ожидается 1
пример «Пример 2 из условия»
дано н равно 3
ожидается 2
пример «Пример 3 из условия»
дано н равно 4
ожидается 3
пример «Нулевое»
дано н равно 0
ожидается 0
пример «Тридцатое»
дано н равно 30
ожидается 832040
«Фибоначчи шагом» от н и 0 и 1
Раскройте карточку — под ней полный файл из flang/examples/leetcode. Связывания модулей в языке нет, поэтому решение самодостаточно и запускается как есть. Раскраска этих 22 файлов лежит отдельным файлом и приезжает при раскрытии карточки: код в разметке есть всегда, цвета — по требованию.
списки
4/4 примеров
2/2 функций тотальны
32 строк
Свёртка с проверкой «содержит». Изменения на месте нет: значения flang неизменяемы, возвращается новый список.
модуль «Удалить повторы»
// LeetCode 26. Remove Duplicates from Sorted Array.
// Из отсортированного списка убрать повторы. В условии просят изменить массив
// на месте и вернуть число уникальных; изменяемых массивов в языке нет и быть
// не может — значения flang неизменяемы, — поэтому возвращается новый список,
// а «число уникальных» вынесено отдельной функцией.
//
// Тотальная: свёртка по списку, рекурсии нет вовсе.
тотальная функция «Без повторов»
принимает элементы: список числа
возвращает список числа
пример «Пример 1 из условия»
дано элементы равно [1, 1, 2]
ожидается [1, 2]
пример «Пример 2 из условия»
дано элементы равно [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
ожидается [0, 1, 2, 3, 4]
свёртка элементы начиная с пустой список как акк и эл
если акк содержит эл то акк иначе добавить эл к акк
тотальная функция «Сколько уникальных»
принимает элементы: список числа
возвращает число
пример «Пример 1 из условия»
дано элементы равно [1, 1, 2]
ожидается 2
пример «Пустой список»
дано элементы равно пустой список
ожидается 0
длина («Без повторов» от элементы)
списки
6/6 примеров
3/3 функций тотальны
57 строк
Перенос идёт справа налево, свёртка — слева направо, поэтому список обращается дважды. Обращение выражено свёрткой: встроенного «в начало» нет.
модуль «Прибавить единицу»
// LeetCode 66. Plus One.
// Список цифр — большое число. Прибавить к нему единицу.
//
// Тотальная. Перенос идёт справа налево, а свёртка идёт слева направо,
// поэтому список сначала обращается, потом сворачивается, потом обращается
// обратно. Обращение выражается свёрткой, а не встроенной формой: приписать
// элемент в начало списка встроенным «добавить … к …» нельзя — оно
// дописывает в конец.
объект «Перенос»
перенос является числом
цифры является список числа
тотальная функция «Приписать в начало»
принимает первый: число, элементы: список числа
возвращает список числа
пример «В непустой»
дано первый равно 1
дано элементы равно [2]
ожидается [1, 2]
свёртка элементы начиная с [первый] как акк и эл → добавить эл к акк
тотальная функция «Обратить»
принимает элементы: список числа
возвращает список числа
пример «Три элемента»
дано элементы равно [1, 2, 3]
ожидается [3, 2, 1]
свёртка элементы начиная с пустой список как акк и эл → «Приписать в начало» от эл и акк
тотальная функция «Прибавить единицу»
принимает цифры: список числа
возвращает список числа
пример «Пример 1 из условия»
дано цифры равно [1, 2, 3]
ожидается [1, 2, 4]
пример «Пример 2 из условия»
дано цифры равно [4, 3, 2, 1]
ожидается [4, 3, 2, 2]
пример «Пример 3 из условия»
дано цифры равно [9]
ожидается [1, 0]
пример «Сплошные девятки»
дано цифры равно [9, 9, 9]
ожидается [1, 0, 0, 0]
пусть начальное равно запись «Перенос» с перенос равным 1 и цифры равным пустой список
пусть итог равно свёртка («Обратить» от цифры) начиная с начальное как акк и цифра
пусть сумма равно цифра плюс акк.перенос
пусть новая равно сумма остаток от 10
пусть дальше равно если сумма не меньше 10 то 1 иначе 0
запись «Перенос» с перенос равным дальше и цифры равным (добавить новая к акк.цифры)
пусть результат равно «Обратить» от итог.цифры
если итог.перенос равен 1
то «Приписать в начало» от 1 и результат
иначе результат
списки
6/6 примеров
3/3 функций тотальны
59 строк
Не классическое слияние (оно убывает то по одному списку, то по другому и получает FLANG_NOT_TOTAL), а вставка в свёртке: O(n·m), зато доказуемо конечно.
модуль «Слияние отсортированных»
// LeetCode 88. Merge Sorted Array.
// Слить два отсортированных списка в один отсортированный.
//
// Тотальная — но не тем алгоритмом, каким её пишут обычно. Классическое
// слияние рекурсирует то по первому списку, то по второму, и анализ
// завершаемости такой цикл отвергает: он требует ОДНУ позицию аргумента,
// убывающую на каждом рекурсивном вызове (totality.mjs, контрпример в шапке
// файла). Слияние даёт две разные позиции и получает FLANG_NOT_TOTAL.
//
// Поэтому здесь слияние вставками: «Вставить по порядку» рекурсирует ровно
// по хвосту второго аргумента, а внешний проход — свёртка. Результат тот же,
// сложность O(n·m) вместо O(n+m).
тотальная функция «Приписать в начало»
принимает первый: число, элементы: список числа
возвращает список числа
пример «В непустой»
дано первый равно 1
дано элементы равно [2]
ожидается [1, 2]
свёртка элементы начиная с [первый] как акк и эл → добавить эл к акк
тотальная функция «Вставить по порядку»
принимает значение: число, элементы: список числа
возвращает список числа
пример «В середину»
дано значение равно 2
дано элементы равно [1, 3]
ожидается [1, 2, 3]
пример «В пустой»
дано значение равно 2
дано элементы равно пустой список
ожидается [2]
разбор элементов
случай пусто
то [значение]
случай голова и хвост
если значение не больше голова
то «Приписать в начало» от значение и элементы
иначе «Приписать в начало» от голова и («Вставить по порядку» от значение и хвост)
тотальная функция «Слить отсортированные»
принимает первый: список числа, второй: список числа
возвращает список числа
пример «Пример 1 из условия»
дано первый равно [1, 2, 3]
дано второй равно [2, 5, 6]
ожидается [1, 2, 2, 3, 5, 6]
пример «Пример 2 из условия»
дано первый равно [1]
дано второй равно пустой список
ожидается [1]
пример «Пример 3 из условия»
дано первый равно пустой список
дано второй равно [1]
ожидается [1]
свёртка второй начиная с первый как акк и эл → «Вставить по порядку» от эл и акк
списки
4/4 примеров
2/2 функций тотальны
36 строк
Побитового исключающего ИЛИ в языке нет вовсе, поэтому подсчёт вхождений: O(n²) вместо O(n).
модуль «Одиночное число»
// LeetCode 136. Single Number.
// В списке каждое число встречается дважды, кроме одного. Найти его.
//
// Тотальная. Канонического решения «сложить всё исключающим ИЛИ» здесь нет:
// побитовых операций в языке нет вообще (SPEC, раздел 4 перечисляет только
// арифметику и сравнения). Поэтому — подсчёт вхождений, O(n²) вместо O(n).
тотальная функция «Считать вхождения»
принимает элементы: список числа, значение: число
возвращает число
пример «Два вхождения»
дано элементы равно [4, 1, 4]
дано значение равно 4
ожидается 2
свёртка элементы начиная с 0 как акк и эл → если эл равен значение то акк плюс 1 иначе акк
тотальная функция «Одиночное число»
принимает элементы: список числа
возвращает число
пример «Пример 1 из условия»
дано элементы равно [2, 2, 1]
ожидается 1
пример «Пример 2 из условия»
дано элементы равно [4, 1, 2, 1, 2]
ожидается 4
пример «Пример 3 из условия»
дано элементы равно [1]
ожидается 1
пусть одиночные равно отфильтровать элементы где эл → («Считать вхождения» от элементы и эл) равен 1
разбор одиночные
случай пусто
то 0
случай голова и хвост
голова
списки
3/3 примеров
2/2 функций тотальны
34 строк
Прямой подсчёт вхождений и фильтр. Бойер — Мур без изменяемых счётчиков всё равно свёлся бы к свёртке с записью.
модуль «Мажоритарный элемент»
// LeetCode 169. Majority Element.
// Найти элемент, встречающийся более чем в половине позиций списка.
//
// Тотальная. Алгоритм Бойера — Мура здесь не нужен: без изменяемых счётчиков
// он всё равно свёлся бы к свёртке с записью-состоянием, а прямой подсчёт
// вхождений короче и очевидно верен. Цена — O(n²).
тотальная функция «Считать вхождения»
принимает элементы: список числа, значение: число
возвращает число
пример «Три тройки»
дано элементы равно [3, 3, 3, 1]
дано значение равно 3
ожидается 3
свёртка элементы начиная с 0 как акк и эл → если эл равен значение то акк плюс 1 иначе акк
тотальная функция «Мажоритарный элемент»
принимает элементы: список числа
возвращает число
пример «Пример 1 из условия»
дано элементы равно [3, 2, 3]
ожидается 3
пример «Пример 2 из условия»
дано элементы равно [2, 2, 1, 1, 1, 2, 2]
ожидается 2
пусть половина равно (длина элементы) делить на 2
пусть частые равно отфильтровать элементы где эл → («Считать вхождения» от элементы и эл) больше половина
разбор частые
случай пусто
то 0
случай голова и хвост
голова
списки
3/3 примеров
1/1 функций тотальны
26 строк
Рекурсия по хвосту плюс «хвост содержит голову». Множеств нет, отсюда O(n²).
модуль «Есть повторы»
// LeetCode 217. Contains Duplicate.
// Есть ли в списке хотя бы одно значение, встречающееся дважды.
//
// Тотальная: рекурсия строго по хвосту списка. Множества в языке нет,
// поэтому проверка «голова встречается дальше» — линейный поиск,
// и всё решение получается O(n²).
тотальная функция «Есть повторы»
принимает элементы: список числа
возвращает признак
пример «Пример 1 из условия»
дано элементы равно [1, 2, 3, 1]
ожидается да
пример «Пример 2 из условия»
дано элементы равно [1, 2, 3, 4]
ожидается нет
пример «Пример 3 из условия»
дано элементы равно [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
ожидается да
разбор элементов
случай пусто
то нет
случай голова и хвост
если хвост содержит голова то да иначе «Есть повторы» от хвоста
списки
3/3 примеров
2/2 функций тотальны
30 строк
Два фильтра и склейка, без рекурсии. «На месте» не выражается: значения неизменяемы.
модуль «Сдвинуть нули»
// LeetCode 283. Move Zeroes.
// Перенести все нули в конец, сохранив порядок остальных.
//
// Тотальная и без единой рекурсии: два фильтра и склейка. В условии просят
// работать «на месте», но изменяемых массивов в языке нет — возвращается
// новый список того же содержания.
тотальная функция «Соединить списки»
принимает первый: список числа, второй: список числа
возвращает список числа
пример «Склейка»
дано первый равно [1]
дано второй равно [0, 0]
ожидается [1, 0, 0]
свёртка второй начиная с первый как акк и эл → добавить эл к акк
тотальная функция «Сдвинуть нули»
принимает элементы: список числа
возвращает список числа
пример «Пример 1 из условия»
дано элементы равно [0, 1, 0, 3, 12]
ожидается [1, 3, 12, 0, 0]
пример «Пример 2 из условия»
дано элементы равно [0]
ожидается [0]
пусть ненулевые равно отфильтровать элементы где эл → эл не равен 0
пусть нули равно отфильтровать элементы где эл → эл равен 0
«Соединить списки» от ненулевые и нули
списки
5/5 примеров
3/3 функций тотальны
41 строк
Условие даёт массив символов — то есть список, а список разбирается структурно. Та же операция над строкой тотальной быть не может.
модуль «Обратить строку»
// LeetCode 344. Reverse String.
// Условие даёт массив символов и просит обратить его на месте. Массив
// символов — это список строки, и здесь это удача: список flang разбирается
// структурно, а строка нет. Поэтому задача остаётся тотальной, тогда как
// та же операция над строкой (модуль stdlib/strings.flang) тотальной быть
// не может — по строке нельзя рекурсировать с доказательством убывания.
//
// Изменения на месте нет и не будет: значения flang неизменяемы.
тотальная функция «Приписать строку в начало»
принимает первая: строка, элементы: список строки
возвращает список строки
пример «В непустой»
дано первая равно "а"
дано элементы равно ["б"]
ожидается ["а", "б"]
свёртка элементы начиная с [первая] как акк и эл → добавить эл к акк
тотальная функция «Обратить символы»
принимает символы: список строки
возвращает список строки
пример «Пример 1 из условия»
дано символы равно ["h", "e", "l", "l", "o"]
ожидается ["o", "l", "l", "e", "h"]
пример «Пример 2 из условия»
дано символы равно ["H", "a", "n", "n", "a", "h"]
ожидается ["h", "a", "n", "n", "a", "H"]
пример «Пустой список»
дано символы равно пустой список
ожидается пустой список
свёртка символы начиная с пустой список как акк и буква → «Приписать строку в начало» от буква и акк
тотальная функция «Строка из символов»
принимает символы: список строки
возвращает строка
пример «Склейка»
дано символы равно ["o", "l", "l", "e", "h"]
ожидается "olleh"
свёртка символы начиная с "" как акк и буква → соединить акк с буква
списки
3/3 примеров
2/2 функций тотальны
29 строк
Уникальные из первого, фильтр по вхождению во второй. Множеств нет, уникальность строится вручную.
модуль «Пересечение списков»
// LeetCode 349. Intersection of Two Arrays.
// Вернуть уникальные значения, встречающиеся в обоих списках.
//
// Тотальная: два прохода свёрткой и фильтром, рекурсии нет.
// Множеств в языке нет, «уникальность» строится вручную через «содержит».
тотальная функция «Уникальные»
принимает элементы: список числа
возвращает список числа
пример «С повторами»
дано элементы равно [1, 1, 2]
ожидается [1, 2]
свёртка элементы начиная с пустой список как акк и эл
если акк содержит эл то акк иначе добавить эл к акк
тотальная функция «Пересечение»
принимает первый: список числа, второй: список числа
возвращает список числа
пример «Пример 1 из условия»
дано первый равно [1, 2, 2, 1]
дано второй равно [2, 2]
ожидается [2]
пример «Пример 2 из условия»
дано первый равно [4, 9, 5]
дано второй равно [9, 4, 9, 8, 4]
ожидается [4, 9]
отфильтровать («Уникальные» от первый) где эл → второй содержит эл
строки
9/9 примеров
2/4 функций тотальны
94 строк
Свёртка с записью-состоянием (сумма и предыдущая цифра). Нетотальна только из-за разложения строки в список символов.
модуль «Римские числа»
// LeetCode 13. Roman to Integer.
// Перевести римскую запись в число.
//
// Обычная, не тотальная — и виновата только строка. Сам разбор («если
// предыдущая цифра меньше текущей, вычесть её дважды») выражается свёрткой
// с записью-состоянием и тотален; но чтобы получить символы строки, её надо
// обойти по одному, а убывание «строка стала короче на символ» анализ
// завершаемости не признаёт: часть значения — это хвост списка, голова,
// поле записи или поле варианта, и ничего больше.
//
// Была бы встроенная форма «символы строки», задача стала бы тотальной
// целиком.
объект «Разбор римского»
сумма является числом
предыдущее является числом
тотальная функция «Приписать строку в начало»
принимает первая: строка, элементы: список строки
возвращает список строки
пример «В непустой»
дано первая равно "I"
дано элементы равно ["V"]
ожидается ["I", "V"]
свёртка элементы начиная с [первая] как акк и эл → добавить эл к акк
тотальная функция «Значение цифры»
принимает буква: строка
возвращает число
пример «Единица»
дано буква равно "I"
ожидается 1
пример «Тысяча»
дано буква равно "M"
ожидается 1000
пример «Не римская цифра»
дано буква равно "щ"
ожидается 0
если буква равен "I"
то 1
иначе
если буква равен "V"
то 5
иначе
если буква равен "X"
то 10
иначе
если буква равен "L"
то 50
иначе
если буква равен "C"
то 100
иначе
если буква равен "D"
то 500
иначе
если буква равен "M" то 1000 иначе 0
функция «Символы с позиции»
принимает текст: строка, позиция: число
возвращает список строки
пример «С последнего символа»
дано текст равно "IV"
дано позиция равно 2
ожидается ["V"]
если позиция больше (длина текст)
то пустой список
иначе
пусть буква равно подстрока текст с позиция по позиция
«Приписать строку в начало» от буква и («Символы с позиции» от текст и (позиция плюс 1))
функция «Римское в число»
принимает текст: строка
возвращает число
пример «Пример 1 из условия»
дано текст равно "III"
ожидается 3
пример «Пример 2 из условия»
дано текст равно "LVIII"
ожидается 58
пример «Пример 3 из условия»
дано текст равно "MCMXCIV"
ожидается 1994
пример «Вычитание»
дано текст равно "IV"
ожидается 4
пусть начальное равно запись «Разбор римского» с сумма равным 0 и предыдущее равным 0
пусть итог равно свёртка («Символы с позиции» от текст и 1) начиная с начальное как акк и буква
пусть значение равно «Значение цифры» от буква
пусть поправка равно если акк.предыдущее меньше значение то (2 умножить на акк.предыдущее) иначе 0
запись «Разбор римского» с сумма равным (акк.сумма плюс значение минус поправка) и предыдущее равным значение
итог.сумма
строки
7/7 примеров
0/3 функций тотальны
60 строк
Свёртка по словам поверх посимвольного сравнения двух слов. Сравнение идёт рекурсией по номеру позиции — её анализ убывания не принимает.
модуль «Общий префикс»
// LeetCode 14. Longest Common Prefix.
// Найти наибольший общий начальный кусок для списка слов.
//
// Обычная. Свёртка по списку слов тотальна, а вот сравнение двух слов идёт
// по позициям — рекурсия по числу, которую анализ завершаемости не
// принимает: «позиция плюс 1» не является частью значения «позиция».
// Ни один известный приём здесь не спасает: топливо (см. задачу 704) можно
// было бы взять из списка слов, но длина слова с длиной списка не связана.
функция «Общий префикс до позиции»
принимает первое: строка, второе: строка, позиция: число
возвращает строка
пример «Совпало два символа»
дано первое равно "flower"
дано второе равно "flow"
дано позиция равно 1
ожидается "flow"
пусть предел равно если (длина первое) меньше (длина второе) то (длина первое) иначе (длина второе)
если позиция больше предел
то подстрока первое с 1 по предел
иначе
если (подстрока первое с позиция по позиция) равен (подстрока второе с позиция по позиция)
то «Общий префикс до позиции» от первое и второе и (позиция плюс 1)
иначе подстрока первое с 1 по (позиция минус 1)
функция «Общий префикс двух»
принимает первое: строка, второе: строка
возвращает строка
пример «Общее начало»
дано первое равно "flower"
дано второе равно "flight"
ожидается "fl"
пример «Ничего общего»
дано первое равно "dog"
дано второе равно "racecar"
ожидается ""
«Общий префикс до позиции» от первое и второе и 1
функция «Наибольший общий префикс»
принимает слова: список строки
возвращает строка
пример «Пример 1 из условия»
дано слова равно ["flower", "flow", "flight"]
ожидается "fl"
пример «Пример 2 из условия»
дано слова равно ["dog", "racecar", "car"]
ожидается ""
пример «Одно слово»
дано слова равно ["abc"]
ожидается "abc"
пример «Пустой список»
дано слова равно пустой список
ожидается ""
разбор слова
случай пусто
то ""
случай голова и хвост
свёртка хвост начиная с голова как акк и слово → «Общий префикс двух» от акк и слово
строки
12/12 примеров
3/5 функций тотальны
99 строк
Стек живёт строкой в накопителе свёртки, поломка запоминается префиксом «!». Списочная версия тотальна, строковая — нет.
модуль «Правильные скобки»
// LeetCode 20. Valid Parentheses.
// Проверить, что скобки трёх видов закрываются в правильном порядке.
//
// Две функции нарочно. «Скобки в списке» принимает список символов и
// тотальна: стек живёт в накопителе свёртки (обычной строкой — стек строк
// потребовал бы отдельного типа), а свёртка конечна по построению.
// «Скобки в строке» принимает строку, как в условии, и тотальной быть не
// может: чтобы получить символы, строку надо обойти, а убывание строки
// анализ завершаемости не признаёт — «пусто» и «голова и хвост» работают
// только со списком.
//
// Прерывать свёртку нельзя, поэтому ошибка запоминается в самом стеке:
// строка, начинающаяся с «!», означает «уже сломано».
тотальная функция «Приписать строку в начало»
принимает первая: строка, элементы: список строки
возвращает список строки
пример «В непустой»
дано первая равно "а"
дано элементы равно ["б"]
ожидается ["а", "б"]
свёртка элементы начиная с [первая] как акк и эл → добавить эл к акк
тотальная функция «Парная открывающая»
принимает закрывающая: строка
возвращает строка
пример «Круглая»
дано закрывающая равно ")"
ожидается "("
пример «Квадратная»
дано закрывающая равно "]"
ожидается "["
если закрывающая равен ")"
то "("
иначе
если закрывающая равен "]" то "[" иначе "{"
тотальная функция «Скобки в списке»
принимает символы: список строки
возвращает признак
пример «Пример 1 из условия»
дано символы равно ["(", ")"]
ожидается да
пример «Пример 2 из условия»
дано символы равно ["(", ")", "[", "]", "{", "}"]
ожидается да
пример «Пример 3 из условия»
дано символы равно ["(", "]"]
ожидается нет
пример «Незакрытая скобка»
дано символы равно ["(", "["]
ожидается нет
пусть стек равно свёртка символы начиная с "" как акк и буква
если акк начинается с "!"
то акк
иначе
если "([{" содержит буква
то соединить акк с буква
иначе
если (длина акк) равен 0
то "!"
иначе
пусть верх равно подстрока акк с (длина акк) по (длина акк)
если верх равен («Парная открывающая» от буква)
то подстрока акк с 1 по ((длина акк) минус 1)
иначе "!"
стек равен ""
функция «Символы с позиции»
принимает текст: строка, позиция: число
возвращает список строки
пример «С последнего символа»
дано текст равно "()"
дано позиция равно 2
ожидается [")"]
если позиция больше (длина текст)
то пустой список
иначе
пусть буква равно подстрока текст с позиция по позиция
«Приписать строку в начало» от буква и («Символы с позиции» от текст и (позиция плюс 1))
функция «Скобки в строке»
принимает текст: строка
возвращает признак
пример «Пример 1 из условия»
дано текст равно "()"
ожидается да
пример «Пример 2 из условия»
дано текст равно "()[]{}"
ожидается да
пример «Пример 3 из условия»
дано текст равно "(]"
ожидается нет
пример «Вложенные скобки»
дано текст равно "{[()]}"
ожидается да
«Скобки в списке» от («Символы с позиции» от текст и 1)
строки
6/6 примеров
5/5 функций тотальны
70 строк
Подпись слова — свёртка по алфавиту с подсчётом через «разделить»; словарь заменён списком записей «Группа» с линейным поиском.
модуль «Группировка анаграмм»
// LeetCode 49. Group Anagrams.
// Разложить слова по группам: в одной группе — слова из одних и тех же букв.
//
// Тотальная. Каноническое решение — словарь «подпись → список слов», а
// ассоциативных массивов в языке нет. Замена: список записей «Группа» и
// линейный поиск по ключу. Подпись слова тоже строится без обхода символов —
// свёрткой по алфавиту с подсчётом через «разделить» (тот же приём, что в
// задаче 242). Порядок групп — порядок первого появления.
//
// Цена отсутствия словаря: O(слов × групп × 26) вместо O(суммарной длины).
объект «Группа»
ключ является строкой
слова является список строки
тотальная функция «Счёт буквы»
принимает текст: строка, буква: строка
возвращает число
пример «Две буквы a»
дано текст равно "abac"
дано буква равно "a"
ожидается 2
(длина (разделить текст по буква)) минус 1
тотальная функция «Подпись»
принимает слово: строка
возвращает строка
пример «Анаграммы дают одну подпись»
дано слово равно "eat"
ожидается "1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,"
пример «Другое слово — другая подпись»
дано слово равно "bat"
ожидается "1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,"
свёртка ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"] начиная с "" как акк и буква
соединить (соединить акк с (к строке («Счёт буквы» от слово и буква))) с ","
тотальная функция «Есть группа»
принимает группы: список «Группа», ключ: строка
возвращает признак
свёртка группы начиная с нет как акк и группа
если акк равен да то да иначе группа.ключ равен ключ
тотальная функция «Добавить слово»
принимает группы: список «Группа», ключ: строка, слово: строка
возвращает список «Группа»
если «Есть группа» от группы и ключ
то
отобразить группы как группа
если группа.ключ равен ключ
то запись «Группа» с ключ равным ключ и слова равным (добавить слово к группа.слова)
иначе группа
иначе добавить (запись «Группа» с ключ равным ключ и слова равным [слово]) к группы
тотальная функция «Группировать анаграммы»
принимает слова: список строки
возвращает список список строки
пример «Пример 1 из условия»
дано слова равно ["eat", "tea", "tan", "ate", "nat", "bat"]
ожидается [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
пример «Пример 2 из условия»
дано слова равно [""]
ожидается [[""]]
пример «Пример 3 из условия»
дано слова равно ["a"]
ожидается [["a"]]
пусть группы равно свёртка слова начиная с пустой список как акк и слово
«Добавить слово» от акк и («Подпись» от слово) и слово
отобразить группы как группа → группа.слова
строки
12/12 примеров
3/7 функций тотальны
98 строк
Нижний регистр — таблицей из двух алфавитов: встроенной формы «код символа» нет. Нетотальна из-за обхода символов; кириллица решением не покрыта.
модуль «Палиндром»
// LeetCode 125. Valid Palindrome.
// Строка считается палиндромом, если после выбрасывания всего, кроме букв и
// цифр, и приведения к нижнему регистру она читается одинаково в обе стороны.
//
// Обычная. Причина та же, что у остальных строковых задач: чтобы пройти по
// символам, нужна рекурсия по строке, а её анализ завершаемости не признаёт.
// Заметно и второе ограничение: нижний регистр приходится делать таблицей
// из двух алфавитов — встроенной формы «код символа» в языке нет, поэтому
// связать «A» и «a» иначе нечем. Кириллица этим решением не покрыта.
тотальная функция «Приписать строку в начало»
принимает первая: строка, элементы: список строки
возвращает список строки
пример «В непустой»
дано первая равно "a"
дано элементы равно ["b"]
ожидается ["a", "b"]
свёртка элементы начиная с [первая] как акк и эл → добавить эл к акк
тотальная функция «Позиция подстроки»
принимает текст: строка, часть: строка
возвращает число
пример «В середине»
дано текст равно "abcd"
дано часть равно "c"
ожидается 3
пример «Нет вхождения»
дано текст равно "abc"
дано часть равно "z"
ожидается 0
если текст содержит часть
то (длина (голова (разделить текст по часть))) плюс 1
иначе 0
тотальная функция «Значащий символ»
принимает буква: строка
возвращает строка
пример «Заглавная становится строчной»
дано буква равно "P"
ожидается "p"
пример «Цифра остаётся»
дано буква равно "7"
ожидается "7"
пример «Знак препинания выбрасывается»
дано буква равно ","
ожидается ""
пусть позиция равно «Позиция подстроки» от "ABCDEFGHIJKLMNOPQRSTUVWXYZ" и буква
если позиция больше 0
то подстрока "abcdefghijklmnopqrstuvwxyz" с позиция по позиция
иначе
если "abcdefghijklmnopqrstuvwxyz0123456789" содержит буква то буква иначе ""
функция «Символы с позиции»
принимает текст: строка, позиция: число
возвращает список строки
пример «С последнего символа»
дано текст равно "ab"
дано позиция равно 2
ожидается ["b"]
если позиция больше (длина текст)
то пустой список
иначе
пусть буква равно подстрока текст с позиция по позиция
«Приписать строку в начало» от буква и («Символы с позиции» от текст и (позиция плюс 1))
функция «Очистить»
принимает текст: строка
возвращает строка
пример «Знаки и регистр»
дано текст равно "A man, a plan"
ожидается "amanaplan"
свёртка («Символы с позиции» от текст и 1) начиная с "" как акк и буква
соединить акк с («Значащий символ» от буква)
функция «Обратить строку»
принимает текст: строка
возвращает строка
пример «Слово»
дано текст равно "abc"
ожидается "cba"
свёртка («Символы с позиции» от текст и 1) начиная с "" как акк и буква → соединить буква с акк
функция «Палиндром»
принимает текст: строка
возвращает признак
пример «Пример 1 из условия»
дано текст равно "A man, a plan, a canal: Panama"
ожидается да
пример «Пример 2 из условия»
дано текст равно "race a car"
ожидается нет
пример «Пример 3 из условия»
дано текст равно " "
ожидается да
пусть чистое равно «Очистить» от текст
чистое равен («Обратить строку» от чистое)
строки
5/5 примеров
2/2 функций тотальны
47 строк
Тотальная задача про строки: счёт буквы = число частей «разделить» минус один, перебор идёт по литеральному алфавиту из 26 букв, а не по символам слова.
модуль «Анаграмма»
// LeetCode 242. Valid Anagram.
// Проверить, что второе слово — перестановка первого. По условию буквы
// только строчные латинские.
//
// Тотальная — и это неожиданно, потому что задача про строки. Приём:
// считать буквы не обходом строки, а встроенной «разделить». Число вхождений
// буквы равно числу частей минус один, а перебирать надо не символы слова,
// а заранее известный алфавит из 26 букв — конечный список, записанный
// литералом. Свёртка по литеральному списку тотальна всегда.
тотальная функция «Счёт буквы»
принимает текст: строка, буква: строка
возвращает число
пример «Две буквы a»
дано текст равно "abac"
дано буква равно "a"
ожидается 2
пример «Буквы нет»
дано текст равно "bbb"
дано буква равно "a"
ожидается 0
(длина (разделить текст по буква)) минус 1
тотальная функция «Анаграмма»
принимает первое: строка, второе: строка
возвращает признак
пример «Пример 1 из условия»
дано первое равно "anagram"
дано второе равно "nagaram"
ожидается да
пример «Пример 2 из условия»
дано первое равно "rat"
дано второе равно "car"
ожидается нет
пример «Разная длина»
дано первое равно "a"
дано второе равно "ab"
ожидается нет
если (длина первое) не равен (длина второе)
то нет
иначе
свёртка ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"] начиная с да как акк и буква
если акк равен нет
то нет
иначе («Счёт буквы» от первое и буква) равен («Счёт буквы» от второе и буква)
динамика
4/4 примеров
1/1 функций тотальны
41 строк
Кадане: состояние из двух чисел укладывается в запись, запись — в накопитель свёртки. Единственная динамика, которая ложится на язык без сопротивления.
модуль «Максимальная подпоследовательность»
// LeetCode 53. Maximum Subarray.
// Найти наибольшую сумму непрерывного куска списка (алгоритм Кадане).
//
// Тотальная. Это самая «динамическая» из задач, которые язык принимает без
// сопротивления: состояние Кадане — два числа, а два числа складываются в
// запись, и запись отлично живёт накопителем свёртки. Настоящая динамика
// с таблицей (Coin Change, Edit Distance) так не переносится — там нужен
// массив с произвольным доступом по индексу, которого в языке нет.
объект «Состояние Кадане»
текущая является числом
лучшая является числом
тотальная функция «Наибольшая сумма куска»
принимает элементы: список числа
возвращает число
пример «Пример 1 из условия»
дано элементы равно [-2, 1, -3, 4, -1, 2, 1, -5, 4]
ожидается 6
пример «Пример 2 из условия»
дано элементы равно [1]
ожидается 1
пример «Пример 3 из условия»
дано элементы равно [5, 4, -1, 7, 8]
ожидается 23
пример «Пустой список»
дано элементы равно пустой список
ожидается 0
разбор элементов
случай пусто
то 0
случай голова и хвост
пусть начальное равно запись «Состояние Кадане» с текущая равным голова и лучшая равным голова
пусть итог равно свёртка хвост начиная с начальное как акк и эл
пусть продолженная равно акк.текущая плюс эл
пусть текущая равно если продолженная больше эл то продолженная иначе эл
пусть лучшая равно если текущая больше акк.лучшая то текущая иначе акк.лучшая
запись «Состояние Кадане» с текущая равным текущая и лучшая равным лучшая
итог.лучшая
динамика
5/5 примеров
0/2 функций тотальны
45 строк
Линейный проход с двумя накопителями. Нетотальна: счётчик «осталось минус 1» — результат арифметики, а не часть значения.
модуль «Ступени»
// LeetCode 70. Climbing Stairs.
// Сколькими способами подняться на n ступеней шагами по одной и по две.
//
// Обычная. Ответ — число Фибоначчи, и считается он за один проход с двумя
// накопителями; тотальной функция всё равно не становится, потому что
// «осталось минус 1» не является частью значения «осталось». Это та же
// граница, что в модуле stdlib/numbers.flang: рекурсия по числу анализу
// недоступна в принципе, ей нужна мера, а мер он не знает.
//
// Обход существует: передать список из n элементов и рекурсировать по нему.
// Но список из n элементов сам по себе строится рекурсией по n — то есть
// обычной функцией, и тотальность не спасена, а лишь передвинута.
функция «Ступени шагом»
принимает осталось: число, предыдущее: число, текущее: число
возвращает число
пример «Один шаг»
дано осталось равно 1
дано предыдущее равно 1
дано текущее равно 1
ожидается 2
если осталось не больше 0
то текущее
иначе «Ступени шагом» от (осталось минус 1) и текущее и (предыдущее плюс текущее)
функция «Ступени»
принимает н: число
возвращает число
пример «Пример 1 из условия»
дано н равно 2
ожидается 2
пример «Пример 2 из условия»
дано н равно 3
ожидается 3
пример «Одна ступень»
дано н равно 1
ожидается 1
пример «Десять ступеней»
дано н равно 10
ожидается 89
если н не больше 1
то 1
иначе «Ступени шагом» от (н минус 1) и 1 и 1
динамика
3/3 примеров
1/1 функций тотальны
36 строк
Один проход свёрткой, состояние — запись «минимальная цена, лучшая прибыль».
модуль «Лучшая сделка»
// LeetCode 121. Best Time to Buy and Sell Stock.
// По списку цен по дням найти наибольшую прибыль от одной покупки и одной
// последующей продажи. Если прибыли нет — ноль.
//
// Тотальная: один проход свёрткой, состояние — запись из двух чисел
// (минимальная цена и лучшая прибыль).
объект «Сделка»
минимум является числом
прибыль является числом
тотальная функция «Лучшая прибыль»
принимает цены: список числа
возвращает число
пример «Пример 1 из условия»
дано цены равно [7, 1, 5, 3, 6, 4]
ожидается 5
пример «Пример 2 из условия»
дано цены равно [7, 6, 4, 3, 1]
ожидается 0
пример «Пустой список»
дано цены равно пустой список
ожидается 0
разбор цены
случай пусто
то 0
случай голова и хвост
пусть начальное равно запись «Сделка» с минимум равным голова и прибыль равным 0
пусть итог равно свёртка хвост начиная с начальное как акк и цена
пусть минимум равно если цена меньше акк.минимум то цена иначе акк.минимум
пусть сегодня равно цена минус акк.минимум
пусть прибыль равно если сегодня больше акк.прибыль то сегодня иначе акк.прибыль
запись «Сделка» с минимум равным минимум и прибыль равным прибыль
итог.прибыль
деревья
3/3 примеров
5/5 функций тотальны
76 строк
Конъюнкция трёх условий записана вложенными «если»: логических «и» и «или» в языке нет.
модуль «Сбалансированное дерево»
// LeetCode 110. Balanced Binary Tree.
// Проверить, что для каждого узла глубины поддеревьев отличаются не более
// чем на единицу.
//
// Тотальная. Логических «и» и «или» в языке нет (SPEC перечисляет только
// арифметику и сравнения), поэтому конъюнкция трёх условий записана
// вложенными «если» — читается длиннее, но означает ровно то же.
тип «Дерево»
вариант Лист
вариант Узел содержит значение: число, левое: «Дерево», правое: «Дерево»
тотальная функция «Вставить в дерево»
принимает дерево: «Дерево», число: число
возвращает «Дерево»
разбор дерева
случай Лист
то Узел с значение равным число и левое равным вариант Лист и правое равным вариант Лист
случай вариант Узел с значение как зн и левое как л и правое как п
если число меньше зн
то
пусть новое равно «Вставить в дерево» от л и число
Узел с значение равным зн и левое равным новое и правое равным п
иначе
пусть новое равно «Вставить в дерево» от п и число
Узел с значение равным зн и левое равным л и правое равным новое
тотальная функция «Дерево из списка»
принимает элементы: список числа
возвращает «Дерево»
свёртка элементы начиная с вариант Лист как акк и эл → «Вставить в дерево» от акк и эл
тотальная функция «Глубина»
принимает дерево: «Дерево»
возвращает число
разбор дерева
случай Лист
то 0
случай вариант Узел с левое как л и правое как п
пусть слева равно «Глубина» от л
пусть справа равно «Глубина» от п
1 плюс (если слева больше справа то слева иначе справа)
тотальная функция «Сбалансировано»
принимает дерево: «Дерево»
возвращает признак
разбор дерева
случай Лист
то да
случай вариант Узел с левое как л и правое как п
если («Сбалансировано» от л) равен нет
то нет
иначе
если («Сбалансировано» от п) равен нет
то нет
иначе
пусть разница равно («Глубина» от л) минус («Глубина» от п)
если разница меньше 0
то (0 минус разница) не больше 1
иначе разница не больше 1
тотальная функция «Сбалансировано для списка»
принимает элементы: список числа
возвращает признак
пример «Сбалансированное дерево»
дано элементы равно [2, 1, 3]
ожидается да
пример «Цепочка не сбалансирована»
дано элементы равно [1, 2, 3, 4]
ожидается нет
пример «Пустое дерево сбалансировано»
дано элементы равно пустой список
ожидается да
«Сбалансировано» от («Дерево из списка» от элементы)
деревья
5/5 примеров
7/7 функций тотальны
88 строк
Само «Развернуть» примера иметь не может — оно возвращает вариант. Проверяется наблюдаемое следствие: обход по порядку до и после разворота.
модуль «Развернуть дерево»
// LeetCode 226. Invert Binary Tree.
// Поменять местами левое и правое поддерево у каждого узла.
//
// Тотальная. Само «Развернуть» примера иметь не может: оно возвращает
// вариант, а значение варианта в «ожидается» не записывается — парсер
// разворачивает конструктор в запись из его полей и теряет имя варианта.
// Поэтому проверяется наблюдаемое следствие: обход по возрастанию до и после
// разворота. У дерева поиска обход по порядку отсортирован, у развёрнутого —
// отсортирован в обратную сторону.
тип «Дерево»
вариант Лист
вариант Узел содержит значение: число, левое: «Дерево», правое: «Дерево»
тотальная функция «Соединить списки»
принимает первый: список числа, второй: список числа
возвращает список числа
пример «Склейка»
дано первый равно [1]
дано второй равно [2, 3]
ожидается [1, 2, 3]
свёртка второй начиная с первый как акк и эл → добавить эл к акк
тотальная функция «Вставить в дерево»
принимает дерево: «Дерево», число: число
возвращает «Дерево»
разбор дерева
случай Лист
то Узел с значение равным число и левое равным вариант Лист и правое равным вариант Лист
случай вариант Узел с значение как зн и левое как л и правое как п
если число меньше зн
то
пусть новое равно «Вставить в дерево» от л и число
Узел с значение равным зн и левое равным новое и правое равным п
иначе
пусть новое равно «Вставить в дерево» от п и число
Узел с значение равным зн и левое равным л и правое равным новое
тотальная функция «Дерево из списка»
принимает элементы: список числа
возвращает «Дерево»
свёртка элементы начиная с вариант Лист как акк и эл → «Вставить в дерево» от акк и эл
тотальная функция «Развернуть»
принимает дерево: «Дерево»
возвращает «Дерево»
разбор дерева
случай Лист
то вариант Лист
случай вариант Узел с значение как зн и левое как л и правое как п
пусть слева равно «Развернуть» от п
пусть справа равно «Развернуть» от л
Узел с значение равным зн и левое равным слева и правое равным справа
тотальная функция «Обход по порядку»
принимает дерево: «Дерево»
возвращает список числа
разбор дерева
случай Лист
то пустой список
случай вариант Узел с значение как зн и левое как л и правое как п
пусть слева равно «Обход по порядку» от л
пусть справа равно «Обход по порядку» от п
«Соединить списки» от (добавить зн к слева) и справа
тотальная функция «Обход дерева из списка»
принимает элементы: список числа
возвращает список числа
пример «Дерево поиска обходится по возрастанию»
дано элементы равно [4, 2, 7, 1, 3, 6, 9]
ожидается [1, 2, 3, 4, 6, 7, 9]
«Обход по порядку» от («Дерево из списка» от элементы)
тотальная функция «Обход после разворота»
принимает элементы: список числа
возвращает список числа
пример «Пример 1 из условия»
дано элементы равно [4, 2, 7, 1, 3, 6, 9]
ожидается [9, 7, 6, 4, 3, 2, 1]
пример «Пример 2 из условия»
дано элементы равно [2, 1, 3]
ожидается [3, 2, 1]
пример «Пустое дерево»
дано элементы равно пустой список
ожидается пустой список
«Обход по порядку» от («Развернуть» от («Дерево из списка» от элементы))
поиск
5/5 примеров
3/3 функций тотальны
75 строк
Приём «топливо»: рядом с настоящими аргументами едет список, у которого на каждом шаге берётся хвост. Топливо убывает структурно, значит цикл доказуемо конечен.
модуль «Двоичный поиск»
// LeetCode 704. Binary Search.
// В отсортированном списке найти номер цели (с нуля) или −1.
//
// Тотальная — но приёмом, который стоит запомнить, потому что он показывает
// границу анализа завершаемости. Двоичный поиск сужает пару чисел «низ» и
// «верх», а убывание по числам totality.mjs не признаёт: «середина плюс 1» —
// результат арифметики, а не часть значения. Прямая запись даёт
// FLANG_NOT_TOTAL.
//
// Обход: рядом с настоящими аргументами едет «топливо» — список, у которого
// на каждом шаге берётся хвост. Топливо убывает структурно, значит цикл
// доказуемо конечен; а поскольку топливом служит сам список, шагов заведомо
// хватает (их нужно log₂n, а есть n). Приём честный, но это именно приём:
// в языке не хватает убывания по мере.
тотальная функция «Элемент»
принимает элементы: список числа, номер: число
возвращает число
пример «Второй элемент»
дано элементы равно [10, 20, 30]
дано номер равно 2
ожидается 20
разбор элементов
случай пусто
то 0
случай голова и хвост
если номер не больше 1
то голова
иначе «Элемент» от хвост и (номер минус 1)
тотальная функция «Поиск в диапазоне»
принимает топливо: список числа, элементы: список числа, цель: число, низ: число, верх: число
возвращает число
пример «Нашли середину»
дано топливо равно [1, 2, 3]
дано элементы равно [1, 2, 3]
дано цель равно 2
дано низ равно 1
дано верх равно 3
ожидается 1
разбор топливо
случай пусто
то -1
случай голова и хвост
если низ больше верх
то -1
иначе
пусть сумма равно низ плюс верх
пусть середина равно (сумма минус (сумма остаток от 2)) делить на 2
пусть значение равно «Элемент» от элементы и середина
если значение равен цель
то середина минус 1
иначе
если значение меньше цель
то «Поиск в диапазоне» от хвост и элементы и цель и (середина плюс 1) и верх
иначе «Поиск в диапазоне» от хвост и элементы и цель и низ и (середина минус 1)
тотальная функция «Двоичный поиск»
принимает элементы: список числа, цель: число
возвращает число
пример «Пример 1 из условия»
дано элементы равно [-1, 0, 3, 5, 9, 12]
дано цель равно 9
ожидается 4
пример «Пример 2 из условия»
дано элементы равно [-1, 0, 3, 5, 9, 12]
дано цель равно 2
ожидается -1
пример «Один элемент»
дано элементы равно [5]
дано цель равно 5
ожидается 0
«Поиск в диапазоне» от элементы и элементы и цель и 1 и (длина элементы)
числа
4/4 примеров
2/2 функций тотальны
32 строк
Сумма прогрессии минус сумма списка. Единственная задача набора, где язык не мешает ничем.
модуль «Пропущенное число»
// LeetCode 268. Missing Number.
// В списке лежат все числа от 0 до n, кроме одного. Найти пропущенное.
//
// Тотальная и без рекурсии: сумма арифметической прогрессии минус сумма
// списка. Здесь язык не мешает вовсе — вся задача выражается двумя свёртками
// и арифметикой.
тотальная функция «Сумма»
принимает элементы: список числа
возвращает число
пример «Сумма трёх»
дано элементы равно [1, 2, 3]
ожидается 6
свёртка элементы начиная с 0 как акк и эл → акк плюс эл
тотальная функция «Пропущенное число»
принимает элементы: список числа
возвращает число
пример «Пример 1 из условия»
дано элементы равно [3, 0, 1]
ожидается 2
пример «Пример 2 из условия»
дано элементы равно [0, 1]
ожидается 2
пример «Пример 3 из условия»
дано элементы равно [9, 6, 4, 2, 3, 5, 7, 0, 1]
ожидается 8
пусть предел равно длина элементы
пусть полная равно (предел умножить на (предел плюс 1)) делить на 2
полная минус («Сумма» от элементы)
Рабочие примеры
Файлы лежат в репозитории курса, покрыты тестами и запускаются одной командой: npm run fts:examples. Ниже их настоящее содержимое.
Node.js отвечает за сокет и коды ответа, FTS — за правило. Примеры модели выполняются на старте: не прошёл предметный тест — сервис не поднялся.
npm run fts:apinode --test examples/fts/discount-api/server.test.mjs/**
* HTTP-сервис расчёта скидки поверх FTS.
*
* Разделение ответственности, ради которого всё и затевалось:
* — FTS отвечает за бизнес-правило (какая скидка положена);
* — Node.js отвечает за эффекты (сокет, маршруты, коды ответа, лимит тела).
*
* Примеры из модели выполняются на старте: если предметный тест не проходит,
* сервис не поднимается вообще. Правило, которое не проходит собственные
* примеры, до продакшена не доезжает.
*
* Запуск: node examples/fts/discount-api/server.mjs
* Проверка: curl -s localhost:8788/discount -d '{"сумма":20000,"постоянный клиент":true}'
*/
import { createServer } from 'node:http';
import { readFile } from 'node:fs/promises';
import { fileURLToPath, pathToFileURL } from 'node:url';
import { resolve } from 'node:path';
import { assertValid, compile, executeUtility, testUtilities } from '../../../static/js/vendor/fts/browser.js';
const here = fileURLToPath(new URL('.', import.meta.url));
export const MODEL_FILE = resolve(here, '../../../static/fts/models/order-discount.fts');
const UTILITY = 'Рассчитать скидку';
const MAX_BODY = 64 * 1024;
export async function createCalculator(modelFile = MODEL_FILE) {
const document = assertValid(compile(await readFile(modelFile, 'utf8')));
const tests = testUtilities(document);
if (!tests.valid) {
const failed = tests.results.filter((result) => !result.passed);
throw new Error(
`FTS-примеры не прошли (${failed.length} из ${tests.total}): ` +
failed.map((result) => `«${result.example}» ожидалось ${result.expected}, получено ${result.actual}`).join('; '),
);
}
return { document, tests, calculate: (purchase) => executeUtility(document, UTILITY, purchase) };
}
export async function createDiscountServer(modelFile = MODEL_FILE) {
const { calculate, tests, document } = await createCalculator(modelFile);
const fields = document.structures.find((structure) => structure.name === 'Покупка').fields;
return createServer(async (request, response) => {
try {
if (request.method === 'GET' && request.url === '/health') {
return send(response, 200, { ok: true, model: document.category, examples: `${tests.passed}/${tests.total}` });
}
if (request.method === 'GET' && request.url === '/contract') {
return send(response, 200, { utility: UTILITY, input: fields, output: 'Деньги' });
}
if (request.method !== 'POST' || request.url !== '/discount') {
return send(response, 404, { error: 'используйте POST /discount' });
}
const purchase = JSON.parse(await readBody(request));
return send(response, 200, { discount: calculate(purchase) });
} catch (error) {
/* Нарушенное свойство и неизвестное поле — это ошибка запроса, а не сбой
сервиса: клиенту возвращается причина, диагностика FTS не теряется. */
return send(response, 400, {
error: error instanceof Error ? error.message : String(error),
diagnostics: error?.diagnostics ?? [],
});
}
});
}
async function readBody(request) {
const chunks = [];
let size = 0;
for await (const chunk of request) {
size += chunk.length;
if (size > MAX_BODY) throw new Error('тело запроса больше 64 КБ');
chunks.push(chunk);
}
return Buffer.concat(chunks).toString('utf8');
}
function send(response, status, body) {
response.writeHead(status, { 'content-type': 'application/json; charset=utf-8' });
response.end(`${JSON.stringify(body, null, 2)}\n`);
}
if (process.argv[1] && import.meta.url === pathToFileURL(process.argv[1]).href) {
const port = Number.parseInt(process.env.FTS_HTTP_PORT ?? '8788', 10);
const server = await createDiscountServer();
server.listen(port, '127.0.0.1', () => {
process.stdout.write(`Discount API: http://127.0.0.1:${port} (POST /discount, GET /contract, GET /health)\n`);
});
}
Модель формулирует утверждение на FTS, а допуск команды выдаёт доказательство на реальных данных заказа. Убедительность текста здесь ничего не решает.
node examples/fts/shipment-guard/guard.mjs ЗК-7781… ЗК-7781 --blocked, код выхода 1/**
* Допуск команды «отгрузить заказ» через доказательство на реальных данных.
*
* Это шаблон для агентских сценариев: модель (или человек) формулирует
* утверждение на FTS, а решение принимает не текст ответа, а движок. Если факт
* в данных не подтверждается, prove() отклоняет теорему и команда не выполняется.
* Эффект (реальная отгрузка) живёт снаружи и вызывается только после allow.
*
* Запуск: node examples/fts/shipment-guard/guard.mjs ЗК-7781
* node examples/fts/shipment-guard/guard.mjs ЗК-7781 --blocked
*/
import { readFile } from 'node:fs/promises';
import { fileURLToPath, pathToFileURL } from 'node:url';
import { resolve } from 'node:path';
import { compile, prove } from '../../../static/js/vendor/fts/browser.js';
const here = fileURLToPath(new URL('.', import.meta.url));
const models = resolve(here, '../../../static/fts/models');
/* Кавычки внутри имени сломали бы разбор, поэтому номер заказа проверяется
до подстановки: в теорему попадают только допустимые идентификаторы. */
const ORDER_NUMBER = /^[\p{L}\p{N}-]{1,32}$/u;
export function shipmentTheorem(orderNumber) {
if (!ORDER_NUMBER.test(orderNumber)) throw new Error(`недопустимый номер заказа: ${orderNumber}`);
return `категория «Исполнение заказа»
объект Заказ
номер является строкой
клиент является строкой
оплачен является признаком
«склад подтвердил» является признаком
«готов к отгрузке» является состоянием «Готов к отгрузке»
морфизм «Готовый заказ можно отгрузить»
если «Готов к отгрузке»
то «Отгрузить заказ разрешено»
теорема «Заказ ${orderNumber} можно отгрузить»
дано Заказ имеет «готов к отгрузке» равное да
в данных заказы найти где номер равен «${orderNumber}»
по морфизму «Готовый заказ можно отгрузить»
следовательно «Отгрузить заказ разрешено»
`;
}
export function decideShipment(orderNumber, context) {
const source = shipmentTheorem(orderNumber);
try {
const proof = prove(compile(source), context);
return { allowed: true, source, proof };
} catch (error) {
return {
allowed: false,
source,
reason: error instanceof Error ? error.message : String(error),
diagnostics: error?.diagnostics ?? [],
};
}
}
export async function loadContext(blocked = false) {
const file = resolve(models, blocked ? 'order-shipment.blocked.context.json' : 'order-shipment.context.json');
return JSON.parse(await readFile(file, 'utf8'));
}
if (process.argv[1] && import.meta.url === pathToFileURL(process.argv[1]).href) {
const orderNumber = process.argv[2] ?? 'ЗК-7781';
const decision = decideShipment(orderNumber, await loadContext(process.argv.includes('--blocked')));
process.stdout.write(`${JSON.stringify(decision, null, 2)}\n`);
/* Ненулевой код возврата делает guard пригодным для shell и CI. */
process.exit(decision.allowed ? 0 : 1);
}
Из модели получаются реализация и тесты на node:test. Режим --check роняет сборку, если правило поправили в TypeScript мимо модели.
node examples/fts/typescript-codegen/generate.mjs… generate.mjs --check// Generated by FTS. Do not edit by hand.
export interface FtsInput0 {
"сумма": number
"постоянный клиент": boolean
}
export const ftsUtilities = {
"Рассчитать скидку": (input: FtsInput0): number => {
let result: number = 0
if (input["сумма"] >= 10000 && input["сумма"] <= 100000) {
result += (10 / 100) * input["сумма"]
}
if (input["постоянный клиент"] === true && input["сумма"] > 0 && input["сумма"] <= 100000) {
result += (5 / 100) * input["сумма"]
}
if (input["сумма"] > 100000) {
result += 15000
}
if (!(result <= 15000)) throw new Error("Нарушено свойство «Скидка ограничена»")
return result
},
} as const
Схема формы выводится из объекта FTS: контрол, тип, обязательность. Компонент React не дублирует контракт, который уже проверяет бэкенд.
node examples/fts/form-schema/schema.mjs Покупкаиногда является отображается в required: false/**
* Форма скидки на React.
*
* Компонент не знает, что покупка состоит из суммы и признака постоянного
* клиента: поля приходят из той же FTS-модели, которую проверяет бэкенд.
* Добавили в модель поле — форма получила контрол без правки JSX.
*
* Предпросчёт скидки выполняется прямо в браузере тем же компилятором, поэтому
* пользователь видит результат без сетевого запроса. Сервер всё равно считает
* заново: браузеру доверять нельзя, но и ждать его не нужно.
*/
import { useMemo, useState } from 'react';
import { compile, executeUtility } from '@digitable-lol/fts/browser';
import { ftsFormSchema } from '../form-schema/schema.mjs';
export function DiscountForm({ source, objectName = 'Покупка', utility = 'Рассчитать скидку', onSubmit }) {
const document = useMemo(() => compile(source), [source]);
const schema = useMemo(() => ftsFormSchema(document, objectName), [document, objectName]);
const [value, setValue] = useState(() =>
Object.fromEntries(schema.fields.map((field) => [field.name, field.control === 'checkbox' ? false : ''])),
);
const preview = useMemo(() => {
try {
const input = Object.fromEntries(
schema.fields.map((field) => [
field.name,
field.control === 'checkbox' ? Boolean(value[field.name]) : Number(value[field.name] || 0),
]),
);
return { ok: true, amount: executeUtility(document, utility, input) };
} catch (error) {
/* Нарушенное свойство модели — это нормальный ответ формы, а не падение UI. */
return { ok: false, reason: error.message };
}
}, [document, schema, utility, value]);
return (
<form
onSubmit={(event) => {
event.preventDefault();
onSubmit?.(value);
}}
>
<h2>{schema.title}</h2>
{schema.fields.map((field) => (
<label key={field.name}>
<span>{field.label}</span>
<input
type={field.control === 'checkbox' ? 'checkbox' : field.control === 'text' ? 'text' : 'number'}
required={field.required}
checked={field.control === 'checkbox' ? Boolean(value[field.name]) : undefined}
value={field.control === 'checkbox' ? undefined : value[field.name]}
onChange={(event) =>
setValue((current) => ({
...current,
[field.name]: field.control === 'checkbox' ? event.target.checked : event.target.value,
}))
}
/>
</label>
))}
<output>
{preview.ok ? `Скидка: ${preview.amount} ₽` : `Правило не выполняется: ${preview.reason}`}
</output>
<button type="submit" disabled={!preview.ok}>
Оформить
</button>
</form>
);
}
Проверка модели, выполнение примеров, сверка сгенерированного кода и тесты интеграций — четыре шага, которые ловят расхождение текста правила и кода.
.github/workflows/fts-check.ymlnpm run fts:examples# Предметные правила как обычный шаг CI.
#
# Смысл шага не в «ещё одном линтере»: примеры внутри .fts — это тесты,
# написанные на языке предметной области, а сгенерированный TypeScript
# сверяется с моделью. Правило, изменённое в коде мимо модели, ломает сборку.
#
# Файл кладётся в .github/workflows/fts-check.yml
name: fts
on:
push:
branches: [master]
pull_request:
jobs:
rules:
runs-on: ubuntu-latest
steps:
- uses: actions/checkout@v4
- uses: actions/setup-node@v4
with:
node-version: 24
cache: npm
- run: npm ci
# Модель разобралась, типы сошлись, ссылки на объекты и поля существуют.
- name: Проверить модели
run: npx fts check static/fts/models/order-discount.fts
# Примеры из .fts выполняются как предметные unit-тесты.
- name: Выполнить предметные примеры
run: npx fts test static/fts/models/order-discount.fts --pretty
# Сгенерированный TypeScript обязан совпадать с закоммиченным.
- name: Сверить сгенерированный код
run: node examples/fts/typescript-codegen/generate.mjs --check
# Интеграции: HTTP-сервис, guard допуска команды, схема формы.
- name: Тесты интеграций
run: node --test "examples/fts/**/*.test.mjs"
Где проходит граница
Внешних эффектов у языка нет вовсе: ни HTTP, ни SQL, ни оплаты. Поэтому интеграция у всех стеков одна и та же и состоит из четырёх шагов, из которых язык занимает ровно один.
Тот же вызов с другой стороны разобран в курсе: Node.js и граница HTTP, форма и таблица в React из одной модели, Python, Go и shell через CLI, допуск команды AI-агенту. Граница везде одна: JSON внутрь, JSON наружу, ненулевой код выхода на провале.
Где применяют
Каждый кейс называет входные факты, роль FTS, выходной артефакт и место интеграции.
Retail: deterministic calculation
Retail: command eligibility
Retail: executable examples
Retail: generated form
Retail: generated table
Retail: verified transition
Retail: agent tool
Retail: regression gate
Marketplaces: deterministic calculation
Marketplaces: command eligibility
Marketplaces: executable examples
Marketplaces: generated form
Marketplaces: generated table
Marketplaces: verified transition
Marketplaces: agent tool
Marketplaces: regression gate
Banking: deterministic calculation
Banking: command eligibility
Banking: executable examples
Banking: generated form
Banking: generated table
Banking: verified transition
Banking: agent tool
Banking: regression gate
Payments: deterministic calculation
Payments: command eligibility
Payments: executable examples
Payments: generated form
Payments: generated table
Payments: verified transition
Payments: agent tool
Payments: regression gate
Insurance: deterministic calculation
Insurance: command eligibility
Insurance: executable examples
Insurance: generated form
Insurance: generated table
Insurance: verified transition
Insurance: agent tool
Insurance: regression gate
Logistics: deterministic calculation
Logistics: command eligibility
Logistics: executable examples
Logistics: generated form
Logistics: generated table
Logistics: verified transition
Logistics: agent tool
Logistics: regression gate
Healthcare: deterministic calculation
Healthcare: command eligibility
Healthcare: executable examples
Healthcare: generated form
Healthcare: generated table
Healthcare: verified transition
Healthcare: agent tool
Healthcare: regression gate
Pharmaceuticals: deterministic calculation
Pharmaceuticals: command eligibility
Pharmaceuticals: executable examples
Pharmaceuticals: generated form
Pharmaceuticals: generated table
Pharmaceuticals: verified transition
Pharmaceuticals: agent tool
Pharmaceuticals: regression gate
HR and hiring: deterministic calculation
HR and hiring: command eligibility
HR and hiring: executable examples
HR and hiring: generated form
HR and hiring: generated table
HR and hiring: verified transition
HR and hiring: agent tool
HR and hiring: regression gate
SaaS: deterministic calculation
SaaS: command eligibility
SaaS: executable examples
SaaS: generated form
SaaS: generated table
SaaS: verified transition
SaaS: agent tool
SaaS: regression gate
Customer support: deterministic calculation
Customer support: command eligibility
Customer support: executable examples
Customer support: generated form
Customer support: generated table
Customer support: verified transition
Customer support: agent tool
Customer support: regression gate
Education: deterministic calculation
Education: command eligibility
Education: executable examples
Education: generated form
Education: generated table
Education: verified transition
Education: agent tool
Education: regression gate
Travel: deterministic calculation
Travel: command eligibility
Travel: executable examples
Travel: generated form
Travel: generated table
Travel: verified transition
Travel: agent tool
Travel: regression gate
Hospitality: deterministic calculation
Hospitality: command eligibility
Hospitality: executable examples
Hospitality: generated form
Hospitality: generated table
Hospitality: verified transition
Hospitality: agent tool
Hospitality: regression gate
Real estate: deterministic calculation
Real estate: command eligibility
Real estate: executable examples
Real estate: generated form
Real estate: generated table
Real estate: verified transition
Real estate: agent tool
Real estate: regression gate
Manufacturing: deterministic calculation
Manufacturing: command eligibility
Manufacturing: executable examples
Manufacturing: generated form
Manufacturing: generated table
Manufacturing: verified transition
Manufacturing: agent tool
Manufacturing: regression gate
Energy: deterministic calculation
Energy: command eligibility
Energy: executable examples
Energy: generated form
Energy: generated table
Energy: verified transition
Energy: agent tool
Energy: regression gate
Telecom: deterministic calculation
Telecom: command eligibility
Telecom: executable examples
Telecom: generated form
Telecom: generated table
Telecom: verified transition
Telecom: agent tool
Telecom: regression gate
Media: deterministic calculation
Media: command eligibility
Media: executable examples
Media: generated form
Media: generated table
Media: verified transition
Media: agent tool
Media: regression gate
Advertising: deterministic calculation
Advertising: command eligibility
Advertising: executable examples
Advertising: generated form
Advertising: generated table
Advertising: verified transition
Advertising: agent tool
Advertising: regression gate
Public services: deterministic calculation
Public services: command eligibility
Public services: executable examples
Public services: generated form
Public services: generated table
Public services: verified transition
Public services: agent tool
Public services: regression gate
Information security: deterministic calculation
Information security: command eligibility
Information security: executable examples
Information security: generated form
Information security: generated table
Information security: verified transition
Information security: agent tool
Information security: regression gate
DevOps and SRE: deterministic calculation
DevOps and SRE: command eligibility
DevOps and SRE: executable examples
DevOps and SRE: generated form
DevOps and SRE: generated table
DevOps and SRE: verified transition
DevOps and SRE: agent tool
DevOps and SRE: regression gate
Agriculture: deterministic calculation
Agriculture: command eligibility
Agriculture: executable examples
Agriculture: generated form
Agriculture: generated table
Agriculture: verified transition
Agriculture: agent tool
Agriculture: regression gate
Legal and compliance: deterministic calculation
Legal and compliance: command eligibility
Legal and compliance: executable examples
Legal and compliance: generated form
Legal and compliance: generated table
Legal and compliance: verified transition
Legal and compliance: agent tool
Legal and compliance: regression gate
E-commerce operations: deterministic calculation
E-commerce operations: command eligibility
E-commerce operations: executable examples
E-commerce operations: generated form
E-commerce operations: generated table
E-commerce operations: verified transition
E-commerce operations: agent tool
E-commerce operations: regression gate
Accounting: deterministic calculation
Accounting: command eligibility
Accounting: executable examples
Accounting: generated form
Accounting: generated table
Accounting: verified transition
Accounting: agent tool
Accounting: regression gate
Procurement: deterministic calculation
Procurement: command eligibility
Procurement: executable examples
Procurement: generated form
Procurement: generated table
Procurement: verified transition
Procurement: agent tool
Procurement: regression gate
Identity and access: deterministic calculation
Identity and access: command eligibility
Identity and access: executable examples
Identity and access: generated form
Identity and access: generated table
Identity and access: verified transition
Identity and access: agent tool
Identity and access: regression gate
По этим фильтрам кейсов нет. Попробуйте убрать один из фильтров.
Границы
map, filter, groupBy, debounce остаются в JavaScript и переезжать не должны.Дальше
23 модулей по FTS и 14 по flang — синтаксис, утилиты, тесты, диагностика, Node.js, React, DDD, AI/MCP, CI, тотальность и кодогенерация. В каждом модуле упражнение, которое открывается прямо в песочнице на шаге 3.
Ступени, треки и материалы портала. Кликните ступень, чтобы раскрыть треки, трек — чтобы увидеть статьи, статью — чтобы увидеть, с чем она связана по общим темам.
Колесо — масштаб, перетаскивание — панорама. Стрелки и Tab — переход между узлами, Enter — раскрыть или выбрать. Повторный клик по материалу показывает его соседей по общим темам.