generator

ИМЯ

generator — процедуры для создания и использования генераторов.

Содержание

Содержание
Краткое описание
Описание
КОМАНДЫ
СТАНДАРТНАЯ БИБЛИОТЕКА
ОШИБКИ, ИДЕИ, ОТЗЫВЫ

КРАТКОЕ ОПИСАНИЕ

package require Tcl 8.6 9
package require generator ?0.3?

ОПИСАНИЕ

Пакет generator предоставляет команды для определения выражений-генераторов и перебора их значений. Генератор — это команда, возвращающая последовательность значений. Однако, в отличие от обычной команды, возвращающей список, генератор выдаёт каждое значение, а затем приостанавливается, позволяя получать последующие значения по мере необходимости. Благодаря этому генераторы можно использовать для эффективного перебора набора значений, не создавая все результаты сразу в памяти. Генераторы подходят для перебора элементов структуры данных, строк в результирующем наборе запроса к базе данных, разделения программных компонентов-производителей и потребителей (например, анализаторов и токенизаторов), а также для реализации сложных пользовательских стратегий управления, таких как поиск с возвратом. Генераторы уменьшают потребность в реализации специальных управляющих конструкций, поскольку многие такие конструкции можно представить в виде генераторов, что упрощает реализацию и обеспечивает более стандартизированный интерфейс. Механизм генераторов построен поверх механизма сопрограмм Tcl 8.6.

Пакет экспортирует единственную команду-ансамбль — generator. Вся функциональность предоставляется в виде подкоманд этой команды. Основные подкоманды пакета — define, yield и foreach. Команда define работает подобно команде Tcl proc, но создаёт процедуру-генератор, то есть процедуру, вызов которой возвращает генератор. Сам генератор — это команда, которую можно вызывать несколько раз: при каждом вызове она возвращает следующее значение в последовательности. Когда последовательность заканчивается, команда генератора возвращает пустой список и уничтожает себя. Однако вместо ручного вызова генератора пакет предоставляет гибкую команду foreach, которая перебирает значения одного или нескольких генераторов. Эта конструкция цикла имитирует встроенную команду Tcl foreach, в том числе поддерживает обработку нескольких возвращаемых значений и одновременный перебор нескольких генераторов. Создать генератор также просто, как и обычную процедуру: достаточно определить его с помощью команды define, а затем вызывать yield вместо return. Например, можно определить генератор для перебора целых чисел в заданном диапазоне:

generator define range {n m} {
    for {set i $n} {$i <= $m} {incr i} { generator yield $i }
}
generator foreach x [range 1 10] {
    puts "x = $x"
}

Приведённый выше пример напечатает числа от 1 до 10 по порядку, как и ожидается. Отличие от обычного перебора списка состоит в том, что числа создаются только по мере необходимости. Если добавить в цикл команду break, оставшиеся числа последовательности созданы не будут. Для примера можно определить генератор, создающий последовательность натуральных чисел — бесконечный ряд. Обычная процедура никогда бы не завершила создание такого ряда в виде списка. Используя генератор, мы создаём только те значения, которые действительно используются:

generator define nats {} {
    while 1 { generator yield [incr nat] }
}
generator foreach n [nats] {
    if {$n > 100} { break }
}

КОМАНДЫ

generator define name params body

Создаёт новую процедуру-генератор. Аргументы команды идентичны аргументам команды proc: имя, список параметров и тело. Формат списка параметров такой же, как у процедуры. В частности, можно использовать значения по умолчанию и синтаксис ?args?. При каждом вызове созданная процедура-генератор создаёт новую команду генератора (сопрограмму), которая при каждом вызове будет выдавать список значений. Каждый результат генератора гарантированно представляет собой непустой список значений. Когда значения генератора заканчиваются, он возвращает пустой список и уничтожает себя, освобождая ресурсы. Попытка вызвать исчерпанный генератор приводит к ошибке, поскольку такой команды больше не существует.
generator yield arg ?args..?

