Specification for a Functional Reactive Programming language

Question

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?

Answer 1

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

---

Answer 2

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.

Answer 3

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!