TheDIM47 2 мар в 20:54

Исследуем монады в Rust через тестирование на основе свойств

Простой

22 мин

1.3K

Перевод

В педагогике программирования монады занимают место мистического объекта из мира функционального программирования, который трудно понять и еще труднее объяснить.
Стереотип о сложности объяснения монад заключается в том, что они делятся на две категории: либо сравнение с каким-то продуктом питания, либо написание сложного математического жаргона, в чем проблема?

Но монады вовсе не являются чем-то эзотерическим или магическим, и они встречаются не только в функциональном программировании.
По сути, монада — это шаблон проектирования, который позволяет вам объединять операции в цепочку внутри системы (framework).
Приметы монадического проектирования могут быть весьма полезны для программистов в любой среде, особенно потому, что это часто нежелательно! Во многих ситуациях монады имеют заметные компромиссы, и иногда (как здесь) мы даже можем собрать конкретные данные, чтобы подтвердить это.

Я попытаюсь объяснить монады:

Ориентируясь на разработчиков Rust, с примерами кода на Rust, хотя я надеюсь, что любой достаточно любознательный программист сможет это понять
Без жаргона: никакого математического формализма
Без каких-либо аналогий и на реальных задачах программирования
Нетривиально: сосредоточившись на примере, готовом к использованию в продакшене, с объективно измеримыми последствиями
Практично: с советами, которые можем использовать все мы, программисты

Другими словами, я попытаюсь написать учебник по монадам, который я бы лично оценил, когда был моложе.
И я собираюсь начать с нетрадиционного места: с тестирования на основе свойств (property-based testing(PBT)), где монады показательны в плане производительности.

Примечание: хотя основная цель этой статьи — объяснить монады, она также служит практическим введением в PBT и метод инъекции ошибок. Если вы новичок, вы познакомитесь с этим совместно с объяснением монад.

Эта статья состоит из пяти разделов:

Раздел Property-based тестирование рассказывает основы PBT
Рисуем остаток совы рассказывает о сложном сценарии: использование PBT для инъекции ошибок
Интегрированный минимайзер показывает, как сократить объем входных данных до разумных пределов
Наконец-то, Монады, здесь мы добавляем монады в контекст PBT и тестируем производительность
Переосмысление структуры, обсуждаем некоторые способы смягчения потерь от использования монад в PBT

1. Тестирование на основе сойств

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

Лучшее объяснение этой общей идеи, которое я видел, содержится в цитате великого аргентинского писателя Хорхе Луиса Борхеса:

"...В той Империи Искусство Картографии достигло такого Совершенства, что карта одной Провинции занимала весь Город, а карта Империи — всю Провинцию. Со временем эти Несоразмерные Карты сочли неудовлетворительными, и Гильдии Картографов начертили Карту Империи, размеры которой были такими же, как у Империи, и которая совпадала с ней точка в точку...”
—On Exactitude in Science, Jorge Luis Borges

Ничто так не иллюстрирует тестирование как моделирование, как PBT-подход, при котором вместо указания точных примеров вы определяете модели в терминах свойств или инвариантов, которым должен удовлетворять ваш код. Затем вы тестируете свои модели на случайно сгенерированных входных данных.

Давайте рассмотрим простой пример процедуры сортировки, скажем, my_sort, определенной для среза целых чисел:

fn my_sort(slice: &mut [u64]) {
    // ...
}

Как нам следует это протестировать?

Самый распространенный способ сделать это — составить список входных данных и убедиться, что они правильно отсортированы, с помощью тестов с примерами (example-based tests).

#[test]
fn test_my_sort() {
    let mut input = [1, 2, 0, 2, 0, 5, 6, 9, 0, 3, 1];
    my_sort(&mut input);
    assert_eq!(input, [0, 0, 0, 1, 1, 2, 2, 3, 5, 6, 9]);

    // Больше примеров перечислено ниже.
}

Тесты с примерами весьма ценны, поскольку их легко писать и они довольно прямолинейны в отношении того, что происходит. Но даже в простом примере, таком как сортировка, легко представить себе ситуацию, когда ваши данные не покрывают все пограничные случаи.

Как можно охватить больше пограничных случаев? Ну, один из способов сделать это — сделать шаг назад и спросить, что пытается сделать сортировка? Цель функции сортировки — гарантировать, что все элементы расположены в порядке возрастания. Можем ли мы проверить это напрямую?

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

Так что, может быть, мы напишем что-то вроде:

#[test]
fn test_my_sort_2() {
    // Повторите тест 1024 раза.
    for _ in 0..1024 {
        // Создайте случайный список, скажем, из 0–512 элементов со значениями от 0 до 10000...
        let input = /* ... */;

        let mut output = input.clone();
        // Вызовите для него процедуру сортировки
        my_sort(&mut output);

        // Проверьте, что все значения расположены в порядке возрастания.
        for i in 1..output.len() {
            assert!(
                output[i - 1] <= output[i],
                "input {input:?} failed at index {i}, output {output:?}",
            );
        }
    }
}

