Дизайн и архитектура в ФП. Часть 3
Свойства и законы. Сценарии. Inversion of Control в Haskell.Совсем немного теории В прошлой части мы убедились, что очень легко запутаться в плохо спроектированном коде. К счастью, с древних времен нам известен принцип «разделяй и властвуй», — он широко применяется при построении архитектуры и дизайна больших систем. Мы знаем разные воплощения этого принципа, как-то: разделение на компоненты, уменьшение зависимости между модулями, интерфейсы взаимодействия, абстрагирование от деталей, выделение специфических языков. Это хорошо работает для императивных языков, и надо полагать, что будет работать в функциональных, за тем исключением, что средства реализации будут другими. Какими же? Рассмотрим принцип Inversion of Control (детальное описание этого принципа можно легко найти в сети, например, здесь и здесь). Он помогает уменьшить связанность между частями программы путем инверсии потока выполнения. Буквально это значит, что мы внедряем в иное место свой код, чтобы там его когда-нибудь вызвали; при этом внедренный код рассматривается как черный ящик с абстрактным интерфейсом. Покажем, что в любом функциональном коде сочетаются оба признака IoC — «внедрение кода» и «черный ящик», для этого рассмотрим простой пример: progression op = iterate (`op` 2) 1 geometricProgression, arithmeticalProgression :: Integer → [Integer]geometricProgression = progression (*)arithmeticalProgression = progression (+) geometricals, arithmeticals :: [Integer]geometricals = take10 $ geometricProgression 1arithmeticals = take10 $ 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 = Inttype 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.hsplasmaFabric :: Player → Point → FabricplasmaFabric pl p = makeObject $ do energyCost .= 1 scheme .= plasma pl p producing .= True placementAlg .= placeToNearestEmptyCell karyon :: Player → Point → Objectkaryon 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 () → amakeObject = 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 $ nnamedValidator 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 ObjectcreateProduct 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 StringproducingScenario = 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) restype 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) _nameddurability = property (key durabilityA) _durabilitybattery = 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 IntconstantId = return 42
Создаем клиентский код в монаде State:nextId :: Int → State Context IntnextId prevId = do let nId = prevId + 1 modify (\ctx → ctx { ctxNextId = nextId nId }) return nId
Запускаем клиентский код, внедряя конкретный экземпляр внешнего состояния:client = do externalId <- get >>= ctxNextId doStuff externalId return externalId
Полный пример: gistВывод программы-примера: Sequental ids:print $ evalState client (Context constantId)print $ evalState client (Context (nextId 0))
[(1, «GNVOERK»),(2, «RIKTIG YOGLA»)]Random ids:[(59, «GNVOERK»),(64, «RIKTIG YOGLA»)]
Модульная абстракция (Module Abstraction)Чем является: Черный ящик.Для чего используется: Выбирать реализацию алгоритма в рантайме.Описание: Есть модуль-фасад, в котором подключены несколько модулей, реализующих одну и ту же функцию. По определенному алгоритму в функции-переключателе фасадного модуля выбирается та или иная реализация. В клиентском коде подключается фасадный модуль, и через функцию-переключатель используется нужный алгоритм.Полный пример: gist
