Классы типов на 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;  } 

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