В прошлой главе мы перенесли A* на F#, после чего в образовательных целях занялись выдёргиванием его «кишок» наружу. Тогда процесс «потрошения» не был завершён до конца, но сегодня мы его добьём. Что касается метагейма, то мы продолжим путь от функции к конструктору и даже успеем слегка залезть на «ту сторону».

Кортежная форма

Последний раз мы закончили на том, что создали оболочку вокруг анонимного рекорда, но надо подчеркнуть, что жёсткой привязки именно к анонимным рекордам нет. Ядро может быть любым. Мы можем положить туда список анонимных рекордов, тупо слишком сложный в описании Result<_,_> или даже кортеж, который можно будет сразу разбить и выставить в качестве полноценных полей:

type PathFound (path, costSoFar, cameFrom, frontier) =
    member this.Path = path
    member this.CostSoFar = costSoFar
    member this.CameFrom = cameFrom
    member this.Frontier = frontier
    
let tryFindPath ... =
    ...
    Ok ^ PathFound(
        List.ofSeq path
        , costSoFar.AsReadOnly()
        , cameFrom.AsReadOnly()
        , List.ofSeq ^ frontier.AsSeq()
    )

Кортежная форма выглядит не так экзотично, но в подведомственных проектах мы ею почти не пользуемся, так как для несформировавшихся или пластичных типов она слишком муторная. В ней надо следить за количеством аргументов, их порядком и соответствием имён. В то время как компилятор умеет жаловаться только на неверное число элементов в кортеже и лишь на очень примитивном уровне: «мне надо 4, а ты сунул 5».

Кроме того, кортежная форма фактически вынуждает нас ссылаться на неё внутри tryFindPath, иначе наружу придётся возвращать кортеж, и тогда проблемы деконструкции станут проблемами всех пользователей функции. То есть вместо fun p -> p.Path надо будет писать (и как-то поддерживать) fun (path, _, _, _) -> path. У анонимного рекорда и оболочки таких проблем нет. Но я предпочитаю именно анонимный рекорд, потому что с большой долей вероятности этот набор данных будет расширен контекстом, характерным для конкретной сцены, а анонимный рекорд дополнить значительно проще, чем оболочку. Последнюю надо будет либо хитро наследовать:

type EspecialPathFound (ordinaryPathFound : PathFinder.PathFound, extraData) =
    inherit PathFinder.PathFound(
        ordinaryPathFound.Path
        , ordinaryPathFound.CostSoFar
        , ordinaryPathFound.CameFrom
        , ordinaryPathFound.Frontier
    )

    member _.ExtraData = extraData

let tryFindPath ... =
    PathFinder.tryFindPath ...
    |> Result.map ^ fun p -> EspecialPathFound(p, extraData)

Либо тупо перекладывать в другую оболочку:

type EspecialPathFound (ordinaryPathFound, extraData) =
    member _.Ordinary = ordinaryPathFound
    member _.ExtraData = extraData

let tryFindPath ... =
    PathFinder.tryFindPath ...
    |> Result.map ^ fun p -> EspecialPathFound(p, extraData)

Желательно обходиться без этого проброса, но если он необходим, то я предпочитаю проекцию (т. е. второй вариант), так как редко вижу здесь семантику наследования. По тестовым прогонам я знаю, что у некоторых возникает желание оспорить этот «акт выборочной слепоты», но позволю себе отложить обсуждение этой темы на далёкое будущее, так как по большому счёту мне без разницы. Мы ничего не теряем от «лишнего» наследования.

module ChaosChampion

module ForecastMaker =
    type OverkillData (kill, chainOpportunity) =
        member _.AsKill = kill // : ForecastMaker.Kill
        member _.ChainOpportunity = chainOpportunity

    type Forecast =
        | Damage of ForecastMaker.DamageData
        | Kill of ForecastMaker.KillData
        | Overkill of OverkillData

    let forecast ... : Forecast =
        match ForecastMaker.forecast ... with
        | ForecastMaker.Kill kill when ... ->
            ...
            Overkill ^ OverkillData(kill, {| ... })
        | ForecastMaker.Kill kill -> Kill kill
        | ForecastMaker.Damage damage -> Damage damage

Связь с оболочкой

Если хочется избавиться от Core в пользовательском коде, то можно настроить маппинг свойств оболочки на свойства ядра:

