Reactive Programming

Whatever happened to reactive programming? FRP in particular -- there was a flurry of activity at Yale over the past decade or so, but it appears to have petered out, and nobody else has picked up on it or tried variants.

(By "reactive programming" I mean using the "signals and systems" paradigm to building a real-time program, (e.g. as in Labview or in some signal processing languages), but fleshed out enough to have a coherent semantics and to be able to do all the other things a PL needs to. Most attempts at this from the programming languages mainstream, dating from Lucid, have tried to use streams...)

--Josh

Still pretty active

Javascript FRP
OCaml FRP
Recent discussion which brings up FRP in scheme and a couple of Java related DSLs
A recent paper about optimizing Yampa
The latest version of .NET (3.0) XAML has something called dependency properties which seem 'reactive.'

By falcon at Sun, 2007-02-11 17:12 | login or register to post comments

SuperGlue is also related to

SuperGlue is also related to some extent.

By Sean McDirmid at Mon, 2007-02-12 14:16 | login or register to post comments

Thanks!

Good stuff, and quite recent. I could see FlapJax catching on big-time if web programmers realize what it gets them.

It'll take me a little time to read thru all the papers/docs, so in case anybody knows offhand: Do any of these projects handle handle the creation of implicit state via directed loops in the dataflow graph?

--Josh

By J Storrs Hall at Sun, 2007-02-11 22:26 | login or register to post comments

Offhand, no

I know Yampa doesn't, and neither does my own system (O'Caml RT). I'm pretty sure neither Flapjax nor FrTime do but I haven't delved into their internals much. In fact it never even occured to me to use directed loops to model state (I've tried my best to avoid loops personally!) but it sounds like it could be a pretty good idea.

By Chris King at Sun, 2007-02-11 23:26 | login or register to post comments

Loops and implicit state

One of Peter Welch's presentations on JCSP includes some examples of using loops to create implicit state (although in the context of concurrent programming ala occam, rather than FRP).

By Allan McInnes at Tue, 2007-02-13 03:41 | login or register to post comments

collect

Yampa has a loop construct and FrTime collect and accum:

collect-e :: event[a] b (a b -> b)) -> event[b]

Additionally, there is a switch statement ( Event[Event[a]] -> Event[a] ). What would you want to do that could not be encoded functionally by using them?

FrTime requires a topological ordering on nodes in the graph, so an actual cycle would break the evaluation engine. Flapjax allows optional non-topological evaluation as a matter of convenience and performance, but doing so means the programmer can then introduce 'tight-cycles', which are feedback loops that starve the system (like paradox aspects).

Perhaps I misunderstood your question. Because constructs like collect conceal state but still have it, and switch is a powerful construct in itself, there have been a few papers about formal frp properties from Paul Hudak. Real-time FRP also needs to be very careful about it.

By lmeyerov at Mon, 2007-02-12 15:50 | login or register to post comments

loops and fixed point

A lot of interesting things simply requires loop, or fixed point constructors, as does FRP or signal processing in general.

In Yampa terms, if we have (equivalent to Yampa's loop combinator)

fixSF :: SF a a -> SF b a

that makes the output signal loop back to the input signal for the given SF a a, and wrap it in a new signal function that duplicates the output while ignoring any input (as it doesn't need any). Then we can define:

--exponential
eSF = fixSF (integral >>> arr (+1))
--sin wave
sinSF = fixSF (arr negate >>> integral >>> arr (+1) >>> integral)

simple and elegant.

But Yampa as of its current status is still pretty theoretical and not suitable for any soft- or hard- real time systems.

By alanine at Tue, 2007-02-13 00:23 | login or register to post comments

flip-flops

I wasn't asking about the loops because I wanted to use them specifically -- indeed, hardware designers almost always sequester state in latches and registers because it's hard to keep track of and get right if implicit in the general circuit (not unlike gotos in sequential code).

It might be useful to compare memory primitives in the different reactive language paradigms...

BTW, what's the function of "arr(+1)" in Yampa? Exp is a solution of

f = integral f

and thus a fixpoint of integral, and sin is a solution of

f = integral integral -f

likewise, so I don't see what the arr(+1) is for. Does it have something to do with the fact that the constant function 0 is also a solution of both equations?

Josh

By J Storrs Hall at Tue, 2007-02-13 20:07 | login or register to post comments

arr would raise f :: a -> b

arr would raise f :: a -> b into the signal function domain arr f :: SF a b.

Expoential starts with 1, so natually the output signal from integral is added by 1 before it loops back, which is just a way to give initialization value other than 0 to the integration.

By alanine at Fri, 2007-02-16 00:57 | login or register to post comments

aha.

Thanks.

By J Storrs Hall at Fri, 2007-02-16 01:21 | login or register to post comments

incremental queries

reactive programming is fundamentally about incremental computation, but without a way of handling collections (i.e. incremental evaluation of queries over collections), its fundamentally limited.

By dmorton at Wed, 2007-02-14 21:52 | login or register to post comments

is it?

I didn't realize that reactive programming couldn't handle collections. If one is doing a fold/map/filter, why couldn't it be dealt in the same manner as processing lazy lists?

From what I recall, at least FrTime, separates continuously changing behaviors from instantaneous events by putting events in a collection, to be processed by frtime. One of the FrTime even mentions continuously updating database queries as one of the possible applications of this technology.

By falcon at Thu, 2007-02-15 00:38 | login or register to post comments

The problem is that

The problem is that fold/map/filter have to be defined recursively in a pure functional language. If you are dealing with a database with thousands of entries, it is not realistic to re-process the whole list if one element is added or removed. I'm not sure what FrTime does (waiting to read Gregory's thesis :) ), but this was something that I had to address in SuperGlue. My solution (still in progress) is to interpret a SQL-like syntax in a reactive way. e.g.,
uiList.entries = ebay.auctions(item = ipod, bid lessthan whatIWantToPay).startDate;
This creates an array signal that filters a list of auctions by two parameters (the item and price) and then does a map. Filter and map are basically built-in to the array signal abstraction so that code behind handles them directly, rather than evaluating the operations with a loop or something horrible like that. What is kind of difficult is that the list of auctions can change; new auctions are added, old ones are removed; the parameters of the auctions can change, e.g., the bid price can be raised; and the parameters of the filter can change; e.g., I might be willing to pay more. All kinds of changes must be handled efficiently through diffs of the signal array (blocks of elements added or removed) rather than recomputing the entire filter over and over again.

