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