Iterator

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Iterator

Ruvim Pinka
Общие соображения об итераторах

Итераторы должны допускать повторное вхождение. Удобней, когда итераторы оставляют стек прозрачным, не занимая его своими внутренними данными (при вызове пользовательского кода). То бишь, желательна допустимость сигнатуры стека для xt типа ( i*x data_n -- j*x )

Наиболее распространенные стековые сигнатуры итераторов, принимающих callback:
( xt -- ) \ коллекция — внешняя или контекстно|косвенно заданная.
( handle xt -- ) \ обработчик (xt) мыслится как уточнение итератора (как R/O для OPEN-FILE); порядок удобен когда обработчик фиксирован в коде.
( xt obj -- )  \ итератор мыслится сообщением объекту obj, несущем xt, (как SEARCH-WORDLIST или WRITE-FILE); порядок удобен когда объект фиксирован в коде.


Пример системы имен с сигнатурой обработчика xt ( entry -- )

Перебор словаря
ENUM-CURRENT ( xt -- ) \ итерация по текущему словарю ( CURRENT )
EACH-WORD  ( wid xt -- ) \
FOR-WORDLIST ( wid xt -- )
FOREACH-WORDLSIT ( xt wid -- )

Потоки
ENUM-THREADS ( xt -- ) \ текущий процесс
EACH-THREAD ( pid xt -- ) \ потоки в процессе pid
FOR-PROCESS ( pid xt -- )
FOREACH-PROCESS ( xt pid -- )

Списки
EACH-NODE ( list xt -- )
FOR-LIST ( list xt -- )
FOREACH-LIST ( xt list -- )

Обобщение
ENUM-[КОЛЛЕКЦИЯ(собственное)] \ итерация по текущему или глобальному объекту.
EACH-[ЭЛЕМЕНТ]  \ тип коллекции должен быть понятен из названия элемента
FOR-[КОЛЛЕКЦИЯ(тип)]
FOREACH-[КОЛЛЕКЦИЯ(тип)] \ именование аналогично SEARCH-WORDLIST

Возможно, иногда удобней будет
ENUM-[ЭЛЕМЕНТЫ(тип)] \ например, ENUM-THREADS,  или ENUM-WINDOWS -- все окна текущего процесса.
FOR-[ЭЛЕМЕНТЫ(тип)] \ например, FOR-WINDOWS ( pid xt -- ) -- все окна заданного процесса,


Кроме явной передачи элемента обработчику встречается косвенная передача, путем установки контекста. В этом случае в качестве суфикса подойдет слово WITHIN, например EACH-NODE-WITHIN ( list xt -- ) \ xt ( -- )

В практике, для итераторов, поддерживающих прерывание обработки по флагу FALSE от xt ( data -- flag ) в качестве префикса использовался знак вопроса: "?FOREACH-LIST", который обозначает условность перебора.

Перебор по древовидной структуре может быть рекурсивным. В практике, для обозначения рекурсивного перебора использовался суфикс "-R", для выборочного перебора (например, лишь каталогов или файлов) также использовались те или иные суффиксы.

--
Ruvim
Reply | Threaded
Open this post in threaded view
|

Re: Iterator

Yuriy Zhilovets
Ruvim Pinka пишет:

> ( xt -- ) \ коллекция — внешняя или контекстно|косвенно заданная.
> ( handle xt -- ) \ обработчик (xt) мыслится как уточнение итератора
> (как R/O для OPEN-FILE); порядок удобен когда обработчик фиксирован в
> коде.
> ( xt obj -- )  \ итератор мыслится сообщением объекту obj, несущем xt,
> (как SEARCH-WORDLIST или WRITE-FILE); порядок удобен когда объект
> фиксирован в коде.
>
Для итераторов нередко требуется еще и передача произвольного параметра
(для различения вызовов итераторов или передачи дополнительных аргументов).
Поэтому появляются дополнительные варианты

( xt param obj -- )
( obj xt param -- )

Ю. Жиловец



Reply | Threaded
Open this post in threaded view
|

Re: Iterator

Ruvim Pinka

On 7/26/07, Yuriy Zhilovets <[hidden email]> wrote:
Для итераторов нередко требуется еще и передача произвольного параметра
(для различения вызовов итераторов или передачи дополнительных аргументов).
Поэтому появляются дополнительные варианты

( xt param obj -- )
( obj xt param -- )

Если этот параметр нужен для xt, то итератор может ничего о нем не знать, достаточно прозрачного стека.

Пример. ENUM-VOCS ( xt -- ) \ xt ( i*x wid -- j*x )

: (ENUM-VOCS-FORTH) ( xt wid -- xt ) \ фильтр
  DUP IS-CLASS-FORTH IF SWAP DUP >R EXECUTE R> EXIT THEN DROP
;
: ENUM-VOCS-FORTH ( xt -- ) \ xt ( wid -- )
\ перебор только обычных форт-словарей
  ['] (ENUM-VOCS-FORTH) ENUM-VOCS  DROP
;

Или ты про другой случай?  (тогда может, пример найдется?)

--
Ruvim
Reply | Threaded
Open this post in threaded view
|

Re: Iterator

Yuriy Zhilovets
Ruvim Pinka пишет:

> Или ты про другой случай?  (тогда может, пример найдется?)

Вроде про этот. Не очень красиво выходит.

: proc ( param xt current -- param xt) ... ;
param ['] proc iterator

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

И еще вспомнил. Из итераторов неплохо предусмотреть выход. Перебирать
все возможности нужно далеко не всегда. Вернее, редко когда нужно.

Ю. Жиловец





Reply | Threaded
Open this post in threaded view
|

Re: Iterator

Ruvim Pinka

On 7/26/07, Yuriy Zhilovets <[hidden email]> wrote:
Сам итератор на прозрачном стеке трудно сделать. Это придется складывать
все на стек возвратов, а потом считать, где оно там находится. И сам
стек возвратов при этом будет очень непрозрачный.

Да, я обычно сохраняю и восстанавливаю через R, а прозрачность стека возвратов роли не играет. Если совсем трудно — локальные переменные помогут :)
А вообще, не раз мне приходилось отказваться от готовых итераторов из-за непрозрачности их стека. Поэтому, лучше немного усложнить реализацию в пользу простоты (некой универсальности) использования.


И еще вспомнил. Из итераторов неплохо предусмотреть выход. Перебирать
все возможности нужно далеко не всегда. Вернее, редко когда нужно.

Приводил я пример "?FOREACH-LIST", xt ( data -- flag ), продолжать перебора пока TRUE, а если xt вернул FALSE — прервать перебор. Смыслы префикса "?" похож на то, как в ?DUP или в ?DO (делать, если TRUE). (правда, если проводить аналогию с пост-условным циклом UNTIL, то смысл флага будет обратным).

--
Ruvim