Commits

Anonymous committed a23c134

iteratee: the type

Comments (0)

Files changed (1)

 "погружения" и "привязки" -- например, итерат, разбирающий две строки
 с помощью итерата "line", и возвращающий их как тупл, будет выглядеть так:
 
-  line >>= fun l1 ->
-  line >>= fun l2 ->
-  return (l1, l2)
+    line >>= fun l1 ->
+    line >>= fun l2 ->
+    return (l1, l2)
 
   И при этом операции привязки ">>=" (из монады итератов) в общем случае
 не будут вызывать операции привязки для монады ввода-вывода --
 типа "либо подстрока, либо подмассив" с выбором нужных функций для работы
 с чанком в рантайме, однако пока профайлер не показал необходимости
 этого.  (может, у вас покажет?)
+
+
+Итераты: тип данных и основные принципы работы.
+
+  Итераты представлены параметрическим типом iteratee 'el 'a, где 'el
+является типом элементов, которые будут в чанках подаваться в этот
+итерат, а тип 'a является типом конечного результата, который этот
+итерат выдаст, когда закончит обработку потока (но не обязательно
+полную обработку, он может оставить часть потока для следующих итератов).
+
+  Если итерат закончил работу, он представлен значением IE_done x, где
+x имеет тип 'a.  За это отвечает вариант
+
+    type iteratee 'el 'a =
+      [ IE_done of 'a
+      | ...
+      ]
+    ;
+
+  Если итерат не закончил работу, это может быть в случае либо ошибки,
+либо требования "дайте мне ещё данные".
+
+  Итераты поддерживают так называемые "recoverable errors", которые
+полезны в случаях, когда ошибка не фатальная, либо когда хочется
+реализовать какую-нибудь функциональность, не совсем естественную
+для потоковой обработки.  Например, Олег Киселёв реализует с помощью
+recoverable errors функциональность seek, перемещение по читаемому файлу.
+Автор этого документа предполагает в недалёком будущем реализовать через
+таковые ошибки что-то наподобие отслеживания позиции входных данных
+в файле (имя файла, номер строки, номер столбца) (однако неизвестно,
+получится ли красиво).
+
+  Есть также фатальные ошибки, после которых продолжение невозможно,
+но они не отличаются представлением от recoverable ошибок, отличие
+определяется энумераторами и энумератами, обрабатывающими конкретные
+ошибки.
+
+  Если итерат не закончил работу, он представлен значением
+IE_cont opt_err k, где opt_err -- опциональное значение, показывающее,
+почему итерат не закончил работу, равное None в случае требования ещё
+данных, и равное Some err в случае ошибки.
+
+  То есть, вырисовывается тип
+
+    type iteratee 'el 'a =
+      [ IE_done of 'a
+      | IE_cont of option err_msg and ...
+      ]
+    and err_msg = exn
+    ;
+
+  (типично буквой "k" обозначаются продолжения в continuation-passing
+style.)
+
+  Значение k ("продолжение") является функцией, которой будет передан
+следующий элемент потока (признак конца потока или чанк с данными;
+элемент с типом stream 'el).  Значит, тип будет иметь вид
+
+    type iteratee 'el 'a =
+      [ IE_done of 'a
+      | IE_cont of option err_msg
+               and (stream 'el -> ...)
+      ]
+    and err_msg = exn
+    ;
+
+
+  Функция k обязана вернуть монадное значение, чтобы можно было
+где-то "развязать" вычисления, выполняющиеся в итератах.  Это нужно
+для того, чтобы хоть где-то можно было выполнять какие-то сайд-эффекты
+при обработке композиции итератов.  Иначе, если бы не было "развязки",
+то всё, что выполняется в итератах, было бы обязано быть без сайд-эффектов.
+А так -- базовая монада используется, например, для чтения следующего
+блока данных в энумераторе, который кормит итераты чанками, читаемыми
+из файлов.
+
+  Кроме того, наличие базовой монады полезно тем, что можно совершать
+какие-либо действия ввода-вывода изнутри самих итератов, что часто
+полезно.
+
+  То есть, k возвращает значение с типом IO.m _, и тип получается:
+
+    type iteratee 'el 'a =
+      [ IE_done of 'a
+      | IE_cont of option err_msg
+               and (stream 'el -> IO.m ...)
+      ]
+    and err_msg = exn
+    ;
+
+  Что же должно возвратить k внутри монадного типа?  Очевидно, если
+итерат возвращает либо IE_done (a : 'a), либо IE_cont, то в случае
+выполнения этого продолжения необходимо будет вернуть тоже итерат
+и тоже с тем же типом -- iteratee 'el 'a.  Который, в свою очередь,
+будет либо нести результат (IE_done a), либо содержать ошибку
+(IE_cont (Some err) k), либо требовать продолжения (IE_cont None k).
+Тип получается:
+
+    type iteratee 'el 'a =
+      [ IE_done of 'a
+      | IE_cont of option err_msg
+               and (stream 'el -> IO.m (iteratee 'el 'a  *  ...))
+      ]
+    and err_msg = exn
+    ;
+
+  Однако, что очень важно, итераты должны композиционироваться
+"горизонтально": итерат, обработавший часть ввода, не должен жадно
+съедать весь поданный чанк, вместо этого он должен оставить то,
+что он не съел, следующему итерату.  Вспомните пример с чтением
+двух строк:
+
+    line >>= fun l1 ->
+    line >>= fun l2 ->
+    return (l1, l2)
+
+  В случае, если чанк содержит символы "abc\ndef\nghi\n", первый итерат,
+читающий первую строку, должен будет вернуть IE_done "abc\n", но
+он также должен указать, что второму итерату обязан достаться чанк,
+содержащий символы "def\nghi\n".
+
+  Соответственно, второй итерат вернёт IE_done "def\n" и оставит чанк
+"ghi\n", и общая композиция этих итератов вернёт IE_done ("abc\n", "def\n"),
+оставив после себя чанк "ghi\n".
+
+  Поэтому внутри значения базовой монады итерат обязан вернуть часть
+непоглощённого потока, stream 'el.
+
+  Итоговый тип итератов таков:
+
+    type iteratee 'el 'a =
+      [ IE_done of 'a
+      | IE_cont of option err_msg
+               and (stream 'el -> IO.m (iteratee 'el 'a  *  stream 'el))
+      ]
+    and err_msg = exn
+    ;