Монады и 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. Посмотрим, как будут выглядеть соответствующие функции.
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, который будет доступен в будущем. Это может быть, например, результат вычисления какой-то очень сложной функции, которая долго вычисляется в другом потоке, или результат ввода, например информация, которая должна будет поступить по сети. Из всего класса 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. Это сделано для обработки ошибок, если нужное значение так и не будет сгенерировано, то получится future содержащий ошибку и функция, переданная в then, сможет его обработать.
Также планируется добавить функцию unwrap которая сможет преобразовывать значения типа future<future> в future. Это аналог 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, но после применения к ним await получается int, аналогично работает и стрелка влево в Хаскеле.

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

Подробнее
Реклама
Комментарии 26
  • +3
    Думаю, что не хватает ссылки FTL — The Functional Template Library
    • +1
      Приятно, что открытия, совершённые Хаскелем более 15 лет назад наконец-то внедряются в мейнстримовые языки программирования
      • +2
        Честно говоря, после C#, Java и прочих современных управляемых языков программирования, смотреть на синтаксис C++ лично мне, все-таки страшно
        • +1
          Зато С++ всё так же работает быстрее, даже если сравнивать C++ с C++, т.е. код на C++11, благодаря семантике перемещения, будет работать быстрее чем код на C++03, а вообще, конечно же, ждём развития D до более менее адекватного состояния.
          • 0
            А в чем там принципиальная разница кроме управляемости, которая не везде в плюс работает?
        • 0
          Не очень элегантно, но классы типов выражаются через аргументы поумолчанию.
          Примерно так:
          template <M> class monadVTBL {
           template <v,x> M<x> bind(v, function<M<x> (M<x>)) = 0;
           template <v> M<v> mreturn(v) = 0;
          }
          
          template<M,x,v> M<x> bind(v i, function<M<x> f(M<x>), monadVTBL<M> tbl = new monadVTBL<M>()) { return tbl.bind(i, f); }
          template<M,v> M<v> mreturn(v i, monadVTBL<M> tbl = new monadVTBL<M>()) { return tbl.mreturn(i); }
          


          А потом специализируем monadTBL для инстансов наших монад.
          По большому счеты Haskell почти так же внутри делает. С небольшими оптимизациями.

          PS на плюсах давно не писал, сейчас проверю компилируемость…
          • 0
            Исправил код
            template <template<typename _> class M, typename v, typename x> class monadVTBL {
             M<x> bind(v, M<x>(*)(M<x>)) = 0;
             M<v> mreturn(v) = 0;
            };
            
            template<template<typename _> class M, typename x, typename v> M<x> bind(v i, M<x>(*f)(M<x>), monadVTBL<M,v,x> tbl = new monadVTBL<M,v,x>()) {
             return tbl.bind(i, f);
            }
            template<template<typename _> class M, typename v> M<v> mreturn(v i, monadVTBL<M,v,void> tbl = new monadVTBL<M,v,void>()) {
             return tbl.mreturn(i);
            }
            
            • 0
              Увлекаетесь скалой? Вы уверены, что это работает? У класса по умолчанию все члены закрытые. Типы у последних аргументов и их значений по-умолчанию в функциях не совпадают.

              Как уже сказал автор статьи, гораздо удобнее и проще монады в с++ реализовать через перегрузку функций.
              • 0
                Не то, что бы увлекаюсь — скорее использую :-). Но Вы правы — этот прием я от туда почерпнул.
                Через перегрузку кое-что теряется. Не получится написать функцию, которая работает с абстрактной монадой, не зная ее конкретный тип. Например как в Haskell:
                example :: (Monad m, Show x) => m x -> m String
                example i o =
                   do
                     x <- i
                     return (show x)
                
                • 0
                  template<typename M, typename T>
                  M<std::string> example(M<T> const& mx)
                  {
                      using monad::map;
                      return map(show, mx);
                  }
                  


                  Что есть o (второй аргумент example) в вашей функции?
                  • 0
                    o — опечатка.

                    А от куда example узнает имплементацию show для типа T?
                    • 0
                      Да, действительно. Первое, что приходит в голову — как-то совместить вывод типов с type erasure, но я не уверен, что это будет работать…
                      template< template<typename _> class M, typename T >
                      M<std::string> example(M<T> const& mx)
                      {
                      	using monad::map;
                      	const std::function<std::string(T)> f = show;
                      	return map(f, mx);
                      }
                      


                      Другой вариант — сделать show шаблонным function object и полагаться на частичные специализации (show<T> f; map(f, mx);), но это не очень в духе с++.
          • +5
            В Хаскеле как известно есть монады, а в C++ их нет

            Монады — это абстракция, они существуют в нашей голове. Средств для явного выражения абстракции монад в с++ нет. Но нужны ли они там? Мне кажется, нет. В C++ другие средства выражения тех же идей, зачем навязывать чуждые ему концепции?

            Возьмём, к примеру, Monoid. В c++ для представления monoid достаточно иметь конструктор по умолчанию и оператор + (желательней, правда, +=). И всё, можно писать простой обобщённый код.
            • +4
              А можно для ржавых сиприплюсников объяснить что такое эта ваша монада и зачем она нужна? А то из статьи в вики я ничего не понял.

              О функциональном программировании знаю только то, что оно существует. Не обессудьте.
              • 0
                В чистом функциональном языке монады используются чтобы получать вычисления, зависимые от ранее вычисленного.
                Или более обще — чтобы получать вычисления в контексте.

                А зачем они нужны плюсам — ещё не до конца понял из статьи.
                По идее может оказаться удобным инструментом для асинхронных вычислений.
                • +5
                  Монада это абстрактная структура (нечто вроде группы в абстрактной алгебре), которая относительно легко поддаётся линейной композиции. Как и в абстрактной алгебре, для определения требуется тип (в случае монады — параметризованный, т.е. шаблонный) и операции над ним. Для начала удобно представлять себе монаду в виде коробки с объектом типа t внутри (шаблонный тип с одним параметром — типом box).

                  Операции включают в себя:
                  1. Операция — единичка. Берёт простой объект типа t и помещает его в коробку box.
                  2. Операция применения (map). Если нам дают коробку box с объектом и функцию t2 f(t), операция map должна применить функцию к объекту внутри коробки и вернуть результат box.
                  3. Операция связывания (bind). Если нам дают коробку с объектом box и функцию box f(t), bind сможет вытащить объект из коробки и подставит его в f, получив новую коробку box.

                  На примере асинхронных вычислений:
                  1. Единичка берёт объект t и возвращает готовый фьючерс async.
                  2. Map берёт фьючерс async и функцию t2 f(t) и возвращает новый фьючерс async, объект в котором получается применением функции f к результату первого фьючерса при его готовности. Это по сути планирующийся then.
                  3. Bind берёт async и возвращает async, полученный ожиданием t из async и применением f к тому, что получилось.

                  Смысл монад в том, что можно написать довольно много обобщённого кода, которых будет работать для многих типов и операций, внешне не связанных, но обладающих похожей структурой. Примеры скрытых монад: std::vector, boost::optional, std::future. Идея в чём-то отражает намерения Степанова, при написании STL. Как итераторы приводят к многим универсальным алгоритмам, так монады приводят к многим управляющим структурам, поддающимся композиции.
                  • +1
                    ну вот, хабр съел мои <t> и <t2>

                    Операции включают в себя:
                    1. Операция — единичка. Берёт простой объект типа t и помещает его в коробку box<t>.
                    2. Операция применения (map). Если нам дают коробку box<t> с объектом и функцию t2 f(t), операция map должна применить функцию к объекту внутри коробки и вернуть результат box<t2>.
                    3. Операция связывания (bind). Если нам дают коробку с объектом box<t> и функцию box<t2> f(t), bind сможет вытащить объект из коробки и подставит его в f, получив новую коробку box<t2>.
                    • 0
                      Хм, а map через bind разве нельзя выразить?

                      Например, вот так на Scala
                      trait M[T] {
                        def map[S](f: T => S): M[S] = flatMap(t => M(f(t)))
                        // ...
                      }
                      

                      • +1
                        Можно.
                        В моей последней статье на Хабре Löb и möb: странные петли в Хаскел я дал код как определён код функции fmap для функтора списков:
                        instance Functor [] where
                            fmap = map
                        


                        Если у нас есть монада, тогда существует и функтор, который можно определить так:
                        instance Monad m => Functor m where
                           fmap = liftM
                        

                        где
                        liftM :: Monad m => (a -> b) -> m a -> m b
                        liftM f m  = m >>= return . f
                        


                        Теперь если допустить, что у нас есть bind для списка, тогда можно пере-определить map

                        map = liftM
                        
                        • +1
                          Вообще, если под map понимать fmap, то монаду теоретически можно определить 2 путями

                          — через return
                          и
                          1) — bind
                          2) — fmap; — join

                          То есть альтернативно bind определяется так:
                          (>>=) :: Monad m => m a -> (a -> m b) -> m b
                          m >>= g ≡ join ((fmap g) m)
                          

                          • 0
                            Причём математическое определение, как правило, использует join, т.к. он проще и нагляднее. Я так понимаю, в Haskell используют bind напрямую, т.к. он важнее с точки зрения практического программирования и его можно реализовать эффективнее.
                            • 0
                              Прежде всего потому, что Функтор не является (всё ещё) суперклассом Монаде, ведь кроме join надо определить ещё и fmap
                              • 0
                                Мне, кстати, в Haskell часто не хватает возможности сказать «любой инстанс класса X является также инстансом класса Y вот таким образом».
                                • 0
                                  Сейчас уже можно так написать, но это всё ещё плохо работает ((
                                  С помощью следующих расширений:
                                  -XUndecidableInstances
                                  -XOverlappingInstances
                                  и возможно,
                                  -XIncoherentInstances
                  • 0
                    Я вот одного не понял, зачем для фьючерсов нужна фукнция mreturn.
                    По идее просто надо в определение bind добавить, что если значение не в асинхронном режиме, то не вытаскиваем его из этого режима, а используем как есть.
                    • 0
                      У Лейбница было понятие — монада всех монад.
                      Здесь такое есть?

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.