Монады и do-нотация в C++

в 6:29, , рубрики: Без рубрики

В Хаскеле как известно есть монады, а в C++ их нет. Но ничто не мешает реализовать монады в С++. Посмотрим есть ли у нас всё необходимое для их реализации:

  • Передача функции как аргумент в другую функцию – есть.
  • Лямбда-функции – есть, добавлены в C++11. Я не уверен, что они необходимы для реализации монад, но с ними, несомненно, проще.
  • Type classes – нет. В C++ хотели добавить их аналог – концепты, но пока не добавили. Но для реализации монад они не нужны, можно просто перегружать функции или операторы под конкретные монады.
  • do-нотация. В C++ её нет, но для реализации монад она не нужна, хотя и делает их использование гораздо более удобным. Уже есть предложение добавить её аналог в стандарт, но об этом ниже.


Монада в Haskell определяется следующим образом:

class Monad m where
	(>>= ) ::m a -> (a->m b)->m b
	(>> ) ::m a->m b->m b
	return ::a->m a
	fail::String->m a

Для начала возьмём некую абстрактную монаду, пусть в C++ она имеет тип Monad<T>. Посмотрим, как будут выглядеть соответствующие функции.

template<typename A, typename B>
Monad<B> operator>>=(Monad<A> ma, function<Monad<B> (A)> f)
{
	... // реализация зависит от монады
}

Эта функция извлекает значение из объекта ma, подставляет в функцию f и возвращает результат f.

template<typename A, typename B>
Monad<B> operator>>(Monad<A> ma, Monad<B> mb)
{
    return Ma >>= [=](A){ return mb; };
}

Эта функция аналогична функции >>=, но она игнорирует значение извлечённое из первой монады. У этой функции есть стандартная реализация (m >> k = m >>= _ -> k), которую я перевёл с Haskell на C++.

template<typename A>
Monad <A> mreturn(A a)
{
    ... // реализация зависит от монады
}

Слово return является зарезервированным в C++, поэтому я назвал эту функцию mreturn. Смысл этой функции в том, что она помещает объект a в некий минимальный контекст для данной монады.
Функция fail нужна для обработки ошибок, чтобы не загромождать эту статью я её опущу.

Итак, теперь понятно как будут выглядеть монады на C++, настало время взять какую-нибудь конкретную монаду и реализовать для неё эти функции. Можно конечно начать с монад типичных для Хаскеля — Maybe, список и др., но меня больше интересует std::future. Этот класс был добавлен в C++11. Объект типа future<T> позволяет получить доступ к объекту типа T, который будет доступен в будущем. Это может быть, например, результат вычисления какой-то очень сложной функции, которая долго вычисляется в другом потоке, или результат ввода, например информация, которая должна будет поступить по сети. Из всего класса future нас будет интересовать только функция get.

template<class T>
class future
{
public:
    ...
    T get(); // функция get дожидается пока будет доступен объект и возвращает его
    ...
};

Также в C++11 появилась новая функция – std::async. В качестве аргумента она принимает функцию, запускает её в другом потоке и возвращает её результат в std::future. То есть можно писать код навроде этого:

future<int> result = async(f);
// делаем какие-то операции одновременно с вычислением функции f
int a = result.get(); // дожидаемся выполнения функции f и получаем её рузультат.

Теперь нам не составит труда реализовать функции mreturn и >>= для монады std::future

#include <future>
using namespace std;

template<typename A>
future<A> mreturn(const A& a)
{
	return async([=]{ return a; });
}

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

template<typename A, typename B>
future<B> operator>>=(future<A>& ma, const function<future<B> (A)>& f)
{
	return async([&] () -> B { return f(ma.get()).get(); });
}

Здесь немного посложнее, мы создаём новый поток, в котором дожидаемся пока будет готово значение из ma, потом передаём это значение в функцию f, затем ждём пока будет готово значение возвращённое из f.

Реализация готова, осталось проверить выполняются ли аксиомы монад. Всего у нас 3 аксиомы, которые на Хаскеле выглядят так:

Left identity : return a >>= f == f a
Right identity: m >>= return == m
Associativity: (m >>= f) >>= g == m >>= (x -> f x >>= g)

Переводим первую аксиому на C++, получается:

(mreturn(a) >>= f) == f(a)

Подставим наши функции, получим:

async([&] () -> B { return f(mreturn(a).get()).get(); }) == f(a)

