Купил замечательную книжку «Лекции по грубой геометрии» (coarse book) дорогого брата Кофейного Теоретика. В первую очередь хочу познакомиться про борнологические группы и грубую неподвижную точку. Темка выросла из алгебраической топологии и теории групп.
В первом приближении, так понял, борнология -- это классная теория по "допустимым" вычислениям (по памяти, времени, размеру)! Идеально для формализации в функциональщине эффектов, f-bounded polymorphism, graded monads... Статическая типизация "что считать ограниченным"!
А грубую фиксточку берём по модулю ограниченной ошибки, и по сути это темка абстрактной интерпретации кода, которая и есть вычисление наименьшей неподвижной точки монотонного оператора на решётке абстрактных свойств! Точный фикспоинт недостижим за конечное время, а тут (widening) мы можем определить борнологию на решётке: "насколько далеко мы готовы прыгнуть, чтобы гарантировать завершение". Там, где обычный let rec эфшарпа зациклится, widening даёт гарантированную остановку с огрублённым ответом. Инварианты циклов выводяся автоматически (эта переменная всегда > 0, список не пуст после N итераций), статический анализ кода (диапазоны, нул-чек, отсутствие переполнений) строже чем в ReSharper...
Ну а когда переходим в любимую HoTT ❤️ получается вообще красотища. Например, иерархия h-уровней; выбор уровня усечения по сути есть выбор борнологии "что считаем неразличимым". Сам фактор огрубления формализуем через HIT: конструктивное widening на уровне типов. А топчик конечно это унивалентность. "Эквивалентные типы равны" для практических целей можем считать как coarse equivalence.
Я уже отмечал много раз, что HoTT -- это самый мощный и непревзойдённый на сегодня "язык программирования". В частности мы на нём можем закодить "равенство по модулю ограниченного огрубления" как первоклассный объект (тот же путь, HIT). И этот ваш widening в статическом анализе кода будет лишь жалкий дискретный аналог усечений в HoTT.
Post #2407
1.88K

- 👍 32
- ✍ 6
- ❤ 6
- ❤🔥 3