Lambda the Ultimate

Yes, exactly. I originally invented "dip" in order to make it easier to define the optimization compositionally. Once I had the inference rules worked out (using dip), it also turned out to be a pretty straightforward way to actually write the implementation.

By the way, the idea behind dip applies to more than just FRP languages. In general, it applies to any monad where where lift (f . g) == (lift f) . (lift g) (as noted in the final section of the paper). For heavyweight monads, like in FRP, it can be a big win.

There are several advantages to the way we did it (i.e. removing lifts wherever possible rather than trying to only insert lifts where appropriate). We did consider doing it the other way. We referred to the approach described in the paper as "optimization", and the approach you suggest as "compilation".

From my perspective, the biggest advantage of the optimization approach is that if an optimizer comes across an unrecognized language construct, it can just throw up its hands and leave the original code unmodified (application of higher order functions is a prime example of this). In contrast, by relying on a compiler to add dataflow semantics only where necessary, you force the compiler to support every possible language feature.

The optimization approach also allows the end programmer to completely disable optimization. This might be desirable if, say, the optimizer produces incorrect code. In contrast, disabling a compiler would guarantee incorrect code.

Finally, by making the optimization into a separate, optional pass, you end up simplifying the language implementation. It's entirely possible to reason about the implementation of FrTime without thinking about dipping at all (I know this is true, because FrTime was fully implemented before dipping was even thought of). In contrast, if you relied on a source-to-source transform to insert lifts where appropriate, you'd need to take that into consideration whenever extending the FrTime language.

Your point about the planet example is well taken, though :) I wasn't thinking especially clearly that night.

Certainly. What I'm trying to do is implement a small, self-contained language that I can compile down to machine code for robot controllers and the like. So I'm expecting the compiler to have to know about all the language features...

But I think I'm still missing something. In many cases, controller programs are polled rather than interrupt-driven; every piece of code is simply run at pre-determined intervals (ranging from microseconds to seconds). Check out the Hardware Abstraction Layer for a reactive system that works this way (running in the kernel space in real-time Linux).

The point is, if you do things this way, your program can do any one-shot computation you like, including higher-order functions etc, and you just consider the whole thing one "dipped" block.

So my question is, what is there about the semantics (as opposed to the implementation) of FrTime that would keep this from working there?

Josh

FrTime has the ability to support stateful nodes in the dataflow graph. For example the delay operator can delay a sequence of events by an arbitrary amount of time. Similarly, the derivative and integral operators won't work unless they're able to remember the previous values of their inputs.

If you were to try to dip these operators, you would get incorrect results -- dipping only works for pure functions, not stateful ones. In other words, the correctness of FrTime programs depends on the fact that the dataflow graph is persistent.

Derivative, integral, and so forth are of course crucial to most signal processing and control applications ... but I conjecture that a single stateful operation suffices: a function that maps a signal onto its history as a list or vector or whatever linear datastructure your static language provides (or if the timesteps are not regular, a double list or alist or the like). Sum it for integral, sample it at a fixed offset for delay, etc.

So: define the other stateful primitives in terms of this one, and wherever it appears in the program, stick in a sequence accumulator.

Is there any stateful function (other than negative delay :-) this wouldn't work for?

Josh

The system need only keep track of the most recent state of any given node -- the node itself can build a history list if that is what is desired.

And yes, this works for all (even noncausal!) state functions. In control theory, any* system can be represented as a first-order differential matrix equation (this is the so-called "state-space" representation): the change in state of some system (i.e. its next state) is purely a function of the input and the current state of the system. The order of the state matrix corresponds directly to the "amount" of state the system has (i.e. how much it can remember).

* "any system" meaning any system which is both linear (due to the use of diff eqs) and lumped (meaning the state can be broken up into discrete chunks and represented as a vector), but these qualifiers don't affect the answer to your question, since computers aren't restricted to diff eqs and their state is already discretized.

Turns out that the "naive" implementation is a little more involved than it first appeared (but what's new?).

In particular, when you "stick in the sequence accumulator," you need a table of accumulators indexed by something approximating the call stack at the time/place of invocation. This assumes of course a purely functional program -- I don't even know what it means if it's imperative.

The tables are a smaller set than the full DFG; it remains to be seen how it stacks up against the optimized DFG.

Josh