Эта команда используется в определении генератора и возвращает потребителю следующий набор значений. После вызова команды yield генератор приостанавливается, чтобы потребитель мог обработать это значение. Когда запрашивается следующее значение, генератор возобновляет выполнение, как если бы команда yield только что вернула управление, и продолжает работу до выдачи следующего результата. Команда yield должна вызываться как минимум с одним аргументом, но может принимать и несколько аргументов; в этом случае она эквивалентна отдельному вызову yield для каждого аргумента.
generator foreach varList generator varList generator ?...? body

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

Команда foreach автоматически очищает все генераторы в конце цикла независимо от того, завершился ли цикл досрочно. Это сделано для удобства, чтобы в обычных случаях не приходилось явно очищать генераторы. Однако генераторы можно уничтожить до завершения цикла; в таком случае цикл продолжится в обычном режиме, пока остальные генераторы не будут уничтожены или исчерпаны.

Команда foreach не создаёт снимок состояния генератора. Любые изменения состояния генератора внутри цикла или в другом коде повлияют на ход цикла. В частности, если код цикла вручную вызывает генератор, чтобы получить следующий элемент, этот элемент не попадёт в цикл, а следующая итерация продолжится со следующего за ним элемента. Следует избегать параллельного изменения генераторов, если такое поведение не требуется (например, при обработке аргументов).
generator next generator ?varName..?

Вручную получает следующие значения из генератора. Для каждой указанной переменной извлекается одно значение и присваивается соответствующей переменной. Если генератор исчерпывается, всем оставшимся переменным присваивается пустая строка.
generator exists generator

Возвращает 1, если генератор (всё ещё) существует, и 0 в противном случае.
generator names

Возвращает список всех существующих в данный момент команд генераторов.
generator destroy ?generator..?

Уничтожает один или несколько генераторов, освобождая связанные с ними ресурсы.
generator finally cmd ?arg..?

Эта команда используется при определении процедуры-генератора и обеспечивает очистку ресурса при уничтожении генератора — как явном, так и неявном, когда значения генератора заканчиваются. Команду можно использовать подобно блоку finally команды try, но она привязана к жизненному циклу генератора, а не к определённой области видимости. Например, если создать генератор для перебора строк текстового файла, с помощью finally можно гарантировать, что файл будет закрыт при уничтожении генератора:

generator define lines file { set in [open $file] # Ensure file is always closed generator finally close $in while {[gets $in line] >= 0} { generator yield $line } } generator foreach line [lines /etc/passwd] { puts "[incr count]: $line" if {$count > 10} { break } }

Файл будет закрыт даже при досрочном выходе

Если создать генератор, использующий другой генератор (например, стандартные генераторы map и filter, определённые далее), следует использовать команду finally, чтобы гарантировать уничтожение этого генератора вместе с родительским. Например, генератор map определяется так:

generator define map {f xs} { generator finally generator destroy $xs generator foreach x $xs { generator yield [{*}$f $x] } }
generator from format value

Создаёт генератор из структуры данных. В настоящее время поддерживаются форматы list, dict и string. В формате списка по очереди выдаётся каждый элемент. Для словарей отдельно выдаются каждый ключ и значение. Для строк по одному выдаются символы.
generator to format generator

Преобразует генератор в структуру данных. Это обратная операция к команде from; поддерживаются те же структуры данных. Эти две операции подчиняются следующим законам тождества (где знак = следует интерпретировать соответствующим образом):

[generator to $fmt [generator from $fmt $value]] = $value [generator from $fmt [generator to $fmt $gen]] = $gen

СТАНДАРТНАЯ БИБЛИОТЕКА

Следующие команды предоставляются как стандартная библиотека комбинаторов генераторов и функций, выполняющих вспомогательные операции над генераторами. Функции этого раздела в общих чертах основаны на соответствующих функциях из стандартной библиотеки Haskell Prelude. Предупреждение: большинство функций этой библиотеки уничтожают переданные им генераторы в качестве побочного эффекта. Если нужны генераторы, сохраняющие состояние, см. библиотеку streams.

generator map function generator

Применяет функцию к каждому элементу генератора и возвращает новый генератор результатов. Это классическая функция map из функционального программирования, применённая к генераторам. Например, с помощью следующего кода можно получить все квадраты чисел (здесь nats определён, как описано выше):

proc square x { expr {$x * $x} } generator foreach n [generator map square [nats]] { puts "n = $n" if {$n > 1000} { break } }
generator filter predicate generator

Ещё одна классическая жемчужина функционального программирования. Эта команда возвращает генератор, выдающий только те элементы генератора-аргумента, которые удовлетворяют предикату (логической функции). Например, если имеется генератор employees, возвращающий поток словарей с данными о людях, можно легко отфильтровать тех, чья зарплата превышает 100 000 долларов (или любую другую сумму в предпочитаемой вами валюте):

proc salary> {amount person} { expr {[dict get $person salary] > $amount} } set fat-cats [generator filter {salary> 100000} $employees]
generator reduce function zero generator

Это классическая операция свёртки слева. Команда принимает функцию, начальное значение и генератор значений. Для каждого элемента генератора она применяет функцию к текущему значению аккумулятора (изначально аргументу zero) и этому элементу, а затем использует результат как новое значение аккумулятора. Процесс продолжается для всего генератора (без отложенных вычислений), после чего возвращается итоговое значение аккумулятора. Если считать функцию бинарным оператором, а аргумент zero — левым нейтральным элементом этой операции, команду reduce можно рассматривать как свёртку оператора между каждой соседней парой значений генератора с левой ассоциативностью. Например, сумму последовательности чисел можно вычислить, применив оператор + между ними, используя 0 в качестве нейтрального элемента:

sum xs = reduce + 0 xs

sum [range 1 5] = reduce + 0 [range 1 5]

= reduce + [+ 0 1] [range 2 5]

= reduce + [+ 1 2] [range 3 5]

= ...

= reduce + [+ 10 5]

= ((((0+1)+2)+3)+4)+5

= 15

proc + {a b} { expr {$a + $b} } proc sum gen { generator reduce + 0 $gen } puts [sum [range 1 10]]

Операция reduce чрезвычайно полезна: с её помощью можно определить множество разнообразных операций. Например, используя генераторы, можно определить функцию факториала как произведение чисел в диапазоне. Это определение одновременно очень наглядно и достаточно эффективно (как по памяти, так и по времени выполнения):

proc * {x y} { expr {$x * $y} } proc prod gen { generator reduce * 0 $gen } proc fac n { prod [range 1 $n] }

Однако, хотя операция reduce эффективна для конечных генераторов, применять её к бесконечному генератору не следует: это приведёт к бесконечному циклу:

sum [nats]; # Never returns
generator foldl function zero generator

Это псевдоним команды reduce.
generator foldr function zero generator

Это версия команды reduce с правой ассоциативностью. Как правило, эта операция неэффективна, поскольку перед началом свёртки весь генератор необходимо вычислить в памяти (в виде списка). В языке с немедленным вычислением, таком как Tcl, эта операция имеет ограниченную область применения, и по возможности её следует избегать.
generator all predicate generator

Возвращает true, если все элементы генератора удовлетворяют заданному предикату.
generator and generator

Возвращает true, если все элементы генератора истинны (то есть вычисляет логическое И для элементов).
generator any generator

Возвращает true, если истинно хотя бы одно значение генератора (то есть вычисляет логическое ИЛИ).
generator concat generator ?generator..?

Возвращает генератор, представляющий собой конкатенацию всех генераторов-аргументов.
generator concatMap function generator

Принимает функцию, преобразующую значение в последовательность значений, и генератор значений такого типа, а затем возвращает генератор всех результатов в виде одной плоской последовательности. Эквивалентно применению concat к результату map.
generator drop n generator

Удаляет указанное количество элементов из начала генератора и возвращает полученный генератор без этих элементов.
generator dropWhile predicate generator

Удаляет из начала генератора все элементы, удовлетворяющие предикату.
generator contains element generator

Возвращает true, если генератор содержит заданный элемент. Обратите внимание: эта команда уничтожает генератор!
generator foldl1 function generator

Версия foldl, в которой аргумент zero берётся из первого элемента генератора. Поэтому эту функцию можно использовать только с непустыми генераторами.
generator foldli function zero generator

Версия foldl, передающая функции целочисленный индекс каждого элемента в качестве первого аргумента. Первый элемент генератора на этом этапе получает индекс 0.
generator foldri function zero generator

Версия foldli с правой ассоциативностью.
generator head generator

Возвращает первый элемент генератора.
generator tail generator

Удаляет первый элемент генератора и возвращает оставшуюся часть.
generator init generator

Возвращает новый генератор, состоящий из всех элементов генератора-аргумента, кроме последнего.
generator takeList n generator

Возвращает следующие n элементов генератора в виде списка. Если в генераторе осталось меньше элементов, возвращаются только оставшиеся элементы.
generator take n generator

Возвращает следующие n элементов генератора в виде нового генератора. Старый генератор уничтожается.
generator iterate function init

Возвращает бесконечный генератор, полученный многократным применением функции к начальному аргументу. Например, числа Фибоначчи можно определить так:

proc fst pair { lindex $pair 0 } proc snd pair { lindex $pair 1 } proc nextFib ab { list [snd $ab] [expr {[fst $ab] + [snd $ab]}] } proc fibs {} { generator map fst [generator iterate nextFib {0 1}] }
generator last generator

Возвращает последний элемент генератора (если он существует).
generator length generator

Возвращает длину генератора, уничтожая его в процессе.
generator or predicate generator

Возвращает 1, если хотя бы один элемент генератора удовлетворяет предикату.
generator product generator

Возвращает произведение чисел в генераторе.
generator repeat n value..

Возвращает генератор, состоящий из n копий заданных элементов. Специальное значение Inf можно использовать для создания бесконечной последовательности.
generator sum generator

Возвращает сумму значений генератора.
generator takeWhile predicate generator

Возвращает генератор, состоящий из начальных элементов генератора-аргумента, удовлетворяющих предикату.
generator splitWhen predicate generator

Разбивает генератор на списки элементов, используя предикат для определения разделителей. Полученные списки возвращаются в виде генератора. Элементы, удовлетворяющие предикату-разделителю, отбрасываются. Например, чтобы разделить генератор с помощью строки "|" в качестве разделителя:

set xs [generator from list {a b c}]

generator split {string equal " "} $xs ;# returns a then b then c
generator scanl function zero generator

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

ОШИБКИ, ИДЕИ, ОТЗЫВЫ

Сообщайте об ошибках в этом документе или описываемом в нём пакете Нилу Мэддену.

Licensed under the BSD license
https://core.tcl-lang.org/tcllib/doc/trunk/embedded/md/tcllib/files/modules/generator/generator.md

set xs [generator from list {a	b	c}]
generator split {string equal "	"} $xs ;# returns a then b then c

generator

ИМЯ

Содержание

КРАТКОЕ ОПИСАНИЕ

ОПИСАНИЕ

КОМАНДЫ

Файл будет закрыт даже при досрочном выходе

СТАНДАРТНАЯ БИБЛИОТЕКА

sum xs = reduce + 0 xs

sum [range 1 5] = reduce + 0 [range 1 5]

= reduce + [+ 0 1] [range 2 5]

= reduce + [+ 1 2] [range 3 5]

= ...

= reduce + [+ 10 5]

= ((((0+1)+2)+3)+4)+5

= 15

ОШИБКИ, ИДЕИ, ОТЗЫВЫ