RDP Progress Report

The current implementation of Reactive Demand Programming (RDP) is a Haskell library called Sirea, and is available on github. The readme file for Sirea serves as a decent introduction to RDP, though I am sure it is lacking in some areas and rambling in others. Many source code files (but not all) further include a discussion on how each piece fits into the greater RDP puzzle.

In mid 2012 August, Sirea reached an alpha completion state – i.e. all the primitives are implemented and moderately tested.

The last primitives to be implemented were `bdisjoin` (which allows flexible conditional expressions) and `beval` (which allows runtime discovery of resources, staged computation, object capability model designs). I tested dynamic evaluation with a naively recursive implementation of Fibonacci function, and a simpler behavior that rotated through simple math functions in accordance with the clock.

An interesting feature of dynamic behaviors in Sirea and RDP is the extensive use of anticipation, which manifests as speculative compilation and evaluation. I only anticipate a few seconds in advance for dynamic behaviors, but that much ensures the behaviors are ready to go by the time I need them. (The real win is speculative resource discovery and acquisition, e.g. loading a configuration file seconds before it is needed and speculatively preparing or discovering even more dynamic behaviors according to the configuration. RDP has enormous promise for developing interactive and reactive applications.)

That said, Sirea (and therefore RDP) is not in a state for regular users.

At the moment, it lacks useful IO adapters. There is a discrete logical clock (deterministic; runs in logical time, but corresponds very closely to real-time) and some console output (print a string when it is known to be stable). While I initially found watching the current time print to console very exciting, that had far more to do with a proof of progress than actual utility. (It was certainly more interesting than printing “Hello, World”.)

Looking Forward

On my agenda right now is getting demand monitors working.

Demand monitors are essential for many development patterns in RDP, serving as a reactive blackboard system and a decent registry to publish dynamic behaviors for consumption elsewhere. Demand monitors are in some ways trivial, but a naive implementation would not be robust to cyclic references (where observed demands are transformed then fed back as new demands). Also, for stability, I’m providing a few variations of demand monitors (e.g. a variation that returns the k minimum values, or returns only whether some activity is present).