Теперь у нас есть модель сортировки, которую мы записали в виде кода: любая пара значений должна быть в порядке возрастания.
(В этом представлении исходные данные также являются простыми моделями: для входных данных X выходными данными должен быть Y.)

Мы запускаем тест и...

thread 'test_my_sort_2' panicked at tests/tests.rs:33:13:
input [7496, 2087, 6900, 7927, 3840, 3065, 6472, 1186, 6464, 4512, 251, 5591, 3410, 2033, 5367, 2202, 5544, 2434, 6491, 8999, 9818, 2885, 8683, 1201, 6115, 2584, 2473, 6817, 5765, 5196, 9389, 5799, 9012, 293, 38, 1024, 9569, 4654, 7449, 7389, 8088, 5074, 3110, 938, 4944, 3859, 7368, 8978, 7524, 9503, 7406, 7591, 8213, 6445, 7000, 7354, 8967, 5549, 7935, 1866, 4048, 4043, 8905, 3154, 4771, 2364, 3982, 5088, 7317, 233, 3396, 1810, 3022, 9065, 454, 6181, 8257, 9598, 3982, 920, 5880, 4165, 4164, 930, 560, 9062, 5587, 6271, 5878, 2495, 9055, 3877, 4352, 1228, 8287, 8901, 3442, 373, 3635, 5316, 4423, 7688, 7919, 4465, 8991, 7043, 7696, 6875, 1478, 2428, 5127, 6809, 6175, 1415, 7263, 5145, 4153, 876, 1528, 6781, 5627, 6750, 3665, 2567, 6855, 141, 2144, 4491, 9121, 7982, 4131, 6337, 1926, 8797, 9382, 1702, 9559, 3910, 1715, 6661, 269, 4366, 6185, 5616, 365, 808, 4864, 3657, 9574, 3057, 7760, 6375, 2326, 7273, 6303, 7018, 8988, 6271, 988, 7796, 2390, 1689, 4279, 9586, 151, 9738, 3659, 7064, 1529, 8237, 4211, 2272, 8909, 7638] failed at index 173, output [38, 141, 151, 233, 251, 269, 293, 365, 373, 454, 560, 808, 876, 920, 930, 938, 988, 1024, 1186, 1201, 1228, 1415, 1478, 1528, 1529, 1689, 1702, 1715, 1810, 1866, 1926, 2033, 2087, 2144, 2202, 2272, 2326, 2364, 2390, 2428, 2434, 2473, 2495, 2567, 2584, 2885, 3022, 3057, 3065, 3110, 3154, 3396, 3410, 3442, 3635, 3657, 3659, 3665, 3840, 3859, 3877, 3910, 3982, 3982, 4043, 4048, 4131, 4153, 4164, 4165, 4211, 4279, 4352, 4366, 4423, 4465, 4491, 4512, 4654, 4771, 4864, 4944, 5074, 5088, 5127, 5145, 5196, 5316, 5367, 5544, 5549, 5587, 5591, 5616, 5627, 5765, 5799, 5878, 5880, 6115, 6175, 6181, 6185, 6271, 6271, 6303, 6337, 6375, 6445, 6464, 6472, 6491, 6661, 6750, 6781, 6809, 6817, 6855, 6875, 6900, 7000, 7018, 7043, 7064, 7263, 7273, 7317, 7354, 7368, 7389, 7406, 7449, 7496, 7524, 7591, 7638, 7688, 7696, 7760, 7796, 7919, 7927, 7935, 7982, 8088, 8213, 8237, 8257, 8287, 8683, 8797, 8901, 8905, 8909, 8967, 8978, 8988, 8991, 8999, 9012, 9055, 9062, 9065, 9121, 9382, 9389, 9503, 9559, 9569, 9574, 9586, 9598, 9818, 9738]
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Упс, похоже, в функции есть ошибка. (Прокрутите приведенный выше пример вправо!)

Этот пример совершенно бесполезен и сложен для понимания! Можно использовать его в качестве входных данных для отладки, но это довольно болезненно. Если бы мы могли использовать автоматизацию, чтобы превратить этот тестовый случай в гораздо меньший, который все еще может воспроизводить ошибку, отладка стала бы значительно проще. Этот процесс называется минимизация или сжатие (в оригинале shrinking or reduction) тестового случая.

Подведем итоги: тестирование на основе свойств состоит из двух компонентов:

Генерация тест-кейса с использованием источника случайности.
При провале теста — сжатие его до небольшого размера.

Реализация сжатия вручную

