# Prototyping Practical FRP

A few days ago I started brainstorming how we might go about handling input in a way that actually satisfies the continuous and temporal nature of FRP behaviors. Today, let’ take a deeper dive into one possible implementation.

## Understanding the Problem

The problem can essentially be broken down into the following goals:

1. Storage of historical input data
2. Efficient interpolation between discrete inputs

For input handling, there are two basic types: digital and analog. The digital input is `on` or `off`, and the analog input is a value that ranges between two `min` and `max` values for the input. However, since all of our input is made up of discreet inputs, the problem is nearly identical.

Here is a sample scatter-plot graph of a keypress:

``````   │
1 ┤    ▪           ▪     ▪       ▪             ▪
│
│
0 └────────▪──────────▪──────▪───────────▪──────────▪───────▶  t
``````

Each of the `▪` represent an actual input change for the button on the time. Of course, the problem with this plot above is that there is no `f(t)` that results in a value for every value of `t`. We need to interpolate that graph:

``````   │
1 ┼────▪───┐       ▪──┐  ▪───┐   ▪───────┐     ▪────┐
│        │       │  │  │   │   │       │     │    │
│        │       │  │  │   │   │       │     │    │
0 └────────▪───────┴──▪──┴───▪───┴───────▪─────┴────▪───────▶  t
t₀       t₁      t₂ t₃ t₄  t₅  t₆      t₇    t₈   t₉
``````

This provides us with a nice step-graph. Now, we can most definitely provide an answer for `f(t)` given any `t` that has occurred.

## Basic Approach

Let’ start thinking about the shape of the algorithm. The simplest approach is to simply loop through the input and return the correct value based on the time range.

Here is a sample program based on the above input graph:

``````let t₀ = 0,  t₁ = 4,  t₂ = 8,  t₃ = 10, t₄ = 12
let t₅ = 15, t₆ = 18, t₇ = 22, t₈ = 25, t₉ = 28

let up = 1, down = 0

struct Range { let start: Int, end: Int }
struct Input { let range: Range, value: Int }

var inputs: [Input] = []

// Simulate an input stream...
inputs.append(Input(range: Range(start: t₀, end: t₁), value: up))
inputs.append(Input(range: Range(start: t₁, end: t₂), value: down))
inputs.append(Input(range: Range(start: t₂, end: t₃), value: up))
inputs.append(Input(range: Range(start: t₃, end: t₄), value: down))
inputs.append(Input(range: Range(start: t₄, end: t₅), value: up))
inputs.append(Input(range: Range(start: t₅, end: t₆), value: down))
inputs.append(Input(range: Range(start: t₆, end: t₇), value: up))
inputs.append(Input(range: Range(start: t₇, end: t₈), value: down))
inputs.append(Input(range: Range(start: t₈, end: t₉), value: up))
inputs.append(Input(range: Range(start: t₉, end: Int.max), value: down))

func f(t: Int) -> Int {
for input in inputs {
if input.range.start <= t && t < input.range.end {
return input.value
}
}

return inputs.last?.value ?? Int.min
}
``````

Then we can simply call the function to get our results:

``````f(0)     // -> 1
f(29)    // -> 0
f(16)    // -> 0
f(22)    // -> 0
``````

Notice that we can call `f(t)` in any order and it all works.

## Optimization

Now, there is a problem with the above implementation: as the game progresses, more and more input will be generated. This is not good‚Ä¶ this is an `O(n)` algorithm. What we want to as close to is the `O(1)` algorithm that is available to us in non-FRP world.

Well, one simple approach is to use the previous result as a hint. Here’ the new function `f(t)`.

``````func f(t: Int, _ index: Int? = nil) -> (value: Int, index: Int) {
let start = index ?? 0
let forward = 1, reverse = -1

let len = inputs.count
let step = t < inputs.get(start)?.range.start ? reverse : forward

// search loop
for var idx = start; 0 <= idx && idx < len; idx += step {
let input = inputs[idx]
if input.range.start <= t && t < input.range.end {
return (input.value, idx)
}
}

let value = (step == forward) ?
inputs.last?.value ?? Int.min :
inputs.first?.value ?? Int.min;

return (value, 0)
}
``````

1. Return a tuple `(value, index)` that can provide us a hint as to the index into the `inputs` history to start at.
2. Based on the given `index`, we can also determine the search order.

