David Sorokin's WebLog in Russian

А не пора ли разбить Scala Library на части?

2012-01-26T11:51:00.000+04:00

Библиотека Scala времени исполнения (она же, Scala Library) выросла к версии 2.9.1 аж до восьми с половиной мегабайт с лишним от почти четырех в версии 2.7.7. Для распространения десктопных приложений на Scala это очень плохо. Конечно, есть ProGuard, который убирает все лишнее, но в него нет веры.

Так, только что пропустил свой код через ProGuard и стал тестировать. Ужалось все до мегабайта, но на выходе из приложения получил неприятное NoSuchMethodException. Там создавался анонимный класс, и почему-то один его метод был безжалостно вырезан ProGuard'ом.

Интересно, а собираются ли разбивать Scala Library на части по примеру того, как сделано в .NET? По-моему пора.

Глубоко-вложенные вычисления

2012-01-16T19:47:00.000+04:00

Тема возникла из моих ответов на вопросы, заданные другим человеком на форумах. Речь пойдет о рекурсивных вычислениях, когда глубина вложенности выше предельно допустимой для стека вызовов. Я покажу, как такая задача может быть решена на Common Lisp. Сразу отмечу, что это возможно не всегда, но в большинстве случаев работает.

В основе лежит та же самая идея, что используется в F# Async. Мы просто переводим наши рекурсивные функции на язык продолжений. Пугаться здесь не стоит, сами мы этого делать не станем. За нас все самое сложное и рутинное сделают WITH-CALL/CC и его специальная версия для функций DEFUN/CC из пакета CL-CONT. Ниже везде предполагается, что пакет CL-CONT импортирован.

Но прежде определимся с исходной задачей. Ниже приведены функции, которые вылетают со Stack Overflow.

(defun compute (x)
(cond ((zerop x) 0)
(t (+ (compute (1- x))
1))))

(defun run ()
(compute 10000000)) ;; Stack Overflow

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

Перепишем функции через продолжения. Функцию COMPUTE определим через DEFUN/CC. Т.е. она будет возвращать не обычное значение, а вычисление, которое еще нужно запустить. В F# это примерно означало бы то, что функция COMPUTE возвращала бы некоторое значение типа Async<'a>.

(defun/cc compute/cc (x)
(cond ((zerop x) 0)
(t (+ (compute/cc (1- x))
1))))

Таким образом мы должны преобразовать всякую функцию, вложенность которой может быть огромной. Вызывать их можно из DEFUN/CC и WITH-CALL/CC:

(defun run/cc ()
(with-call/cc (compute/cc 10000000)))

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

Увы, не все лисп-машины хорошо оптимизируют хвостовые вызовы. Для CLozure CL и LispWorks Personal мы по-прежнему получим Stack Overflow. К счастью есть выход - использовать трамплин.

Внутри вычисления DEFUN/CC нам доступно продолжение. Если глубина стека вызовов стала большой, то мы можем запомнить продолжение и раскрутить в обратную сторону стек, возвращая управление некоторому внешнему циклу. Внутри этого цикла мы будем проверять, а нет ли у нас очередного продолжения для, так сказать, продления вычисления. Если есть, то запускаем это продолжение. Фокус состоит в том, что при запуске продолжения стек вызовов уже очищен, что нам и требуется.

Сначала определим утилиты трамплина:

(defparameter *cont* nil)

(defun/cc trampoline-push/cc ()
(call/cc
(lambda (k)
(push k *cont*))))

(defmacro trampoline/cc (expr)
(let ((result (gensym)))
`(progn
(trampoline-push/cc)
(let ((,result ,expr))
(trampoline-push/cc)
,result))))

(defmacro with-trampoline/cc (&body body)
(let ((result (gensym)))
`(let ((,result nil))
(with-call/cc
(trampoline-push/cc)
,@body)
(loop while *cont*
do (let ((cont (pop *cont*)))
(setf ,result (funcall cont))))
,result)))

Утилита TRAMPOLINE-PUSH/CC кладет продолжение вычисления в ячейку *CONT* и возвращает управление внешнему циклу из WITH-TRAMPOLINE/CC, откуда все должно быть запущено. Макрос TRAMPOLINE/СС оборачивает заданное выражение, где трамплин вызывается до и после вычисления выражения.

Мы можем использовать трамплин часто, но это неэффективно. Пусть он вызывается на каждой сотой итерации:

(defun/cc smart-compute/cc (x)
(cond ((zerop x) 0)
((zerop (mod x 100))
;; on every 100th iteration use the trampoline
(+ (trampoline/cc (smart-compute/cc (1- x)))
1))
(t
(+ (smart-compute/cc (1- x))
1))))

;; No Stack Overflow
(defun smart-run/cc ()
(with-trampoline/cc (smart-compute/cc 10000000)))

Это работает даже для CLISP, где нет никакой оптимизации хвостового вызова. Мы успешно имитирует рекурсивный вызов с глубиной вложенности десять миллионов!

Первые впечатления о CAPI из LispWorks

2012-01-14T20:56:00.001+04:00

Сегодня впервые использовал CAPI для создания каркаса будущего редактора диаграмм. Остался очень довольным. Местами не похоже на Windows Forms, WPF/Silverlight, Swing, SWT, но разобраться можно. Работает, что отрадно.

Еще очень радует среда LispWorks. Сейчас в проекте 250 килобайт кода на лиспе. Секунда или две после внесения изменений – и я уже вижу обновленное окошко моего редактора. Помню, как я мучился в ожидании, когда почти ту же самую задачу реализовывал на Scala с помощью IntelliJ Idea. Приходилось ждать целую вечность!

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

2011-09-10T17:19:00.000+04:00

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

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

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

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

2011-03-30T12:18:00.000+04:00

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

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

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

Маниловщина

2011-03-04T10:58:00.000+03:00

Иногда очень хочется, чтобы F# был отделен от .NET. Чтобы программы на нем работали под юниксами и виндой без использования тяжелой виртуальной машины. Или, как минимум, все его новшества были портированы в окамл. Уж больно F# хорош!

Однако реализация F# иногда хромает. Например, в нем есть такие костыли как OptimizedClosures.FSharpFunc и FSharpFunc.InvokeFast. На деле это означает, что при вызове функции со многими аргументами задействуется RTTI, чтобы узнать, а есть ли прямой вызов функции, минуя каррирование. Во многом потому, что это снизу .NET. Подозреваю, что в окамле такой вызов функции сильно оптимизирован, и он не использует RTTI.

Simtegra MapSys v4.0

2010-11-01T20:35:00.000+03:00

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

Всего разработано мною более 240 тысяч строк кода на C# вместе с сопутствующими библиотеками. Пока еще можно двигаться вперед, используя Far и jEdit, изредка загружая Visual Studio C# Express для отладки. Подавляющая часть кода была создана при помощи замечательного редактора jEdit. А в последнее время стал все чаще использовать Far в качестве редактора... Для сборки сначала использовал NMAKE, потом перешел на MSBuild. Пока еще используем .NET v2.0 и WinForms.

О логике, математике и программировании

2010-10-06T12:15:00.000+04:00

Навеяно одними однотипными высказываниями на форуме одного индивидуума.

Человек не рождается с умением логически мыслить. Логика – это искусственное изобретение человеческого разума. Она противоестественна тому, как мы на самом деле мыслим. Даже в логических законах Аристотеля спустя почти две с половиной тысячи лет современными математиками была найдена ошибка. А если сам Аристотель ошибался, то что остается нам, простым смертным?

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

А программирование в этом вопросе мало отличается от математики, только масштабы сильно скромнее.

Размышления о движке моделирования

2010-09-18T11:00:00.003+04:00

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

Создал два очень разных движка: MapSim и Aivika.

1. Первый – MapSim (лицензия LGPL). Генерирует очень быструю симуляцию, даже удивительно быструю. Но умеет только системную динамику. Очень узкая область. Движок очень хорошо делает свое дело, хотя даже в таком качестве MapSim может показаться отступнически революционным, ибо целиком написан на C#, а не на популярных в этой области Си или Си++ с Фортраном.

2. Второй – Айвика (лицензия BSD). Фантастически универсальный движок. Умеет самые разные парадигмы имитационного моделирования. Но редкостный тормоз на задачах системной динамики (интегралы чудовищно неэффективны). Дискретное событийное моделирование более-менее (быстрый двоичный хип). Скорость же процесс-ориентированной дискретной симуляции сильно зависит от качества реализации системы памяти (создается много легковесных функций) и хвостовой рекурсии (.NET на порядок быстрее, чем Mono), но в целом медленная симуляция. Агентное моделирование медленнее, чем в AnyLogic, но я думаю, что приемлемо. Еще движок Айвика – это полный переворот сознания для обычного модельера. Трудно для понимания.

