Introduction

Project status: As of 2023-03 there are four chapters with examples but lots of todos and missing prose.

Tip

If you don’t care about the motivation, background, history of functional reactive programming and know Haskell already, just skip to Embedding.

Functional Reactive Programming (FRP) is an elegant approach for developing interactive programs, such as games, which inherently consist of dynamic structures and operate within a temporal context. Rooted in a solid mathematical foundation and using pure functional programming, FRP yields highly reusable and composable components which lead to the creation of dynamic signal networks, as illustrated in the following diagram:

_images/arrows_example_.svg

In contrast to the imperative programming paradigm, where the process resembles a step-by-step execution of actions (e.g. if there is input, move the player, handle collisions, draw the character), the functional reactive programming paradim takes a different perspective. It uses a declarative approach, where a picture is displayed at the player’s position, which again is derived from input and collision events over time.

This book focuses on the Yampa libary and aims to provide a gentle introduction to game programmers transitioning from an imperative background (e.g. Unity), who posses some knowledge of Haskell but may not be fully versed in Monads and more complex type-classes. Based on the [FrpRefac16] paper, this tutorial breaks down the concepts into manageable steps and how to apply them to real-world game programming scenarios.

Motivation

Why functional

A lot has been said about “why functional programming matters” [WhyFP90] already. There is no point on iterating about it here much more.

Why reactive

Let’s start with a simple uni-directional user interface example of a counter. Let there be three buttons: increase, decrease and reset which change a label text.

    let count = 0

    const buttonIncrease = document.createElement('button')
    const buttonDecrease = document.createElement('button')
    const buttonReset    = document.createElement('button')
    const labelCounter   = document.createElement('label')
    const components = [buttonIncrease, buttonDecrease, buttonReset, labelCounter]

    buttonIncrease.innerHTML = "increase"
    buttonDecrease.innerHTML = "decrease"
    buttonReset   .innerHTML = "reset"
    labelCounter  .innerHTML = count.toString()

    buttonIncrease.onclick = () => { count += 1; labelCounter.innerHTML = count.toString() }
    buttonDecrease.onclick = () => { count -= 1; labelCounter.innerHTML = count.toString() }
    buttonReset   .onclick = () => { count  = 0; labelCounter.innerHTML = count.toString() }

counter0.html

There is a lot to criticise about this code already. Maybe we should introduce a class Counter which extends (or composes) a Label and make count private to hide it away from all other sites. While this may be better the basic problem remains. After all, there are already three if-conditions which change the counter variable. We just move the problem into Counter and encapsulate it a bit shielding it from outside manipulation. If you are not disciplined enough this might get out of hand again soon, the code might look the same, just within the Counter class.

There is a popular architectural pattern called Model-View-Controller (MVC for short). The model represents some intrinsic state. The view displays the states in multiple forms (text, charts). The controller manipulates the model state. And maybe we should add a general EventManager singleton and call EventManager.onEvent(“inc”) and let the corresponding components handled it themselves. While this removes the reference to labelCount it introduced another indirection in that we don’t know were the event came from.

// model states
count = 0

// views representing the model states
labelCount = new Label("0")
labelCount.update() =>
  this.text = count.toString()

buttonInc = new Button("inc")
buttonDec = new Button("dec")
buttonNul = new Button("nul")

// controllers manipulating the model state
countHandler = (type) =>
  if (type == "inc") count += 1
  if (type == "dec") count -= 1
  if (type == "nul") count  = 0
EventManager.addHandler(countHandler)

buttonInc.onClick = () => EventManager.onEvent("inc")
buttonDec.onClick = () => EventManager.onEvent("dec")
buttonNul.onClick = () => EventManager.onEvent("nul")

Lets add another uni-directionl event source which acts on the counter. Let the counter be increased or decreased by keyboard input.

InputManager.onKeyPressed = (key) =>
  if (key == "plus" ) EventManager.onEvent("inc")
  if (key == "minus") EventManager.onEvent("dec")
  if (key == "del"  ) EventManager.onEvent("nul")

