In a previous article, we mentioned that mainstream programming languages do not have any concept of time. This article is the third in a series that examines three languages (first, a markup language, then two programing languages) that focus on timing and synchronization. In the first article, we saw how SMIL defines a powerful timing and synchronization model for presenting multimedia content. In the second article, we saw how the ChucK programming language provides a sample-accurate scheduler for the production of computer music, from digital signal processing algorithms to musical composition; and finally, in this article we look at the synchronous reactive programming model of the Esterel language.
Esterel is our pick from a group of synchronous languages that emerged from early 1980’s French academia, together with others such as Argos, Lustre and Signal (cf. the 1993 survey Synchronous Programming of Reactive Systems by Nicolas Halbwachs), which emphasize control and target reactive systems; often, these are large industrial systems used in domains like aviation or nuclear power, where complex time-critical processes have serious safety requirements.
Esterel grew from an earlier effort to design a language for controlling a robot car; the authors recognizing the need for specific statements to deal with time, namely delays and preemption in order to achieve their goal. The language grew by adopting more formal semantics and experimenting with various compilation techniques, first by using deterministic finite-state automata (which can grow exponentially in size for large programs), and then compiling to electrical circuits, with gates and registers, removing the need for determinization (it is also possible to compile to C, or simulate the generated circuits in software).
In order to see what Esterel looks like, here is its “Hello world” example, from the Esterel v5 Language Primer by Gérard Berry (2004). This program implements the following specification: Emit an output O as soon as two inputs A and B have occurred. Reset this behavior each time the input R occurs.
module ABRO: input A, B, R; output O; loop [ await A || await B ]; emit O each R end module
Esterel deals with input and output signals, such as A, B, R, and O in this example. Signals can be either present or absent, similarly to how a bit can be set or unset, or how a voltage in a circuit can toggle between a low and a high value. Since Esterel can compile to a digital circuit, if follows a simple timing model where input or output events (based on the status, or presence or absence of a signal) are processed at every clock cycle; time is logical and corresponds to the sequence of instants corresponding to hardware clock cycle. Output events happen at the exact same logical time as inputs, in an (idealized) perfectly synchronous model. (Recall that this is the model also adopted by ChucK.)
Esterel is an imperative language, where a statement starts at some instant t and remains
active until it terminates at some instant t’ such that t’ ≥ t (if t = t’, then
the statement is instantaneous). The statement await A starts at some t and remains
active until the signal A occurs at some time t’ > t. In the statement Await A
|| Await B, the || operator indicates that the two child statements occur concurrently:
both start immediately, and the whole statement terminates when both terminate. The ; operator
indicates that its two children happen in sequence, the second one starting exactly when the first one
terminates. [ await A || await B ]; emit O therefore implements the first part of the
specification (the square brackets are simply syntax to ensure the correct order of application of the || and ; operators).
This statement is itself embedded into a loop ... each R statement, which
indicates that the inner behaviour repeats (i.e., starts again) as soon as the signal R occurs. loop is an example of preemption in Esterel: if R occurs before
either A or B, then O does not occur, and the system is reset. On the other
hand, the system also waits for R to occur before restarting after O was emitted.
Readers of the previous article in this series on SMIL will recognize || and ; as the par and seq containers of SMIL; indeed, there are many other
similarities between the two languages (loop and await also have SMIL equivalents
in repeat and event values for timing
attributes). But Esterel is a full-fledged programming language and also deals with values (in
the form of valued signals and variables) and erros, which are outside of the realm of a presentation
language like SMIL. Another big difference (which also sets Esterel apart from ChucK) is how mapping
instants to actual time values is not always necessary; and indeed, there are no predefined time
units like seconds or minutes.
Another example from the primer illustrates this idea. Here, the speed of a vehicle is computed by
using two input signals, Centimeter (emitted every time the vehicle has moved one centimeter),
and Second (emitted every time a second elapses).
loop
var Distance := 0 : integer in
abort
every Centimeter do
Distance := Distance+1
end every
when Second do
emit Speed(Distance)
end abort
end var
end loop A few new constructs are introduced but are easily understood. An inner loop increments a Distance variable for every Centimeter. This inner loop is embedded into an abort ... when statement, which is another form of preemption; an occurrence of Second terminates the count and emits a Speed signal. Notice here that Speed is a valued signal as it carries as its value the number of centimeters travelled within the last second
(i.e., the value of Distance). The loop then repeats instantly and resets Distance to zero; the Speed signal is therefore emitted every second with the current speed of the
vehicle in cm/s. Esterel does not distinguish between something that happens every second, or every
centimer, or every lap, or any other significant measurements implemented by the input signals of the
program.
It is possible to get the value of a signal with the ? operator. But this can lead to causality issues, as in the following program that (attempts) to increment a counter every
time an input is received:
input I;
output COUNT := 0 : integer;
every I do
emit COUNT(?COUNT+1)
end every Because signals are broadcast through an Esterel program synchronously, COUNT must
simultaneously have both the values c (its value before the input signal I occurred)
and c + 1, which is impossible. A solution to this problem is to use the pre operator,
which allows accessing the value of a signal at a previous tick, so emit COUNT(pre(?COUNT)+1) is a valid program. Esterel also has the equivalent of an if statement, so that a signal can be
emitted depending on whether another signal is present or absent; and this is another way to introduce
these cyclic dependencies if the author is not careful. It is still possible however, even desirable
in some cases, to allow sound cyclic programs, so Esterel uses so-called constructive semantics to analyze whether a program is sound, by attempting to prove if the presence or absence of a signal
can be determined deterministically.
We started this series lamenting the absence of the very concept of time in most programming
languages, then we highlighted three different ways to address this issue in the domain of multimedia
presentations, computer music, and reactive systems. We saw that time can be abstracted and even
suspended through the synchronous hypothesis; that new constructs like par and seq can introduce structure into handling events occurring at various points in time throughout the
execution of a program, rather than relying on unmanaged event handlers or opaque promises. This is by
no means an exhaustive survey, but suggests many fascinating threads to pull on in order to improve
the future of programming interactive applications. ⚂⚀