В общем, два антипода. Есть идея скрестить их. Это возможно благодаря универсальности Айвики. Тут два момента.

1. Симуляцию, сгенерированную с помощью MapSim, можно представить как вычисление в монаде моделирования Dynamics. Это значит, что такую симуляцию можно использовать в Айвике как равноправную. Есть накладные расходы, связанные с оборачиванием итерационного процесса, порождаемого MapSim, в небольшую прослойку, которая будет выглядеть внешне как динамический процесс Dynamics. Нужно будет где-то хранить значения выходных переменных. Чем меньше переменных на выходе, тем быстрее эта прослойка. Придется повозиться.

2. Внутри симуляции под управлением MapSim можно использовать вычисления в монаде Dynamics. Другими словами, MapSim может использовать модели Айвики. Накладные расходы минимальны. Реализовать очень просто.

Теоретических проблем нет. Все должно работать. Я уже продумал. И если бы я снова стал создавать визуальную среду моделирования Simtegra MapSys, то сейчас уже взял бы за основной общесистемный движок Айвику, а системную динамику оптимизировал бы с помощью MapSim. То есть, я очень серьезно отношусь к Айвике, хотя с первого взгляда она может показаться просто игрушкой функционального программирования :)

CodeDom для F#

2010-09-17T15:34:00.002+04:00

Сегодня взял свою библиотеку MapSim, которая умеет создавать код через CodeDom, и заменил СSharpCodeProvider на FSharpCodeProvider из F# PowerPack. Сработало! MapSim по заданному входу сгенерировал код на F#. Только местами забавный код получился. В одном месте создаются исключения только для того, чтобы их тут же перехватить. Странно как-то. Но в целом качество кода сопоставимо с тем, что у меня создает стандартный провайдер C#.

А не переписать ли MapSim на F#?

2010-09-15T12:48:00.001+04:00

Иногда возникают мысли переписать свою библиотеку моделирования MapSim на F#. Сейчас она написана на C#. Думаю, что будет большая польза от использования абстрактных типов данных (ADTs). Также можно будет добавить разный back-end, т.е. создавать симуляции не только для .NET, но и для Java, JavaScript и C++ с фортраном.

Чертовски быстрая симуляция получается даже сейчас на .NET. Код линеен, почти не создает объектов, не выделяет память, а используемая память умещается в кеш процессора. JIT-компилятор создает код, сравнимый с ассемблером. Симуляцию можно еще ускорить, если использовать локальные переменные – сейчас везде используются поля объекта для надежности (в .NET есть лимит в 64 кб для локальных переменных).

Думаю, что когда-нибудь можно будет подружить MapSim и Айвику. Тогда симуляция в Айвике для системной динамики будет намного быстрее. Эту тему затронул в обзорной статье Aivika Overview.

Aivika версии 2.0.12.0

2010-09-15T12:30:00.001+04:00

Залил новую версию своей библиотеки по моделированию. Сам код не изменился. Перевел проект на .NET v4 и Visual Studio 2010. Добавил статью Aivika Overview, где на восьми страницах дается обзор метода. Кроме прочего, упоминаются и монады, ибо вся соль моего метода в том, что заданная имитационная модель сводится к динамическому процессу, а такой процесс является монадой. Отсюда фантастические возможности по комбинированию процессов. Хотя я уже писал об этом прежде :)

О вычислительных выражениях

2010-09-12T13:57:00.002+04:00

Уже почти год пишу на F#, и мне так понравились вычислительные выражения! Удивительно простая в использовании штука. Такое выражение можно записать в императивном стиле как почти обычный код на F#, используя while, for и try, а оно потом на выходе будет преобразовано компилятором F# в выражение, состоящее из композиции функции. Императивная конструкция превращается в сугубо функциональное выражение. Замечательная идея. Сюда же легко вписываются монады и моноиды. Вот, с монадными трансформерами накладка.

Поддержка таких выражений – это просто непередаваемая по значимости вещь для императивных монад типа Async для асинхронных вычислений. Более того, не нужно поддерживать на уровне языка продолжения – для них можно использовать те же вычислительные выражения (но нужна поддержка TCO на уровне исполняющей среды). Продолжения не совсем императивны, но все же блоки try-with и try-finally обрабатывать в таком языке как F# надо. И здесь нет известной проблемы Common Lisp.

Кстати, о Лиспе. Считаю, что вычислительные выражения и макросы мешают друг другу. Эти выражения предполагают, что есть ограниченное множество конструкций языка, которые могут быть “офункционалены” (превращены в функции). Макросы это нарушают. Когда я добавлял поддержку вычислительных выражений в Немерле, то оставлял макросы как есть. Не знаю, можно ли придумать здесь что-то лучше? (интересно, а как макросы и продолжения сосуществуют в Схеме?)

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

"Асинхронные" продолжения

2010-08-13T19:10:00.004+04:00

Сегодня осознал одну замечательную вещь. Оказывается, что в F# можно использовать async workflow вместо продолжений… Фактически, async состоит из трех продолжений: основной ветки вычислений, обработки ошибок и экстренной отмены вычислений. Все это разные продолжения под куполом единого значения в монаде Async.

Вот, пример примитивного вычисления функции Аккермана с кешированием промежуточных результатов:

open System.Collections.Generic

let ackermann m n =
   let dict = Dictionary<_, _> ()
   let fix m n x = async {
       let! a = x
       dict.Add ((m, n), a)
       return! x
   }
   let rec ack m n = async {
       if m = 0 then
           return n + 1
       elif dict.ContainsKey (m, n) then
           return dict.[(m, n)]
       elif n = 0 then
           return! fix m n <| ack (m - 1) 1
       else
           let! x = ack m (n - 1)
           return! fix m n <| ack (m - 1) x
   }
   ack m n

А это результат работы:

> ackermann 3 19 |> Async.RunSynchronously;;
Real: 00:01:15.849, CPU: 00:01:15.816, GC gen0: 1398, gen1: 515, gen2: 7
val it : int = 4194301

Без продолжений был бы явный StackOverflowException при гораздо меньших значениях n и m.

Разбор XML на F# с помощью комбинаторов

2010-08-07T15:33:00.003+04:00

Возникла задача разбора потока данных XML, выдаваемых стандартным дотнетовским парсером XmlReader. Раньше я много раз это проделывал на C#, но часто приходилось создавать много дополнительных методов для обработки вложенных тегов XML. Код неприлично разрастался. Теперь захотелось выразительности и декларативности, чтобы разбор сводился к заданию структуры тегов с вкраплениями кода для сбора данных. Получилась представленная ниже крошечная библиотека, идейно близкая к парсер-комбинаторам.

Итак, входной поток задается объектом-значением XmlReader. Неприятность в том, что этот объект несет в себе изменяемое состояние. Это ограничивает наши возможности по разбору. Вероятно, об откатах придется забыть.

Представим наш парсер в виде функции, которая по заданному объекту XmlReader возвращает прочитанные данные в случае успеха, либо сигнализирует о неудаче.


namespace Maritegra.Xml

open System.Xml

type XmlReader<'a> = XmlReader -> 'a option

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

В определении полиморфного типа XmlReader<’a> использована такая особенность дотнета, которая разделяет одноименные типы по параметрам. То есть, введенный тип XmlReader<’a> и стандартный тип XmlReader из System.Xml – это два разных типа. Далее полиморфный тип XmlReader<’a> я буду называть парсером, а, говоря о стандартном типе XmlReader, буду просто использовать его название.

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

Ближе к делу. Очевидно, что парсер XmlReader<’a> является монадой. Сильно не буду углубляться в эту тему. Лишь приведу необходимые определения.

Вот, основные монадические функции, скрытые внутри отдельного модуля (новый F# обычно не позволяет определять глобальные функции вне модулей):


module XmlReaderImpl =

    let returnXR a = fun (r: XmlReader) -> Some a
    let bindXR m k = fun (r: XmlReader) -> match m r with | Some a -> (k a) r | None -> None
    let delayXR k  = fun (r: XmlReader) -> (k ()) r
    let zeroXR     = fun (r: XmlReader) -> Some ()
    let combineXR m1 m2 = fun (r: XmlReader) -> match m1 r with | Some () -> m2 r | None -> None

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


open XmlReaderImpl

type XmlReaderBuilder () =

    member x.Return (a)  = returnXR a
    member x.Bind (m, k) = bindXR m k
    member x.Delay (k)   = delayXR (k: unit -> XmlReader<'a>)
    member x.Zero ()     = zeroXR
    member x.Combine (m1, m2) = combineXR m1 m2

Завершающее определение построителя монады xmlreader:


[<AutoOpen>]
module XmlReaderWorkflow =

    let xmlreader = XmlReaderBuilder ()

Атрибут AutoOpen автоматически делает доступным определение построителя.

Сейчас создадим еще один XmlReader, но уже модуль. Язык F# превосходно справляется с таким смешением имен, но для этого модуль нужно снабдить следующим длинным атрибутом CompilationRepresentation (CompilationRepresentationFlags.ModuleSuffix). Поместим в этот модуль функции запуска run и отображения map. В комментариях указана сигнатура функций. Кроме того, модуль снабдим атрибутом RequireQualifiedAccess, который указывает на обязательность имени модуля при обращении к функциям.


[<RequireQualifiedAccess>]
[<CompilationRepresentation (CompilationRepresentationFlags.ModuleSuffix)>]
module XmlReader =

    // val run: XmlReader -> XmlReader<'a> -> 'a
    let run (r: XmlReader) m = 
        match m r with
        | Some a -> a
        | None -> failwithf "Invalid input data"

    // val map: ('a -> 'b) -> XmlReader<'a> -> XmlReader<'b>
    let map f m = fun (r: XmlReader) ->
        match m r with
        | Some a -> Some (f a)
        | None -> None

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

Начнем с простых комбинаторов, которые извлекают информацию об атрибутах. Они безболезненны и не меняют состояние объекта XmlReader. По заданному имени или порядковому номеру получаем значение атрибута, обернутое в монаду:


    // val attr: string -> XmlReader<string>
    let attr (name: string) = fun (r: XmlReader) -> Some <| r.GetAttribute (name)

    // val attri: int -> XmlReader<string>
    let attri (i: int) = fun (r: XmlReader) -> Some <| r.GetAttribute (i)

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


    // val text: XmlReader<string>
    let text = fun (r: XmlReader) -> Some <| r.ReadElementContentAsString ()

Более сложный случай – это разбор элемента. Комбинатор elem разбирает элемент с заданным именем, применяя для содержимого другой парсер. Если элемент не тот, то, не меняя состояния XmlReader, сразу возвращается None, как и было оговорено в изначальном условии, накладываемом на парсер.


    // val elem: string -> XmlReader<'a> -> XmlReader<'a>
    let elem (name: string) m = fun (r: XmlReader) ->
        if r.IsStartElement (name) then m r else None

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


    // val contents: XmlReader<unit> -> XmlReader<unit>
    let contents (m: XmlReader<unit>) = fun (r: XmlReader) ->
        if r.IsStartElement () then
            if not r.IsEmptyElement then
                let depth = r.Depth
                while r.Read () && (r.Depth > depth) do
                    if (r.Depth = 1 + depth) then 
                        m r |> ignore
            Some ()
        else
            None
            
    // val selectContents: XmlReader<'a> -> XmlReader<'a list>
    let selectContents (m: XmlReader<_>) = fun (r: XmlReader) ->
        if r.IsStartElement () then
            [ if not r.IsEmptyElement then
                let depth = r.Depth
                while r.Read () && (r.Depth > depth) do
                if (r.Depth = 1 + depth) then
                    match m r with
                    | Some a -> yield a
                    | None -> ()
            ] |> Some
        else None

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

На этом определение модуля XmlReader закончено. Теперь в отдельном модуле введем вспомогательный бинарный оператор (+++), который бы объединял два заданных парсера, пытаясь сначала применить первый, а затем второй в случае неудачи.


module Operators =

    // val (+++): XmlReader<'a> -> XmlReader<'a> -> XmlReader<'a>
    let (+++) m1 m2 = fun (r: XmlReader) ->
        match m1 r with
        | Some a as n -> n
        | None -> m2 r

Библиотека закончена. Она содержится в пространстве имен Maritegra.Xml.

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


let document = 
    @"<struct>
        <items>
           <item id='1001' x='1'>10</item>
           <item id='1002' x='2'>20</item>
           <item id='1003' x='3'>30</item>
        </items>
        <links>
           <link source-id='1001' target-id='1003'>PuperLink</link>
           <link source-id='1001' target-id='1002'>WeakLink</link>
        </links>
      </struct>"

Задача состоит в извлечении информации из тегов item и link. Сделать это довольно просто:


open System
open System.Collections
open System.Collections.Generic
open System.IO
open System.Xml

open Maritegra.Xml
open Maritegra.Xml.Operators

type Item = Item of string * string * string
type Link = Link of string * string * string

let proc document =

    use reader = new XmlTextReader (new StringReader (document))
    
    let items = List<_> ()
    let links = List<_> ()
    
    (XmlReader.elem "struct" <|
        (XmlReader.contents <|
            (XmlReader.elem "items" <|
                (XmlReader.contents <|
                    (XmlReader.elem "item" <|
                        xmlreader {
                            let! id   = XmlReader.attr "id"
                            let! x    = XmlReader.attr "x"
                            let! text = XmlReader.text
                            items.Add (Item (id, x, text))
                        })))
            +++
            (XmlReader.elem "links" <|
                (XmlReader.contents <|
                    (XmlReader.elem "link" <|
                        xmlreader {
                            let! sourceId = XmlReader.attr "source-id"
                            let! targetId = XmlReader.attr "target-id"
                            let! text = XmlReader.text
                            links.Add (Link (sourceId, targetId, text))
                        })))))
    |> XmlReader.run reader

    (items, links)

Теперь сюда помещаем определение значения document (единственное место, где порядок приведения кода отличается от линейного). Затем производим разбор и выводим результат:


let (items, links) = proc document

let sprintItem (Item (id, x, text)) = sprintf "Item (%s, %s, %s)" id x text
let sprintLink (Link (sid, tid, text)) = sprintf "Link (%s, %s, %s)" sid tid text

items |> Seq.map sprintItem
      |> Seq.reduce (fun s1 s2 -> s1 + ", " + s2)
      |> printfn "items = seq [%s]"

links |> Seq.map sprintLink
      |> Seq.reduce (fun s1 s2 -> s1 + ", " + s2)
      |> printfn "links = seq [%s]"

Итак, удалось довольно рутинный разбор XML втиснуть внутрь одной функции. На мой взгляд, получилось выразительно, хотя и несколько пестрит словом XmlReader. Используя вышеприведенный подход, можно разбирать довольно сложный XML с большой степенью вложенности, оставаясь в рамках одной функции или выражения. Конечно, метод не претендует на полноту. Например, пока не придумал, как разбирать текстовые поля, чередующиеся с тегами на одном уровне, но мне это и ненужно. Тем не менее, метод интересен тем, что XmlReader очень быстр и легковесен в отличие от того же XmlDocument. Правда стоит отметить, что для XmlDocument можно использовать такую чудесную вещь как активное сопоставление с образцом, что позволяет писать чрезвычайно наглядный и выразительный код, но там нужно предварительно полностью загрузить документ XML в промежуточное представление XmlDocument. В общем, нет в мире совершенства!

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

2010-06-14T12:39:00.000+04:00

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

Дискретно-событийное моделирование

2010-06-06T13:43:00.002+04:00

Для своей маленькой библиотеки имитационного моделирования Айвика [http://sourceforge.net/projects/aivika/] в документацию добавил законченную главу о дискретно-событийном моделировании (DES) и интеграции подмоделей DES в единую гибридную модель. Там получилось все очень функционально.

Вообще, я часто думаю, а можно ли перевести библиотеку на Хаскель? Тем более, самый первый прототип был именно на Хаскеле. Но тут два препятствия. Во-первых, нужна мемоизация, которая бы действовала, пока симуляция запущена. Ну, это, мне кажется, можно обойти, ради скорости сфальшивив в некоторых местах через unsafePerformIO. Все равно, все будет спрятано за монадами, что даст определенные непробиваемые гарантии (как сейчас на F# в Айвике).

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

Обновленная документация к Айвике

2010-05-31T18:23:00.002+04:00

Если кому интересно, то я сегодня выложил обновленную версию свой библиотеки моделирования Айвика [http://sourceforge.net/projects/aivika/]. Там содержится более полная документация. Я описал то, как реализуются в Айвике activity-oriented и event-oriented парадигмы дискретно-событийного моделирования (DES). Также есть краткая информация о монаде DynamicsCont, которая лежит в основе моей реализации process-oriented парадигмы DES. В общем, среди парадигм теперь осталось осветить этот самый process-oriented DES и агентное моделирование (agent-based modeling).

Удивительное дело получается. Сплав методов функционального программирования и имитационного моделирования. Наиболее поразительны результаты в области DES. Тут и две монады, одна из которых является монадным трансформером, параметризованным по другой монаде. Тут еще computation expressions, которые являются в F# синтаксическим сахаром для монад и моноидов. Они делают сочинение моделей DES довольно приятным занятием. Тут же замыкания, которые используются для передачи данных вместе с событиями. Само событие у меня – это просто значение (), обернутое в монаду Dynamics. В общем, красота.

Что несколько удручает, так это большая нагрузка на систему управления памятью (GC). Монады означают, что создается во время моделирования до черта кратко-живущих функций с замыканиями (модуль системной динамики этим не страдает). Но дотнетовский GC неплох, очень неплох. Его двойник в Mono оказался на одной модельке намного тормознее.

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

Aivika версии 2.0

2010-05-23T18:28:00.006+04:00

В ходе разработки моей небольшой библиотеки моделирования Айвика на языке F# произошел ряд важных прорывных событий. Во-первых, я значительно ускорил модуль системной динамики. Обсчет модели по методу Рунге-Кутта стал в раз 5 быстрее. Потом я добавил агентное моделирование (АМ), как его понял после прочтения статьи Андрея Борщева (одного из создателей системы AnyLogic). Для этого я переписал очередь событий модуля дискретно-событийного моделирования (DES), который стал на порядки производительнее. В общем, теперь охватываются все три основные парадигмы имитационного моделирования (ИМ), и в целом я доволен скоростью имитации. Также создал каталог с примерами моделей, каждая из которых снабжена справочной информацией и ссылками. Теперь более подробно.

Модуль системной динамики (SD)

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

Поэтому я переписал внутренности модуля так, чтобы везде использовалась функция одного аргумента. Теперь монада Dynamics стала просто частным случаем монады Reader с небольшим исключением: некоторые функции создают жестко контролируемый побочный эффект. Мне кажется, это можно как-то записать и в хаскеле, но там придется программировать на Си, реализуя местами функциональность монады ST.

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

Еще я лучше осознал смысл термина комбинатор. Оказывается, что все функции eDSL системной динамики являются у меня комбинаторами. Причем выглядят они почти так же как в специализированных системах Simtegra MapSys, ithink или Vensim. Но у меня функции, которые принимают одни функции и создают другие, обладая свойством замыкания.

Агентное моделирование (АМ)

Система AnyLogic использует карты состояний (statecharts) для описания агентов. Я придумал API, которое позволяет достаточно декларативно задавать агенты и их состояния так, как если бы мы использовали эти самые карты состояний. Получается кратко и наглядно. Все действия задаются в монаде Dynamics. Широко используются такие возможности F# как взаимно-рекурсивные определения через let rec и объектные выражения (object expressions). Благодаря монаде Dynamics агенты легко интегрируются с модулем системной динамики.

Дискретно-событийное моделирование (DES)

Агентное моделирование реализовано поверх очереди событий, которая является сердцем DES.

В предыдущей версии очередь была реализована как proof-of-concept, т.е. через двусторонний список… Тормоза стали особенно заметны после добавления АМ. Сначала я переписал очередь через иммутабельный хип, описанный в одной замечательной книге по хаскелю. Но функции добавления и удаления по-прежнему продолжали висеть в списке десяти самых тормозных функций, показываемых профайлером SharpDevelop. Тогда я переписал очередь через императивный бинарный хип, реализованный на основе массива. Функции работы c очередью ушли из списка. Агентное моделирование просто взлетело.

Примеры моделей

Я создал аналоги моделей, используемых в системах Simtegra MapSys (SD), Berkeley&Madonna (SD), AnyLogic (АМ) и SimPy (DES). Также реализовал пару моделей, описанных в книге Ильи Труба “Объектно-ориентированное моделирование на C++”.

Планы

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

Сейчас в документации достаточно полно освещен модуль системной динамики. Теперь нужно описать модули дискретно-событийного моделирования (DES) и агентного моделирования (АМ). Думаю, что можно заняться продвижением. Важно, что библиотеку можно использовать и из C#, но наиболее полно возможности доступны только через F#.

Релиз MapSim версии 4.1

2010-05-01T20:39:00.002+04:00

Сегодня выложил релиз версии 4.1 движка моделирования MapSim для системной динамики. Он используется в визуальной среде для моделирования Simtegra MapSys, также разработанном мною в сотрудничестве со своим партнером. Основная новая возможность – можно менять параметры во время симуляции. Это нужно для проигрывания симуляций в MapSys. Все написано на C#.

Работа над ошибками

2010-05-01T09:36:00.000+04:00

Выпустил новую версию 1.0.4.0 библиотеки моделирования Aivika на F#. В прежней версии обнаружил ошибку в реализации блоков try-finally и try-with для вычислительного выражения dynamicscont. По своей сути это частный случай монадного трансформера, построенного на основе продолжения. Дело в том, что фактически надо хранить два продолжения, а не одно. Первое продолжение используется для основной ветки вычислений. Второе продолжение - для обработки исключительных ситуаций.

Обновленный тип выглядит так:

type DynamicsCont<'a> = Dynamics<('a -> unit) * (exn -> unit)> -> Dynamics<unit>

Выводится из следующего типа Cont с учетом одного упрощения, характерного именно для монадного типа Dynamics:

type Cont<'a> = ('a -> unit) * (exn -> unit) -> unit

Здесь функция от двух продолжений: основного потока вычислений и обработчика ошибок. Особенность заключается в том, что монадический переход bind должен быть защищен в узком месте блоком try. В случае возникновения ошибки должно активироваться второе продолжение для обработки ошибок.

Сначала я составил необходимые функции для Cont. Потом сверил с реализацией стандартного async. Убедился, что все правильно. Затем перенес на тип DynamicsCont.

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

Добавил Computation Expressions в Nemerle

2010-04-25T20:08:00.000+04:00

При содействии Андрея Белякова (WolfHound) и Владислава Чистякова (VladD2) я добавил поддержку computation expressions в Nemerle. Поддерживаются все вычислительные конструкции F#, но несколько своим образом, подстроенным под особенности самого Nemerle. Но пока синтаксис не устоялся.

Я думаю, что мне удалось угадать алгоритм разбора правильно. На базе computation expressions реализованы list comprehension, array comprehension и enumerable (sequence) comprehension как частный случай общего механизма. Добавил все, используя макросы и не меняя сам компилятор языка. Получилась внешняя библиотека.

Должен сказать, что Nemerle произвел очень приятное впечатление. Язык и среда достойны всяческого внимания.

Aivika версии 1.0.3.0

2010-04-14T11:40:00.000+04:00

Выложил новую версию библиотеки моделирования Aivika. Написана она на F# с использованием двух монад. Эта библиотека позволяет создавать и запускать имитацию гибридных моделей. Сейчас охватывается системная динамика (System Dynamics) и Discrete Event Simulation (как time-driven, event-driven так и process-driven simulation). В планах добавление agent-based modeling. В тестах обгоняет SimPy примерно в два раза на его же типе задач, хотя Aivika умеет значительно больше. Есть недописанный обрывок документации.

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

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

Поверх этой монады есть ее продолжение DynamicsCont<’a> = Dynamics<’a -> unit> -> Dynamics<unit>. Фишка в том, что используя синтаксис вычислительный выражений, можно писать как бы “обычный” код на F# в монаде DynamicsCont, который будет временами прерываться. Это нужно для реализации “процессов”, которые могут усыпляться, просыпаться, ставиться в очередь на выполнение в такое-то время, блокироваться для захвата разделяемого ресурса и т.д. Все это предполагается в process-driven simulation. Используются свойства продолжения.

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

Все хозяйство представляет собой embedded domain specific language (eDSL). Поскольку внутри используются монады, то легко встраивать вызовы функций .NET внутрь симуляции через вычислительные выражения, т.е. через монадический bind. eDSL же дает возможность встраивать симуляции в обычные .NET приложения.

Подозреваю, что подобные системы стоят дорого. Проблема в том, что мой код получился очень маленьким по объему (90 кб)… и не таким быстрым.

Обратные связи

2010-03-23T19:31:00.000+03:00

Язык F# в наследство от OCaml получил интересную возможность задавать рекуррентные отношения декларативно, как есть. Например, в моих сообщениях постоянно используется одна и та же система дифф-уров. Теперь ее можно переписать на F# следующим образом:


  let rec a = integF (lazy (- ka*a)) 100.0
  and b = integF (lazy (ka*a - kb*b)) 0.0
  and c  = integF (lazy (kb*b)) 0.0
  and ka = 1.0
  and kb = 1.0

Это – работающий пример, где функция integF возвращает интеграл (как некое вычисление в монаде моделирования) по заданной производной и начальному значению. Здесь мы видим, что (1) переменные можно задавать произвольно без указания зависимости, (2) обратные связи задаются через явную ленивость. Фактически есть еще третий очень важный пункт: (3) компилятор сам следит за разрешимостью системы (в отличие от того же Haskell). Мне особенно нравится этот пункт, поскольку он делает подобный метод пригодным для широкого практического применения. Например, у нас имеется eDSL, а неискушенные пользователи задают свои системы. Компилятор сам все проверит и укажет на ошибку в случае необходимости. Неоценимое свойство.

Правда, в случае одной более сложной системы компилятор F# (v1.9.9.9) почему-то неправильно вывел переменные. Соответствующий bug report был отослан. Я думаю, что это – временное явление.

Рекуррентные отношения можно задавать и более хитрым способом, используя генераторы массивов:


  let smoothNI (x: Lazy<Dynamics<float>>) (t: Lazy<Dynamics<float>>) n (i: Dynamics<float>) =
   let rec s = [|
    for k = 0 to n-1 do
     if k = 0 then
      yield integ (lazy ((x.Value - s.[k]) / (t.Value / (float n)))) i
     else
      yield integ (lazy ((s.[k-1] - s.[k]) / (t.Value / (float n)))) i |]
   in s.[n-1]

Здесь возвращается функция (значение в монаде моделирования), которая называется экспоненциальной порядка n сглаживающей x по времени t с начальным значением i.

Мне нравится.

Потоки (Streams)

2010-02-28T20:26:00.000+03:00

Вчера прочитал главу SICP, посвященную потокам (streams). Возникло острое желание переписать примеры на Common Lisp (CL). Тема очень интересна сама по себе. Еще подстегивало то, что некоторые активисты упорно пропагандируют идею оторванности CL от функциональной парадигмы (ФП), как бы это абсурдно ни звучало. Но когда я приступил к переписыванию кода на CL, мое первое обманчивое впечатление было таким, что потоки будет реализовать труднее, чем в Схеме. Например, в CL нет аналога схемовского DEFINE, который бы позволил определять переменные рекурсивно. Но, к счастью, все разрешилось удачным образом. Как и должно было быть, выручили макросы, могучая сила CL. Они же мне позволили в свое время добавить очень простой и удобный синтаксический сахар для монад по типу нотации do, о чем я писал ранее. Итак, все начинается с ленивости. Для этого определяются конструкции DELAY и FORCE, но прежде нужна вспомогательная функция MEMO, которая возвращает функцию без аргументов, результат которой кешируется: (defun memo (fun) (let ((already-run? nil) (result nil)) #'(lambda () (if (not already-run?) (progn (setf result (funcall fun)) (setf already-run? t) result) result)))) Тут все по книге SICP, только там функция называлась MEMO-PROC. Дальше определяем конструкции DELAY и FORCE, причем DELAY должен быть непременно макросом, чтобы он мог упрятать свой аргумент в лямбду, сделав его тем самым ленивым: (defmacro delay (exp) `(memo #'(lambda() ,exp))) (defun force (delayed-exp) (funcall delayed-exp)) Теперь можно приступить к реализации примитивов, с помощью которых будут создаваться потоки. Среди этих примитивов выделяется особо конструктор пары CONS-STREAM, который тоже должен быть макросом, чтобы иметь возможность сделать свой второй аргумент ленивым. Собственно, в этом заключена суть потоков. (defmacro cons-stream (a b) `(cons ,a (delay ,b))) (defun stream-car (stream) (car stream)) (defun stream-cdr (stream) (force (cdr stream))) (defun stream-null (stream) (null stream)) (defparameter *empty-stream* nil) Функция STREAM-CDR раскрывает ленивую CDR-часть потока, если она не была до того уже раскрыта. Как помним, на нижнем уровне за это отвечает функция MEMO, которая встраивается при создании каждой пары. В общем, это все уже описано в SICP. Поэтому останавливаться не буду. Следующая функция STREAM-REF аналогична AREF, но работает уже с потоками. (defun stream-ref (stream n) (loop for i from 0 to n for s = stream then (stream-cdr s) finally (return (stream-car s)))) Несмотря на присутствие в реализации совсем нефункционального LOOP, функция является чистой. Далее идут отображения для потоков. Вполне в духе ФП. (defun stream-map (fun stream) (if (stream-null stream) stream (cons-stream (funcall fun (stream-car stream)) (stream-map fun (stream-cdr stream))))) (defun stream-map2 (fun s1 s2) (cond ((stream-null s1) s1) ((stream-null s2) s2) (t (cons-stream (funcall fun (stream-car s1) (stream-car s2)) (stream-map2 fun (stream-cdr s1) (stream-cdr s2)))))) Далее понадобится функция фильтрации потока. Я поменял имя STREAM-FILTER на более идиоматическое. К тому же задействовал LOOP. При этом функция остается чистой. (defun stream-remove-if-not (test stream) (loop for s = stream then (stream-cdr s) when (stream-null s) do (return s) when (funcall test (stream-car s)) do (return (cons-stream (stream-car s) (stream-remove-if-not test (stream-cdr s)))))) Чтобы опробовать новые возможности в деле, понадобятся еще итератор и функция вывода: (defun stream-iter (fun stream) (loop for s = stream then (stream-cdr s) while (not (stream-null s)) do (funcall fun (stream-car s)))) (defun print-stream (stream) (stream-iter #'(lambda (x) (format t "~%~a" x)) stream)) Теперь, можно немного поиграться, чтобы убедиться в работоспособности базовых конструкций: CL-USER> (print-stream (cons-stream 1 (cons-stream 2 (cons-stream 3 nil)))) 1 2 3 NIL Подходим к главному препятствию. В схеме мы могли легко определить поток рекурсивно. Например, поток единиц задавался бы так: (define ones (cons-stream 1 ones)) ;; Scheme! Несмотря на кажущуюся простоту выражения, компилятор выполняет много работы. Придется это повторить. Я лишь покажу конечный результат. Аналогом на CL будет следующее определение: (defparameter *ones* (recurrent-let ((ones (cons-stream 1 ones))) ones)) Здесь RECURRENT-LET похож на LET с одной переменной. Отличие заключается в том, что к самой переменной можно обращаться внутри определения. То есть, определение может быть рекурсивным. Сам макрос RECURRENT-LET достаточно прост: (defmacro recurrent-let (((name value)) &body body) (let ((x (gensym))) `(let ((,x (cons nil nil))) (symbol-macrolet ((,name (force (car ,x)))) (setf (car ,x) (delay ,value)) ,@body)))) Вот, во что будет раскрыта внутренняя часть определения параметра *ONES*: (LET ((#:G764 (CONS NIL NIL))) (SYMBOL-MACROLET ((ONES (FORCE (CAR #:G764)))) (SETF (CAR #:G764) (DELAY (CONS-STREAM 1 ONES))) ONES)) Мы создаем некий объект с одним полем. Это поле содержит ленивое значение переменной. Любое (рекурсивное) обращение к переменной мы трактуем как попытку немедленно вычислить ее значение, если оно еще не вычислено. Трюк работает, потому что мы успеваем присвоить полю объекта ленивое значение прежде первого обращения к этой переменной. Это гарантирует использованный макрос DELAY. Стоит заметить, что данное представление бесконечного потока единиц на самом деле занимает очень мало памяти, поскольку поток ссылается на самого себя. Если присмотреться к определению макроса, то можно увидеть, что внутри определения рекурсивной переменной мы можем использовать еще один RECURRENT-LET, а также любую другую конструкцию, включая LET, FLET и LABELS. Это открывает путь к вложенным и более сложным взаимно-рекурсивным определениям, что и будет продемонстрировано далее. В соответствии с SICP определим вспомогательные функции: (defun add-streams (stream1 stream2) (stream-map2 #'+ stream1 stream2)) (defun scale-stream (stream factor) (stream-map #'(lambda (x) (* x factor)) stream)) Далее определим поток целых чисел: (defun integers-starting-from (n) (cons-stream n (integers-starting-from (+ n 1)))) (defparameter *integers-alpha* (integers-starting-from 1)) Этот же самый поток мы можем определить иначе: (defparameter *integers* (recurrent-let ((integers (cons-stream 1 (add-streams *ones* integers)))) integers)) Естественно, без определения потока чисел Фибоначчи мое сообщение можно было бы считать неполным: (defparameter *fibs* (recurrent-let ((fibs (cons-stream 0 (cons-stream 1 (add-streams (stream-cdr fibs) fibs))))) fibs)) Теперь можем узнать, каким будет 1001-ое число Фибоначчи: CL-USER> (stream-ref *fibs* 1001) 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501 Как и следовало ожидать, ответ был немедленным. Следуя SICP, далее приведу пример определения потока простых чисел. Но прежде мне понадобятся две простые утилиты. (defun square (n) (* n n)) (defun divisible-p (x y) (= (mod x y) 0)) Сам поток определен ниже. Это также пример взаимно-рекурсивного определения. (defparameter *primes* (recurrent-let ((primes (flet ((prime-p (n) (labels ((iter (ps) (cond ((> (square (stream-car ps)) n) t) ((divisible-p n (stream-car ps)) nil) (t (iter (stream-cdr ps)))))) (iter primes)))) (cons-stream 2 (stream-remove-if-not #'prime-p (integers-starting-from 3)))))) primes)) Еще один пример — решатель дифференциальных уравнений. Сначала определяем интеграл, где интегрируемая функция передается лениво: (defun integral (delayed-integrand initial-value dt) (recurrent-let ((int (cons-stream initial-value (let ((integrand (force delayed-integrand))) (add-streams (scale-stream integrand dt) int))))) int)) Теперь сам решатель: (defun solve (f y0 dt) (recurrent-let ((y (recurrent-let ((dy (stream-map f y))) (integral (delay dy) y0 dt)))) y)) Можем проверить как и в SICP: CL-USER> (stream-ref (solve #'(lambda (y) y) 1 0.001) 1000) 2.7169204 Как видим, примеры достаточно легко ложатся на CL, хотя и выглядят несколько иначе. При этом они вполне соответствуют духу ФП. Разве что, использование LOOP несколько необычно для этой области, но это прекрасный пример сочетания разных подходов к программированию. Основа остается несомненно функциональной. Неужели после этого может кто-то по-прежнему утверждать, что CL не является языком функционального программирования?

Монада моделирования. Код

2010-02-06T14:18:00.000+03:00

Открыл новый проект Aivika на SourceForge. Там лежат исходники моделирующей библиотеки для F#. Пожалуй, функцию memo нужно будет оптимизировать. Вероятно, из-за нее тормозит. Но есть задача важнее. Теперь буду пытаться продвигать идею на инглише.

Монада моделирования. Часть вторая. Первые шаги в Common Lisp.

2010-02-05T09:33:00.000+03:00

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

В общем, это все уже работает на F#, хотя и медленно. Рабочее название соответствующей библиотеки для F# – Aivika. Теперь я перенес базовую часть на Common Lisp, назвав новую библиотеку Salika. Соответствующий монадический макрос назвал как WITH-DYNAMICS-MONAD. Этот макрос полностью соответствует интерфейсу монадических макросов из пакета cl-monad-macros, о котором я писал в своем блоге ранее. Вкратце, такие макросы добавляют удобный синтаксический сахар по типу нотации do из хаскеля.

Возьмем простую динамическую систему, описанную на языке MapSim:

A = integ (-F, 100);
B = integ (F - G, 0);
C = integ (G, 0);

F = ka * A;
G = kb * B;

ka = 1;
kb = 1;

Функция integ задает интеграл. В первом параметре функции определяется производная по времени. Во втором – начальное значение интеграла. Интегрирование происходит на промежутке starttime <= t <= stoptime с шагом dt. Здесь A(t), B(t) и C(t) – интегралы. Их еще иногда называют в системной динамике резервуарами. Функции F(t) и G(t) называют дополнительными. В системе также заданы константы ka и kb.

В первой ссылке есть пример того, как эту систему можно задать на языке F#. Там получается достаточно близко к математической нотации. Во многом благодаря тому, что для типа монады моделирования легко определить арифметические операции и стандартные функции типа синуса и косинуса. Такой подход можно встретить, например, в книге “The Haskell School of Expression” автора Paul Hudak. В случае же Common Lisp я предпочитаю использовать монадические макросы напрямую, поскольку это порождает в целом более эффективный код. Думаю, что наглядность при этом страдает несильно.

Итак, такую систему мы можем описать на Common Lisp следующим образом.

(defun create-process ()
(let* ((ka 1d0)
         (kb 1d0))
    (let* ((integ-a (make-instance 'integ-stock :initial-value 100d0))
           (integ-b (make-instance 'integ-stock :initial-value 0d0))
           (integ-c (make-instance 'integ-stock :initial-value 0d0)))
      (let* ((f (with-dynamics-monad
                  (let! ((a (current-value integ-a)))
                    (unit (* ka a)))))
             (g (with-dynamics-monad
                  (let! ((b (current-value integ-b)))
                    (unit (* kb b))))))
        (setf (outflow integ-a) f)
        (setf (inflow integ-b) f)
        (setf (outflow integ-b) g)
        (setf (inflow integ-c) g)
        (current-value integ-a)))))

Единственный момент – в примере возвращается лишь интеграл A, но как часть всей системы. Здесь монаду можно увидеть в том, как задаются динамические процессы для переменных F и G. Внутри макроса WITH-DYNAMICS-MONAD макроc LET! эквивалентен стрелке из нотации do, а макрос UNIT – функции return для монады. Получается, что F и G возвращают монады. Более того, выражение (current-value integ-a) – тоже монада. Это представления динамических процессов.

Такую систему достаточно просто промоделировать. Нижеследующая функция запускает соответствующую имитацию и возвращает значения интеграла A в основных узлах интегрирования, как это принято в методах Эйлера и Рунге-Кутта.

(defun run-process ()
(with-dynamics-monad
(run! (create-process) (make-specs :start-time 0.0 :stop-time 10.0 :method 'runge-kutta-4 :dt 0.1)))))

Среда лиспа проинтегрирует модель методом Рунге-Кутта четвертого порядка, начиная от точки 0 и заканчивая точкой 10 с основным шагом интегрирования 0,1.

SALIKA> (run-process)
(100.0d0 90.48374986516933d0 81.8730898966253d0 74.08184186894766d0
         67.03202849220888d0 60.65309299043932d0 54.88119294695767d0
         49.658561349146126d0 44.932928437803035d0 40.65699857475723d0
         36.787976893068794d0 33.28714099238066d0 30.119453392811955d0
         27.253210868708226d0 24.65972715266909d0 22.313045834254343d0
         ...)

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

Тем не менее, во время интегрирования таких уравнений внутри используется сугубо императивная функция мемоизации MEMO-PROCESS. Она аналогична функции memo из F#-вской библиотеки. Обе эти функции принимают динамический процесс, т.е. некоторое значение в монаде моделирования, и возвращают процесс-двойник, который кеширует все значения первого процесса в узлах интегрирования, причем вычисления происходят строго последовательно по узлам. Это открывает путь к построению гибридных моделей, поскольку мы здесь знаем, что первый, т.е. кешируемый процесс будет вычисляться в строго определенном порядке (если нет других ссылок на него). Такой процесс мы можем реализовать как итерационный. Это еще одна вещь наряду с недетерминизмом, которую будет трудно или почти невозможно воспроизвести в хаскеле.

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

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

Версия для F# достаточно зрелая и многое умеет, включая стохастику. Версия для Common Lisp реализует пока лишь интегралы и мемоизацию, причем нет оптимизации по типам. Может быть, потом выложу результаты в свободный доступ. Хотя мне кажется, что описанное в обеих частях достаточно легко воспроизвести, поскольку первая часть содержит полное описание монады моделирования на языке F#.

Монада моделирования

2010-02-03T10:27:00.000+03:00

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

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

Сначала приведу пример простой динамической системы, записанной на языке MapSim:

A = integ (-F, 100);
B = integ (F - G, 0);
C = integ (G, 0);

F = ka * A;
G = kb * B;

ka = 1;
kb = 1;

Здесь функция integ задает интеграл. Ее первым параметром является производная по времени, а вторым – начальное значение. То есть, A(t) является интегралом (еще говорят резервуаром), производная которого равна dA/dt = –ka*A(t). В начальный момент времени значение A(t₀) равно 100. Это задача Коши.

Такая система может быть интегрирована методами Эйлера и Рунге-Кутта второго и четвертого порядков. Задается начальное время starttime, конечное stoptime и основной шаг интегрирования dt. Затем временная шкала разбивается на узлы: starttime, starttime + dt, starttime + 2*dt, …, stoptime. В случае методов Рунге-Кутта создаются еще дополнительные внутренние под-узлы. В итоге каждый узел сетки интегрирования однозначно задается парой целых чисел: номером итерации и номером фазы. Метод Эйлера имеет всего одну фазу. Метод Рунге-Кутта второго порядка – две фазы. Метод четвертого порядка – четыре фазы.

type Iteration = int
type Phase = int
type Method = Euler | RungeKutta2 | RungeKutta4

Здесь и далее я буду использовать F# для записи кода.

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

type Randomness = SimpleRnd | StrongRnd

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

type Specs = {
spcStartTime: float; spcStopTime: float; spcDT: float;
spcMethod: Method; spcRandomness: Randomness
}

Для нашего примера мы могли бы взять следующие параметры: начальное время – 0, конечное время – 10, основной шаг интегрирования – 0,1, метод – Рунге-Кутта четвертого порядка, а режим генератора – «сильная» псевдо-случайность, хотя последний никак не используется в этой модели.

let specs = {
spcStartTime=0.0; spcStopTime=10.0; spcDT=0.1;
spcMethod=RungeKutta4; spcRandomness=StrongRnd
}

Саму систему мы можем начать описывать с констант ka и kb.

let ka = 1.0
let kb = 1.0

Затем объявляем интегралы и задаем для них начальные значения.

let a = Integ 100.0
let b = Integ 0.0
let c = Integ 0.0

Каждый из трех интегралов имеет свойства Value, Inflow и Outflow. Эти свойства связаны дифференциальными уравнениями, одно из которых я покажу на примере интеграла a:

d/dt (a.Value) = (a.Inflow – a.Outflow)

Такие же уравнения имеют место для других интегралов. Свойство Value возвращает текущее значение интеграла, и оно доступно только по чтению. Свойства Inflow и Outflow можно менять. Они оба вместе задают производную. По-умолчанию, они представляют нулевые значения. То есть, если мы не зададим ни одно из свойств Inflow и Outflow, то производная будет равна нулю, а интеграл окажется константой.

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

let f = ka * a.Value
let g = kb * b.Value

И завершаем описание задачи собственно самими дифференциальными уравнениями:

a.Inflow <- -f
b.Inflow <- f – g
c.Inflow <- g

Удивительно, но это все – что нам нужно, чтобы немедленно запросить библиотеку промоделировать, скажем, переменную a и вернуть результат:

> runDynamics a.Value specs;;
val it : float [] =
[|100.0; 90.48375; 81.87309014; 74.0818422; 67.03202889; 60.65309344;
    54.88119344; 49.65856187; 44.93292897; 40.65699912; 36.78797744;
    33.28714154; 30.11945393; 27.2532114; 24.65972767; 22.31304633;
    20.18968106; 18.26838054; 16.52991577; 14.95688766; 13.53355284;
    12.24566612; 11.08033792; 10.02590526; 9.071815051; 8.208518451;
    7.427375314; 6.720567711; 6.081021686; 5.50233646; 4.978720367;...|]

Более того, мы можем запросить результаты не только для одной переменной, но и для целой группы, попросив включить в список и модельное время:

> runDynamics Dynamics.ofArray [| time; a.Value; b.Value; c.Value |] specs;;
[|[|0.0; 100.0; 0.0; 0.0|];
[|0.1; 90.48375; 9.048333333; 0.4679166667|];
[|0.2; 81.87309014; 16.37454263; 1.752367234|];
[|0.3; 74.0818422; 22.22445032; 3.693707481|];
[|0.4; 67.03202889; 26.81268809; 6.155283021|];
[|0.5; 60.65309344; 30.32640707; 9.020499487|]; ...|]

Поразительная краткость, не правда ли?

Все это стало возможным благодаря использованию монады моделирования, которая является вариацией стандартной монады Reader. Еще меня натолкнула на ее написание замечательная книга «The Haskell School of Expression» автора Paul Hudak.

Итак, мы моделируем некоторый динамический процесс, который в каждый момент времени возвращает некоторое значение типа 'a. Обозначим этот полиморфный тип как Dynamics<'a>.

[]
type Dynamics<'a> (iter: Iterator<'a>) =
member d.Iterator = iter

let iterator (p: Dynamics<'a>) = p.Iterator

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

type Iterator<'a> = Run -> Specs -> Iteration -> Phase -> 'a

То есть, итератор – это просто функция. Здесь появился новый тип Run, c которым связан недетерминизм и не только. В упрощенном виде (после удаления некоторых оптимизаций) этот тип выглядит так.

type Run () =
    let mutable disposed = false
    let disposedEvent = new Event<_>()
    member x.Disposed = disposedEvent.Publish
    member x.IsDisposed = disposed
    interface IDisposable with
        member x.Dispose() =
            if not disposed then
                disposedEvent.Trigger()
                disposed <- true

Когда мы запускаем имитацию, мы создаем уникальный экземпляр типа Run. Затем во время интегрирования мы передаем это значение в итератор динамического процесса. Ориентируясь на такое значение, любая функция может создать некоторые внутренние данные, которые будут актуальны, пока существует значение типа Run. Например, это может быть таблица кеширования предыдущих значений для интеграла внутри объекта типа Integ. Когда имитация заканчивается, значение типа Run разрушается, но предварительно вызывается метод Dispose, который посылает сигнал Disposed. Одна из внутренних функций интеграла или уровнем ниже ловит этот сигнал, и разрушает таблицу кеширования. Так достигается следующее.

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

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

let runDynamics d specs = [|

    use r = new Run ()

    let f1 = iterator d r specs
    let f2 = fun n -> f1 n 0

    for i = 0 to (Specs.iterations specs - 1) do yield f2 i
|]

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

Собственно, все. Дальше монада моделирования определяется просто. Ее функции return и bind почти такие же, как и в случае монады Reader.

[]
type DynamicsBuilder() =
    member d.Return (a) =
        new Dynamics<'a> (fun r s n ph -> a)
    member d.Bind (m, k) =
        new Dynamics<'b> (fun r s n ph ->
            let a = iterator m r s n ph
            let m' = k a
            iterator m' r s n ph)

Тогда мы можем определить свой workflow. Назовем его dynamics. Он позволяет использовать синтаксический сахар в F#, похожий на нотацию do из хаскеля, где let! будет эквивалентен стрелке.

let dynamics = new DynamicsBuilder()

Более того, мы можем определить арифметические операции и основные функции типа синуса в соответствии с образцом:

type Dynamics<'a> with
static member (+) (a: Dynamics, b: Dynamics) =
Dynamics.lift2 (+) a b

Здесь функция lift2 достаточно идиоматична. Она берет некоторую функцию и два значения, обернутые в монаду. Значения извлекаются, к ним применяется функция, и результат снова заворачивается в монаду.

module Dynamics =
    let lift2 f m1 m2 = dynamics {
        let! a1 = m1
        let! a2 = m2
        return f a1 a2}

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

module Dynamics =
    let lift2 f m1 m2 = Dynamics<_> (fun r s n ph ->
        let a1 = iterator m1 r s n ph
        let a2 = iterator m2 r s n ph
        in f a1 a2)

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

module Dynamics =
val memo: Dynamics<'a> -> Dynamics<'a>

Здесь для краткости приведу лишь функцию integ – аналог одноименной функции MapSim, причем только для интегрирования по методу Рунге-Кутта второго порядка. Для других методов определены аналогичные внутренние функции integEuler и integRK4.

    let integ (f: Dynamics) (i: Dynamics) =

        // integEuler and integRK4

        let integRK2 (y: Dynamics<_>) (f: Dynamics<_>) (i: Dynamics<_>) r s =
            let vy n = iterator y r s n 0
            let vi n = iterator i r s n 0
            let k1 n = iterator f r s n 0
            let k2 n = iterator f r s n 1
            fun n ph ->
                match n, ph with
                    | 0, 0 -> vi 0
                    | n, 0 -> vy (n-1) + s.spcDT/2.0 * (k1 (n-1) + k2 (n-1))
                    | n, 1 -> vy n + s.spcDT * k1 n
                    | _ -> failwithf "integRK2: incorrect phase = %i" ph

        let rec y = Dynamics.memo z
        and z = Dynamics<_> (fun r s ->
            match s.spcMethod with
                | Euler -> integEuler y f i r s
                | RungeKutta2 -> integRK2 y f i r s
                | RungeKutta4 -> integRK4 y f i r s)
        in y

Но одной функции integ недостаточно в F#, потому что нужно разруливать как-то рекурсивные связи. Поэтому придумал трюк с отдельным типом Integ и тремя его свойствами Value, Inflow и Outflow. Сам тип Integ использует внутри функцию integ.

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

В заключение несколько слов о скорости имитации. Она ужасна. Мои тесты показали, что библиотека Aivika медленнее MapSim в десятки или сотни раз, хотя и там, и там – .NET. И автор один и тот же J.

Теперь вот думаю, а не написать ли мне подобное на Common Lisp – там некоторые вещи можно сделать быстрее за счет более умной кодогенерации.

Алгебраические типы данных в Common Lisp

2010-01-28T12:34:00.001+03:00

В продолжение функциональной темы. В ходе беседы у меня возникла идея того, как можно создавать и обрабатывать так называемые алгебраические типы данных (algebraic data types - ADT) вроде таких

data TaggedType a = NoneValue
| SingleValue a
| DoubleValue (a, a)

Здесь NoneValue, SingleValue и DoubleValue являются также конструкторами данных. Компилятор хаскеля по такому определению автоматически создает одноименные функции. Мы их тоже создадим. Будем делать все через списки. Первым элементом списка будет идти символическое имя конструктора, т.е. тег. Затем в списке будут идти данные. Это позволит нам различать значения.

(defun none-value ()
(list 'none-value))

(defun single-value (a)
(list 'single-value a))

(defun double-value (a1 a2)
(list 'double-value a1 a2))

Как видим, все очень просто. Теперь мы можем вручную устроить сопоставление с образцом (pattern-matching).

(defun test-tagged-type (v)
(ecase (car v)
    (none-value (format t "NoneValue "))
    (single-value (format t "SingleValue ~A" (cadr v)))
    (double-value (format t "DoubleValue (~A, ~A)" (cadr v) (caddr v)))))

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

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

(defmacro define-adt (name &rest args)
`(defun ,name (,@args)
(list ',name ,@args)))

Следующий макрос позволяет более наглядно сопоставлять с образцом. Его имя похоже на имена стандартных макросов CASE, CCASE и ECASE. Приставка ADT указывает, что работа идет с алгебраическими типами данных.

(defmacro adt-case (value &body cs)
(let* ((t-defined nil)
         (ps (loop for c in cs collect
                  (cond
                    ((eql (car c) 't)
                     (setf t-defined t)
                     (append '(t) (cdr c)))
                    (t
                     (when t-defined
                       (error "The T clause can be only the last in the form."))
                     (destructuring-bind ((name &rest args) &body body) c
                       (adt-pattern value name args body)))))))
    (if t-defined
        `(case (car ,value) ,@ps)
        `(ecase (car ,value) ,@ps))))

(defun adt-pattern (value name args body)
`(,name
    ,(if (null args)
         `(progn ,@body)
         `(destructuring-bind (,@args) (cdr ,value) ,@body))))

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

(define-adt none-value)
(define-adt single-value a)
(define-adt double-value a1 a2)

(defun test-tagged-type (v)
(adt-case v
    ((none-value) (format t "NoneValue"))
    ((single-value a) (format t "SingleValue ~a" a))
    ((double-value a1 a2) (format t "DoubleValue (~a, ~a)" a1 a2))))

Сопоставление с образцом было бы неполным, если бы не было замены хаскелевского шаблона “_”. Я выбрал в качестве аналога лисповский терм T. Соответствующее условие должно быть самым последним в списке, иначе компилятор выдаст ошибку.

(defun test-tagged-type-2 (v)
(adt-case v
((none-value) (format t "NoneValue"))
(t (format t "Not NoneValue"))))

И, наконец, приведу функцию, которая берет значение типа TaggedType и возвращает либо NIL, либо новую CONS-пару.

(defun tagged-type->cons (v)
(adt-case v
    ((none-value) nil)
    ((single-value a) (list a))
    ((double-value a1 a2) (cons a1 a2))))

Пример использования:

CL-USER> (tagged-type->cons (double-value 1 2))
(1 . 2)

Монадические макросы для Common Lisp

2010-01-22T14:48:00.000+03:00

Изобрел монадические макросы для Common Lisp и оформил их в виде пакета cl-monad-macros. На мой взгляд, получилась довольно интересная вещь, основным достоинством которой является высокая эффективность генерируемого кода. Здесь было бы интересно посостязаться с хаскелевскими компиляторами. Потом поместил объявление на comp.lang.lisp.

Основная идея состоит в том, что мы задаем монадические макросы типа WITH-MONAD, которые внутри себя через MACROLET определяют унифицированные макросы UNIT, FUNCALL!, LET! и PROGN!. Макрос UNIT – это хасклевская функция return, FUNCALL! – это bind с обратным порядком параметров (=<<), LET! – альтернатива стрелке, а PROGN! – замена хаскелевского then (>>). Причем LET! по виду похож на стандартный LET*, а PROGN! – на стандартный PROGN. Более того, в случае монады Identity (макрос WITH-IDENTITY-MONAD) макрос LET! совпадает с LET*, PROGN! – с PROGN, FUNCALL! – c FUNCALL, а UNIT становится эквивалентным обычной функции IDENTITY. Все это позволяет писать код в единой нотации – меняем только монадические макросы типа WITH-MONAD.

Например, макрос WITH-LIST-MONAD задает монаду List. Следующая функция возвращает все возможные перестановки заданного списка.

(defun perms (xs)
(with-list-monad
      (if (null xs)
         (unit nil)
          (let! ((y xs)
                (ys (perms (remove y xs :count 1))))
                (unit (cons y ys))))))

Функцию можно протестировать:

CL-USER> (perms '(1 2 3))
((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))

По своей сути LET! – это обобщенный случай List Comprehension. PROGN! создает последовательность вычислений. Самое интересное, что реализация всех этих макросов в общем случае проста как топор. За это отвечает монадический макрос WITH-MONAD.

Пакет cl-monad-macros предоставляет также готовые монадические макросы для монад Identity, List, Maybe, Reader, State и Writer. Последняя монада несколько отличается от канона, но суть та же. Такие специализированные макросы порождают намного более эффективный код для своих монад, чем обобщенный макрос WITH-MONAD.

Были сложности с монадными трансформерами. Для них, кстати, отдельные макросы – необходимость. В пакете есть макросы для трансформеров Reader, State и Writer. Это параметризуемые монадические макросы, где параметром является другой монадический макрос. Довольно мощная абстракция, которая позволяет комбинировать несколько монад в одной.

Если пытаться использовать монадические макросы для транформеров непосредственно в коде, то легко загнать лисповский компилятор в ступор. Дело в том, что эти макросы при раскрытии создают множество вложенных MACROLET-ов. У компиляторов от этого сносит голову напрочь. Но пока мне такая кодо-генерация представляется единственно возможной для трансформеров, если делать именно через макросы, а не generic-функции. Но, к счастью, есть простое решение. Назвал его упрощением (редукцией) монадических макросов. С обычными же непараметризуемыми макросами типа WITH-MONAD и WITH-LIST-MONAD все нормально.

Теперь вот думаю дополнить монадические макросы вспомогательными макросами. Нужны аналоги хаскелевских полиморфных функций типа fmap, sequence, join и т.д. Еще нужно что-то придумать для циклов. В хаскеле этого уже нет, но зато есть в F#.

Это все собираюсь использовать для симуляции моделей системной динамики. Обнаружил, что динамический процесс может быть определен как вариация монады Reader. Что важно, это позволяет задавать задачи моделирования декларативно, т.е. на высоком уровне абстракции. Я уже написал такую библиотеку на F#, но меня не устраивает ее скорость – слишком много накладных расходов, связанных с монадами. Надеюсь, что лисповская реализация на основе придуманных мною монадических макросов будет быстрее, во многом благодаря особой технике генерации кода для монады Reader. Там получается, что FUNCALL и LAMBDA чередуются друг с другом, то есть их можно сократить, но об этом написано уже у меня в документации к пакету cl-monad-macros.

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

2009-12-02T20:31:00.000+03:00

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

Другим мотивом послужило повышение внимания к теме Хаскеля со стороны некоторых программистов [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#. Это – совершенно другой язык смешанного типа с энергичной стратегией вычислений. Но наиболее красиво и целостно это все выглядит именно в Хаскеле.