Esterel History

1. The Birth of Esterel

In 1982, Jean-Paul Marmorat and Jean-Paul Rigault, two researchers in Control Theory and Computer Science at CMA, were designing a robot car for a race organized by an early microcomputer journal.
They rapidly understood that the tools they had for programming the car were very far from being satisfactory: classical languages did not let them write control algorithms in the way they were thinking about them.

They recognized the need for specific statements to deal with time, namely delays and preemp-tion, and they made the point that the repetition of any signal should count as an autonomous time unit.
They drafted a little language using intuitive keywords.
At that time, Gérard Berry was working on theoretical aspects of lambda-calculus and denotational semantics.

He found the application area and the new ideas interesting and challenging, and he tried to make mathematical sense out of the language proposal.

With Sabine Moisan — who found the name Esterel — and Jacques Camerini, he sorted out the primitives and he tried to use the newly developed SCCS and Meije synchronous process calculi to give their semantics (SCCS is due to Robin Milner and Meije to Gérard Boudol). However, process calculi turned out not to be well adapted to Esterel.

Fortunately, Gordon Plotkin published his seminal book on Structural Operational Semantics.
This new semantics style provided much sharper tools to describe intrinsic semantics, and, above all, it freed the team from the classical vision of concurrency as bound to interleaving and rendez-vous communication, which was inappropriate for the control world.

Gérard Berry and Laurent Cosserat worked out a better set of primitives and made much better sense of instantaneous control propagation and communication, which is the key to get Esterel right.
During the same period of time, two other teams defined synchronous languages based on the same principles: the Lustre team in Grenoble and the Signal team in Rennes. In the sequel, the three teams kept cooperating to establish their common point of view (and, of course, their divergences).

2. Esterel v2 and v3 : from Programs to Automata

Gérard Berry rediscovered the beautiful derivative algorithm of Brzozowski that translates any kind of regular expression into automata and that can be extended to any finite-state language described by SOS rules.
Using this algorithm, Laurent Cosserat wrote the first Esterel v1 prototype compiler to automata. This compiler was entirely rewritten by Philippe Couronné and Gérard Berry in 1985-1986, and the new Esterel v2 system was swiftly used for non-trivial academic and industrial applications.

Georges Gonthier’s thesis was a major step in the development of Esterel. He understood the fundamental distinction between the behavioral semantics, which is of a logical nature and based on mutual agreement about signal presence and values, and causality issues that deal with effective information propagation.

He introduced the fundamental encoding of synchronization and exception by integers, and he designed much more efficient operational semantics and compiling algorithms.

While the Esterel v2 compiler strictly used Brzozowski’s original derivative algorithm in which automaton states are program texts, which is unreasonably memory consuming, Gonthier’s technique uses simple bit-sets as states, which is orders of magnitude more efficient.
Finally, Gonthier designed the overall architecture of the Esterel v3 compiler, which was written in 1987-88 by Raphaël Bernhard, Gérard Berry, Frédéric Boussinot, Annie Ressouche, Jean-Paul Rigault, and Jean-Marc Tanzi. The Esterel v3 effort was strongly supported by Dassault Aviation, which acted as an early adopter of Esterel.

The architecture and some intermediate codes have been kept basically unchanged since then. Esterel v3 has been used rather heavily. It worked well for small to medium size programs, but blew up or big programs for which state space explosion turned out to be the rule.

3. Esterel v4 : from Programs to Circuits

The next progress came from interaction with Jean Vuillemin’s group at Digital Equipment Paris Research Laboratory.This group was developing the PeRLe FPGA-based programmable hardware machine.
Many of the hardware designs involved controllers that are a pain in the neck to write with gates and registers, and the group thought that Esterel was very well adapted for direct controller specification.
G. Berry learned about logic and hardware and developed a structural translation of Esterel programs into gates that could be used to directly generate netlists, fully avoiding the state space explosion of Esterel v3.

He then extended the logic translation to software implementation of general Esterel programs.

Hervé Touati brought fancy Computer Aided Design technology in the picture and he showed how to deeply optimize the obtained netlists.