Что значит «небольшого»? Для списка чисел, в идеале, мы могли бы минимизировать как количество элементов в списке, так и сами целые числа. Предполагаемый алгоритм сжатия:

Сначала попробуйте минимизировать размер списка с помощью алгоритма бинарного поиска. Например:
- Попробуйте применить к процедуре первую половину списка.
- Если это покажет ошибку, попробуйте рекурсивно сжать эту половину.
- Если это не сработает, попробуйте со второй половиной списка.
- Если ни то, ни другое не сработает или в списке 1 или меньше элементов, переходите к следующему шагу.
После того, как список будет сжат, начните сокращать элементы в списке, применяя бинарный поиск к значению каждого элемента.

После того, как вы закончите писать этот алгоритм, вы будете на пути к созданию оригинальной библиотеки тестирования на основе свойств, QuickCheck.
Этот подход заставляет вас написать две функции: генератор и минимайзер.

Так вы можете получить гораздо более удобный вывод:

input [58, 33] failed at index 1, output [58, 33]

И для относительно простых случаев, таких как списки целых чисел, этот тип сжатия работает довольно хорошо!

Но мы здесь не для того, чтобы тестировать простые случаи. Мы здесь для сложных.

2. Рисуем остаток совы

Разрушая этот мем, в этом разделе мы рассмотрим сложность реального мира.

Большинство реальных реализаций сортировки работают не только со списком целых чисел. Они написаны так, чтобы быть полиморфными по всему, что может быть отсортировано.
На языке Rust это означает все, что реализует трейт Ord; и даже если нет, можно предоставить пользовательскую функцию компаратора.

Но Ord можно написать вручную, и пользовательские компараторы практически всегда пишутся вручную.

Одним из непосредственных последствий является то, что функция компаратора может сказать, что два элемента равны, но на самом деле они разные. В таком случае следует ли сохранять порядок элементов?

Реализация сортировки, которая сохраняет порядок, называется стабильной (устойчивой) сортировкой.
Реализация, которая этого не делает, называется нестабильной (неустойчивой) сортировкой.

Нестабильные сортировки, как правило, быстрее стабильных, и есть веские причины отдавать предпочтение каждому из них в разное время.
(В стандартной библиотеке Rust имеются отдельные реализации для стабильных и нестабильных сортировок.)

Кроме того, самописные реализации означают, что пользователи могут совершать ошибки!
Алгоритм сортировки промышленного уровня должен вести себя разумно в условиях произвольного ввода данных пользователем, не только в фактических сортируемых элементах, но и в функции сравнения
(поблагодарим Лукаса Бергдолла за его обширное исследование):

Безопасный Ord (Ord safety): пользователи могут написать компаратор, который попросту неверен. Простой способ — ввести разницу между порядком и равенством, например, вернув Ordering::Less для двух элементов, которые на самом деле равны. Пользователи также могут возвращать разные ответы для одного и того же сравнения при вызове в разное время[^1].
Безопасная паника (Panic safety): компаратор может паниковать в процессе выполнения. Поскольку паники могут быть обнаружены, входные данные должны быть в каком-то допустимом состоянии после этого.
Безопасность наблюдения (Observation safety): если компаратор изменяет какие-либо входные данные, эти изменения должны быть сохранены в итоговом выводе. (В Rust мутация через общие ссылки возможна через внутреннюю изменчивость (interrior mutability), как это реализовано в RefCell или Mutex). В этих случаях успешное завершение сортировки становится невозможным. Но важно, чтобы мы оставили входные данные в разумном состоянии.

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

Давайте сейчас сосредоточимся на безопасности Ord с компаратором, который меняет результат в 20% случаев:

#[derive(Clone, Copy, Debug)]
enum OrdBehavior {
    Regular,
    Flipped,
}

struct BadType {
    value: u64,
    ord_behavior: RefCell<Vec<OrdBehavior>>,
}

impl Ord for BadType {
    fn cmp(&self, other: &Self) -> Ordering {
        // Получаем следующий вариант поведения из списка
        match self.ord_behavior.borrow_mut().pop() {
            Some(OrdBehavior::Regular) | None => {
                self.value.cmp(&other.value)
            }
            Some(OrdBehavior::Flipped) => {
                // Меняем поведение на противоположное
                other.value.cmp(&self.value)
            }
        }
    }
}

Генератор для BadType:

fn generate_bad_type() -> BadType {
    // Сгенерируйте значение от 0 до 10000;
    let value = /* ... */;
    // Сгенерируйте список поведений длиной 0..128 в пропорции: Regular - 80% и Flipped - 20%
    let ord_behavior: Vec<OrdBehavior> = /* ... */;

    BadType {
        value,
        ord_behavior: RefCell::new(ord_behavior),
    }
}