Note: I’m using an extension to `Array`; you can find it here: Array.get.

The updated usage code:

``````let f₀  = f(0)
let f₁₆ = f(16, f₀.index + 1)
let f₂₂ = f(22, f₁₆.index + 1)
let f₂₉ = f(29, f₂₂.index + 1)
``````

When they are called in the expected time order, the number of times through the “search loop” above is reduced from 25 down to 10. The thing to note from the value 10 here, is that this is the minimum number of searches required for this approach.

That’ great!

Also, imagine if there were thousands of inputs. The value of 25 above would be significantly higher as each search would be starting at index 0. With this new optimized approach, the number searches will be bound by the number of inputs that have happened since the last call of `f(t)`.

It’s good to note that you could still call this version of the function in any order and all should still be good. The the index hint is only used as the starting search point in the `inputs` array.

# Summary

This approach is looking pretty solid to me, though, I’ve only really played around with it in the playground and with fake, simulated input data. Next time, I’ll explore out how this algorithm looks with real input handling code.

# Taking a Look at Practical FRP

My last blog post got me thinking… if we wanted to keep track of input over some arbitrary time range T, what is a way to approach the problem?

1. Keyboards
2. Mice

For each of these inputs, my primary question to ask breaks down into:

1. What was the starting state of the input component
2. What was the ending state of the input component

Further, for each of the types, I may ask some additional questions depending on the type:

1. digital – how many transitions were made over t?
2. analog – what was the actual path over t? the averaged result over t?

As we can see, the basic need is to perform some operation on individual components of the input over a set of those inputs that represent a time range.

## Keyboard

There are lots of different types of keyboards, but both in the US and internationally, the standard keyboards do not have any more than 105 keys.

Great! At any given moment in time, any combination of keys can be down.

This means that a 128 bit wide bitfield will be more than adequate to store this data.

## Mouse

For the mouse, well, some mice have LOT of buttons. Of course, many of those buttons come across as actual keystrokes. Regardless, we know we need the following data:

1. The (x, y) coords of the mouse
2. The button state of some number of supported buttons
3. The rotation of the mouse wheel (x, y)

For now, we can choose the following data layout:

1. 32 bits for the x-coordinate
2. 32 bits for the y-coordinate
3. 32 bits for each of the mouse wheel coords (64 bits)
4. A bitfield for each of the supported buttons, let’s say 7 buttons.

So, for a mouse, we can store the data in a 136 bits without any trouble at all.

If we take a look at the basics of an Xbox or PlayStation controller, you can see the following controls:

1. Two thumb-sticks (analog)
2. Two triggers (analog)
3. Two bumpers
5. 4 primary buttons
6. Three auxiliary buttons (“select”, “start”, “power”)
7. Two buttons on the thumb-sticks

The digital buttons account for 19 bits. The analog inputs account for 6-axises of input data. If we use 16 bits for each axis, then the analog components need 96 bits.

The gamepad can be represented in 120 bits.

## Keeping the History

Now that we have a strategy to handle storing the input in a somewhat compact way, it is good to look at storing the history of the inputs over time. Recall that a behavior is about a continuous value for the input.

So how much space is that?

Originally, I was thinking that this would be a bit impractical‚Ä¶ however, after thinking about it a bit more, especially in the context of this compact storage, this really doesn’t seem so bad.

Here’s the math so we can talk about it more deeply:

var tangle = new Tangle(document.body, {
initialize: function () {
this.KeyboardInputSizeInBits = 128;
this.MouseInputSizeInBits = 136;

this.KeyboardInputs = 1;
this.MiceInputs = 1;

this.KeyboardSampleRate = 60;
this.MouseSampleRate = 60;

this.CaptureTimeInMinutes = 120;
},
update: function () {
function SizeInMB(BitsPerSample, SamplesPerSecond, TimeInMinutes) {
var BitsPerSecond = BitsPerSample * SamplesPerSecond;
var DurationInSeconds = TimeInMinutes * 60;
var BitsPerMB = 1024 * 1024 * 8;
return BitsPerSecond * DurationInSeconds / BitsPerMB;
}
var KeyboardSizeInMB = SizeInMB(this.KeyboardInputSizeInBits, this.KeyboardSampleRate, this.CaptureTimeInMinutes);
var MouseSizeInMB = SizeInMB(this.MouseInputSizeInBits, this.MouseSampleRate, this.CaptureTimeInMinutes);

this.MemoryUsageInMB = KeyboardSizeInMB * this.KeyboardInputs + MouseSizeInMB * this.MiceInputs + GamePadSizeInMB * this.GamePadInputs;
}
});
}, false);

