## 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

## Comment viewing options

### 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.'

### SuperGlue is also related to

SuperGlue is also related to some extent.

### 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

### 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.

### 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).

Hi Chris, the http://users.wpi.edu/~squirrel/ocamlrt/ URL seems to be dead, is there a newer link to that page?

### 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.

### 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.

### 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

### 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.

Thanks.

### 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.

### 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.

### 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.

### 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 :)

### 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.

### thanks

...looking forward to your paper then!

### 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 :)

### Antony Courtney

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.

I think you are referring to Antony Courtney.

I tried finding this thesis today, it only took me two hours :)

See: Modeling User interfaces in a functional language -- unfortunately, requires a ProQuest subscription, or a one-time purchase fee

Note to LtU users: it can be a considerable nicety to other users to provide hyperlinks, rather than make people search, especially when you may have better search keywords in mind than the unacclimated searcher. If you read a paper, consider logging it in CiteULike, a Tumblog, or some other mechanism for tracking papers. I have also heard good things about the Mac app Papers. Such a tool will let you more easily find papers to link when something crosses your mind as relevant to LtU discussion.

### I believe Functional

I believe Functional Reactive Programming, Continued, by Antony Courtney and others, also contains some discussion on dynamic collections in FRP:

[...] In this paper, we describe the AFRP programming style and our Haskell-based implementation. Of particular interest are the AFRP combinators that support dynamic collections and continuation-based switching. We show how these combinators can be used to express systems with an evolving structure that are difficult to model in more traditional dataflow languages.

Perhaps this is the one Sean was referring to.

### 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.

### 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.

### Has there been any progress

Has there been any progress on the best way to represent and implement these deltas?

### Reactive Programming and Delta Propagation

I'm also interested in historical progress along these lines.

As I understand it, the problem is two-sided:

First, you must properly identify and isolate deltas. It helps if the API to the data resource can be captured as a history of deltas: for SQL, deltas may be DML operations; for a persistent structure, deltas may be T->T lambda transformations; for an object graph, deltas may correspond to a command API (akin to Prevayler). This first part is made considerably more difficult if the API involves replacing a whole construct, as then (if you want delta propagation) you must isolate differences in a separate operation (i.e. creating a patch or diff file) and 'lazy' updates may become difficult to achieve. OTOH, having deltas orthogonal to the API may offer other advantages.

Second, you must propagate these deltas across functional transforms. This is the place I'm having trouble; for flexible deltas (like T->T transforms, even in a total language) I'm not even sure it can be done 'in general'. But, even if it cannot be done 'in general', I'd really like to identify places where it would be profitable and feasible to perform the delta propagation.

Does anyone know of good papers on the subject of implementing delta propagation?

### That particular experiment

That particular experiment didn't have enough motivation to keep going and I've switched topics away from FRP for the last ~2 years (though, as explained later, I might be somewhat returning).

I think the state of the art comes down to Tom Rep's old work in incremental attribute grammars which shows theoretical optimality and pretty much no performance results/evaluation and then Kim Burchett's paper saying getting rid of incrementalism in FrTime is often good. Acar attempted to claim otherwise recently with his more explicit approach, but his examples/evaluation seemed contrived. Getting 'optimized' support for collections/data structures etc. is thus standing on murky ground (and I haven't seen anything about it).

However... for my parallel browser / CSS engine work, now that I have algorithms for initial parallel layout / rendering, I'm revisiting the incrementalism problem for interactions/animations (and will likely attempt to avoid the array problem by restricting my specification language to something similar to attribute grammars!). This is scheduled for the summer; before then, I think I'm going to performed retained mode CSS rendering and add pixel shaders to CSS / formally specify CSS / generate a parallel (initial) CSS layout engine o_O.

### We've been doing incremental

We've been doing incremental layout for a couple of years now, but through a physics engine. The physics engine is essentially a constraint solver that can (a) easily run on the GPU, and (b) is optimized at solving spring constraints (think, any layout you could possibly want!) and (c) is very incremental (in fact, you might not get to a stable solution for more than a few frames, depending on the strength of your constraints). Also, for natural user interfaces (Surface, iPhone), you don't have much choice beyond using physics.

This is why I think physics might be a better paradigm than FRP in long run.

### I presume you mean physics

I presume you mean physics is superior for UI layout and animation, and not for reactive systems/dataflow-dependencies in general? If that's not what you meant, perhaps I don't understand what a physics engine implies.

### Physics is more

Physics is more constraint-oriented than FRP, although many will argue that FRP is very similar to constraint-oriented programming in the first place. Physics can make sense for a reactive system, and is fundamentally more expressive than FRP in the kinds of reactive systems that it can support. The dataflow dependencies that you can express with physics are more expressive because cyclic dependency are perfectly reasonable and...actually useful. Consider keeping two boxes next to each other according to two constraints:

boxA.right = boxB.left;
boxB.left = boxA.right;


This would look like non-sense in FRP but works fine in physics if each constraint is only partially satisfied (say 50%) per solution cycle.

### A slight aside: FrTime

A slight aside: FrTime supports dynamically reconfigurable reactive expressions, but this seriously complicates the implementation. How necessary are these in practice? Does anyone have any anecdotal evidence they'd like to share on their relative importance?

### Live programming is an

Live programming is an obvious use case for dynamically reconfiguring reactive expressions. Beyond that, if you have a sufficiently expressive graph to begin with and no imperative forces acting on the graph, I don't think dynamic reconfiguration is necessary. However, allowing for graph mutations is fairly pragmatic.

### I wouldn't think Bling

I wouldn't think Bling supports dynamic reconfiguration since it compiles these expression to the GPU. Or if it does, it would require fully recompiling at least the changed part. Is this what happens?

What sorts of imperative forces would act on reconfiguring the graph itself, in such a way that these changes cannot be exposed as signals themselves?

### The part of Bling that

The part of Bling that compiles to the GPU is not related to FRP (Bling also isn't real FRP, just sugar around databinding or physics). All change propagation is handled on the CPU, and we simply refresh shader inputs and re-run the shaders on the new inputs. This would include state that is maintained on the GPU itself (though telling that state has changed is a lot harder when the data is on the GPU...).

Right now, you cannot live edit Bling code, since it's C#. But if you could, we could simply compile new shaders and reconfigure the GPU to use these shaders.

IF you are building a pragmatic system, a mutable assignment hammer might be useful, even if its not very clean. But you are right: you can probably express all behavior as part of the graph's immutable structure, depending on how expressive your graph composition language is.

### How necessary are these in

How necessary are these in practice? Does anyone have any anecdotal evidence they'd like to share on their relative importance?

It's super useful if you're doing stuff like dynamically loading content (e.g., shopping cart elements based on a search result) and want to be able to interact with them.

However... reading code with 'switch' can get confusing unless well documented. Imperatively switching connections is often a clearer alternative, but obviously unpleasing from a purist view.

Not sure why you say it's such a problem to implement (unless you have particular optimizations in mind..).

### Yes, the FrTime approach

The FrTime approach with weak references gets pretty hairy on .NET, and the overhead is significant when compared to native primitives for event handling and dispatch. So yes, I was speaking from an optimization perspective.

I instead implemented a sort of phase separation between building a dataflow graph, then "compiling" it to a more "flat" representation that exploits the CLR primitives. It turned out to be pretty simple, but obviously some of the dynamism is lost. Higher-order signals may still be possible though, in which case I may need those weak references after all.

In any case, I'm still toying with it, so perhaps I'll find a better approach.

### I instead implemented a sort

I instead implemented a sort of phase separation between building a dataflow graph, then "compiling" it to a more "flat" representation that exploits the CLR primitives. It turned out to be pretty simple, but obviously some of the dynamism is lost. Higher-order signals may still be possible though, in which case I may need those weak references after all.

This is similar to Bling: if you create a data binding dynamically, at that point...when the binding is created, Bling will use Linq to generate code for the binding. Linq/DLR is pretty fast though, so it shouldn't be much of a performance drain if you generate small chunks of code dynamically. However, if you are dealing with the entire graph as one big chunk, then you might want to add some modularity to the graph so you can separately rebuild chunks of the graph as needed. Bling or SuperGlue doesn't have this problem, as we don't have an explicit graph (and consequently, we don't bother dealing with glitches that result from not having a graph).

### Wow, that clears up a lot

I'm wondering if you can still get a notion of glitch-free semantics from this by restricting the language a little and/or being careful in how to compose chunks. Will need to let that swish around my head for a bit :)

### Weak references also 1)

Weak references also 1) become a concerning performance point once you really stress the implementation and 2) a semantic concern when allowing side effects on expressions (so if collection is not immediate upon losing a reference, as is typically non-deterministically delayed with weak reference implementations), you can run into unexpected behavior. In short, they make implementation easy in PL-y languages... but I'm not sure if they're a good idea from other often necessary metrics in general language design.