И чтобы это проверить:

#[test]
fn test_my_sort_3() {
    // Повторите тест 1024 раза.
    for _ in 0..1024 {
        // Сгенерируйте список BadType с помощью generate_bad_type.
        let input: Vec<BadType> = /* ... */;

        // Вызовите сортировку
        let mut output = input.clone();
        my_sort(&mut output);

        // В этом случае сортировка не совсем определена, но мы можем
        // гарантировать два свойства:
        //
        // 1. my_sort не паникует (неявно проверяется, попадая сюда)
        // 2. все входные значения по-прежнему присутствуют в выходных данных
        let mut input_values: Vec<u64> =
            input.iter().map(|v| v.value).collect();
        let mut output_values: Vec<u64> =
            output.iter().map(|v| v.value).collect();

        // Отсортируйте входные и выходные значения и убедитесь, что они совпадают.
        my_sort(&mut input_values);
        my_sort(&mut output_values);
        assert_eq!(input_values, output_values);
    }
}

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

3. Интегрированный минимайзер

Как написать минимайзер для Vec<BadType>? Казалось бы, это довольно просто для списка целых чисел. Но это список, где элементы — пара из целого числа и другого списка. Также:

Пока что мы только протестировали безопасность Ord — как только мы добавим инъекцию ошибок для других видов безопасности, сложность покажется бесконечной.
И что еще важнее, нет хорошего способа объединить простые минимайзеры вместе, чтобы сформировать более сложный. Написание минимайзеров и так уже требует много работы, и какой смысл, если вам придется делать все это снова и снова?

Практический результат заключается в том, что большую часть времени написание минимайзера для таких типов, как Vec<BadType>, довольно сложно. И написание его также технически необязательно, поскольку:

Если тест пройден, минимайзеры никогда не вызываются. Просто напишите правильный код, и минимизация просто не будет проблемой!
Если тест не пройден, разработчики могут отлаживать, используя начальные входные данные. Это больно, но возможно.

В целом, если выбирать между написанием минимайзера вручную или просто продолжать жить дальше, большинство разработчиков склонны выбирать последнее[^2]. Из-за этого большинство современных систем тестирования на основе свойств, таких как proptest в Rust, пытаются позаботиться о минимизации за вас при помощи концепции интегрированного минимайзера.

Идея интегрированного минимайзера заключается в следующем: когда вы генерируете случайные входные данные, вы не просто генерируете само значение. Вы также генерируете некоторый контекст, который полезен для уменьшения размера входных данных.

В proptest это объединенное значение и контекст называются деревом значений.
Любая реализация, которая принимает генератор случайных чисел и превращает его в дерево значений, называется стратегией.

Библиотека proptest содержит множество различных видов стратегий, которые можно объединить для создания более сложных стратегий. Чтобы сгенерировать экземпляр OrdBehavior, мы будем использовать две стратегии:

"Простая" стратегия (Just), которая возвращает единственное значение.
Стратегия "Один Из" (prop_oneof), которая генерирует значения из одного из возможных списков стратегий, где каждый выбор имеет заданную вероятность. (Функция, которая принимает одну или несколько стратегий в качестве входных данных и выдает стратегию в качестве выходных данных, называется комбинатором.)

fn generate_ord_behavior() -> impl Strategy<Value = OrdBehavior> {
    prop_oneof![
        // Вероятность того, что будет сгенерирована обычная реализация, составляет 80% (4/5)
        4 => Just(OrdBehavior::Regular),
        // Вероятность "противоположной" реализации составляет 20% (1/5).
        1 => Just(OrdBehavior::Flipped),
    ]
}

Для генерации BadType мы будем использовать generate_ord_behavior, а также:

Стратегию диапазона, например 0..10000_u64, которая генерирует равномерно распределенные случайные значения в заданном диапазоне.
Комбинатор vec, который принимает стратегию для элементов и параметр размера.

fn generate_bad_type() -> impl Strategy<Value = BadType> {
    // Используйте стратегию диапазона для равномерной случайной генерации значений.
    let value_strategy = 0..10000_u64;

    // Используйте стратегию `vec` для создания списка поведений: `0..128` элементов.
    let ord_behavior_strategy = vec(generate_ord_behavior(), 0..128);

    // Что теперь? Нам нужно скомпоновать эти стратегии вместе. С помощью `proptest`,
    // это можно сделать, сначала создав кортеж стратегий.
    let tuple_strategy = (value_strategy, ord_behavior_strategy);

    // Кортеж стратегий — это тоже стратегия! Сгенерированные значения — это кортеж
    // составляющих.
    //
    // Обладая этим знанием, мы можем использовать функцию `prop_map`, чтобы превратить
    // кортеж в `BadType`.
    tuple_strategy.prop_map(|(value, ord_behavior)| {
        BadType {
            value,
            ord_behavior: RefCell::new(ord_behavior),
        }
    })
}

