Версия 1.3 моей библиотеки имитационного моделирования Айвики на Haskell

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

Айвика уже много лет умеет:

• системную динамику (обыкновенные диффуры и разностные уравнения);
• дискретно-событийное моделирование (управляемое временем, событиями и процессами);
• самые базовые вещи из агентного моделирования.

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

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

Все работает на единой схеме. Формализм и базовое API описаны в документе PDF на странице Wiki проекта Aivika (пока к сожалению, только на английском):

https://github.com/dsorokin/aivika/wiki

Сам код библиотеки полностью документирован с помощью комментариев haddock. Это стандартный для Haskell способ документирования API.

Для реализации я использовал очень много разных вещей из мира функционального программирования - ввел несколько монад и две стрелки. Многое взял из учебников по Haskell и F#. Библиотека по всей своей природе целиком принадлежит миру ФП, хотя и ориентирована на императивные вычисления: стохастику и прочее IO. Просто некоторые слишком узком понимают ФП, ограничивая себя рамками детерминированности, но забывая при этом, что IO вполне поддается ссылочной прозрачности. У меня нигде там нет unsafePerformIO, и это особый предмет гордости :)

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

Можем сохранить таблицы в файлы CSV, нарисовать графики, гистограммы, подсчитать сводную статистику по переменным, показать на специальном графике тренд и вероятные границы отклонения по правилу 3-х сигм. 

В результате эксперимента создается файл HTML с результатами, который может быть просмотрен в любом современном браузере интернета.

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

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

Вообще, моя библиотека предоставляет eDSL, который органично вписывается в язык Haskell. При определении модели мы можем использовать практически весь арсенал средств этого языка программирования общего назначения, что открывает просто фантастические возможности для описания очень сложных процессов, конечно, при соответствующем знании языка. Дополняет эти возможности то, что заявленные выше парадигмы имитационного моделирования реализованы на основе единой схемы - они все интегрированы между собой, и фактически сводятся друг к другу.

Библиотека со всеми пакетами размещена на официальном репозитории Hackage DB, который интегрирован с Haskell Platform. Используемая лицензия очень либеральна - BSD3. Код распространяется полностью в открытых исходниках. 

На винде устанавливается так:

> cabal update

> cabal install aivika

> cabal install aivika-experiment

> cabal install aivika-experiment-chart

> cabal install aivika-experiment-diagrams

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

На маке (OS X) и особенно линуксе лучше установить еще другой рендерер графиков:

$ cabal install aivika-experiment-cairo

Он использует библиотеку Cairo, и графики на мой взгляд получаются красивее.

Будет интересно получить комментарии и пожелания. Так же интересует, насколько вероятна возможность консалтинга. Готов рассмотреть взаимовыгодные и заманчивые предложения. 

F# на юниксе

Оказывается, можно замечательно использовать F# на маке с помощью Mono и Xamarin Studio. Очень удобно, и мой проект от Visual Studio работает прекрасно. Попробовал редактировать и создавать файлы в Xamarin Studio. Мне понравилось. Даже лень было сегодня загружаться в винду, где у меня установлена Visual Studio. 

Надо сказать, что ребята из Xamarin достигли заметного прогресса. Что меня больше всего потрясло, так это то, что в некоторых моих тестах Mono заметно обгоняет .NET, делая поправку на то, что гонял я тесты на одной машине, но под разными операционками, да и тесты, вероятно были несколько специфическими. Ни за что бы не поверил в возможность такого еще пару лет назад!

А вдруг есть такой чудесный плагин для Scala?

Пока самые лучшие и знаменитые наши умы заняты очень серьезным мероприятием, хочу поделиться со всеми остальными о наболевшем.

Есть у меня одна уже работающая задумка, но мне нужен для Scala хороший и удобный синтаксический сахар для монад (эх, еще бы для стрелок…). Мечтаю о чем-то подобном computation expressions из F# - это такой аналог нотации do для языка, в котором нет классов типов. Как понимаю, нужен плагин к компилятору в случае Scala.

Ни встроенный for-comprehension, ни плагин продолжений не впечатляют нисколько. Отчасти они дублируют друг друга, но ни одно из них не решает свою задачу хорошо в моем понимании, давно извращенным другими языками. В общем, тот случай, где количество не переходит в качество, и даже не помышляет о том.

Очень хотел использовать Scala, но сейчас пребываю в полной печали. Для моей задачи технически идеально подходит Haskell, но я хочу продвинуть библиотеку в широкие массы, а потому Haskell пока хорош только как полигон для выработки, обкатки и кристаллизации моих безумных идей, и здесь он свою миссию уже выполнил на все 350% с блеском и шиком. Но сейчас хочется получить уже широкую аудиторию из исключительно меркантильных соображений, а потому интересует Scala. 

Комментарий о хвостовой рекурсии

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

В прошлом году вышел замечательный перевод книги Пола Грэма "ANSI Common Lisp". В оригинале этой книги на странице 216 есть такое предложение: "A good compiler can compile a tail call into a goto, and so can compile a tail-recursive function into a loop". Дальше идет довольно общее описание того, как это может быть сделано.