After the incrementalism problem and maybe the usability of switch or interface with parallelism/side effects, this might be next on my list of implementation concerns about FRP for GPLs.

### How would you implement

How would you implement dynamic reconfiguration with efficient push-driven update, but without weak references? Or is there another non-push-driven update technique I'm not considering?

### Implement w/o Weak Refs

What makes you believe weak-refs are necessary? Is it something specific to dynamic reconfiguration?

If you keep dynamic reconfiguration to certain points in the FRP expression, it certainly becomes a lot easier to support dynamic reconfiguration. I.e. you could use a cell to carry an FRP expression, then have an explicit FRP primitive to dereference another FRP expression. I do not see where weak references would be useful in this design. The capability to tweak the expression would simply be a capability to affect the cell.

Are you assuming auto-lifted FRP expressions?

### Not dynamic reconfiguration

Not dynamic reconfiguration on its own, but dynamic reconfiguration with push-driven update. This implies a bidirectional relationship between nodes that requires one arrow be weak to properly collect dead child nodes.

What I'm trying now is to build in a notion of signal completion, which propagates a cleanup event that unregisters listeners for any completed signals. So far it seems doable, but it obviously depends on the source signals being properly "completed" when no more values are forthcoming.

### bidirectional relationship

bidirectional relationship between nodes that requires one arrow be weak to properly collect dead child nodes

I see.

This doesn't actually take a weak-ref. What you're depending on is a state-change (in this case, a weak-ref becoming null) to signal that an element is no longer needed. Given destructors and reference to shared state, the same sort of state-change can be effected without any bi-directional references.

I agree with using whichever your GC supports, though. Not all GCs support destructors.

a notion of signal completion, which propagates a cleanup event that unregisters listeners for any completed signals

Yeah, I can see the utility in doing so. I plan to do something similar for FRP in my language by separating the update and access capabilities for cells. If the update capability is collected, then the signal is in a final state and all access can be finalized (which has some nice optimization properties). If the access capability is collected, then all future updates are pointless and all update infrastructure (any objects transitively annotated to 'depend' upon that update capability) can be destroyed in a clean little cascade, and further messages may be dropped.

### Given destructors and

Given destructors and reference to shared state, the same sort of state-change can be effected without any bi-directional references.

I tried coming up with some representation using shared state, but nothing was satisfactory. If you have some efficient representation in mind, I'd love to hear it.

Using shared state like this opens up the possibility to abstract the signal network's state, which is particularly attractive for applications where a single signal network could be shared by multiple clients, for instance, a web framework: request comes in, restore signal network state scoped to that request, process updates, save the new state. The best I've come up with here is some sort of dynamically scoped variable backed by thread-local storage. I'm not using it now, but I'll probably try it out at some point.

by separating the update and access capabilities for cells. If the update capability is collected, then the signal is in a final state and all access can be finalized (which has some nice optimization properties).

Coincidentially, this is the exact approach I'm implementing. The link I provided above shows that I already have a capability for inputting values into a signal (RefSignal<T>), and now that I've added a completion event, I was considering whether to raise this event in the capability's destructor. As you said, I think that should properly handle all resource cleanup, assuming the combinators registered proper cleanup handlers.

### I tried coming up with some

I tried coming up with some representation using shared state, but nothing was satisfactory. If you have some efficient representation in mind, I'd love to hear it.

