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

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

Anna | 24.06.2014 | нет комментариев
Теснее было описано как реализовать монады на 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 имеет два параметра (2-й отвечает за политику аллокации и может подставляться поумолчанию). Теперешний 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;
 }

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

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

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