Дизайн и архитектура в ФП. Часть 3

Свойства и законы. Сценарии. Inversion of Control в Haskell.

Совсем немного теории

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

Рассмотрим принцип Inversion of Control (детальное описание этого принципа можно легко найти в сети, например, здесь и здесь). Он помогает уменьшить связанность между частями программы путем инверсии потока выполнения. Буквально это значит, что мы внедряем в иное место свой код, чтобы там его когда-нибудь вызвали; при этом внедренный код рассматривается как черный ящик с абстрактным интерфейсом. Покажем, что в любом функциональном коде сочетаются оба признака IoC — “внедрение кода” и “черный ящик”, для этого рассмотрим простой пример:

progression op = iterate (`op` 2) 
 
geometricProgression, arithmeticalProgression :: Integer -> [Integer]
geometricProgression = progression (*)
arithmeticalProgression = progression (+)
 
geometricals, arithmeticals :: [Integer]
geometricals = take 10 $ geometricProgression 1
arithmeticals = take 10 $ arithmeticalProgression 1

Здесь на вход одним функциям (iterate, progression) передаются другие функции ((*), (+), `op` 2), то есть, внедряется какой-то код. И внутри принимающих функций этот код рассматривается как черный ящик, для которого известен лишь тип. В случае iterate, например, второй аргумент должен быть типа Integer -> Integer, и неважно, насколько сложным будет его устройство. Таким образом, инверсия управления лежит в основе функционального программирования; в теории, функции высших порядков позволяют построить сколь угодно большое приложение. Есть только одна проблема: подобное толкование IoC слишком наивное, и это ведет, конечно же, к наивному коду. Уже в приведенном выше примере видно, что код представляет собой монолитную пирамиду, а в реальном приложении она бы разрослась до гигантских размеров и стала бы абсолютно неподдерживаемой.

Посмотрим на IoC с другой стороны, — то есть, со стороны “гостеприимного” клиентского кода. В нем мы получаем какой-то внешний артефакт, служащий определенной цели. Снаружи данный артефакт может быть подменен другим, но для принимающей стороны подмена должна быть незаметной. Это так называемый принцип подстановки Лисков. Он служит ориентиром в ООП-мире и предписывает, чтобы у артефактов было предсказуемое поведение. “Предписывает”, а не “гарантирует”, поскольку в ООП-языках такой гарантии дать нельзя, — в любом артефакте может внезапно появиться любой побочный эффект, который и нарушит принцип. Применим ли этот принцип в функциональных языках? Да, конечно. Более того, при условии, что код чистый, мы получим более сильные гарантии, — особенно если язык со строгой статической типизацией.

В конце статьи приводится краткое описание разных реализаций Inversion of Control на языке Haskell. Некоторые шаблоны являются практически полными аналогами таковых в императивном мире (например, монадическая инъекция состояния есть Dependency Injection), а какие-то лишь в незначительной степени напоминают IoC. Но все они в равной степени полезны для хорошего дизайна.

Много практики

Настало время писать хороший код. В этой статье мы продолжим изучать дизайн игры “The Amoeba World”, — целую его эпоху, очерченную этим и этим коммитами. Эпоха была насыщенная. Кроме полностью переписанной игровой логики, были испробованы такие инструменты как линзы, введено тестирование с помощью QuickCheck, придуман язык сценариев, написан его интерпретатор, интегрирован A* — алгоритм поиска по графу мира, и найден еще один специфический антипаттерн, который и положил конец этой эпохе. В этой статье наш разговор коснется только свойств и сценариев, все остальное оставим для следующих частей.

Свойства и объекты

Из прошлого опыта стало ясно, чем объекты являются на самом деле, из чего они состоят. Главная идея, заложенная в этот дизайн, такова: объект — это сущность, составленная из некоторых свойств. Объекты “Karyon”, “Plasma”, “Border” и другие были расчленены, и получен такой набор свойств:

• Уникальный идентификатор
• Название
• Прочность (максимум и текущее количество HP)
• Владелец (игрок)
• Слой (подземелье, земля, небо)
• Расположение (на карте)
• Возраст (максимум и текущий возраст)
• Батарейка (максимум и текущее количество энергии)
• Запрет движения (по определенному слою в этой ячейке)
• Направление
• Движение
• Фабрика (возможность создавать другие объекты)
• Самоуничтожение
• Коллизии (с другими объектами)

Дотошный читатель может увидеть здесь несовершенство, например, почему-то “слой” и “расположение” разделены на два свойства, хотя вроде бы они про одно и то же. И что за свойство такое “коллизии”? А “Фабрика”? А “Возраст” и “Самоуничтожение”? И зачем каждому объекту строковое название, которое будет пожирать память? Претензии обоснованные, — и уже в следующей эпохе список был еще раз пересмотрен, причем тем же способом: выделением свойств у свойств. В итоге осталось только шесть, самых важных, “рантаймовых” и “статических”, а остальные логичным образом превратились во внешние эффекты и действия…

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

Ядро:
    Имя = “Karyon”
    Расположение = (1, 1, 1)
    Слой = Земля
    Владелец = Игрок1
    Прочность = 100 / 100
    Батарейка = 300 / 2000
    Фабрика = Плазма, Игрок1
 
Плазма:
    Имя = “Plasma”
    Расположение = (2, 1, 1)
    Слой = Земля
    Владелец = Игрок1
    Прочность = 30 / 40

Так как свойств конечное число, решено было сделать для каждого тип-обертку и разместить их всех под одним алгебраическим типом (код):

-- Object.hs:
data Property = PNamed Named
              | PDurability (Resource Durability)
              | PBattery (Resource Energy)
              | POwnership Player
              | PLayer Layer
              ...
  deriving (Show, Read, Eq)

Определим тип абстрактного объекта:

-- Object.hs:
type PropertyKey = Int
type PropertyMap = M.Map PropertyKey Property
 
data Object = Object { propertyMap :: PropertyMap }
  deriving (Show, Read, Eq)

Первая мысль, которая напрашивается при виде Property, — что мы вернулись к тому, с чего начинали, то есть, к проблеме God ADT (в тот момент это был тип Item). Однако это не так. Существенное различие — в уровне абстракции, который предоставляет нам тип Object. У нас появилось то, что можно назвать “комбинаторной свободой”: небольшое количество свойств дает комбинаторный взрыв возможностей по компоновке новых объектов. Каких-то иных свойств не планируется, — а если таковые и появятся, изменения не будут распространяться по коду, словно волна по доминошкам. Мы убедимся в этом, когда поговорим о сценариях, а пока зададимся вопросом: как же создавать эти самые конкретные объекты?

Самый простой способ — заполнить список свойств и преобразовать его в Data.Map:

-- Objects.hs:
import Object
 
karyon = Object $ M.fromList [ (1, PObjectId 1)
 , (4, PNamed “Karyon”)
 , (2, PDurability (Resource 100 100))
 , (3, PBattery (Resource 300 2000))
 , (10, POwnership Player1)
 , (5, PDislocation (Point 1 1 1))
 , ...]

… но стоп! По какой такой логике мы прописываем PObjectId, Dislocation и Ownership? Ведь о них имеет смысл говорить только для объектов, находящихся на карте! С другой стороны, есть свойства общие, которые задают класс объектов и потом не изменяются: PNamed и PLayer, PFabric и PPassRestriction (запрет движения). У Karyon слой может быть только Ground, а свойство PNamed “Plasma” может принадлежать, соответственно, только плазме. Здесь мы сталкиваемся с проблемой, что объекты должны создаваться при непосредственном помещении на карту, и при этом нужно иметь шаблоны с первоначальными данными. В качестве шаблонов подойдут так называемые “умные конструкторы” — функции, которые будут создавать нам готовый объект по готовым лекалам и небольшому набору входных параметров. Вот как выглядит более умная функция karyon:

-- Objects.hs:
import Object
 
karyon pId player point = Object $ M.fromList [ (1, PObjectId pId)
 , (4, PNamed “Karyon”)
 , (2, PDurability (Resource 100 100))
 , (3, PBattery (Resource 300 2000))
 , (10, POwnership player)
 , (5, PDislocation point)
 , ...]

Данный синтаксис трудно назвать изящным, слишком много “шума” и телодвижений. Haskell — лаконичный язык, и мы должны стремиться к простоте и функциональному минимализму, тогда код будет красивее, понятнее и удобнее. Ах, как бы было хорошо, если бы словесное описание шаблона, представленное несколькими абзацами выше, можно было перенести в код… Нет ничего невозможного!

-- Objects.hs
plasmaFabric :: Player -> Point -> Fabric
plasmaFabric pl p = makeObject $ do
    energyCost   .= 1
    scheme       .= plasma pl p
    producing    .= True
    placementAlg .= placeToNearestEmptyCell
 
karyon :: Player -> Point -> Object
karyon pl p = makeObject $ do
    namedA       |= karyonName
    layerA       |= ground
    dislocationA |= p
    batteryA     |= (300, Just 2000)
    durabilityA  |= (100, Just 100)
    ownershipA   |= pl
    fabricA      |= plasmaFabric pl p

Понятность кода зависит от того, насколько знания и мышление читающего совпали со знаниями и мышлением автора. Понятен ли этот код? Ясно, что он делает, но как он работает? Что, например, здесь значат операторы “.=” и “|=”? Как работает функция makeObject? Почему у некоторых названий есть буква “A”, а у некоторых ее нет? И это что, монада, что ли?..

Туманный ответ на эти правильные вопросы звучит так: в этом коде используется внутренний язык по компоновке объектов. Его дизайн основан на применении линз совместно с монадой State. Функции с “A”-постфиксами — это умные конструкторы (“аксессоры”) самих свойств, знающие порядковый номер конкретного свойства и умеющие валидировать значения. Функции без “А” — это линзы. Оператор “.=” принадлежит библиотеке линз и позволяет внутри монады State задать значение, находящееся “под увеличением”. Функция plasmaFabric заполняет АТД Fabric, а функция karyon заполняет PropertyMap и Object. Во втором примере аксессоры и данные передаются в кастомный оператор |=, для корректности будем называть его “оператором заполнения”. Оператор заполнения работает внутри монады State. Он вытаскивает текущую PropertyMap и помещает в нее провалидированное аксессором свойство:

-- Object.hs:
makeObject :: Default a => State a () -> a
makeObject = flip execState def
 
data PAccessor a = PAccessor { key :: PropertyKey
                             , constr :: a -> Property }
 
-- Оператор заполнения свойств:
(|=) accessor v = do
    props <- get
    let oldPropMap = _propertyMap props
    let newPropMap = insertProperty (key accessor) (constr accessor v) oldPropMap
    put $ props { _propertyMap = newPropMap }
 
-- Аксессор для свойства Named:
isNamedValid (Named n) = not . null $ n
namedValidator n | isNamedValid n = n
                 | otherwise      = error $ "Invalid named property: " ++ show n
 
namedA = PAccessor 0 $ PNamed . namedValidator

Этот дизайн не идеален. Очень опасной выглядит валидация свойств, так как она может упасть с ошибкой в рантайме. Мы также не следим за тем, есть ли уже такое свойство в наборе, — просто записываем поверх него новое. И тот, и другой недостаток можно легко исправить, создав стек из монад Either и State, и обрабатывать исключительные ситуации безопасным образом. При этом код в модуле с шаблонами (Objects.hs) изменится незначительно. Плюсов много, но есть одно возражение: пока язык компоновки объектов используется лишь для создания шаблонов, и пока их можно протестировать, лишняя логика будет только мешаться. С другой стороны, когда этот код пойдет в сценарии, безопасность станет важной.

Наш последний вопрос, связанный с объектами, таков: как теперь выглядит тип данных World? Здесь особых изменений не произошло, мир по-прежнему является типом Map:

type World = M.Map Point Object

