Prototyping Practical FRP

owensd,

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)
}

The major updates are:

  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.

Prototyping Practical FRP