Проблема в том, что без знания контекста тот текст можно неправильно истолковать. Все встает на свои места, если обратиться к книге PAIP Питера Норвига, которую Пол Грэм безусловно читал. В той книге приведена некая абстрактная машина. Там действительно хвостовая рекурсия компилируется в циклы, но в циклы не языка высокого уровня, а в циклы ассемблера той абстрактной машины (фактически через goto). Вот, в чем загвоздка.

Многие почему-то считают, что хвостовую рекурсию можно всегда преобразовать в циклы Scala, F# или Common Lisp. Мне кажется это неправильным. Можно придумать контр-пример. Достаточно обернуть рекурсивный вызов в лямбду и дальше передать эту лямбду другой функции. Например, компилятор Scala не сможет это превратить в цикл на уровне явовского байт-кода, а на уровне абстрактной машины из PAIP цикл получился бы сам собою.

Функциональная чистота и ссылочная прозрачность

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

Что касается "функциональной чистоты", то с нею более-менее понятно: результат зависит только от входных параметров, и функция не производит внешних побочных эффектов в том смысле, что не изменяет состояние окружающего мира. Для статически типизированных языков это обычно означает, что все, что функция делает и производит, описано в ее сигнатуре. Тут я изучал самые разные источники, включая учебники по Common Lisp, Haskell, F# и Scala. Трактовка везде примерно такая, почему-то за исключением одного русскоязычного учебника (не буду называть).

Для определенности возьмем такую вариацию этих терминов из еще невышедшей книги "Functional Programming in Scala":

"An expression e is referentially transparent if for all programs p, all occurrences of e in p can be replaced by the result of evaluating e, without affecting the observable behavior of p. A function f is pure if the expression f(x) is referentially transparent for all referentially transparent x."

Здесь содержатся одно из возможных определений для ссылочной прозрачности и вывод о том, что если выражение f(x) ccылочно-прозрачно для всех ссылочно-прозрачных x, то функция f является чистой. Определение чистоты в книге дается обычное в другом месте. Меня смущает то, что хотя используется слово "if" в последнем предложении, трактуется оно почему-то как "if and only if".

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

Второе. У меня складывается ощущение, что ссылочная прозрачность жестко привязана к конкретному языку программирования, тогда как свойство функции быть чистой является в большой степени над-языковым. Припоминая ассемблер PDP-11, сдается мне, что даже на уровне ассемблера можно оперировать чистотой, если ввести определенные допущения для стека (или стеков). Это так? Если да, то тогда оба понятия действительно не могут быть эквивалентными уже по этому.

В общем, прошу вразумить и поставить на путь истинный.

Ряд Фибоначчи

Давеча рекламировал свои обобщенные последовательности (Generic Sequences), а какие могут быть последовательности без ряда Фибоначчи? Это что-то вроде обязательного ритуала. Опустим здесь тот факт, что я создал эту библиотеку для вполне практической задачи, когда мне понадобилось быстро и эффективно сравнивать деревья, а там ленивые последовательности дюже полезны.

Итак, ниже приведена рабоче-крестьянская версия, которая выдает ленивую бесконечную последовательности ряда Фибоначчи через то, что я назвал Sequence Comprehension:

(defparameter *fibs-1*
  (with-seq/cc
    (do ((a 1 b)
         (b 1 (+ a b)))
        (nil)
      (yield/cc a))))

Очень просто, не правда ли?

Теперь каноническая версия через поток:

(defparameter *fibs-2*
  (reclet 
      ((fibs (seq->stream
              (seq-cons
               1 (seq-cons
                  1 (seq-map
                     (lambda (x)
                       (+ (first x) (second x)))
                     (seq-zip
                      (delay-seq fibs)
                      (delay-seq (seq-cdr fibs)))))))))
    fibs))

Проверка:

? (seq->list (seq-take 20 *fibs-1*))
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)

? (seq->list (seq-take 20 *fibs-2*))
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)

Дополнение.

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

(defparameter *fibs-3*
  (make-seq
   (labels ((traverse (a b)
              (enum-cons a (traverse b (+ a b)))))
     (traverse 1 1))))

Основная идея заключается в том, что мы работаем как с обычным списком, что очень удобно при обходе индуктивных/рекурсивных структур данных. Собственно, все комбинаторы написаны у меня в таком стиле.

И если вам по какой-то причине не нравятся комбинаторы, то результат можно получить с помощью известного макроса iter, для которого я добавил конструкцию in-seq:

? (iter (for i from 1 to 20)
        (for x in-seq *fibs-3*)
        (collect x))
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765) 

Обобщенные последовательности

Рекламирую свою новую библиотеку Generic Sequences [1] для Common Lisp. Она вводит обобщенные последовательности похожие на обычные списки Common Lisp, ленивые последовательности clojure, списки Haskell, а также похожие на итераторы, которые можно встретить в таких языках программирования как C#, F#, Java и Scala. С помощью комбинаторов легко создавать обобщенные последовательности, и их легко итерировать с помощью макроса ITER.

Более того, есть так называемое Sequence Comprehension, основанное на продолжениях из пакета CL-CONT. Это что-то похожее на синтаксис Sequence Expression из F# и конструкцию Yield из C#, где мы можем определить ленивую последовательность очень простым и декларативным способом.

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

Есть небольшая документация [2] в формате PDF.

[1] https://github.com/dsorokin/generic-sequences

[2] https://github.com/dsorokin/generic-sequences/blob/master/doc/generic-sequences-manual.pdf