Chaining Effects with Incremental Dependencies

[askvortsov1]

Hi! I'm working on a snake tutorial, and ran into a design challenge. I was wondering if you had any suggestions for a clean way to implement this in Bonsai.

The premise of my design is that I have 2 "lower-level" stateful computations:

• Player, which packages a Snake.t (glorified deque of (row,col) coords), direction, score, and status
• Apple, which packages a Apple.t (just a (row, col) record)

On every tick:

1. The snake moves
2. For every apple it eats, the score increases, and the snake's "left_to_grow" param is increased
3. Every eatten apple is respawned

Additionally, on game restart, every snake and apple is randomly placed on the game grid.

I've attempted several implementations, but none are as clean as I'd like.

Snakes Are in Charge

This is the current code at this commit.

Here, the Player's Move action takes the other elements on the board as parameters. For a game with 1 snake and 1 apple, heres the signature for Player actions:

module Action : sig
  type t =
    | Restart
    | Move of (Apple.t * (Apple.Action.t -> unit Effect.t))
    | Change_direction of Direction.t
end

and for Apple actions:

module Action = struct
  type t =
    | Spawn of Position.t list
    | Eatten of Position.t list
  [@@deriving sexp]
end

On a player's tick, if the snake has eatten the apple, it will use schedule_event to dispatch a Eatten action to the apple, with its current position as an argument.

This becomes messy fast when we add n snakes and m apples. Each player needs to receive all the snakes and apples (and their inject functions!). But because we need to use Effect.Many to combine all these actions into one effect on tick, the ith player could eat an apple causing it to respawn, but the i+1th player would still see the old position of the apple, and of the snakes that have already moved:

  (* Tick logic *)
  let%sub () =
    let%sub clock_effect =
      let%arr player1_inject = player1_inject
      and player2_inject = player2_inject
      and game_elements = game_elements in
      Effect.Many
        [ player1_inject (Move game_elements); player2_inject (Move game_elements) ]
    in
    Bonsai.Clock.every [%here] (Time_ns.Span.of_sec 0.25) clock_effect
  in

This means that the apple could spawn right under where the i+1th snake is about to move, but the i+1th snake would never know.
This also doesn't fix the issue of elements spawning on top of each other when the entire board is reset.

Apples Take The Reins (of their fate)

I tried to fix the generalized snake game in this commit. Essentially:

• A Game_element.t type represents all Snake.ts and Apple.ts in the game, and comes with a helper to get all occupied positions on the board. I had to separate Apple and Apple_state into separate files to avoid dependency cycles.
• A Game_element.t is computed incrementally from all Player_state.computations and Apple_state.computations.
• Apple_state now has a Tick action, which takes that Game_elements.t as input. Apples are responsible for checking if they have been eatten, and for respawning themselves. Players will still separately grow/increase score when they eat an apple.
• Player_state's Restart and Move actions take that Game_elements.t as input. That way, snakes will not spawn on an existing game element, and will be aware of everything on the board. Apple_state's Spawn and Tick actions do the same

My hope was that each snake would move, check for eatting itself/OOB, and then grow if it ate an apple. Then, all apples would respawn if eatten. Because everything takes Game_elements.t as input, and that Game_elements.t is computed incrementally, the apply_action function would always have an up-to-date view of the world.

Sadly, I can't figure out a way to do this with Bonsai's current API. If I want to dispatch multiple effects at once, I need to combine them with Effect.Many. But that means that all effects are calculated incrementally from Game_elements.t pre-tick, and will not update in response to previous events being evaluated.

I tried Bonsai.lazy_ to compute the effects, but that didn't seem to help. I might be using it incorrectly though.

Input It Out...

As an alternative to all this, we could instantiate computations of snakes and apples in a chain, with each element taking the positions of all previously instantiated elements as an input. That position input could then be used to control where apples/snakes couldn't spawn.

There's 2 big problems with this:

• I want to leave state machine inputs open for rows and cols, which could be controlled by a form. Having a 3-tuple of inputs would be messy.
• With this chain approach, the ith apple could never respawn on top of the i-1th apple. However, there's nothing stopping the i+1th apple from respawning on top of the ith apple. I suppose we could use this for full board resets and pass around Game_elements.t through actions for apple respawns in-game, but that feels confusing and messy.

Effect.many_value?

The cleanest solution that comes to my mind would be having some:

val many_value : Effect.t Value.t list -> Effect.t Value.t

that isn't just Value.all, but rather lazily evaluates each effect when its time to call it.
I'm not sure that this would be possible with how Value.t is currently implemented though.

I would also appreciate any suggestions if there's a cleaner / more idiomatic way of doing this. Thanks!

[TyOverby]

I don't have a good intuition for what the best way to solve your problem would be, but these functions might be useful:

1. wrap Wrap allows you to build a "coordinating" state machine that has access to the result of the computation that its coordinating. The interesting thing is that the coordinated components can communicate with - and see the model of - the coordinator.
2. actor* Actors can respond to actions by returning values, allowing them to communicate more naturally with other components.
3. with_inject_fixed_point This is actually just a small wrapper around wrap, but makes it easy to use an effect that is computed somewhere else.

[askvortsov1]

I think I've found the solution I was looking for (at least on v0.15, but I don't see why it shouldn't carry over)!

To simplify my excessively long initial post, I wanted to:

• Instantiate a bunch of Player_state and Apple_state computations
• Incrementally compute all active Snake.ts and Apple.ts from that
• Make the most up-to-date Snake.ts and Apple.ts available to every Player_state and Apple_state' when they:
  • Spawn
  • Tick

In particular, as each element spawns / ticks and changes its state, the worldview provided to all further spawns / ticks should be updated.

I could probably implement this with wrap. The coordinated components would be the individual Player/Apple computations, and the coordinator would be a Game_elements.t. The downside is that coordinated components would need to explicitly tell the coordinator when their state updates, so recalculating Game_elements.t would be an explicit update, instead of a declarative, equational derivation.

I don't think it's possible in Bonsai to sequentially execute a list of lazily evaluated unit Effect.t Value.ts. However, this case is helped greatly by the fact that the actions in question are all Move of Game_elements.t and Tick of Game_elements.t, or Restart of Game_elements.t and Spawn of Game_elements.t. I could separate the "chain effects" part, and the "incremental dependency" part. Here's what I came up with:

let chain_scheduler
  : type a. a Value.t -> ((a -> unit Ui_effect.t) list -> unit Ui_effect.t) Computation.t
  =
 fun input ->
  let module Action = struct
    type t = Run of (a -> unit Effect.t) list [@@deriving sexp]
  end
  in
  let apply_action ~inject ~schedule_event input _model (Action.Run effect_fns) =
    match effect_fns with
    | effect_fn :: dependents ->
      schedule_event (Effect.Many [ effect_fn input; inject (Action.Run dependents) ])
    | [] -> ()
  in
  let open Bonsai.Let_syntax in
  let%sub (), inject =
    Bonsai.state_machine1
      [%here]
      (module Unit)
      (module Action)
      ~default_model:()
      ~apply_action
      input
  in
  let%arr inject = inject in
  fun effects -> inject (Action.Run effects)
;;

Then, to use it:

let%sub player1, player1_inject = Player_state.computation ~rows ~cols ~color:"green" in
  let%sub player2, player2_inject = Player_state.computation ~rows ~cols ~color:"blue" in
  let%sub apple, apple_inject = Apple_state.computation ~rows ~cols in
  let%sub apple2, apple2_inject = Apple_state.computation ~rows ~cols in
  let%sub game_elements =
    let%arr player1 = player1
    and player2 = player2
    and apple = apple
    and apple2 = apple2 in
    { Game_elements.snakes = Player_state.Model.snakes [ player1; player2 ]
    ; apples = Apple_state.Model.apples [ apple; apple2 ]
    }
  in
  let%sub scheduler = chain_scheduler game_elements in
  (* Tick logic *)
  let%sub () =
    let%sub clock_effect =
      let%arr player1_inject = player1_inject
      and player2_inject = player2_inject
      and apple_inject = apple_inject
      and apple2_inject = apple2_inject
      and scheduler = scheduler in
      scheduler
        [ (fun g -> player1_inject (Move g))
        ; (fun g -> player2_inject (Move g))
        ; (fun g -> apple_inject (Tick g))
        ; (fun g -> apple2_inject (Tick g))
        ]
    in
    Bonsai.Clock.every [%here] (Time_ns.Span.of_sec 2.) clock_effect
  in

The reset effect is defined similarly.

And exactly as desired, every state machine gets an up-to-date view of the world when handling its actions.
It's also really simple to understand and maintain: every state machine just needs to decide how it should act based on the world state, and doesn't need to be aware of / communicate with other state machines.

Even better, I think this might be a general solution for sequentially composing effects that depend on an incremental input, which might change as the effects are executed. I feel like this might be useful for enabling / simplifying other applications, although I haven't worked enough with production Bonsai code to have any particular ones in mind.

[TyOverby]

module Continuation = Effect.Define1 (struct
    module Action = struct
      type 'a t = ('a -> unit Ui_effect.t) -> unit Ui_effect.t
    end

    let handle action ~on_response =
      on_response
      |> Effect.of_sync_fun
      |> action
      |> Effect.Expert.handle_non_dom_event_exn
     ;;
  end)

val with_yoink
  :  ('a Effect.t Value.t -> 'a Computation.t)
  -> 'a Computation.t

let with_yoink f =
  Bonsai.wrap
    ()
    ~default_model:()
    ~apply_action:(fun ctx result () cb ->
      Bonsai.Apply_action_context.schedule_event ctx (cb result))
    ~f:(fun _model inject ->
      let%sub result = Bonsai.pure Continuation.inject inject in
      f result)
;;

[TyOverby]

Apparently this combinator already exists and is called Bonsai_extra.with_self_effect...