итеративный

В функциональном программировании итератор — это компонуемая абстракция для постепенной обработки последовательно представленных фрагментов входных данных чисто функциональным способом. С помощью итераций можно лениво трансформировать то, как ресурс будет выдавать данные, например, преобразуя каждый фрагмент входных данных в верхний регистр по мере их извлечения или ограничивая данные только пятью первыми фрагментами, не загружая все входные данные в память. Итераторы также отвечают за открытие и закрытие ресурсов, обеспечивая предсказуемое управление ресурсами.

На каждом шаге итерируемому предоставляется один из трех возможных типов значений: следующий фрагмент данных, значение, указывающее, что данные недоступны, или значение, указывающее на завершение итерационного процесса. Он может возвращать один из трех возможных типов значений, чтобы указать вызывающей стороне, что следует делать дальше: одно, которое означает «остановить» (и содержит окончательное возвращаемое значение), другое, которое означает «продолжить» (и указывает, как продолжить). и тот, который означает «сигнализировать об ошибке». Последние типы значений по сути представляют собой возможные «состояния» итерируемого объекта. Итерация обычно начинается в состоянии «продолжить».

Итерации используются в Haskell и Scala (в Play Framework ^[1] и в Scalaz ), а также доступны для F# . ^[2] Существуют различные немного отличающиеся реализации итераций. Например, в платформе Play они задействуют Futures , чтобы можно было выполнять асинхронную обработку.

Поскольку итераторы вызываются другим кодом, который передает им данные, они являются примером инверсии управления . Однако, в отличие от многих других примеров инверсии управления, таких как синтаксический анализ XML SAX , итерируемый сохраняет ограниченный объем контроля над процессом. Он не может вернуться назад и просмотреть предыдущие данные (если только он не сохраняет эти данные внутри себя), но он может полностью остановить процесс, не вызывая исключения (использование исключений в качестве средства потока управления , а не для сигнализации об исключительном событии, часто не одобряется). программистами ^[3]).

Часто связанные абстракции

Следующие абстракции, строго говоря, не являются необходимыми для работы с итеративными объектами, но они делают ее более удобной.

Счетчики

Enumerator — это удобная абстракция для подачи данных в итерируемый объект из произвольного источника данных. Обычно перечислитель берет на себя всю необходимую очистку ресурсов, связанных с источником данных. Поскольку перечислитель точно знает, когда итерируемый объект завершил чтение данных, он выполнит очистку ресурса (например, закрытие файла) точно в нужное время — ни слишком рано, ни слишком поздно. Однако он может сделать это без необходимости знать о реализации итерируемого объекта или быть совмещенным с ним — таким образом, перечислители и итерируемые элементы образуют пример разделения задач .

Перечисленные

Enumeratee — это удобная абстракция для преобразования вывода перечислителя или итерируемого объекта и передачи этих результатов итерируемому объекту. Например, перечислитель «карта» будет отображать функцию на каждый входной фрагмент. ^[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 , происхождение которого можно проследить до машин через несколько портов, переименований и рефакторингов.
пакет Safe-lazy-io В Haskell существует . Он обеспечивает более простое решение некоторых из тех же проблем, которое, по сути, предполагает «достаточную строгость» для пропуска всех данных, которые требуются или могут потребоваться, через конвейер, который заботится об очистке ресурсов по завершении.

Ссылки

^ «Реактивная обработка потоков данных» . Документация Play Framework . Проверено 29 июня 2013 г.
^ «Результаты поиска на Github: Iteratee в FSharpx» . Гитхаб .
^ «Теория и практика Java: дебаты об исключениях» . IBM DeveloperWorks . Проверено 17 мая 2014 г.
^ «Перечисленные» . Документация по платформе Play . Проверено 29 июня 2013 г.
^ Jump up to: ^а ^б ^с Киселёв, О. (2012). «Итераторы». Функциональное и логическое программирование . Конспекты лекций по информатике. Том. 7294. стр. 166–181. дои : 10.1007/978-3-642-29822-6_15 . ISBN 978-3-642-29821-9 .
^ Джеймс Ропер (10 декабря 2012 г.). "Json.скала" . play-iteratees-дополнительные материалы . Проверено 29 июня 2013 г.

Дальнейшее чтение

Джон В. Лато (12 мая 2010 г.). «Итерируемый: обучение старых трюкам новым трюкам» . Выпуск №16 журнала Monad Reader . Проверено 29 июня 2013 г. Это относится к Хаскелю.

Внешние ссылки

Учебники по Scala
- Играть 2.0
  - Понимание итераций Play 2 для обычных людей
  - Итерации для императивных программистов
- Скалаз
  - Учебное пособие по Scalaz: ввод-вывод на основе перечисления с итерациями
Учебники по Хаскеллу
- Конспекты лекций Стэнфорда
Дополнительная информация
- Страница Итераторов и перечислителей Олега Киселёва

[1] «Реактивная обработка потоков данных» . Документация Play Framework . Проверено 29 июня 2013 г.

[fsharpx-2] «Результаты поиска на Github: Iteratee в FSharpx» . Гитхаб .

[3] «Теория и практика Java: дебаты об исключениях» . IBM DeveloperWorks . Проверено 17 мая 2014 г.

[play-enumeratee-4] «Перечисленные» . Документация по платформе Play . Проверено 29 июня 2013 г.

[kiselyov-5] Jump up to: ^а ^б ^с Киселёв, О. (2012). «Итераторы». Функциональное и логическое программирование . Конспекты лекций по информатике. Том. 7294. стр. 166–181. дои : 10.1007/978-3-642-29822-6_15 . ISBN 978-3-642-29821-9 .

[iteratee-json-play-6] Джеймс Ропер (10 декабря 2012 г.). "Json.скала" . play-iteratees-дополнительные материалы . Проверено 29 июня 2013 г.

[1]

[2]

[3]

[4]

[5]

[6]