I do not believe the shared state approach is any more efficient at the small scale than is the weak reference design.

But, as you note, the greater flexibility may offer some performance enhancements at the large scale regarding multi-cast (i.e. sharing common subgraphs), distribution, lazy computation, implicit caching, partial memoization. Given my focus on scalable composition, I consider such optimizations to be among FRP's finest attributes.

### I can't comment on it much,

I can't comment on it much, but I've seen similar implementations in both high-level languages and more C++-like ones. I believe Arjun Guha started adding something similar to Flapjax for cleaning up DOM event handlers.

It's still a problem, especially as you scale, going more fine-grained/low-level and including more code. Doing some sort of bulk optimizations / graph compactions / parallel traversals etc. to give magnitude+ improvements seems key. There are other issues here too, like decentralizing for local/independent computation. Good stuff :)

### As you said, I think that

As you said, I think that should properly handle all resource cleanup, assuming the combinators registered proper cleanup handlers.

Actually, this isn't true. Consider a trivial case:

(C, CRef) = signal.make 2
B = C + 1

Now lose the reference to B. B is still live because C has a registered handler to push updates to B, even though it's no longer accessible. So parent->child refs seem to require one of:

1. a weak parent->child reference
2. explicit disposal of the child signal

I can see how C++ can handle this with smart pointers by simply not counting any parent->child pointers. I can't think of a way to detect that "the only live references are parent->child push pointers" without weak refs or explicit disposal in a GC'd language.

In some cases, this explicit disposal can be done automatically. For instance, the LINQ TakeUntil combinator which specifies an explicit termination condition for the child signal. However, a good approach for the general case seems elusive.

### Now lose the reference to B.

Now lose the reference to B. B is still live because C has a registered handler to push updates to B, even though it's no longer accessible.

The B in your example shouldn't even register a callback inside C. B is not an 'observer' of the expression - that is, the mere existence of B places no demand to keep C up-to-date. B, instead, should be considered a name for a description of a reactive expression. B could be evaluated like a normal expression. Only when someone creates a subscription to B would any callback registration be needed. In that case, the subscription object itself could be a location for shared state and recipient of callbacks.

Now, assume object S exists to reify the subscription by associating the resources with necessary callbacks. In this case, at least one of those callbacks will reference an observer O. But neither the observer nor the data resources need a reference directly to object S. In this case, if a reference to S is dropped, S's destructor may automatically and explicitly unregister O from the expression.

This gives you the flexibility of dissociating the callback registration from the observer (which simplifies object APIs) and dissociating demand from description (allowing the system to become far more demand-driven, which is very useful). If all references to S are lost, S's destructor will ensure everything is cleaned up appropriately. S may also support such features as 'make_permanent()' should you wish it, allowing you to drop S without losing the callbacks.

### Ok, I think I see where

Ok, I think I see where you're going. So you delegate to clients when to actually observe a signal, which should significantly reduce the number of subscriptions, but not eliminate them outright. Then you add an abstraction to mediate subscriptions. Let me see if I have the taxonomy right:

• Signals: sources, or compound expressions on sources. The only operations are signal combinators, which produce compound expressions, and an explicit Subscribe function, which produces a Sampler and registers a callback with the source to notify the sampler of any changes.
• Sampler: reifies a subscription and mediates all callbacks between clients and signal sources. Clients can't register callbacks with a signal or operate on signal values, but they operate on Samplers to operate on values and register callbacks. If a reference to a given Sampler is lost, the Sampler destructor unregisters itself and all callbacks registered via that Sampler, from the signal source.

Does that about sum it up?

### Yep. That's good.

This falls along those all-pervasive 'another layer of indirection' and 'reify that which was implicit' principles.

### What happens if you ask for

What happens if you ask for a Sampler on a compound Signal? Now the compound signal has to start listening to its inputs (and if the input is also compound that one has to start listening too). If you destroy the Sampler how do the compound signals know if they should stop updating, maybe there are other samplers on them. It seems like you'd need to keep reference counts. And if you have cycles you'd basically need to write your own GC?

Is that right or am I missing something?

### I'm not sure how David's

I'm not sure how David's scheme supports compound signals, but what really loses me is the "explicitly uninstall observer" part. The sampler has to be able to reproduce the computation that installed the observer in the first place, or has to maintain a list of where the observer is installed, thus potentially creating a vicious GC cycle.

One of my main implementation techniques is to implicitly uninstall observers when they are used, and then not have to support explicit uninstall at all because the problem is so messy. So a sink's observer will be uninstalled on multiple sources, and when any source changes, it flushes all its observers and tells the sink to recompute its value. An observer might remained installed on a source that its sink is no longer interested in, but whatever, one spurious change notification is acceptable. Weak references help a lot though, since we don't want these stragglers pinning objects in the heap.

Ah, but then I can see where David's approach might be usable here: the sampler maintains a list of its observers, and is able to tell the observers to self destruct when the sampler is destructed. The sources that the observers are installed on will then flush when an update occurs, and the observers won't be installed, so they can go to sleep.

### what really loses me is the

what really loses me is the "explicitly uninstall observer" part

A Client has a Signal S and an Observer O. The client asks for H = S.new_sampler(), then calls H.listen(O). Now, for as long as H is around, O will receive callbacks whenever the value described by S is changed.

When H is destroyed by the GC, or upon explicit request, O will stop receiving updates.

The 'explicit uninstall' is occurring under the hood to achieve these semantics via GC support for destructors or disposables. To the user, this behavior will often be implicit, but explicit uninstall is readily available if desired.

One is free to create a GC cycle by handing H directly to O. In practice, this is not necessary; O maintaining its own callbacks is a pretty large violation of the one responsibility rule, and the system tends to be simpler if you avoid doing so.

implicitly uninstall observers when they are used

Under which conditions do you implicitly uninstall them?

### We are too deep, so I'll

We are too deep, so I'll keep my reply short: observers are uninstalled whenever the observed source changes. The observer simply notifies a sink to "update" its value through re-evaluation, which will cause the observer to be reinstalled if the sink still depends on the source. Implicit uninstall reduces the amount of state that we have to maintain at the cost of some spurious notifications as well as needing to reinstall observers on each change. Still can be a win on performance though, since book-keeping needed otherwise (e.g., a graph) often has greater overhead (depends on the situation though).

