Книга про моделирование и Haskell

Здесь тоже поделюсь. Написал книгу про имитационное моделирование с той точки зрения, как я это реализовал на языке Haskell в своем комплексе программных библиотек Айвика. Книгу назвал «Aivika: Computation-based Modeling and Simulation in Haskell».

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

http://aivikasoft.com/downloads/aivika/aivika.pdf

https://github.com/dsorokin/dsorokin.github.io/blob/master/downloads/aivika/aivika.pdf

Книга охватывает последовательное моделирование, параллельное и распределенное моделирование, а также вложенное моделирование. Фокус на дискретно-событийном моделировании, прежде всего, процесс-ориентированной парадигме, которая сводится на уровне реализации к событийно-ориентированной.

Начну представлять книгу с конца.

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

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

Главная же часть книги описывает основные концепции дискретно-событийного моделирования применительно к последовательной имитации. Дискретные события, дискретные процессы, ресурсы, вытеснение ресурса, очереди и т.д. Но очень важно заметить, что практически все это работает и в случае распределенного моделирования, и вложенного моделирования, включая GPSS-подобный предметно-ориентированный язык, который тоже бегло описан.

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

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

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

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

Трансляция модели из Python в Haskell

Вспомнив известные слова про гору и Магомета, решил сделать свои наработки более доступными. Создал для языка программирования Python пакет aivika-modeler, который позволяет создавать дискретно-событийные модели. а затем запускать основанные на них имитационные эксперименты по методу Монте-Карло с тысячами запусков в серии и более.

Пакет больше предназначен быть неким клеем, с помощью которого на языке Python можно соединять и объединять готовые компоненты в единую модель, причем сами компоненты предполагается создавать уже на языке Haskell. Однако, во многих случаях должно хватить существующего набора компонент, и поэтому часто можно ограничиться одним языком Python. В планах добавить поддержку GPSS-подобного DSL.

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

Итак, модель описывается на языке Python. По ней автоматически создается соответствующий код на языке Haskell. Более того, создается готовый проект на основе системы сборки Stack. Собственно, это главное техническое требование - на системе пользователя должен быть установлен Stack. Здесь предвижу некоторые возможные трудности с пакетом old-time на некоторых системах Windows, но надеюсь, что со временем они благополучно разрешатся.

Так вот, автоматически созданный проект на Stack собирается, а потом запускается на исполнение. В случае успеха в самом конце открывается веб-браузер с результатами имитационного эксперимента. Там могут быть графики, гистограммы, ссылки на таблицы в формате CSV, сводная статистика и прочая информация. Вид и формат желаемых итоговых результатов задается также на языке Python.

Мне был довольно интересен такой эксперимент по использованию Haskell из Python. Может быть, кто-нибудь возьмет идею на вооружение

GPSS на Haskell

