среда, 9 октября 2019 г.

[prog.c++] Что-то я неслабо затупил из-за отсутствия fold expression в C++14

Столкнулся со следующей задачей: есть экземпляр std::tuple, который содержит объекты-парсеры. Нужно пробежаться от первого элемента тупла к последнему и для каждого парсера вызвать метод try_parse с определенными параметрами. Но! Нужно прервать эту итерацию как только очередной try_parse вернет false.

В C++17 это элементарно записывается посредством fold expression:

templatetypename Tuple, std::size_t... Indexes >
bool try_parse_impl(
   const std::string & source,
   Tuple & t, 
   std::index_sequence<Indexes...>)
{
   return (... && std::get<Indexes>(t).try_parse(source));
}

templatetypename... F >
bool try_parse(const std::string & source, std::tuple<F...> & parsers)
{
   return try_parse_impl(source, parsers, std::index_sequence_for<F...>());
}

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

А вот как сделать тоже самое, но в C++14, где fold expression нет?

Единственное, что у меня пока вышло -- это вот такое:

templatebool valid_index, std::size_t I >
struct try_parse_impl
{
   templatetypename... Parsers >
   static bool apply(const std::string & source, std::tuple<Parsers...> & t)
   {
      if( std::get<I>(t).try_parse(source) )
         return try_parse_impl< (I+1 < sizeof...(Parsers)), I+1 >::apply(source, t);
      else
         return false;
   }
};

template< std::size_t I >
struct try_parse_impl< false, I >
{
   templatetypename... Parsers >
   static bool apply(const std::string &, std::tuple<Parsers...> &)
   {
      return true;
   }
};

templatetypename... F >
bool try_parse(const std::string & source, std::tuple<F...> & parsers)
{
   return try_parse_impl< (0 < sizeof...(F)), 0 >::apply(source, parsers);
}

Возможно, вместо всего этого как-то можно было бы обойтись более прямой работой с std::index_sequence. Но что-то для этого моего понимания механизма распаковки параметров в variadic templates не хватает. И примеры, которые я находил в Интернетах не очень помогают, т.к. там идет итерация по всем элементам тупла, без анализа результата на очередной итерации и прерывания цикла.

Поиграться с полным примером можно здесь.

PS. Специально для желающих лишний раз уличить меня в том, что программист из меня никакой: узбагойтесь, хорошим программистом я перестал себя считать уже очень и очень давно. Возможно, еще даже до рождения некоторых из моих персональных хейтеров. Программирую как могу. К сожалению, у многих вокруг получается еще хуже, хотя я предпочел бы, чтобы было наоборот.

16 комментариев:

Stanislav Mischenko комментирует...

Позволю предложить свой вариант. Код ещё времён C++11 (gcc 4.4). Если не скомпилируется, то заранее прошу прощения, на плюсах с тех пор не прогал. Кстати, если, конечно несложно, подскажите, что бы прочитать, дабы наверстать упущенное?
https://pastebin.com/AVDEFNu4

NN​ комментирует...

Как только появилась возможность использовать выражения свёртки весь этот ужасный код был выброшен :)
Кстати, лучше использовать шаблон вместо прямого std::tuple, тогда и классы вроде std::pair можно будет обработать.

template class Tuple, typename... Types >
bool try_parse(const std::string & source, Tuple & parsers)

Grigory Demchenko комментирует...

Потролю немного: это все из-за того, что C++ позволяет легко реализовывать простые вещи и ты не задумываешься по нескольку часов и не спрашиваешь коллег о том, как сделать что-то настолько элементарное. Это говорит о мощи и элегантности языка.

eao197 комментирует...

@Grigory Demchenko

Интересно было бы посмотреть на то, как проход по туплу с объектами неизвестного типа реализуется в:

a) других статически типизированных языках;
b) других статически типизированных языках без GC.

eao197 комментирует...

@Unknown

Насколько я понял, ваш код -- это что-то типа std::accumulate, но только для частного случая с парсерами. И, опять же насколько я понял, у вас вызов try_parse будет выполняться для всех парсеров в тупле. Т.к. я не увидел прерывания итерации, если какой-то из try_parse вернет false.

Что почитать не подскажу, т.к. где-то года с 2014-го в основном читаю блоги, ссылки на которые время от времени проскакивают на reddit-е. Отсюда и какое-то представление о возможностях современного C++.

Stanislav Mischenko комментирует...

> Насколько я понял, ваш код -- это что-то типа std::accumulate,

да

> но только для частного случая с парсерами.

нет, как и accumulate, код работает с любым предикатом, в примере это лямбда.

>И, опять же насколько я понял, у вас вызов try_parse будет выполняться для всех парсеров в тупле. Т.к. я не увидел прерывания итерации, если какой-то из try_parse вернет false.

