Выдержки из главы 6 книги Барбары Лисков и Джона Гатэга "Использование абстракций и спецификаций при разработке программ" (MIT Press 1986, "Мир" 1989):
__________________________________________
< прим. Предыдущие главы назывались "Процедурная абстракция", "Абстракции данных" и "Исключительные ситуации" >
6. Абстракция итерации
В этой главе обсуждается наш последний механизм абстракции -- абстракция итерации, или, коротко, итератор. Итераторы являются некоторым обобщением итерационных методов, имеющихся в большинстве языков программирования. Они позволяют пользователям выполнять итерации для произвольных типов данных удобным и эффективным способом.
...
6.3. Примеры
В этом разделе приводится несколько примеров итераторов. Первый пример, приведённый на рис. 6.7, -- это простой "фильтр". он называется фильтром потому, что удаляет некоторые элементы, выданные другим итератором, и выдаёт только остальные элементы в процедуру, которая к нему обращается.
Код: filter = iter (s: intset, els: itertype (intset) yields (int),
pred: proctype (int) returns (bool)) yields (int)
requires чтобы s не модифицировалась в теле цикла.
effects Выдаёт в произвольном порядке все элементы, выданные операцией els (s),
которые удовлетворяют условию, заданному в pred.
filter = iter (s: intset, els: itertype (intset) yields (int),
pred: proctype (int) returns (bool)) yields (int)
for e: int in els (s) do
if pred (e) then yield (e) end
end
end filter
Рис. 6.7. Фильтр.
Например, если операция odd выдаёт значение true, только если её целый аргумент является нечётным числом, то фильтр
filter (s, intset$elements, odd)
выдаёт нечетные числа из набора s.
...
6.5. Обзор главы
В этой главе рассматривается проблема полноты типов данных, которые являются совокупностью объектов. Поскольку совокупность, вообще говоря, используется для выполнения некоторого действия над её элементами, нам необходим некоторый способ доступа ко всем элементам. Этот способ должен быть эффективным в смысле времени и пространства, удобным для использования и не должен разрушать данную совокупность. Кроме того, он должен обеспечивать абстракцию через спецификацию.
Итераторы являются тем механизмом, который решает эту задачу. Поскольку они выдают объекты по одному, не требуется дополнительного пространства для хранения объектов, и процедура может быть остановлена, когда нужный объект будет найден. Итераторы поддерживают абстракцию через спецификацию, инкапсулируя метод выдачи объекта. Этот метод зависит от знания представления этих объектов, но использующие его программы защищены от этого знания.
Итераторы эффективны для исполнения. Выдача из итератора аналогична обращению к процедуре. К телу цикла for "обращаются" из итератора. Возобновление работы итератора аналогично возврату из процедуры. Тело цикла "возвращает" управление в итератор. Следовательно, затраты на использование итераторов состоят максимум из одного обращения к процедуре на выполнение тела цикла. Такие затраты могут быть меньше из-за оптимизаций компилятора.
Итераторы полезны сами по себе, как это имело место в примерах permutations и primes. Однако их основным применением являются операции над типами данных. В конце книги мы рассмотрим другие примеры их использования.
< конец цитаты >
__________________________________________
Приведённый в этом примере итератор filter можно, конечно, реализовать в виде обычной процедуры, возвращающей отфильтрованный набор элементов, но это хуже тем, что не так удобно в использовании (нужно заводить специальную переменную для хранения этого набора после вызова такой процедуры), а так же эти элементы в случае использования итератора будут вычисляться только когда они действительно нужны (своего рода ленивые вычисления в энергичном языке), а если вдруг часть этих элементов не нужна, то они и вычисляться не будут, тогда как в случае с процедурой (энергичной) все эти элементы будут в любом случае обработаны и вычислены (создавая заметную ненужную паузу), и если их слишком много или они требуют много ресурсов, то это может стать просто неприемлемым вариантом.
|
)