type PathFound with
    member this.Path = this.Core.Path
    member this.CostSoFar = this.Core.CostSoFar
    member this.CameFrom = this.Core.CameFrom
    member this.Frontier = this.Core.Frontier

С той же целью можно зашадовить оболочку ядром, тогда необходимость упоминать Core также отпадёт:

let path = path.Core

Но в этом случае мы теряем доступ ко всем свойствам и методам за пределами ядра. Кроме того, из-за своей невыразимости, ядро неудобно перемещать по системе сообщений ECS. Если одновременно нужны и краткость, и доступ, то можно инвертировать зависимость, зашадовив оболочку модифицированным рекордом:

let path = {| path.Core with Shell = path |}

Таким образом, мы получаем непосредственный доступ к данным и при этом сохраняем ссылку на оболочку в Shell.

Этот же способ применяется в ситуациях, когда мы строим новый рекорд на основе старого. Например, для анимации передвижения космического корабля в принципе достаточно простого let mutable motionSrc : Vector2I list. Когда сумма delta превысит время шага, этот список можно будет проматчить и передвинуть корабль в следующую точку:

match motion with
| [] ->
    ()
| next :: remain ->
    spaceship.LookToward next
    spaceship.Position <- next
    motion <- remain

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

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

// По ПКМ.
motionSrc <- Some {| 
    path.Core with
        Shell = path
        Remain = path.Core.Path
|}

Тогда шаг будет выглядеть так:

match motion.Remain with
| [] ->
    motionSrc <- None
| next :: remain ->
    spaceship.LookToward next
    spaceship.Position <- next
    motionSrc <- Some {| motion with Remain = remain |}

А рисование маски будет зависеть от наличия motionSrc:

seq {
    match motionSrc, path with
    | Some motion, _ ->
        for step in motion.Path do
            Colors.DarkOrange, step
    | _, Some path ->
        for step in path.Core.Path do
            Colors.Orange, step
        Colors.OrangeRed, cellUnderMouse
    | _ -> 
        Colors.DarkRed, cellUnderMouse
}
|> Seq.iter ^ fun (color, cell) ->
    mainGrid.Cell.Fill gridSurface color cell

Запечатанная оболочка

Если добавлять Shell приходится слишком часто, то расширенную версию можно подготовить заранее. В самом простом случае можно докинуть расширение типа:

type PathFound with
    member this.CoreWithShell = {| this.Core with Shell = this |}

Но в идеале хочется обходиться без дублирования. Shell должен быть в Core изначально. Проблема в том, что нельзя сразу создать модифицированный Core:

// Невалидный код.
type PathFound (core) =
    member this.Core = {| core with Shell = this |}

Компилятор разрешает {| core with .. |}, только когда уверен, что core является конкретным рекордом в момент «вызова». Функцию ниже (и позже) он не учитывает, так что контекстный вывод отваливается. Однако нам не надо возвращаться к явным типизациям, если мы можем поднять функцию выше определения Core:

type PathFound (core) =
    static member TryCreate ... =
        PathFinder.tryFindPath ...
        |> Result.map PathFound

    member this.Core = {| core with Shell = this |}

Итоговое расположение (ну или нейминг) PathFound.TryCreate выглядит необычно, но для столь утилитарных типов он не имеет принципиального значения. Особенно с учётом того, что вместо завёрнутого PathFound можно сразу вернуть развёрнутое ядро:

static member TryCreate ... =
    PathFinder.tryFindPath ...
    |> Result.map ^ fun p -> PathFound(p).Core

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

path.Core.Shell.Core.Shell

Правда, есть один нюанс. Shell в этой цепочке один и тот же (буквально), а вот Core при каждом вызове создаётся новый, так как это лишь фабрика, которая выглядит как свойство. На производительности это не скажется, однако ссылочную эквивалентность мы потеряем. При этом «обычная» эквивалентность останется и будет зависеть от содержимого анонимного рекорда. Надо полагать, что в большинстве случаев этого более чем достаточно, но даже в исключительных ситуациях от этого нюанса можно избавиться.

В F# за автоматические свойства отвечает val:

static member TryCreate ... =
    PathFinder.tryFindPath ...
    |> Result.map PathFound

member val Core = {| core with Shell = this |}

Однако ХМ анализирует val-ы отдельным треком, который хронологически расположен до других member-ов. Таким образом, TryCreate включается в процесс вывода типов слишком поздно (после val), и компилятор опять не распознаёт core как рекорд.