Объединение простых стратегий для BadType.

Вам может быть интересно, где находится весь код минимизации. На самом деле он реализован на соответствующих деревьях значений для каждой стратегии:

Стратегии диапазона используют бинарный поиск, чтобы уменьшать значения.
Простая стратегия (Just strategy) не выполняет никакой минимизации, поскольку она просто возвращает единственное значение.
Комбинатор prop_oneof минимизируется в направлении начала списка вариантов: в этом случае Flipped минимизируется до Regular.
Комбинатор vec реализует примерно тот же алгоритм, что и в нашей ручной реализации минимайзера выше.

Обратите внимание как базовые стратегии превращаются в последовательно более крупные с помощью комбинаторов, таких как prop_oneof.
Это очень похоже на Iterator, где вы можете продолжать вызывать .map, .filter, .enumerate и так далее снова и снова[^3].

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

Но есть один большой недостаток с интегрированным минимайзером. И этот недостаток — монады.

4. Наконец-то, Монады

В предыдущих нескольких разделах мы создали весь необходимый контекст. Теперь мы рассмотрим фундаментальную операцию, которая вводит монадическую композицию в proptest: prop_flat_map.

В приведенном выше примере есть функция prop_map, которую мы используем для преобразования кортежа компонентов в значение BadType. Что происходит, когда вы пытаетесь минимизировать значение с помощью prop_map? Это очень просто:

Пытаетесь получить меньшее значение из базового дерева значений.
Вызываете функцию map для значения.

Таким образом, prop_map — это проводник, через который проходят значения: он просто преобразовывает одно значение в другое и никак не меняет структуру дерева значений.

Теперь предположим, что мы хотим протестировать пары экземпляров BadType, где способ генерации второго BadType зависит от значения первого. Это ситуация, когда нам нужно не просто преобразовать одно значение в другое — нам нужно сгенерировать совершенно новую стратегию на основе исходного значения.

Это фундаментальное изменение:

Как и выше, prop_map преобразует одно значение в другое, но сохраняет исходную структуру.
Новый метод, prop_flat_map, выходит далеко за рамки этого. На основе сгенерированного значения он создает совершенно новую стратегию со своей собственной структурой.

Это монадическая композиция в действии. Результат одной операции контролирует во время выполнения всю форму следующей операции.

Например, вот один из способов генерации пар BadTypes, где второе значение всегда больше первого:

fn generate_bad_type_pair() -> impl Strategy<Value = (BadType, BadType)> {
    // Сначала сгенерируйте BadType.
    generate_bad_type().prop_flat_map(
        |first_bad_type| {
            // Теперь создайте второй BadType со значением больше первого.
            (
                (first_bad_type.value + 1)..20000_u64,
                vec(generate_ord_behavior(), 0..128),
            )
            .prop_map(move |(second_value, ord_behavior)| {
                // Сгенерируйте второе значение.
                let second_bad_type = BadType {
                    value: second_value,
                    ord_behavior: RefCell::new(ord_behavior),
                };

                // Верните пару значений
                (first_bad_type.clone(), second_bad_type)
            })
        }
    )
}

Ваша первая реакция может быть: вау, это кажется действительно мощным. И вы будете правы! Вы можете написать все, что захотите, в теле prop_flat_map:

Вы можете вернуть одну или другую стратегию, переопределив prop_oneof.
Вы можете сначала сгенерировать значение размера, а затем вернуть вектор с этим количеством элементов, переопределив комбинатор vec.
Вы можете снова вызвать prop_flat_map столько раз, сколько захотите.

Реально, prop_flat_map максимально мощный. Каждый комбинатор, о котором мы говорили, и, по сути, большую часть библиотеки proptest, можно записать в терминах prop_flat_map.

Так почему же существуют все эти комбинаторы? Почему бы нам просто не использовать prop_flat_map везде?

Функция на самом деле работает достаточно хорошо и на практике. Она генерирует случайные значения с правильной структурой и корректно сжимает их при неудачном входном значении.

Но.

Минимизация происходит очень, очень медленно.

Экспоненциально медленно.

prop_flat_map с отображением из x в стратегию 0..x². Каждый раз, когда исходное значение уменьшается, создается совершенно новая стратегия (выделена красным), и минимайзеру приходится начинать заново.

Почему это так? Рассмотрим, что происходит, когда мы хотим минимизировать значение с помощью prop_flat_map. Как и раньше:

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

Поскольку prop_flat_map генерирует совершенно новые деревья значений каждый раз, когда он вызывается, минимизацию приходится начинать заново, с нуля, каждый раз! Это суть монадической композиции: мощная, неограниченная и принципиально непредсказуемая.