Input Sizes: Keyboard: bits Mouse: bits Gamepad: bits

Number of Inputs: Keyboards: Mice: Gamepads:

Sample Rates: Keyboard: Hz Mouse: Hz Gamepad: Hz

Time to Capture: minutes

Memory Usage: MB

Note: The data above is completely interactive; play with it to your heart’s content.

So, with the default values above we can store two hours of continuous input1 data that it will only cost us about 20 MB of memory. However, this is basically the worst case scenario. Normal players are simply not going to be able to give you 60 different keyboard inputs over a second.

Instead, if we normalize the values to: keyboard = 1 Hz, mouse = 10 Hz, and gamepad = 5 Hz, now we are only talking about 1.79 MB over a two hour gameplay session.

This is starting to look a lot more feasible that I first suspected.

Next time, I’ll take a look at what it will take to actually process this data and some API structures we may want to use.

1. Continuous in this context means 60 samples per second.

# Value Add – Bring Something to the Table

There was a comment on my Programming Theory and Practice blog article about a reactive solution for interacting with `IOHIDManager`. The full gist of it can be found here: https://gist.github.com/mprudhom/607560e767942063baaa.

My thoughts on it can be summed up essentially as:

1. It requires another library to actually see the code that is going on (the `ChannelZ` lib from the author), that is bad.
2. The solution requires bridging from Swift to ObjC back to Swift again, that is bad (though it cannot currently be avoided).
3. It is no better than the ObjC or C

The last point is the real kicker for me, especially as of late. If I'm going to invest in a new technology, I want to understand the value that I'm getting back from it. In other words: am I getting a good ROI (return on investment) from it?

The thing is, we can write the same "reactive-style" API today, in C or C compiler). To me, this is very valuable and is currently a significant negative (really, a potential deal-breaker for me) against Swift1. We don't know the plans for Swift, so it's hard to say what is going to happen here, and I am personally not interested in any of the managed ports I've been seeing for other platforms.

The API for the reactive-style needs to care about three basic things:

1. `connect` – we need to know when a new device has been connected
2. `disconnect` – we need to know when a device has been disconnected
3. `input` – we need to know when the input has changed

When we implement these things, we can do so in a pull, push, or a push-pull manner. My primary use case is for a game, so I'm going to use the pull model. This means that I want my `input` to actually be a collection of input values since the last time I requested them. I'm also going to ignore `connect` and `disconnect` for this example as they are really not that interesting and adds very little to this example.

The API is starting to look like this:

``````struct DeviceManager {
var input: [Input]
let hidManager: IOHIDManagerRef
}
``````

The C

``````struct DeviceManager {
std::vector<Input> input;
IOHIDManagerRef hidManager;
};
``````

Let's also say that `Input` looks like this:

``````enum Input {
case Mouse(x: Int, y: Int, buttons: [ButtonState] /* only want max of 5 */)
case Keyboard(keyCode: VirtualKey, state: KeyState)
}
``````

To model that in C

``````namespace DeviceType {
enum Type { Mouse, Keyboard };
};

struct Input {
DeviceType::Type type;

union {
struct { /* Mouse */
int x;
int y;
ButtonState buttons;
};
struct { /* Keyboard */
VirtualKey keyCode;
KeyState state;
};
};
};
``````

Clearly, the Swift version has some nice wins on syntax here.

Now, I said that I'm using the pull-model, so I have some `update` function:

``````func update() { /* The signature doesn't matter... */
let mouseInputs = filter(manager.inputs) {
switch (\$0) {
case let .Mouse(_): return true
default: return false
}
}
// do something interesting with the filtered mouse signals
}
``````

I'm not sure if there is a better way to do that check with associated enum values, but it kinda sucks. The C

``````void update() {
auto mouseInputs = filter(manager.inputs, [] (DeviceInput input) {
return input.type == DeviceType.Mouse;
});
// do something interesting with the filtered mouse signals
}
``````

Ironically, the C

## What's the Value?

The above example is only a subset of the full solution, but it is not really that far off from being complete. For me, I've been looking at and really wondering what the ROI is going to be for me to fully invest in learning and using Swift. Honestly, I'm not sure.

At this point, it is really starting to look like that I should just go back to C11 features, there is really not a whole lot that Swift can do over C

1. Lack of code portability
2. Lack of code interoperability
3. Lack of full memory control

Yes, it is true that each of these also has a cost associated with it in regards to C

Remember, Swift is still in its infancy – it is going to need to get a lot more sophisticated to realize its aspirations, especially to become a "systems level language".

For me personally, I think it is going to be a much better use of my time writing modern C

1. You need to evaluate this for your own needs; this type of cross-platform sharing may be of little to no value for you.

# Programming Theory and Practice

Note: This is a bit of a personal reflection exploratory post; if you are looking for deep insights into the Swift language or programming in general, you're probably not going to find much here.

## A little Swift aside for some context?

So why did I even start to go down this route of exploration into FRP? Well, I wanted to create an API that felt natural in Swift for interacting with the `IOHIDManager` class for a prototype of a game idea that I have (thanks to much motivation from Handmade Hero). This is the only way that know how to interact with multiple gamepads, keyboards, and mice to build a proper platform layer for a game on OS X (and potentially iOS).

It turns out, building this in Swift is a pretty bad experience. The `IOHIDManager` class relies on C callback functions for device connection, removal, and input. This is the point in my Swift work that I know is just going to be painful as I've done it multiple times now. The only way for this to work 1 is to:

1. Create a C file (and corresponding header) to actually implement the callbacks
2. Export that callback in a variable so that Swift can use it
3. Create another Swift class with the `@objc` attribute so that I can pass data from C back into Swift via this class. Of course, this class needs to be public which artificially adds an implementation detail to the public interface, which I also really dislike.

Ok, this is easy to do, but annoying. Also, at this point, I have now introduced a lot of overhead for dealing with input events, both in terms of code required and runtime costs. I don't like this at all… and I need to do for keyboard, gamepad, and mouse events.

What's really annoying, I just simply wanted to start prototyping with something like this:

``````public enum VirtualKey {
case A
// ...
}

public enum KeyState {
case Up
case Down
}

public struct MergedKeyState {
let key: VirtualKey
let start: KeyState
let transitions: Int
}

public struct KeyboardInput {
var samples: [VirtualKey : [KeyState]]

public init() {
self.samples = [VirtualKey : [KeyState]]()
self.samples[VirtualKey.A] = [KeyState]()
}

public mutating func add(key: VirtualKey, state: KeyState) {
samples[key]?.append(state)
}

public mutating func key(key: VirtualKey) -> [KeyState] {
if let input = self.samples[key] {
self.samples[key]?.removeAll()
return input
}
else {
return []
}
}

public mutating func keyA() -> MergedKeyState? {
let merged: MergedKeyState? = reduce(self.key(.A), nil) {
merged, state in
if let merged = merged {
return MergedKeyState(key: merged.key,
start: merged.start,
transitions: merged.transitions + 1)
}
else {
return MergedKeyState(key: .A, start: state, transitions: 0)
}
}

return merged
}
}
``````

Is this a good approach to the problem? I don't know, that's why I'm prototyping out potential solutions. There is a bunch of mutating attributes, that might be bad‚Ä¶ but the point is, the only way I could actually start playing with this is to remove it from the context of the problem all together because of the C interop issues.

## So what's my point?

Excellent question! Honestly, I don't even know if I'm quite sure. I have a lot of thoughts in my head around many tangentially related topics, but I guess if we focus it merely on this trend in functional programming and FRP implementations, I feel like I have to be missing something because all I really see is this: a very primitive architecture for a game engine.

If you are using "pull" to get the data, you really are simply handling input just like many game engines would. That input cascades changes down some structure of data to determine what needs to be updated and re-drawn.

If you are using a "push" model, you've really just implemented a potentially nicer way doing exactly what you are doing today with event driven or notification driven UI patterns. Yes, there are some nice things we can do here, but this seems to continue with one of the biggest problems: mutations from random places at random times, albeit, maybe slightly more controlled.

I guess at the end of it all I have a bit of melancholy about the whole situation. I wish more people were thinking up these models and really applying them to the hardware instead of using the hardware to, essentially, brute force the conceptual model into working on our current hardware.

1. As of Xcode 6.3 beta 2‚Ä¶