Мы уже размещали функции в свойствах, когда прокидывали фабрики нод из C# в F#. Если сделаем это снова, то проблема с идентификацией core решится:

static member val TryCreate = fun gridSize isObstacle start goal ->
    PathFinder.tryFindPath gridSize isObstacle start goal
    |> Result.map PathFound

member val Core = {| core with Shell = this |}

Но возникнут две другие:

1. fun не сохраняют имена параметров, так что снаружи нельзя понять, какая из двух точек start, а какая goal;

2. Компилятор начнёт жаловаться на то, что он не знает никаких this в Shell = this.

С первым пунктом мы можем разобраться имеющимися средствами. Достаточно спрятать свойство за (почти) одноимённым методом:

static member val private tryCreate = fun gridSize isObstacle start goal ->
    PathFinder.tryFindPath gridSize isObstacle start goal
    |> Result.map PathFound

static member TryCreate gridSize isObstacle start goal =
    // NB: Вызов статических членов требует упоминания класса.
    PathFound.tryCreate gridSize isObstacle start goal

Если вам кажется, что этот код выглядит странно, то вам не кажется. К сожалению, радикально улучшить его невозможно. Нам в любом случае потребуется приватная функция поближе к конструктору, так что перекладывание аргументов останется. Но мы сможем снизить эффект неожиданности, если избавимся хотя бы от fun:

type PathFound (core) =
    static let tryCreate gridSize isObstacle start goal =
        PathFinder.tryFindPath gridSize isObstacle start goal
        |> Result.map PathFound

    static member TryCreate gridSize isObstacle start goal =
        // NB: Вызов статической привязки не требует упоминания класса.
        tryCreate gridSize isObstacle start goal

tryCreate — это приватный статический метод, который:

• Ощущается как полноценная функция;

• Определён выше/раньше всех остальных member-ов и val-ов;

• Видим всем внутри класса.

Набор из привязок static let можно воспринимать как необъявленный модуль внутри PathFound. Но если вдаваться в технические детали, то следует знать, что все привязки, объявленные через static let, относятся к секции статического конструктора PathFound. Они принудительно приватны и будут «вычислены» только один раз при первом обращении к типу. Зная об этом, F# требует определять static let до всех остальных членов класса. С некоторой долей сомнения предположу, что было бы здорово, если бы в отношении member val были предприняты аналогичные ограничения, но пока что довольствуюсь аналогичной по смыслу конвенцией.

Привязка this

Даже после перехода на static let компилятор будет жаловаться на отсутствие this в автосвойстве:

member val Core = {| core with Shell = this |}

Дело в том, что в F# нет такого ключевого слова. Когда мы пишем this в member this.Core, то мы буквально говорим: let this = <ссылка на объект, который содержит member Core>. Из этого следует, что:

1. Вместо this можно взять любое другое валидное имя.

2. Если ссылка на самого себя не нужна, то её можно не брать (member _.Core), и ваши коллеги скажут вам «спасибо» за подчёркивание этого факта.

3. Если ссылка на самого себя нужна, то её надо где-то добыть.

Относительно большинства языков фича выглядит как нечто, свалившееся с неба. Возникла она из-за того, что в F# возможна ситуация, когда в одном скоупе сосуществуют две и более ссылок «на самого себя» от разных объектов, и при этом на них надо корректно ссылаться. Как такое могло произойти и почему это круто, мы будем разбирать через пару глав. Сейчас достаточно знать, что this в val это не право, а привилегия не норма, а аномалия. На неё надо реагировать явным образом через добавление as this в определение типа:

type PathFound (core) as this =
    static let tryCreate ... =
        PathFinder.tryFindPath ...
        |> Result.map PathFound
        
    member val Core = {| core with Shell = this |}

После этого на this можно будет ссылаться во всех member-ах экземпляра, в том числе в member _.Core. За последнее вас будут бить (люди, не компилятор), но ошибиться ненароком тут сложно, так как IDE раскрашивает такой this иначе. Например, в VS его цвет совпадает с цветом мутабельной переменной. Это не значит, что this можно присвоить новое значение. Просто надо проснуться и сконцентрироваться, так как нарушена привычная линейность повествования, и она может выйти нам боком.