### Compound Signal Samplers

If you destroy the Sampler how do the compound signals know if they should stop updating, maybe there are other samplers on them. It seems like you'd need to keep reference counts.

The signal object does not carry a reference to any sampler objects. Each sampler object is 'new', and thus the samplers themselves serve as implicit reference counts. This is necessary to ensure that callbacks are associated with specific samplers. (Different samplers will tend to share resources, of course.)

A signal is free to stop updating when there is no remaining demand. This could be 'no more samplers', or alternatively could be 'no more callbacks'. It is also free to stop updating when there is no more potential for update. E.g. if you request a subscription to (const Value), it would be free to implement this by immediately calling back with Value and not keeping any state at all regarding the number of subscribers.

What happens if you ask for a Sampler on a compound Signal?

You get a dedicated sampler for that sort of compound signal. E.g. A+B might translate to (bind (const (+)) A B), where 'const (+)' is a signal that always returns the value of the function (+), and A and B are arbitrary signals. If you ask for a sampler on this resulting signal then request a callback, it will introduce samplers on A and B, and a relatively trivial sampler on (const (+)), introduce the appropriate callbacks to keep each of them up-to-date, combine them all, and produce its own callbacks.

Things get to be interesting when you start using signals that carry signals (allowing combinators such as (deref SS)) and conditional expressions (if A then B else C).

if you have cycles you'd basically need to write your own GC?

Typically, I avoid cycles in the FRP expressions themselves. Dealing with FRP fixpoints is a paaaaaain, and not a very worthy one: 90+% of what I could possibly do with FRP cycles, I could do via binding a recursive pure function, e.g. (bind (const RecursiveFunction) A1 A2 .. AN). The other 10% isn't worth the extra complexity at the FRP layer; termination guarantees at the pure functional and FRP layers are of extreme value to partial evaluation optimizations.

### Thanks. Do you have an

Thanks.

Do you have an implementation or a specification somewhere?

How do you avoid that a value of a signal gets recomputed multiple times if multiple samplers with callbacks are installed?

### Recomputing

How do you avoid that a value of a signal gets recomputed multiple times if multiple samplers with callbacks are installed?

Since the signal creates the sampler, the signal gets full control over how its sampler behaves along with the set of shared resources. The signal is, thus, responsible for deciding how callbacks are installed and what gets recomputed, what gets cached, and so on.

