как работать с algebraic data types на C++

Landstreicher

Нужно реализовать некоторый аналог algebraic data types на C++.
Рассмотрим в качестве примера такой код на Haskell:

import qualified Data.Map as Map



data Expr = Const Double

          | Var String

          | Add [Expr]



type Env = Map.Map String Double



eval :: Expr -> Env -> Double

eval expr env =

    case expr of

      Const c -> c

      Var v -> env Map.! v

      Add lst -> sum (map (\e -> eval e env) lst)



compile :: Expr -> (Env -> Double)

compile expr = eval expr



e1 = Add [Var "x", Const 1, Var "y"]



env1 = Map.fromList [("x", 20 ("y", 30 ("z", 40)]



main = do

  let f = compile e1

  putStrLn $ show (f env1)

Суть в следующем — есть некоторый тип данных Expr, который наиболее удобно выражается через алгебраические типы данных. В реальности, конечно, это никакой не Expr, а сложный запрос к базе данных. Он представляется в виде дерева, листовые узлы которого — примитивные запросы, а нелистовые — арифметические или логические операция.
Как реализовать такой тип данных в C++? Классический метод, описанный во всех учебниках, состоит в следующем:

#include <vector>

#include <map>

#include <string>



typedef std::map<std::string, double> env_t;



class func

{

public:

  virtual double calculate(env_t& env) = 0;

  virtual ~func { }

};



class const_func : public func

{

public:

  const_func(double c_) : c(c_) { }

  virtual double calculate(env_t& env);

private:

  double c;

};



double const_func::calculate(env_t&)

{

  return c;

}



class var_func : public func

{

public:

  var_func(std::string var_) : var(var_) { }

  virtual double calculate(env_t& env);

private:

  std::string var;

};



double var_func::calculate(env_t& env)

{

  return env[var];

}



class add_func : public func

{

public:

  add_func(std::vector<func*> childs_) : childs(childs_) { }

  virtual double calculate(env_t& env);

private:

  std::vector<func*> childs;

};



double add_func::calculate(env_t& env)

{

  double result = 0;

  for (std::vector<func*>::iterator it = childs.begin; it != childs.end; ++it) {

    result += (*it)->calculate(env);

  }

  return result;

}



int main

{

  std::vector<func*> fvec;

  fvec.push_back(new var_func("x";

  fvec.push_back(new const_func(1;

  fvec.push_back(new var_func("y";

  func *f = new add_func(fvec);

  env_t env1;

  env1["x"] = 20;

  env1["y"] = 30;

  env1["z"] = 40;

  printf("%f\n", f->calculate(env1;

}

Такой подход будет правильно и достаточно быстро работать. Не будем обращать внимание на большое количество одинакового тупого кода — это особенность языка, и с ней, судя по всему, ничего не сделать (у кого есть идеи — пишите).
Однако, на практике применение такого способа вызывает три сложных вопроса.
Во-первых, непонятно как считать много функций. Сейчас по выражению считается только одна функция — вычислить выражение. На практике по выражению нужно считать не одну, а много функций. Например, в данном примере это может быть функция взятия производной:
derivative :: Expr -> Expr
(в исходной задаче это simplify_query :: Query -> Query, estimate_complexity :: Query -> Double и еще десяток).
При применении приведенного выше метода получается что-то такое:

class func

{

  ...

  virtual double calculate(env_t& env) = 0;

  virtual func* derivative = 0; // новая функция

};



class const_func : public func

{

  ...

  virtual double calculate(env_t& env);

  virtual func* derivative; // новая функция

};

...

func* const_func::derivative // новая функция

{

  return new const_func(0);

}

Нужно добавлять метод derivative во все классы. Если функций, которые обрабатывают запросы много (порядка 10-20 и они постоянно добавляются, то код нечеловечески разбухает.
Во-вторых, допустим, нужно сделать простенькую функцию типа такой:

is_const :: Expr -> Bool

is_const (Const c) = True

is_const _ = False

Поскольку _ сделать нельзя, то нужно добавлять новый виртуальный метод во все наследники, которых может быть много (более 10).
В-третьих, возникают проблемы с памятью. В том коде, который приведен, налицо утечки памяти. Должен ли add_func освобождать childs при своем удалении? Возможны оба варианта. Вариант, когда не стирает, может легко приводить к утечкам памяти. Вариант, когда стирает, может приводит к проблемам в случае сложных преобразований деревьев, когда часть вершин остается, часть меняется.
Чтобы избежать проблем с неуправляемым ростом числа виртуальных функций, можно попытаться сделать по-другому, например, так:

enum node_type {

  node_const = 0,

  node_var = 1,

  node_add = 2

};



struct node_t;



struct node_const_t

{

  double c;

};



struct node_var_t

{

  std::string var;

};



struct node_add_t

{

  std::vector<node_t*> childs;

};



struct node_t

{

  node_type ntype;

  union {

    node_const_t n_const;

    node_var_t n_var;

    node_add_t n_add;

  };

};



double calculate(node_t& node);

Такой способ плох по двум причинам.
1) Он противоречит всем канонам программирования на C++, в которых рекомендуется все switch/case такого типа заменять на виртуальные функции. Кроме того, нельзя нормально пользоваться конструкторами/деструкторами.
2) Это в принципе не может работать. Достаточно скомпилировать и посмотреть на ошибки:
error: member ‘node_var_t node_t::<anonymous union>::n_var’ with constructor not allowed in union
error: member ‘node_var_t node_t::<anonymous union>::n_var’ with destructor not allowed in union
error: member ‘node_var_t node_t::<anonymous union>::n_var’ with copy assignment operator not allowed in union
error: member ‘node_add_t node_t::<anonymous union>::n_add’ with constructor not allowed in union
error: member ‘node_add_t node_t::<anonymous union>::n_add’ with destructor not allowed in union
error: member ‘node_add_t node_t::<anonymous union>::n_add’ with copy assignment operator not allowed in union
В общем, как такое правильно делать в C++?
Кстати, для тех, кто знаком с Java/C# — как такое принято делать в этих языках?

Realist

1. Нечеловеческое разбухание кода — особенность С++. Полагаю, что ты просто переботал Haskell. Ибо можно было бы начать с проблемы номер ноль: программа на Хаскеле для одного метода calculate короче раза в 2 с половиной.
Бороться можно разделением классов по разным файлам. Ну или напиши транслятор с хаскеля на С++ для этой задачи.
2. Я, наверное, не понял, в чем вопрос-то? Переопредели этот метод только в одном наследнике — Const. В остальных путь будет базовый вариант, который истину возвращает.
3. Почему не предлагаешь использовать умные указатели?

smit1

Поскольку _ сделать нельзя, то нужно добавлять новый виртуальный метод во все наследники, которых может быть много (более 10).

bool func::is_const const

{

  return false;

}



bool const_func::is_const const

{

  return true;

}

Не так уж и ужасно вроде (?)

Dasar

ты хочешь код быстрый или понятный? C++ одиннаково плохо позволяет писать и так, и так.
потому что вот этот код можно записать и вот так:

is_const :: Expr -> Bool

is_const (Const c) = True

is_const _ = False

static bool is_const(Expr expr)

{

   return expr is const_func;

}

Landstreicher

static bool is_const(Expr expr)
{
return expr is const_func;
}
Это на каком языке программирования? И как такое сделать на C++?

Landstreicher

> Не так уж и ужасно вроде (?)
Ок, проблему с _ решили.
А что делать с другими функциями? Допустим у меня куча функций вида Expr -> Expr. Как мне их писать?

Dasar

> Это на каком языке программирования?
а это разве не плюсы?
> И как такое сделать на C++?

return dynamic_cast<const_func>(expr) != NULL;

Dasar

> А что делать с другими функциями? Допустим у меня куча функций вида Expr -> Expr. Как мне их писать?
ты лучше пальцем покажи, что хочешь..., хотя бы на haskell-е

bleyman

Я не смог прочитать весь код, но тот, что смог, поверг меня в смятение.
Откуда там дети вообще? Мне показалось, или ты что-то вроде арифметических операций делаешь? Так они ассоциативны и замечательно раскладываются в бинарное дерево, прикинь! Более того, если ты вдруг поищешь в интернетах кодовые слова вроде "C++ (lazy|delayed) evaluation", а то и поспрошаешь у ВМКшных чуваков третьего-четвёртого курса программистской направленности, то сможешь надыбать прекрасный код для отложенных матричных вычислений, который не то чтобы настоящие отложенные вычисления реализует, но по крайней мере существенно экономит на выделениях временной памяти. А тебе он будет полезен тем, что ты увидишь, как на плюсах нужно писать такие штуки.
Ежели ты ещё и какие-то дополнительные действия хочешь делать, изначально непредусмотренные, то возботай паттерн Visitor и аккуратненько проведи его по дереву.

KViH

А расскажи про задачу. Обертка с algebraic data types, это, наверное, конечно клево будет смотреться, но интересней что у вас в calculate, simplify_query, estimate_complexity. Требований к производительности нету, или у вас такая своебразная база, что эти методы можно реализовать с приемлимым качеством.

Landstreicher

> Откуда там дети вообще? Мне показалось, или ты что-то вроде арифметических операций делаешь? Так
> они ассоциативны и замечательно раскладываются в бинарное дерево, прикинь!
Выражения приведены для примера, на практике там более сложные вещи и узел дерева действительно может иметь много потомков.
> Более того, если ты вдруг поищешь в интернетах кодовые слова вроде "C++ (lazy|delayed)
> evaluation"
Искал, находится всякая фигня. Работоспособного кода не нашел. Скинь URL, плз.
> а то и поспрошаешь у ВМКшных чуваков третьего-четвёртого курса программистской направленности,
> то сможешь надыбать прекрасный код для отложенных матричных вычислений, который не то чтобы
> настоящие отложенные вычисления реализует, но по крайней мере существенно экономит на выделениях
> временной памяти. А тебе он будет полезен тем, что ты увидишь, как на плюсах нужно писать такие
> штуки.
Скинь мне это код? Или хотя бы напиши основную идею?
> Ежели ты ещё и какие-то дополнительные действия хочешь делать, изначально непредусмотренные, то
> возботай паттерн Visitor и аккуратненько проведи его по дереву.
Как мне может помочь паттерн Visitor? По-моему, от него код только разбухнет, а лучше не станет.
Приведи какой-нибудь пример, показывающий, как он может помочь.

Landstreicher

> А расскажи про задачу.
Ок. Есть некоторые данные, например, документы, файлы — не важно. Они заиндексированы, по ним производится поиск по запросам вида "(СОДЕРЖИТ СЛОВА "AA", "ББ") AND (СОЗДАН НЕ РАНЕЕ 2006 г) AND (НА РУССКОМ ЯЗЫКЕ) AND NOT (ОТНОСИТСЯ К ТЕМЕ "ФЛУД")". На вход поступает запрос в виде текстовой строки, он парсится в дерево, после чего несколько раз преобразуется. Затем некоторым образом (каким именно неважно) достаются индексы по всем условиям в листовых узлах. Далее происходит проверка соответствия запросу. Проверку сделать достаточно просто. Далее — самое интересное — подсчет релевантности документа. Фишка в том, что релевантность документа D по запросу Q_1 AND Q_2 НЕ ЕСТЬ некоторая простая функция от релевантности по запросу Q_1 и релевантности по запросу Q_2, а считается более хитро, в зависимости от структуры Q_1 и Q_2. Сейчас как раз основной затык — как грамотно написать функцию подсчета релевантности. Как писать подобную функциональность на Haskell — я понимаю, как на C++ — нет (т.е. какой-то вариант я могу написать, но он уродский и мне не нравится).
> Обертка с algebraic data types
Почему обертка? Это не обертка, это самый что ни на есть настоящий algebraic data type и есть.
> но интересней что у вас в calculate, simplify_query, estimate_complexity
simplify_query — функция, которая упрощает запросы, например (A OR B) AND A преобразует в A.
Есть функции, которые A AND B могут превращать в B AND A и т.п, чтобы было потом быстрее искать.

bleyman

Прочитал внимательно, кажется понял, что ты хочешь.
Ты хочешь построить какое-то дерево операций, которое умеет не только вычислять собственное значение, но и какие-то дополнительные штуки с собой делать, типа значение производной считать, например. Так?
Причём это дерево изначально строится динамически, так что мой совет про delayed evaluation можешь смело пропускать мимо ушей — он был про то, как можно написать хитроумные классы, которые вместо непосредственных вычислений как раз строят дерево, ну, чтобы можно было писать a = b + c * d прямо в виде кода, а оно бы на самом деле строило структуру выражения и вычисляло её с оптимизациями всякими. Но тут не то, видимо.
Так вот. У меня такое ощущение, что ты черезмерно усложняешь задачу, пытаясь писать всеобъемлющий универсальный код, строго следующий ООП-гайдлайнам. Дело хорошее, конечно...
Во-первых, может быть всё-таки сделать операции строго бинарными? Они ж на самом деле такие и есть в underlying SQL-запросе, разве нет?
Во-вторых, может быть всё-таки разделить данные и операции? Типа есть у тебя дерево, отлично. А операция — это один метод, который по дереву бродит и что-то считает именно так, как хочется. В явном виде то есть бродит. И уже потом, когда у тебя получается большой однородный switch, ты можешь его отрефакторить в виртуальные функции — кстати, если ты вдруг не знал, виртуальные функции не обязаны быть абстрактными =) Причём рефакторить, опять же, не в полном объёме, а только то, что нужно, например если тебе нужно считать какую-нибудь хитроумную фигню типа суммы значений и производных с коэффициентами, можно загнать в виртуальные функции вычисление значения и производной, а вычисление, собственно, этой взвешенной функции оставить внешним, в том методе, который обходит дерево. То есть как только switch исчезает, уже больше ничего виртуализировать не надо.
Паттерн Visitor, по сути, позволяет не писать каждый раз код обхода дерева для разных таких внешних функций.

Dasar

. А операция — это один метод, который по дереву бродит и что-то считает именно так, как хочется. В явном виде то есть бродит.

как минимум еще нужны преобразования дерева, и как раз обычно с преобразованиями и засада.

kokoc88

Нужно реализовать некоторый аналог algebraic data types на C++.

Мне кажется, что такие вещи делаются только на шаблонах. Впрочем, я бы нашёл императивное решение задачи, потому что даже простой пример с adt деревом выглядит, мягко говоря, объёмно и убого. Например, node мог бы выглядеть примерно так:

template<class tl, class tr>

tree<tl, tr> node(tl left, tr right)

{

	return tree<tl, tr>(left, right);

} 

Дерево можно было бы конструировать вот так:

node(empty node(node(leaf	leaf empty

Причём это ещё без проверок типов tl и tr, которые надо ограничить каким-то множеством. Мало того, большая часть объявлений будет compile-time, а поэтому ты замучаешься писать всякие обёртки для хранения произвольных типов, получающихся после разворачивания шаблонов. Да и все функции для работы с деревом будут тоже шаблонными, с условиями останова.

В-третьих, возникают проблемы с памятью. В том коде, который приведен, налицо утечки памяти. Должен ли add_func освобождать childs при своем удалении? Возможны оба варианта. Вариант, когда не стирает, может легко приводить к утечкам памяти. Вариант, когда стирает, может приводит к проблемам в случае сложных преобразований деревьев, когда часть вершин остается, часть меняется.

Используй boost::shared_ptr для хранения данных. Поскольку у тебя древовидная структура данных, кольцевых ссылок быть не должно.

Не будем обращать внимание на большое количество одинакового тупого кода — это особенность языка, и с ней, судя по всему, ничего не сделать (у кого есть идеи — пишите).

Ты вряд ли избавишься от большого количества кода для написания класов. Впрочем, при этом можно добиться вполне приемлемого кода использования, например, задавать дерево вот так:

arg_ptr func = mul

    [

        add [ val(11.0 val(5.0 val(9.0) ],

        add [ val(5.0 val(6.0) ]

    ];

И ещё я согласен, что стоит применять Visitor. Тебе всё равно надо описать методы вычисления различных функций над каждой вершиной дерева. Если ты уверен, что какой-то функции не будет, можно написать пустые заглушки. При грамотной реализации ты даже сможешь делать преобразования дерева. Но в таком случае надо долго думать, как сделать это производительно.

kokoc88

Скинь мне это код? Или хотя бы напиши основную идею?

В общем, можно написать код, на котором можно делать так:

		arg_ptr func = mul

				add val(11.0 val(5.0 val(9.0) 

				add var("x" var("y" add val(5.0 val(1.0)  

			;

		tenv env;

		env["x"] = 1.5;

		env["y"] = 3.5;

		derivative dx("x");

		derivative dy("y");

		null_method null;

		cout << "calculate: " << get(env, func) << endl;

		cout << "calculate derivative by x: " << get(env, func->invoke(&dx << endl;

		cout << "calculate null method: " << get(env, func->invoke(&null << endl;

		arg_ptr func2 = mul var("x" var("x" var("x") ;

		cout << "calculate cube: " << get(env, func2) << endl;

		cout << "calculate derivative by y: " << get(env, func2->invoke(&dy << endl;

		cout << "calculate derivative by x: " << get(env, func2->invoke(&dx << endl; 

Если хочешь, я могу тебе его прислать.