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

В Хаскеле как известно есть монады, а в 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 функциями и монадами довольно очевидна.