Re[15]: Generators in C++, (a.k.a. foreach & iteartors) - C/C++

По следам плодотворной дискусии про итераторы...

Используя идею "coroutines in C" Simon Tatham вот родилось следующее решение для C++.

Прежде всего пример генератора:


#include "generator.h"

generator(desc) 
{
   int i;
   emit(int) // будем выдавать int'ы
     for (i = 10; i > 0; --i)
       yield(i); // a.k.a. yield in Python - return next number in [10..1]
   stop(0); // все, конец последовательности.
};

При вызове оного "оператор" yield выдает следуещее число последовательности. Используется например так:

Пока есть следующее число печатаем его:

int main(int argc, char* argv[])
{
  desc gen;
  do
    printf("got number %d\n", gen());
  while (gen);
  return 0;
}

Вот весь исходник generator.h:


// generator/continuation for C++
// author: Andrew Fedoniouk @ terrainformatica.com
// idea borrowed from: "coroutines in C" Simon Tatham, 
//                     http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html

#ifndef __generator_h_
#define __generator_h_

struct _generator
{
  int _line;
  _generator():_line(-1) {}
  operator bool() const { return _line != 0; }
};

#define generator(NAME) struct NAME : public _generator

#define emit(T)     T operator()() { \
                     if(_line < 0) { _line=0;}\
                     switch(_line) { case 0:;

#define stop(V)     } _line = 0; return (V); }

#define yield(V)     \
        do {\
            _line=__LINE__;\
            return (V); case __LINE__:;\
        } while (0)


#endif // __generator_h_

Вот другой пример: сканируем последовательность:

generator(backward) 
{
   int *head;
   int *tail;
   backward(int *start, int *end ): head(start), tail(end){}

   emit(int)
     while(--tail > head) 
         yield(*tail);
   stop(*tail);
};

int main(int argc, char* argv[])
{
  int arr[] = {1,2,3,4,5,6};
  backward scan(&arr[0],&arr[6]);
  do 
    printf("got number %d\n", scan());
  while(scan);
  return 0;
}

Вот такие вот пироги.

Здравствуйте, Gluk_Kazan, Вы писали:

G_K>Пошел посыпать голову пеплом

G_K>Как этот case в середину цикла вообще работает ???

switch в С и С++ -- это такой род goto. Работает тогда же, когда и goto, кстати...

Меня забавляет другое. Люди, которые против использования goto, даже если и по делу, как дети рады использованию его аналога, да ещё и хитрых довольно макросов

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, remark, Вы писали:

R>>С рекурсией ещё проще:

E>А разве так

struct waw {
E>    std::vector<waw> Oh;
E>};

можно?

Тебе какие-то религиозные убеждения запрещают так делать? Или что-то более материальное?

Здравствуйте, c-smile, Вы писали:

CS>По следам плодотворной дискусии про итераторы...
У меня такое ощущение что этому коду дальше идеи не уйти и что в нормальном проекте за его использование будут отрубать пальцы по самые уши

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, remark, Вы писали:

R>>А ну да. i и inner надо вынести в переменные класса

E>Ну вот это-то мне тут и не нравится..
E>Но дальше миссер, дальше...
E>

class CPlusPlusPorno {
E>    CPlusPlusPorno inner;
E>};

точно не скомпилируется...

Ну ладно-ладно, туплю. Нужен auto_ptr, как ты сказал.

Здравствуйте, gear nuke, Вы писали:

GN>Здравствуйте, remark, Вы писали:

R>>Это уже Сapriccio Thread, это тупиковый вариант

GN>Не смотрел даже

испугали слова "нереальный анализ потребления стека функциями".

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

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

GN>ИМХО не надо искать серебрянную пулю (некоторые автоматы вообще руками писать не стоит) а под конкретные задачи размер стека можно прикинуть... Я лишь хотел сказать что контекст копировать — это всё равно что
GN>

GN>volatile int global;

GN>int main()
GN>{
GN>  int i;
GN>  global = 2;
GN>  i = global;
GN>}
GN>

Здравствуйте, remark, Вы писали:

R>Здравствуйте, Erop, Вы писали:

CS>>>Думаю про решение которое и красивое и эффективное.

E>>Мне эффективно и поддерживаемо...

R>Переделать на массив дочерних узлов, я надеюсь, особого труда не составит...

Кстати, в результате попытки использовать эту штуку в реальной ситуации вскрылось несколько проблем.

1. Почему "do {...} while (gen);", а не "while (gen) {...};"? А если последовательность пустая?!

2. Попытка вызвать в теле цикла gen() несколько раз приводит в очень неинтуитивному результату. Хотелось бы что бы новый элемент получался только после прохождения итерации, т.е. после вызова gen.operator bool().

3. Необходимость передавать в макрос stop() реальный элемент. Очень не удобно. Очень. Выход из функции должен означать конец последовательности, никаких элементов уже не должно быть.

R>

Здравствуйте, anonim_44ax, Вы писали:

_>К сожалению даже так можно:

_>

_>При этом, сей код под MS VS 7.1.3 не только компиллируется, но и успешно работает.

То, что это работает, это я проверил. Вопрос — насколько это соотв. стандарту. Ну или хотя бы будет работать на других компиляторах?

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

template<typename T>
class vector
{
  char buf [sizeof(T)];
  ...
};

siv>>Увы, не хватает "динамического goto" какого-нибудь:
CS>В GCC кстати такой goto есть. И там можно все это построить без наворотов со switch.
CS>Там можно взять адрес label и по нему перейти — goto *label.
Да, с ним всё просто и красиво. Вот, чуточку доработал один из твоих вариантов на предмет VC/G++ и поддержки switch/case :

#ifndef __generator_h_
#define __generator_h_

#include <boost/preprocessor/cat.hpp>

struct _generator
{
    void * _addr;
    _generator():_addr(0) {}
};

//------------------------------------------------------------------------------
#define $generator(NAME) class NAME : protected _generator

//.......
/// \note NB: Remember! The values of local varaibles are not preserved between
///       generator() invocation. Use them with precaution or use class members.
#define $emit(T)    bool operator()(T& _rv)              \
                    {                                    \
                      GOTO_GENERATOR_LABEL               \
                      {
//.......
#define $yield(V)       do {                             \
                          _rv = (V);                     \
                          SAVE_ADDR;                     \
                          return true;                   \
                      GENERATOR_LABEL:;                  \
                        } while (0);
//.......
#define $stop         }                                  \
                     _addr = 0;                          \
                     return false;                       \
                   }

//------------------------------------------------------------------------------
/// auxiliary macroses
#define GENERATOR_LABEL BOOST_PP_CAT(generator_label_,__LINE__)

#if defined(_MSC_VER)
# define  GOTO_GENERATOR_LABEL                           \
    if ( _addr )                                         \
    {                                                    \
      void * addr = _addr;                               \
      __asm                                              \
      {                                                  \
        __asm jmp addr                                   \
      }                                                  \
    }

# define SAVE_ADDR \
    {                                                    \
      void * pAddr = &_addr;                             \
      __asm                                              \
      {                                                  \
        __asm mov ebx, dword ptr [pAddr]                 \
        __asm mov eax, OFFSET GENERATOR_LABEL            \
        __asm mov dword ptr [ebx], eax                   \
      }                                                  \
    }

#elif defined(__GNUC__)
# define  GOTO_GENERATOR_LABEL                           \
    if ( _addr )                                         \
    {                                                    \
      void * addr = _addr;                               \
      goto *addr;                                        \
    }

# define SAVE_ADDR                                       \
    {                                                    \
      void * addr = &&GENERATOR_LABEL;                   \
      _addr = addr;                                      \
    }
#else
# error You have to check a support of "goto *label" on your platform or implement it yourself.
#endif

#endif // __generator_h_

//=============================================================================
#include <stdio.h>

$generator(desc)
{
  int m_i;

public:
  desc( int start=-1 ) : m_i(start) {}

  $emit(int) 
  {
    for(; m_i >= 0; --m_i)
    {
      switch ( m_i )
      {
        case 9 : case 7 :
          $yield( m_i + 100 );
        break;

        case 5:
          $yield( m_i + 100000 );
        break;
      
        default:
          $yield( m_i );
      }
      $yield( m_i );
    }
  }
  $stop  
};


int main(int argc, char* argv[])
{
  desc gen( 11 );
  int i;
  while(gen(i))
  {    
    printf("got number %d\n", i);
  }
}

Здравствуйте, remark, Вы писали:

CS>>В общем случае нужен stack on the heap.

CS>>Для C++ по всей видимости вполне себе будет достаточно объявления _generator как CRTP
CS>>структуры/шаблона плюс поле _generatror<NAME>* _stack.

CS>>Это точно будет работать — т.е. можно и рекурсивные вызовы делать (но только себя самого)

R>А можешь привести полную реализацию с примером использования. А то пока это всё не складывается в единое целое...

Вот generator с поддержкой restart — рекурсивный рестарт себя самого.

template<typename T>
  struct _generator
  {
    T* _stack;
    int _line;
    _generator():_stack(0), _line(-1) {}
    void _push() { T* n = new T; *n = *static_cast<T*>(this); _stack = n; }
    bool _pop() { if(!_stack) return false; T* t = _stack; *static_cast<T*>(this) = *_stack; t->_stack = 0; delete t; return true; }
    ~_generator() { while(_pop()); }
  };

  #define $generator(NAME) struct NAME : public _generator<NAME>

  #define $emit(T) bool operator()(T& _rv) { \
                      if(_line < 0) _line=0; \
                      $START: switch(_line) { case 0:;

  #define $stop  } _line = 0; if(_pop()) goto $START; return false; }

  #define $restart(WITH) { _push(); _stack->_line = __LINE__; _line=0; WITH; goto $START; case __LINE__:; }

  #define $yield(V)     \
          do {\
              _line=__LINE__;\
              _rv = (V); return true; case __LINE__:;\
          } while (0)

Используется так (обход дерева):

struct node
{
   int   value;
   node* next;
   node* kid;
   node(int v):value(v), next(0), kid(0) {}
   node* foster( node* child ) { child->next = kid; kid = child; return child; }
};

$generator(scan)
{
  node* n;
  scan( node* root = 0 ): n(root) {}

  $emit(int)
    for(;n; n = n->next)
    {
      $yield(n->value);
      if( n->kid )
        $restart( n = n->kid );
    }
  $stop
};

int main(int argc, char* argv[])
{
  node * root = new node(0);
  root->foster(new node(1));
  root->foster(new node(2));
  root->foster(new node(3));
  root->foster(new node(4));
  node * child5 = root->foster(new node(5));
  root->foster(new node(6));
  root->foster(new node(7));
  root->foster(new node(8));
  root->foster(new node(9));

  child5->foster(new node(50));
  child5->foster(new node(51));
  child5->foster(new node(52));
  child5->foster(new node(53));

  scan g(root);
  for(int n; g(n);)
      printf("n = %d\n",n);
    return 0;
}

Усовершенствования возможны.

Здравствуйте, remark, Вы писали:

R>В любом случае — ну замени ты std::vector<iterate_tree_rec_t> на std::vector<iterate_tree_rec_t*>, чего ты придираешься — рекурсия на лицо.

Просто интересно зачем там массив. IMHO и auto_ptr<iterate_tree_rec_t> хватит

Здравствуйте, remark, Вы писали:

R>>Это на основе немного пропатченой версии — сейчас я её запосчу.

R>http://gzip.rsdn.ru/forum/message/2967473.1.aspx

А вот моя обновлённая версия.
Решает проблему stop значения.

  //++ coroutine, generator, continuation for C++

  struct _generator
  {
    int _line;
    _generator():_line(-1) {}
  };

  #define $generator(NAME) struct NAME : public _generator

  #define $emit(T) bool operator()(T& _rv) { \
                      if(_line < 0) { _line=0;}\
                      switch(_line) { case 0:;

  #define $stop  } _line = 0; return false; }

  #define $yield(V)     \
          do {\
              _line=__LINE__;\
              _rv = (V); return true; case __LINE__:;\
          } while (0)

  //-- coroutine, generator, continuation for C++

Генератор описывается как:

$generator(sample_gen)
{
  int n;
  $emit(int) 
    for(n = 10; n >= 0; --n)   
      $yield(n);
  $stop
};

Использование такое же как и в JS — for(var i in seq)

int main(int argc, char* argv[])
{
  sample_gen gen;
  
  for(int n;gen(n);)
      printf("got number = %d\n",n);
    return 0;
}

Здравствуйте, siv, Вы писали:

siv>Увы, не хватает "динамического goto" какого-нибудь:

В GCC кстати такой goto есть. И там можно все это построить без наворотов со switch.
Там можно взять адрес label и по нему перейти — goto *label.

Здравствуйте, Erop, Вы писали:

E>Так не интересно. Для этого нет нужды городить генератор. У тебя и так состояние явно выписано, да ещё и в узле индекс хранить надо

Если нет нужды держать index (мне лично он нужен ибе есть селекторы типа li:nth-child(n)) то дерево наверное надо делать
как двухсвязный список:

  strict node { node* child, *prev, *next;  };

В этом случае последовательность можно тоже линеаризовать достаточно тривиально.

E>Нет уж. Узел выглядит так:

strict node { array<node*> subs; };

И никаких поблажек!

Это challenge, надо думать.

Здравствуйте, Erop, Вы писали:

CS>>Думаю про решение которое и красивое и эффективное.

E>Мне эффективно и поддерживаемо...

typedef unsigned value_t;

struct node
{
   node* left_;
   node* right_;
   value_t value_;
};

generator(iterate_tree_t) 
{
    node* curr;
    std::vector<node*> node_queue;

    iterate_tree_t(node* root) : curr (root) {}

    /** Depth-first iteration over tree
     *  Time complexity: O(N)
     *  Average space complexity: O(log N)
     *  Worst space complexity: O(N)
     */
    emit(node*)
        if (curr)
        {
            node_queue.clear();
            node_queue.reserve(128);
            
            for (;;)
            {
                yield(curr);

               if (curr->left_ && curr->right_)
               {
                   node_queue.push_back(curr->right_);
                   curr = curr->left_;
               }
               else if (curr->left_)
               {
                   curr = curr->left_;
               }
               else if (curr->right_)
               {
                   curr = curr->right_;
               }
               else
               {
                   if (node_queue.empty())
                       break;
                   curr = node_queue.back();
                   node_queue.pop_back();
               }
            }
       }
    stop(0);
};

int main()
{
    node tree [4] = {};
    
    tree[0].value_ = 11;
    tree[0].left_ = &tree[1];
    tree[0].right_ = &tree[2];

    tree[1].value_ = 21;
    tree[1].left_ = &tree[3];
    tree[1].right_ = 0;

    tree[2].value_ = 22;
    tree[2].left_ = 0;
    tree[2].right_ = 0;

    tree[3].value_ = 31;
    tree[3].left_ = 0;
    tree[3].right_ = 0;

    iterate_tree_t iter (&tree[0]);
    do
    {
        node* n = iter();
        if (n)
            std::cout << "node: " << n->value_ << std::endl;
        else
            std::cout << "[end]" << std::endl;
    }
    while (iter);
}

Переделать на массив дочерних узлов, я надеюсь, особого труда не составит...

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, remark, Вы писали:

R>>В любом случае — ну замени ты std::vector<iterate_tree_rec_t> на std::vector<iterate_tree_rec_t*>, чего ты придираешься — рекурсия на лицо.

E>Просто интересно зачем там массив. IMHO и auto_ptr<iterate_tree_rec_t> хватит

Если подумать, то должно прокатить прямо так:

generator(iterate_tree_rec_t, node*) 
{
    node* root;

public:
    iterate_tree_rec_t(node* root)
        : root (root)
    {}

    emit(node*)
        if (0 == root)
            return;

        yield(root);

        for (size_t i = 0; i != root->children_.size(); ++i)
        {
               iterate_tree_rec_t inner (root->children_[i]);
               while (inner.next())
                    yield(inner.value());
        }
    stop_emit();
};

По-моему вполне читаемо и поддерживаемо...

Здравствуйте, c-smile, Вы писали:

CS>Используя идею "coroutines in C" Simon Tatham вот родилось следующее решение для C++.

Очень занятно. Сам не так давно думал над подобным, но почему-то опрометчиво раньше времени подумал, что в С++ с таким подходом ничего хорошего не выйдет. Тем не менее пока все попытки "сломать" этот код успехом не увенчались. Как минимум выдается варнинг. Пробовал вставлять определение локальной переменной с инициализацией, без инициализации, break.
Кстати, если есть цикл и внутри него ветка case и стоит break, это определено, что break будет относиться к циклу, а не к case?

Кто-нибудь может это сломать???

Что бы не было даже варнинга на самом высоком уровне предупреждений.

Собственно а подумал я, что ничего хорошего не выйдет, т.к. 3 известные мне реализации yield() в С/С++ все страдают серьезными проблемами.

Первая — это в Cilk. Но там используется специальный препроцессор, который генерирует код для запоминания/восстановления стековых переменных. Работает соотв. только для С.
http://supertech.csail.mit.edu/papers/cilk5.pdf
На Figure 3 видно, какой код генерирует препроцессор. Помимо запоминая PC (_line), так же запоминаются все локальные переменные.

Вторая — это в библиотеке Сapriccio. Но там они пытаются делать нереальный анализ потребления стека функциями и в итоге делают честную подмену/восстановление стека.
http://capriccio.cs.berkeley.edu/pubs/capriccio-sosp-2003.pdf

Третья — это в библиотеке Protothreads. Там они честно говорят, что потоки бесстековые, т.е. если хотите локальные переменные — перерассчитывайте их заново после каждого yield(). Реализация, кстати, по-ходу практически один в один с этой.
http://www.sics.se/~adam/pt/

Здравствуйте, remark, Вы писали:

R>Здравствуйте, c-smile, Вы писали:

CS>>Используя идею "coroutines in C" Simon Tatham вот родилось следующее решение для C++.

R>Очень занятно. Сам не так давно думал над подобным, но почему-то опрометчиво раньше времени подумал, что в С++ с таким подходом ничего хорошего не выйдет.

"Imagination is more important than knowledge" (C) Альберт.
В том смысле что иногда полезно отвлечься на tiscript какой от голого C++.

R>Тем не менее пока все попытки "сломать" этот код успехом не увенчались. Как минимум выдается варнинг. Пробовал вставлять определение локальной переменной с инициализацией, без инициализации, break.

Да, в c++ в этом смысле даже удачнее получилось чем в C.

R>Кстати, если есть цикл и внутри него ветка case и стоит break, это определено, что break будет относиться к циклу, а не к case?

break относится к ближайшему циклу или switch.

R>Собственно а подумал я, что ничего хорошего не выйдет, т.к. 3 известные мне реализации yield() в С/С++ все страдают серьезными проблемами.

Да, protothreads выглядят симпатично.

Но мой вариант с классом/структурой позволяет не заморачиваться с аллокациями. Да и переменные контекст естественнее выглядят.

Здравствуйте, c-smile, Вы писали:

CS>По следам плодотворной дискусии про итераторы...

Не этим ли кодом навеяно?

Качество кода open-source

Решено: щас всё брошу, пойду изучать, как делаются континюэйшены в лиспе.

... << RSDN@Home 1.2.0 alpha rev. 655>>

Здравствуйте, c-smile, Вы писали:

CS>По следам плодотворной дискусии про итераторы...

Пошел посыпать голову пеплом

Как этот case в середину цикла вообще работает ???

Здравствуйте, Erop, Вы писали:

E>switch в С и С++ -- это такой род goto. Работает тогда же, когда и goto, кстати...

Уже посмотрел во что ассемблируется.
Получил порцию культурного шока

E>Меня забавляет другое. Люди, которые против использования goto, даже если и по делу, как дети рады использованию его аналога, да ещё и хитрых довольно макросов

Собственно некоторое время назад была на работе тема посмотреть PuTTY на предмет криптографии
Ага, чую во что бы это вылилось

Здравствуйте, remark, Вы писали:

R>Но там используется специальный препроцессор, который генерирует код для запоминания/восстановления стековых переменных.

SwitchToFiber решает именно эту задачу в виндовсе. Решения здесь пробегали...

Здравствуйте, Vain, Вы писали:

V>Здравствуйте, c-smile, Вы писали:
CS>>По следам плодотворной дискусии про итераторы...

V>У меня такое ощущение что этому коду дальше идеи не уйти и что в нормальном проекте за его использование будут отрубать пальцы по самые уши

А нормальный проект это какой?
Эта абстракиция позваляет сократить количество вызовов и размер кода. Иногда значительно.
Скажем сложные FSM (finite state machine) парсеры (push/pull).

Или вот чего далеко ходить: есть дерево DOM элементов, достаточно хитрое местами.
Нужно написать функцию (хотя бы тот же итератор), который принимает на вход фильтр и позволяет обходить это дерево.
Количество разных FSM состояний из которых возможен выход по yield() — примерно десяток.

Здравствуйте, c-smile, Вы писали:

CS>А нормальный проект это какой?
Это который простой до такой степени, что большенству программеров разобраться в нём не составляет особого труда.
CS>Эта абстракиция позваляет сократить количество вызовов и размер кода. Иногда значительно.
Это абстракция добавляет ещё один способ зашифровать исходники

CS>Или вот чего далеко ходить: есть дерево DOM элементов, достаточно хитрое местами.
CS>Нужно написать функцию (хотя бы тот же итератор), который принимает на вход фильтр и позволяет обходить это дерево.
CS>Количество разных FSM состояний из которых возможен выход по yield() — примерно десяток.
Скажите сначало почему вам так хочется прикрутить yield к C++?

Здравствуйте, c-smile, Вы писали:

CS>Вот такие вот пироги.

Очень хорошо. Как написать что-нибудь рекурсивное? Например обход дерева в глубину?

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, c-smile, Вы писали:

CS>>Вот такие вот пироги.

E>Очень хорошо. Как написать что-нибудь рекурсивное? Например обход дерева в глубину?

Если дерево состоит из

struct node 
{ 
  node*         parent;
  int           index;
  array<node*>  subs;
};

То generator выглядит так:

  $generator(node_iterator)
  {
    node* root;
    node* c;
    node* t;
    int   n;
    node_iterator( node* root_node ): root(root_blk) { }

    $emit(node*)
       n = 0; c = root;
       while( c )
       {
         for(; n < c->subs.size(); ++n )
         {
            t = c->subs[n];
            $yield(t);
            n = 0; c = t;
         }
         if( c == root )
           break;
         n = c->index + 1; c = c->parent;
       }
    $stop(0)
  };

(я переименовал макросы $generator, $emit, $yield и $stop во избежание конфликтов)

В реале у меня такй генератор несколько сложнее ибо используется еще два фильтра skip_node и accept_node.

Здравствуйте, c-smile, Вы писали:

CS>Здравствуйте, Erop, Вы писали:

E>>Здравствуйте, c-smile, Вы писали:

CS>>>Вот такие вот пироги.

E>>Очень хорошо. Как написать что-нибудь рекурсивное? Например обход дерева в глубину?

CS>Если дерево состоит из

CS>

CS>struct node 
CS>{ 
CS>  node*         parent;
CS>  int           index;
CS>  array<node*>  subs;
CS>};
CS>

CS>В реале у меня такй генератор несколько сложнее ибо используется еще два фильтра skip_node и accept_node.

Так не интересно. Для этого нет нужды городить генератор. У тебя и так состояние явно выписано, да ещё и в узле индекс хранить надо

Нет уж. Узел выглядит так:

strict node { array<node*> subs; };

И никаких поблажек!

Изврат, конечно, но мне лично дико понравилось!

Если в пример использования добавить такой вот "бред", например, то зациклится:

int main(int argc, char* argv[])
{
  desc gen;
  do {
    printf("got number %d\n", gen());
    gen.i = 10; // <- бред, но всё же...
  }
  while (gen);
  return 0;
}

Посему предлагаю чуток закрутить гайки, а именно вот такое лобовое и тривиальное дополнение:

class _generator // <- class вместо struct
{
protected: // <- + это
  int _line;
public: // <- + это
  _generator():_line(-1) {}
  operator bool() const { return _line != 0; }
};

// тут тоже аналогично class вместо struct 
#define generator(NAME) class NAME : public _generator

// ну и напоследок сюда public вставим
#define emit(T)   public: \

Здравствуйте, c-smile, Вы писали:

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

E>>Нет уж. Узел выглядит так:

strict node { array<node*> subs; };

И никаких поблажек!
CS>Это challenge, надо думать.
Дык я сразу спросил, как рекурсивный алгорим позвать...

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, c-smile, Вы писали:

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

E>>>Нет уж. Узел выглядит так:

strict node { array<node*> subs; };

И никаких поблажек!
CS>>Это challenge, надо думать.
E>Дык я сразу спросил, как рекурсивный алгорим позвать...

Тебе как? красиво или эффективно?

Думаю про решение которое и красивое и эффективное.

Здравствуйте, siv, Вы писали:

siv>Изврат, конечно, но мне лично дико понравилось!

Это из тех в общем-то редких извратов которые помогают.
Делать всякого рода FSA удобнее и нагляднее(==надежнее) с этим чем бе оного.

siv>Если в пример использования добавить такой вот "бред", например, то зациклится:

А не надо бред добавлять. Когда понимаешь что делаешь то возможность руками переменные менять полезна. Редко но тем не менее.

Здравствуйте, c-smile, Вы писали:

CS>Тебе как? красиво или эффективно?

Первый критерий зело субъективен

CS>Думаю про решение которое и красивое и эффективное.

Мне эффективно и поддерживаемо...

Здравствуйте, gear nuke, Вы писали:

GN>Здравствуйте, remark, Вы писали:

R>>Но там используется специальный препроцессор, который генерирует код для запоминания/восстановления стековых переменных.

GN>SwitchToFiber решает именно эту задачу в виндовсе. Решения здесь пробегали...

Можно ли создать несколько десятков миллионов фиберов? Что бы каждый фибер занимал не более 32 байт? Что-то я сомневаюсь. Всё-таки на роль очень легковесных потоков фиберы не тянут.

Здравствуйте, remark, Вы писали:

R>Переделать на массив дочерних узлов, я надеюсь, особого труда не составит...

R>

И где тут рекурсия?..

Здравствуйте, remark, Вы писали:

R>2. Попытка вызвать в теле цикла gen() несколько раз приводит в очень неинтуитивному результату. Хотелось бы что бы новый элемент получался только после прохождения итерации, т.е. после вызова gen.operator bool().

как это не интуитивный? генератор на каждый вызов должен новый элемент выдавать.

R>3. Необходимость передавать в макрос stop() реальный элемент. Очень не удобно. Очень. Выход из функции должен означать конец последовательности, никаких элементов уже не должно быть.

Ну я вижу только один достаточно простой выход — кидать эксепшн в конце. как итераторы в питоне.

Здравствуйте, Erop, Вы писали:

R>>Переделать на массив дочерних узлов, я надеюсь, особого труда не составит...

E>И где тут рекурсия?..

С рекурсией ещё проще:

generator(iterate_tree_rec_t, node*) 
{
    node* root;
    std::vector<iterate_tree_rec_t> iter_queue;

public:
    iterate_tree_rec_t(node* root)
        : root (root)
    {}

    emit(node*)
        if (0 == root)
            return;

        yield(root);

        {
            for (size_t i = 0; i != root->children_.size(); ++i)
                iter_queue.push_back(root->children_[i]);
        }

        while (iter_queue.size())
        {
            while (iter_queue.back().next())
                yield(iter_queue.back().value());
            iter_queue.pop_back();
        }

    stop_emit();
};

Это на основе немного пропатченой версии — сейчас я её запосчу.

Здравствуйте, dotidot, Вы писали:

D> Ну я вижу только один достаточно простой выход — кидать эксепшн в конце. как итераторы в питоне.
Для С++ это слишком жёстко

Здравствуйте, remark, Вы писали:

R>С рекурсией ещё проще:

А разве так

struct waw {
    std::vector<waw> Oh;
};

можно?

Здравствуйте, dotidot, Вы писали:

D>Здравствуйте, remark, Вы писали:

R>>2. Попытка вызвать в теле цикла gen() несколько раз приводит в очень неинтуитивному результату. Хотелось бы что бы новый элемент получался только после прохождения итерации, т.е. после вызова gen.operator bool().

D> как это не интуитивный? генератор на каждый вызов должен новый элемент выдавать.

Я, честно говоря, не очень знаком с концепцией генераторов. Зато я, как и любой другой С++ программист, знаком с концепцией итераторов (на которую, кстати, генераторы очень похожи). У С++ итератор функция получения текущего элемента не сдвигает итератор. Поэтому для меня такое поведение генератора *ОЧЕНЬ* не интуитивно.

R>>3. Необходимость передавать в макрос stop() реальный элемент. Очень не удобно. Очень. Выход из функции должен означать конец последовательности, никаких элементов уже не должно быть.

D> Ну я вижу только один достаточно простой выход — кидать эксепшн в конце. как итераторы в питоне.

http://gzip.rsdn.ru/forum/message/2967473.1.aspx

Там можно так же писать просто return посередине функции генерации — это будет означать конец последовательности.

Здравствуйте, remark, Вы писали:

E>>И где тут рекурсия?..

R>С рекурсией ещё проще:

R>Это на основе немного пропатченой версии — сейчас я её запосчу.

http://gzip.rsdn.ru/forum/message/2967473.1.aspx

R>

Здравствуйте, remark, Вы писали:

E>>А разве так

struct waw {
E>>    std::vector<waw> Oh;
E>>};

можно?

R>Тебе какие-то религиозные убеждения запрещают так делать? Или что-то более материальное?
Кажется, по стандарту, std::vector требует, чтобы его первый параметр был уже полностью определён?
Например, он имеет вроде бы имеет право иметь в себе поле этого типа, скажем, или буффер размера sizeof(тот самый тип)
Соответсвенно такая конструкция, кажется, может быть совместима не со всеми версиями STL...

Здравствуйте, remark, Вы писали:

R>Можно ли создать несколько десятков миллионов фиберов? Что бы каждый фибер занимал не более 32 байт?

Количество создаваемых системой фиберов ограничивается из-за выделения отдельных стеков (менее 8-12KB резервировать не удастся, да еще думать о требованиях к стеку у вызываемых API...) Всегда можно найти неприемлимые условия, так что это не аргумент. Вот на что тянет ручное копирование стековых переменных? Минимум — оверхед в рантайме

да еще с генерацией какого-то кода препроцессором... процитирую: "только для С".

Fiber — архитектурно правильное решение. Если локальные переменные аллоцируются в стеке, то они там и хранятся. Плюс сохраняется состояние переменных аллоцированных в регистрах. Время переключения контекстов пренебрежительно мало.

R> Всё-таки на роль очень легковесных потоков фиберы не тянут.

Дык не надо стрелять из пушки по воробьям. Для 32х байт состояния нужны не фиберы, а функторы — и вперёд, синтаксический подсластив генератором c-smile

Они тоже не перетасовывают 320Mb на каждый чих

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, remark, Вы писали:

E>>>А разве так

struct waw {
E>>>    std::vector<waw> Oh;
E>>>};

можно?

R>>Тебе какие-то религиозные убеждения запрещают так делать? Или что-то более материальное?

E>Кажется, по стандарту, std::vector требует, чтобы его первый параметр был уже полностью определён?
E>Например, он имеет вроде бы имеет право иметь в себе поле этого типа, скажем, или буффер размера sizeof(тот самый тип)
E>Соответсвенно такая конструкция, кажется, может быть совместима не со всеми версиями STL...

Да... я думаю, что ты прав... хотя вопрос занятный.
Вроде как требования Assignable и CopyConstructible можно удовлетворить и для "не полного" типа — достаточно поместить объявления соотв. функций перед определением переменной vector. А то, что sizeof от типа можно брать — так такого требования к элементам не предъявляется

В любом случае — ну замени ты std::vector<iterate_tree_rec_t> на std::vector<iterate_tree_rec_t*>, чего ты придираешься — рекурсия на лицо.

Здравствуйте, gear nuke, Вы писали:

R>> Всё-таки на роль очень легковесных потоков фиберы не тянут.

GN>Дык не надо стрелять из пушки по воробьям. Для 32х байт состояния нужны не фиберы, а функторы — и вперёд, синтаксический подсластив генератором c-smile

Они тоже не перетасовывают 320Mb на каждый чих

Ну так там именно "воробьи" и есть. Поэтому и препроцессор.

Здравствуйте, remark, Вы писали:

R>


R>        for (size_t i = 0; i != root->children_.size(); ++i)
R>        {
R>               iterate_tree_rec_t inner (root->children_[i]);
R>               while (inner.next())
R>                    yield(inner.value());
R>        }
R>

А во что это, по твоему, должно развернуться?

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, remark, Вы писали:

R>>


R>>        for (size_t i = 0; i != root->children_.size(); ++i)
R>>        {
R>>               iterate_tree_rec_t inner (root->children_[i]);
R>>               while (inner.next())
R>>                    yield(inner.value());
R>>        }
R>>

E>А во что это, по твоему, должно развернуться?

А ну да. i и inner надо вынести в переменные класса

Здравствуйте, remark, Вы писали:

R>А ну да. i и inner надо вынести в переменные класса

Ну вот это-то мне тут и не нравится..
Но дальше миссер, дальше...

class CPlusPlusPorno {
    CPlusPlusPorno inner;
};

точно не скомпилируется...

Здравствуйте, remark, Вы писали:

R>Ну так там именно "воробьи" и есть. Поэтому и препроцессор.

Для воробъев слишком жирные, постоянное копирование контекста даром не обходится, да и кеши всякие...

Файбер же выделяет стек страницами, и даже если он 1Mb то коммитится пара страниц... Если очень нужно, можно попробовать сделать заточенную под задачу реализацию (SwitchToFiber — 32 команды x86) с малым стеком... например вызывать жрущие стек АПИ подменяя стек на большой (тут подойдёт Call wrapper

)

Здравствуйте, remark, Вы писали:

R>Ну ладно-ладно, туплю. Нужен auto_ptr, как ты сказал.

В общем случае нужен stack on the heap.

Для C++ по всей видимости вполне себе будет достаточно объявления _generator как CRTP
структуры/шаблона плюс поле _generatror<NAME>* _stack.

Это точно будет работать — т.е. можно и рекурсивные вызовы делать (но только себя самого)

bool operator()(T& _rv)
{
  do { 
     ....    

  } while(_pop());
}

bool _pop()
{
  if(!_stack) return false;
  _generatror<NAME>* t = _stack;
  *this = *_stack;
  delete t;
}

Здравствуйте, c-smile, Вы писали:

CS>Здравствуйте, remark, Вы писали:

R>>Ну ладно-ладно, туплю. Нужен auto_ptr, как ты сказал.

CS>В общем случае нужен stack on the heap.

CS>Для C++ по всей видимости вполне себе будет достаточно объявления _generator как CRTP
CS>структуры/шаблона плюс поле _generatror<NAME>* _stack.

CS>Это точно будет работать — т.е. можно и рекурсивные вызовы делать (но только себя самого)

А можешь привести полную реализацию с примером использования. А то пока это всё не складывается в единое целое...

Здравствуйте, gear nuke, Вы писали:

GN>Здравствуйте, remark, Вы писали:

R>>Ну так там именно "воробьи" и есть. Поэтому и препроцессор.

GN>Для воробъев слишком жирные, постоянное копирование контекста даром не обходится, да и кеши всякие...

GN>Файбер же выделяет стек страницами, и даже если он 1Mb то коммитится пара страниц... Если очень нужно, можно попробовать сделать заточенную под задачу реализацию (SwitchToFiber — 32 команды x86) с малым стеком... например вызывать жрущие стек АПИ подменяя стек на большой (тут подойдёт Call wrapper

)

Это уже Сapriccio Thread, это тупиковый вариант
http://gzip.rsdn.ru/forum/message/2965307.1.aspx

Здравствуйте, c-smile, Вы писали:

CS>А вот моя обновлённая версия.
CS>Решает проблему stop значения.

... но return в середине писать всё равно нельзя.
Без него сложные генераторы становятся... ещё сложнее

CS>Использование такое же как и в JS — for(var i in seq)
CS>

CS>int main(int argc, char* argv[])
CS>{
CS>  sample_gen gen;
  
CS>  for(int n;gen(n);)
CS>      printf("got number = %d\n",n);
CS>    return 0;
CS>}
CS>

Раз уж тут и так всё из макросов, можно накрутить, что бы вот так писать:

$foreach(int i, some_gen(10))
  printf("got number = %d\n",n);

Здравствуйте, remark, Вы писали:

CS>>В общем случае нужен stack on the heap.

CS>>Для C++ по всей видимости вполне себе будет достаточно объявления _generator как CRTP
CS>>структуры/шаблона плюс поле _generatror<NAME>* _stack.

CS>>Это точно будет работать — т.е. можно и рекурсивные вызовы делать (но только себя самого)

R>А можешь привести полную реализацию с примером использования. А то пока это всё не складывается в единое целое...

Постараюсь на неделе соорудить. Сейчас со временем — швах.

Здравствуйте, remark, Вы писали:

R>Здравствуйте, c-smile, Вы писали:

CS>>А вот моя обновлённая версия.
CS>>Решает проблему stop значения.

R>... но return в середине писать всё равно нельзя.
R>Без него сложные генераторы становятся... ещё сложнее

break по смыслу я понимаю. А return-то зачем?

R>Раз уж тут и так всё из макросов, можно накрутить, что бы вот так писать:
R>

R>$foreach(int i, some_gen(10))
R>  printf("got number = %d\n",n);
R>

Да вроде и с for(v;gen(v)

нормально. Или я чего не понял?

CS>А вот моя обновлённая версия.
CS>Решает проблему stop значения.

Теперь ещё изящнее.
Жаль, что в теле генератора нельзя yield во внутреннем switch использовать.
Увы, не хватает "динамического goto" какого-нибудь:

#define $emit(T)    bool operator()(T& _rv) { \
                      if(_line < 0) { _line=0;}\
                      goto label(_line) // <- иди туда, куда _line укажет или... exception or UB

#define $yield(V)     \
          do {\
              _line=__LINE__;\
              _rv = (V); \
               return true; \
               label(__LINE__):;\ // <- сегануть сюда бы, да без помощи свича!
          } while (0)

Думаю, что _asm тут бы помого, но было бы непортабельно и еще более извращеннее.

Здравствуйте, siv, Вы писали:

siv>

siv>               label(__LINE__):;\ // <- сегануть сюда бы, да без помощи свича!
siv>

siv>Думаю, что _asm тут бы помого, но было бы непортабельно и еще более извращеннее.

А думаешь нельзя?

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, siv, Вы писали:

siv>>

siv>>               label(__LINE__):;\ // <- сегануть сюда бы, да без помощи свича!
siv>>

siv>>Думаю, что _asm тут бы помог, но было бы непортабельно и еще более извращеннее.

E>А думаешь нельзя?
Что нельзя?
Реализовать? На asm — думаю вполне можно.
Извращаться? Зависит от политики...
Забить на портабильность? Сделать под каждую платфорсу вариант? Можно, но зависит от...

Здравствуйте, Кодт, Вы писали:

К>Решено: щас всё брошу, пойду изучать, как делаются континюэйшены в лиспе.

Если не шутишь, то можешь посмотреть как это делает Слава здесь.

Здравствуйте, remark, Вы писали:

R>Это уже Сapriccio Thread, это тупиковый вариант

Не смотрел даже

испугали слова "нереальный анализ потребления стека функциями". ИМХО не надо искать серебрянную пулю (некоторые автоматы вообще руками писать не стоит) а под конкретные задачи размер стека можно прикинуть... Я лишь хотел сказать что контекст копировать — это всё равно что

volatile int global;

int main()
{
  int i;
  global = 2;
  i = global;
}

К сожалению даже так можно:

#include <vector>

struct SomeType
{
      std::vector< SomeType > vec;
};

int main()
{
      SomeType variable;
      variable.vec.push_back( variable );
      return 0;
}

При этом, сей код под MS VS 7.1.3 не только компиллируется, но и успешно работает.

Здравствуйте, anonim_44ax, Вы писали:

_>К сожалению даже так можно:
Почему "к сожалению"?

_>При этом, сей код под MS VS 7.1.3 не только компиллируется, но и успешно работает.
Вопрос не в том, "может ли это скомпилироваться", а несколько в обратном "может ли это НЕ скомпилироваться"

siv>>Думаю, что _asm тут бы помого, но было бы непортабельно и еще более извращеннее.
E>А думаешь нельзя?

Вот, на скорую руку сваял ещё одно "извращение" just for fun.
Можно внутри генераторов обойтись без Duff's device извращений и заработает switch.
VC8. Под g++ такое не осилю в данный момент.

#ifndef __generator_h_
#define __generator_h_

#include <boost/preprocessor/cat.hpp>

class _generator
{
protected:
    int _addr;
    _generator():_addr(-1) {}
};

//..................................................................
#define $generator(NAME) class NAME : public _generator

#define  GOTO_LABEL         \
  if ( _addr!=-1 )          \
  {                         \
    int addr = _addr;       \
    __asm                   \
    {                       \
      __asm mov eax, addr   \
      __asm jmp eax         \
    }                       \
  }

#define $emit(T)    bool operator()(T& _rv)     \
                    {                           \
                      GOTO_LABEL                \
                      {
//.......

#define $stop         }                       \
                     _addr = -1;              \
                     return false;            \
                   }

#define $yield(V)                             \
          do {                                \
            _rv = (V);                        \
                                              \
            int * iPtr = &_addr;              \
            __asm mov ecx, dword ptr [iPtr]   \
            __asm                             \
            {                                 \
              __asm mov eax, OFFSET BOOST_PP_CAT(label,__LINE__) \
              __asm mov dword ptr [ecx], eax  \
            }                                 \
                                              \
            return true;                      \
            BOOST_PP_CAT(label,__LINE__)##:;  \
          } while (0);

#endif // __generator_h_

//=============================================================================
#include <stdio.h>

$generator(desc)
{
  int m_i;

public:
  desc( int start=-1 ) : m_i(start) {}

  $emit(int) 
  {
    for(; m_i >= 0; --m_i)
    {
// doesn't it work ?
      switch ( m_i )
      {
        case 9 : case 7 :
          $yield( m_i + 100 );
        break;

        case 5:
          $yield( m_i + 100000 );
        break;
      
        default:
          $yield( m_i );
      }
    }
  }
  $stop  
};


int main(int argc, char* argv[])
{
  desc gen( 11 );
  int i;
  while(gen(i))
  {    
    printf("got number %d\n", i);
    //gen.m_i = 10;
  }
}

Пришлось выкрутасы делать из-за странностей VC, например

int * iPtr = &_addr;              \
__asm mov ecx, dword ptr [iPtr]   \

siv>>Увы, не хватает "динамического goto" какого-нибудь:

CS>В GCC кстати такой goto есть. И там можно все это построить без наворотов со switch.
CS>Там можно взять адрес label и по нему перейти — goto *label.
Вах, не знал! Супер, может быть таки поюзаю тогда в реальном проекте под Вынь\Линукс...

Согласен, потому и говорю, что к сожалению сие компиллится под MS VS 7.1.3, хотя и не должно.

Здравствуйте, c-smile, Вы писали:

CS>

CS>$generator(scan)
CS>{
CS>  node* n;
CS>  scan( node* root = 0 ): n(root) {}
CS>  $emit(int)
CS>    for(;n; n = n->next)
CS>    {
CS>      $yield(n->value);
CS>      if( n->kid )
CS>        $restart( n = n->kid );
CS>    }
CS>  $stop
CS>};
CS>

Выглядит интересно... Надо помедитировать...

Здравствуйте, remark, Вы писали:

R>Там что-то типа такого, что пользовательский код анализируется специальным компилятором на потребление стека.
R>На стандартные библиотечные функции они рассчитывают, что будут специальные аннотации по поводу максимального потребления стека.
R>А для известного кода используются специальные большие стеки, которые динамически подцепляются и отцепляются.

------/\/\
---для неизвестного

От:	c-smile	http://terrainformatica.com
Дата:	26.05.08 21:01
Оценка:	243 (25)

	От:	Erop
	Дата:	27.05.08 12:32
	Оценка:	1 (1) +4

От:	remark	http://www.1024cores.net/
Дата:	28.05.08 10:42
Оценка:	3 (1) +1

От:	Vain	google.ru
Дата:	27.05.08 14:30
Оценка:	1 (1) +2

От:	remark	http://www.1024cores.net/
Дата:	28.05.08 13:30
Оценка:	+2