This is sort of related to relational programming or array-programming.

By Sean McDirmid at Thu, 2007-02-15 07:14 | login or register to post comments

how does sql solve it?

Sean,
I didn't quite get how an interpreting sql-like syntax (non-turing complete, non-recursive?) in a reactive way solves the problem.

Do you mean that instead of thinking in terms of low level fold/filter/map, you provide a declarative description and let the implementation optimize any way it wants?

For example, say I am showing a user the running sum of items he has bought at an auction (updated with each purchase). Let's say we define this as a very simple sum [itemprice1, itemprice2, ...] where the usual operations of a collection (or an sql table) are available. What if they sell an item...remove an item from the 'ownership' collection. How can any formalism understand that we need to subtract the value of the item from our sum? Even if we tell our system that the opposite of + is -, how are square_roots handled?

As far as I can tell, 'constantly updating databases' don't handle stream queries that involve updates or deletes.

I'll go over relational programming in PVR's book. Let me know if there is a specific section of your dissertation I should study. This stuff is not as simple as I had assumed :)

By falcon at Thu, 2007-02-15 15:29 | login or register to post comments

I haven't really published

I haven't really published any of this, so there is nowhere to look. The real point is to have a SQL-like interface between the high-level reactive language and the lower-level more-expressive code that provides access to the data. E.g., the provider of the ebay object makes its mutable data available via an SQL-like interface, which directly supports filter, map, and change.

If you are thinking in terms of a pure reactive language, I don't think this model is very useful. The problem with a pure functional approach is that there is no natural way to encode arrays of data, at least, not unless it is through a cons list. A language that supports arrays directly (someone mentioned APL) would be a better fit, but the interfaces used in these languages is very similar to a relational language.

BTW, the Yampa people seem to solve this problem through dynamic switchable collections (see Andrew Courtney's thesis), but I've never been able to figure out how there solution works.

By Sean McDirmid at Thu, 2007-02-15 21:13 | login or register to post comments

thanks

...looking forward to your paper then!

By falcon at Fri, 2007-02-16 00:02 | login or register to post comments

The live editing paper will

The live editing paper will come first, which is what I'm working on now, it makes for a better demo :)

By Sean McDirmid at Fri, 2007-02-16 07:02 | login or register to post comments

isomorphism exists between

isomorphism exists between an array of signals and a signal of array. So ineed what you wanted to do is already expressible in FRP. And if you worry about efficiency of list, you always replace list with array or any other collection type you like. I don't see a problem here.

On the other hand, if what you want is a collection of signal functions coupled with complex switch construct, there it could be a bit problematic as this area isn't well studied. Yampa has a way to handle it, but there could be better approaches.

By alanine at Fri, 2007-02-16 01:11 | login or register to post comments

delta propagation

What is kind of difficult is that the list of auctions can change; new auctions are added, old ones are removed; the parameters of the auctions can change, e.g., the bid price can be raised; and the parameters of the filter can change; e.g., I might be willing to pay more. All kinds of changes must be handled efficiently through diffs of the signal array (blocks of elements added or removed) rather than recomputing the entire filter over and over again.

This is sort of related to relational programming or array-programming.

I recently started toying with intuitive approaches to signal arrays (and yeah, I think FrTime automatically converts all list signals into signal lists). The initial motivation was that I like still allowing callbacks some times, so arrays are also implicitly functions of push/pop/etc streams. That means I can cheaply propagate what a delta is, and if the array is constructed by something like a fold, I can, in the worst case, walk it to estimate the tightest splice estimate that would account for the delta.

Modification of nested objects is much more subtle to me. I'm also curious about optimizations made when implementing db triggers; there might be some lessons learned.

By lmeyerov at Fri, 2007-02-16 02:52 | login or register to post comments

incremental

If the only operations you have are simple scalar functions, and the only way you have of dealing with collections is one datum at a time, that would indeed be limiting.

Imagine, however, a "reactive APL", where an input signal is a whole raster array from a video camera and an output signal likewise:
mask <- in = blue out <- (in × ~mask) + background × mask
You've just implemented chroma-keying.

The same basic idea could apply to an entire database, if you have the paradigm to treat it as a single, parallel, value.

Josh

By J Storrs Hall at Thu, 2007-02-15 01:40 | login or register to post comments

oh transputers/cm5/niagara/etc., where art thou?

Seems like true massive parallelism is potentially really useful, but I guess is still relegated to special-purpose or niche areas? It would be super dandy if desktops really did have 128+ processors, each with decent memory, so everyone could investigate how to take advantage of that even in our daily boring desktop apps. Perhaps there has been a perceived lack of good languages for massive parallelism?

By raould at Thu, 2007-02-15 20:55 | login or register to post comments

or Intel's new teraflop chip

... 80 cores on one chip!
I conjecture that reactive paradigms will help us handle the programming of these things.

Something had better...

Josh

By J Storrs Hall at Fri, 2007-02-16 01:29 | login or register to post comments

Lambda the Ultimate

User login

Navigation