Functional Reactive Programming

Functional Reactive Programming (FRP) is like FunctionalProgramming except that each function can accept a stream of input values. If a new input value arrives on an argument, then the function is reevaluated with all the most recent input values, and a new output value is created. This is a kind of DataflowProgramming. It can handle nondeterminism, so it is more expressive than declarative concurrency. -- PeterVanRoy

FRP has intentionally deterministic semantics. Specifically, the meaning of a behavior/signal is a function from time to values. I don't know where the idea that it "can handle nondeterminism" came from. And I'd say, FRP is an example of FunctionalProgramming, rather than being like FunctionalProgramming. --ConalElliott

Note: ConalElliott and PaulHudak? were the inventors of FRP. If there is an authoritative definition, it is theirs. The original FRP supports instantaneous events in addition to continuous behaviors.

Experiments in this paradigm have been done in OzLanguage, HaskellLanguage, SchemeLanguage, and JavaScript. The commercial EsterelLanguage also looks promising. It also sounds similar to FlowBasedProgramming.

In modern design, FRP is often arrowized - we describe a behavior as a function from signal to signal:

  type Sig a = T -> a
  type SF a b = Sig a -> Sig b

By restricting constructors for SF, it is possible to protect against anti-causal behaviors (where we look into the future of the input) and enforce other efficiency properties.

Discrete-varying FRP is also popular, i.e. where behaviors change only at specific instants. They allow much greater performance.

Advantages of FRP

At the small scale, FRP doesn't offer any real advantages over FunctionalProgramming or ProceduralProgramming. I.e. given a small example such as 'a = b + c', the fact that 'a' might vary over time doesn't seem a big deal. When it changes, just re-evaluate the expression! If you need to know when it changes, just poll! poll! poll!

However, as the system begins to scale upwards in any one of several dimensions (number of inputs, number of observers, concurrency of changes, size of expressions, number of expressions, integration across modules, etc.) FunctionalReactiveProgramming begins to offer several advantages over other paradigms:

efficiency: FRP has at least the potential cause you to only re-evaluate what has changed. As the number of expressions increases, this can offer great efficiency advantages. Even DataDeltaIsolation may be implicit... i.e. consider a function that performs a SELECT statement on a table as part of a much more complex expression. The table might change, but the result of that SELECT statement may be unaffected. When this happens, the runtime is free to avoid re-evaluating anything that depends upon that SELECT statement.
low-latency updates: when polling, the average latency at which you'll see updates is the rate at which you poll, and thus you must choose between latency and efficiency. A PublishSubscribeModel, however, makes it possible to notify interested parties very shortly after an update to any relevant resource, thus allowing low-latency. Usefully, FRP makes it easy to accurately identify specific interests and interested parties, even if those sets change rapidly.
implicit caching and multi-cast: if the expression 'a = b + c' is observed by many, and is not intended for SideEffects, then re-evaluating it once per observer may be very expensive. (For integers it wouldn't be so bad, but that expression could just as easily be set union or string concatenation or matrix addition. Of course, even for integer addition, if fetching 'b' or 'c' requires a fetch to a DataBase, possibly across a network, performance could be awful.) An FRP implementation can easily introduce caching where appropriate, i.e. based upon profiling. As we up the scale to include distributed resources and observers, FRP is even suitable to form a multi-cast network to reduce total compute costs.

Challenges for FRP

FRP has very few troubles so long as it is written entirely in the 'perpetual NOW'. However, to update the 'perpetual NOW' in response to (for example) user input, one would certainly need to escape the FRP paradigm and resort to SideEffects that will modify the world as it NOW exists. "Escaping the paradigm" isn't a bad design option, though it might sound better if we called it a "companion paradigm". But the interface between paradigms becomes a point for much awkwardness, and is undesirable... and to handle 'interaction' is critical to develop pretty much any service at all, be it UserInterface or a WebServer or DeviceDriver or PluggableArchitecture.

space-time leaks: many interactive services need to keep memory. What a UserInterface should look like at the moment may easily be influenced by mouse clicks and positions in the distant past. In 'pure' FunctionalProgramming and FunctionalReactiveProgramming, however, this is typically achieved by making a complete history the default, and allowing GarbageCollection to sweep away unnecessary information. Unfortunately, GC is far from perfect, and many 'straightforward' FRP expressions may easily result in subtle 'space-time' leaks, causing the FRP model to gradually slow down and consume ever more memory (the slow-down is caused by unnecessary recomputation over one's history). While one can be 'clever' to avoid problems, that cleverness cannot effectively be isolated to just one place in the code[1]. You need to be clever all the time, and that's a problem.
- In an ImperativeProgramming discipline, the 'model' itself typically manages the information it will need in the future, including via interactions with databases. While developers of the model often make mistakes (producing MemoryLeaks or errors) - and make mistakes even more often when concurrency is involved - they rarely blame the ImperativeProgramming discipline. Maybe they should.
extensibility and integration: FRP programs have seen practical use for a variety of purposes, such as driving video displays and animations. With a little care, they can even be used to guide behaviors: demand on behaviors represents 'interest', and interest can be used to drive where a telescope is pointed or guide decisions regarding where a UAV patrols[2]. However, FRP programs cannot advertise their services. Even accumulating and providing the 'history' that causes the space-time leak issues in the first place must be achieved from outside the paradigm.

[1]: an exception here is modifying the language implementation. A language that supports runtime specializations and beta-reduction of functions, and performs GarbageCollection to remove unnecessary code, would go a very long way towards draining many leaks. And enforcing that 'Time' is monotonically increasing may also help.

[2]: ReactiveDemandProgramming embraces these issues and notions fully, making reactive, concurrent, continuous, and potentially conflicting 'demand' an explicit part of the model.

PeterVanRoy further explains FunctionalReactiveProgramming's ability to 'handle nondeterminism'. Paraphrasing from memory: FRP may be hooked to external time-varying values, perhaps controlled by user, an OS file, or hooking into sensors of other sorts. The updates to these external (time-varying) data sources may be non-deterministic (they certainly aren't determined locally), yet FRP can 'handle' this nondeterminism quite effectively by propagating the updates to observers of the function. Properly, this must be achieved without glitches. For example, a change of 'x' from 2 to 3 is essentially atomic across all observations - x*(x+2) must go from 8 -> 15, not 8 -> 12 -> 15 or 8 -> 10 -> 15 as would be the case if the update to x is seen in one sub-expression before another.

It may be necessary to sacrifice some determinism (or at least switch to eventual determinism) if FRP is to scale to very large programs.

It seems, then, that most HardwareDescriptionLanguages are FRP. Verilog simulators, in particular, try to optimize the simulation time by computing results only when inputs change. I seem to recall some Verilog simulators being able to farm out work to dedicated processing nodes too (imagine trying to simulate a VLSI chip on a single computer!). This would seem to suggest, then, that FRPLs would be ideal for simulation applications. --SamuelFalvo?

If you exclude delays then they'd be pure FRP. By introducing delays, they become state-machines, and a lot of the features offered by the less expressive pure FRP are lost. I won't say that impure FRP is 'bad', but even simple hybrids greatly hinder many composition and optimization that can be safely performed in a pure FRP design. One would be even better off with a clean separation between the FRP layer and the state/delay/communications layer.

FRP can model delays and state (e.g. accumulators of events, integrals). It's still a pure function of the input signals. There are some similarities with Verilog and SynchronousReactiveProgramming?, but FRP is pure with respect to outside communication (no $write equivalent).

There isn't much here about implementation of FunctionalReactiveProgramming. Much of what I have found while having a look is based on HaskellLanguage. See SpecifyingBehaviorInCpp for an isolated example in CeePlusPlus. Much of what there is can be applied for FunctionalSimulationProgramming. -- JohnFletcher

There are many ways to implement FunctionalReactiveProgramming. Haskell has a library for it. Many spreadsheets software serve as simple implementations. Flapjax, Bling, LabView, etc. also offer impure FRP. I have not seen many languages aimed at pure FRP, but FRP really needs a companion paradigm to make a practical language. You might peruse http://lambda-the-ultimate.org/node/2057

There are two easily accessed examples of very-large-scale implementations (though the programmers might not have used the term "FunctionalReactiveProgramming" to describe what they do) complete with open source code, published API's, and large development communities to learn from --Twitter and Google Wave. Wave lets everyone on a wave see what you are doing to it in real time, so I'd guess they've found good answers to all the interesting questions. -- MarcThibault