Again, this looks very innocent but in reality we can never tell where an event was fired from, thus loosing all call stack information in debugging. At some cycle the onEvent listener may be called with “add” but we don’t know who called it: buttonAdd? onKeyPressed? Did mysteryProcedure add some other event calling sites? We also note a lot of criss- and cross-referencing of variables and objects. labelCount references count. Does something else also reference count? What is mysteryProcedure doing to labelCount?

Let’s make it even more weird and look at a bi-directional user interface example. Let there be a number field and a slider while one always shows the value of the other.

    const numberInput = document.createElement('input')
    const sliderInput = document.createElement('input')
    sliderInput.type = "range"
    const components = [numberInput, sliderInput]

    numberInput.value = 0
    sliderInput.value = 0

    numberInput.onkeyup     = () => sliderInput.value = numberInput.value
    sliderInput.onmousemove = () => numberInput.value = sliderInput.value

bidirectional0.html

Okay, but who is in charge of the model state “value” now?

    let value = "0"
    let changedBy = null

    const numberInput = document.createElement('input')
    const sliderInput = document.createElement('input')
    const components = [numberInput, sliderInput]
    sliderInput.type = "range"

    numberInput.update = () => {
      if (changedBy != null && changedBy !== "numberInput") {
        numberInput.value = value
        changedBy = null
      }
    }
    sliderInput.update = () => {
      if (changedBy != null && changedBy !== "sliderInput") {
        sliderInput.value = value
        changedBy = null
      }
    }

    numberInput.onkeyup     = () => { value = numberInput.value; changedBy = "numberInput" }
    sliderInput.onmousemove = () => { value = sliderInput.value; changedBy = "sliderInput" }

    const update = () => {
      components.forEach(c => c.update())
      window.requestAnimationFrame(update)
    }

    update()

bidirectional1.html

There is a way to make all of this more structured called “immediate mode user interfaces” (IMGUI). We can imagine it like rendering and handling the UI components at every update cycle.

value = 0

update() =>
  enteredValue? = numberField(value)
  slidedValue?  = slider(value)

  if (enteredValue != null || slidedValue != null)
    value = merge(enteredValue, slidedValue)

main() =>
  while(true)
    update()

This also makes another property very clear: could it be possible that the number field and slider is in some way changed at the same time… like on a multi-touch device? And if so which component should win out? merge could for example bias towards the first parameter.

Now in functional reactive programming we would define value to BE the (merged) input of numberField and slider over time. Just like you would define the cell of a spreadsheet to BE the sum of multiple cells and whenever one of the referenced cells changes the sum changes automatically too. Except that spreadsheets usually don’t have a way to handle bi-directional (“cyclic”) data flow.

 | A | B | C
-+---+---+---
1|123|   |
-+---|---+---
2|234|   |
-+---|---+---
3|345|   |
-+---|---+---
4|=SUM(A1:A3)
-+---|---+---
5|=AVG(A1:A3)

Let’s imagine a more complex real-time, interactive computer game which uses an user interface with hierarchical component structure, user inputs bubbling down and up the component tree, each component handling the input and/or prevent further bubbling, while the user interface overlays an interactive game scene, were objects can be selected or dragged, UI components can be selected or dragged, depending on some internal operation state. Scene objects overlay scene objects, UI component overlay UI components, UI components overlay scene objects and some of them have a bi-directional dependency on each other to form an internal model state (like a player position). Good luck with that! User input events will pop up out of nowhere, going anywhere, changing global-ish states, states which may be changed at multiple sites, concerns scattered across multiple locations, impossible to track, debug, test and extend in the long run.

With (functional) reactive programming the data flow is clear.

Why temporal

History

Todo

Complete history of FRP based on papers

Todo

Timeline of FRP

  • Fran allows to describe and compose animations over time (no support for Events and dynamic list of Behaviours)

  • Push and pull discussion

  • Optimizing CCAs

  • Fruits criticism https://mail.haskell.org/pipermail/gui/2003-February/000140.html “Things like getting an alien spaceship to move slowly downwards, moving randomly to the left and right, and bouncing off the walls, turned out to be a major headache.” => no changing behaviours.

  • Yampa arcade in [YamCade03]

  • Wormholes to route IO into the signal network

  • [FrpRefac16] to provide Reader and Writer monads within in the signal network

Perez et al developed Monadic Stream Functions and showed that Yampa could be described as special case of Reader MSFs which provides time deltas. FRP apparently is the first concept to describe inherently stateful tasks which supposedly required imperative programming (things like simulations, GUIs). With [FrpRefac16] it appears we finally reached a point were most of the issues are out of the way:

[FrpExt17] 3.3.2: Limitations of FRP and Arrowized FRP [regarding old Yampa]: Fixed Time Domain and Clock, I/O Bottleneck, Explicit Wiring, Referential Transparency Across Executions, Style and code modularity.

Attention

Differenciate between Yampa (old Yampa, Yampa 1), Dunai (MSFs) and BearRiver Yampa (new Yampa, Yampa 2) which is based on Dunai. The function signatures of BearRiver are a little different to the old Yampa (e.g. embed is now a Monad).

bearriver Hackage “Because dunai is particularly fast, especially with optimizations enabled, this implementation is faster than traditional Yampa for medium-sized and large applications.”

Ivan Perez: “There’s some fundamental differences, like the fact that, in principle, bearriver signals do not exist at time 0”

Reddit - Ivan Perez on What makes Dunai special?

Haskell

This books assumes the reader is familiar with progamming interactive applications, basic Haskell and Monads. It will not provide yet another tutorial on Haskell and Monads because there are enough out there already. Some important aspects will be reiterated if need be. If you must learn Haskell first I recommend to start with [LearnGood11]. Monads are on a different difficulty level. Always remember they are an abstract mathematical concept and a lot of smart computer scientists found them useful in many different situations and therefore it’s worthwhile to learn them the hard way. Keep away from metaphors. I recommend to start with [MonadFP95] which is still relevant even after 25 years and clearly shows the motivation using simple examples for imperative programmers, how to use them and why. Then take a deep dive with [AllMonads03] and make sure you understand how the abstraction builds up from Functor, Applicative to Monad ( Monad Transformer) up to Arrow according to the Typeclassopedia:

_images/typeclassopedia.png

Arrows

Arrows are an essential building block of Yampa and together with the arrow notation provide a way to write clear and readable signal networks. Similar to Monads, Arrows are a general way to “combine things” hence a “combinator library”. Different to Monads however, Arrows allow to specify exactly which input parameter of a tuple is used and how it connects to the output parameters. It is also important to understand how all of this is put together to form Yampa:

  • The Arrow type class provides the general combinators. Type classes need concrete instances however.

  • There are libraries out there (which one?) which provide general arrow combinations independent of the concrete class instance (i.e. independent of Yampa), only using the combinator functions (>>>, &&& etc.).

  • Dunai’s MSFs and Yampa’s signal functions are an instance of the arrow type class which encapsulate and abstract away the concept of continuous time.

  • Dunai provides a general way to implement causality (“step! step! step!”).

  • BearRiver Yampa is a specific implementation of causality in the concept of continuous time (“tiiick”) using MSFs plus events.

  • Yampa provides additional functions which are useful within the context of continuous time and events (integral, accumHold etc.).

See the Arrows homepage for additional information. Here are description excerpts from the arrow papers:

[GenMonArr00] One of the distinguishing features of functional programming is the widespread use of combinators to construct programs. A combinator is a function which builds program fragments from program fragments; in a sense the programmer using combinators constructs much of the desired program automatically, rather that writing every detail by hand.

[NewNotatArr01] The categorical notion of monad, used by Moggi to structure denotational descriptions, has proved to be a powerful tool for structuring combinator libraries. Moreover, the monadic programming style provides a convenient syntax for many kinds of computation, so that each library defines a new sublanguage.

[ArrComp03] Many programs and libraries involve components that are “function-like”, in that they take inputs and produce outputs, but are not simple functions from inputs to outputs. This chapter explores the features of such “notions of computation”, defining a common interface, called “arrows”. This allows all these notions of computation to share infrastructure, such as libraries, proofs or language support. Arrows also provide a useful discipline for structuring many programs, and allow one to program at a greater level of generality.

[ProgArr05] We can think of arrows as computations, too. The Arrow class we have defined is clearly analogous to the usual Monad class - we have a way of creating a pure computation without effects (arr/return), and a way of sequencing computations ((>>>)/(>>=)). But whereas monadic computations are parameterised over the type of their output, but not their input, arrow computations are parameterised over both.

arr

_images/arrow_arr_.svg

Lift a function to an arrow.

returnA

_images/arrow_returnA_.svg

The identity arrow, which plays the role of return in arrow notation.

first second

_images/arrow_first_.svg
_images/arrow_second_.svg

Pass-through component and leave it unchanged.

(>>>) (<<<)

_images/arrow_rcompose_.svg
_images/arrow_lcompose_.svg

Just feed the output of one arrow as input into the other.

(***)

_images/arrow_parallel_.svg

(&&&)

_images/arrow_fanout_.svg

Called fan-out or widening.

loop

_images/arrow_loop_.svg

(^>>) (>>^) (<<^) (^<<)

_images/arrow_lprecomp_.svg

Convenience function if just want to compose with a pure function but don’t want to write arr all the time.

Todo

add simple arrow combinator examples

Arrow notation

Introductions from the arrow notation papers:

[NewNotatArr01] Recently, several workers have proposed a generalization of monads, called variously “arrows” or Freyd-categories. The extra generality promises to increase the power, expressiveness and efficiency of the embedded approach, but does not mesh as well with the native abstraction and application. Definitions are typically given in a point-free style, which is useful for proving general properties, but can be awkward for programming specific instances.

[ArrComp03] With this machinery, we can give a common structure to programs based on different notions of computation. The generality of arrows tends to force one into a point-free style, which is useful for proving general properties. However it is not to everyone’s taste, and can be awkward for programming specific instances. The solution is a point-wise notation for arrows, which is automatically translated to the functional language Haskell. Each notion of computation thus defines a special sublanguage of Haskell.

myArr static0 = proc (in0, in1, in2) -> do
  x <- anotherArrA -< in0
  let a = x + in0
  y <- anotherArrB -< (in1, in2)
  z <- anotherArrC -< in2
  rec
    r0 <- recursiveArrA -< r1
    r1 <- recursiveArrB -< r0
  returnA -< (x + y + z, 123, "abc")

Installation

If you want to follow along with the examples, which is highly recommended, you need to setup some things first:

>>> apt install build-essential curl libffi-dev libffi7 libgmp3-dev libgmp10 libncurses-dev libncurses5 libtinfo5 # using libgmp3-dev instead of libgmp-dev and libffi7 instead of libffi6
>>> ghcup tui

Install GHC 9.0.2 (as of 2022-08-21 newer versions are incompatible with Haskell Language Server 1.7)

>>> cabal update
>>> cabal build
  • Get the git repository with

>>> git clone https://gitlab.com/gerold.meisinger/yampa-book.git

If everything works you should see a notification in Visual Studio saying:

_images/vscode_haskell.png _images/vscode_hls.png

Visual Studio Code may suggest other extension for Restructedtext, Python etc. Install them if you like.

This is a book, so you might as well just read it.

If you like to contribute to this docs and learn how to build the documentation see Contributing. You can add public annotations and highlights on the sidebar right.

_images/annotate.gif

Troubleshooting

For troubleshooting of contributing-related issues see contributing troubleshooting.

Visual Studio Code + Haskell Language Server: ghcide not found

Restart the Haskell Language Server with Control-Shift-p

error: parse error on input '->'

sf = proc input -> do
  ...

Add the following line on top of your file: {-# LANGUAGE Arrows #-}

<no location info>: error:
  Could not find module `Data.MonadicStreamFunction'
  It is not a module in the current program, or in any known package.

Start with cabal repl instead of just ghci otherwise the modules won’t be loaded.

I'm getting strange garbled output in ghci on Windows

You interrupted the execution with Control-C and now need to restart your terminal!. This is a known issue which I still don’t know how to resolve.