Introduction

Learn yourself a Yampa for great good!

Project status: As of 2021-09 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.

Motivation

Functional Reactive Programming is an elegant concept to describe interactive programs (e.g. computer games) with a dynamic structure (e.g. create and destroy objects) within a temporal context (e.g. animations, game logic). It is formulated on a fundamental mathematical basis using pure functional programming which results in true, highly reusable components. In the end what we get are dynamic signal networks like this:

_images/arrows_example_.svg

Within the imperative programming paradigm the way we write programs is something like: if there is input, move the player forward, use new position to handle collision, use new position to draw picture. Within the functional reactive programming paradigm it’s in some way the other way around: here be a picture at the position of the player which is derived from input and collision events over time.

The scope of this book is to provide a gentle introduction for game programmers who come from an imperative background (e.g. Unity), who already know some Haskell but are not yet proficient enough with Monads, Monad Transformers and Arrows to read and understand the papers in one go. This book is based on the [FrpRefac16] paper and works it through step-by-step. Some examples are probably verbose, but it’s better to err on the side of too much explanation and hopefully developers finally start using Yampa!

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:

[GenMonArr98] 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:

  • Get and install stack (which installs GHC and Haskell)

Note

If you work on Windows make sure you use a resolver for GHC >= 9 otherwise the console won’t work properly. In stack.yaml set resolver to either ghc-9 or use on of a currently nightly like nightly-2021-09-07 but the git repo already used the correct version. Until I know how to resolve this issue you have to restart the terminal after every interuption with Control-C. You might also consider setting up a virtual machine with Linux and run the examples there (VirtualBox + Ubuntu image (2GiB)).

  • 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

Manual setup

If you cloned the repository you should be fine to following along with the examples. If you want to setup your own project you need add at least the following packages to stack:

package.yml

dependencies:
- dunai
- bearriver
- time
...

stack.yml

extra-deps:
- bearriver-0.13.1.3@sha256:125ada5168c74c0f79d1ec7bb0e9d3fc0fb7b2d57b51de66ba62190e1a6d2a3e,1796
#- Yampa-0.13.1@sha256:4612a2646c27bcd3ac55c90dbc34249303e28aa5b3bc3e0c6fa9ce58b889843c,5436
- time-1.11.1.2@sha256:a957467595420495c2dd440d9efa1f58c62277cf9438c7e7a515d7a4c65571ec,6287

Troubleshooting

Visual Studio Code + Haskell Language Server: ghcide not found

Run stack clean and 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 stack ghci 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.