Sirea RDP Progress Update: Demand Monitors are Working

My implementation of Reactive Demand Programming (RDP), Sirea, is gradually approaching a usable state. After vacation, I sat down and in just a couple programming sessions I got demand monitors into a working order. The implementation of demand monitors further provides useful components for rapid, robust integration of a variety of IO resources with RDP.

A demand monitor is a resource modeled as a pair of behaviors (respectively called ‘demand’ and ‘monitor’) that are implicitly coupled through a shared-state side effect. Signals sent to the demand facet are collected into a list then projected to the monitor facet. That is, a set of signals becomes a signal of sets (`(Ord a) => [Sig a] -> Sig [a]`). Demand monitors support many communication patterns: one-to-many communication (by sharing just the monitor facet), many-to-one communication (by sharing just the demand facet), and many-to-many communication (by sharing both).

Demand monitors are among the simplest useful resources in RDP systems, and exhibit many features that (collectively) distinguish RDP from other reactive or dataflow models. Demand monitors support implicit bi-directional communication, logical concurrency, anticipation, and open extension. Understanding demand monitors can help with grokking all of RDP’s effects model, which is why I have said demand monitors the heart and soul of RDP.

In Sirea, demand monitors are accessed as an ambient capability, uniquely identified by data type, partition, a string.

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}
type DemandMonitor b p e z = (b (S p e) (S p ()), b (S p ()) (S p z))
class HasDemandMonitor b p where 
    demandMonitor :: (Typeable e, Ord e) => String -> DemandMonitor b p e [e]
instance (Partition p) => HasDemandMonitor (BCX w) p

BCX is a concrete behavior implementation that has access to a reified ‘global’ resource environment. While RDP is designed for object capability model, Sirea favors ambient authority to better align with Haskell’s FFI and module system. The BCX instance of HasDemandMonitor will locate a unique demand monitor resource for each unique (typeOf e, typeOf p, String) triple. This enables easy sharing between independent modules, while also supporting modular encapsulation (e.g. with simple use of newtype).

A toy application with demand monitor might be to receive a set of numbers from behaviors representing concurrent agents, then print them to the console.

test :: BCX w (S P0 ()) (S P0 ())
test = injectNumbers |*| printResult 
   where dm = demandMonitor "test"
         injectNumbers = inject (3 :: Int) |*| inject 7 |*| inject 4 
                     |*| inject 5 |*| inject 4
         inject n = bconst n >>> fst dm
         printResult = snd dm >>> bprint show
main = runSireaApp test -- prints [3,4,5,7] to console

(Aside: `|*| :: b x y -> b x z -> b x x` is concurrent composition, ignoring response from both behaviors. It’s useful for modeling concurrent processes or independent agents. It is easily defined in terms of bdup, bfirst, and bsnd.)

Demand monitors are not complicated, but still present several implementation challenges:

  1. Robust handling of cycles, e.g. progress and predictable performance guarantees. (Cycles are generally of the form `monitor >>> process >>> demand`.)
  2. Garbage collection of cached signal data, especially when detaching
  3. Optimal update-ordering to avoid rework within a step
  4. Efficient processing of cycles; minimizing downstream exposure of intermediate data

Cycles may be robustly broken by shifting the monitor updates into the next partition step. Doing so ensures predictable performance and preserves snapshot consistency (per demand monitor). Optimal update ordering uses the ln_touch mechanism to ensure all updates are received at each locus before processing takes place. For GC, I extended my architecture with an ability to schedule events on ‘heartbeats’, which are provided by the main thread at 10-20Hz.

Unfortunately, I was unable to accomplish the fourth point. Efficient processing of cycles requires breaking them at a minimal set of locations. Once all the cycles are broken, the remaining demand monitors can deliver their updates immediately. Doing so reduces exposure to intermediate values, and generally reduces downstream rework. But breaking cycles precisely requires knowledge of where the cycles are at – knowledge that I cannot obtain due to opaque processing and dynamic behaviors.

So for now, demand monitors in Sirea are working but their performance does not compose or scale very well. I may later need something similar to ln_touch just for detecting cycles, or some sort of static analysis.

An interesting property of cyclic feedback is that it’s also capable of representing volatile state:

tstCycle = monitor >>> bdelay 0.2 >>> addOne 
                   >>> bprint show >>> demand
  where addOne ls = if (null ls) then (0::Int) else (succ (maximum ls))
        (demand,monitor) = demandMonitor "tstCycle"

Here, tstCycle will, five times a second, add one to the highest monitored value and push it back into the demand set. After thirty seconds, the value will be 150, assuming no other influence or interference. This is essentially a model of delay line memory. Use of cyclic feedback to model state is not efficient, stable, robust, or recommended – but does serve as a nice demonstration of why RDP is essentially stateful despite having no local state.

The above tstCycle will actually aggregate memory – not by leaking it, rather by computing / anticipating too far ahead. I’ve developed a behavior `bfchoke` (in Sirea.Utility) to address the issue of anticipating too far ahead, but I’m still contemplating whether I should build something like that into the demand monitors.

(Aside: As an exercise, contemplate tstCycle and understand why it is spatially idempotent – e.g. why redundant computation of tstCycle at the same logical latency will not change the observed effects. By nature, all RDP behaviors are spatially idempotent. This is a useful feature: it enables refactoring or elimination of common sub-expressions, despite side-effects.)

Regular demandMonitor requires an `Ord` constraint, which ensures safe usage: the output list is ordered and without duplicates, representing a set of values. Unfortunately, this hinders use of opaque data types, such as dynamic behaviors. To address this, I also provide unsafeDemandListMonitor, which is just like demandMonitor except without the ordering or duplicate eliminations. This takes more discipline to use safely, i.e. to respect RDP’s invariants.

What’s Next?

The components used for demand monitors are useful for a few IO integration support concepts, i.e. to bridge RDP with Haskell IO. For example, variables that are automatically published to multiple observers, or that automatically gather signals from multiple sources. But that won’t take long (I’m mostly done already, after just a few hours on it). After that, in the short term I plan to implement a simplistic filesystem adapter, maybe a GLFW adapter (basic user input and visual output), and a few state models.

Over the last week or so, I’ve also been working on a more wholistic API user interfaces that aligns well with design principles and features of RDP. (E.g. RDP seems very well suited for variations on immediate-mode GUIs.) I’m leaning heavily towards a reactive application server concept. I would be targeting an abstract client API (also RDP based), and supporting occasionally offline systems but also runtime update while connected. I plan to write more on the subject in a future article.

About these ads
This entry was posted in Concurrency, Open Systems Programming, Reactive Demand Programming, State. Bookmark the permalink.

One Response to Sirea RDP Progress Update: Demand Monitors are Working

  1. wannabehacker says:

    Cool, can’t wait to try it to see if I can manage to understand how this stuff works.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s