gds (gds) wrote,
gds
gds

ocaml-lazy-labelled

Ну, вы меня знаете. Не люблю я ленивые рекурсивные вычисления. Хотя бы потому, что они прекрасно умеют зацикливаться, и по словленному исключению CamlinternalLazy.Undefined не определить, между какими данными возник цикл.
Однако один из текущих алгоритмов (в earley parser, вычисление "нуллябельных" нетерминалов), по прикидкам, будет на 100..200 строк кода меньше, если его изобразить в виде ленивых рекурсивных вычислений.
Надо что-то делать. И вчера я таки сообразил, что именно.
Как определить, какие значения формируют цикл вычислений, если они все сами по себе ленивые? Нужно их пометить не-ленивыми значениями, вот и всё. А отлов минимального цикла -- дело техники.
Что меняем в готовом алгоритме для того, чтобы ловить циклы:
  1. при помощи функтора создаём новый модуль Lazy (аргумент функтора содержит тип метки, так как исключения у нас не полиморфные),
  2. при создании вместо lazy (expr) указываем { Lazy.l = your_label; v = lazy (expr) },
  3. вместо ловли CamlinternalLazy.Undefined ловим Lazy.Cycle labels_list со списком меток, образующих цикл.

Репозиторий: http://bitbucket.org/gds/ocaml-lazy-labelled/src
Примеры: http://bitbucket.org/gds/ocaml-lazy-labelled/src/tip/tests.ml
Пока нерешённая проблема с форсированием ленивых значений из разных модулей (для разных типов меток; там получаются перекрёстные L1.force и L2.force, и цикл будет отловлен только по одному из типов меток, и вообще, не факт, что корректно. Поэтому пока так не делайте.)
Да, и модуль не thread-safe, как и стандартный модуль Lazy.
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments