Tutorial: Roguelike with effect handlers

Hello!

The recent conversations about eio 0.1 and agnostic blocking have made me very curious about effect handlers. The multicore team has done an awesome job with their tutorials, examples and talks, but the laymen have been too quiet for such an exciting feature! Where are all the blog posts about how “you could have invented algebraic effects” and “one-shot continuations are like spaghetti”?

In any case, I’m hoping to tease some of you into trying them out with a simple tutorial about programming a roguelike with effect handlers :slight_smile:

There’s nothing new here besides the fun use-case! So if you already have an intuitive understanding of the syntax and motivations, you may be more interested by a deeper look at the scope of effect handlers – and a soft introduction to some less common features of the type system. (this link was previously posted deep into the eio thread)

I would be grateful if you spot any mistake! I’m also curious of other fun applications for effect handlers… and if you feel like sharing your own surprises and discoveries, I believe it could really help others learn faster :slight_smile:

36 Likes

Great blog post! That seems like a very elegant implementation!

Funny you should make a rougelike :smiley: , I guess effect handlers + games might be popular for games, because I also had a blog post about effect handlers and their applications, in particular for games, although in my case it was for animations:

https://gopiandcode.uk/logs/log-bye-bye-monads-algebraic-effects.html

9 Likes

Thanks for sharing your blog @Gopiandcode, that’s exactly the type of content I was looking for! :heart:

1 Like

Note: the “upstream” status of effect handlers is a little uncertain/confusing right now. Your blog post (I didn’t get a chance to read it yet, but it sounds very nice!) uses the experimental syntax of multicore-4.12+effects, but that syntax was intentionally not upstreamed, and it will not be part of OCaml 5.0.

I think there is a risk of confusion because the community is aware that Multicore OCaml has effect handlers, and also that Multicore OCaml has been merged upstream. So it can be tempting to believe that the upcoming OCaml release (or maybe one or two releases after that, we said the first Multicore release would be more like a preview) will support effect handlers as a language feature. It will not! Effects as a language feature were removed from Multicore OCaml before the upstream merge. And no one knows if/when they will be supported upstream.

So: I think that your blog posts on using effect handlers could have somewhere a short mention that the code is using an experimental extension of OCaml that is not supported by the upstream implementation.


The reasoning for this choice is that we want to give a chance to a type system for effect handlers, but that still need quite a bit more time than the Multicore runtime itself. We don’t want to encourage the ecosystem to rely on untyped effects, if it means a lot of pain upgrading to typed effects later (or risk having to support both).

5.0 only contains basic support for effect handlers as a runtime primitive, but dos not support handlers as a language feature. I think they should be considered experimental: you can rely on them for their intended purpose of exposing a flexible interface for concurrent fibers, but uses beyond that may break in the future.

So, in a sense, we don’t want people to use them. It’s of course fine to use experimental features from experimental forks of the OCaml compiler (effect handlers, modular implicits or explicits, runtime type representations and what not), and the people working on these experimental features do benefit from other people trying them and giving them feedback. But we don’t want people to depend on it in production, whatever that means. (For example, code using it is likely to get stuck on 4.12 forever and never see an upgrade to upcoming OCaml versions, although of course people could choose to port the experimental branch forward.)

8 Likes

Thanks for the clarification on their hazy status! I picked the pretty syntax because it felt easier to explain, but I should have added the fat warnings earlier :slight_smile:

Fun read with the rogue-like! - especially concerning your experiments with avoiding the gameloop via effects, as I’ve been thinking about gameloopy stuff in the context of FRP.

I don’t think the structure you propose scales very well concerning the complexity of extending the game semantics over time, which you also stumbled over - but I guess that wasn’t the intention.

A problem related to what you mentioned about updating other entities life, and having them update their state before they are done sleeping - is that you would need to update your state after each resume of your continuation based on what other entities communicated via the shared state. So in the end the code doesn’t look as elegant, and becomes more errorprone.

If others are interested in the “alternative gameloop” aspects - I implemented a simple browser-game with an Elm-style gameloop using FRP in OCaml some years ago: flappy/flap.ml at master · rand00/flappy · GitHub

2 Likes

Nah it would scale just fine ^^ . The endings are sketchy because the game state isn’t given the proper attention it deserves. I wish I had explained how to remove the impure mutations on the world by using an effect End_of_turn : world -> world and other variations to help with the characters public state.

Anyway you would have to solve the same issues with The Elm Architecture, because TEA is actually very similar if you ignore the obfuscation by defunctionalization. In your flappy game, you have this “big match” function on all the events:

type event =
  [ `WingFlap ...
  | `Frame ...
  | `PauseToggle
  | ... ]

val update : event -> (model -> model)

This update is giving an interpretation of event as a function to update the model… But since that’s the only use of event, you could re-functionalize your code:

type event = model -> model

let update event model = event model (* no more match! *)

let wing_flap (player, direction) model =
  when_not_paused model @@
    ... { model with birds; feathers }

let handle_keypresses ev = match ev##.keyCode with
  | 87 (*w*) -> GameEvent.sink_eupd (wing_flap (0, `Up)) 

This gets rid of the big match on all the events. If you keep pushing in that direction to support the sequencing required by character’s AI, you can quickly end up with a monad for event – at which point it’s pretty much the same as effect handlers :slight_smile:

In the roguelike tutorial, I mentionned the explicit state machines solution which would yield a similar outcome as the defunctionalization of TEA. I guess it would be interesting to implement the elephant and spider behavior with TEA if you are not convinced!

(Thanks for sharing your game btw!)

3 Likes

This doesn’t address the specific critique I mentioned. I’ll try to describe the problem in other terms. What seems elegant in your code to begin with is that you jump back/forward between the scheduler and the current branch in the decision-tree of the AI.

The problem that arises is that you suddenly want to let other entities influence your state - and as your decision-tree is dependent on your state, you suddenly need to be able to jump back to the root of the decision-tree under certain conditions. So the earlier advantage of continuing the AI from where it left of, now raises the complexity of the logic. What would your solution be to this? I’m guessing you would need to throw something like an Reset_decision_tree exception/effect, catched at the top of the AI loop.

Your suggestions to my games structure doesn’t seem advantageous to me. What I like about the current structure, which seems lost after your suggestions, is:

  • you know where to look to see all updates to the game-model
  • a function to update an entity never is given the whole model - as I want to be explicit about dependencies for all functions
  • the game-logic is fully separated from the imperative IO

I believe the most ergonomic way is to pass the event affecting the entity via continue, in addition to the remaining sleep time or None if nothing interrupted the sleep. We then also need an event effect that resumes another entity immediately i.e.

effect Sleep : int -> (event * int) option
effect Event : (cell * event) -> unit

If, for example, the elephant is sleeping for 20 turns but is hit after 15, it would be resumed immediately with (HitBy Spider, 5) which it could then handle by:

  • Ignoring if irrelevant
  • Handling and going back to sleep

That would also allow chain reactions (if intended). For example a knockback event could result in:
Elephant acts and knocks Camel back. Camel wakes up, attempts to move in intended direction but is blocked by a spider. It would then perform a knockback event on the spider (returning to the scheduler which continues the spider with the appropriate event). The spider then moves out of the way and sleeps again. Camel has succeeded with its event and moves too etc.

We could also discontinue the Sleep continuation with an exception. The result is basically identical to the Reset_decision_tree exception.

This is what I mean - you would need to handle this after each performance of an effect. And as there is choice here - depending on the branch of the decision tree - you get more complex code than neccesary. The alternative is that you go through your decision tree based on your updated state from the root on each frame - here there is only one place where you choose what decisions to prioritize.

I don’t think there is much difference there because this is inherent, unavoidable complexity. You always need a function akin to f : internal_state -> event -> action * internal_state because for every point you need to decide how you react to external events. It shouldn’t be that complex because you just have to wrap each sleep in an appropriate handler (e.g. vulnerable (sleep 10), burrowing (sleep 1), defending (sleep 1) etc).
Whether you always start at the root of your decision tree and traverse it according to the internal state and the event or you continue at the previous node, handle the event and then continue boils down to personal preference.

I think:

  • Always starting at the root prefers shallow decision trees and complex event handlers as we must explicitly encode in internal state at what node of the decision tree we were but events are free to manipulate the state in any way they want.
  • Continuing from the previous node prefers complex decision trees and simple event handlers (specifically: event handlers that do not interrupt the behavior in complex ways by e.g. continuing along a different path) as jumping to a sibling node in the decision tree is difficult.

