1. Dmitry Grebeniuk
  2. ocaml-iteratees-tutorial-rus

Commits

Dmitry Grebeniuk  committed dcc80ff

quotes

  • Participants
  • Parent commits 1ddd318
  • Branches default

Comments (0)

Files changed (1)

File input.txt

View file
  • Ignore whitespace
 
   - итераты обычно пишутся так, что, имея заданное количество входных
     элементов, они используют ограниченный объём вычислений и памяти,
-    выдавая либо результат (значение или ошибку).
+    выдавая результат (значение или ошибку).
 
   - часты случаи, когда каждая функция из цепочки обработки данных
     выделяет фиксированный буфер, который затем используется при обработке
   - непросто связать Stream с асинхронным вводом-выводом; автору
     текста кажется, что это потребует фокусов с delimited continuations,
     тоже детищем Олега Киселёва (по крайней мере в применении к окамлу),
-    но совершенно другим детищем,
+    но с совершенно другим детищем,
   - код на Stream недостаточно декларативный/высокоуровневый в среднем
     случае (хотя это частично решается синтаксическим расширением для работы
     со Stream-потоками).
   Данные хранятся в так называемых "подмассивах".  Подмассив -- это запись,
 содержащая ссылку на сам массив с данными, начальное смещение данных в этом
 массиве и длину данных.  Они и логика работы с ними описана в
-модуле Subarray (файл subarray.ml).
+модуле Subarray (файл subarray.ml в библиотеке ocaml-iteratees).
 
 - почему не списки?
   Для эффективности операций, работающих с чанками, например, тех,
   которые берут какие-то части чанка, а не просто последовательно идут
   по нему (например, для операции, возвращающих последовательность
   первых n элементов).  В случае списков этого нельзя достичь иначе,
-  чем через копирование части списка.
+  чем через копирование части списка.  В случае подмассивов это
+  достигается созданием значения, содержащего ссылку на массив
+  и на новые начальное смещение и длину подмассива.
 
 - почему не строки?
   Потому что итераты в целом полиморфны, если не указано иного.  Они
 
 - почему изменяемые массивы это безопасно?
   Потому что:
