В функциональном программировании , iteratee является компонуемыми абстракциями для постепеннога обработки последовательно представлены кусков входных данных в чисто функциональной моде. С помощью итераций можно лениво преобразовать то, как ресурс будет выдавать данные, например, преобразовав каждый фрагмент ввода в верхний регистр по мере извлечения или ограничив данные только пятью первыми фрагментами без загрузки всех входных данных объем памяти. Итераторы также отвечают за открытие и закрытие ресурсов, обеспечивая предсказуемое управление ресурсами.
На каждом шаге итерируемому предоставляется один из трех возможных типов значений: следующий фрагмент данных, значение, указывающее, что данные недоступны, или значение, указывающее, что процесс итерации завершен. Он может возвращать один из трех возможных типов значений, чтобы указать вызывающей стороне, что следует делать дальше: одно означает «стоп» (и содержит окончательное возвращаемое значение), другое означает «продолжить» (и указывает, как продолжить). , и тот, который означает «сигнализировать об ошибке». Фактически, последние типы значений представляют возможные «состояния» итерационного объекта. Итератор обычно запускается в состоянии «продолжить».
Итеративы используются в Haskell и Scala (в Play Framework [1] и в Scalaz ), а также доступны для F # . [2] Существуют несколько различных реализаций итераций. Например, в платформе Play они включают Futures, чтобы можно было выполнять асинхронную обработку.
Поскольку итераторы вызываются другим кодом, который снабжает их данными, они являются примером инверсии управления . Однако, в отличие от многих других примеров инверсии управления, таких как синтаксический анализ SAX XML, итератор сохраняет ограниченный контроль над процессом. Он не может вернуться назад и просмотреть предыдущие данные (если он не хранит эти данные внутри), но он может полностью остановить процесс, не вызывая исключения (использование исключений в качестве средства потока управления , а не для сигнализации об исключительном событии, часто не одобряется программистами [3] ).
Обычно связанные абстракции
Следующие абстракции, строго говоря, не являются необходимыми для работы с итерациями, но они делают ее более удобной.
Счетчики
Перечислитель является удобной абстракцией для подачи данных в iteratee из произвольного источника данных. Обычно перечислитель позаботится о любой необходимой очистке ресурсов, связанных с источником данных. Поскольку перечислитель точно знает, когда итерационный объект закончил чтение данных, он выполнит очистку ресурса (например, закрытие файла) точно в нужное время - ни слишком рано, ни слишком поздно. Тем не менее, он может делать это без необходимости знать о реализации итератора или находиться вместе с ним, поэтому перечислители и итераторы образуют пример разделения задач .
Перечислители
Enumeratee является удобной абстракцией для преобразования выходного сигнала либо перечислителя или iteratee, и подачи , что выход к iteratee. Например, перечислитель «map» отобразит функцию на каждый входной блок. [4]
Мотивации
Итеративы были созданы из-за проблем с существующими чисто функциональными решениями проблемы создания компоновочного, но правильного ввода / вывода . Ленивый ввод-вывод в Haskell позволял чистым функциям работать с данными на диске, как если бы они находились в памяти, без явного ввода-вывода вообще после открытия файла - своего рода файловая функция с отображением в памяти - но потому что это было невозможно в общее (из-за проблемы с остановкой ) для среды выполнения, чтобы знать, нужен ли файл или другой ресурс, чрезмерное количество файлов может оставаться открытыми без необходимости, что приводит к исчерпанию дескриптора файла на уровне операционной системы . С другой стороны, традиционный ввод-вывод в стиле C был слишком низкоуровневым и требовал от разработчика заботиться о деталях низкого уровня, таких как текущая позиция в файле, что затрудняло компоновку. Итераторы и перечислители сочетают преимущества функционального программирования высокого уровня ленивого ввода-вывода с возможностью управления ресурсами и низкоуровневыми деталями, где это необходимо, предоставляемыми вводом-выводом в стиле C. [5]
Примеры
Использует
Итеративы используются в платформе Play для передачи данных на давно работающие соединения Comet и WebSocket в веб-браузеры .
Итераторы также могут использоваться для выполнения инкрементного синтаксического анализа (то есть синтаксического анализа, который не считывает все данные в память сразу), например, JSON . [6]
Однако важно отметить, что итерации представляют собой очень общую абстракцию и могут использоваться для произвольных видов последовательной обработки информации (или смешанной обработки последовательного / произвольного доступа) - и не требуют вообще никакого ввода-вывода. Это позволяет легко перепрофилировать итерацию для работы с набором данных в памяти вместо данных, поступающих из сети.
История
В некотором смысле далеким предшественником идеи перечислителя, проталкивающего данные в цепочку из одного или нескольких итераций, была концепция конвейера в операционных системах. Однако, в отличие от типичного конвейера, итерации не являются отдельными процессами (и, следовательно, не имеют накладных расходов IPC ) или даже отдельными потоками, хотя они могут выполнять работу аналогично цепочке рабочих потоков, отправляющих сообщения друг другу. Это означает, что итерации легче, чем процессы или потоки - в отличие от ситуаций с отдельными процессами или потоками, дополнительных стеков не требуется.
Итеративы и счетчики были изобретены Олегом Киселевым для использования в Haskell. [5] Позже они были введены в Scalaz (в версии 5.0; перечислители отсутствовали и были введены в Scalaz 7) и в Play Framework 2.0.
Формальная семантика
Итерации были формально смоделированы как свободные монады , позволяющие проверять законы уравнений и использоваться для оптимизации программ с использованием итераций. [5]
Альтернативы
- Итераторы могут использоваться вместо итераторов в Scala, но они обязательны , поэтому не являются чисто функциональным решением.
- В Haskell были разработаны две альтернативные абстракции, известные как Conduits и Pipes. (Эти каналы не являются каналами уровня операционной системы, поэтому, как итерации, они не требуют использования системных вызовов ). Каналы, в частности, связаны с значительно более богатыми библиотеками примитивов и комбинаторов, чем итерации; Существуют адаптеры каналов для дополнительных функций, таких как синтаксический анализ HTML, XML, обобщенный синтаксический анализ, выполнение HTTP-запросов и обработка ответов, что делает каналы более подходящими, чем итераторы, для разработки промышленного программного обеспечения на Haskell прямо из коробки.
- Также существует высокоуровневая абстракция под названием « машины» . В Scala есть пакет под названием FS2: Functional Streams for Scala , происхождение которого можно проследить до машин через несколько портов, переименований и рефакторов.
- В Haskell существует пакет safe-lazy-io . Он обеспечивает более простое решение некоторых из тех же проблем, которое, по сути, включает в себя «достаточно строгость» для извлечения всех данных, которые требуются или могут потребоваться, через конвейер, который заботится об очистке ресурсов по завершении.
Рекомендации
- ^ «Реактивная обработка потоков данных» . Документация по Play Framework . Проверено 29 июня 2013 года .
- ^ «Результаты поиска Github: итерация в FSharpx» .
- ^ «Теория и практика Java: дебаты об исключениях» . IBM developerWorks . Дата обращения 17 мая 2014 .
- ^ «Счетчики» . Документация по фреймворку Play . Проверено 29 июня 2013 года .
- ^ а б в Киселев, О. (2012). «Итераторы». Функциональное и логическое программирование . Конспект лекций по информатике. 7294 . С. 166–181. DOI : 10.1007 / 978-3-642-29822-6_15 . ISBN 978-3-642-29821-9.
- ^ Джеймс Ропер (10 декабря 2012 г.). "Json.scala" . play-iteratees-extras . Проверено 29 июня 2013 года .
дальнейшее чтение
- Джон В. Лато (12 мая 2010 г.). «Итеративная: обучение старым новым трюкам» . Выпуск # 16 Монады Читателя . Проверено 29 июня 2013 года . Это относится к Haskell.
Внешние ссылки
- Scala учебники
- Играть 2.0
- Понимание итераций Play 2 для нормальных людей
- Итераторы для императивных программистов
- Скалаз
- Учебное пособие по Scalaz: ввод-вывод на основе перечисления с итерациями
- Играть 2.0
- Учебники Haskell
- Конспект лекций Стэнфорда
- Дальнейшая информация
- Страница Олега Киселева "Итераторы и счетчики"