I believe in general the second approach is preferable because we don’t have to manage a large internal state encoding all the necessary information and instead can handle each subbehavior in its own function.

1 Like

I would need to test the different structures in practice to be sure, but it seems like several game-features would become more complex to implement via the effect-based one, as the game-state is distributed between the decision-tree and a game-state-value of the entity. Also, as the state of the decision-tree is represented via continuations, it can’t be manipulated directly as a result of incoming events.

Another observation: it seems like there is a tendency of the effects-based structure to distribute state and handling to separate places (like OO), whereas FP commonly handles state-transitions in the same place.

I’m currently experimenting with a UI framework using effect handlers and have made similar observations. Some features become more complex (in my case modifying the current state based on certain, rare events) but it also makes most of the code easier to reason about.

The structure encouraged by effects seems to be very similar to the actor model of Erlang with a lot of objects/actors/threads communicating via effects. While “resumable exceptions” are certainly an interesting feature, it seems that, whenever an effect handler invokes continuations of previous effects, the real power of effects is seen. For example a scheduler managing multiple threads, actors communicating via (a-)synchronous message passing etc. In some sense, resuming continuations later is all about distributing state and handling in a functional way I guess.

1 Like

Hm so, I don’t think the two styles are that different, as there is a mechanical way of rewriting one into the other and vice-versa [1]. But yes they do favor different situations: Effect handlers are very good at sequencing “do this and then do that”, while TEA is all about “how do you react to this or that”. The good news is that you don’t have to pick a side, you can mix and match the two depending on the situation. For the roguelike, it made sense to use sequencing for the AI [2] – but when handling external events after an End_of_turn, you would naturally opt for a TEA update on the character state.

Anyway, state management in FP is always going to be a variation on model -> model. Whether it’s better to “keep everything in the same place” or “distribute in separate places” is not about FP vs OO, it only depends on what’s important to understand the logic. I mean, you are going to split your code as soon as it doesn’t fit in one file/function, but you are going to choose which stuff to keep together or separate. (For example in flappy, it could make sense to separate the menu/pause logic and the gameplay logic… but that refactoring wouldn’t make it less FP)

Ah also, closures already give you “internal private state”, effect handlers don’t bring anything new here. This internal state is not a bad thing if it gives you confidence that no one else is touching it (just like abstract types), but yes you should also have “public state” in your model for the rest :slight_smile:


  1. You don’t even need to rewrite your code to integrate it with the other style: if you give me a TEA framework, I can still use it to write my code with the effect handlers style. And if I gave you my effect-based scheduler, you could also do an inversion of control and write your code as TEA recommends. ↩︎

  2. Keep in mind that my examples AI for the roguelike are tailor-made for demonstrating effect handlers! ↩︎

3 Likes

I don’t think that argument is relevant - we are talking about the complexity as seen from the programmer - who’s not just mechanical.

Yes ofc. you can, but what I bring up is how practical it is to extend the game logic when you have comitted yourself to a certain structure. Specifically I comment on the scaling of complexity when representing part of the gamestate as continuations instead of as data. Why I comment on this, is that decision-tree as continuations was essential to how you elegantly factored the gameloop to become a scheduler.

This doesn’t have anything to do with it. As long as the auxiliary functions are called from the same place, you know where to look for the code updating the state. With the effect-based structure it seems like it becomes much less obvious who’s updating what state when.

I would not have chosen to represent gamestate as closures.

