technology from back to front

FRP with STMs

I had an idea for an interesting application of Software Transactional Memory (STM) the other day: Functional Reactive Programming (FRP).

Shriram Krishnamurti gave two excellenttalks at SchemeUK. In the pub discussion afterwards he explained some of the implementation challenges and techniques in FrTime (pronounced “Father Time”), the Functional Reactive Programming system for PLT Scheme. It occurred to me then that STMs, in particular the flavour proposed in Composable
Memory Transactions
paper, may provide a neat platform for FRP.

One of the challenges faced by FRP are glitches. Glitches can occur when a signal propagates via different routes at different speeds and the signals from these routes are combined. The combined signal may be produced from values that are out of sync. More generally, glitches can occur anytime several signals are combined that are affected by synchronised input signals.

If signals were represented by STM memory cells, we could express synchrony through transaction atomicity. A change of value in one or several synchronised signals would propagate through the entire signalling network atomically.

Another FRP implementation challenge are change notifications – signal values need to be recalculated whenever their input values change, which may in turn be calculated from other inputs etc. FrTime employs weak pointers from signals to their consumers for this and broadcasts
notifications along these, essentially implementing a “push” model of signal propagation.

In an STM implementation of FRP we should be able to exploit the retry and orElse constructs. The former allows us to wait for a change in inputs until it produces a change in output. The latter is used for composition.

I attempted a quick implementation of some of my ideas on top of Haskell’s STM. It didn’t take long to get something to work. However, that also revealed some fundamental design flaws in my initial approach. Here are some of the challenges:

  • Making sure that signal values don’t get lost; every value change must be propagated

  • Invoking all the right signal processing functions, in the right order, as part of single transactions

  • Dealing with feedback, i.e. cycles in the signal processing graph

At this stage it is not yet clear whether STMs really do make FRP implementations significantly easier – my efforts may get unstuck on the above, or some other problems I have yet to discover.

by
matthias
on
12/12/05
 
 


nine − = 6

2000-14 LShift Ltd, 1st Floor, Hoxton Point, 6 Rufus Street, London, N1 6PE, UK+44 (0)20 7729 7060   Contact us