Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

Anna | 24.06.2014 | нет комментариев

В Хаскеле как вестимо есть монады, а в 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; });
}

То есть, Дабы поме/code> из 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, подобно работает и стрелка налево в Хаскеле.

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

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB