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

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

Создал два очень разных движка: 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#

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

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

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

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

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

Aivika версии 2.0.12.0

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

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

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

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

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

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

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

Сегодня осознал одну замечательную вещь. Оказывается, что в 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# с помощью комбинаторов

Возникла задача разбора потока данных 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. В общем, нет в мире совершенства!