У структуры Data.Map страдает производительность. Более подходящим решением здесь видится двумерный массив; в Haskell существуют эффективные реализации векторов, такие как vector или repa. Когда станет ясно, что производительность игры недостаточно высокая, можно будет вернуться и пересмотреть хранилище мира, но пока скорость разработки важнее.

Сценарии

Сценарии — это законы мира. Сценарии описывают то или иное явление. Явления в мире локальные; в одном явлении участвуют только нужные свойства на определенном участке карты. Например, при взрыве бомбы нас интересует прочность объектов в радиусе N, — именно ее мы должны уменьшить на величину урона, и если прочность упала ниже 0, нужно убрать объекты с карты. Если же у нас работает фабрика, мы должны сначала обеспечить ее ресурсом, затем получить продукт и разместить его где-то неподалеку. Прочность не важна, но важны ресурсы, сама фабрика и пустое пространство под продукт.

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

Проиллюстрируем это примерами. Пусть у нас имеется две фабрики, которые производят по одному танку стоимостью в 1 единицу. В запасе у нас есть всего 1 единица ресурса. Первый сценарий отработает успешно, но второй должен узнать, что все ресурсы израсходованы, и прекратить работу. Или другая ситуация: два объекта движутся встречными курсами. Когда между ними остается одна клетка, что должно произойти? Столкновение или невозможность движения одного из объектов? Подобных нюансов может быть очень много; хотелось бы, чтобы сценарии были полными, но оставались предельно простыми для чтения и написания.

Очертим требования к подсистеме сценариев:

• надежность;
• ориентированность на свойства;
• последовательность;
• простота;
• сценарии могут фэйлиться;
• быстродействие;
• сценарии могут запускать другие сценарии;
• ...

В игре “The Amoeba World” был задизайнен язык Scenario DSL, и написан его интерпретатор (код). Вот как выглядит кусок сценария для свойства Fabric (код):

-- Scenario.hs:
createProduct :: Energy -> Object -> Eval Object
createProduct eCost sch = do
    pl <- read ownership
    d  <- read dislocation
    withdrawEnergy pl eCost
    return $ adjust sch [ownership .~ pl, dislocation .~ d]
 
placeProduct prod plAlg = do
    l   <- withDefault ground $ getProperty layer prod
    obj <- getActedObject
    p   <- evaluatePlacementAlg plAlg l obj
    save $ objectDislocation .~ p $ prod
 
produce f = do
    prodObj <- createProduct (f ^. energyCost) (f ^. scheme)
    placeProduct prodObj (f ^. placementAlg)
    return "Successfully produced."
 
producingScenario :: Eval String
producingScenario = do
    f <- read fabric
    if f ^. producing
        then produce f
        else return "Producing paused."

Во второй части цикла статей, а именно в разделе ‘let-функции’, мы видели код громоздкий и непонятный. Теперь же мы видим код легкий, по-прежнему непонятный, но в нем уже просматривается определенная система. Попробуем в ней разобраться.

Scenario DSL делится на две части: язык запросов к игровым данным и среда исполнения. В основе всего лежит тип Eval — стек из монад Either и State:

-- Evaluation.hs:
type EvalType ctx res = EitherT EvalError (State ctx) res
type Eval res = EvalType EvaluationContext res

Внутренняя монада State позволяет хранить и изменять контекст исполнения. Текущий мир, оперативные данные, рандом-генератор, — все это лежит в контексте:

data DataContext = DataContext { dataObjects :: Eval Objects
                               , dataObjectGraph :: Eval (NeighboursFunc -> ObjectGraph)
                               , dataObjectAt :: Point -> Eval (Maybe Object) }
 
data EvaluationContext = EvaluationContext { ctxData :: DataContext
                                           , ctxTransactionMap :: TransactionMap
                                           , ctxActedObject :: Maybe Object
                                           , ctxNextRndNum :: Eval Int }