In one of my implementations (which is not part of a FOSS package, sorry), the samplers would simply 'install' the callbacks directly into the signals. When the signals updated, it would run a list and hit all the callbacks with the new immutable value. Later, when the sampler was cleared or destroyed, it would remove from said signal all the callbacks associated with it. (Of course, I didn't use signal/sampler terminology, but Sandro chose well here.)

But this is really an optimization decision, and we should all know to be wary of naive or sweeping optimization decisions! The presence of parallelism, concurrency, and distribution can make a huge difference as to what is 'efficient'. Whether you should recompute vs. attempt to share state is something I believe ought be left to a good optimizer, and perhaps some programmer annotations developed according to experience and profiling.

### buffering considered harmful

But this is really an optimization decision, and we should all know to be wary of naive or sweeping optimization decisions!

Even in the simple non-parallel, non-concurrent, non-distributed case, buffering can slow things down more than it speeds things up. For example, there is no point to buffer a + b, as re-computing is extremely cheap while messing with memory to load/store a + b and to check if a + b changed is ALOT of overhead.

In general, it makes sense to let the programmer choose where signals need to be buffered, if anywhere at all.

### Buffering is necessary if

Buffering is necessary if you don't want to propagate non-changes.

E.g. if A = 1 and B = abs(A) and someone sets A = -1 then you may or may not want to call the callbacks on B. Not calling them is useful as it allows you to have mutually dependent inputs/outputs:

t1 = TextBox()
t2 = TextBox()
t1.text = reverse(t2.text)
t2.text = reverse(t1.text)


edit: Oh you can do this without buffering. You only have to remember the inputs, not the intermediate steps.

### Not buffering means being

Not buffering means being able to tolerate non-changes yourself. If your sink can't tolerate non-changes, it should remember the last observed value itself for comparison. Your buffering example doesn't make sense to me, if you have recursive dependencies...their has to be a reason for that and either you can provide your own buffer...or use physics.

All bets are off when we start thinking about collections. They have their own problems and usually require some kind of states.

### Tombstones

Are you familiar with Smalltalk-style tombstones?

On entry, you simply check to see if the code graph is dead or not. If it's dead, you pass along the instructions to whoever inherited the dead code's will. This prevents Dangling Pointers by modeling how the object graph can change.

Furthermore, you can pool your tombstones into a pool so that everyone checks a registry to find the right tombstone.

### Why are weak references a

Why are weak references a concerning performance point?

### Weak ref performance

Weak references tend to involve memory barriers, indirection, and extra allocation or GC steps. The memory barriers (needed to produce a strong ref from a weak ref in an environment with a concurrent collector) tend to scale poorly wrgt to processor-layer data parallelism.

### Which papers/web pages can I

Which papers/web pages do you recommend on using physics for UI layout?

This page shows neat examples of how to use Bling's physics. How do you apply this to real world interfaces?

### Any kind of layout that you

Any kind of layout that you can think of can be expressed by some number of spring constraints. So even if you are building a traditional form-based application, you could still express your layout in physics, though it might not be very useful if there isn't a lot of dynamism. This is why physics really comes into its own when you start considering natural user interfaces, because you can force a layout for your elements but still expect them to react to touch rather than just sit still.

The Bling examples show how you can apply constraints to do layout, but I'm still looking for a cleaner/easier system that hides more details. Essentially, using physics should be a matter of just expressing your constraints (this box is next to that box), then that you are using physics for layout should transparent. E.g., one might still use a stack or dock panel in WPF to do layout, its just that the constraints that the layouts impose go through a physics solver, and you could "push" elements out of the layout if you wanted to, and the system would completely handle that to.

### Thanks, that makes sense.

Thanks, that makes sense. How do you override existing constraints (e.g. do you assign priorities to constraints)? How do you remove existing constraints? Which other types of constraints are you considering (other than springs)?

### Right now, there is no

Right now, there is no rule-based dispatch of constraints in Bling (like SuperGlue supports). Instead, you can assign strength and guards to a constraint, which is heavily used in Bling's fan example. The "strength" of a constraint determines how far the constraint is met on each solution cycle, e.g., 50% strength is 0.5.lerp(old, new). Now, we can make strength a signal, so you can disable and enable constraints by lowering and raising constraint strength. For example, consider a grid layout + weak strength gravity, we can lower the grid layout constraint strength to zero, causing all the items in the grid to fall down. Now, raise that back to 100%, and the items will simply rise up and become a grid again (gravity is too weak to have any effect).

Actually, spring is not a built-in constraint in Bling. Since Bling is based on Verlet, constraints are expressed simply by changing the value of what is constrained. That basically means normal imperative assignment, although we have to be careful to incorporate the previous value into the target value lest we ignore the results of other constraints. If you look at Bling's fan example, you'll see lot's of non-spring constraints on rotation.

### FRP Physics Hybrid UIs

This is why I think physics might be a better paradigm than FRP in long run.

As I understand it, a physics-based approach involves incrementally meeting a set of constraints. If the constraints change, the system incrementally moves to its new set of constraints from its current state, which means the output is influenced by history and timing of constraint-update events. Increments may occur over time, in which case different choices of incremental constraint solver ends up producing different animations. The rules guiding the constraint solver itself, thus, correspond to a virtual 'physics'. If the physics change, the system starts applying the new physics rules until it again reaches a low-energy (minimal movement) state.

Via the influence of its history, the physics approach can result in more 'stable' UI interfaces. That is, there is little risk of a big change in layout layout after a small change in the display specification, which may prove a problem in FRP. So long as the physics aren't unstable and you aren't throwing curveballs at it, the solver will move from one "low-energy state" to another in just a few moves. This may be more predictable and feel more 'natural' to users. Users might also select or provide their own 'physics' via browser or site options, thus offering some interesting tuning and standardization opportunities. Users may also move things around on their own, after which they'll float along or snap to place depending on the rules.

On the downside, if you fully 'refresh' a physics-based UI that has reached a low-energy state - forcing it to resolve the constraints again from the beginning - you may end up with a very different layout. There is also risk of entropy and risk UI corruption - for example, an icon may get 'stuck' in some funky places. And significantly more state management is required to follow a user around from terminal to terminal if a user wishes to have stable views of a system.

A useful hybrid is eventually consistent solvers that are guaranteed to incrementally always reach the same low-energy state as they would reach after a full refresh and any initial random positioning of the elements (at least in the absence of continuous 'time' based motion or constraints). In this case, the solvers can be distinguished by which end-state they reach, how they reach it, and how long it takes. That is, each physics is a choice on final layout plus animation characteristics. I have always been assuming the use of these eventually consistent physics as part of any high-quality FRP UI design, i.e. something the browser provides to support navigation and animation effects (fading, sliding, minor animation effects, etc.). The set of eventually-consistent 'physics' is minute compared to the total set of physics options, but is still large enough to support interesting tuning, animations, and integration with browser constraints.

I do agree that if the choice was between 'FRP' stability across refreshes and 'physics' stability from instant-to-instant, that I'd probably favor the stability offered by a physics approach. A browser could keep a little state on layout state - for consistency across restarts - but users would just learn to deal with inconsistency after a refresh or restart, learn to refresh after UI corruption due to timing issues. Besides, one can always implement eventually-consistent physics given the physics approach, but vice versa is much more difficult.

OTOH, I still favor FRP for defining and gathering the constraint-set itself (plus, perhaps, defining and gathering any physics tweaks, akin to inline CSS). The popular option today is to define and imperatively manipulate an initial state for a Document Object Model or GUI shell, as per WPF or dynamic HTML. But the use of FRP for this purpose has many advantages for collaborative and distributed access, and for various forms of sharing/embedding of data resources.

Only eventual consistency is lost by using arbitrary physics for the layout solution, and I'd say that's often an acceptable sacrifice.

### Only for layout

But only for layout, right? If not, how you express user events (button clicks and so on) in physics? (My interest in FRP is mainly for handling events in UIs; I'm less interested in layout.)

### Two words (or maybe one):

Two words (or maybe one): multi touch.

Physics is the only way to reason about input in a naturalistic UI, if multi-touch input becomes popular, we really have no choice.

If input means buttons to you, then physics is not really relevant.

### Doug Engelbart

Doug's original mouse pioneered multi-sensor input hypermedia, using keychords to simulate simultaneous 'touches'. The mouse we use today is a simplified design of Doug's original power-user vision.

Likewise, my DataHand keyboard allows me to program macros that, although not actually evaluated in parallel, could be if not limited to the PS/2 serial interface.

Also, to overcome limitations with GUIs that have a notion of 'keyboard focus', I've wanted to support "administrative" capabilities that allow me to interact with the GUI via voice recognition software; this would allow me to keep keyboard focus and use the "voice stream" as a separate "input pipe" to launch background, debugging tasks.

### Do you have a link to Kim

Do you have a link to Kim Burchett's paper?

### lowering Recently there was

lowering

Recently there was an (ICFP?) paper that does similar stuff from a first skim, but they never discussed the relation.

### Exceptions in signal networks

How are errors generally handled in FRP? I can think of two approaches, but I'm not sure which is more useful:

1. Propagate: the error is propagated downwards to all dependent signals.
2. Error site: the error is stored in the signal node that generated it, but propagates no further. The next update clears it out.

The FrTime papers I have don't discuss error handling very much, aside from mentioning that they provide an error tracer.

### RE: Exceptions with Signals

I don't know how most languages handle exceptions. I do support failure for FRP due to potential for disruption and a need for graceful degradation, plus any soft-typing failures. My FRP language provides dedicated 'fallback' primitives, switching to alternative FRP expressions on failure (i.e. to switch to a mirror if the primary is unavailable). Similarly, one may expressly represent {failure} as a primitive signal.

My design does not support generic data-carrying exceptions at the moment - i.e. nothing like {failure ComplexValueHere}. I could do this easily enough, and support conditional (and argumented!) fallbacks... but I'm not sure whether I should. I am still weighing pros against cons regarding scalable (aka distributed) composition and modularity. Certainly, representing 'failure state' of external systems should be a perfectly normal signal value, quite distinct from FRP failures.

In any case, I would suggest that failures propagate, except where explicitly blocked by a signal constructor. Developers must be able to handle partial-failure effectively, so burying them by default makes things a tad difficult.

### Thanks for the suggestions

Thanks for the suggestions Sean and David. I suspected that propagation was the right approach, and I appreciate the confirmation from people with more experience in this domain.

I would suggest that failures propagate, except where explicitly blocked by a signal constructor.

Could you clarify the meaning of "signal constructor"?

### Signal constructors

Could you clarify the meaning of "signal constructor"?

You'd use the word 'compound expression', I believe.

I chose to avoid the word 'compound' because it implies composing two or more signals, whereas constructors might involve zero or one prior signals... e.g. {const Value}, {deref SignalOfSignals}, {failure} are constructors, but not strictly compounds.

I instead distinguish capabilities (external resources that can only be referenced by unforgeable names, not constructed) from constructors. FRP expressions are incapable of producing new capabilities, but an OOP/FRP paired language could produce new FRP signal capabilities via object constructors.

To handle propagated errors, there could be a dedicated compound expression (constructor) to catch and handle failures or certain exceptions, i.e. by allowing fallback expressions.

The real trick is deciding how callback observers see failure. If you plan to report the last value along with another element to distinguish a failure case (like Sean does) then you must buffer the last value reported (though that is also useful for eliminating same-value callbacks, it can be a performance hit). At the moment, I simply don't issue callbacks for failure... but I'm still deciding whether to do this vs. provide a callback with an extra 'failure' condition in the dynamic scope.

### I think the approach I just

You'd use the word 'compound expression', I believe.

Ah, so in the terminology I used above, errors propagate only to samplers.

I'm not using samplers at the moment, but the approach I just committed is essentially the error monad: a signal carries a sum type, of (value | last value * exception). Error propagation is thus handled the same as value propagation. I'm striving for absolute simplicity by leveraging .NET's native event handling facilities, and it's come together nicely so far.

One minor sticking point prior to adding errors was distinguishing a disposed signal, but now that signals carry errors, I simply leave the signal in a permanent ObjectDisposedException state.

### Disposed Signals, Last Value, Information Carrying Failures

Using the error monad is reasonable if it is mostly hidden. We mostly need to avoid cluttering the compound expressions with too much error handling. Haskell manages this via lifting the exception condition into a hidden monad argument, but it this may be difficult to achieve in languages that don't provide that particular brand of syntactic sugar.

The 'last value * exception' above wouldn't propagate across compound expressions all that well due to potential for multiple exceptions. Consider: which exception should you report for A+B when both A and B are in failure states?

Actually, now that I review my notes, this is one of those 'big' reasons I chose to avoid information-carrying failures in my design. The semantics for information-carrying errors, along with errors that report 'last value', are difficult to reconcile with a variety of optimizations (including laziness, reordering, and data-parallelism).

And a similar good reason to avoid 'last value' as part of the failure state: what shall you do when failing as of the very first value? (which may occur when starting in a disrupted state).

One minor sticking point prior to adding errors was distinguishing a disposed signal, but now that signals carry errors, I simply leave the signal in a permanent ObjectDisposedException state.

For cells (mutable state, accessed via signal), I do not believe disposal of signals is appropriate. If the update facet is lost (RefSignal<T> in your case, IIRC) then the associated Signal should be finalized in a good state rather than be disposed. Finalization amounts simply to clearing the callbacks list since no more updates will ever be forthcoming. This, in turn, clears up memory resources for which those callbacks were the only reference.

### (i.e. what do you report for

(i.e. what do you report for A+B when both A and B are in a failure state?).

It's currently ordered choice, so the error in A is propagated. Once A's error is cleared, the error in B will be propagated, assuming it still exists. I can see how it could be useful to report all errors simultaneously rather than one at a time, but we'll see how far I get this way.

One interesting challenge for error propagation is how to selectively either stop the propagation, or ignore the error and just display the last value (I currently throw the error when trying to access the value of a signal in an error state). Consider a UI framework like Bling where various controls are connected by signals. An erroneous input in one control will propagate that error to all derived signals and show error messages at all derived values in a form, but we really only want to display the error at the source.

For cells (mutable state, accessed via signal), I do not believe disposal of signals is appropriate. If the update facet is lost (RefSignal in your case, IIRC) then the associated Signal should be finalized in a good state rather than be disposed.

Disposal is idempotent, and finalization implies disposal. The notion of signal disposal I use is "no further updates", and a cleanup event that fires. I perform no operations, disposal or otherwise, on values carried within signals, so it would be up to clients to dispose of values. I'm not sure whether this addresses your concerns.

### Ordered Choice, Finalization and Disposal

I tend to disfavor 'ordered choice' semantics of any sort because it doesn't integrate well with syntactic extensions (such as macros), reordering, laziness, that sort of thing.

The 'finalization implies disposal' philosophy seems oddly inconsistent to me.

Compare A + B vs. 1 + B.

If the last update to A leaves it at 1, I would (under principle of least surprise) think the values of these expressions should be equivalent. To be equivalent, either all constants in FRP expressions would need to produce 'disposed' exceptions, or finalization is not disposal.

You also make a semantic distinction between 'last update' (i.e. when a RefSignal receives its last update) and 'provably last update' (i.e. when a RefSignal is actually collected or GC'd). I do not know what this extra distinction implies, except for extra complexity.

### I tend to disfavor 'ordered

I tend to disfavor 'ordered choice' semantics of any sort because it doesn't integrate well with syntactic extensions (such as macros), reordering, laziness, that sort of thing.

Not really worried about most of these issues considering this is a C# EDSL.

To be equivalent, either all constants in FRP expressions would need to produce 'disposed' exceptions, or finalization is not disposal.

Good point. RefSignal disposal/finalization should not dispose the signal, but should make the signal a constant. Signal disposal and finalization can still be equivalent, since disposal is an explicit act (except during finalization where its effects aren't observable anyway). I don't see a semantic problem with A + B differing from 1 + B when the sequence of events is:

ref(A).Value = 1;
A.Dispose();

However, I agree this sequence of events should produce a constant, not a disposal error:

ref(A).Value = 1;
ref(A).Dispose(); // or GC.Collect(ref(A))

I'm not actually convinced signals should be disposable in general, since it's a rather powerful authority given how it can affect other computations. It was just easy at the time.

You also make a semantic distinction between 'last update' (i.e. when a RefSignal receives its last update) and 'provably last update' (i.e. when a RefSignal is actually collected or GC'd).

I'm not sure what you mean by this. Given the above change to RefSignal disposal, is this still a concern?

### Disposable Signals

I'm not actually convinced signals should be disposable in general, since it's a rather powerful authority given how it can affect other computations. It was just easy at the time.

I agree. Disposable Samplers and disposable update facets (RefSignal facet, in your case) make reasonable sense. Disposable Signals, however, would be far too excessive an authority to share with everyone who has access to a signal, and is semantically very questionable in the case of expressions for 'compound' signals.

Given the above change to RefSignal disposal, is this still a concern?

Not really worried about most of these issues considering this is a C# EDSL.

I had assumed as much. My own work is for a language design with first-class FRP, so optimization and integration with other EDSLs (syntax extensions, macros, libraries) are of great relevance.

### If you plan to report the

If you plan to report the last value along with another element to distinguish a failure case (like Sean does) then you must buffer the last value reported (though that is also useful for eliminating same-value callbacks, it can be a performance hit).

The value of the signal could be its last value, though not necessarily. A good example would be a something / 0, whose value would be 0 + an error. Actually, the last value is only used if the error is coming directly from a source that knows its last value anyways.

Just accompany signals with an extra error channel, then sinks can read this channel to take appropriate action (e.g., make the text field red). I guess there should be some error routing capability in the glue code, but I haven't done that yet.

### Extra Error Channel

Most domain modeling (including datalog-style logic programming, multi-database queries, etc.) can easily be produced inside FRP rather than in object code. Many expected errors can be represented via sum or product type results. E.g. A/B could return just(Number)|div_by_zero. I tend to favor the sum-types approach over the product-types approach (result:Number error:(ok|div_by_zero)).

Error channels (for clarity, I refer to an extra signal for status and meta-data) could be used to carry information about out-of-band errors, i.e. whether the whole form is 'consistent'. It is difficult to point fingers at any given source as a cause of inconsistency (last one updated is a possibility, but not the only one). I favor extra error channels where they improve simplicity. (This is not the same has having an error-channel be implicitly propagated with each channel.)

However, error channels don't actually solve the general problem, not unless they are 'special' primitives. A reference to a signal resource that happens to not exist (perhaps the joystick or webcam), or reference to a distributed resource (perhaps a remote file or web-page) that is temporarily disrupted, needs a true failure state. I would say that disruption or disposal should not be considered a 'value' for any stream because they are not parts of the domain model.

Restricting in-band errors to those inherent to the domain model greatly simplifies integration of functional code with FRP.

### Simplicity is important,

Simplicity is important, keeping the value part of a signal as simply a value makes client code easier to write. Making errors available on a separate channel that is propagated along with the signal is just as expressive, although you can easily ignore the error channel if you don't want to bother with errors.

In SuperGlue, the error channel can't reveal too much about the error since you can't really get access to anything that you are not connected to. So embedding references in an error is not allowed. Really, the sink of a signal just needs to know that the value of the signal is bad, they can't hope to resolve the error. Resolution has to come from logic elsewhere.

### Channel is a rather

Channel is a rather overloaded term, so to make sure I understand your meaning, are you equating channel and signal? So a signal is defined thusly:

public sealed class Signal<T>
{
public Signal<Exception> Errors { get; }
...
}

### The way I'm using the term,

The way I'm using the term, a signal has two channels: one for its value and one for its status (ok, in error, etc...). E.g.,:

class Signal[T] {
Channel[T] Value { get; }
Channel[Status] Status { get; }
Signal[S] SMap[S](Func[T,S] F);
}


So we've added another layer of channel structure beneath a signal, but users only see this layer if they want to. A channel is very simple when compared to a signal; e.g., all the change propagation behavior remains in the signal layer.

### Ah.

That's different than what I assumed. It seems you're using 'Channel' primarily to avoid infinite regression.

### What's the semantics of your

What's the semantics of your channel then? Channels from process calculi support get/put operations, essentially a stream type. Is this the intent? To buffer errors in a list and let clients pull them off at their leisure?

### Channels have no semantics,

Channels have no semantics, they are simply a level of indirection. When you "eval" a signal to get its value, you thunk its value channel. If you want to know its status "now" you thunk its status channel. If either the value or status channel could have changed, all observers are notified that change could have occurred. If an error occurred but you didn't look at the status channel at the right time, then you just miss the error, it isn't buffered anywhere.

Come to think of it, even this scheme might be a bit over engineered. SuperGlue separates the notions of change notification and thunking: so you are notified of when change could have occurred, but now how the signal changed, you have to re-eval the signal to get its current value. In this case, we could have just used normal exception handling so that sinks (which exist outside of glue code) can just catch exceptions when they re-eval the signal. The drawback is that there is no way to deal with errors in the signal language.

### If I understand correctly,

If I understand correctly, this doesn't seem appreciably different from the error monad approach I described above (unless signal error states don't propagate to derived signals?). The only significant difference is that signal value/state is not directly observable in my approach, it's only observable to lifted functions. I plan to also lift error handlers in a symmetric way.

As an aside, at one point I also considered using a special IValue<T> type, whose Value property will return the value for a successful update, or throw the exception from an unsuccessful update. Lifted functions operate only on IValue<T> types, instead of T. While this allows the use of native exception handling, I suspect it will harm composition somewhat. It certainly doesn't play well with LINQ query syntax.

### I use 1: Signal expressions

I use 1: Signal expressions have a value and also an indicator on whether they are in error or not. The signal still evaluates to a valid value (often the last valid value, but not necessarily), but sinks can query why the value is in error and possibly deal with that error. If the error results from a glitch (divide by zero), you might be able to just ignore the error (it goes away quickly).

### Glitches in FrTime

FrTime uses priority queues to sort expressions by height for glitch-free updates. They use the following example:

y = seconds < 1 + seconds

y should always be true. Let's break it down thusly:

x = seconds + 1
y = seconds & lt; x

So x depends on seconds, and y depends on seconds and x. Let's say 'seconds' updates to 2, here's a glitch-free update:

seconds = 2
=> x = 3
=> y = true
=> y = true

seconds = 2
=> y = false   (GLITCH!)
=> x = 3
=> y = true

For the following, I assume that creating a child signal immediately registers a listener with the parent signal, and that a new listener is always appended to the list of listeners.

So given y presupposes the existence of x, how can y ever be updated before x in a call-by-value setting? Is it Scheme's macros that cause the trouble here?

### I think some of this is

I think some of this is alluded to further, but there are more options:

1) a global exception stream (oddly, I found this one to be convenient in practice) -- if you want to propagate exceptions, put in a mechanism catch them at the lifted function level and explicitly propagate as a value!

2) a shadow exception stream (so exceptions are semantically propagated but, by default, computations are on a semantically filtered stream)

3) rollback support (TM, explicit, continuations -- diff implementations and interfaces)

However... I wouldn't go with *any* of the solutions proposed here unless it's one that doesn't impact your implementation. The only 'tried and true' approach would be something in an established dataflow language like LabVIEW (and I don't know what they do); the only publicly known FRP language that had significantly sized applications written in it was Flapjax and there we didn't have any major lessons with exceptions (that I know of). Well, no -- we converged on 1), but there was no real evaluation, just a decision.