Измерение

Мы можем измерить влияние монадической композиции напрямую, по двум связанным осям: количество времени, необходимое для завершения итераций, и количество итераций, за которые выполняется минимизация.

Для этого поста я написал(а) небольшую программу на Rust, которая собирает метрики минимизации для:

Реализации prop_flat_map для пар BadType описанной выше, и немонадической реализации с использованием prop_map (см. ниже)
То же самое для троек (BadType, BadType, BadType): немонадической реализации с prop_map, и монадическая с двумя уровнями prop_flat_map.

С помощью этой программы я произвел(а) 512 запусков на своей рабочей станции и проанализировал(а) данные. (Я запустил(а) программу с opt-level=1, чтобы имитировать типичные сборки dev в более крупных проектах Rust[^4]).

Во-первых, время, необходимое для минимизации значений, по ключу процентиль:

Метрика	Пары (prop_map)	Тройки (prop_map)	Пары (prop_flat_map)	Тройки (prop_flat_map)
min	11 µs	48 µs	3.85 ms	8.95 ms
p50	1.70 ms	2.52 ms	8.52 ms	181 ms
p75	3.74 ms	5.77 ms	10.04 ms	307 ms
p90	5.25 ms	8.41 ms	11.76 ms	435 ms
max	7.00 ms	10.55 ms	15.53 ms	1808 ms

В этой таблице p50 представляет собой медианное время завершения, а p75 и p90 показывают время, в течение которого уложились 75% и 90% запусков.
С prop_map время масштабируется почти линейно, когда мы переходим от пар к тройкам.
Но всего с одним дополнительным уровнем prop_flat_map производительность резко ухудшается, от менее чем 20 миллисекунд к почти 2 секундам!
Это более чем в 100 раз медленнее.

Разница в количестве итераций еще более поразительна:

Метрика	Пары (prop_map)	Тройки (prop_map)	Пары (prop_flat_map)	Тройки (prop_flat_map)
min	48	93	1228	11223
p50	215	306	6722	281016
p75	270	354	9315	481996
p90	310	410	10722	693358
max	387	530	12242	884729

От сотен итераций до почти миллиона! И мы здесь тоже работаем с довольно простыми структурами.
Еще один уровень prop_flat_map сделает минимизацию заметно медленнее, а следующий будет просто катастрофой.

Данные здесь охватывают несколько порядков величины. Хороший способ визуализировать этот тип данных — использовать CDF, построенной в логарифмическом масштабе. На этих графиках ось x показывает время или итерации, а ось y показывает кумулятивную вероятность.
Кривые, которые находятся правее, хуже, а логарифмический масштаб показывает, что различия находятся в порядках величины.

Кумулятивные функции распределения для пар и троек prop_map и prop_flat_map. Это логарифмическая шкала, поэтому различия находятся в порядках величин.

5. Переосмысление структуры

Что делает монадическую композицию такой сложной для работы? Это связано фактом, о котором упоминалось выше, вы можете писать все, что захотите внутри prop_flat_map.
Поскольку prop_flat_map может содержать произвольные вычисления внутри себя, и это вычисление возвращает совершенно новые стратегии, определение того, как значение будет уменьшаться, принципиально непредсказуемо без фактического его выполнения.

Другими словами, колбэк prop_flat_map довольно непрозрачен. Почему так?
Это потому, что колбэк prop_flat_map написан на Rust, который является мощным, Тьюринг-полным языком.
Невозможно полностью проанализировать семантику Тьюринг-полных языков[^5]. (Возможно вы знаете это как проблему остановки или теорему Райса.)

Но тот факт, что некоторый анализ требует решения проблемы остановки, — это всего лишь начало обсуждения, а не его конец!
Существует обширная литература о том, как находить приближенные решения для задач, которые в противном случае неразрешимы из-за теоремы Райса.
Для минимизации существует несколько подходов, которые, как известно, работают.

Один из вариантов — установить ограничения на то, как долго выполняется минимизация. Обратите внимание, что prop_flat_map не имеет проблем при генерации значений, только при их минимизации[^6].
Сама библиотека proptest устанавливает ограничения на стадии минимизации, особенно в экземплярах prop_flat_map.
Это гарантирует, что операции минимизации завершатся за разумное время, даже если они не приведут к минимальным значениям.

Лучшим вариантом будет переписать генераторы так, чтобы они не использовали монадическую композицию.
Для приведенного выше примера это не очень сложно[^7]:

fn better_generate_bad_type_pair() -> impl Strategy<Value = (BadType, BadType)> {
    // Создайте два экземпляра BadType.
    (
        generate_bad_type(),
        generate_bad_type(),
    )
    // Смотрите, никакого `prop_flat_map`! Это немонадическая композиция.
    .prop_map(|(bad1, mut bad2)| {
        // Добавьте `bad1.value` к `bad2.value`. Поскольку эти два числа неотрицательны
        // (целые числа без знака), это гарантирует, что `bad2.value` всегда
        // больше, чем `bad1.value`.
        bad2.value += bad1.value;
        (bad1, bad2)
    })
}

