# 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.