Xavier Fornari extended the hardware optimization techniques to deal with software generation. Frédéric Mignard cleaned up many processors of the Esterel v3 compiler and built a bunch of new ones. Jean-Pierre Paris implemented external task control by the exec statement. Jean-Paul Marmorat and Jean-Pierre Paris developed the graphical simulator and symbolic debugger xsimul, which later became the current xes tool.
The resulting Esterel v4 compiler was delivered in 1992.

4. Esterel v5 : Handling Cyclic Programs

Esterel v4 was much better than Esterel v3 since it avoided state space explosion.
However, it required the generated circuits to be acyclic. Although this condition is standard in hardware or data-flow systems design, it turned out to be too restrictive for Esterel.

The older Esterel v3 compiler was quite smart about causality and was able to compile many correct but cyclic programs that were rejected by the more recent Esterel v4 compiler.

This made our users unhappy, and we could not convince them that the problem lied in their bad programming habits. On the contrary, they convinced us that making safe cycles is natural when programming symmetric protocols or resource access strategies.

The solution came from an encounter with a paper of Sharad Malik on cyclic circuits, which Gérard Berry later extended with Tom Shiple (Berkeley University) by showing the equivalence between three points of views on Boolean circuits:

the electrical point of view that deals with current propagation and delays,

the constructive logic point of view that deals with proving values of Boolean variables in a constructive way, and

the denotational point of view of Scott’s ternary logic.

This lead to the constructive semantics and to the current Esterel v5 compiler.

Technically, the compiling algorithms for the constructive semantics are based on Binary Decision Diagrams. They were implemented by Tom Shiple and Horia Toma with help of Herve Touati and Jean-Christophe Madre, using the Tiger BDD system of Olivier Coudert, J-C. Madre, and H. Touati.
Ellen Sentovich made many contributions to the presentation of the semantics and to optimization techniques, which were developed and implemented by Horia Toma.

Xavier Fornari is now in charge of the development of the Esterel v5 compiler, which has been heavily tested by Monica Robert.

5. Esterel Programs Verification

The verification tools for Esterel are developed by a group headed by Robert de Simone, who also deeply contributed to many aspects of the design of the language and tools.

Didier Vergamini developed the early automata manipulation algorithms included in the Auto explicit verification system. Valérie Roy developed the Autograph automata visualization tools. Annie Ressouche wrote most of the programs that interface the compiler and the verifiers.
Amar Bouali wrote the current Xeve BDD-based verification package using the Tiger library.
Carlos Puchol, from University of Texas, and Lalita Jagadeesan, from AT&T Bell Laboratories, developed the Tempest temporal logic verification system for Esterel, later improved into the Hurricane BDD-based verifier. These tools are accessible from the Esterel downloads page.

6. Extensions of Esterel

SyncCharts is a graphical version of Esterel developed by Charles André at I3S Nice using the drawings initially introduced by Davis Harel for Statecharts. The Simulog company is currently commercializing an environment for Esterel and Syncharts.

The ECL language developed by L. Lavagno and E. Sentovich at Cadence Design Systems is an integration of Esterel into C. A similar effort is the Jester integration of Esterel into Java.

Maestro is an Esterel-based robot-control language, developed in Eve Coste-Manière’s group at INRIA.

Synchronous languages are not enough for complex systems programming and they must interact with other languages and communication styles, in particular with asynchronous ones.

The CRP formalism (Communicating Reactive Processes) developed by G. Berry, R.K. Shyamasundar from TIFR Bombay and S. Ramesh from IIT Bombay, India, is an attempt at marrying Esterel and CSP.

Gérard Berry and Ellen Sentovich are currently working on Multiclock Esterel, an extension that drops the single-clock requirement of the current language.

7. Current Developments

The Esterel team is currently developing Esterel v6, a modular version of Esterel. The idea is to use a separate compilation into subcircuits later linked to form bigger circuits. This process is non-trivial because of a complex phenomenon called reincarnation. The advantage is to separately optimize submodules before performing global optimization or verification. This should yield a significant improvement in the size of programs handled by the optimizers and verifiers.

The newly introduced Esterelv5_90 compiler handles the pre operator of Lustre and Signal. This paves the road for a later smooth embedding of synchronous programs written in data-flow style into Esterel programs.

A better hardware generation should be available soon. It will translate Esterel programs into VHDL or Verilog, including data-handling.