### 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

### 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?

### 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.

Josh

Are there just a few essential, "canonical" papers on FRP - hopefully both theory and pragmatics?

Scott

The Yale Haskell Group: functional programming for the real world publications page, would probably be your best resource.

I can provide others, but have not really attempted to make a bibliography in the past.

[Edit: Also the Haskell website has a more specific Publications on FRP page.]

### Arguments in FRP

In functional reactive programming, what kinds of arguments can get passed? I gather that they can have a time component. Is this time measured at the input to the system as a whole? Is the time of a + a later than the time of a?

### Signals, event streams, or

Signals, event streams, or bundles thereof, are the usual arguments in FRP.

A signal describes a time-varying value (like mouse position). A relatively naive representation of a signal is Time â†’ MousePos. In practice, more sophisticated representations are used to simplify update and garbage-collection.

An event stream is an unbounded sequence of (Time,Value) pairs, ordered in time, representing instantaneous actions. Event streams are widely considered useful for modeling button presses and such. My professional opinion is that events a terrible abstraction that should be avoided or eliminated. But in some cases they're necessary at the interfaces to hardware or imperative software.

In most FRP languages, purely functional operations such as + that combine two signals are logically instantaneous. Of course, it is possible to model + as having delay, but regarding the 'one responsibility rule' it is often better to model it as instantaneous then express delay as an orthogonal function.