Ясно, что mreturn(a).get() это тоже самое, что а. Эта конструкция просто помещает a в std::future, а затем извлекает его оттуда. Упрощаем, получаем:

async([&] () -> B { return f(a).get(); }) == f(a)

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

Вторая аксиома:

m >>= mreturn == m

Подставим наши функции, получим:

async([&] () -> B { return mreturn(m.get()).get(); }) == m

Мы опять можем избавиться от mreturn(x).get(), получим:

async([&] () -> B { return m.get(); }) == m

Теперь ясно, что выражение слева эквивалентно m. Оно просто создаёт поток, который дожидается пока будет доступно значение из m.

Третья аксиома:

(m >>= f) >>= g == m >>= (x -> f x >>= g)

Рассматривать подробно третью аксиому мне уже лень, но грубо говоря, она означает следующее. В выражении слева к фьючеру m навешивается функция f, которая будет выполнена, когда будет доступно значение из m. Затем на полученную конструкцию вешается функция g, которая будет выполнена после f. В выражении справа функции f и g сперва объединяются в одну функцию и затем уже она вешается на фьючер m.

С аксиомами мы разобрались. Теперь можно написать какой-нибудь бессмысленный код с нашей монадой:

function<future<int> (int)> f = [](int a){ cout << a << 'n'; return mreturn(a + 6); };
int a = (mreturn(5) >>= f).get();
cout << a;

Как и ожидалось, этот код выводит 5 и 11.

В C++11 нет функций аналогичных написанным мной mreturn и >>=. Но есть предложение добавить подобные функции: n3721
Аналогом mreturn будет make_ready_future.
Аналогом >>=, будет функция класса std::future под названием then. Основное её отличие в том, что она принимает аргумент не типа A, а типа future<A>. Это сделано для обработки ошибок, если нужное значение так и не будет сгенерировано, то получится future<A> содержащий ошибку и функция, переданная в then, сможет его обработать.
Также планируется добавить функцию unwrap которая сможет преобразовывать значения типа future<future<A>> в future<A>. Это аналог join из Control.Monad в Хаскеле.

Использование then может стать весьма нетривиальной вещью:

future<int> f(shared_ptr<stream> str) 
{ 
    shared_ptr<vector<char>> buf = ...; 
    return str->read(512, buf).then([](future<int> op) 
    {
        return op.get() + 11; 
    }); 
} 

future<void> g() 
{ 
    shared_ptr<stream> s = ...; 
    return f(s).then([s](future<int> op) 
    { 
        s->close();
    }); 
} 

Сразу так и не поймешь, что тут происходит, и это у нас ещё нет условных операторов и циклов. Для решения этой проблемы были предложены resumable функции: n3722. С ними этот кусок кода будет выглядеть так:

future<int> f(stream str) resumable
{ 
    shared_ptr<vector<char>> buf = ...; 
    int count = await str.read(512, buf); 
    return count + 11; 
} 
future<void> g() resumable
{ 
    stream s = ...; 
    int pls11 = await f(s); 
    s.close(); 
} 

Ключевое слово resumable означает, что это определение функции, которая может быть прервана, а затем её вычисление может быть продолжено. Самое интересное здесь это await – это аналог стрелки влево (<-) в do нотации в Хаскеле. Заметьте, что и str.read и f возвращают значения типа future<int>, но после применения к ним await получается int, аналогично работает и стрелка влево в Хаскеле.

Как же всё это должно работать? Та статья, в которой это предлагается, даёт два возможных пути для реализации: первый из них основан на создании дополнительного стека под каждую resumable функцию, аналогично тому, как работают Fibers в Windows или boost::coroutine. Второй способ более эффективный, интересный и сложный для реализации. В этом случае каждая resumable функция будет как-бы разбиваться на составляющие в местах, в которых находится await. Так, что каждый await будет вызывать соответствующий then и передавать ему в качестве аргумента функцию, которая начинается после await. Это позволит использовать resumable функции не только с std::future, но и с любыми типами у которых есть методы then и get. Тогда можно будет использовать и другие монады на C++, хотя возможно проблемы могут возникнуть с теми монадами, где требуется копирование функции, как например, в монаде список. Сложно сказать будет ли вообще смысл в использовании других монад помимо std::future.
Что интересно, в статье предлагающей resumable функции ни разу не упоминается слово монада. Видимо её авторы не знают что это такое, так как связь между resumable функциями и монадами довольно очевидна.

Автор: stepik777

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js