Generators in C++, (a.k.a. foreach & iteartors)
От: c-smile Канада http://terrainformatica.com
Дата: 26.05.08 21:01
Оценка: 243 (25) :)))
По следам плодотворной дискусии про итераторы...

Используя идею "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;
}


Вот такие вот пироги.
Re: Generators in C++, (a.k.a. foreach & iteartors)
От: remark Россия http://www.1024cores.net/
Дата: 26.05.08 23:49
Оценка:
Здравствуйте, 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/



1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[2]: Generators in C++, (a.k.a. foreach & iteartors)
От: c-smile Канада http://terrainformatica.com
Дата: 27.05.08 01:51
Оценка:
Здравствуйте, 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 выглядят симпатично.

Но мой вариант с классом/структурой позволяет не заморачиваться с аллокациями. Да и переменные контекст естественнее выглядят.
Re: Generators in C++, (a.k.a. foreach & iteartors)
От: Кодт Россия  
Дата: 27.05.08 08:34
Оценка:
Здравствуйте, c-smile, Вы писали:

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


Не этим ли кодом навеяно?
Качество кода open-source
Автор: Lonely Dog
Дата: 22.05.08


Решено: щас всё брошу, пойду изучать, как делаются континюэйшены в лиспе.
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re: Generators in C++, (a.k.a. foreach & iteartors)
От: Gluk_Kazan  
Дата: 27.05.08 12:17
Оценка:
Здравствуйте, c-smile, Вы писали:

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


Пошел посыпать голову пеплом
Как этот case в середину цикла вообще работает ???
Re[2]: switch vs goto
От: Erop Россия  
Дата: 27.05.08 12:32
Оценка: 1 (1) +4 :)))
Здравствуйте, Gluk_Kazan, Вы писали:

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

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

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

Меня забавляет другое. Люди, которые против использования goto, даже если и по делу, как дети рады использованию его аналога, да ещё и хитрых довольно макросов
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[3]: switch vs goto
От: Gluk_Kazan  
Дата: 27.05.08 12:56
Оценка:
Здравствуйте, Erop, Вы писали:

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


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

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


Собственно некоторое время назад была на работе тема посмотреть PuTTY на предмет криптографии
Ага, чую во что бы это вылилось
Re: Generators in C++, (a.k.a. foreach & iteartors)
От: Vain Россия google.ru
Дата: 27.05.08 14:30
Оценка: 1 (1) +2
Здравствуйте, c-smile, Вы писали:

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

У меня такое ощущение что этому коду дальше идеи не уйти и что в нормальном проекте за его использование будут отрубать пальцы по самые уши
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[2]: Generators in C++, (a.k.a. foreach & iteartors)
От: gear nuke  
Дата: 27.05.08 14:51
Оценка:
Здравствуйте, remark, Вы писали:

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


SwitchToFiber решает именно эту задачу в виндовсе. Решения здесь пробегали...
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Re[2]: Generators in C++, (a.k.a. foreach & iteartors)
От: c-smile Канада http://terrainformatica.com
Дата: 27.05.08 15:57
Оценка:
Здравствуйте, Vain, Вы писали:

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

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

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


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

Или вот чего далеко ходить: есть дерево DOM элементов, достаточно хитрое местами.
Нужно написать функцию (хотя бы тот же итератор), который принимает на вход фильтр и позволяет обходить это дерево.
Количество разных FSM состояний из которых возможен выход по yield() — примерно десяток.
Re[3]: Generators in C++, (a.k.a. foreach & iteartors)
От: Vain Россия google.ru
Дата: 27.05.08 16:06
Оценка:
Здравствуйте, c-smile, Вы писали:

CS>А нормальный проект это какой?

Это который простой до такой степени, что большенству программеров разобраться в нём не составляет особого труда.
CS>Эта абстракиция позваляет сократить количество вызовов и размер кода. Иногда значительно.
Это абстракция добавляет ещё один способ зашифровать исходники
CS>Или вот чего далеко ходить: есть дерево DOM элементов, достаточно хитрое местами.
CS>Нужно написать функцию (хотя бы тот же итератор), который принимает на вход фильтр и позволяет обходить это дерево.
CS>Количество разных FSM состояний из которых возможен выход по yield() — примерно десяток.
Скажите сначало почему вам так хочется прикрутить yield к C++?
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re: Generators in C++, (a.k.a. foreach & iteartors)
От: Erop Россия  
Дата: 27.05.08 16:45
Оценка:
Здравствуйте, c-smile, Вы писали:

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


Очень хорошо. Как написать что-нибудь рекурсивное? Например обход дерева в глубину?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[2]: Generators in C++, (a.k.a. foreach & iteartors)
От: c-smile Канада http://terrainformatica.com
Дата: 27.05.08 18:52
Оценка:
Здравствуйте, 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.
Re[3]: Generators in C++, (a.k.a. foreach & iteartors)
От: Erop Россия  
Дата: 27.05.08 19:22
Оценка:
Здравствуйте, 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; };
И никаких поблажек!
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re: Generators in C++, (a.k.a. foreach & iteartors)
От: siv Украина  
Дата: 27.05.08 19:31
Оценка:
Изврат, конечно, но мне лично дико понравилось!
Если в пример использования добавить такой вот "бред", например, то зациклится:
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: \
Re[4]: Generators in C++, (a.k.a. foreach & iteartors)
От: c-smile Канада http://terrainformatica.com
Дата: 27.05.08 19:57
Оценка: :)
Здравствуйте, Erop, Вы писали:

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


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

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


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

E>Нет уж. Узел выглядит так:
strict node { array<node*> subs; };
И никаких поблажек!


Это challenge, надо думать.
Re[5]: Generators in C++, (a.k.a. foreach & iteartors)
От: Erop Россия  
Дата: 27.05.08 20:02
Оценка:
Здравствуйте, c-smile, Вы писали:

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

Это понятно, задача давно решена и обсосона. Но тогда и генератор никакой не нужен

E>>Нет уж. Узел выглядит так:
strict node { array<node*> subs; };
И никаких поблажек!

CS>Это challenge, надо думать.
Дык я сразу спросил, как рекурсивный алгорим позвать...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[6]: Generators in C++, (a.k.a. foreach & iteartors)
От: c-smile Канада http://terrainformatica.com
Дата: 28.05.08 01:56
Оценка:
Здравствуйте, Erop, Вы писали:

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


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

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

E>>>Нет уж. Узел выглядит так:
strict node { array<node*> subs; };
И никаких поблажек!

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

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

Думаю про решение которое и красивое и эффективное.
Re[2]: Generators in C++, (a.k.a. foreach & iteartors)
От: c-smile Канада http://terrainformatica.com
Дата: 28.05.08 03:24
Оценка:
Здравствуйте, siv, Вы писали:

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


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

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


А не надо бред добавлять. Когда понимаешь что делаешь то возможность руками переменные менять полезна. Редко но тем не менее.
Re[7]: Generators in C++, (a.k.a. foreach & iteartors)
От: Erop Россия  
Дата: 28.05.08 05:29
Оценка:
Здравствуйте, c-smile, Вы писали:

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

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

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

Мне эффективно и поддерживаемо...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.