Но это может быть довольно проблематично по мере увеличения сложности! Библиотека proptest поставляется с рядом помощников для написания немонадических стратегий,
в частности prop_recursive и sample::Index. Но есть реальные ситуации, особенно с большими и сложными структурами данных
(например, случайно сгенерированными деревьями синтаксиса языка программирования), где ни один из этих вариантов не подходит, и вам придется использовать всю мощь prop_flat_map.

И последнее, но не менее важное: есть набор подходов, которые я собираюсь отнести к категории переосмысления структуры через flat_map-ы.
Ключ к ним — понимание того, что когда вы генерируете случайное значение, вы превращаете ГСЧ (RNG), который является случайным потоком битов, в конкретные, структурированные значения.
Можем ли мы придумать что-то поумнее, глядя на поток битов ГСЧ?

Один из вариантов — инструментировать тест, например, с помощью фаззера. Фаззинг (fuzzing) заключается в генерации случайных данных, анализе пройденных ветвей и корректировке случайных данных, чтобы гарантировать прохождение других ветвей. Это отлично подходит для того, чтобы пристальнее присмотреться к черному ящику монадической композиции.
Другой вариант — проявить смекалку с генератором случайных чисел. Случайное число в конечном итоге генерирует последовательность единиц и нулей. Можем ли мы поковыряться в этой последовательности, возможно, с помощью некоторых подсказок из самих стратегий? Это реализовано фреймворком Hypothesis для Python; см. прекрасную статью об этом.

Оба эти подхода эвристические и довольно сложные. Но это то, что вам нужно, чтобы снова собрать некоторую структуру, после того как она прошла через блендер монадической композиции.

Заключение: "constraints liberate, liberties constrain" [^8]

Автобан в Германии. Организованный транспортный поток и строгое следование полосам движения дают большую свободу: неограниченную скорость. Tarboosh/Wikimedia Commons

В этой статье мы рассмотрели монады как шаблон проектирования: способ для пользователя комбинировать операции в рамках системы.
Мы рассмотрели как монадические функции, такие как prop_flat_map, так и немонадические, такие как prop_map и prop_oneof.
Наконец, мы увидели, как в контексте PBT монадическая композиция оказывает существенное влияние на производительность.

Обладая этими знаниями, вы сможете теперь обнаружить монадическую композицию и в других местах:

Futures в Rust, где .await является монадическим, но futures ожидаются последовательно. Для параллельного запуска futures необходимо использовать немонадические операции, такие как future::join.
Некоторые системы сборки, в которых отдельные узлы сборки могут генерировать дополнительные узлы, что делает невозможным создание графа зависимостей без выполнения сборки. (Cargo, к счастью, немонадический.)
И даже с итераторами, где Iterator::map возвращает итератор с той же длиной, что и раньше, а filter_map возвращает итератор с той же или меньшей длиной, но длина flat_map не ограничена.
Option::and_then, Result::and_then и Result::or_else также являются монадическими операциями, хотя все они достаточно просты, чтобы не иметь никаких практических недостатков.

Общая черта всех этих примеров заключается в том, что в рамках системы монадическая композиция происходит не просто от значения к значению.
Она происходит от значения к следующему экземпляру этой системы. Возвращаемое значение future.await может привести к созданию большого количества объектов future,
монадические узлы сборки могут генерировать еще больше узлов сборки, а flat_map превращает отдельные значения в итераторы.
Эта свобода делает монады одновременно и самым гибким видом композиции, и самым сложным для предсказания их поведения.

Это часть общего наблюдения в программировании, когда происходит взаимодействие между двумя сторонами или двумя частями.
Чем больше ограничений на одной стороне, тем свободнее другая сторона может делать то, что ей нравится.
Монадическая композиция — это крайний случай, экстремальная версия: самая мощная и наименее ограниченная форма композиции для пользователя, но самая сложная для работы с системой.

Независимо от того, являетесь ли вы пользователем или разработчиком библиотеки, уделяйте пристальное внимание ситуациям, когда ваши операции являются монадическими.
Они могут обеспечить большую мощь; возможно, слишком большую во многих обстоятельствах. Если немонадических операций достаточно для достижения вашей цели, предпочитайте их.

А когда их недостаточно: ну, теперь вы знаете, во что ввязываетесь!

Спасибо Fiona и Cliff Biffle за рецензирование черновиков этой статьи. Все ошибки в ней — мои собственные.
Обновлено 2025-02-20: Уточнено примечание о полноте по Тьюрингу, чтобы указать, что не сама композиция является полной по Тьюрингу — проблема заключается в языке, используемом для записи колбэка.

