Lambda the Ultimate

Thanks. I unintentionally omitted FrTime from the Related Work section, and I'll add some remarks. It's perhaps something of an apples-and-oranges comparison, as the semantics are quite different: pure & synchronous vs impure & asynchronous.

I think these are the most important sort of comparisons. It's easy to say "We're just like the FrobNozzle system [12], but with the extra blarg feature". The interesting comparison talks about the impact of the fundamental choices you're making. For example, is purity important to the semantics of FRP in your system? Is it important to the optimizations? Or is the reason for purity just the underlying use of Haskell? Is synchronous update easy for the programmer to understand? Does asynchrony mean their system if faster? Slower?

These questions are obviously harder to answer than most of what we write for related work. But they are the ones that make a real difference in the end.

Thanks, Sam. I like these questions.

The most fundamental choice for me is simple denotational semantics. Determinacy (in spite of the multi-threaded implementation) and lack of side-effects both have a huge impact on the semantic simplicity. The denotational semantics literally is as simple as

    B a = Time -> a
    E a = [(Time,a)]

and semantic definitions are as simple as

    at (fmap f b) = f . at b

Beside simplicity, another fundamental semantic issue for me is supporting continuously (not just frequently) varying values. I don't know if FrTime had continuously varying behaviors or just discrete ones. I think its temporal primitives seconds and milliseconds were integer-valued, so perhaps it had only discretly-changing behaviors (step functions).

After formal simplicity, my next goals are responsiveness and efficiency of implementation. For these goals, the purity & simplicity of the formal semantics are both challenging (especially determinacy) and helpful (to easily and rigorously justify optimizations).

After re-reading the FrTime paper today, I see that the term "synchronous" is probably being used in (at least) two distinct ways. I used the word to refer to a semantic property, e.g., that fmap f b undergoes transitions exactly when b changes. I did not mean the implementation property of sampling all behaviors at the same time, as in most previous FRP systems, which is very inefficient.

So: no, the semantic purity (and more generally, simplicity) is not just a by-product of using Haskell; and yes I believe semantic purity much simpler for the programmer and user to understand. I don't know about the net impact on performance, though I wouldn't sacrifice the semantics to get a faster implementation.

I am not familiar with FRP. I see there is a construct for a continuous function of time, and one for a series of discrete events. Are they these?

B a = Time -> a
E a = [(Time,a)]

How do you combine them? Can you make a series of events into a function of time?

B and E are the semantic domains for the library type (constructor)s Behavior and Event, which capture the continuous and discrete aspects FRP. The domains relate to the data types via via semantic functions:

at   :: Behavior a -> B a
occs :: Event a    -> E a

For making a behavior from an event (from what you called "a series of events"), the basic tool is

switcher :: Behavior a -> Event (Behavior a) -> Behavior a

The first argument is the initial behavior, and the second provides a timed stream of new behaviors to switch to.

The other main connection between behaviors and events is the ability to take a boolean behavior b and construct an event that occurs each time b changes from false to true.

If LabView is mentioned, I must plug-in the Hardware Description Langages and the way their simulators work : VHDL, Verilog, SystemC,...

It is essentially PUSH based event-driven interactions, with the availability of arbitrary scheduling of future events

Clock = NOT Clock after 10 ns;

The mixed mode analog+digital variants (like VHDL-AMS) are somewhat more functional with the continuous behaviour of analog parts.

[rant](Bbtw, yes, LabVew is a toy ;-)[/rant]

These are similar to other early data flow languages: you define the next time step's value in terms of the current. This leads to tight cycles - I don't think these systems typically feature reasoning to determine whether fixpoints exist in such cases, breaking synchrony assumptions. Regardless, citing them seems redundant to me. [Not to say they're not important; for example, there's some fun work going on in the FPGA world to more directly support them].

I haven't really seen good survey papers providing sufficient depth on the language properties of modern data flow / reactive systems. By that I mean the couple I've read both skipped FRP and Lucid/Synchrone styles of languages, which, to me, were fairly significant departures from Esterel et al.