tag:blogger.com,1999:blog-86410423126831985342024-03-13T01:35:56.877+03:00Давид Сорокинdsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.comBlogger54125tag:blogger.com,1999:blog-8641042312683198534.post-11753213970617540502018-01-13T08:11:00.000+03:002018-01-13T08:11:02.653+03:00Обращение в будущее<div dir="ltr" style="text-align: left;" trbidi="on">
Убедительная просьба к тем, кто будет создавать следующий язык программирования, скажем, Java Pro или Scala ++. Пожалуйста, добавьте синтаксический сахар для монад, например, похожий на вычислительные выражения F#. Порою очень не хватает</div>
dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com0tag:blogger.com,1999:blog-8641042312683198534.post-32351870668245008182017-11-11T13:52:00.000+03:002017-11-11T13:52:54.369+03:00Книга про моделирование и Haskell<div dir="ltr" style="text-align: left;" trbidi="on">
Здесь тоже поделюсь. Написал книгу про имитационное моделирование с той точки зрения, как я это реализовал на языке Haskell в своем комплексе программных библиотек Айвика. Книгу назвал <i>«Aivika: Computation-based Modeling and Simulation in Haskell»</i>.<br /><br />Скачать можно по любой из двух следующих ссылок, которые обе ведут на один источник, но вторая ссылка точно должна работать:<br /><br /><a href="http://aivikasoft.com/downloads/aivika/aivika.pdf">http://aivikasoft.com/downloads/aivika/aivika.pdf</a><br /><br /><a href="https://github.com/dsorokin/dsorokin.github.io/blob/master/downloads/aivika/aivika.pdf">https://github.com/dsorokin/dsorokin.github.io/blob/master/downloads/aivika/aivika.pdf</a><br /><br />Книга охватывает последовательное моделирование, параллельное и распределенное моделирование, а также вложенное моделирование. Фокус на дискретно-событийном моделировании, прежде всего, процесс-ориентированной парадигме, которая сводится на уровне реализации к событийно-ориентированной.<br /><br />Начну представлять книгу с конца.<br /><br />В самом конце книги описан мой эксперимент по вложенному моделированию, который можно применить, например, к финансовому моделированию. Так, в узлах решетки я запускаю вложенные имитации для эмуляции некоторого случайного процесса, который потом можно оценить. Мне кажется, что это может быть очень интересным расширением известной биномиальной модели, которая широко применяется для оценки опционов и контрактов. Я же позволяю случайные процессы описывать еще в терминах дискретных событий и дискретных процессов, да того же GPSS.<br /><br />Середина книги посвящена моей реализации параллельного и распределенного моделирования на основе оптимистичного метода деформации времени. Описано, как создавать такие модели, как запускать, как мониторить, как работать с вводом-выводом в условиях распределенной имитации с откатами, какие есть нюансы, например, при определении пороговых значений очередей для эффективного задания горизонта моделирования.<br /><br />Главная же часть книги описывает основные концепции дискретно-событийного моделирования применительно к последовательной имитации. Дискретные события, дискретные процессы, ресурсы, вытеснение ресурса, очереди и т.д. Но очень важно заметить, что практически все это работает и в случае распределенного моделирования, и вложенного моделирования, включая GPSS-подобный предметно-ориентированный язык, который тоже бегло описан.<br /><br />Книга снабжена графиками и гистограммами, которые создала сама Айвика во время имитационных экспериментов. Вы их также можете запрограммировать. Готовые отчеты с результатами моделирования Айвика умеет создавать автоматически. Поддерживается метод Монте-Карло. Можно проводить анализ чувствительности относительно случайных внешних параметров. Легко запустить имитацию с тысячами параллельных прогонов.<br /><br />При всем этом мы можем с помощью довольно высокоуровневых вычислений просто определять довольно сложные имитационные модели, где в иных условиях пришлось бы прибегнуть к помощи дорогущих и сложных систем визуального моделирования.<br /><br />В общем, приглашаю к прочтению. Книга о том, как можно использовать мой комплекс библиотек Айвика для решения самых разных задач имитационного моделирования. Есть только один нюанс. Для охвата более широкой аудитории я решил написать книгу на английском языке.<br /><br />И добавлю еще, что на мой взгляд скорость моделирования получилась очень хорошей. Постоянно делаю замеры.</div>
dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com0tag:blogger.com,1999:blog-8641042312683198534.post-9285815382443117002017-08-16T07:31:00.000+03:002017-08-16T07:31:12.349+03:00Трансляция модели из Python в Haskell<div dir="ltr" style="text-align: left;" trbidi="on">
Вспомнив известные слова про гору и Магомета, решил сделать свои наработки более доступными. Создал для языка программирования Python пакет <a href="https://pypi.python.org/pypi/aivika-modeler">aivika-modeler</a>, который позволяет создавать дискретно-событийные модели. а затем запускать основанные на них имитационные эксперименты по методу Монте-Карло с тысячами запусков в серии и более.<br />
<br />
Пакет больше предназначен быть неким клеем, с помощью которого на языке Python можно соединять и объединять готовые компоненты в единую модель, причем сами компоненты предполагается создавать уже на языке Haskell. Однако, во многих случаях должно хватить существующего набора компонент, и поэтому часто можно ограничиться одним языком Python. В планах добавить поддержку GPSS-подобного DSL.<br />
<br />
Есть довольно большая категория людей из целевой аудитории, которые не знают, не хотят и не любят программирование, но Python вполне могут знать на некотором простом уровне. Однако, они могут быть очень хорошими специалистами в своей предметной области. Мой пакет может показаться удобным для них.<br />
<br />
Итак, модель описывается на языке Python. По ней автоматически создается соответствующий код на языке Haskell. Более того, создается готовый проект на основе системы сборки <a href="http://docs.haskellstack.org/">Stack</a>. Собственно, это главное техническое требование - на системе пользователя должен быть установлен Stack. Здесь предвижу некоторые возможные трудности с пакетом <i>old-time</i> на некоторых системах Windows, но надеюсь, что со временем они благополучно разрешатся.<br />
<br />
Так вот, автоматически созданный проект на Stack собирается, а потом запускается на исполнение. В случае успеха в самом конце открывается веб-браузер с результатами имитационного эксперимента. Там могут быть графики, гистограммы, ссылки на таблицы в формате CSV, сводная статистика и прочая информация. Вид и формат желаемых итоговых результатов задается также на языке Python.<br />
<br />
Мне был довольно интересен такой эксперимент по использованию Haskell из Python. Может быть, кто-нибудь возьмет идею на вооружение</div>
dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com1tag:blogger.com,1999:blog-8641042312683198534.post-31967250892101463582017-03-20T20:56:00.000+03:002017-03-20T20:56:00.873+03:00GPSS на Haskell<div dir="ltr" style="text-align: left;" trbidi="on">
Если кто еще не знает, GPSS - это один из самых известных специализированных языков дискретно-событийного моделирования. Так вот, я добавил в AivikaSim [<a href="http://www.aivikasoft.com/ru/products/aivikasim.html">http://www.aivikasoft.com/ru/products/aivikasim.html</a>] поддержку GPSS-подобного предметного-ориентированного языка. Это пакет aivikasim-gpss [<a href="https://github.com/dsorokin/aivikasim-gpss">https://github.com/dsorokin/aivikasim-gpss</a>]. Вот здесь находится работающий тестовый пример [<a href="https://github.com/dsorokin/aivikasim-gpss-test">https://github.com/dsorokin/aivikasim-gpss-test</a>].<br />
<br />
Постарался охватить основные моделирующие блоки, такие как SEIZE, PREEMPT, GATHER, ASSEMBLE, MATCH. Другие либо имеют явные аналоги у меня, либо требуют небольшого программирования как в случае блоков LINK и UNLINK. Не гарантируется точного совпадения результатов с GPSS World, так как логика работы с транзактами у меня совершенно иная, но в некоторых случаях результаты получаются очень близкими.<br />
<br />
Вот, здесь примеры моделей [<a href="https://github.com/dsorokin/aivikasim-gpss/tree/master/examples">https://github.com/dsorokin/aivikasim-gpss/tree/master/examples</a>] из красной книги Шрайбера по GPSS. Там в начале каждого примера приводится соответствующий код модели на языке GPSS World. Можно сличить результаты.<br />
<br />
<i>Example2A.hs</i> означает, что это пример 2A из книги, а вот <i>Example7-26.hs</i> означает, что это соответствует модели на рисунке 7.26. Модели с окончанием Trans, такие как <i>Example2BTrans.hs</i>, означают, что там используется обобщенная версия AivikaSim. Фактически это означает, что приведенный код готов для использования в распределенной имитации.<br />
<br />
Более того, пример <i>Example7-26Distributed.hs</i> непосредственно запускается через модуль распределенного моделирования. В данном случае это формально последовательная модель, но запускается она фактически в виде распределенной, т.е. она готова для кластера компьютеров. Используется оптимистичный алгоритм деформации времени.<br />
<br />
Сразу напишу, что хотя для приведенных моделей удалось добиться очень хорошего соответствия с GPSS, то вот для примера 5D из книги Шрайбера такого близкого соответствия, скорее всего, не получится. Сейчас совпадение идет в 9 случаях против одного, где модель будет уже другой. Причем, совпадает даже на очень нетривиальных моделях, где важен порядок обработки транзактов.<br />
<br />
Касательно скорости моделирования. Модуль GPSS-подобного языка последовательной версии AivikaSim моделирует примерно в 5-7 раз медленнее, чем GPSS World, но зато позволяет использовать разные методы в рамках одной модели, например, агенты и события. Для сравнения, распределенный модуль AivikaSim на последовательных задачах медленнее в раз 6-9, чем последовательная версия AivikaSim, но зато распределенную версию можно запустить много раз на разных узлах в рамках одной модели. Например, можно запустить 7 параллельно работающих локальных процессов на одной системе с 8-ядерным процессором.<br />
<br />
Если кто захочет проверить результаты, то вот руководство по установке AivikaSim [<a href="https://github.com/dsorokin/aivikasim-installer">https://github.com/dsorokin/aivikasim-installer</a>].</div>
dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com0tag:blogger.com,1999:blog-8641042312683198534.post-11575129261398503022017-02-18T15:29:00.000+03:002017-02-18T15:29:32.055+03:00Демо-тест распределенной имитации на монадах<div dir="ltr" style="text-align: left;" trbidi="on">
Создал тестовый демонстрационный пример распределенной дискретно-событийной имитации на основе своего нового продукта AivikaSim. Тест легко воспроизвести по приведенной инструкции:<br />
<br />
<a href="https://github.com/dsorokin/aivikasim-distributed-test">https://github.com/dsorokin/aivikasim-distributed-test</a><br />
<br />
Код написан на языке Haskell, но для воспроизведения теста язык программирования знать не требуется.<br />
<br />
Для реализации мне очень помогла платформа Cloud Haskell, разработчикам которого хочу выразить отдельную благодарность.<br />
<br />
При воспроизведении теста можно обойтись одним локалхостом, а можно объединить до четырех машин в кластер. На самом деле, кластер мог бы состоять и из сотни машин, но для данной модели нужно всего четыре вычислительных узла.<br />
<br />
Особая фишка в том, что узлы можно размещать, используя ненадежные соединения и обычные компьютеры. То есть, теоретически кластер может состоять из машин, расположенных в разных континентах, но вопрос тогда только в том, насколько быстро будет идти имитация, потому что для целей тестирования там сознательно создается очень много сообщений. Происходят постоянные откаты назад и попытки заново обработать дискретные события, потому как реализован оптимистичный алгоритм «деформации времени» (Time Warp).<br />
<br />
Если возникнет кратковременная потеря связи на минуту или две, а я в своих тестах просто на время выдергивал Ethernet-кабель, то распределенная имитация должна сама себя излечить после восстановления связи. В принципе, время потери связи может быть и значительно дольше, но тогда надо подкрутить внешние параметры запуска.<br />
<br />
Только стоит заметить, что восстановление имитации на Linux и macOS работает как часы, а вот на Windows немного похрамывает, но, видимо, это связано с тем, что у Haskell-сообщества Unix-системы приоритетнее, что скорее хорошо.<br />
<br />
По приведенной ссылке лишь скромный небольшой демонстрационный пример, показывающий возможности системы AivikaSim. </div>
dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com0tag:blogger.com,1999:blog-8641042312683198534.post-3388072000253042292016-11-29T20:25:00.000+03:002016-11-29T20:25:42.941+03:00Сетевое моделирование с Айвикой<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="p1">
Давно присматриваюсь к сетевому моделированию (англ. <i>network simulation</i>). Нахожу, что многое можно моделировать с помощью моей <a href="http://hackage.haskell.org/package/aivika">Айвики</a> уже сейчас, в том числе, моделировать распределенно на кластере или параллельно на суперкомпьютере.</div>
<div class="p2">
<br /></div>
<div class="p1">
Основная идея такая. Обычно говорят о портах - источниках данных. В Айвике источники могут быть как активными, так и пассивными. Активный источник сам проталкивает данные дальше для обработки. Это у меня тип <span style="font-family: "courier new" , "courier" , monospace;">Signal a</span> (или <span style="font-family: "courier new" , "courier" , monospace;">Signal m a</span> в обобщенной версии). Тогда каналом будет просто преобразование одного сигнала в другой. Модуль будет функцией, отображающей входные сигналы на выходные.</div>
<div class="p2">
<br /></div>
<div class="p1">
Сигналы - это фактически приложение идеи шаблона <span style="font-family: "courier new" , "courier" , monospace;">IObservable</span> из .NET к имитационному моделированию. Сигналы можно комбинировать, соединять друг с другом. Еще их можно задерживать по времени через очередь событий.</div>
<div class="p2">
<br /></div>
<div class="p1">
Похоже, что сигналы могут подойти для моделирования многих компьютерных сетей, но это пока предположение.</div>
<div class="p2">
<br /></div>
<div class="p1">
Пассивные источники данных у меня в Айвике представлены потоками <span style="font-family: "courier new" , "courier" , monospace;">Stream a</span> (или <span style="font-family: "courier new" , "courier" , monospace;">Stream m a</span> в обобщенной версии). Их нужно запрашивать, чтобы вытянуть из них данные. Их можно распараллеливать для обработки, а потом снова сливать в один поток.</div>
<div class="p2">
<br /></div>
<div class="p1">
Потоки являются обобщением собственно самой идеи потока из функционального программирования, но примененное к имитационному моделированию. Так, потоки можно задерживать по времени.</div>
<div class="p2">
<br /></div>
<div class="p1">
Такие потоки подходят для моделирования сетей массового обслуживания. Поэтому я часто называю их просто потоками транзактов, потому что это они самые и есть.</div>
<div class="p2">
<br /></div>
<div class="p1">
Любопытно, что активные сигналы и пассивные потоки могут быть преобразованы к друг другу тривиальным образом, используя очереди, если необходимо.</div>
<div class="p2">
<br /></div>
<style type="text/css">
p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica}
p.p2 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica; min-height: 14.0px}
</style>
<br />
<div class="p1">
В общем, у меня есть достаточно общий аппарат, который может быть применен к широкому классу задач на мой взгляд. Более того, используя модуль <a href="http://hackage.haskell.org/package/aivika-distributed">aivika-distributed</a>, такие задачи можно обсчитывать распределенно на кластере или параллельно в случае необходимости. Как раз на днях значительно улучшил этот модуль.</div>
</div>
dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com0tag:blogger.com,1999:blog-8641042312683198534.post-63798026992860615462016-11-29T20:23:00.002+03:002016-11-29T20:23:47.382+03:00Распределенное моделирование c Айвикой<div dir="ltr" style="text-align: left;" trbidi="on">
<div class="p1">
Обновил версию <a href="http://hackage.haskell.org/package/aivika-distributed">aivika-distributed</a>, которую можно использовать для распределенного и параллельного моделирования. Реализована оптимистичная стратегия по методу <i>Time Warp</i>. В этой версии значительно улучшена синхронизация глобального времени. Используется алгоритм Самади. В общем, если соединения между узлами достаточно надежные, то распределенная имитация должна вполне хорошо работать.</div>
<div class="p2">
<br /></div>
<div class="p1">
Чтобы использовать эту версию, достаточно вооружиться <a href="http://www.aivikasoft.com/downloads/aivika/aivika-simulation.pdf">документацией</a> PDF по базовой версии Айвики. Здесь все то же самое, т.е. события, процессы, ресурсы, сигналы, потоки транзактов, все это применимо и к распределенной версии. Только типы будут выглядеть по другому. Там, где был <span style="font-family: "courier new" , "courier" , monospace;">Event a</span>, станет <span style="font-family: "courier new" , "courier" , monospace;">Event DIO a</span> и т.д. Последний <span style="font-family: "courier new" , "courier" , monospace;">Event</span> - это фактически монадный трансформер, но я решил не добавлять к его названию букву T, как это обычно делают, а сохранить все названия из базовой версии. Тому были причины.</div>
<div class="p2">
<br /></div>
<div class="p1">
Итак, вооружившись документацией по базовой версии Айвики, можно создавать имитационные модели. Распределенность добавляется через посылку и прием сообщений вот из этого модуля <a href="http://hackage.haskell.org/package/aivika-distributed-0.3.1/docs/Simulation-Aivika-Distributed-Optimistic-Message.html">Message</a>. </div>
<div class="p2">
<br /></div>
<div class="p2">
Собственно, все! В следующем сообщении напишу, как это можно применить к сетевому моделированию (англ. <i>network simulation</i>)</div>
<style type="text/css">
p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica}
p.p2 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica; min-height: 14.0px}
</style></div>
dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com0tag:blogger.com,1999:blog-8641042312683198534.post-87803821073247923312016-06-07T15:47:00.000+03:002016-06-07T15:47:36.083+03:00Айвика как конструктор общецелевых библиотек имитационного моделирования<div dir="ltr" style="text-align: left;" trbidi="on">
Пока в отпуске написал <a href="http://www.aivikasoft.com/ru/tutorials/constructor/aivika-constructor.html">статью</a> о том, как функциональное программирование может быть применено к задачам вложенного моделирования и задачам параллельного распределенного моделирования на примере моей Айвики. Раскрыты некоторые ключевые детали реализации для более полного понимания того, как работает Айвика.</div>
dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com0tag:blogger.com,1999:blog-8641042312683198534.post-58343259050413513842016-04-29T10:41:00.002+03:002016-04-29T10:41:21.770+03:00Айвика для кластера и суперкомпьютера<div dir="ltr" style="text-align: left;" trbidi="on">
<div style="font-family: Helvetica; font-size: 12px; line-height: normal;">
В прошлую субботу выпустил первую версию [5] своей Айвики, которая позволяет создавать и обсчитывать параллельные распределенные дискретно-событийные модели на кластере и/или суперкомпьютере.</div>
<div style="font-family: Helvetica; font-size: 12px; line-height: normal; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px; line-height: normal;">
В общем, идея такая. </div>
<div style="font-family: Helvetica; font-size: 12px; line-height: normal; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px; line-height: normal;">
У меня есть основная версия [2] обще-целевой библиотеки, о которой я много писал у себя в блоге. Она построена на основе стандартного вычисления IO. Самая быстрая версия. Можно автоматизировать вывод графиков и таблиц. Есть документация [1] в формате PDF. Много примеров.</div>
<div style="font-family: Helvetica; font-size: 12px; line-height: normal; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px; line-height: normal;">
Потом я обобщил эту версию для произвольных вычислений, которые должны удовлетворять небольшому числу ограничений, в числе которых возможность создавать изменяемые ссылки и возможность иметь очередь событий. Так родилась обобщенная версия [3] библиотеки. Это тоже обще-целевая библиотека с возможностью формулировать модели в терминах событий, дискретных процессов, очередей, ресурсов, потоков транзактов, процессоров и т.п., но в рамках задаваемого извне типа вычислений. Практически совпадает с основной версией на уровне реализации, в том числе, в названиях, но типы и сигнатуры функций другие.</div>
<div style="font-family: Helvetica; font-size: 12px; line-height: normal; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px; line-height: normal;">
Дальше идут приложения. Создаю частные случаи вычислений, удовлетворяющие требованиям обобщенной версии Айвики, но добавляющие те или иные желаемые свойства.</div>
<div style="font-family: Helvetica; font-size: 12px; line-height: normal; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px; line-height: normal;">
Так родилась версия [4] для вложенных имитаций. Это когда из «настоящего» мы можем относительно дешево и быстро заглядывать в «будущее» модели столько раз, сколько необходимо, а потом на основе полученной информации принимать решения уже в «настоящем». Конек в относительной дешевизне создания вложенных имитаций и в том, что это по-прежнему обще-целевая библиотека имитационного моделирования.</div>
<div style="font-family: Helvetica; font-size: 12px; line-height: normal; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px; line-height: normal;">
Теперь же воплотил в жизнь еще и версию [5] для параллельного распределенного имитационного моделирования. Тоже обще-целевая библиотека моделирования. Здесь независимые узлы могут обмениваться друг с другом асинхронными сообщениями, привязанными к временным меткам. Если на узле уже «будущее», а приходит сообщение в «прошлое», то происходит прозрачный откат до «прошлого» модели. Все сообщения, которые были посланы узлом и стали устаревшими, отменяются, и, соответственно, рассылаются так называемые «анти-сообщения». Короче, реализована оптимистичная стратегия с прозрачными, возможно, каскадными откатами на основе идей метода «деформации времени» (англ. «time warp»), датируемого началом 80-х.</div>
<div style="font-family: Helvetica; font-size: 12px; line-height: normal; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px; line-height: normal;">
В распределенной версии экспериментальная реализация механизма синхронизации времени. Есть разные параметры, которые можно настраивать. Правда, с документацией немного туговато, да и требуется хорошее знание Haskell, но там очень мало отличий от основной версии, для которой уже есть документация. Если есть желающие, то пробуйте в своих университетах! :)</div>
<div style="font-family: Helvetica; font-size: 12px; line-height: normal; min-height: 14px;">
<span style="font-kerning: none;"></span><br /></div>
<div style="color: #4787ff; font-family: Helvetica; font-size: 12px; line-height: normal;">
<span style="color: black; font-kerning: none;">[1] <a href="http://www.aivikasoft.com/ru/products/aivika.html"><span style="-webkit-font-kerning: none;">http://www.aivikasoft.com/ru/products/aivika.html</span></a></span></div>
<div style="color: #4787ff; font-family: Helvetica; font-size: 12px; line-height: normal;">
<span style="color: black; font-kerning: none;">[2] <a href="http://hackage.haskell.org/package/aivika"><span style="-webkit-font-kerning: none;">http://hackage.haskell.org/package/aivika</span></a></span></div>
<div style="color: #4787ff; font-family: Helvetica; font-size: 12px; line-height: normal;">
<span style="color: black; font-kerning: none;">[3] <a href="http://hackage.haskell.org/package/aivika-transformers"><span style="-webkit-font-kerning: none;">http://hackage.haskell.org/package/aivika-transformers</span></a></span></div>
<div style="color: #4787ff; font-family: Helvetica; font-size: 12px; line-height: normal;">
<span style="color: black; font-kerning: none;">[4] <a href="http://hackage.haskell.org/package/aivika-branches"><span style="-webkit-font-kerning: none;">http://hackage.haskell.org/package/aivika-branches</span></a></span></div>
<br />
<div style="color: #4787ff; font-family: Helvetica; font-size: 12px; line-height: normal;">
<span style="color: black; font-kerning: none;">[5] <span style="-webkit-font-kerning: none;"><a href="http://hackage.haskell.org/package/aivika-distributed">http://hackage.haskell.org/package/aivika-distributed</a></span></span></div>
<div>
<span style="color: black; font-kerning: none;"><br /></span></div>
</div>
dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com0tag:blogger.com,1999:blog-8641042312683198534.post-73185742889593553242016-01-31T08:45:00.000+03:002016-01-31T08:45:20.535+03:00Айвика: ветвящееся дискретно-событийное моделирование на Haskell<div dir="ltr" style="text-align: left;" trbidi="on">
На днях сделал анонс своих новых наработок на Haskell Cafe. Повторю и здесь.<br />
<br />
Выпустил три новых релиза. Это входит в серию библиотек, которую я условно называю Айвикой [1, 2, 3]. Главная новинка - пакет aivika-branches [3], который позволяет делать то, что я для себя назвал «ветвящимся дискретно-событийным моделированием» (англ. «branching discrete event simulation») с возможностью запускать вложенные имитации внутри имитации для предсказания и оценки будущего поведения системы на этапе самой имитации. Сейчас попробую описать подробнее.<br />
<br />
Допустим, что у нас есть достаточно общая библиотека, которая позволяет реализовывать дискретно-событийные модели. Там могут быть потоки случайных заданий (требований, они же, тразакты). Могут быть ограниченные ресурсы, за которые идет конкурентная борьба дискретных процессов. Есть глобальная очередь событий. Есть просто очереди сущностей. Есть активности, привязанные к обработке событий и т.п. В общем, все то, что реализовано в моем пакете aivika [1].<br />
<br />
Мой метод заключается в том, что мы описываем поведение имитационной модели с помощью абстрактных вычислений. Во время своего запуска основное вычисление имеет состояние, которое сводится к состоянию очереди обработчиков будущих событий и к состоянию всех ссылок (они же, переменные), которые используются в модели.<br />
<br />
Теперь главная новинка. Представим, что мы умеем достаточно эффективно клонировать состояние модели, порождая производную ветвь модели в текущий момент времени. То есть, мы клонируем и очередь всех обработчиков будущих событий, которые должны еще отработать в будущем. Мы также клонируем состояние всех изменяемых ссылок для новой ветки модели.<br />
<br />
Тогда мы можем запросить из текущего времени будущее значение заданного под-вычисления, как если бы мы продолжили текущую имитацию, но без фактического изменения самой имитации!<br />
<br />
Именно это умеет делать следующая функция из нового пакета aivika-branches [3]:<br />
<br />
<span style="font-family: Courier New, Courier, monospace;">futureEvent :: Double -> Event BrIO a -> Event BrIO a</span><br />
<br />
Здесь мы создаем новую ветку имитационной модели и запускаем заданное под-вычисление в желаемое время в будущем или настоящем, причем текущая имитационная модель остается нетронутой. В порожденной ветке отрабатывают все ожидающие выполнения обработчики событий вплоть до заданного времени.<br />
<br />
Что касается типов, то здесь появляются монадные трансоформеры из другого пакета aivika-transformers [2], который является обобщение пакета aivika. На самом деле, пакет aivika-transformers я подготовил для реализации распределенного и параллельного дискретно-событийного моделирования, но он получился таким общим и гибким, что я смог его применить и к ветвящемуся дискретно-событийному моделированию.<br />
<br />
Как я уже написал, фишка в том, что функция futureEvent относительно дешевая. Мы можем относительно быстро клонировать состояние целого мира имитационной модели! Это стало возможным во многом благодаря повсеместному использованию приемов функционального программирования (тут в скобках замечу, что очень забавно со стороны смотрятся те, кто наивно полагает по своему неразумению, что монада IO не относится к функциональному программированию. Просто не понимают, что функциональное и императивное программирование - это разные, но совсем не антагонистичные и не исключающие друг друга взгляды на то, как можно писать компьютерные программы. Эти оба взгляда вполне могут сосуществовать). Еще там используются такие вещи, как слабые ссылки для того, чтобы не было утечки пространства (англ. space leak) при разветвлении состояния ссылок, чтобы вовремя подчищалась память.<br />
<br />
Фактически получаем дерево имитаций, которое нужно ограничивать или по уровню вложенности или с помощью метода ветвей и границ. Что-то похожее встречается в финансовом моделировании.<br />
<br />
Вообще, мне кажется, что ветвящееся дискретно-событийное моделирование может быть полезно для описания систем, которые моделируют поведение человека, который способен предвидеть будущее, самообучаться и сообразно менять свое поведение на ходу. Мне кажется, что это очень интересная и перспективная область.<br />
<br />
[1] <a href="http://hackage.haskell.org/package/aivika">http://hackage.haskell.org/package/aivika</a><br />
[2] <a href="http://hackage.haskell.org/package/aivika-transformers">http://hackage.haskell.org/package/aivika-transformers</a><br />
[3] <a href="http://hackage.haskell.org/package/aivika-branches">http://hackage.haskell.org/package/aivika-branches</a><br />
<div>
<br /></div>
</div>
dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com0tag:blogger.com,1999:blog-8641042312683198534.post-88655386126865415542015-11-20T07:41:00.000+03:002015-11-20T07:41:48.276+03:00Релиз системы моделирования VisualAivika 5<div dir="ltr" style="text-align: left;" trbidi="on">
Всем привет! Недавно выпустил версию своей визуальной системы моделирования для системной динамики <a href="http://www.aivikasoft.com/">VisualAivika</a>.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-Mdb-gvNy0RA/Vk6hPfFYDvI/AAAAAAAAAHo/SDINFD7jDtU/s1600/visualaivika.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="191" src="http://4.bp.blogspot.com/-Mdb-gvNy0RA/Vk6hPfFYDvI/AAAAAAAAAHo/SDINFD7jDtU/s320/visualaivika.png" width="320" /></a></div>
<br />
Функциональное программирование здесь при том, что на конечном этапе исходная система диффуров преобразуется в модель в терминах моей библиотеки <a href="http://www.aivikasoft.com/ru/products/aivika-fsharp.html">Айвика</a>, которая написана на языке F#, который, как говорят его создатели, functional first.<br />
<br />
Может быть интересна история создания Айвики. Первоначальная идея возникла при изучении Haskell, но я очень быстро переключился реализовывать идею на F#. Первая версия на F# была ужасна. Ее до сих пор можно найти на простора интернета, но я не хочу давать ссылку на нее - пусть останется для истории.<br />
<br />
Мне всегда было очень интересно реализовать Айвику на Haskell. И попытка переписать с F# на Haskell была неудачной. Нарвался на то, что компилятор Haskell предполагает ссылочную прозрачность, и соответственно оптимизирует код. Это решается с помощью прагм, что некрасиво, но главная нехорошесть была в другом. У меня там возникал вложенный двухэтажный одноименный тип в сигнатурах, что было прямым указанием на какую-то логическую ошибку.<br />
<br />
Прояснение пришло не сразу. Сначала я пытался все выразить в рамках одного вычисления, т.е. монады. Все кардинально упростилось, когда я понял, что мне нужно ввести несколько вычислений. В итоге полностью избавился от нехорошего unsafePerformIO, сигнатуры функций стали понятными с первого взгляда, код целиком стал ссылочно-прозрачным. Просто красота! Так родилась <a href="http://www.aivikasoft.com/ru/products/aivika.html">версия Айвики</a> для Haskell.<br />
<br />
Потом я уже переписал обратно c Haskell на F#. Пришлось пойти не некоторые упрощения и хитрости, но в целом, версия Айвики на F# примерно соответствует своей старшей сестрице, хотя и будет немного слабее. Именно переписанная версия теперь используется у меня в визуальной системе моделирования.<br />
<br />
Возвращаясь к исходной теме. Даже если имитационное моделирование не входит в область ваших интересов, то может быть интересно то, что VisualAivika позволяет создавать так называемые Casual Loop Diagrams (CLD), область применения которых довольно широка. Это Systems Thinking или системное мышление.<br />
<br />
Ниже показан пример такой диаграммы, которую я накидал в своей VisualAivika за минуту-две.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-q4snyrAQpBo/Vk6h-enV0NI/AAAAAAAAAHw/bLvN8nlotsk/s1600/Programming_in_FP.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="198" src="http://2.bp.blogspot.com/-q4snyrAQpBo/Vk6h-enV0NI/AAAAAAAAAHw/bLvN8nlotsk/s320/Programming_in_FP.png" width="320" /></a></div>
<br />
<br />
Здесь знак плюса указывает на положительную связь, знак минуса - на отрицательную. Видим, что приведенный цикл является устойчивым. Нет ни бурного роста, ни активного падения.</div>
dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com2tag:blogger.com,1999:blog-8641042312683198534.post-57854622577700106662015-06-12T09:28:00.000+03:002015-06-12T09:33:56.777+03:00Обновленная Aivika for .NET<div dir="ltr" style="text-align: left;" trbidi="on">
<div style="font-family: Helvetica; font-size: 12px;">
Открыл по лицензии GNU дополнительные компоненты к версии своей библиотеки имитационного моделирования Айвика, написанной на языке F#. Теперь по открытой лицензии доступны не только разработка и запуск модели в Visual Studio или Xamarin Studio, но можно также сохранять результаты, строить графики и т.п. Все это удовольствие автоматизируется несколькими дополнительными строками кода.</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
<a href="https://github.com/dsorokin/aivika-fsharp-ce">https://github.com/dsorokin/aivika-fsharp-ce</a></div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
В дополнение к существующей документации в формате PDF выложил исходники примеров, которые охватывают наиболее известные области имитационного моделирования: системная динамика, дискретно-событийное моделирование (управляемое временем, событиями и процессами), базовое агентное моделирование.</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Здесь замечу, что версия на Haskell по-прежнему остается более функциональной, и она имеет более чистый дизайн. В случае с F# пришлось пойти на некоторые упрощения. Зато доступна Visual Studio с IntelliSense, хотя лично я предпочитаю Aquamacs и runghc / cabal в терминале :)</div>
</div>
dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com0tag:blogger.com,1999:blog-8641042312683198534.post-21014611007633335822015-05-04T19:32:00.001+03:002015-05-04T19:32:55.920+03:00Зарелизил Aivika for .NET<div dir="ltr" style="text-align: left;" trbidi="on">
Выпустил движок имитационного моделирования Aivika for .NET по двойной лицензии: GPLv3 и коммерческая. Коммерческая версия имеет дополнительные плюшки в виде модулей для быстрого и удобного возвращения результатов, обработки и анализа. Но сам движок полностью самодостаточен, и он лежит теперь на гитхабе:<br />
<br />
<a href="https://github.com/dsorokin/aivika-fsharp-ce">https://github.com/dsorokin/aivika-fsharp-ce</a><br />
<br /></div>
dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com0tag:blogger.com,1999:blog-8641042312683198534.post-75404995638527863182015-05-01T14:59:00.000+03:002015-05-01T14:59:16.043+03:00Айвика для .NET Framework и Mono<div dir="ltr" style="text-align: left;" trbidi="on">
<h2 style="text-align: left;">
Айвика для .NET Framework и Mono</h2>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
Портировал свою библиотеку имитационного моделирования Айвику на .NET Framework и Mono. Если кратко, это такая библиотека, которая поддерживает большинство известных парадигм имитационного моделирования. Звучит очень амбициозно, но это действительно так. Можете проверить, взяв открытую версию для Haskell. Код доступен. Есть примеры. Есть документация. Даже Google очень уважает мою библиотеку по поисковой фразе «simulation library», хотя замечу, что его выдача бывает нестабильной и зависит от многих факторов.</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
<a href="https://github.com/dsorokin/aivika/wiki">https://github.com/dsorokin/aivika/wiki</a></div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Теперь есть порт для .NET и Mono. Написано на F#. В отличие от открытой версии для Haskell, этот порт закрыт, но доступна документация в формате PDF по ссылке в конце приведенной выше страницы Wiki. Больше 100 страниц с описанием основного API, примерами, графиками и т.п.</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Что может дать новая версия? </div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Как и в случае Haskell, можно составлять имитационные модели практически любой степени сложности и нетривиальности, используя очень простую концепцию, где основные моделируемые активности представлены как вычисления. По сути, это функциональное программирование в чистом виде: монады, потоки, стрелки и т.п., но этим можно особо не заморачиваться, поскольку F# создает иллюзию простоты, насколько возможно.</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Все настолько топорно устроено, что не может не работать. Чем больше проверяю на разных примерах, тем больше убеждаюсь, что метод работает. Иногда вношу неточности в примеры моделей, но потом обычно исправляюсь. Получаю такие же результаты, как в других источниках литературы, хотя последние иногда грешат :)</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Библиотека охватывает такие вещи, как обыкновенные диффуры, так и вытесняющую многопроцессность для систем массового обслуживания. Например, вытеснение ресурса позволяет с легкостью моделировать поломку станков. А потоки с мультиплексированием позволяют моделировать станки параллельно.</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
По модели можно запустить вычислительный эксперимент и получить итоговую страницу HTML с графиками, гистограммами, таблицами в формате CSV и прочим, что позволяет проводить быстрый анализ модели, если нужно, экспортируя результаты в R для более детального изучения. </div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<br />
<div style="font-family: Helvetica; font-size: 12px;">
Теперь это все доступно на платформах .NET Framework и Mono. Работает на Windows, OS X и Linux. Можно составлять модели в удобном редакторе Visual Studio или Xamarin Studio с подсветкой типов и автодополнением. Возможно создание интерактивных тренажеров. Можно интегрировать с существующими решениями, использующими .NET. </div>
</div>
dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com0tag:blogger.com,1999:blog-8641042312683198534.post-9582217676814246102014-06-29T13:08:00.000+04:002014-06-29T13:08:11.637+04:00Версия 1.3 моей библиотеки имитационного моделирования Айвики на Haskell<div dir="ltr" style="text-align: left;" trbidi="on">
<div style="font-family: Helvetica; font-size: 12px;">
Вчера обновил документацию, а также новую версию моей библиотеки имитационного моделирования Айвики, написанную целиком на языке функционального программирования Haskell.</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Айвика уже много лет умеет:</div>
<div style="font-family: Helvetica; font-size: 12px;">
</div>
<ul style="text-align: left;">
<li>системную динамику (обыкновенные диффуры и разностные уравнения);</li>
<li>дискретно-событийное моделирование (управляемое временем, событиями и процессами);</li>
<li>самые базовые вещи из агентного моделирования.</li>
</ul>
<br />
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Примерно год назад добавил потоки данных и процессоры, которые позволяют на достаточно высоком уровне и декларативно описывать сети массового ожидания с очередями, серверами и прочими сущностями. Код выглядит близко к тому, как если бы мы описывали такую сеть с помощью диаграмм.</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Совсем недавно добавил конечные автоматы, которые позволяют моделировать с некоторым упрощением цифровые схемы. Для интеграции со всем остальным эти автоматы синхронизируются с очередью событий. Схемы могут быть рекурсивными, могут иметь задержки на такт.</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Все работает на единой схеме. Формализм и базовое API описаны в документе PDF на странице Wiki проекта Aivika (пока к сожалению, только на английском):</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
<a href="https://github.com/dsorokin/aivika/wiki">https://github.com/dsorokin/aivika/wiki</a></div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
Сам код библиотеки полностью документирован с помощью комментариев haddock. Это стандартный для Haskell способ документирования API.</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Для реализации я использовал очень много разных вещей из мира функционального программирования - ввел несколько монад и две стрелки. Многое взял из учебников по Haskell и F#. Библиотека по всей своей природе целиком принадлежит миру ФП, хотя и ориентирована на императивные вычисления: стохастику и прочее IO. Просто некоторые слишком узком понимают ФП, ограничивая себя рамками детерминированности, но забывая при этом, что IO вполне поддается ссылочной прозрачности. У меня нигде там нет unsafePerformIO, и это особый предмет гордости :)</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Библиотека ориентирована на практику. Мало составить модель, нужно еще вывести результаты, как-то их обработать и представить в удобном виде при минимуме рутины. Для этого существуют дополнительные пакеты, которые позволяют автоматизировать имитационные эксперименты, где мы можем достаточно декларативно описать, какие данные мы хотим вывести и в каком виде. </div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Можем сохранить таблицы в файлы CSV, нарисовать графики, гистограммы, подсчитать сводную статистику по переменным, показать на специальном графике тренд и вероятные границы отклонения по правилу 3-х сигм. </div>
<div style="font-family: Helvetica; font-size: 12px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
В результате эксперимента создается файл HTML с результатами, который может быть просмотрен в любом современном браузере интернета.</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Модель может иметь внешние параметры, которые могут быть случайными или быть прочитанными из файла в случае необходимости. </div>
<div style="font-family: Helvetica; font-size: 12px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Например, это позволяет проводить анализ чувствительности тех или иных переменных по отношению к внешним параметрам посредством множественных запусков по методу Монте-Карло. Можем планировать эксперимент. </div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Вообще, моя библиотека предоставляет eDSL, который органично вписывается в язык Haskell. При определении модели мы можем использовать практически весь арсенал средств этого языка программирования общего назначения, что открывает просто фантастические возможности для описания очень сложных процессов, конечно, при соответствующем знании языка. Дополняет эти возможности то, что заявленные выше парадигмы имитационного моделирования реализованы на основе единой схемы - они все интегрированы между собой, и фактически сводятся друг к другу.</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Библиотека со всеми пакетами размещена на официальном репозитории Hackage DB, который интегрирован с Haskell Platform. Используемая лицензия очень либеральна - BSD3. Код распространяется полностью в открытых исходниках. </div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
На винде устанавливается так:</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
> cabal update</div>
<div style="font-family: Helvetica; font-size: 12px;">
> cabal install aivika</div>
<div style="font-family: Helvetica; font-size: 12px;">
> cabal install aivika-experiment</div>
<div style="font-family: Helvetica; font-size: 12px;">
> cabal install aivika-experiment-chart</div>
<div style="font-family: Helvetica; font-size: 12px;">
> cabal install aivika-experiment-diagrams</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Первые три пакета помимо самого кода содержат еще и примеры. Особенно интересными могут быть примеры из третьего пакета, где выводятся графики, но для этого как раз нужен четвертый, который уже непосредственно рендерит графики.</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
На маке (OS X) и особенно линуксе лучше установить еще другой рендерер графиков:</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
$ cabal install aivika-experiment-cairo</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Он использует библиотеку Cairo, и графики на мой взгляд получаются красивее.</div>
<div style="font-family: Helvetica; font-size: 12px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Будет интересно получить комментарии и пожелания. Так же интересует, насколько вероятна возможность консалтинга. Готов рассмотреть взаимовыгодные и заманчивые предложения. </div>
</div>
dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com0tag:blogger.com,1999:blog-8641042312683198534.post-49174848241340318922013-08-25T19:24:00.000+04:002013-08-25T19:24:09.714+04:00F# на юниксе<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
<div style="font-family: Helvetica; font-size: 12px;">
Оказывается, можно замечательно использовать F# на маке с помощью Mono и Xamarin Studio. Очень удобно, и мой проект от Visual Studio работает прекрасно. Попробовал редактировать и создавать файлы в Xamarin Studio. Мне понравилось. Даже лень было сегодня загружаться в винду, где у меня установлена Visual Studio. </div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Надо сказать, что ребята из Xamarin достигли заметного прогресса. Что меня больше всего потрясло, так это то, что в некоторых моих тестах Mono заметно обгоняет .NET, делая поправку на то, что гонял я тесты на одной машине, но под разными операционками, да и тесты, вероятно были несколько специфическими. Ни за что бы не поверил в возможность такого еще пару лет назад!</div>
</div>
dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com2tag:blogger.com,1999:blog-8641042312683198534.post-91188508835125643982013-08-10T15:22:00.001+04:002013-08-10T15:22:26.242+04:00А вдруг есть такой чудесный плагин для Scala?<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
<div style="font-family: Helvetica; font-size: 12px;">
Пока самые лучшие и знаменитые наши умы заняты очень серьезным мероприятием, хочу поделиться со всеми остальными о наболевшем.</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Есть у меня одна уже работающая задумка, но мне нужен для Scala хороший и удобный синтаксический сахар для монад (эх, еще бы для стрелок…). Мечтаю о чем-то подобном computation expressions из F# - это такой аналог нотации do для языка, в котором нет классов типов. Как понимаю, нужен плагин к компилятору в случае Scala.</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Ни встроенный for-comprehension, ни плагин продолжений не впечатляют нисколько. Отчасти они дублируют друг друга, но ни одно из них не решает свою задачу хорошо в моем понимании, давно извращенным другими языками. В общем, тот случай, где количество не переходит в качество, и даже не помышляет о том.</div>
<div style="font-family: Helvetica; font-size: 12px; min-height: 14px;">
<br /></div>
<div style="font-family: Helvetica; font-size: 12px;">
Очень хотел использовать Scala, но сейчас пребываю в полной печали. Для моей задачи технически идеально подходит Haskell, но я хочу продвинуть библиотеку в широкие массы, а потому Haskell пока хорош только как полигон для выработки, обкатки и кристаллизации моих безумных идей, и здесь он свою миссию уже выполнил на все 350% с блеском и шиком. Но сейчас хочется получить уже широкую аудиторию из исключительно меркантильных соображений, а потому интересует Scala. </div>
</div>
dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com12tag:blogger.com,1999:blog-8641042312683198534.post-40353189272880177572013-03-22T10:42:00.000+04:002013-03-22T10:42:16.203+04:00Комментарий о хвостовой рекурсии<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
Как известно, дьявол скрывается в деталях. Порою, небольшая деталь может сильно изменить смысл. Получается эффект бабочки. Что-то такое иногда происходит с пониманием хвостовой рекурсии. Мне всегда эта тема казалось сложной.<br />
<br />
В прошлом году вышел замечательный перевод книги Пола Грэма "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". Дальше идет довольно общее описание того, как это может быть сделано.<br />
<br />
Проблема в том, что без знания контекста тот текст можно неправильно истолковать. Все встает на свои места, если обратиться к книге PAIP Питера Норвига, которую Пол Грэм безусловно читал. В той книге приведена некая абстрактная машина. Там действительно хвостовая рекурсия компилируется в циклы, но в циклы не языка высокого уровня, а в циклы ассемблера той абстрактной машины (фактически через goto). Вот, в чем загвоздка.<br />
<br />
Многие почему-то считают, что хвостовую рекурсию можно всегда преобразовать в циклы Scala, F# или Common Lisp. Мне кажется это неправильным. Можно придумать контр-пример. Достаточно обернуть рекурсивный вызов в лямбду и дальше передать эту лямбду другой функции. Например, компилятор Scala не сможет это превратить в цикл на уровне явовского байт-кода, а на уровне абстрактной машины из PAIP цикл получился бы сам собою.<br />
</div>
dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com10tag:blogger.com,1999:blog-8641042312683198534.post-28262786428282088932013-03-19T09:42:00.001+04:002013-03-19T09:42:41.254+04:00Функциональная чистота и ссылочная прозрачность<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
Есть мнение, что термин "ссылочная прозрачность" является ненадежным, поскольку люди до сих пор не могут договориться об его точном определении, точно также как не могут договориться о том, какие языки программирования считать функциональными, а какие - нет. Тем не менее, термин широко встречается в литературе.<br />
<br />
Что касается "функциональной чистоты", то с нею более-менее понятно: результат зависит только от входных параметров, и функция не производит внешних побочных эффектов в том смысле, что не изменяет состояние окружающего мира. Для статически типизированных языков это обычно означает, что все, что функция делает и производит, описано в ее сигнатуре. Тут я изучал самые разные источники, включая учебники по Common Lisp, Haskell, F# и Scala. Трактовка везде примерно такая, почему-то за исключением одного русскоязычного учебника (не буду называть).<br />
<br />
Для определенности возьмем такую вариацию этих терминов из еще невышедшей книги "Functional Programming in Scala":<br />
<br />
"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."<br />
<br />
Здесь содержатся одно из возможных определений для ссылочной прозрачности и вывод о том, что если выражение f(x) ccылочно-прозрачно для всех ссылочно-прозрачных x, то функция f является чистой. Определение чистоты в книге дается обычное в другом месте. Меня смущает то, что хотя используется слово "if" в последнем предложении, трактуется оно почему-то как "if and only if".<br />
<br />
Вопрос номер один. Правильно ли я понимаю, что в такой постановке ссылочная прозрачность является достаточным условием для функциональной чистоты, и оба эти понятия, вообще говоря, не эквивалентны в математическом смысле, т.е. ссылочная прозрачность уже не является необходимым условием чистоты?<br />
<br />
Второе. У меня складывается ощущение, что ссылочная прозрачность жестко привязана к конкретному языку программирования, тогда как свойство функции быть чистой является в большой степени над-языковым. Припоминая ассемблер PDP-11, сдается мне, что даже на уровне ассемблера можно оперировать чистотой, если ввести определенные допущения для стека (или стеков). Это так? Если да, то тогда оба понятия действительно не могут быть эквивалентными уже по этому.<br />
<br />
В общем, прошу вразумить и поставить на путь истинный.<br />
</div>
dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com1tag:blogger.com,1999:blog-8641042312683198534.post-60042058959723478462012-12-10T13:10:00.000+04:002012-12-10T19:12:45.928+04:00Ряд Фибоначчи<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
Давеча рекламировал свои обобщенные последовательности (Generic Sequences), а какие могут быть последовательности без ряда Фибоначчи? Это что-то вроде обязательного ритуала. Опустим здесь тот факт, что я создал эту библиотеку для вполне практической задачи, когда мне понадобилось быстро и эффективно сравнивать деревья, а там ленивые последовательности дюже полезны.<br />
<br />
Итак, ниже приведена рабоче-крестьянская версия, которая выдает ленивую бесконечную последовательности ряда Фибоначчи через то, что я назвал Sequence Comprehension:<br />
<br />
<pre>(defparameter *fibs-1*
(with-seq/cc
(do ((a 1 b)
(b 1 (+ a b)))
(nil)
(yield/cc a))))
</pre>
<br />
Очень просто, не правда ли?<br />
<br />
Теперь каноническая версия через поток:<br />
<br />
<pre>(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))
</pre>
<br />
Проверка:<br />
<br />
<pre>? (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)</pre>
</div>
<br />
<b>Дополнение.</b><br />
<br />
Чтобы не сложилось неправильного впечатления, сейчас покажу наиболее эффективную реализацию, которая только возможна в рамках моей библиотеки.<br />
<br />
<pre>(defparameter *fibs-3*
(make-seq
(labels ((traverse (a b)
(enum-cons a (traverse b (+ a b)))))
(traverse 1 1))))
</pre>
<br />
Основная идея заключается в том, что мы работаем как с обычным списком, что очень удобно при обходе индуктивных/рекурсивных структур данных. Собственно, все комбинаторы написаны у меня в таком стиле.<br />
<br />
И если вам по какой-то причине не нравятся комбинаторы, то результат можно получить с помощью известного макроса iter, для которого я добавил конструкцию in-seq:<br />
<br />
<pre>? (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)
</pre>
</div>
dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com0tag:blogger.com,1999:blog-8641042312683198534.post-87077998506464562372012-12-09T13:18:00.000+04:002012-12-09T13:18:02.552+04:00Обобщенные последовательности<div dir="ltr" style="text-align: left;" trbidi="on">
<style type="text/css">
<!--
@page { margin: 2cm }
P { margin-bottom: 0.21cm }
-->
</style>
<br />
<div style="margin-bottom: 0cm;">
Рекламирую свою новую
библиотеку Generic Sequences [1] для Common Lisp. Она
вводит обобщенные последовательности
похожие на обычные списки Common Lisp, ленивые
последовательности clojure, списки Haskell, а
также похожие на итераторы, которые
можно встретить в таких языках
программирования как C#, F#, Java и Scala. С
помощью комбинаторов легко создавать
обобщенные последовательности, и их
легко итерировать с помощью макроса
ITER.</div>
<div style="margin-bottom: 0cm;">
<br />
</div>
<div style="margin-bottom: 0cm;">
Более того, есть так
называемое Sequence Comprehension, основанное на
продолжениях из пакета CL-CONT. Это что-то
похожее на синтаксис Sequence Expression из F# и
конструкцию Yield из C#, где мы можем
определить ленивую последовательность
очень простым и декларативным способом.</div>
<div style="margin-bottom: 0cm;">
<br />
</div>
<div style="margin-bottom: 0cm;">
В то же самое время,
обобщенные последовательности могут
быть очень легко преобразованы в ленивые
потоки, которые широко распространены
в мире функционального программирования.
Помимо этого, такие потоки также
трактуются как обобщенные последовательности.
В дополнение к этому, стандартные списки
и векторы Common Lisp тоже трактуются как
обобщенные последовательности. Еще можно создавать свои последовательности, реализуя протокол из всего двух обобщенных функций.</div>
<div style="margin-bottom: 0cm;">
<br />
</div>
<div style="margin-bottom: 0cm;">
Есть небольшая
документация [2] в формате PDF.</div>
<div style="margin-bottom: 0cm;">
<br />
</div>
<div style="margin-bottom: 0cm;">
[1]
<a href="https://github.com/dsorokin/generic-sequences">https://github.com/dsorokin/generic-sequences</a></div>
<div style="margin-bottom: 0cm;">
<br /></div>
<div style="margin-bottom: 0cm;">
[2]
<a href="https://github.com/dsorokin/generic-sequences/blob/master/doc/generic-sequences-manual.pdf">https://github.com/dsorokin/generic-sequences/blob/master/doc/generic-sequences-manual.pdf</a></div>
</div>
dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com1tag:blogger.com,1999:blog-8641042312683198534.post-34789139041473430082012-07-07T12:06:00.000+04:002012-07-07T12:06:54.432+04:00Порт библиотеки Айвика на язык Scala<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
После полугода раздумий решил выложить новый порт своей библиотеки имитационного моделирования Айвика. Теперь языком реализации является Scala. Это значит, что можно использовать Java в имитационных моделях. Лицензия - BSD3.<br />
<br />
<a href="https://github.com/dsorokin/scala-aivika">https://github.com/dsorokin/scala-aivika</a><br />
<br />
Основное отличие от двух других реализаций на F# и Haskell состоит в том, что сейчас можно получать результаты моделирования и частично их анализ в виде HTML, графиков и таблиц. Для этого задается так называемый эксперимент. Он описывает либо единичную симуляцию, либо серию по методу Монте-Карло, которая может зависеть от внешних параметров. Также описывается, что мы желаем получить. Всего в нескольких строках можно запросить график отклонения по правилу “три сигма”. Также легко можно запросить таблицы в формате CSV с результатами моделирования, гистограммы, графики траекторий случайных процессов, сводную статистику и т.п. Затем информацию можно посмотреть с помощью вашего любимого браузера.<br />
<br />
Здесь так же как в F# легко задавать обыкновенные дифференциальные уравнения, что позволяет красиво и просто строить модели системной динамики. Процессы же дискретно-событийных моделей задаются с помощью продолжений. Через объекты задаются агенты и их состояния. Все это вместе работает на основе единой достаточно простой схемы.<br />
<br />
К тому же, имитации можно распараллелить, если они для этого готовы, например, если используют специальные ссылки вместо переменных и параметры для каждой отдельной имитации, т.е. когда побочные эффекты контролируемы.<br />
</div>dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com0tag:blogger.com,1999:blog-8641042312683198534.post-41388843716075303322012-05-22T11:01:00.000+04:002012-05-22T11:01:15.391+04:00О хвостовой рекурсии<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
Тут вышла статья на хабре [1], где написано:<br />
<br />
<i>"Хвостовая рекурсия это частный случай рекурсии, когда рекурсивный вызов может быть заменен итерацией."</i><br />
<br />
Я почему-то всегда считал, что хвостовая рекурсия сложнее. Применительно к F# можно взять такой контр-пример.<br />
<br />
Возьмем реализацию оператора while для F# Async. В исходниках F# это будет функция whileA. Если считать, что bindA - это монадическая связка для Async, то видим, что:<br />
<br />
1) функция whileA вызывает bindA и передает последней вызов на саму себя, т.е. whileA определяется рекурсивно;<br />
<br />
2) функции whileA и bindA используют хвостовые вызовы.<br />
<br />
Отсюда можно заключить, что имеем случай хвостовой рекурсии (я прав в терминах?). При этом очевидно, что ни о какой замене whileA итерацией не может быть и речи, как минимум, в терминах .NET. Нужна соответствующая поддержка со стороны виртуальной машины.<br />
<br />
В данном случае все хвостовые вызовы внутри whileA и bindA будут помечены в IL специальным тегом, который опознается виртуальной машиной .NET. Это ощутимо замедляет выполнение кода, но стек вызовов не увеличивается, что и требуется.<br />
<br />
Так вот, имеем случай хвостовой рекурсии, несводимой к простой итерации в рамках .NET. Может быть, виртуальная машина и использует итерации, но это уже совсем другой внешний уровень.<br />
<br />
[1] <a href="http://habrahabr.ru/post/143690/">http://habrahabr.ru/post/143690/</a><br />
</div>dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com3tag:blogger.com,1999:blog-8641042312683198534.post-77869176389657315992012-01-26T11:51:00.000+04:002012-01-26T11:51:49.059+04:00А не пора ли разбить Scala Library на части?<div dir="ltr" style="text-align: left;" trbidi="on"><br />
Библиотека Scala времени исполнения (она же, Scala Library) выросла к версии 2.9.1 аж до восьми с половиной мегабайт с лишним от почти четырех в версии 2.7.7. Для распространения десктопных приложений на Scala это очень плохо. Конечно, есть ProGuard, который убирает все лишнее, но в него нет веры.<br />
<br />
Так, только что пропустил свой код через ProGuard и стал тестировать. Ужалось все до мегабайта, но на выходе из приложения получил неприятное NoSuchMethodException. Там создавался анонимный класс, и почему-то один его метод был безжалостно вырезан ProGuard'ом.<br />
<br />
Интересно, а собираются ли разбивать Scala Library на части по примеру того, как сделано в .NET? По-моему пора.<br />
</div>dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com1tag:blogger.com,1999:blog-8641042312683198534.post-46798034109881835392012-01-16T19:47:00.000+04:002012-01-16T19:47:19.212+04:00Глубоко-вложенные вычисления<div dir="ltr" style="text-align: left;" trbidi="on"><br />
Тема возникла из моих ответов на вопросы, заданные другим человеком на форумах. Речь пойдет о рекурсивных вычислениях, когда глубина вложенности выше предельно допустимой для стека вызовов. Я покажу, как такая задача может быть решена на Common Lisp. Сразу отмечу, что это возможно не всегда, но в большинстве случаев работает.<br />
<br />
В основе лежит та же самая идея, что используется в F# Async. Мы просто переводим наши рекурсивные функции на язык продолжений. Пугаться здесь не стоит, сами мы этого делать не станем. За нас все самое сложное и рутинное сделают WITH-CALL/CC и его специальная версия для функций DEFUN/CC из пакета CL-CONT. Ниже везде предполагается, что пакет CL-CONT импортирован.<br />
<br />
Но прежде определимся с исходной задачей. Ниже приведены функции, которые вылетают со Stack Overflow.<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;">(defun compute (x)</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (cond ((zerop x) 0)</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (t (+ (compute (1- x))</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> 1))))</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"><br />
</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;">(defun run ()</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (compute 10000000)) ;; Stack Overflow</span><br />
<br />
Функции намерено взяты такими. Сами по себе эти функции ничего не представляют. Нам интересно то, что функция COMPUTE рекурсивная, с большой глубиной, вызов - не хвостовой. В общем случае, рекурсивных вызовов может быть несколько.<br />
<br />
Перепишем функции через продолжения. Функцию COMPUTE определим через DEFUN/CC. Т.е. она будет возвращать не обычное значение, а вычисление, которое еще нужно запустить. В F# это примерно означало бы то, что функция COMPUTE возвращала бы некоторое значение типа Async<'a>.<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;">(defun/cc compute/cc (x)</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (cond ((zerop x) 0)</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (t (+ (compute/cc (1- x))</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> 1))))</span><br />
<br />
Таким образом мы должны преобразовать всякую функцию, вложенность которой может быть огромной. Вызывать их можно из DEFUN/CC и WITH-CALL/CC:<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;">(defun run/cc ()</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (with-call/cc (compute/cc 10000000)))</span><br />
<br />
Если у вас SBCL, то на этом можно остановиться. У этой лисп-машины превосходный оптимизатор хвостового вызова. У нас фактически все операции COMPUTE превращаются в цепочку хвостовых вызовов. Поэтому все работает. Стек как бы уходит в память.<br />
<br />
Увы, не все лисп-машины хорошо оптимизируют хвостовые вызовы. Для CLozure CL и LispWorks Personal мы по-прежнему получим Stack Overflow. К счастью есть выход - использовать трамплин.<br />
<br />
Внутри вычисления DEFUN/CC нам доступно продолжение. Если глубина стека вызовов стала большой, то мы можем запомнить продолжение и раскрутить в обратную сторону стек, возвращая управление некоторому внешнему циклу. Внутри этого цикла мы будем проверять, а нет ли у нас очередного продолжения для, так сказать, продления вычисления. Если есть, то запускаем это продолжение. Фокус состоит в том, что при запуске продолжения стек вызовов уже очищен, что нам и требуется.<br />
<br />
Сначала определим утилиты трамплина:<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;">(defparameter *cont* nil)</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"><br />
</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;">(defun/cc trampoline-push/cc ()</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (call/cc </span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (lambda (k)</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (push k *cont*))))</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"><br />
</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;">(defmacro trampoline/cc (expr)</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (let ((result (gensym)))</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> `(progn</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (trampoline-push/cc)</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (let ((,result ,expr))</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (trampoline-push/cc)</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> ,result))))</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"><br />
</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;">(defmacro with-trampoline/cc (&body body)</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (let ((result (gensym)))</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> `(let ((,result nil))</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (with-call/cc</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (trampoline-push/cc)</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> ,@body)</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (loop while *cont*</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> do (let ((cont (pop *cont*)))</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (setf ,result (funcall cont))))</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> ,result)))</span><br />
<br />
Утилита TRAMPOLINE-PUSH/CC кладет продолжение вычисления в ячейку *CONT* и возвращает управление внешнему циклу из WITH-TRAMPOLINE/CC, откуда все должно быть запущено. Макрос TRAMPOLINE/СС оборачивает заданное выражение, где трамплин вызывается до и после вычисления выражения.<br />
<br />
Мы можем использовать трамплин часто, но это неэффективно. Пусть он вызывается на каждой сотой итерации:<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;">(defun/cc smart-compute/cc (x)</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (cond ((zerop x) 0)</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> ((zerop (mod x 100)) </span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> ;; on every 100th iteration use the trampoline</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (+ (trampoline/cc (smart-compute/cc (1- x)))</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> 1))</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (t </span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (+ (smart-compute/cc (1- x))</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> 1))))</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"><br />
</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> ;; No Stack Overflow</span> <br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (defun smart-run/cc ()</span><br />
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> (with-trampoline/cc (smart-compute/cc 10000000)))</span><br />
<br />
Это работает даже для CLISP, где нет никакой оптимизации хвостового вызова. Мы успешно имитирует рекурсивный вызов с глубиной вложенности десять миллионов!<br />
</div>dsorokinhttp://www.blogger.com/profile/12343205630861084400noreply@blogger.com6