### Controlling Calculations in FRP

Suppose we want to calculate the value of some function at some argument. We already have the value of the argument, but we want to try two algorithms to attempt to calculate the result of applying the function. We will start two processes in parallel to try the two algorithms, limiting how much maximum RAM each one uses and limiting the proportion of a CPU's time each algorithm uses in a given time period. If one of the calculations finishes, we will stop the other one. Is Functional Reactive Programming (FRP) suitable to code such a strategy? Does the semantics about time in FRP fit well to the notion of how much time the calculation takes?

### Formal Process Control

In order to control a process formally, it must be modeled incrementally. This way, you can choose at each increment whether to halt, pause, or continue the process. (This is in opposition to, for example, relying on external mechanisms to fork and signal/kill a computation.) It is not difficult to model an incremental process... e.g. a relatively trivial model is something like ÂµP.(aâ†’(b*P)).

Multiple processes could then be modeled as operating in lockstep. And, if you wish, you can halt after at least one process reaches a final state. But increments can be computed in parallel, which can be profitable if the increments are sufficiently coarse grained. Even sequential increments for a single process can be computed in parallel, pipeline parallelism.

FRP systems are well suited to this sort of incremental computation on the temporal axis, so long as developers model adequate delays at each step. Indeed, most FRP implementations already incorporate incremental process models to represent state (folds and integrals over signals). But this also isn't a conventional way to use FRP - i.e. FRP models tend to be oriented more towards the domain than the algorithm/machine layer.