Внешняя монада Either позволяет безопасным образом обрабатывать ошибки исполнения. Самая распространенная ситуация — когда происходят коллизии, и какой-то сценарий должен оборваться на середине работы. Чтобы состояние игры оставалось правильным, нужно откатить все его изменения, а если сценарий был вызван из другого сценария, — то и там следует как-то реагировать на проблему. Поэтому многие функции имеют тип Eval, который скрывает за собой монаду Either. Фактически, все функции с типом Eval являются сценариями. Даже функции интерпретатора (evalTransact, getTransactionObjects) и функции языка запросов (single, find) работают в этом типе и, по факту, тоже являются сценариями. Иными словами, язык Scenario DSL унифицирован типом Eval, что делает код консистентным и монадно-компонующимся.

Так как любая функция с типом Eval — это сценарий, то каждую из них можно запускать и тестировать. Интерпретация сценария — это всего лишь выполнение стека монад:

-- Evaluation.hs:
evaluate scenario = evalState (runEitherT scenario)
execute scenario = execState (runEitherT scenario)
run scenario = runState (runEitherT scenario)

Для игровых сценариев есть одна точка входа — обобщающая функция mainScenario:

-- Scenario.hs:
mainScenario :: Eval ()
mainScenario = do
    forProperty fabric producingScenario
    forProperty moving movingScenario
    return ()
 
-- Где-то в главном коде - один тик всей игры:
stepGame gameContext = runScenario mainScenario gameContext

Точно так же запускаются и отдельные сценарии, а значит, можно ввести модульное и функциональное тестирование кода. Вот, например, отладочный код из модуля ScenarioTest.hs, — при необходимости его можно трансформировать в полноценный тест QuickCheck или HUnit:

main = do
    let ctx = testContext $ initialGame 1
    let result = execute (placeProduct (plasma player1 point1) nearestEmptyCell) ctx
    print result

Теперь, когда мы познакомились с некоторыми особенностями среды исполнения Scenario DSL, препарируем следующую функцию:

withdrawEnergy pl cnt = do
    obj <- singleActual $ named `is` karyonName ~&~ ownership `is` pl ~&~ batteryCharge `suchThat` (>= cnt)
    batRes <- getProperty battery obj
    save $ batteryCharge .~ modifyResourceStock batRes cnt $ obj

Это тоже сценарий, служащий определенной цели: для игрока pl изъять из ядра энергию в количестве cnt. Что нужно сделать для этого? Прежде всего, найти на карте объект с такими свойствами: Named == “Karyon” и Ownership == pl. В коде выше мы видим вызов singleActual — эта функция ищет для нас объект по предикату. Благодаря языку запросов словесное описание почти точно переводится в код:

named `is` karyonName
~&~ ownership `is` pl
~&~ batteryCharge `suchThat` (>= cnt)

Нетрудно догадаться, что оператор (~&~) означает “И”, а оператор `is` задает равенство определенного свойства значению. Третье условие предиката выбирает только те объекты, для которых батарея заряжена достаточно, чтобы оттуда изъять еще энергии. Конечно же, энергия может кончиться, и тогда объект не будет найден, — в этом случае, начнется fail-ветка монады Either, и весь сценарий будет отменен. Но если энергию можно изъять, то изымаем и накапливаем изменения:

save $ batteryCharge .~ modifyResourceStock batRes cnt $ obj

Стоит упомянуть, что в Scenario DSL активно используются линзы, что весьма сокращает код. Например, вместо лаконичного (batteryCharge .~ 10) нам бы пришлось заниматься археологическими раскопками по цепочке: Object -> PropertyMap -> PBattery -> Resource -> изменить stock -> сохранить все обратно. Хоть идиоматичность линз вызывает сомнения, инструмент этот очень и очень полезный.

В языке запросов есть много полезных функций. Можно искать множество объектов по предикату (функция query), можно искать одиночный объект (функция single), а если таковых найдется много, — фэйлить сценарий. Также есть стратегии поиска: искать только старые данные, искать только новые, или все вместе, — и пусть клиентский код сам разбирается. В целом, Scenario DSL хорошо справлялся со своей функцией, и были возможности по его расширению. И была лишь одна серьезная проблема, по которой снова пришлось пересмотреть основу основ — дизайн типа Object. Имя этой проблеме…

