Thursday, June 7, 2012

Reactive Programming

The last time we've been thinking "Are Variables Evil?" Now let's try to understand the ideas behind reactive programming.

The author of the Haskell library Reactive-banana writes:
At this point, I should probably explain the design philosophy that makes it all work. What led me to my library is the following question:
What is the essence of functional reactive programming?
A common answer would be that “FRP is all about describing a system in terms of time-varying functions instead of mutable state”, and that would certainly not be wrong. This is the semantic viewpoint. But in my opinion, the deeper, more satisfying answer is given by the following purely syntactic criterion:
The essence of functional reactive programming is to specify the dynamic behavior of a value completely at the time of declaration.
For instance, take the example of a counter: you have two buttons labelled “Up” and “Down” which can be used to increment or decrement the counter. Imperatively, you would first specify an initial value and then change it whenever a button is pressed; something like this:
The point is that at the time of declaration, only the initial value for the counter is specified; the dynamic behavior of counter is implicit in the rest of the program text. In contrast, functional reactive programming specifies the whole dynamic behavior at the time of declaration, like this:
Whenever you want to understand the dynamics of counter, you only have to look at its definition. Everything that can happen to it will appear on the right-hand side. This is very much in contrast to the imperative approach where subsequent declarations can change the dynamic behavior of previously declared values.

What is (functional) reactive programming?

In pure functional programming, there are no side-effects. For many types of software (for example, anything with user interaction) side-effects are necessary at some level.
One way to get side-effect like behavior while still retaining a functional style is to use functional reactive programming. This is the combination of functional programming, and reactive programming. (The Wikipedia article you linked to is about the latter.)
The basic idea behind reactive programming is that there are certain datatypes that represent a value "over time". Computations that involve these changing-over-time values will themselves have values that change over time.
For example, you could represent the mouse coordinates as a pair of integer-over-time values. Let's say we had something like (this is pseudo-code):
x = <mouse-x>;
y = <mouse-y>;
At any moment in time, x and y would have the coordinates of the mouse. Unlike non-reactive programming, we only need to make this assignment once, and the x and y variables will stay "up to date" automatically. This is why reactive programming and functional programming work so well together: reactive programming removes the need to mutate variables while still letting you do a lot of what you could accomplish with variable mutations.
If we then do some computations based on this the resulting values will also be values that change over time. For example:
minX = x - 16;
minY = y - 16;
maxX = x + 16;
maxY = y + 16;
In this example, minX will always be 16 less than the x coordinate of the mouse pointer. With reactive-aware libraries you could then say something like:
rectangle(minX, minY, maxX, maxY)
And a 32x32 box will be drawn around the mouse pointer and will track it wherever it moves.

An easy way of reaching a first intuition about what it's like is to imagine your program is a spreadsheet and all of your variables are cells. If any of the cells in a spreadsheet change, any cells that refer to that cell change as well. It's just the same with FRP. Now imagine that some of the cells change on their own (or rather, are taken from the outside world): in a GUI situation, the position of the mouse would be a good example.
That necessarily misses out rather a lot. The metaphor breaks down pretty fast when you actually use a FRP system. For one, there are usually attempts to model discrete events as well (e.g. the mouse being clicked). I'm only putting this here to give you an idea what it's like.

