Declarative programming for deterministic real time control

Question

Let's say you want control a motor in real time. Normally you would use a microcontroller or PC with e.g. c-programming language. So you would use an imperative approach. You tell the microcontroller exactly HOW to do the motor control. And for determinism you would use specific time frames to do the control.

My question is, would it also be possible to use a declarative approach with e.g. a functional programming language? In declarative algorithms I tell the control device HOW to do the motor control. E.G. I want to use F#. What are the advantages or disadvantages to that with functional programming? Could that also be deterministic? Would you use it for real time controls? If not, why would you not use it?

Answer 1

A lot of this kind of code is already much less imperative than you might think. It's usually very close to a functional reactive programming model, where a function gets called in response to some external event, in this case a timer tick.

Typically, that function receives some sort of context data structure as an argument, which it can use along with reading some registers to determine its previous state. It then typically modifies some registers to perform its task, and mutates the context to track its next state.

It's really not that much of a modification to return a new context and register state instead of mutating the old one. And we have a pretty good boundary where we know the old context is going out of scope, where the compiler can deterministically schedule some garbage collection.

I've actually been mulling creating an FRP language that's usable on microcontrollers. It's a much closer fit to the hardware than people realize.

Answer 2

There is a long history of data-flow programming languages for reactive systems. In the eighties, several languages were developed under the Synchronous Programming approach. I think that Translating Discrete Time SIMULINK to SIGNAL would be a good starting point to get exposed to Simulink, Signal. Also, there is a DC motor use-case.

Synchronous approach

Instead of manipulating values, synchronous languages define equations over synchronous flows. At each logical clock step, inputs are read and instantaneously propagate to local variables and outputs. The zero-delay assumption means that it takes a constant time to update your state (up to you to prove that the actual execution time always fits in the required physical time period). Here is an example with an internal state, in Lustre:

node sum (in : int) returns (sum : int);
let
   sum = in + (0 -> pre(sum));
tel;

The arrow separate code that is executed the first time (initialization, on left) and code that is updated at all other instants (general case, on right). On the right of the arrow, it is thus allowed to refer to past values of sum: this is the purpose of pre.

With the above definition, we can analyse dependencies ahead of time, make a static scheduling of code and produce C code based on an init function and a step function, which basically are:

/* local globals */
inline int sum, in, tmp;

/* Interface with other code */
extern int read_in();
extern void write_sum(int);

void sum_init() 
{
   tmp = 0;
}

void sum_step ()
{
   in = read_in(); /* external */
   sum = tmp + in;
   write_sum(sum); /* external */

   /* Update memory */
   tmp = sum;
}

Today there seem to be a renewed interest for Functional Reactive Programming. Even though there are some research around Real-Time FRP , the FRP generally provided does not offer the same kind of static guarantees that are required in embedded/critical systems:

• constant memory usage: memory is statically allocated and completely determined ahead of time (no GC, thanks). Past values are only accessed through delay operators (e.g. pre), so the number of nested delay operators indicates how many previous versions of a variable to keep, which is statically known. You could imagine that you build a sliding window of memory to observe the infinite flow described by your equations.

• constant execution time: worst-case execution time of each time-step is much more easier to compute.

• causality analysis: the order of operations is known in advance. When designing distributed reactive systems, you can guarantee that you won't deadlock.

• Synchronous languages also use clocks, which determine when a computation must occur: you can write x when b to have a flow where the only values computed exist when the boolean data-flow b evaluates to true (and notice that b is a data-flow itself, which can also have a clock).

  In the Signal language, which allows to describe distributed units of computations, clocks allow for example to emit only the necessary synchronization information between separated, asynchronous, units: if you transmit a tick counter between two systems and the clock relationships tell you that flow A is present every 5 ticks and flow B every 7 ticks, you do not need to also transmits the actual boolean clock flow of A and B: the receiver knows exactly when to read a value for A and one for B, based only on the tick. Clocks form boolean relationships and can sometime be inferred implicitly from the known status of other clocks.

Those languages are developed in industrial contexts, generally as part of a larger tool-chain: look for SCADE, etc. Depending on your usage, you might prefer to use academic compilers.

What about F#?

F# is garbage-collected, as far as I know. I tend to think that you can execute controllers in a garbage-collected environment, if you are careful enough and your device does not require precise timings. I would personally mutate existing variable to avoid allocating memory during execution, so that the actual memory consumption in your control loop would be zero.

If memory is continuously allocated (and then collected, hopefully), you might have, on average, a constant memory usage with possible GC pauses. The garbage-collector is not real-time (even though there exist real-time GCs), but if the physical period is large enough, you will have a low probability of missing a deadline.

If missing a deadline is out of question, use some generated code from the above languages, or write one by hand if you only need a simple control loop. Use a low-level language like C or Ada (maybe within a Real-Time OS or directly on the micro-controller).

Answer 3

Yes, so long as garbage collection doesn't interfere with your real-time requirements and you have sufficient memory and processor horsepower.

Imperative languages allow you to have finer control over the computing resources that are being used (precisely because you're describing how). You may need this level of fine control if you're running motors with real-time demands. Declarative languages commonly abstract those details away from you, by design.

If you're going to go with functional purity (i.e. full immutability), you might have to get very clever with your data structures to get them to perform well enough (cf. Okasaki).

Note that using F# will require you to have an ecosystem that supports F#; at a minimum, you will need to support the .NET Compact Framework. You might also be interested in the Netduino.

You could get the best of both worlds by writing a small DSL in an imperative language (it can be a small set of functions) that optimizes for motor control but still gives you the declarative capabilities you want.