64

I am looking at messing around with creating a functional reactive framework at some point. I have read quite a lot about it and seen a few examples but I wanted to get a clear idea of what this framework would HAVE to do to be considered an FRP extension/dsl. I'm not really concerned with implementation problems or specifics etc but more as to what would be desired in a perfect world situation.

What would be the key operations and qualities of an ideal functional reactive programming language?

Engineer
  • 8,529
  • 7
  • 65
  • 105
seadowg
  • 4,215
  • 6
  • 35
  • 43

3 Answers3

126

I'm glad you're starting by asking about a specification rather than implementation first. There are a lot of ideas floating around about what FRP is. From the very start in the early 90's (when I was working in interactive graphics at Sun Microsystems and then Microsoft Research), it has been about two properties (a) denotative and (b) temporally continuous. Many folks drop both of these properties and identify FRP with various implementation notions, all of which are beside the point in my perspective. To reduce confusion, I would like to see the term "functional reactive programming" replaced by the more accurate & descriptive "denotative, continuous-time programming" (DCTP), as suggested by Jake McArthur in a conversation last year.

By "denotative", I mean founded on a precise, simple, implementation-independent, compositional semantics that exactly specifies the meaning of each type and building block. The compositional nature of the semantics then determines the meaning of all type-correct combinations of the building blocks. For me, denotative is the heart & essence of functional programming, and is what enables precise & tractable reasoning and thus a foundation for correctness, derivation, and optimization. Peter Landin recommended "denotative" as a substantive replacement to the fuzzier term "functional" and a way to distinguish deeply/genuinely functional programming from merely functional-looking notations. See this comment for some Landin quotes and a paper reference.

About continuous time, see the post Why program with continuous time? and my quote in AshleyF's answer on this page. I'm surprised over & over by hearing the claim that the idea of continuous time is somehow unnatural or impossible to implement, considering the discrete nature of computers. This line of thinking strikes me as bizarre, especially when coming from Haskellers, for a few reasons:

  • Using lazy functional languages, we casually program with infinite data on finite machines. We get lovely modularity as a result, as illustrated in John Hughes's classic paper Why Functional Programming Matters.
  • There are many examples of programming in continuous space, for instance, vector graphics, but also things like Pan.
  • I like my programs to reflect how I think about the problem space rather than the machine that executes the programs, and I tend to expect other high-level language programmers to share that preference. ("A programming language is low level when its programs require attention to the irrelevant." - Alan Perlis)

I've been making libraries for programming with continuous time since TBAG and ActiveVRML (the first DCTP/FRP system) and later Fran. It's easy to implement correctly. A few different approaches are described in the paper Functional Implementations of Continuous Modeled Animation. Implementing continuous time efficiently (and still correctly!) is another matter, especially avoidance of recomputing unchanging values. (See the paper Push-pull functional reactive programming.)

For related remarks, please see my answer to The difference between Reactive and Functional-Reactive programming and to What is (functional) reactive programming? Update: For more on why continuous time matters, see these notes. Update: See also, my 2015 talk The essence and origins of FRP (and the related talks linked there).

Good luck with your exploration, and please let me know if you have any questions. My contact info is on my home page.

