Functional Reactive Programming Notes

frpnotes.md

FRP Notes

Implementations in Scala, but conceptually should apply to all FP languages

Reactive programming is about reacting to sequences of events that happen in time

Functional view: Aggregate an event sequence into a signal.

A signal is a value that changes over time

It is represented as a function from time to the value domain

Instead of propagating updates to mutable state, we define new signals in terms of existing ones.

Basics: event-based view of a mouse moving:

Two fundamental operations over signals:

1. Obtain the value of the signal at the current time.

mousePosition()

2. Define a signal in terms of other signals.

def inReactangle(LL: Position, UR: Position): Signal[Boolean] = 
  Signal {
    val pos = mousePosition()
    LL <= pos && pos <= UR
  }

Value of type Signal are immutable.

Signals of type Var look like mutable variables, where

sig()

is dereferencing, and

sig() = newValue

is updating, but there is a crucial difference. We can map over signals, which returns a relation between two signals that is maintained automatically, at all future points in time. No such mechanism exists for mutable variables, so updates need to be propagated manually.

Looking at a toy example of a bank account:

class BankAccount {
  val balance = Var(0)
    def deposit(amount: Int): Unit = 
      if (amount > 0) {
        val b = balance()
        balance() = b + amount
      }
    def withdraw(amount: Int): Unit = 
      if (0 < amount && amount <= balance()) {
        val b = balance()
        balance() = b - amount
    }  else throw new Error("insufficient funds")
}

Where a var balance has been replaced by a Var() signal. It is important tp

Continuing with some example use cases:

object accounts {
  def consolidated(accts: List[BankAccount]): Signal[Int] = 
    Signal(accts.map(_.balance()).sum)
  val a = new BankAccount()
  val b = new BankAccount()
  val c = consolidated(List(a, b))
  val exchange = Signal(250.00)
  val inDollars = Signal(c() * exchange)
}

There is an important difference between the variable assignment

v = v + 1

and the signal update

s() = s() + 1

In the first case, the new value of v becomes the old value of v plus 1. In the second case, the signal definition makes no sense because it is implying that signal s exists at all points in time one larger than itself.

Comparing and contrasting variables vs signal updates:

val num = Var(1)
val twice = Signal(num() * 2)
num() = 2
// returns 4

and

val num = Var(1)
val twice = Signal(num() * 2)
num() = 2
// returns 2

A more realistic implementation

Presuming a package frp

With an API:

class Signal[T](expr: => T) {
  def apply(): T = ???
}
object Signal {
  def apply[T](expr: => T) = new Signal(expr)
}
class Var[T](expr: => T) extends Signal[T](expr) {
  def update(): T = ???
}
object Var {
  def apply[T](expr: => T) = new Var(expr)
}

Each signal maintains

its current value

the current expression that defines the signal value

a set of observers: the other signals that depend on its value.

If the signal changes, all observers need to be re-evaluated.

How are dependencies recorded in observers?

When evaluating a signal-valued expression, need ot know which signal caller gets defined or updated by the expression

Executing a sig() means adding caller to the observers of sig

When signal sig's value changes, all previously observing signals are re-evaluated and the set sig.observers is cleared.

Re-evaluation will re-enter a calling signal caller in sig.observers, as long as caller's value still depends on sig.

How does one determine on whose behalf a signal expression is evaluated?

A class for stackable variables:

class StackableVariable[T](init: T) {
  private var values: List[T] = List(init)
  def value: T = values.head
  def withValue[R](newValue: T)(op: => R): R = {
    values newValue :: values
    try op finally values = vlaues.tail
  }
}

which is accessed like so:

val caller = new StackableVar(initialSig)
caller.withValue(otherSig) { ... }
... caller.value ...

A so-called "sentinel" object, NoSignal is the caller for expressions at the top level where there are no other signals that are defined or updated:

object NoSignal extends Signal[Nothing](???) { ...}

object Signal {
  private val caller = new StackableVariable[Signal[_]](NoSignal)
  def apply[T](expr: => T) = new Signal(expr)
}

The signal class:

class Signal[T](expr: => T) {
  import Signal._
  private var myExpr: () => T = _
  private var myValue: T = _
  private var observers: Set[Signal[_]] = Set()
  update(expr)

  protected def update(expr: => T): Unit = {
    myExpr = () => expr
    computeValue()
  }
  
  protected def computeValue(): Unit = {
    val newValue = caller.withValue(this)(myExpr())
    if (myValue != newValue) {
      myValue = newValue
      val obs = observers
      observers = Set()
      obs.foreach(_.computeValue())
    }
  }

  def apply() = {
    observers += caller.value
    assert(!caller.value.observers.contains(this), "cyclic signal definition")
    myValue
  }
}

// In order to properly handle NoSignal, override compute value and return unit
object NoSignal extends Signal[Nothing](???) {
  override def computeValue() = ()
}

Var is a Signal which can be updated by a client program.

class Var[T](expr: => T) extends Signal[T](expr) {
  override def update(expr: => T): Unit = super.update(expr)
}

object Var {
  def apply[T](expr: => T) = new Var(expr)
}