За аналогией обратимся к Godot, в котором фактическая инициализация ноды завязана на метод (реже сигнал) _Ready, а не на конструктор объекта. Причина проста: в фазе конструктора нода пребывает в великом ничто, поэтому большая часть окружения ещё не существует. Вызов GetParent() в конструкторе вернёт null, а в _Ready реальную ноду. Оба варианта корректны, просто вызов в конструкторе происходит несвоевременно.

С this в конструкторе та же проблема. Инициализация одного member val может дёрнуть другой member val, который ещё не был инициализирован:

type A () as this =
    member val B = this.C
    member val C = 42

В теории B мог бы принять значение Unchecked.defaultof, что было бы катастрофическим поведением с нулевым шансом к исправлению в рантайме из-за иммутабельности обоих свойств. В действительности же мы получим исключение:

> A();;
> System.InvalidOperationException: Инициализация объекта или значения привела к рекурсивному вызову объекта или значения перед его полной инициализацией.

Компилятор проведёт большую работу под капотом as this. Он скрытно введёт флаг состояния mutable init = false, который будет меняться на true в самом конце конструктора. Этот флаг будет управлять входным фильтром в самом начале всех member-ов, определённых в классе. Поведение предков не изменится, так как к этому моменту их конструкторы уже завершены:

if not init then
    invalidOp "Инициализация объекта или значения привела к рекурсивному вызову объекта или значения перед его полной инициализацией."

Как видно, в этом вопросе компилятору плевать на порядок определения B и C, так что именно для обхода исключения вертеть свойствами бесполезно. Вызывать member-ы класса до завершения конструктора нельзя. Если очень хочется, то надо использовать первичный конструктор. Что это за зверь, мы поговорим в другой главе, ибо он большой и сильно отличается от той поделки, что была реализована в C#. Сейчас же я буду вынужден прокомментировать многократно озвученное предложение: «Компилятор должен проанализировать цепочку вызовов и разрулить ситуацию самостоятельно на этапе компиляции, ну или хотя бы не допускать компиляцию перекрёстных вызовов вообще.»

Я не могу доказать, но думаю, что это технологически невозможно. Тотальный фильтр неизбежно создаст ситуацию, когда анализ упрётся в цепочку запечённых вызовов и ветвлений. Например, здесь D содержит вызовы B и C, но seq ленив, так что определение D нельзя запрещать:

member val D = seq {
    this.B
    this.C
}

Кому кажется, что seq тоже можно проанализировать, напомню, что в F# можно писать собственные билдеры, ленивость которых зависит от их авторов и внешних факторов. Для Hopac архетипична ситуация, когда асинхронные «методы» мемоизируют, если их многократный вызов недопустим или лишён смысла. В результате получается объект типа Promise, который является job-ой с состоянием, поэтому его необходимо хранить, а не создавать на лету:

member val Die = memo ^ job {
    do! this.CloseDialog()
    ...
}

С синтаксической точки зрения memo ^ job { ... } мало чем отличается от run ^ job { ... }, но первый пример ленив, а второй жаден и поэтому выстрелит в рантайме. Доступ анализатора к исходникам тоже мало что даст, так как в Hopac есть стадия инициализации планировщика, которая зависят от окружения, и в которой используются лямбды. Получается, что абсолютное решение невозможно, а частичное я предпочту держать во внешних тулах, ибо на практике мне вполне достаточно того, что:

• IDE подсвечивает «опасный» this;

• Компилятор страхует некорректный вызов в рантайме;

• Разработчик контролирует вызовы на верхнем уровне.

Передача поведения

В последний раз наш A* выглядел так:

let tryFindPath mapSize isObstacle start goal =
    if not ^ inMap mapSize goal then Result.Error OutOfBounds
    elif isObstacle goal then Result.Error Obstacle else
    let frontier = PriorityStack.singleton 0 start
    let cameFrom = Dictionary.singleton start start
    let costSoFar = Dictionary.singleton start 0

    let rec tryFind () =
        match frontier.TryTake () with
        | None -> Result.Error Unreachable
        | Some (Eq goal) ->
            let path = Stack()
            path.Push goal
            let rec buildPath current =
                if current <> start then
                    let current = cameFrom.[current]
                    path.Push current
                    buildPath current
            buildPath goal
            Ok {|
                Path = List.ofSeq path
                Cost = costSoFar.[goal]
                Start = start
                Goal = goal
                CostSoFar = costSoFar.AsReadOnly()
                CameFrom = cameFrom.AsReadOnly()
                Frontier = List.ofSeq ^ frontier.AsSeq()
            |}
        | Some current ->
            let newCost = costSoFar.[current] + 1
            for next in neighbours mapSize isObstacle current do
                match costSoFar.TryGetValue next with
                | true, oldCost when newCost >= oldCost -> ()
                | _ ->
                    costSoFar.[next] <- newCost
                    frontier.Put (newCost + heuristic goal next) next
                    cameFrom.[next] <- current
            tryFind ()
    tryFind ()