-  1. чанки рождаются только в энумераторах (в том числе в энумератах),
+  1. подмассивы (и чанки, содержащие подмассивы) рождаются только
+     в энумераторах (в том числе в энумератах),
   2. у каждого энумератора есть свой массив, и вложенные итераты
      по правилам хорошего тона должны только читать этот массив и не
      модифицировать его (хотя это и допустимо в некоторых случаях,
      хорошего тона, всё безопасно.
 
   Однако автор этого документа думал про представление данных в виде
-типа "либо подстрока, либо подмассив" с выбором нужных функций для работы
-с чанком в рантайме, однако пока профайлер не показал необходимости
-этого.  (может, у вас покажет?)
+типа "либо подстрока, либо подмассив" с выбором нужных функций
+для работы с чанком в рантайме, однако пока профайлер не показал
+необходимости этого.  (может, у вас покажет?)
 
 
 Итераты: тип данных и основные принципы работы.
 
-  Итераты представлены параметрическим типом iteratee 'el 'a, где 'el
-является типом элементов, которые будут в чанках подаваться в этот
+  Итераты представлены параметрическим типом "iteratee 'el 'a", где
+'el является типом элементов, которые будут в чанках подаваться в этот
 итерат, а тип 'a является типом конечного результата, который этот
 итерат выдаст, когда закончит обработку потока (но не обязательно
 полную обработку, он может оставить часть потока для следующих итератов).
 
-  Если итерат закончил работу, он представлен значением IE_done x, где
-x имеет тип 'a.  За это отвечает вариант
+  Если итерат закончил работу, он представлен значением "IE_done x",
+где x имеет тип 'a.  За это отвечает вариант
 
     type iteratee 'el 'a =
       [ IE_done of 'a
 ошибки.
 
   Если итерат не закончил работу, он представлен значением
-IE_cont opt_err k, где opt_err -- опциональное значение, показывающее,
+"IE_cont opt_err k", где opt_err -- опциональное значение, показывающее,
 почему итерат не закончил работу, равное None в случае требования ещё
-данных, и равное Some err в случае ошибки.
+данных, и равное "Some err" в случае ошибки.
 
   То есть, вырисовывается тип
 
 
   Значение k ("продолжение") является функцией, которой будет передан
 следующий элемент потока (признак конца потока или чанк с данными;
-элемент с типом stream 'el).  Значит, тип будет иметь вид
+элемент с типом "stream 'el").  Значит, тип будет иметь вид
 
     type iteratee 'el 'a =
       [ IE_done of 'a
 какие-либо действия ввода-вывода изнутри самих итератов, что часто
 полезно.
 
-  То есть, k возвращает значение с типом IO.m _, и тип получается:
+  То есть, k возвращает значение с типом "IO.m _", и тип получается:
 
     type iteratee 'el 'a =
       [ IE_done of 'a
     ;
 
   Что же должно возвратить k внутри монадного типа?  Очевидно, если
-итерат возвращает либо IE_done (a : 'a), либо IE_cont, то в случае
+итерат возвращает либо "IE_done (a : 'a)", либо IE_cont, то в случае
 выполнения этого продолжения необходимо будет вернуть тоже итерат
-и тоже с тем же типом -- iteratee 'el 'a.  Который, в свою очередь,
-будет либо нести результат (IE_done a), либо содержать ошибку
-(IE_cont (Some err) k), либо требовать продолжения (IE_cont None k).
-Тип получается:
+и тоже с тем же типом -- "iteratee 'el 'a".  Который, в свою очередь,
+будет либо нести результат ("IE_done a"), либо содержать ошибку
+("IE_cont (Some err) k"), либо требовать продолжения ("IE_cont None k").
+Тип получается таким:
 
     type iteratee 'el 'a =
       [ IE_done of 'a
     return (l1, l2)
 
   В случае, если чанк содержит символы "abc\ndef\nghi\n", первый итерат,
-читающий первую строку, должен будет вернуть IE_done "abc\n", но
+читающий первую строку, должен будет вернуть " IE_done "abc\n" ", но
 он также должен указать, что второму итерату обязан достаться чанк,
 содержащий символы "def\nghi\n".
 
-  Соответственно, второй итерат вернёт IE_done "def\n" и оставит чанк
-"ghi\n", и общая композиция этих итератов вернёт IE_done ("abc\n", "def\n"),
-оставив после себя чанк "ghi\n".
+  Соответственно, второй итерат вернёт " IE_done "def\n" " и оставит чанк
+"ghi\n", и общая композиция этих итератов вернёт
+" IE_done ("abc\n", "def\n") ", оставив после себя чанк "ghi\n".
 
   Поэтому внутри значения базовой монады итерат обязан вернуть часть
-непоглощённого потока, stream 'el.
+непоглощённого потока, "stream 'el".
 
   Итоговый тип итератов таков:
 
   Этот итерат должен брать поток с элементами произвольных типов,
 обозначим тип как 'el.  Итерат должен возвращать первый элемент потока,
 но бывают случаи, когда поток закончился.  Поэтому разумно будет
-возвращать тип option 'el.  То есть, итерат будет иметь вид
+возвращать тип "option 'el".  То есть, итерат будет иметь вид
 
     value peek : iteratee 'el (option 'el) =
       ...
 
   Этот итерат не сразу возвращает значение, ему необходимо исследовать
 входящий поток, хотя бы на один элемент вперёд.  Следовательно, он
-должен представлять собой значение вида IE_cont None k -- "требую ещё
+должен представлять собой значение вида "IE_cont None k" -- "требую ещё
 данных".  None потому, что собственно ошибки в этом нет, это нормальный
 ход работы данного итерата.
 
         ...
     ;
 
-  Функция является тем самым продолжением, которое берёт поток (stream 'el)
-и возвращает результат работы продолжения:
-IO.m (iteratee 'el (option 'el) * stream 'el).
+  Функция является тем самым продолжением, которое берёт поток с типом
+"stream 'el" и возвращает результат работы продолжения:
+"IO.m (iteratee 'el (option 'el) * stream 'el)".
 
-  s имеет тип stream 'el, и по правилам хорошего тона необходимо разобрать
-его паттерн-матчингом.
+  s имеет тип "stream 'el", и по правилам хорошего тона необходимо
+разобрать его паттерн-матчингом.
 
     value peek : iteratee 'el (option 'el) =
       IE_cont None step
   В случае чанка необходимо проанализировать, является ли чанк пустым.
 Если он не пустой (то есть, если S.is_empty вернуло False),
 берём первый элемент чанка через S.get_first_item и возвращаем его
-в Some конструкторе, возвращая исходный поток.
+в Some-конструкторе, возвращая исходный поток.
 
     value peek : iteratee 'el (option 'el) =
       IE_cont None step
   Если же чанк пустой, необходимо вернуть указание "итерат продолжит
 работу, если ему будет передан ещё чанк".  А продолжить работу он
 сможет из той же функции step, которая обработала первый чанк.  То есть,
-возвращённый итерат будет иметь вид IE_cont None step.  А возвращённый
+возвращённый итерат будет иметь вид "IE_cont None step".  А возвращённый
 чанк с остатком потока будет равен s.
 
   Итого, результат выглядит так:
 
   Итераты должны соблюдать некоторые правила хорошего тона.  Например,
 одно из них таково: если итерат запрашивает продолжения данных
-(IE_cont None k), то он обязан обработать весь поток, который ему был
+("IE_cont None k"), то он обязан обработать весь поток, который ему был
 дан.  Это правило окажется полезным при композиции итератов.
 
   Таким образом, разумно ввести вспомогательный комбинатор, который
 будет брать функцию-продолжение (в итерате peek это будет функция step)
-и возвращать её в IE_cont None, и возвращать пустой поток.  Существует
-значение empty_stream, равное чанку, не содержащему никаких данных.
+и возвращать её в "IE_cont None ...", и возвращать пустой поток.
+Существует значение empty_stream, равное потоку, являющемуся чанком,
+не содержащим никаких данных.
 
   У нас в peek это правило выполняется неявно: в случае, когда
-S.is_empty c = True, очевидно, что поток s пустой, поэтому нет ничего
+"S.is_empty c = True", очевидно, что поток s пустой, поэтому нет ничего
 плохого в том, чтобы возвратить именно s вместо empty_stream.
 
   Кроме того, мы должны возвращать значение из базовой монады --
 элемент из потока, но при этом возвращать поток без первого элемента,
 что полезно для простого поэлементного разбора потока.
 
-  Итерат будет иметь тип iteratee 'el 'el, то есть, будет возвращать
-непосредственно элемент потока, без оборачивания его в option 'el,
+  Итерат будет иметь тип "iteratee 'el 'el", то есть, будет возвращать
+непосредственно элемент потока, без оборачивания его в "option 'el",
 в отличие от peek.
 
   Ещё из отличий от peek: здесь будет использоваться не функция
 S.get_first_item, а функция S.destruct_first_item, которая будет
-возвращать либо None для пустого подмассива, либо Some (h, t),
+возвращать либо None для пустого подмассива, либо "Some (h, t)",
 где h будет первым элементом подмассива, а t будет остатком этого
-подмассива, тоже подмассивом.  (это напоминает разбор списка list 'a
-в индуктивный тип [None | Some (head, tail)].)
+подмассива, тоже подмассивом.  (это напоминает разбор списка "list 'a"
+в индуктивный тип "[None | Some (head, tail)]".)
 
   Кроме этого, будет отличие в возвращаемых ошибках.  Если итерату
 head дают поток, содержащий ошибку (например, ошибку ввода-вывода),
-он получит на вход значение EOF (Some err).  В этом случае необходимо
+он получит на вход значение "EOF (Some err)".  В этом случае необходимо
 вернуть эту ошибку как результат работы.  Если же ошибки нет, но
 поток просто закончился, для итерата head это тоже является ошибкой,
 и её будем возвращать как ошибку End_of_file.
 исключениями, что удобно для монады Identity.
 
   Итак, для обработки ошибок в итерате head (для преобразования
-EOF None в ошибку End_of_file) напишем функцию, которая будет
+"EOF None" в ошибку End_of_file) напишем функцию, которая будет
 анализировать поток и возвращать нужную ошибку:
 
     value (set_eof : stream 'el -> err_msg) s =
     ;
 
   В данной функции не слишком понятен разве что возврат End_of_file
-для потоков, содержащих данные (Chunk _), но: 1. этот код написал
+для потоков, содержащих данные ("Chunk _"), но: 1. этот код написал
 не я, а Олег Киселёв, 2. делать по-другому смысла мало, так как
 функцию set_eof будут использовать только для потоков, не содержащих
 данные, поэтому можно оставить и так, 3. есть вероятность, что где-то
 
   Если же получилось разбить подмассив на голову и хвост, то с помощью
 комбинатора ie_doneM возвращаем голову как результат, а хвост, являющийся
-подмассивом, оформляем в чанк с помощью конструктора потоков: Chunk t.
+подмассивом, оформляем в чанк с помощью конструктора потоков: "Chunk t".
 Тут оказывается полезным то, что итераты в общем случае не обязаны
 рассчитывать на непустой чанк, а ведь подмассив t может оказаться пустым,
 если в исходном массиве был ровно один элемент h.  Поэтому, не долго думая,
 
   Если же в функцию step передали окончание потока, то с помощью set_eof
 получаем реальную ошибку, которую передаём как результат в
-IE_cont (Some реальная_ошибка).
+"IE_cont (Some реальная_ошибка)".
 
   Однако, данную ошибочную ситуацию с точки зрения гибкости лучше сделать
 recoverable.  Представим, что "пользователь" (тот, кто использует head)