Свойства как компас: точное программирование ✛ ✎

Оригинал: "Accurate Programming: Thinking about programs in terms of properties"
arXiv:1109.0786 · 2011-09-05 · arXiv non-exclusive · собственный разбор · 2 мин
Программы — это не только код, но и математические свойства, которые можно проверять автоматически.

Туман сгущается над строкой «def max(a: Int, b: Int): Int». Что она делает? Возвращает большее из двух чисел — но как это проверить? Можно написать десяток тестов с конкретными парами: max(2,3)=3, max(5,5)=5, max(-1,0)=0. И всё равно останется тревога: а вдруг для какого-нибудь миллиона и минус миллиона она сломается? Вместо того чтобы вглядываться в туман, разработчик может взять компас — и компас этот называется свойством.

Свойство — это утверждение о программе, которое должно быть верно для всех входных данных. Не «для 2 и 3 возвращает 3», а «для любых a и b результат не меньше каждого из них». Такое утверждение можно записать не только на бумаге, но и в коде. Библиотека ScalaCheck умеет генерировать сотни случайных значений, подставлять их в свойство и сообщать, если хоть одно нарушилось. Это и есть тестирование на основе свойств: вместо ручного перебора примеров — автоматическая проверка закона.

Свойство как компас: оно не ведёт вас по одному маршруту, а задаёт направление, которое верно для любого пути. Для функции max три таких направления — симметрия (max(a,b)=max(b,a)), идемпотентность (max(a,a)=a) и свойство наименьшей верхней границы (результат не меньше каждого аргумента и не больше любого другого такого числа). Вместе они полностью определяют, что значит «максимум».

Но свойства не только проверяют готовый код — они помогают его писать. Возьмём функцию sum, которая складывает список чисел. Одно из свойств — монотонность: если взять список и добавить в него положительное число, сумма вырастет. Казалось бы, очевидно. Но ScalaCheck находит контрпример: для списка [65536] и добавленного 1 сумма не растёт, а остаётся 65537 — из-за переполнения целого типа в некоторых языках. Компас указал на скалу, которую не видели обычные тесты.

Свойства можно уточнять, как настройку компаса. Функция count считает элементы списка. Первое свойство — «результат неотрицательный» — слишком слабое: ему удовлетворяет даже функция, всегда возвращающая ноль. Добавляем свойство «для списка из одного элемента результат равен 1» — ноль отсеивается, но остаются другие самозванцы. Постепенно, шаг за шагом, свойства сходятся к единственной правильной реализации.

И вот поворот: сама программа — это тоже свойство. Если функция всегда возвращает 42, её можно описать свойством «для любого входа результат равен 42». Грань между спецификацией (что мы хотим) и реализацией (как мы это делаем) размывается. Точное программирование — это подход, при котором разработчик держит в голове не только код, но и свойства, которые этот код обязан выполнять. Это мост между тестированием и формальной верификацией: мы не доказываем программу целиком, но получаем большинство гарантий за малую долю цены.

Туман рассеивается. Строка «def max» больше не выглядит загадкой: у неё есть три свойства-компаса, и каждый из них можно проверить автоматически. Программирование перестаёт быть угадыванием и становится навигацией по карте, которую мы сами чертим.

Название библиотеки ScalaCheck отсылает к идее автоматической проверки свойств, а не к «проверке Скалы» — это инструмент для проверки свойств в Scala.

В сериале «Мир Дикого Запада» поведение роботов определяется сложными правилами, но их корректность не гарантирована. Точное программирование могло бы помочь формулировать и проверять свойства поведения, предотвращая неожиданные сбои.

Учёные
Erwin SchrödingerHugh Everett IIIMax BornAlbert EinsteinJohn von NeumannAugustin-Louis Cauchy
Понятия
точность автоматизация оптимизация диагностическая точность обработка естественного языка реальное время квантовый алгоритм дизайн лекарств открытый исходный код сходимость машинное обучение компьютерное моделирование распознавание речи персонализированная медицина искусственный интеллект робототехника вычисление классификация точное решение точность