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

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

    Похожие публикации

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 15

      +6
      Сложно, многословно, медленно, утекает память.
        –2
        Да, на Haskell проще :-).
          +4
          Сложно, многословно, медленно, утекает память.

          Хокку
          +2
          Какое-то сумбурное изложение мыслей. Непонятно что и зачем. Я конечно хаскель не знаю, но почему-то есть чувство, что тащить функциональщину в таком виде в C++ просто не стоит. С++ является процедурным языком программирования. И не стоит тащить функциональщинку в процедурщину. Да, функциональный подход используется в компайл-тайм метапрограмминге, но в вашем случае на всю катушку используется рантайм.

          Ну и в статье такие сумбурные вещи написаны, что я чуть со стула не упал.

          >> Основная идея классов типов в отделении реализации интерфейса от структуры данных.
          Основная идея интерфейсов в отделении реализации от объявления.

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

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

          Больше не смотрел, сил не хватило.

          Посмотрите на boost.mpl, посмотрите нормально на реализацию stl и не городите огороды, описанные вещи делаются элементарно, без какой-либо функциональщины.
            +4
            >> Основная идея классов типов в отделении реализации интерфейса от структуры данных.
            Основная идея интерфейсов в отделении реализации от объявления.

            Зря вы так.
            Основная суть интерфейсов — подключать интерфейсы к классам объектов.
            А основная суть классов типов — подключать интерфейсы отдельно от класса объекта.
              +1
              Классы типов не связаны с функциональным программированием.

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

              «Функциональщины», кроме использования указателей на функции и примеры на Haskell, в этой статье нет. Все вполне императивно.
                0
                Это как Extention methods из C# что ли?
                  0
                  Может быть. На C# не смотрел, но слышал что там много интересного.
                    0
                    Extention method не сделает целевой класс реализующим нужный интерфейс. Классы типов позволяют делать тип Т реализующим интерфейс И, не изменяя ни Т, ни И.
                    Классы типов больше похожи на шаблон Адаптер, только неявный.
                      0
                      Классы типов это и делают.
                  0
                  При чтении таких статьях мне всё время мерещится картинка с троллейбусом и буханкой…
                    0
                    Если интересно:
                    C++Concepts — отвергнутое предложение о введении концептов (аналог классов типов) в C++
                      0
                      Страуструпп не любит вводить новые конструкции, если их можно хоть как-то выразить через старые. Его сложность и многословность не пугают.
                        +2
                        я так понимаю, это устаревшая тяжеловесная реализация.
                        Есть гораздо более легковесное предложение, у которогое возможно будущее: Concepts Lite: Constraining Templates with Predicates.
                        Бьёрн рассказывал о нём на GoingNative 2013 (о концептах примерно с 1:00:00).
                      0
                      del

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

                      Самое читаемое