Рассмотрим синтетическую ситуацию, когда нам надо построить путь к другой точке на основе того же результата (т. е. без перезапуска алгоритма). Такой запрос будет некорректным, так как некоторые точки вовсе не попали в обработку, а те, что попали, могли быть обработаны не до конца (подробнее поговорим в следующей главе). Но сейчас нам важно не это, а то, что функция построения пути buildPath находится где-то в недрах алгоритма и прибита гвоздями к cameFrom, start и path. Если она нужна нам в PathFound, то согласно мнению в интернетах, её надо либо дублировать, либо выносить в модуль и делать «чистой».

Оба варианта меня не устраивают своей вербозностью. В качестве моментального решения они неприменимы. В действительности зависимость от cameFrom и start не так уж плоха, так как точка старта у нас фиксирована, и она однозначно обусловливает граф переходов. А вот path у нас одноразовый, так что его придётся создавать при каждом вызове:

| Some current when current = goal ->
    let buildPath goal =
        let path = Stack()
        path.Push goal
        let rec buildPath current =
            if current <> start then
                let current = cameFrom.[current]
                path.Push current
                buildPath current
        buildPath goal
        List.ofSeq path

buildPath сначала построит «главный путь», а потом будет передан наружу:

Ok {|
    Path = buildPath goal
    BuildPath = buildPath // Vector2I -> Vector2I list
    ...
|}

Дальше в PathFound можно объяснить, что в функцию передаётся именно альтернативный goal:

member this.BuildPath target = this.Core.BuildPath target

member this.TryBuildPath target =
    if this.Core.CameFrom.HasKey target
    then Some ^ this.BuildPath target
    else None

Этим примером я хотел обратить внимание на то, что мы можем возвращать не только данные, но и функции над конкретно этими данными. То есть речь идёт о «поведении», которое мы привыкли ассоциировать с типами, а не с аморфной кучкой значений. Более того, это поведение поддаётся переопределению, что можно трактовать как подобие наследования:

{| core with
    BuildPath =
        if core.CameFrom.HasKey target
        then this.BuildPath target
        else []
|}

Эту мысль надо переварить и усвоить, ибо она означает, что в великом ничто можно произвольно выбрать несколько точек, назвать их объектом, назначить им какой-то набор «методов» и жить с этим столько сколько нужно, вообще не беспокоясь об институционализированных структурах. А когда с ходом времени набор доступных точек поменяется, мы сможем повторить эту процедуру ещё раз, так как наши возможности формировать новые скопления останутся в силе. Таким образом, мы всегда сможем очень близко моделировать действительность.

Промежуточное заключение

Мы зачистили почти всё пространство на подступах к конструктору. Есть ещё несколько интересных моментов, касающихся асинхронного развёртывания, но это слишком сильный и объёмный вбоквел. Им я займусь когда-нибудь потом. Сейчас же для нас главное то, что мы можем переварить вероятностное развёртывание любой сложности, максимально эксплуатируя автоматический вывод типов.

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

На всякий случай уточню, что, говоря «легко», я не имею в виду решение только через оболочки. Они часто обходятся дешевле, чем определение полноценных типов «с нуля», но это всё-таки нишевое решение на стыке обычной функции и общего пространства типов, поэтому на библиотечном уровне они почти не используются. В этом плане концепция оболочек похожа на homo erectus. Вы можете легко разместить его в эволюционной цепи гоминидов, но попутно придёте к тому же выводу — на больших дистанциях мускулистый примат проигрывает вооружённому. В общем, мы имеем очередную вилку, когда каждое из решений имеет свои плюсы и свои минусы. И лучший игрок тот, кто умеет переключаться между ними с максимальной выгодой для дела.

В следующей главе мы сделаем небольшую паузу в изучении языковых фич и вместо этого сосредоточимся на иммутабельных структурах данных на примере расширенного A*.

НЛО прилетело и оставило здесь промокод для читателей нашего блога:
-15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.