Lambda the Ultimate

I definitely recommend the Esterel book and papers, although I would probably not consider Esterel particularly "declarative." (It is an unusual language and I find it a bit difficult to get my head around how to design programs in it.)

Synchronous reactive programming languages, like Esterel and Lustre, typically execute the `whole graph` (whole program) on a per-cycle basis. That is, there is no special optimization to only recompute the parts that updated.

As a small aside, I don't think this is actually correct, at least with respect to Esterel. The literature (and Compiling Esterel in particular) describes several rather different methods of compiling/executing Esterel code. Some do have the property you describe, but some do support minimal recomputation. There is a brief discussion of the tradeoff, which of course depends on size of program and expected type of inputs, whether you plan to run on a sequential CPU or synthesize custom logic gates, etc.

There is one execution model in particular (that used in the Columbia Esterel Compiler, IIRC) which is quite similar to the type of "topological sort plus dynamic scheduling" that we recently discussed in another thread. Extra tricks are required since Esterel does not require a statically acyclic graph, only that the graph be dynamically acyclic for any particular set of inputs (which is incidentally quite a sophisticated condition and which leads, in my view, to a lot of the subtle difficulties with Esterel).

Anyway, I think this is a very interesting body of work that has unfortunately not had the impact on mainstream programming that it deserves. There is quite a number of strands of thought that lead in a similar direction: FRP, synchronous reactive, statecharts, CEP, data stream query, hardware design languages, spreadsheets, Dedalus (Datalog + time), even rules engines/production systems are related. Unfortunately, there has not always been sufficient cross-pollination among these areas, and each has too often remained concerned with its own traditional areas of application (GUIs/animation, databases, AI, hardware, etc.), to the point where the lack of even a shared vocabulary makes navigating the literature somewhat difficult. Too bad.

I believe it is difficult to squeeze minimal computation AND hard real-time into the same implementation, though there are certainly benefits to achieving both (lets you squeeze in some asynchronous computations or save energy). In any case, I'm only reporting on the couple implementations I've seen fielded - a couple years before the Compiling Esterel book was written.

I agree that computing with time deserves a heavier impact on mainstream programming.

With RDP, I'm tackling some problems that I think are holding back the FRP and synchronous reactive models - e.g. with regards to open, extensible, reconfigurable, parallel and distributed systems. But I'm at a loss with regards to `common vocabulary`, so I end up creating my own. ;)

The lack of a shared vocabulary, optimization in FRP, and the OP's reference to declarative languages made me think of the
Rete Algorithm. I wonder how Esterel's optimizations relate to work done in Expert System technology in the 70s, as well as Statechart compilation and table compaction.

This is exactly what I had in mind when I mentioned "rules engines/production systems." I think the less well-known LEAPS algorithm is probably even more closely related than Rete.

Regarding Statecharts: I believe it's easy to express programs in Esterel that would require exponential blowup if expressed as Statecharts (or else extensive use of state variables alongside the static structure of the states). But yes, there is definitely a deep connection.

I recently spent a bit of time looking for an interpreter/VM for any kind of statechart-based language, and apart from one rather neglected research project (SVM), I was surprised to come up empty-handed. It seems that synthesis and hand-editing of rather ugly C/C++ is much more common. It seems that the generated code is usually in a quite straightforward FSM style (e.g., functions/objects with big switch statements), although maybe there are proprietary Statecharts compilers which produce more sophisticated code.

There was some work done at ITU, the SCOPE compiler; I first noticed it via this paper: A. WÄ…sowski, Flattening Statecharts without Explosions from LCTES 2004.

I believe the flattening algorithm is (or at least was) used in IAR visualSTATE a commercial tool I have enjoyed using professionally.

The code does not use big switch statements but rather takes advantage of the fact pointer-to-member functions in C++ are essentially compilable down to a GOTO instruction. Apart from that, there are other concerns to think about for a statechart-based language. Samek covers the issues quite well and also points out common implementation pitfalls in his books.

From a language design perspective, we would like to:

1) Statically determine if the statechart requires all the features of a statechart
2) Based on the structural analysis, generate the most efficient code possible
3) Have any value be lift-able to a signal
4) Determine if transitions can be dynamic or are all static, and use static knowledge of transitions to cache the call chain and avoid branching.
5) When necessary, make rollback to prior history states as cheap as managing the current state and its nearest transition states.
6) Modularity guarantees. The control flow provided by history should only be triggered via non-local control flow mechanism, and the substate should have no knowledge of its super state.
7) Efficient state clean-up, including possibly in-place memory re-use.

Yes, I am an admirer of Samek's work as well. Practical UML Statecharts in C/C++ is a great book, much better than the title would suggest. I haven't used QP in any seriousness, but it looks to be quite good. The code doesn't use "big switch statements," true, but it does use small ones, and since it is intended to be clean enough to be maintained by hand, I do think it falls into the category of fairly straightforward. But I don't mean to say I don't like it: I think it's a very nice approach.

Also, in response to this and the prior comment... To be clear, I was specifically looking for an interpreter/VM for something based on statecharts, hopefully a design for something that might be suitable for embedding into a larger application to dynamically load/execute small state machines. This mostly rules out bigger compilation frameworks and definitely rules out design patterns for hand-coding. I guess, to sloganize a bit, I was hoping for something like "Lua for statecharts." (As it happened, I found a small project written in Lua (rFSM, but that's not quite the same thing.)

That's a nice list of language design issues, and of course there are many more. If starting from scratch, particularly with a textual representation (which I feel is necessary), it's not obvious to me that statecharts are the right formalism. Certainly they have intuitive semantics and are pleasant enough to work with. I would broaden my slogan, though, and admit that I really just want something like Lua for synchronous reactive programs in general. But anyway I'm starting to feel like I've hijacked this thread, so I'll give it a rest.

In my humble opinion, any language purporting to be "Lua for statecharts" needs to allow constructing FSMs using both Moore and Mealy machines. You need both the "fire and forget" representation for transitions that simple Moore state machines provide, and the alternate representation Mealy provides for where to associate the action. While academics point out they are equivalent in expressive power, the combined use of both allows achieving minimal number of states and transitions to represent a complex system. In this way, I claim you need both.

As for how good Samek's approach is, there are some weaknesses. It is not type safe, he relies on clever casting tricks in his Q_TRAN macros that manipulate pointer-to-member function logic, and this particular encoding using macros means that all transitions are equally expensive since he must treat every transition as possibly dynamic due to loss of static structural information that should otherwise be available.

Another very good system is Adrian Thurston's Ragel State Machine compiler, one of the world's most widely used state chart compilers. Why is it so widely used? Because it was what drove Zed Shaw's Mongrel web server, back when Mongrel was the go-to web server for Ruby on Rails.

I fully agree with your first paragraph. I mostly agree with the second, but I think that in its niche (hand-written C/C++) these shortcomings are quite forgivable and even to some degree idiomatic.

I hadn't seen Ragel, it looks pretty interesting. I'll be reading more about it. Thanks!

Of course, you can still model programs that take an unknown number of cycles to complete, e.g. for incremental tasks. This simply requires keeping some state.

I'm not sure about that. A very important property of Lustre (in particular in the SCADE variety) is its deterministic memory allocation for program state. Lustre allows for using historic dataflow values (via the followed-by operator), but the number is bounded and can be decided at compile time.

Therefore, once the program is compiled, the worst case execution time can be determined. Of course, the real CPU time cannot be directly derived from Lustre, but has to be determined from the generated C/Ada code on a specific CPU.

What example are you thinking of for an incremental task with an unknown number of cycles?

A classic example of a task taking many cycles in finite space would be fibonacci sequence - it only takes two or three integer registers to compute, but to compute fib N would still take about N cycles using those registers. If you are looking for real problems that take an unknown number of cycles (or even infinite cycles), look to convergence problems, control theory, Kalman filters and similar.

Many incremental operations, even many search problems (planning, SMT solvers) and many batch processes (such as ray tracing) can be achieved with bounded memory. Also, even if your language constrains you to a limited amount of internal memory, you can generally access external memory (databases, for example, or even a Turing tape). In general, you cannot assert the worst-case execution time for a task based on real-time instants and constant space. Real-time would also require you know a worst-case for how many instants are needed for an incremental process.

There is no difficulty at all modeling various esoteric Turing-tarpits in a synchronous programming language, with each `instant` representing some constant number of steps.

What synchronous programming can offer (by restricting expressiveness in each time-step) are worst-case latency bounds for interrupts, and preventing the batch processing from interfering with real-time signal processing. It also makes real-time the default mode for programming, with batch processing being the mode developers need to work at (forcing developers to write an incremental program).

I will add the Prelude language to the list (http://www.lifl.fr/~forget/prelude.html). Prelude is built upon Lustre and extends the language by allowing the definition of multi-periodic systems.

There are a number of static analysis tool for the language (e.g. for schedulability analysis) and the compiler targets Muli-threaded C code generation.

Nice! I will definitely check this out. As a first question, how do you deal with cycles? Do you require a statically acyclic structure? If not, do you detect cycles dynamically or will the program just loop? How do you deal with other causality problems?

A program cannot trigger external events, only wait for them.
Hence, cycles due to external events are impossible.

Internal events follow a stack execution rule that breaks cycles.
I show an example in the tutorial that imposes a constraint between two variables.

The answer is: Programs are acyclic, but some expressions that use internal events seem to be cyclic in the practical sense that they may execute multiple times during the same reaction.

Note:
Céu also avoids `tight loops´ at compile time.
The following yields a compile time error:

loop do
    a = a + 1;
end

Leo.

Can you please elaborate further? Walid's work restricts recursion. Why do you say "the question remains of restrictions for RT code"? Is what you are looking for is a library of DSLs each with different resource bounding semantics, perhaps enabling more modular resource control? If so, do you have a problem for me you could sketch out to demonstrate the need for such semantics?

Thanks.

I don't work in RT, so I want to be clear that this is postulating.

I'm guessing that we want to control space over time (neelk's work) and mungy details like oversubscribed hw (think SoCs). Even for bounded recursion, we still may want something of a time bound over time -- for building and using data structures, a dependent clock calculus might represent some of this, but I can imagine a lot.that I don't know how to express. This is an area I cannot.believe a calculus solves the hard parts without a demonstration. Maybe I'm wrong and this was all the embedded rt community needed; it's not my thing.

Taha's related work, Event-driven FRP, deals with this concern. In Real-time FRP, events still have to propagate through an entire system. Event notifications can thus swamp the system. To address this concern, Event-driven FRP was created as a practical way to take advantage of the formal methods provided by RT-FRP.

Neelk's work with FRP is to model it with linear typing, allowing much greater control over how many observers there are on a given resource (i.e. fanout) and the space costs at any instant.

It is unclear to me how event-driven FRP deals with this concern at all - except as a coincidence that Taha describes RT-FRP in the same paper as E-FRP. Developers with E-FRP must still constrain event-processing (especially accumulators) to reason about space resources.

I don't like the idea of using events in FRP. They hinder scalability and resilience and extensibility, and processing events requires too much non-essential internal state (though events do make that state easier to manipulate). Taha's E-FRP requires that each event is serialized into some arbitrary ordering, which won't scale much beyond its intended use as a robot controller.

Our solutions for controlling space shouldn't be sacrificing scalability.

A lot of the interest in RT is for using limited physical resources. A robot's hands, DSP units and bandwidth for audio, memory on a mote. A 'real' language that claims to solve problems in the RT domain should have a position on these.

A calculus / theoretical solution tries to model the domain concerns, and I won't believe the model until it's been tested. Currently, a popular solution is for the language to simply get out of the way of a systems-level programmer. This suggests, to me, that the models go too far in trivializing the problems in their claims of being 'RT' languages.

These resource concerns seem often, but not always, orthogonal to the overall orchestration ('synchrony hypothesis'), so the problem is not necessarily as bad as I make it out to be. E.g., in a Lustre program, a developer can be careful to make sure only one event sequence uses the DSP unit. That doesn't mean the orchestration language actually helped achieve that. Lustre might be used in a RT setting, but that doesn't mean it's actually addressing RT concerns.

While the problems of real-time and bounded-space programming do often intersect, I think it a mistake to conflate them, e.g. to claim that a language fails to address RT concerns simply because it doesn't address resource control concerns. Memory, DSPs, GPUs, regions of display, space on GPGPUs, etc. are all potential resources to be allocated and controlled.

I agree that our RT languages should at least not interfere with addressing these concerns, thus allowing developers to form their own idioms and disciplines. C++ auto_ptr serves as an adequate approach to linearity if one applies a little discipline. Object capability security offers many patterns for managing resources.

IMO, the goal of an RT and other cross-cutting features is not to address all the concerns, but rather to simplify reasoning and free up brainpower so developers can spend their thoughts on other relevant concerns.

I think we all agree that there are nice techniques out there.

Decoupling orchestration and resources is a bad idea for what people actually mean by RT. Don't get fooled by the "time" part of the name and gloss over the "real" part. Real physical resources break software abstractions of time. We can't just virtualize because there is a time bound. The theories to solve the problems might decouple them, but the end solution must address both.

My higher point is that, for any other PL 'solution', we risk alienating actual RT users if we overclaim. "ocaps + RT-FRP + control theory + magic dust gives you what you need" is an unsubstantiated claim. I admit this is a bit of a strawman, but I hope my examples show why I am skeptical of current notions of language-level 'H-RT' solutions.

To my pedant eye, there is a huge difference between coupling concerns and conflating them (and, conversely, between decoupling concerns and distinguishing them).

I agree that we should not `decouple` or `separate` the concerns of time and resource control. Similarly, security is not a separable concern. There are many concerns that are difficult or infeasible to separate. My own efforts with RDP are, essentially, an attempt to wrangle many such concerns into just a few, simple abstractions and idioms. (It's a tight fit.)

Regarding your example: if I were to suggest use of "ocaps + RT-FRP + control theory + magic dust", that implies that I do not have a 'PL solution' to the problem. I have discipline, design patterns, frameworks and architecture - the same substance from which I'd build an RT-app in a more conventional language (such as C). While I can respect being skeptical of an unproven solution, it isn't clear to me how this example serves your point.

I wrote a paper once that included constructs for reasoning about events that could happen in the future as well as those that occur in the past by analyzing code. Its not the same thing for sure, but it is related to what crazy things we can do with causality. However, I got out of the aspect business after I realized how difficult it is to reason about code like this in practice.

Physics-based programming abstractions provide some hope in reasoning about what could probably occur in the future, you just run the simulation ahead a few time steps without considering external inputs and make this result visible in your signal abstraction. Bullet/tunnel-resistant collision detection works this way.

Anti-causal reasoning is actually a major foundation for my RDP paradigm. There I call it `anticipation`, and I've designed RDP such that anticipation is composable in an open system (no analysis of code is necessary).

Note that composing anticipation isn't the same as actually performing it. I only ensure that anticipated state will propagate from point A to point B across any intermediate computation, as opposed to working entirely in the present. Yet this is sufficient to distribute the benefits of prediction and planning systems injected into the model. I can improve results in a whole program, transparently, by injection of a prediction filter (with a world model, leveraging some state) near sensors, i.e. without requiring direct references to the prediction or plan.

As an advantage I did not anticipate, composable anticipation certainly makes it easier to chain prediction and planning systems together, and to combine prediction and planning models.

I've developed idioms for leveraging anticipation, and it greatly helps counterbalance the fact that I've eliminated local state for reasons involving resilience, persistence, declarative reasoning, live programming, and garbage collection (control over space). (RDP developers can access state; it's just modeled as external, like a database or filesystem.) I've developed external state models that also compose with anticipation.

My vision is similar to Bret Victor's vision of abstracting time, described in his Inventing on Principle video. My goal is to get anticipation all the way down to the command-and-control protocols and sensors, such that it would be easy for me to display the `anticipated` future track of a vehicle, for example, without relying on access to its routing information.

Z-bo's already heard much of this, but I thought it worth reinforcing his point on the value of anti-causal reasoning. It does not seem to be a very well-explored subject in PL. Even the weaker form I provide - simple composition of anticipation - could become a disruptive force in programming languages.