up vote147down voteaccepted
If you want to get a feel for FRP, you could start with the old Fran tutorial from 1998, which has animated illustrations. For papers, start with Functional Reactive Animation and then follow up on links on the publications link on my home page and the FRP link on the Haskell wiki.
Personally, I like to think about what FRP means, rather than how it might be implemented. So I don't describe FRP in representation/implementation terms as Thomas K does in another answer (graphs, nodes, edges, firing, execution, etc). There are many possible implementation styles, but no implementation says what FRP is.
I do resonate with Laurence G's simple description that FRP is about "datatypes that represent a value 'over time' ". Conventional imperative programming captures these dynamic values only indirectly, through state and mutations. The complete history (past, present, future) has no first class representation. Moreover, only discretely evolving values can be (indirectly) captured, since the imperative paradigm is temporally discrete. In contrast, FRP captures these evolving values directly and has no difficulty with continuously evolving values.
FRP is also unusual in that it is concurrent without running afoul of the theoretical & pragmatic rats' nest that plagues imperative concurrency. Semantically, FRP's concurrency is fine-graineddeterminate, andcontinuous. (I'm talking about meaning, not implementation. An implementation may or may not involve concurrency or parallelism.) Semantic determinacy is very important for reasoning, both rigorous and informal. While concurrency adds enormous complexity to imperative programming, due to nondeterministic interleaving, it is effortless in FRP.
So, what is FRP? You could have invented it yourself. Start with these ideas:
  • Dynamic/evolving values (i.e., values "over time") are first class values in themselves. You can define them and combine them, pass them into & out of functions. I called these things "behaviors".
  • Behaviors are built up out of a few primitives, like constant (static) behaviors and time (like a clock), and then with sequential and parallel combination. n behaviors are combined by applying an n-ary function (on static values), "point-wise", i.e., continuously over time.
  • To account for discrete phenomena, have another type (family) of "events", each of which has a stream (finite or infinite) of occurrences. Each occurrence has an associated time and value.
  • To come up with the compositional vocabulary out of which all behaviors and events can be built, play with some examples. Keep deconstructing into pieces that are more general/simple.
So that you know you're on solid ground, give the whole model a compositional foundation, using the technique of denotational semantics, which just means that (a) each type has a corresponding simple & precise mathematical type of "meanings", and (b) each primitive and operator has a simple & precise meaning as a function of the meanings of the constituents.
If you stick with these principles, I expect you'll get something more-or-less in the spirit of FRP.
Where did I get these principles? In software design, I always ask the same question: "what does it mean?". Denotational semantics gave me a precise framework for this question, and one that fits my aesthetics (unlike operational or axiomatic semantics, which leaves me unsatisfied). So I asked myself what is behavior? I soon realized that the temporally discrete nature of imperative computation is an accommodation to a particular style of machine, rather than a natural description of behavior itself. The simplest precise description of behavior I can think of is simply "function of time", so that's my model. Delightfully, this model handles continuous, deterministic concurrency with ease and grace.
It's been quite a challenge to implement this model correctly and efficiently, but that's another story.

Conal Elliott
Declarative Event-Oriented Programming
October 19, 1998
Technical Report MSR-TR-98-24 Microsoft Research
Events play an important role in the construction of most software that involves interaction or simulation.  Typically, programmers make use of a fixed set of low level events supplied by a window system, possibly augmented with timers and UI components.  Event handling generally involves some interpretation of these event occurrences, followed by external actions or modifications to program state.

It is possible to extend the event paradigm by using event interpretation to synthesize new kinds of events tailored specifically for a domain or application.  In turn, these new events may be used to synthesize yet others, and so on, to an arbitrarily sophisticated degree.  This programming paradigm, which we call  event-oriented programming, aids in the factoring of programs into understandable and reusable pieces.

We propose a declarative approach to event-oriented programming, based on a powerfully expressive event language with a lightweight notation.  We illustrate this new approach through the design of an interactive curve editor.


13 Conclusions

Declarative event-oriented programming makes it convenient to encapsulate significant portions of an interactive application into a set of high level, reusable building blocks. These events appear to capture important aspects of an application's design directly, and so may be useful in reducing the cost of creation and maintenance of modern interactive software.

As software becomes increasingly powerful, its internal complexity tends to grow. As Edsger Dijkstra pointed out in his Turing Award lecture, the ideas we can express, and even think, are greatly influenced by the languages we use. In order to achieve our software-building ambitions, we therefore need languages that support abstraction and factoring of algorithms to form “intellectually managable programs”.
One hopes that tomorrow's programming languages will differ greatly from what we are used to now: to a much greater extent than hitherto they should invite us to reflect in the structure of what we write down all abstractions needed to cope conceptually with the complexity of what we are designing. [5]

"Deprecating the Observer Pattern" - is another interesting paper on that topic. It is co-authored by Martin Odersky (Scala creator, Java compiler author). You can find an excerpt from it in the next article.

No comments:

Post a Comment