Если кто еще не знает, GPSS - это один из самых известных специализированных языков дискретно-событийного моделирования. Так вот, я добавил в AivikaSim [http://www.aivikasoft.com/ru/products/aivikasim.html] поддержку GPSS-подобного предметного-ориентированного языка. Это пакет aivikasim-gpss [https://github.com/dsorokin/aivikasim-gpss]. Вот здесь находится работающий тестовый пример [https://github.com/dsorokin/aivikasim-gpss-test].

Постарался охватить основные моделирующие блоки, такие как SEIZE, PREEMPT, GATHER, ASSEMBLE, MATCH. Другие либо имеют явные аналоги у меня, либо требуют небольшого программирования как в случае блоков LINK и UNLINK. Не гарантируется точного совпадения результатов с GPSS World, так как логика работы с транзактами у меня совершенно иная, но в некоторых случаях результаты получаются очень близкими.

Вот, здесь примеры моделей [https://github.com/dsorokin/aivikasim-gpss/tree/master/examples] из красной книги Шрайбера по GPSS. Там в начале каждого примера приводится соответствующий код модели на языке GPSS World. Можно сличить результаты.

Example2A.hs означает, что это пример 2A из книги, а вот Example7-26.hs означает, что это соответствует модели на рисунке 7.26. Модели с окончанием Trans, такие как Example2BTrans.hs, означают, что там используется обобщенная версия AivikaSim. Фактически это означает, что приведенный код готов для использования в распределенной имитации.

Более того, пример Example7-26Distributed.hs непосредственно запускается через модуль распределенного моделирования. В данном случае это формально последовательная модель, но запускается она фактически в виде распределенной, т.е. она готова для кластера компьютеров. Используется оптимистичный алгоритм деформации времени.

Сразу напишу, что хотя для приведенных моделей удалось добиться очень хорошего соответствия с GPSS, то вот для примера 5D из книги Шрайбера такого близкого соответствия, скорее всего, не получится. Сейчас совпадение идет в 9 случаях против одного, где модель будет уже другой. Причем, совпадает даже на очень нетривиальных моделях, где важен порядок обработки транзактов.

Касательно скорости моделирования. Модуль GPSS-подобного языка последовательной версии AivikaSim моделирует примерно в 5-7 раз медленнее, чем GPSS World, но зато позволяет использовать разные методы в рамках одной модели, например, агенты и события. Для сравнения, распределенный модуль AivikaSim на последовательных задачах медленнее в раз 6-9, чем последовательная версия AivikaSim, но зато распределенную версию можно запустить много раз на разных узлах в рамках одной модели. Например, можно запустить 7 параллельно работающих локальных процессов на одной системе с 8-ядерным процессором.

Если кто захочет проверить результаты, то вот руководство по установке AivikaSim [https://github.com/dsorokin/aivikasim-installer].

Демо-тест распределенной имитации на монадах

Создал тестовый демонстрационный пример распределенной дискретно-событийной имитации на основе своего нового продукта AivikaSim. Тест легко воспроизвести по приведенной инструкции:

https://github.com/dsorokin/aivikasim-distributed-test

Код написан на языке Haskell, но для воспроизведения теста язык программирования знать не требуется.

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

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

Особая фишка в том, что узлы можно размещать, используя ненадежные соединения и обычные компьютеры. То есть, теоретически кластер может состоять из машин, расположенных в разных континентах, но вопрос тогда только в том, насколько быстро будет идти имитация, потому что для целей тестирования там сознательно создается очень много сообщений. Происходят постоянные откаты назад и попытки заново обработать дискретные события, потому как реализован оптимистичный алгоритм «деформации времени» (Time Warp).

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

Только стоит заметить, что восстановление имитации на Linux и macOS работает как часы, а вот на Windows немного похрамывает, но, видимо, это связано с тем, что у Haskell-сообщества Unix-системы приоритетнее, что скорее хорошо.

По приведенной ссылке лишь скромный небольшой демонстрационный пример, показывающий возможности системы AivikaSim. 

Сетевое моделирование с Айвикой

Давно присматриваюсь к сетевому моделированию (англ. network simulation). Нахожу, что многое можно моделировать с помощью моей Айвики уже сейчас, в том числе, моделировать распределенно на кластере или параллельно на суперкомпьютере.

Основная идея такая. Обычно говорят о портах - источниках данных. В Айвике источники могут быть как активными, так и пассивными. Активный источник сам проталкивает данные дальше для обработки. Это у меня тип Signal a (или Signal m a в обобщенной версии). Тогда каналом будет просто преобразование одного сигнала в другой. Модуль будет функцией, отображающей входные сигналы на выходные.

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

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

Пассивные источники данных у меня в Айвике представлены потоками Stream a (или Stream m a в обобщенной версии). Их нужно запрашивать, чтобы вытянуть из них данные. Их можно распараллеливать для обработки, а потом снова сливать в один поток.

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

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

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

В общем, у меня есть достаточно общий аппарат, который может быть применен к широкому классу задач на мой взгляд. Более того, используя модуль aivika-distributed, такие задачи можно обсчитывать распределенно на кластере или параллельно в случае необходимости. Как раз на днях значительно улучшил этот модуль.

Распределенное моделирование c Айвикой

Обновил версию aivika-distributed, которую можно использовать для распределенного и параллельного моделирования. Реализована оптимистичная стратегия по методу Time Warp. В этой версии значительно улучшена синхронизация глобального времени. Используется алгоритм Самади. В общем, если соединения между узлами достаточно надежные, то распределенная имитация должна вполне хорошо работать.

Чтобы использовать эту версию, достаточно вооружиться документацией PDF по базовой версии Айвики. Здесь все то же самое, т.е. события, процессы, ресурсы, сигналы, потоки транзактов, все это применимо и к распределенной версии. Только типы будут выглядеть по другому. Там, где был Event a, станет Event DIO a и т.д.  Последний Event - это фактически монадный трансформер, но я решил не добавлять к его названию букву T, как это обычно делают, а сохранить все названия из базовой версии. Тому были причины.

Итак, вооружившись документацией по базовой версии Айвики, можно создавать имитационные модели. Распределенность добавляется через посылку и прием сообщений вот из этого модуля Message. 

Собственно, все! В следующем сообщении напишу, как это можно применить к сетевому моделированию (англ. network simulation)

Айвика как конструктор общецелевых библиотек имитационного моделирования

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

Айвика для кластера и суперкомпьютера

В прошлую субботу выпустил первую версию [5] своей Айвики, которая позволяет создавать и обсчитывать параллельные распределенные дискретно-событийные модели на кластере и/или суперкомпьютере.

В общем, идея такая. 

У меня есть основная версия [2] обще-целевой библиотеки, о которой я много писал у себя в блоге. Она построена на основе стандартного вычисления IO. Самая быстрая версия. Можно автоматизировать вывод графиков и таблиц. Есть документация [1] в формате PDF. Много примеров.

Потом я обобщил эту версию для произвольных вычислений, которые должны удовлетворять небольшому числу ограничений, в числе которых возможность создавать изменяемые ссылки и возможность иметь очередь событий. Так родилась обобщенная версия [3] библиотеки. Это тоже обще-целевая библиотека с возможностью формулировать модели в терминах событий, дискретных процессов, очередей, ресурсов, потоков транзактов, процессоров и т.п., но в рамках задаваемого извне типа вычислений. Практически совпадает с основной версией на уровне реализации, в том числе, в названиях, но типы и сигнатуры функций другие.

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

Так родилась версия [4] для вложенных имитаций. Это когда из «настоящего» мы можем относительно дешево и быстро заглядывать в «будущее» модели столько раз, сколько необходимо, а потом на основе полученной информации принимать решения уже в «настоящем». Конек в относительной дешевизне создания вложенных имитаций и в том, что это по-прежнему обще-целевая библиотека имитационного моделирования.

Теперь же воплотил в жизнь еще и версию [5] для параллельного распределенного имитационного моделирования. Тоже обще-целевая библиотека моделирования. Здесь независимые узлы могут обмениваться друг с другом асинхронными сообщениями, привязанными к временным меткам. Если на узле уже «будущее», а приходит сообщение в «прошлое», то происходит прозрачный откат до «прошлого» модели. Все сообщения, которые были посланы узлом и стали устаревшими, отменяются, и, соответственно, рассылаются так называемые «анти-сообщения». Короче, реализована оптимистичная стратегия с прозрачными, возможно, каскадными откатами на основе идей метода «деформации времени» (англ. «time warp»), датируемого началом 80-х.

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

[1] http://www.aivikasoft.com/ru/products/aivika.html

[2] http://hackage.haskell.org/package/aivika

[3] http://hackage.haskell.org/package/aivika-transformers

[4] http://hackage.haskell.org/package/aivika-branches

[5] http://hackage.haskell.org/package/aivika-distributed

Айвика: ветвящееся дискретно-событийное моделирование на Haskell

На днях сделал анонс своих новых наработок на Haskell Cafe. Повторю и здесь.

Выпустил три новых релиза. Это входит в серию библиотек, которую я условно называю Айвикой [1, 2, 3]. Главная новинка - пакет aivika-branches [3], который позволяет делать то, что я для себя назвал «ветвящимся дискретно-событийным моделированием» (англ. «branching discrete event simulation») с возможностью запускать вложенные имитации внутри имитации для предсказания и оценки будущего поведения системы на этапе самой имитации. Сейчас попробую описать подробнее.

Допустим, что у нас есть достаточно общая библиотека, которая позволяет реализовывать дискретно-событийные модели. Там могут быть потоки случайных заданий (требований, они же, тразакты). Могут быть ограниченные ресурсы, за которые идет конкурентная борьба дискретных процессов. Есть глобальная очередь событий. Есть просто очереди сущностей. Есть активности, привязанные к обработке событий и т.п. В общем, все то, что реализовано в моем пакете aivika [1].

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

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

Тогда мы можем запросить из текущего времени будущее значение заданного под-вычисления, как если бы мы продолжили текущую имитацию, но без фактического изменения самой имитации!

Именно это умеет делать следующая функция из нового пакета aivika-branches [3]:

futureEvent :: Double -> Event BrIO a -> Event BrIO a

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

Что касается типов, то здесь появляются монадные трансоформеры из другого пакета aivika-transformers [2], который является обобщение пакета aivika. На самом деле, пакет aivika-transformers я подготовил для реализации распределенного и параллельного дискретно-событийного моделирования, но он получился таким общим и гибким, что я смог его применить и к ветвящемуся дискретно-событийному моделированию.

Как я уже написал, фишка в том, что функция futureEvent относительно дешевая. Мы можем относительно быстро клонировать состояние целого мира имитационной модели! Это стало возможным во многом благодаря повсеместному использованию приемов функционального программирования (тут в скобках замечу, что очень забавно со стороны смотрятся те, кто наивно полагает по своему неразумению, что монада IO не относится к функциональному программированию. Просто не понимают, что функциональное и императивное программирование - это разные, но совсем не антагонистичные и не исключающие друг друга взгляды на то, как можно писать компьютерные программы. Эти оба взгляда вполне могут сосуществовать). Еще там используются такие вещи, как слабые ссылки для того, чтобы не было утечки пространства (англ. space leak) при разветвлении состояния ссылок, чтобы вовремя подчищалась память.

Фактически получаем дерево имитаций, которое нужно ограничивать или по уровню вложенности или с помощью метода ветвей и границ. Что-то похожее встречается в финансовом моделировании.

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

[1] http://hackage.haskell.org/package/aivika
[2] http://hackage.haskell.org/package/aivika-transformers
[3] http://hackage.haskell.org/package/aivika-branches

Релиз системы моделирования VisualAivika 5

Всем привет! Недавно выпустил версию своей визуальной системы моделирования для системной динамики VisualAivika.

Функциональное программирование здесь при том, что на конечном этапе исходная система диффуров преобразуется в модель в терминах моей библиотеки Айвика, которая написана на языке F#, который, как говорят его создатели, functional first.

Может быть интересна история создания Айвики. Первоначальная идея возникла при изучении Haskell, но я очень быстро переключился реализовывать идею на F#.  Первая версия на F# была ужасна. Ее до сих пор можно найти на простора интернета, но я не хочу давать ссылку на нее - пусть останется для истории.

Мне всегда было очень интересно реализовать Айвику на Haskell. И попытка переписать с F# на Haskell была неудачной. Нарвался на то, что компилятор Haskell предполагает ссылочную прозрачность, и соответственно оптимизирует код. Это решается с помощью прагм, что некрасиво, но главная нехорошесть была в другом. У меня там возникал вложенный двухэтажный одноименный тип в сигнатурах, что было прямым указанием на какую-то логическую ошибку.

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

Потом я уже переписал обратно c Haskell на F#. Пришлось пойти не некоторые упрощения и хитрости, но в целом, версия Айвики на F# примерно соответствует своей старшей сестрице, хотя и будет немного слабее. Именно переписанная версия теперь используется у меня в визуальной системе моделирования.

Возвращаясь к исходной теме. Даже если имитационное моделирование не входит в область ваших интересов, то может быть интересно то, что VisualAivika позволяет создавать так называемые Casual Loop Diagrams (CLD), область применения которых довольно широка. Это Systems Thinking или системное мышление.

Ниже показан пример такой диаграммы, которую я накидал в своей VisualAivika за минуту-две.

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

Версия 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, и графики на мой взгляд получаются красивее.

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

Ускоряющий инлайнинг

Компилятор GHC достаточно хорошо оптимизирует, когда код свален в одну кучу в одном модуле. Исполняется быстро, но с таким кодом работать неудобно. Так в одной куче у меня код долго и оставался, пока сегодня не попробовал прагму компилятора INLINE, которая подобна конструкции inline в C++.

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

Так вот, чудесная новость состоит в том, что прежняя скорость вернулась, какой она была до разбиения программы на модули. Другими словами, некоторые вещи ускорились в 3-4 раза.

Портировал одну свою работу на хаскель

Портировал свою библиотеку имитационного моделирования Айвика с F# на хаскель. Зарелизил самую первую версию 0.1 на Hackage DB вместе с 51-страничным описанием в формате PDF.

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

В общем, получил море позитива. Доволен результатом.

Разбиение на модули

Я просто обалдеваю. Разбил программу на модули, а она стала в 4,3 раза медленнее. Пришлось вернуть. Компилятор: The Glorious Glasgow Haskell Compilation System, version 6.12.1.

Следствия чистоты языка

Недавно открыл для себя мир функциональных языков. Увлечен. Особенно удивил Хаскель. Последний довольно необычен и не похож на другие языки. Решил для себя привести свои мысли о нем в порядок и записать в виде небольшого изложения. У меня получается, что Хаскель – очень продуманный язык, где разные концепции взаимосвязаны и следуют друг от друга. Отправной точкой служит чистота языка.

Другим мотивом послужило повышение внимания к теме Хаскеля со стороны некоторых программистов [lisp-univ-etc]. Есть ряд заблуждений и мифов относительно языка. Поэтому хотелось бы некоторые вещи прояснить для самого себя.

Итак, начало следует.

1. Чистота языка и ленивость.

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

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

2. Чистота монад.

Монады строятся на основе чистых функций, и потому они чисты. Несколько особняком стоят монады IO и ST, которые используют внутренности компилятора. Монада ST опирается на квантор всеобщности при своем запуске, который и гарантирует чистоту. Монада же IO по большому счету должна запускаться всего один раз самой исполняемой средой и на самом верхнем уровне, используя значение main. Этот запуск осуществляется всего один раз, и именно он привносит побочный эффект. Но запуск происходит как бы уже “за пределами” языка, и все формально остается чистым.

3. Монады как вычисления.

Монады можно воспринимать как вычисления, обычно отложенные. Когда нам нужно выразить побочный эффект мы не возвращаем конкретное вычисленное значение x, которое кстати может разниться от запуска к запуску. Вместо этого мы возвращаем само вычисление, которое уже позволяет получить x при некоторых начальных условиях. Такое вычисление можно обернуть в монаду m. Тогда само вычисление обозначим как m x.

Для получения результата вычисления существуют многочисленные функции, чьи названия начинаются со слова run: runST, runState, runWriter и т.д.

Другой способ запуска вычисления – это передача самого вычисления другому вычислению. Тогда первое вычисление становится частью второго. Здесь используются функции lift и liftIO. Это приводит нас к понятию монады-трансформера. Большинство монад, за исключением IO, имеют свои дубликаты – трансформеры, которые сами являются вычислениями и дополнительно могут быть контейнерами для других вычислений (монад). Монада IO является крайней, и у нее не может быть трансформера.

Кроме этого, вычисления могут непосредственно содержать вычисленные данные. Например, монады List и Identity так и делают. Поэтому дополнительный запуск вычисления им не нужен.

4. Программа как вычисление.

Программа на Хаскеле заключена в значении main, которое имеет тип IO (). То есть, это - некоторое вычисление в монаде IO, которое возвращает значение типа (). Причем само значение main является чистым. Для его получения не могут быть использованы никакие побочные эффекты, даже если то вычисление, которое задает main, их производит. Ведь мы не вычисляем, а возвращаем лишь вычисление!

Это принципиально отличается от большинства языков. На C++ функция main() выполняет последовательно программу. В Хаскеле main возвращает отложенное вычисление, которое еще надо запустить. Такой запуск осуществляется извне самой исполняющей средой Хаскеля. Просто другой взгляд на вещи.

5. Выражение побочного эффекта через чистые функции.

Мы не можем в чистом языке вызвать функцию, производящую побочный эффект. Но как показывает пример main, мы можем вернуть отложенное вычисление, которое уже при своем запуске произведет заданный побочный эффект. Это – ключевая идея.

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

Вопрос в том, насколько полным является базис, т.е. в данном случае набор примитивов, возвращающих значения в монаде IO. Поскольку в Хаскеле есть FFI, то мы можем считать такой базис достаточно полным.

6. Почему ленивость?

Чистый язык не обязан быть ленивым. Он вполне мог бы быть энергичным. Но тут возникает проблема.

Итак, main возвращает отложенное вычисление в монаде IO. Но будь язык энергичным, мы должны были бы полностью сконструировать в памяти все вычисление. И сделать это сразу после запуска до начала реального выполнения программы. Это было бы неэффективно как с точки зрения скорости исполнения, так и с позиции потребления памяти.

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

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

7. Монады как связующее звено.

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

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

                f :: m x -> m y -> ?

Чтобы сохранить оба вычисления мы должны вернуть новое. Тогда можем вернуть либо m x, либо m y. Выберем второе. Так мы получили функцию “then”:

                (>>): m x -> m y -> m y

В общем случае второе вычисление может зависеть от результата первого вычисления. Приходим к функции “bind”:

                (>>=): m x -> (x -> m y) -> my

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

Иногда нам нужно вычисление, которое только и делает, что просто вычисляет заданное фиксированное значение x. Для этого вводится функция “return”:

                return: x -> m x

Так мы пришли к более полному определению типо-класса монад.

8. Ленивость монад.

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

Например, монада IO опирается на этот порядок и производит операции ввода-вывода строго последовательно. Но так поступают не все монады. Например, монада Maybe может просто проигнорировать оставшуюся часть вычислений, а монада Backwards State, вообще, распространяет состояние в порядке обратном следованию! Такое возможно только в ленивом языке.

Итог.

Получается, что чистота, ленивость и монады взаимосвязаны. Последние два являются следствием чистоты. Но это не значит, что ленивость и монады характерны только для Хаскеля. Частично они присутствует и в других языках. Например, монады есть в F#. Это – совершенно другой язык смешанного типа с энергичной стратегией вычислений. Но наиболее красиво и целостно это все выглядит именно в Хаскеле.