Functional Reactive Programming
Combined Stream
last posted Sept. 9, 2015, 6:02 a.m.
I/O Operations as Result Objects
Interesting approach to I/O for FRP from discussion with +Shriram Krishnamurti and reading this paper:
http://cs.brown.edu/~sk/Publications/Papers/Published/ick-adapt-oo-fwk-frp/paper.pdf
Basically the idea is that the UI would have an invisible widget to represent files, the console, or network resources. The widgets are defined outside the system.
The FRP program can use the properties of the input widgets to "read". The FRP program can specify the properties of the output widgets to "write" or possibly initiate a read.
So in an FRP program responsible for yielding a scene graph, the resulting scene graph may include these invisible objects that specify any I/O operations that should be in progress.
These invisible scene objects would have some sort of static identity the FRP program uses for continuity between updates.
Alternatively, the FRP program can return the I/O graph separately.
In a streaming context (like the console or a network stream) you could have a read/write property of such a widget representing the current output buffer. The runtime drains the buffer between updates. There can also be an input buffer which the runtime fills between updates. Thus the widget need not maintain the entire history of input and output.
Also, if a particular file or socket disappears from the list of I/O activities, the runtime can close it.
Inverse dependency graph
In FrTime (and probably other FRP systems) an inverse depedency graph is used to update signals efficiently. When an event occurs, new values are inserted into the signals at the root of the (inverse) graph - if a signal's value has changed, any signals that depend on that signal will also be updated, propagating all the way to the leaves of that inverse dependency graph. Finally, the runtime can observe the new values of those final signals to update the outside world.
Re-frame (ClojureScript)
An FRP library for ClojureScript, the ReadMe has a lot of good links about FRP.
Adaptive Functional Programming / Self-Adjusting Computation
AFP / Self-Adjusting Computation is closely related to FRP - the outputs are adjusted in response to changes in the inputs. This is very similar to the way FrTime works.
- Self-Adjusting Computation - Umut Acar (2005) http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.114.7647&rep=rep1&type=pdf
- Adaptive Function Programming - Umut Acar (2002) http://www.cs.cmu.edu/~blelloch/papers/ABH06.pdf
- A Proposal for Parallel Self-Adjusting Computation - Matthew Hammer, Umut Acar (2007) https://www.cs.umd.edu/~hammer/papers/damp07.pdf
- Self-Adjusting Machines http://www.cs.umd.edu/~hammer/selfadjmachines/self-adjusting-machines--hammer2012.pdf
- More papers and implementations for C and ML here: http://www.umut-acar.org/self-adjusting-computation
Elm
Elm is a programming language / system based on Functional Reactive Programming that has been making some headway:
The Elm language is an eager, pure, statically typed, functional language with syntax based mainly on Haskell.
In Elm you explicitly construct a Signal graph and return it back to the runtime for interpretation; the signal graph does not change while the application is running.
FrTime
FrTime (aka "Father Time") is a Scheme / Racket dialect that automatically updates outputs that depend on time-varying inputs. It does this by changing the program to monitor what signals are used during the evaluation of a given expression and constructing a dynamic dependency graph from that.
Then, it updates the inputs based on events and those updates are propagated through the dependency graph to update the outputs.
Links:
- Embedding Dynamic Dataflow in a Call-by-Value Language http://cs.brown.edu/~sk/Publications/Papers/Published/ck-frtime/
- FrTime: Functional Reactive Programming in PLT Scheme http://cs.brown.edu/research/pubs/techreports/reports/CS-03-20.html
LuaGravity
LuaGravity is a reactive version of Lua. It's not actually FRP because lua is a procedural language, but interesting nevertheless.
https://thesynchronousblog.wordpress.com/2008/08/17/a-first-glance-at-luagravity/
Conal Elliott
Conal coined the term FRP and has been developing this style of programming since a long time ago, at least at Microsoft developing ActiveVRML in 1996.
He has mainly done FRP implementation embedded in Haskell, such as Fran and Reactive.
You can read his blog here: http://conal.net/
Why "folding over event streams" makes sense in FRP
I just had a light-bulb go off about why folding over a list would work as a way to deal with events in FRP.
The reason is this - the FRP implementation is conceptually updating the list of events, and recomputing only the part of the list affected by the change (i.e. the tail of the list). However, the fold doesn't keep track of past parts of the list, and the runtime also need only remember the tail of list so it can update it, so those old events in the list can be garbage collected (in theory) since there are no references to them.
FRP Performance Trade-Offs
For FRP (and self-adjusting computation), performance and memory usage depends on many factors.
In order to be successful, an FRP system must be able to tune and optimize these aspects of the program to strive towards having the same performance characteristics as an application where updates are processed by hand by a programmer.
Signal Granularity
In the simplest form, the whole program can be re-run completely on every update. In this case there may be some inefficiency as some values will be recomputed unnecessarily. Also, if events are represented as streams, then the entire history of events might be reprocessed. This is the original approach to implementing Classic FRP, also referred to as "pull FRP". The drawback here is that recomputing everything becomes too slow.
On the other side of the spectrum, every calculated value might be a separate signal / subprogram and only the values that depend on a changed input are recalculated on an update. However, in this case there is a very high overhead in keeping track of every intermediate value and its dependents, typically exceeding the savings had from avoiding unnecessary computation. This is more like the initial implementation of FrTime, it might be referred to referred to as "push FRP".
More recent works in FRP try to find a way to combine and balance the push and pull approach, typically by making the programmer manually specify which is which (as in Elm) or by matching it to some existing boundary, like a function boundary (in the lowering transformation for FrTime).
Signal Dependencies / Evaluation Strategy
As part of slicing a program into signals, there is some flexibility available in terms of how a computation can be broken down into steps (sequentialization) or signals (dependency analysis).
For example, if the application performs a transformation of each element of a list and returns a new list, the elements of the new list could depend on the entire input list (corresponding to an eager evaluation strategy) or only on the corresponding element in the input list (corresponding to a lazy evaluation strategy).
A more lazy evaluation strategy should reduce the cost of an incremental update, but it may also result in a higher memory overhead to keep cached values and dependencies.
Continuation-based FRP in Haskell
A simple FRP implementation in Haskell using continuations:
http://www.paolocapriotti.com/blog/2012/06/04/continuation-based-relative-time-frp/
Intro to FRP Slides
Edward Amsden's slides talking about FRP, for those new to the subject:
Functional Reactive Programming in Scheme with guile-2d
http://dthompson.us/functional-reactive-programming-in-scheme-with-guile-2d.html
Froc
Froc is a library for functional reactive programming in OCaml.
The interface is similar to FrTime and FlapJax, but (of course) typed, implementing a monad of changeable values. The implementation is data-driven, using the dynamic dependency graphs of Acar et al.’s self-adjusting computation.
Froc can be used with ocamljs, and with the included froc-dom library can be used for web browser programming.
And an article on "How Froc Works":
http://ambassadortothecomputers.blogspot.ca/2010/05/how-froc-works.html
FRP as an end-to-end web solution
One interesting area of exploration is the use of FRP / SAC for web applications. If one could respond to changes to the database and user inputs in a reactive manner and send down to the web client just enough information to update the current display, that would seem to be a very advanced and efficient manner of operation.
Monadic FRP
Monadic FRP is an alternative approach to FRP, sample implementation in Haskell.
http://homepages.cwi.nl/~ploeg/sfrpdocs/
Note that FRPNow! (below) is the successor to this paper.
Input APIs can look synchronous
An FRP I/O read can be considered referentially transparent if reads are repeatable; that is, the data you read is treated as a snapshot, and multiple (filesystem/network) reads from the same snapshot return the same value. Then only writes need to be handled as procedural.
Time, or some snapshot identifier, must be a parameter to the read operation for this to actually be referentially transparent.
Fran
One of Conal Elliot's first implementations of FRP in Haskell:
http://conal.net/fran/tutorial.htm
Fran stands for "Functional Reactive Animation".
Python FRP
Another interesting paper about FRP in Python:
http://www.cs.jhu.edu/~roe/padl2014.pdf
Abstract. We present our experiences integrating Functional Reactive Programming (FRP) into a new host language, Python, and a variety of computational contexts: a game engine, a GUI system, and an embedded controller. We demonstrate FRP principles extended to a dynamic environment and the integration of object-oriented libraries into the reactive environment. A number of FRP semantic issues are addressed in a straight-forward way to produce an elegant combination of FRP and object-oriented programming. In particular, reactive proxies integrate traditional objects with the reactive world and event-triggered reactors allow reconfiguration of the network of reactive proxies and interaction with the outside world. This work demonstrates that FRP can serve as a unifying framework that simplifies programming and allows novices to build reactive systems. This system has been used to develop a wide variety of game programs and reactive animations in a summer camp which introduces programming concepts to teenagers.
FRP Now!
I'm not sure I understand everything but my rough understanding of FRPNow! is ...
Rather than model events always as a stream of events as in most other FRP papers I have read, they consider events individually as a sort of future or promise. The Event acts in many ways like a Behavior of Maybe and they even provide a function "fromJust" which converts a Behavior of Maybe to an Event.
When an async operation starts, the Event is marked as not having occurred yet and having neither time nor value (or infinite future time and undefined value). When the async operation completes, the Event is marked complete and has a timestamp and value.
To create an event stream ala Classic FRP events, they can start with an initial event (say, "read keyboard") and then "unfold" the stream so that the "tail" of the stream is a behavior that depends on the "head" of stream being already available and re-runs the same IO operation over and over.
Behaviors are actually modeled in terms of events - there's the "current" value and an Event for the "future" behavior which will have a new current value and a new Event for the future (recursively).
The rest of the work seems to be how to make this model work efficiently in Haskell without space leaks, which does seem to introduce a fair amount of incidental complexity.
Links:
Sly FRP
Sly is a free software game engine written in Guile Scheme. It provides an abstraction layer above SDL and OpenGL for common game programming requirements such as:
- Animation
- Shaders
- Sprites
- Tilesets
- Scene graph
- Keyboard/mouse/joystick input
- Scripting
Sly differentiates itself from most other game engines by encouraging live coding and emphasizing functional reactive programming.
As of August 2015, seems to be under active development.
Links:
FRPWorks - Nu Game Engine
"The Nu Game Engine is a game development platform that aims to drastically reduce the cost of game development by providing a superior programming model for games via Iterative Functional Reactive Programming (IFRP). While the engine is still pre-1.0, the implementation has matured enough to prove both the efficacy and viability of pure functional programming in indie games in terms of performance, programmability, and reliability."
This repository hosts several projects, including -
- the Nu Game Engine
- a cross-platform F# 2D game engine built in the functional style. Uses SDL2 and Farseer Physics.
- the small but potentially useful F# code library Prime (interesting features, but lacks unit tests).
- the sample game BlazeVector.
Links:
Function Reactive Programming (FRP) is a style of functional programming where an application is a function from inputs to outputs.
One can imagine the output of an application as a function of its initial state plus a stream of events to produce an output. As new events occur, the function can be re-run to update the application output.
If an application has internal state of some sort, it can "fold" over the event stream with a subroutine taking the current internal state plus a new event to yield a new internal state.
FRP is a very conceptual model for writing interactive applications but it has some challenges in efficient implementation - the memory requirements of keeping a complete or even partial history of all inputs are too great.
In lazy languages like Haskell this history might be kept accidentally because unevaluated expressions can keep references to older states.
So now FRP implementations don't give you the whole list. Instead you provide a function that the runtime applies to new events (and optionally a past and present state).