рамки для представления обработки данных в виде конвейера - PullRequest
16 голосов
/ 16 ноября 2011

Большая часть обработки данных может быть представлена ​​в виде конвейера компонентов, выход одного ввода на вход другого. Типичный конвейер обработки:

reader | handler | writer

В качестве фольги для начала этого обсуждения давайте рассмотрим объектно-ориентированную реализацию этого конвейера, где каждый сегмент является объектом. Объект handler содержит ссылки на объекты reader и writer и имеет метод run, который выглядит следующим образом:

define handler.run:
  while (reader.has_next) {
    data = reader.next
    output = ...some function of data...
    writer.put(output)
  }

Схематически зависимости:

reader <- handler -> writer

Теперь предположим, что я хочу вставить новый сегмент конвейера между читателем и обработчиком:

reader | tweaker | handler | writer

Опять же, в этой реализации OO tweaker будет оболочкой вокруг объекта reader, а методы tweaker могут выглядеть примерно так (в некотором псевдо-императивном коде):

define tweaker.has_next:
  return reader.has_next

define tweaker.next:
  value = reader.next
  result = ...some function of value...
  return result

Я обнаружил, что это не очень составная абстракция. Некоторые проблемы:

  1. tweaker можно использовать только с левой стороны от handler, т. Е. Я не могу использовать вышеприведенную реализацию tweaker для формирования этого конвейера:

    читатель | обработчик | твикер | писатель

  2. Я хотел бы использовать ассоциативное свойство конвейеров, чтобы этот конвейер:

    читатель | обработчик | писатель

может быть выражено как:

reader | p

, где p - конвейер handler | writer. В этой ОО-реализации мне пришлось бы частично создать экземпляр handler объекта

  1. Отчасти из-за того, что (1) объекты должны знать, «толкают» или «вытягивают» данные.

Я ищу платформу (не обязательно OO) для создания конвейеров обработки данных, которая решает эти проблемы.

Я отметил это с помощью Haskell и functional programming, потому что я чувствую, что здесь могут быть полезны концепции функционального программирования.

В качестве цели было бы неплохо иметь возможность создать конвейер, подобный этому:

                     handler1
                   /          \
reader | partition              writer
                   \          /
                     handler2

В некоторой перспективе Unix shell pipe решает многие из этих проблем с помощью следующих решений реализации:

  1. Компоненты конвейера работают асинхронно в отдельных процессах

  2. Объекты Pipe обеспечивают передачу данных между "толкателями" и "съемниками"; то есть они блокируют авторов, которые пишут данные слишком быстро, и читателей, которые пытаются читать слишком быстро.

  3. Вы используете специальные соединители < и > для подключения пассивных компонентов (то есть файлов) к конвейеру

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

Спасибо!

Ответы [ 4 ]

20 голосов
/ 16 ноября 2011

Да, стрелки почти наверняка ваш мужчина.

Я подозреваю, что вы довольно плохо знакомы с Haskell, просто исходя из того, что вы говорите в своем вопросе. Стрелки, вероятно, будут казаться довольно абстрактными, особенно если вы ищете "рамки". Я знаю, что мне потребовалось некоторое время, чтобы действительно понять, что происходит со стрелками.

Так что вы можете посмотреть на эту страницу и сказать: «Да, это похоже на то, что я хочу», а затем довольно заблудиться в том, как начать использовать стрелки для решения проблемы. Вот небольшое руководство, чтобы вы знали, на что смотрите.

Стрелки не решат вашу проблему. Вместо этого они дают вам язык, на котором вы можете сформулировать свою проблему. Вы можете обнаружить, что некоторая предопределенная стрелка будет делать эту работу - возможно, некоторая стрелка Клейсли - но в конце дня вы захотите реализовать стрелку (предопределенные просто дают вам простые способы реализовать их), который выражает то, что вы подразумеваете под «процессором данных». В качестве почти тривиального примера предположим, что вы хотите реализовать свои процессоры данных с помощью простых функций. Вы бы написали:

newtype Proc a b = Proc { unProc :: a -> b }

-- I believe Arrow has recently become a subclass of Category, so assuming that.

instance Category Proc where
    id = Proc (\x -> x)
    Proc f . Proc g = Proc (\x -> f (g x))

instance Arrow Proc where
    arr f = Proc f
    first (Proc f) = Proc (\(x,y) -> (f x, y))

Это дает вам механизм для использования различных комбинаций стрелок (***), (&&&), (>>>) и т. Д., А также обозначения стрелок, что очень удобно, если вы делаете сложные вещи. Итак, как отмечает Даниэль Фишер в комментарии, конвейер, который вы описали в своем вопросе, может быть составлен следующим образом:

reader >>> partition >>> (handler1 *** handler2) >>> writer

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

newtype Proc' a b = Proc (Source a -> Sink b -> IO ())

А затем соответствующим образом реализовать комбинаторы.

Так вот, на что вы смотрите: словарь для разговора о создании процессов, который содержит немного кода для повторного использования, но в первую очередь поможет вам мыслить при реализации этих комбинаторов для определения полезного определения процессора в вашем домене.

Один из моих первых нетривиальных проектов на Haskell состоял в том, чтобы реализовать стрелку для квантовой запутанности ; этот проект заставил меня по-настоящему понять образ мышления Хаскелла, что стало переломным моментом в моей карьере программиста. Может быть, этот ваш проект сделает для вас то же самое? : -)

7 голосов
/ 16 ноября 2011

Благодаря ленивому вычислению мы можем выразить конвейеры в терминах композиций обычных функций в Haskell. Вот пример, который вычисляет максимальную длину строки в файле:

main = interact (show . maximum . map length . lines)

Все здесь - обычная функция, как, например,

lines :: String -> [String]

но благодаря ленивым вычислениям эти функции обрабатывают ввод только постепенно и только столько, сколько нужно, как в конвейере UNIX.

4 голосов
/ 16 ноября 2011

Пакет перечислителя для Haskell является хорошей основой для этого.Он определяет три типа объектов:

  1. Перечислители, которые производят данные в чанках.
  2. Итерации, которые потребляют порции данных и возвращают значение после достаточного потребления.которые сидят в середине трубопровода.Они потребляют куски и производят куски, возможно, с побочными эффектами.

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

ET.enumHandle stdin $$ ET.map toUpper =$ ET.iterHandle stdout

, где модуль Data.Enumerator.Text был импортирован как ET.

2 голосов
/ 10 октября 2012

В инфраструктуре Yesod используется библиотека труб Haskell в виде пакета трубопровода .

...