Conal
  • 18,517
  • 2
  • 37
  • 40
  • 2
    What's interesting to me is that the notion of a continuous *function* is all about finite limitations. The definition of continuity for a function is: for any finite amount of information you want out, there exists a finite amount of information you have to put in. So if you are working with continuous time, all you need is continuous functions to go with it and it is perfectly natural. – luqui May 04 '11 at 12:18
  • 1
    @Conal Are RxJS or Bacon.js FRP? If not, why? How are they different than what you describe above? Should they be called something else instead? – Bradford May 19 '14 at 23:38
  • 1
    @Bradford Are you asking whether RxJs and Bacon.js have the two foundational properties in my answer above? – Conal May 20 '14 at 15:33
  • 1
    @Conal yes. I heard a few people on twitter mentioning that Rx (Java) wasn't FRP. And then this SO answer was referenced as an example of what FRP is. I'm interested in how Rx (java), Rx.js, and Bacon.js (the ones I'm familiar with) are not FRP, if that is your claim as well. Some explicit comparisons are more concrete and thus easier for me to understand. – Bradford May 20 '14 at 16:11
  • 11
    @Bradford Got it. As far as I can tell, Rx and Bacon.js lack *both* of the two fundamental properties on which I based the original FRP. In that sense, they're not what FRP set out to be. Which is fine with me, as I love to see a multitude of abstractions explored. Using a single term to describe them all, however, creates more confusion about what each means and how they differ. I think an accurate description of Rx and Bacon.js is "compositional event systems inspired by FRP". – Conal May 20 '14 at 22:06
  • 1
    I like "compositional event systems" as a description of Bacon.js and Rx. I am still unclear how those libraries lack the "temporally continuous" property. – Bradford May 20 '14 at 22:52
  • 4
    These systems are *discrete*, being based on streams, i.e., possibly-infinite sequences of sample separated by temporal gaps. Continuous systems, in contrast, define values for *all* times, without any temporal gaps. In other words discrete systems have finite resolution, while continuous systems have infinite resolution. – Conal May 20 '14 at 23:42
  • 1
    This distinction is the temporal analog to the spatial distinction between bitmap graphics (discrete / finite resolution) or vector graphics (continuous / infinite resolution) and has the same benefits of composability and simple, precise semantics with simple & useful equational properties to support use and optimization. In both cases, the implementation maintains some sort of analytic representation and postpones sampling until all spatial or temporal transformation is done. In this way, we avoid undersampling (inaccuracy) and oversampling (inefficiency) – Conal May 20 '14 at 23:42
  • 2
    See also [Discrete time and continuous time](https://en.wikipedia.org/wiki/Discrete_time_and_continuous_time). – Conal May 21 '14 at 01:26
  • @Conal can you refer to any libraries/languages that implement real FRP as described by you (and put them in the answer?). It seems the continuous/discrete distinction only exists at a high level, and at the low level, the processing is discrete because of sampling, but then at an even *lower* level, maybe the universe becomes continuous again! – CMCDragonkai Oct 01 '14 at 09:05
  • @CMCDragonkai If by "only exists at a high level", you mean in the semantics, then yes, and the implementation must be exactly faithful to those semantics in a precise sense: every question one is able to ask (via the API) must be answered exactly consistently with the continuous-time semantics. Similarly, non-strict languages like Haskell allow infinite data structures, and the correct finite implementation gives exactly the right question to every askable question. The same possibility and advantages apply with continuous space, as in vector graphics. See also http://conal.net/Pan. – Conal Oct 03 '14 at 01:02
  • 3
    @CMCDragonkai And I share your perspective that temporal discreteness in digital computers is just an abstraction, not the nature of the machine. And we can easily and correctly implement continuous time abstractions atop the digital abstraction, as well as infinite atop finite. After all, continuous & uncountable mathematics is expressed atop finite alphabets, inference systems, and inferences. – Conal Oct 03 '14 at 01:06
6

I assume you've probably seen Matthias Felleisen’s talk on Functional I/O and read his paper. I think his is a very pragmatic and beautiful approach. Hopefully you've also stumbled onto some of Conal Elliott's excellent work.

My personal requirements would be that the system is completely pure. That is, all behavior is defined by pure world->world functions and all realization or visualization is defined by world->visual functions; where visual is some static description of the output from the system.

My other primary feature would be a historical debugger. It should be relatively trivial to maintain a history of world states and be able to replay from any point in time.

One area of extremely interesting research (I believe an unsolved problem) would be to use continuous time rather than iterating the world->world functions upon some discrete clock ticks. I once did a few blog posts on FRP and Conal Elliott left the following thought provoking comment:

I like denotative/functional approaches, for composability & semantic clarity. For the same reasons, I prefer continuous time & space over discrete time & space. In all of these cases, the less machine-like formulation nicely separates the what from the how of its machine-based presentation.

Solve that and you'll be a hero!

AshleyF
  • 3,682
  • 1
  • 25
  • 23
  • 5
    I have two main problems with the `world -> world` model. First, unless I'm confused, that model supports only *sequential* composition, and is unfriendly to *parallel* composition. Imagine how you might combine two `world->world` values *in parallel*. Second, I haven't been able to see how it could possibly support *continuous* time. Both of these problems thwart composability, which is a key goal for me in library design. – Conal May 04 '11 at 04:31
0

Well, unless by perfect world you mean telepathic computers (yikes!), then you'll require some way to process user I/O - I'll assume something like orthogonal persistence has subsumed the more boring file I/O...

Let's start with input...because it already has one solution. From page 4 of 11 in Conal Elliott's and Paul Hudak's pioneering paper Functional Reactive Animation:

lbp; rbp : Time → Event Event ( )

which, in Haskell, would look something like:

 -- read left and right mouse button-press events
lbp, rbp :: Time -> Event (Event ())

So for input from the keyboard:

kbd :: Time -> Event Char.

Other inputs can be dealt with in similar fashion.

So...what about output? The actual word doesn't appear anywhere in the paper (neither does "I/O" for that matter) - we'll have to figure this one out ourselves. But this time, it's our Haskell translation:

lbp, rbp :: Time -> Event (Event ())

providing the hint - Event () - the unit-event. That can serve as the result of sending a Char off, to appear somewhere on your screen:

viewChar :: Char -> Time -> Event ()

Again, other outputs can be dealt with using similar techniques.

...what's that - it isn't denotative? Because viewChar is...what - impure? If so, that means lbp and rbp are also impure - are you sure about this?

Alright...let's have a type for taking in a series of those mouse button-press, or other events:

type Intake a = [a]

lpb, rbp :: Intake (Event (Event ())

Is that any better? Good! Well, sort of - what happens if the mouse is unplugged? That could put parts of a program into a spin waiting for input (and using [] would permanently end the series - no more button presses!).

We need to change Intake:

data Intake a = None (Intake a) | Next a (Intake a)

Now unplugging the mouse results in None … appearing, which a program can detect and react accordingly e.g. yielding its OS thread, suspending itself, etc.

So, what about output? Well, output devices can often be unplugged too. Taking a hint from Intake:

data Outlet a = Wait (Outlet a) | Went (… (Outlet a) …)

It's similar to unplugging an input device - upon encountering
Wait …, a program can pause transmission.

So what should the type of Went be? Well, an Outlet accepts values incrementally to allow Wait … to appear if needed - the accepting of each value should present us with the rest of the Output. Therefore:

data Outlet a = Wait (Outlet a) | Went (a -> Outlet a)

Bringing that altogether:

data Intake a = None (Intake a) | Next a (Intake a)

lbp, rbp :: Intake (Event (Event ())


data Outlet a = Wait (Outlet a) | Went (a -> Outlet a)

viewChar :: Outlet Char

So is all this valid? If you're not sure, see section 20.4.2 (page 86 of 263) of Fudgets - Purely Functional Processes with applications to Graphical User Interfaces by Magnus Carlsson and Thomas Hallgren - if Intake and Outlet look dubious then so is what can be seen there, in the paper...

atravers
  • 455
  • 4
  • 8