FRP can also orchestrate informal models, such as use of amb or a non-deterministic oracle machine. But I favor the formal models for incremental processing.

### Comparable Expositor

Who is to FRP as Leonard Susskind is to the elementary quantum mechanics of electron spin, in the sense of explaining it without the listener having to have gotten very far in math in order to understand?

### Probably Conal Elliott. He

Probably Conal Elliott. He posted an answer on StackOverflow with a short introduction and links to material that explains it more in depth. However, as one of the commenters on his answer says:

@Conal: you clearly know what you're talking about, but your language presumes I have a doctorate in computational mathematics, which I do not. I do have a background in systems engineering and 20+ years of experience with computers and programming languages, still I feel your response leaves me baffled. I challenge you to repost your reply in english ;-)

I think the best way is to follow the links to his paper on functional reactive animation and just read through the code in that paper. Don't expect to fully understand it on the first read though, some things just aren't that easy until you're already familiar with related notions.

### Is FRP Suitable for Distributed Computing?

Is FRP Suitable for Distributed Computing?

### FRP for distributed

FRP has been used for client-server applications, e.g. in Elm. It's doable. You might model, for example, acquiring a web page as a signal transformer from URL to Maybe HTML. But I think FRP is awkward for some aspects of distributed programming. In many cases, especially in open systems, it's much more natural to push information rather than pull it.