How to Generate (Hard) Real-Time Code from Declarative Programming Languages?

Hello all!

First let me emphasize I'm a bit of a noob with language design and implementation, so feel free to dumb things down in response (in fact I would prefer it!)

I'm interested in the possibility of generating code for hard-real-time software from a declarative language. Two examples I've seen are Lustre (for reliability software) and Erlang (not sure how this could work actually since it's a general purpose language...) But when I dig down to find out exactly HOW we know that these systems generate real-time code, I come up empty handed. Where are the white papers / books / etc on how to determine a) that real-time code can be generated from a particular semantics in the first place, and b) how is the code actually generated in practice? Alternatively, how might we answer the same questions for soft-real-time code generation? Finally, can we answer this question for VMs as well, such as with .NET CIL code?

Hopefully this area of research isn't still a black art :)

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Atom and Esterel

You might take a look at Atom, which is a DSL embedded into Haskell, and is used to produce real-time code for commercial products. It's open source, so you can see what they do. You could also look at the book Compiling Esterel, or some of Stephen Edwards' papers on the same topic.

Aside: Erlang isn't really a hard real-time language.

Seconded

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

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. Since the allowed functions are themselves finite, this makes it easy to determine exactly how long each cycle will take. Inputs and interrupts are processed only at the beginning of a new cycle, and buffering is constrained (e.g. a signal might only be on or off).

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. But the important feature is that you have a precise idea of how long it will take to process new inputs and interrupts, and that the batch processes are explicitly modeled so they can't interfere in unexpected ways with the real-time parts of the program.

Haskell's Atom uses a similar technique. A point I found interesting is that, given an `if` conditional, Atom will simply execute BOTH branches in order to preserve the timing properties. Outputs of the dead branch are simply dropped. (This observation might be dated. I've not tracked Atom since its initial release.)

Real-time is really about semantics, not implementation. The hard real-time properties do take some extra attention (since you need to guarantee real-time garbage collection and scheduling, etc.). Yet, supposing you simply interpret a real-time model, and nothing is terribly wrong with GC and so on, you will still achieve soft real-time properties and a nearly flat memory profile. So unless you're designing for an embedded system controller or mission-critical device, you can probably do without the hard real-time.

Erlang's concept of real-time is definitely in this `soft` class - you can achieve predictable performance and space with just a little discipline.

Synchronous reactive

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.

Hard Real-time

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

Shared vocabulary elusive, declarative languages

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.

Indeed

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.

Statechart compiler

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.

Miro Samek's Quantum Framework handles statecharts

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

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.

Issues with Statechart implementations, including Quantum

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

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!

determinism

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?

Hard Memory Limits do not imply Real-time

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

The Prelude language

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.

An Esterel inspired new language

Hello, I'm currently working on a new language inspired in the Esterel
synchronous reactive execution model.
It has a small footprint (2Kb-ROM, 100b-RAM, 16bits platform) and is targetted at real-time/embedded systems.

http://www.ceu-lang.org/

It's open source and I've been using it a lot with Arduino and TinyOS.

An important semantic difference to Esterel is that Céu doesn't
allow simultaneous events. As a consequence, programs can share memory deterministically (through a static analysis).

Nice! I will definitely

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?

Céu differentiates External vs Internal events

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

For any of these functional

For any of these functional etc. languages over time, I'd look at Walid Taha's RT-FRP work as a simple first step. He basically restricts the expressiveness within any time step.

The question remains of restrictions for RT code. For example, whether you want to allow heap allocation (requiring RT-GC) and how you want to bound recursion.

Finally, I think a big thing in practice for such systems is having good meta/staged compilation. There were a bunch of great ML papers about cleanly typing the separate stages.

First and second sentences seem incongruent

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

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.

What is meant by oversubscribed hardware?

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.

Linear Typed

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

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.

Conflating real-time and resource control

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.

Decoupling orchestration and

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.

Not separate concerns

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.

Answer, Part 1

generating code for hard-real-time software from a declarative language. Two examples I've seen are Lustre (for reliability software) and Erlang (not sure how this could work actually since it's a general purpose language...) But when I dig down to find out exactly HOW we know that these systems generate real-time code, I come up empty handed.

How they generate code is an implementation detail. The important part of the system is the semantics, developing highly re-usable abstractions, since building real-time systems is hard and error-prone. With a real-time system, component communication needs to be well-defined and fair. There are also safeguards like 'deadlines' and static analysis tools for schedulability analysis.

Real-time systems are regulated by feedback and causality. Feedback can be positive or negative, open or closed, etc.

What makes Erlang work as a soft real-time system is its feedback mechanism: it has pure computations hedged by supervisory computations with timers for determining timeouts. There are many 'patterns' for composing real-time systems. Some of the best high-level explanations are by Douglas in his real-time object-oriented design books.

Causality is a much bigger topic than feedback. For example, anti-causality cannot be physically implemented in reality, but it is a an extremely useful concept - you cannot optimize a control system without both 'backwards in time' and 'forwards in time' models. Note the trick here is to use models of time, rather than reason directly based on the present. We can create a model for what we think will happen, and continuously measure what actually happens, and make corrections to re-plan the future. In some cases, we can even cheat the future through implicit knowledge about the future! For example, the nose cone of a plane can have a sensor that can provide useful information that can then be used to determine wing lift in advance of the wing being affected by what will happen when turbulence arrives. Here, the central concern, especially when thinking about how to build hard real time systems at intergalactic scales, is propagation delay vs. latency. A control theory problem becomes in part also an information theory problem, because no possible solution will ever be perfect - we only have nonconvex solutions.

This is probably more abstract than what you were looking for, but I have been wondering similar things as you for awhile in order to pin down the right feature set for a control flow language I am working on, and these thoughts are where my mind heads.

I wrote a paper once that

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.

Anticipation

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.

Answer, Part 2

I realize there may be a need to step back and answer a broader question here: What are the known limitations of Classical Real-time Systems?, and How has theory contributed a modern approach to real-time systems?, and What will it look like to build real-time systems 100 years from now?

For example, there are more QoS metrics than simply timeliness. There is a recent paper featuring a discussion on the pitfalls of applying real-time techniques from one problem domain to another problem domain, wireless sensor networks: Timeliness in Wireless Sensor Networks: Common Misconceptions. But there are many more papers like this one.

Further, for schedulability analysis, many forms of the scheduling problem are NP-Hard. It is perhaps better to solve the problem by avoiding it, e.g. don't expose antiquated scheduling abstractions like priorities and expect programmers to do priority mapping correctly even with the help of tools.