Антипаттерн Lens + NoMonomorphismRestriction

Причина всех бед лежит в типе данных PropertyMap и в линзах для свойств:

property k l = propertyMap . at k . traverse . l
 
named            = property (key namedA)            _named
durability       = property (key durabilityA)       _durability
battery          = property (key batteryA)          _battery
...

Функция property во всех случаях возвращает разные линзы, что нельзя сделать при включенной проверке мономорфизма. Поэтому пришлось включить расширение языка NoMonomorphismRestriction. К сожалению, из-за этого вывод типов стал ломаться в самых неожиданных местах, и приходилось искать обходные пути. Хуже того: режим NoMonomorphismRestriction начал распространяться по коду. Он появлялся везде, где использовались линзы модуля Object.hs, и заражал безумием тайпчекер. В конце концов, дизайн Scenario DSL стал прогибаться под ограничениями тайпчекера, — что привело к нескольким не очень хорошим решениям.

Проблему можно искоренить, отказавшись от типа PropertyMap. Тогда в типе Object окажутся все свойства, — даже те, которые конкретному объекту не понадобятся. Возможно, есть и другие решения, но в следующей версии дизайна было сделано именно так:

data Object = Object {
                        -- Properties:
                         objectId :: ObjectId          -- static property
                       , objectType :: ObjectType      -- predefined property
 
                       -- Runtime properties, resources:
                       , ownership :: Player           -- runtime property... or can be effect!
 
                       , lifebound  :: IntResource    -- runtime property
                       , durability :: IntResource    -- runtime property
                       , energy     :: IntResource    -- runtime property
                       }

Нет худа без добра, — в результате пересмотра другие свойства превратились во внешние эффекты и действия. Дизайн стал более правильным, хотя и пришлось выбросить большую часть наработок по Scenario DSL…

Вместо заключения

Новый движок сценариев, предположительно, будет основан уже на иных принципах. В частности, планируется сделать не внутренний DSL, а внешний, — тогда сценарии можно будет писать в обычных текстовых файлах. На данный момент автор работает над слоями Application и View, над поиском оптимальной модели использования FRP. В следующих главах будет рассказано о том, какая идея стоит за FRP, и как с помощью реактивного программирования можно соединить разрозненные части большого приложения.

Реализации Inversion of Control в Haskell

Disclaimer: автор не успел закончить исследования для данного раздела. Продолжение будет в следующих статьях.

Монадическая инъекция состояния (Monadic state injection)

Чем является: Инъекция зависимости (Dependency Injection).
Для чего используется: Для абстрагированной работы с внешним состоянием в клиентском коде.
Описание: Внешнее состояние внедряется через монаду State как контекст. Клиентский код запускается в монаде State с этим контекстом. При обращении к контексту клиентский код получает данные из внешнего состояния.
Структура:

Определяем тип данных Context — он будет содержать внешнее состояние в виде монады State:

data Context = Context { ctxNextId :: State Context Int }

Определяем конкретные экземпляры внедряемого кода. Код может выдавать константный результат:

constantId :: State Context Int
constantId = return 42

Или же может выдавать разные результаты на каждый вызов:

nextId :: Int -> State Context Int
nextId prevId = do let nId = prevId + 1
                   modify (\ctx -> ctx { ctxNextId = nextId nId })
                   return nId

Создаем клиентский код в монаде State:

        client = do
            externalId <- get >>= ctxNextId
            doStuff externalId
            return externalId

Запускаем клиентский код, внедряя конкретный экземпляр внешнего состояния:

print $ evalState client (Context constantId)
print $ evalState client (Context (nextId 0))

Полный пример: gist
Вывод программы-примера:

Sequental ids:
[(1,"GNVOERK"),(2,"RIKTIG YOGLA")]
Random ids:
[(59,"GNVOERK"),(64,"RIKTIG YOGLA")]

Модульная абстракция (Module Abstraction)

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