Классы типов на C++

Уже было описано как реализовать монады на C++ без классов типов. Я же хочу показать, как можно реализовать классы типов, использую в качестве примера монады.

Этот прием широко применяется в языке Scala, но может быть использован и в C++. Кратко я его описал в качестве иллюстрации трудностей унифицированного описания библиотек, сейчас же продемонстрирую его реализацию.

Нужно отметить что классы типов применяются не только в декларативных языках, как Haskell и Mercurry, но о нашли свое отражение в достаточно классических Go и Rust.

Этот прием так же подходит для реализации мультиметодов из Common Lisp и Clojure.

C++ я не брал в руки уже лет шесть, так что код может быть не идеоматичным и не использовать новые (полезные) фичи.

Кроме того, я полностью игнорирую проблему управления памятью — практикующие C++ справятся с этим лучше меня.

Работоспособность кода проверялась на gcc 4.7.3.

Основная идея классов типов в отделении реализации интерфейса от структуры данных. Один и тот же интерфейс может использоваться для работы с совершенно разными структурами данных, и для каждого типа данных должен реализовываться отдельно. Код, использующий этот интерфейс, не обязан знать подробности его реализации.

С монадами сложности добавляет то, что этот интерфейс реализуется для обобщенного типа, параметризованного другим типом.

Реализация интерфейса должна где-то храниться, а у нас для этого есть только классы:

#include <stddef.h>

template <template<typename _> class M> class monadVTBL {
public:
 template<typename v, typename x> static M<v> bind(M<x>, M<v>(*)(x));
 template<typename v> static M<v> mreturn(v);
};

template<template<typename _> class M, typename v, typename x> M<v> bind(M<x> i, M<v>(*f)(x), monadVTBL<M> *tbl = NULL) {
 return monadVTBL<M>::bind(i, f);
}

template<template<typename _> class M, typename v> M<v> mreturn(v i, monadVTBL<M> *tbl = NULL) {
 return monadVTBL<M>::mreturn(i);
}

Как мы видем, реализация передается в использующие ее функции в качестве дополнительного параметра со значением поумолчанию. В данном случае нам достаточно только типа этого параметра (по этому он всегда NULL), и мы могли бы перенести его в локальную переменную. Использование параметра дает дополнительную гибкость, которая при некотором старании позволит сэкономить память на инстанцирование шаблонов (функции придется спрятать в классы, наследующие реализацию обобщенных функций через void*) и пригодится для реализации мультиметодов.

template <template<typename _> class M> M<char> inc(char c) { return mreturn<M,char>(c+1); }

Достаточно простая функция, использующая монаду.

На Haskell она вызлядит

inc :: (Monad m) => Char -> m Char
inc c = return (succ c)

return здесь обозначает совсем другое, чем в C++.

А теперь перейдем к реализации монады IO. Объекты, с которыми работает монадный интерфейс в данном случае — операции вводв-вывода. В Haskell это обычные величины, в C++ они будут моделироваться классами.

#include<stdio.h>

template<typename v> class IOop {
public:
 virtual v run() = 0;
};

template<typename v> class IOm {
public:
 IOop<v> *op;
 IOm(IOop<v> *o) {
  op = o;
 }
 v run() {
  op->run();
 }
};

Метод run выполняет эту операцию (в Haskell фактически он вызывается runtime-системой у объекта main).

Класс-контейнер IOm нужен, что бы спрятать тип операции, который может быть переменного размера.

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

class getChar: public IOop<char> {
public:
 getChar() {}
 virtual char run() {
  return getchar();
 }
} _getChar[1];
IOm<char> getChar(_getChar);

typedef class unit { } unit;
unit Unit;

class _putChar: public IOop<unit> {
 char v;
public:
 _putChar(char c) {
  v = c;
 }
 virtual unit run() {
  putchar(v);
  return Unit;
 }
};
class IOm<unit> putChar(char c) { IOm<unit> o(new _putChar(c)); return o; };

А вот две конкретные операции ввода-вывода — получить символ со стандартного ввода и вывести символ на стандартный вывод. А так же функция, которая превращает символ в операцию, которая его выводит.

template<typename v> class mconst: public IOop<v> {
 v r;
public:
 mconst(v x) {
  r=x;
 }
 virtual v run() {
  return r;
 }
};

Этот класс реализует монадическую операцию «return», которая в данном случае создает операцию ввода-вывода, которая всегда «вводит» константу.

template<typename v, typename i> class mbind: public IOop<v> {
 IOop<i> *s;
 IOm<v> (*f)(i);
public:
 v run() { return (*f)(s->run()).run(); }
 mbind(IOop<i> *x, IOm<v> (*g)(i)) {
  s=x;
  f=g;
 }
};

А эта операция ">>=", которая сцепляет монаду с генератором новой монады.

template<> class monadVTBL<IOm> {
public:
 template<typename v, typename i> static IOm<v> bind(IOm<i> x, IOm<v>(*f)(i)) { IOm<v> b(new mbind<v,i>(x.op,f)); return b; }
 template<typename v> static IOm<v> mreturn(v x) { IOm<v> r(new mconst<v>(x)); return r; }
};

А вот и самое главное — специализация реализации монады для IO.

template<typename i> IOm<unit> ignNL(i v) {
 return bind<IOm,unit,char>(mreturn<IOm,char>('\n'),putChar);
}

Это генератор IO, который игнорирует результат предыдущей монады и печатает '\n'.

ign :: a -> IO ()
ign _ = putChar '\n'

Для IO (и некоторых других монад, например парсеров) это игнорирование предыдущей монады достаточно популярная операция и для нее есть функция:

(>>) :: (Monad m) => m a -> m b -> m b
a >> b = a >>= \_ -> b

А теперь проверим, как все это работает:

bind<IOm,unit,unit>(bind<IOm,unit,char>(bind<IOm,char,char>(getChar,inc),putChar),ignNL<unit>).run();

Мы читаем со стандартного ввода символ, его инкрементируем, печатаем, и печатаем перевод строки.

А теперь реализуем интерфейс монады для другого класса, который знает о монадах еще меньше.

#include<vector>

template<typename v> class myvector: public std::vector<v> { };

К сожалению, шаблон std::vector имеет два параметра (второй отвечает за политику аллокации и может подставляться поумолчанию). Современный gcc не позволяет его передавать в шаблон, который ждет шаблон с одним параметром (если мне память не изменяет, раньше таких строгостей не было). По этому приходится создавать простую обертку.

template<> class monadVTBL<myvector> {
public:
 template<typename v, typename i> static myvector<v> bind(myvector<i> x, myvector<v>(*f)(i)){
  myvector<v> e;
  for(typename myvector<i>::iterator it = x.begin(); it != x.end(); ++it) {
   myvector<v> c = f(*it);
   for(typename myvector<v>::iterator i = c.begin(); i != c.end(); ++i) {
    e.push_back(*i);
   }
  }
  return e;
 }
 template<typename v> static myvector<v> mreturn(v x) {
  myvector<v> e;
  e.push_back(x);
  return e;
 }
};

Функциональность монады std::vector аналогична функциональности монады List в Haskell.

Пробуем, как это работает:

 myvector<char> x;
 x.push_back('q');
 x.push_back('w');
 x.push_back('e');
 myvector<char> z = bind<myvector,char,char>(x,inc);
 for(typename myvector<char>::iterator i = z.begin(); i != z.end(); ++i) {
  std::cout << *i;
 }

Для подобной функциональности было бы достаточно класса типов «функтор», но мне не хотелось придумывать более сложный пример.

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.