Вы правы, единственно что, вызывается несколько раз лямбда, а не try_parse; try_parse больше не вызовется, после того как предыдуший вернул false. Чтобы сделать, как Вы хотите, мне надо было бы написать tuple_all, который бы работал как std::all_of().

А вообще моё предложение в улущение кода заключается как раз в написании небольшого набора таких вот функций типа tuple_reduce, tuple_all, и использовать только их. Таким образом неважно какой страшности там код, ибо он в одном месте, и его легко поменять. А в остальных местах, где используются функции, код компактный и лаконичый, и не надо вспоминать как там раскрывать эти tuple-ы каждый раз.

eao197 комментирует...


> нет, как и accumulate, код работает с любым предикатом, в примере это лямбда.

Это я неправильно выразился.

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

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

Pavel комментирует...

Привет, Евгений

Можно воспользоваться идей tuple iterator и применить std::all_of() для всех указателей на функции try_parse, сгенерированных для каждого из элементов кортежа в initializer_list.

К сожалению, применить constexpr к получающемуся initializer_list не получается, так что остается только надеяться, что компилятор сможет это как-то соптимизировать. Зато без рекурсивных воплощений шаблонов :)

https://wandbox.org/permlink/LLAAzsDPXXl0yHSN

eao197 комментирует...

@Pavel

Приветствую!

Прикольное решение, спасибо! Заставило напрячь мозги чтобы понять, что именно здесь происходит.

Pavel комментирует...

Да, код не очень понятным получился, лень было разбираться с типами, использовал везде auto.

Продублирую здесь с явными типами. Идея та же - переносим обработку элементов кортежа в runtime. Для этого создаем initializer_list с указателями на функции try_parser_at для доступа к каждому элементу кортежа, и ищем первую функцию, вернувшую false, с помощью стандартной std::all_of.

Не знаю только, возможно ли в принципе избавиться от вспомогательной try_parse_impl() с пачкой индексов в шаблоне.
Wandbox

template
bool try_parser_at(const std::string & source, Tuple & parsers)
{
return std::get(parsers).try_parse(source);
}

template
bool try_parse_impl(const std::string & source, Tuple & parsers, std::index_sequence)
{
using try_parser_func_ptr = bool(*)(const std::string & source, Tuple & parsers);

const std::initializer_list try_parsers =
{
&try_parser_at...
};

return std::all_of(try_parsers.begin(), try_parsers.end(),
[&source, &parsers](try_parser_func_ptr try_parser)
{
return try_parser(source, parsers);
});
}

template< typename... F >
bool try_parse(const std::string & source, std::tuple & parsers)
{
using Indexes = std::make_index_sequence;
return try_parse_impl(source, parsers, Indexes{});
}

Alexander комментирует...

Ещё вариант: https://pastebin.com/Lyya4fDy

eao197 комментирует...

@Alexander

> Ещё вариант: https://pastebin.com/Lyya4fDy

Очень прикольно, спасибо большое!

Я, правда, озадачился другим вопросом: а есть ли здесь гарантии того, что все будет выполняться в нужном порядке. Ведь, по сути, там происходит следующее:

initializer_list&lf;bool> a = {
result && (result = get<0>(parsers).try_parse(source)),
result && (result = get<1>(parsers).try_parse(source)),
result && (result = get<2>(parsers).try_parse(source)),
...
};

Внутри каждого выражения вычисления должны идти слева направо (хотя нет уверенности в том, что здесь нет UB, т.к. result и читается, и пишется в одном выражении). Но вот то, что все эти выражения должны вычисляться от индекса 0 к индексу N, а не наоборот, в этом у меня уверенности нет.

Alexander комментирует...

Насколько я понимаю написанное здесь, a && b и {a, b} вычисляются так, что все side-эффекты вычисления a заканчиваются до начала вычисления b (пункты 6 и 10 соответственно)

eao197 комментирует...

@Alexander

Ага, спасибо за ссылки. Действительно, пункты 6 и 10 показывают, что должно быть все нормально.

Но подумалось вот о чем: если в этот initializer-list попадает 20 выражений, из которых на практике надо бы вычислить только 3, то вычисляться-то будут всегда 20. Но 3 полноценно, с вызовом try_parse, а у остальных 17 будет вычисляться только левый операнд в &&. Но все равно будет.

На практике эти расходы вряд ли будут иметь значение. Но сам факт...

Alexander комментирует...

Да, тут остаётся надеяться только на компилятор. C -O0 он, похоже, проходится по всем элементам, а вот уже с -O1 идёт сразу на выход функции, если она вернула false: https://godbolt.org/z/Zo19Qp

Alexander комментирует...

если try_parse вернула false