After demand monitors, there is still much I plan to do to make RDP usable and desirable in practice:

  • Simplistic filesystem integration. Initially, just ability to read and write small files. This can also serve as an initial UI model – e.g. set the RDP app to watch a file, save it in the text editor, and see reactions to the new file. Via dynamic behaviors, can serve as a reactive or live coding buffer. Part of being “simplistic” is that this won’t do much to properly handle concurrent demands to write the same file… just some arbitrary (but well defined) decision policy like “largest file in lexicographic order, wins”. I’ll leave it to developers to avoid concurrent writes to a file. I would like integration with inotify (in Linux) or FindFirstChangeNotification (in Windows); unfortunately, I have been unable to find a portable library for watching filesystems.
  • Real time user input: ability to observe keyboard, mouse, and joystick. I am considering SDL and GLFW for this role, though I am not entirely happy with them. Ideally, I would like the precise timing information that is available from DirectInput (in Windows) and /dev/input (in Linux). Precise timing of input can greatly improve the user experience. And I’d like to separate the module for the input system from the window system.
  • Windowed visual output. I am thinking either Cairo or OpenGL. I have not decided how to handle concurrent display requests, though I am thinking that I may model a simple window manager with declarative layout and z-ordering. (Use of a stateless stable model is very promising for a layout role.) Long term, I would like to consider use of GPipe or an RDP-based variation for high-performance output.
  • State models. RDP uniformly treats state as an external resource. This has some very nice advantages: it allows orthogonal persistence, easy auditing of state, and separate upgrade of the application and state. Sirea will be persistent by default, probably via acid-state. The declarative semantics associated with RDP avoid many disadvantages commonly associated with shared state concurrency! Unfortunately, RDP cannot use the traditional imperative state models (sequenced `get` and `set` operations). For RDP, I need declarative state models: tuple spaces, state transition systems (cf. reactive state transition), and term or graph rewrite systems (cf. reactive term rewriting), potentially discrete event systems. (Fortunately, another advantage of having state as an external resource is that it becomes relatively easy to orchestrate many heterogeneous models of state.)
  • Plugins and Live Programming support. My current design for Sirea plugins will support concurrent `main` behaviors (thus allowing the toplevel for a Sirea application to represent a multi-agent system) and support type-driven dependency injection (type-matching via Data.Typeable). If there are multiple instances for a given type, only one shall be injected (chosen based on a simple priorities and constraints) but the other instances can serve as robust backups in case policies change or the plugin changes (e.g. during edit). A toplevel agent can also inject resources dynamically, assuming it asks for the plugin-system’s type, which can result in applications that are very adaptive to their current environment. Haskell does have effective support for plugins, via System.Plugins or hint. Ultimately, I would like to start most Sirea applications before I start editing them. I would like `sirea` to be a command-line application that simply runs a (live, reactive) configuration file that specifies a bit of initial policy plus which plugins, directories, or more configuration files to load – basically develop Sirea applications as a blank slate plus plugins.
  • Sound and Music output. I’m not entirely sure how to adapt sound output to a reactive paradigm. From what I’ve studied so far, there seems to be some state involved – e.g. a cursor moving through a spatial representation of a sound – and I’d like to approach the bare essentials in that respect. I look forward to studying the Haskell School of Music and much of Henning Thielemann’s work (e.g. live-sequencer and reactive-balsa). I have an interest in programming music that I haven’t had much explored since middle school. I am not sure how much RDP will help with the sound specification, but it should help integrate sound with other applications and real-time user inputs.
  • Traditional WIMPy GUI integration, most likely GTK or wxWidgets. This is low priority for me; I think traditional windowed GUIs are a common source of awful (e.g. with respect to composition, cooperative work, mashups, replay and testing, reuse, and scalability). WIMP is a systemic evil, like slavery or prejudice – “just the way things are,” until they’re not. RDP was designed for a much larger vision for ZUIs and live documents, a paradigm close in nature to the web-applications concept (albeit differing in terms of implicit client-side state). However, I expect RDP will gain wider acceptance after it proves to support traditional paradigms. One idea I have to make WIMP at least slightly less intolerable is to favor an unhosted approach to the retained-mode state – i.e. the state may still exist, but every stateful field (text, list, radio button, checkbox, scrollbar, cursor) will be pushed to client-controlled state and reactively updated from it. This gives the client more control over state, and more uniform ability to observe or influence it reactively, and will result more readily in persistent applications. Persistence aids scalability and auditing, since it means we can close the windows we don’t need without losing valuable information. I’ve done this sort of layering a few times in my dayjob but I expect it will be no less difficult this time around than it was in previous efforts.
  • Reactive Web App Server. I could probably model a more traditional HTTP server in RDP using an intermediate blackboard or something, but I don’t see a point – for the traditional web services, Yesod or Happstack will do it better, and RDP would mostly be unnecessary overhead. However, an RDP-based web server may do very well for real-time interactive web-apps, where the server must maintain a long-lived connection to continue updating the page and vice versa. I have some ideas on how to approach this. The RDP app, for example, might specify a `dynamic behavior` and register it against a URL. When a client attaches to the URI, then, they’d essentially initiate a session with that dynamic behavior. Most likely I’ll leverage websockets or Socket.IO.
  • Alternative state models: stateless stability, decaying history, machine learning (ant clustering, bloom filters, weighted search tactics), etc. I might target some of these earlier as they could be very effective for deciding plugins, window layout, etc.
  • Adapt more data sources: HTTP (with caching), SQL, DDS, Redis, Datomic, etc.
  • Adapt more input sources: camera, microphone, LEAP, etc.
  • Vision processing libraries. Vision processing fits reactive dataflow very well, and RDP can also cover the feed acquisition issues easily.

Very little of this will affect sirea-core, though there might be some common elements I decide to port back. At this point I’ll be developing multiple Sirea modules for different roles and adapters, and eventually I’ll get around to implementing the plugins system and adapting the existing modules to it. I could probably use help at this point, since many of these could be developed independently, but I don’t expect much until I’m a bit further along for demonstrations.