Приложение

Этот раздел содержит немного жаргона, но он в основном здесь для удовлетворения педантов, которые неизбежно будут нажимать Ctrl-F для «законов монадичности».
Пожалуйста, проигнорируйте этот раздел, если вы не попали сюда через поиск этой строки.

Формально, монады — это любая структура с двумя операциями return и bind, где эти операции подчиняются трем законам монадичности. Для Strategy эти функции будут:

fn return<T>(x: T) -> impl Strategy<Value = T>;

fn bind<U, ST, F, SU>(base: ST, f: F) -> impl Strategy<Value = U>
where
    ST: Strategy,
    F: Fn(ST::Value) -> SU,
    SU: Strategy<Value = U>;

Для стратегий return — Just, а bind — prop_flat_map.

Вот три закона монадичности, выраженные в терминах proptestа:

Left identity: для любого значения Just(value).prop_flat_map(f) должно быть эквивалентно f(value). Это действительно так, как для генерации, так и для минимизации. Поскольку Just не выполняет никакой минимизации, патологическое поведение prop_flat_map не проявляется.
Right identity: для любой strategy strategy.prop_flat_map(Just) должно эквивалентно strategy. Это также выполняется. Каждый раз, когда strategy минимизируется, prop_flat_map должен отбросить состояние, возвращаемое зависимой стратегией. Но Just — это тривиальная стратегия, которая не имеет никакого состояния, поэтому это фактически пустая операция (no-op).
Associativity: если у вас есть цепочка из двух prop_flat_map, вы можете применить вторую либо «внутри», либо «снаружи» первой. Более конкретно, для любой strategy, с определениями:

let strat1 = strategy.prop_flat_map(f).prop_flat_map(g);
let strat2 = strategy.prop_flat_map(|value| f(value).prop_flat_map(g));

этот закон требует, чтобы strat1 и strat2 были одинаковыми. Это также выполняется, как для генерации, так и для минимизации, хотя последнее увидеть немного сложнее.

Можно возразить, указав, что в Rust вышеприведенные операции приводят к разным типам, даже если они ведут себя одинаково.
Это верно, но также не особенно актуально, поскольку вы всегда можете вызвать Strategy::boxed, чтобы стереть тип.

Можно также отметить, что мы не говорили здесь о классе типов (typeclass) или трейте Monad. Это отвлекает!
Монадическая композиция существует повсюду в программировании, независимо от того, позволяет ли язык выразить Monad как конкретный тип.
Вы можете выразить Monad в современных версиях Rust через GAT (Generic Associated Types), но в этом действительно мало практической пользы.

Спасибо!

[^1]: Некоторые из этих примеров могут показаться слишком искусственными, чтобы их можно было встретить в реальном мире.
Но реализация, которая справляться с наихудшими входными данными, сможет также обрабатывать не столь плохие данные.
Функций сортировки промышленного уровня имеет смысл проектировать для случая наихудших из возможных входных данных.

[^2]: Это не моральный провал со стороны этих разработчиков, потому что свободной воли не существует. Это совершенно нормально и это стоит принять! Интегрированная минимизация изменяет окружение в процессе.

[^3]: Как и в случае с итераторами, сигнатуры типов также становятся довольно длинными!

[^4]: Значение по умолчанию opt-level, 0, подходит для prop_map, но недопустимо для prop_flat_map с тройками.

[^5]: Проблема не является специфичной для Тьюринг-полных языков, она существует даже в языках, таковыми не являющимися.
Например, если бы колбэк был написан на языке, в котором были бы только циклы for, без циклов while, система все равно не смогла бы заглянуть за пределы минимизатора.

[^6]: Я думаю, что это ключевое понимание, которое упускают многие руководства по монадам.
Когда пишешь о монадах, возникает соблазн сосредоточиться на простых примерах, таких как Option::and_then,
где монадическое поведение не имеет значительных практических последствий.
Здесь также, если мы ограничимся только генерацией значений, с prop_flat_map все в порядке. Проблемы монадической композиции проявляются только во время минимизации.
Если вы объясняете монады аудитории, подумайте о том, чтобы акцентировать внимание не только на том, что такое монады, но и на том, когда их неограниченная сила становится скорее недостатком, чем преимуществом.

[^7]: Если вы внимательно следите, вы можете заметить, что, хотя эта функция соответствует изложенным нами требованиям, генерируемое случайное распределение несколько отличается.
В данном случае можно получить распределение, эквивалентное примеру с prop_flat_map, используя sample::Index.

[^8]: Constraints Liberate, Liberties Constrain — Runar Bjarnason

Теги:

Хабы: