- Передача функции как аргумент в другую функцию – есть.
- Лямбда-функции – есть, добавлены в 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 функциями и монадами довольно очевидна.
This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers.
Комментариев нет:
Отправить комментарий