For demonstrations: RDP will also need several proof-of-concept applications. I have a few in mind, but I might start with a simple game and world-building utilities. I’d like to try something in metroidvania or megaman style, but with a bit of puzzle-adventure or interactive fiction aspect to it. And I’d like something extensible – e.g. where regions of the world can be accessed, linked, and updated via HTTP or similar. I think I could cover a wide variety of IO and performance aspects. (The main problem with “simple game” seems to be that it doesn’t stay “simple” for very long.)

Looking Back

The efforts on Sirea began in 2012 March. My prior effort to implement RDP was called RDPIO. RDPIO started in 2010 October, but by January 2012 was lost deep in some abstract rabbit hole caused by premature generalization. I lack the motivation to recover the library. Sirea was developed with an intention of covering a representative but far more concrete implementation of RDP, so doesn’t attempt to cover all the corner cases (such as distributed programming or continuous signals).

Sirea was inspired significantly by the FRP.Sodium library.

In particular, I loved how Sodium used types for partitions and automatically created a thread per partition (leveraging Haskell’s Data.Typeable). One of my regular complaints while working with RDPIO was the “setup” issues: a developer would need to explicitly spawn the partitions, wrap RDP behaviors around associated resources, then compose those RDP behaviors from the bottom up. All this setup effort was performed in a monad, and severely distracted from a declarative programming experience! Another complaint for RDPIO was that I had no easy way to reason about where to perform `zip` operations and similar: to combine two signals, requires they coincide in time (synchronized) and space (same thread), but which thread was left to an optimizer and difficult to predict or control. Partition types require developers to use explicit `bcross` to decide on a partition before zipping, which was nice.

Basically, the notion of partition types solved two problems I was facing. Similar to FRP.Sodium, Sirea will associate each partition with a different thread (which is created the first time a partition is used), and partitions themselves may be declaratively associated with resources. This makes it very convenient to create a Sirea app that, for example, monitors the filesystem: you just `bcross` to a `Filesystem` partition, then ask for a certain file. To integrate resources with behaviors without building the resources in advance, Sirea provides a partition context object (Sirea.PCX) which logically carries one resource of each type, available for discovery on demand. Thus, types are used to name some resource or FFI adapters.

Partition types also introduce a challenge: with partition types, certain operations (especially disjoin and dynamic behaviors) cannot be fully generic with respect to type. It took me some time to reconcile disjoin with partition types – i.e. I really couldn’t “disjoin at a distance”. Eventually I found a way – a typeclass constraint to specify all signals are in one partition; this was also applied for dynamic behaviors (i.e. all signal inputs to a dynamic behavior must start in the same partition).

I fear Sirea’s current partitions and PCX model might not translate well to my plugins design, mostly because I’ll need more precise ability to safely shutdown and restart threads owned by different plugins, and to more cleanly separate resources provided by different plugins (prohibit direct bindings between them). However, I’m willing to replace the model (or layer atop it) if and when it becomes necessary.

Sirea uses the vat model developed for RDPIO, but a more implicit and simplistic version of it. In RDPIO, I forced everyone to use a particular monad per vat – which proved a mistake for adapters that need their own event loop (e.g. if I was using GLUT, which I’m not). In Sirea, the RDP event loop in each thread (including the main thread) is externalized into a `Stepper` object (which has a runStepper operation and a couple callback hooks). This makes it easy to integrate Sirea with any other event loop.

Sirea is also based on an arrows model, much like RDPIO. Sirea’s arrows are not compatible with Haskell’s arrows, nor quite compatible with Adam Megacz’s generalized arrows. Consequently, there is very little syntactic sugar go local variable names; arrow code is almost point-free (though one can use freely variables from a prior `stage` of computation, e.g. the function that builds the arrow). Arrows are unfortunately intimidating to the newcomer, though they are easy to use (much like pipelines in a command line) once you get used to them. I might eventually develop some sugar for Sirea, if I ever learn enough Template Haskell to try it.

This entry was posted in Language Design, Reactive Demand Programming. Bookmark the permalink.

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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s