Would be interesting to see examples of this (including the UI framework) (:

I think we have a disagreement on closures because we are looking at them from a different point of view: for me they are the solution to managing the scaling of complexity, but for you they increase it? I’m speculating, but I’m looking at the code complexity (where implicit closures/continuations help) while I believe you are looking at the datatypes? (where seeing a closure is a red flag: “this could do anything, good luck figuring it out!”)

To reuse the flappy example:

module Actions : sig
  type event
  val update : event -> model -> model
  val wing_flap : direction -> event
  val toggle_pause : event
end
= struct ... end

You already said that you prefer to implement this module with type event = Wing_flap of direction | Toggle_pause, a complex “big match” update and trivial constructors for the operations.
While for me it’s much more direct to define type event = model -> model, because then update is trivial and all my update code is organized in a standard way by OCaml builtin let. The explicit sum type would add an indirection in that logic[1], so I would only do that extra work if I needed to serialize those values (which is a valid point for not having closures in your game state!)

Anyway so to answer your question, my solution to handling the complexity of closures is that the model should contain only public stuff: then it’s much less dangerous to have arbitrary closures since they can only do so much. But I get to hide the private state in the closures, so they can still be smart, and I can add new closures/perform at arbitrary points without much effort (which is nice for exploratory programming, a big part of game dev.)

Without hidden internal state, the model must contain both the public and private state… and from my perspective, this is unmanageable: it’s less clear what is really public with all the noisy private state in there. It’s more fragile, since adding/removing private state for some operation requires a model type update which may break other functions. In fact in Elm, they grossly cheat when it comes to HTML widgets as they are allowed to have internal private state that isn’t reflected in your model (but it’s a convenience hack, so this feature isn’t available to Elm programmers).

Either way, there is always going to be a magical convention that helps structure our understanding of the code. With enough practice in one style, we learn to ignore the organizational aspects that don’t contribute to the task at hand.


  1. The code is the same, I just feel like I’m doing the compiler work if I can’t use closures! ↩︎

Sorry about the late reply, I was busy actually verifying that my concept works out. Thankfully it does :smile:

The UI framework is inspired by Concur which means that every widget listens for some set of events and suspends computation until one of these events occurs. Once it does, it continues execution until it encounter the next await at which point it will suspend once more. Once a widget has fulfilled its purpose it terminates with some return value (e.g. text input is confirmed with enter → return with a string).
Complex UIs are then built by composing simpler widgets. A more detailed explanation can be found in the link above.

I’ve implemented this concept using an await function that takes a list of triggers and a handler for each possible event:

effect Await : Event.t list -> Event.t
let rec await triggers handler =
  handler (EffectHandlers.perform (Await triggers))

let rec check_box checked  =
  (* display check box *)
  ...;
  await [Mouse_press; Key_press] (function
  | Mouse_press ->
    print_endline "I've been (un-)checked!";
    check_box (not checked)
  | Key_press -> (* Terminate if any key is pressed *) checked)

Every widget can then be implemented as a function which displays the widget and performs an Await triggers which is resumed by passing an event from triggers, for example the check box above.

The most complex widget I’ve implemented so far is a single line text input. It can be clicked or selected with tab. Moving the mouse while holding the button down changes the selection. As an automaton:

image

Obviously, this is not a directed acyclic graph and therefore not a perfect fit for the implicit state stored in the continuation. Specifically, Pressed has an edge to one of its multiple parents. We can extract the Pressed state into its own function and therefore avoid this issue by ‘duplicating’ this state. Now Pressed no longer has multiple parents:

image

Some cycles remain and we can’t remove them because they are essential to the functionality. Instead we throw an exception Repeat that returns us to a parent node (explicitly shown for Focused → Pressed → Released → Focused). To do that we modify await:

let rec await triggers handler =
  try handler (EffectHandlers.perform (Await triggers)) with
  | Repeat -> await triggers handler

In the end this results in this main method for the text input, with only minor simplifications:

method execute =
  (* Represent the Pressed state.
     We await the Mouse_release and handle Mouse_motion while we wait. *)
  let pressed (x,_) =
    selection <- Point x;
    await [`Mouse_release; `Mouse_motion] @@ function
    | `Mouse_release (_, LMB) ->
      ()
    | `Mouse_motion (x,_) ->
      self#select x;
      raise Repeat (* This restarts the await function *)
    | _ ->
      raise Repeat
  in

  (* We start in the Unfocused state *)
  begin
    await [`Mouse_press; `Key_press] @@ function
    | `Mouse_press (pos, LMB) ->
       (* We have registered the press, but only when it is released
          will we be focused. *)
       pressed pos
    | `Key_press Tab ->
      selection <- Area (0, List.length keys)
    | _ -> raise Repeat
  end;

  (* We move into the Focused state *)
  begin
    await [`Codepoint; `Key_press; `Mouse_press] @@ function
    | `Key_press Tab | `Key_press Return ->
      () (* The only path without raising Repeat.
            Therefore we only leave this await when a tab or return occurs *)
    | `Mouse_press (pos, LMB) ->
      pressed pos;
      raise Repeat
    | `Key_press c ->
      self#insert c;
      raise Repeat
    | _ -> raise Repeat
  end;
  (* We have reached the finished state. We can now return the entered text. *)
  self#text

I think that this method captures the automaton above quite nicely and can be relatively easily understood (hopefully even when one is unfamiliar with the framework and accepts that some magic is happening in the background (: ). Implementing automatons in terms of effect handlers seems to work quite well, at least for games and UIs. What these automatons have in common is that they can be thought of as flows, starting at some state and ending at one of multiple final states and only have few edges that don’t fit this scheme, turning them into ‘directed almost acyclic graphs’.

There is obviously a lot more necessary for a UI framework (e.g. resizing the window/widgets, delegating the events to the correct widget, composing widgets, drawing on the screen etc.) and I plan to write about it at some point in the future. But for that I will first need to actually solve these problems as right now their implementation is quite barebones. The code can be found here for those interested (still very early in development!): GitHub - Willenbrink/bogue: GUI library for ocaml based on SDL2

4 Likes

If you want to be able to animate several widgets at the same time - do you intend to handle concurrency in the widget-scheduler or in a wrapping concurrency-scheduler? Would be nice to see composition of schedulers.

Though maybe one wants to handle concurrency in the widget-scheduler in the end, e.g. to control render-framerates of widgets based on some heuristic. Could this be implemented by handling effects intended for the wrapping scheduler, and filtering them before reperforming them?

But I guess that you often want a widget to continue existing, and return intermediate values too?

Very much like FRP, though you can use fixpoint combinators to make recursion over the whole FRP-graph. Do you avoid cycles to let the code be simple, or are there other reasons?

I’ve not given much thought to animations yet but the simplest way would be to add a Clock or FrameRate event that is triggered at a fixed interval (basically a FRP signal). Then a simple delay could be:

let duration = ref 100 in
await [`Clock] @@ function
| `Clock delta_t ->
  duration := !duration - delta_t in
  if !duration > 0
  then raise Repeat
  else ()

Regarding the scheduler, currently there is no one singular scheduler. Each widget (except the root widget) is contained in another widget. This parent widget is then responsible for scheduling+drawing its children.
In the layout window (row [button; label]) the awaits of button and label are handled by row and its continuation are also stored there. row then performs its own await with a union of all the awaited events of its children. That gives row a lot of fine-grained control on how it intends to delegate the events (e.g. redirecting the click events on both the button and the label to the button, thereby allowing one to click on the label and also affect the button).

If I understand you correctly, this is handled by the distributed schedulers.

Yes, yes I do. Currently I can’t get that to work unfortunately. Ideally we solve this by simply extending the Await effect: effect Await : Event.t list * 'a -> Event.t. This has the unfortunate effect that (perhaps due to the lack of an effect system?) the parent can not determine that the child performed an Await with the correct type. In theory it should be possible as every widget is represented as a parametric object and the children and the parent have an identical type:

class virtual ['a] widget =
  object
    (* An effect system should determine that execute only raises Awaits with type 'a *)
    method virtual execute : 'a
  end
class ['a] row =
  object
    val child : 'a widget (* For simplicity only one child *)

    method execute =
      try child#execute with
      | effect Await (events, state) k -> ... (* state has a locally abstract type and NOT 'a *)

    method exeucte_alt =
      (* Does not typecheck as 'a is not bound (although it should be by the surrounding class ['a] row.) I might miss an obvious solution here. *)
      let effect Await_alt : Event.t list * 'a -> Event.t in
      let await x = perform (Await_alt x) in
      try child#execute_alt await with
      | effect Await_alt (events, state) k -> ...
  end

Perhaps objects were not the right choice and I should have used first-class modules instead. Although objects seem to perfectly fit the needs of a GUI.

I’ve never really looked into FRP and am therefore unfamiliar with the fixpoint combinators. I also don’t really see the parallel here to FRP. The window emits events on user input and a signal representing frame draws / elapsed time and the widgets react to events. This is similar to FRP. But what I was talking about there is the implicit state stored in the continuation. Can you elaborate? As I understand it:

await [A,C] @@ function
| A -> (*state A *)
    begin await [B;C] @@ function
    | B -> ... (* state B*)
    | C ->
(* How would I move from here to state C below? That would basically be a goto.
   My solution is to duplicate the state C by extracting it into a function called both here and below. *)
    handle_state_C ()
(* Alternatively we can do that with exceptions *)
    raise State_C
    end
| C | exception State_C -> handle_state_C ()