Esterel

Last updated

Esterel is a synchronous programming language for the development of complex reactive systems. The imperative programming style of Esterel allows the simple expression of parallelism and preemption. As a consequence, it is well suited for control-dominated model designs.

Contents

The development of the language started in the early 1980s, and was mainly carried out by a team of Ecole des Mines de Paris and INRIA led by Gérard Berry in France. Current compilers take Esterel programs and generate C code or hardware (RTL) implementations (VHDL or Verilog).

The language is still under development, with several compilers out. The commercial version of Esterel is the development environment Esterel Studio. The company that commercialize it (Synfora) initiated a normalization process with the IEEE in April 2007 however the working group (P1778) dissolved March 2011. The Esterel v7 Reference Manual Version v7 30 – initial IEEE standardization proposal is publicly available.

The Multiform Notion of Time

The notion of time used in Esterel differs from that of non-synchronous languages in the following way: The notion of physical time is replaced with the notion of order. Only the simultaneity and precedence of events are considered. This means that the physical time does not play any special role. This is called multiform notion of time. An Esterel program describes a totally ordered sequence of logical instants. At each instant, an arbitrary number of events occur (including 0). Event occurrences that happen at the same logical instant are considered simultaneous. Other events are ordered as their instances of occurrences. There are two types of statements: Those that take zero time (execute and terminate in the same instant) and those that delay for a prescribed number of cycles.

Signals

Signals are the only means of communication. There are valued and non-valued signals. They are further categorized as being input, output, or local signals. A signal has the property of being either present or absent in an instant. Valued signals also contain a value. Signals are broadcast across the program, and that means any process can read or write a signal. The value of a valued signal can be determined in any instant, even if the signal is absent. The default status of a signal is absent. Signals remain absent until they are explicitly set to present using the emit statement. Communication is instantaneous, that means that a signal emitted in a cycle is visible immediately. Note that one can communicate back and forth in the same cycle.

Signal Coherence rules

Thus

present A else     emit A end

is an erroneous program: the writer "emit A" must run before the reader "present A", but this program asks the "present A" to be performed first.

The language constructs

Primitive Esterel statements

Pure Esterel has eleven primitive statements. [1]

nothingTerminates immediately with no other effect.
pauseBlocks control flow in the current cycle for resumption in the next cycle.
p;qRuns p until it terminates and then, in the same reaction, start q.
p||qRuns p and q in parallel
looppendRestart the body p as soon as it terminates. Every path through the loop body must contain at least one pause statement to avoid unbounded looping within a single reaction.
signalSinpendDeclares a local signal.
emitSMake signal S present in the current instant. A signal is absent unless it is emitted.
presentSthenpelseqendIf signal S is present in the current instant, immediately run p, otherwise run q.
suspendpwhenSSuspends the execution of the body in instants where S is present.
trapTinpendDeclare a labeled escape block.
exitTJump to the end of the innermost T-labeled escape block.

Derived Esterel statements

Esterel has several derived constructions: [2] [3]

Derived statementExpansion
haltloop pause end
sustainsloop emits; pause end
presentsthenpendpresentsthenpelse nothingend
awaitstrap T in loop pause; presentsthen exit T end end loop end
await immediatestrap T in loop presentsthen exit T end; pause end loop end
suspendpwhen immediatessuspend presentsthen pause end;pwhens
abortpwhen (immediate)strap T in suspendpwhen (immediate)s; exit T || await (immediate)s; exit T; end
weak abortpwhen (immediate)strap T inp; exit T || await (immediate)s; exit T; end
looppeachsloop abortp; halt whensend loop
every (immediate)sdopend everyawait (immediate)s; looppeachs

Other Esterel statements

The full Esterel language also has statements for declaring and instantiating modules, for variables, for calling external procedures, and for valued signals.

Example (ABRO)

The following program emits the output O as soon as both inputs A and B have been received. Reset the behaviour whenever the input R is received.

module ABRO: input A, B, R; output O;  loop   [ await A || await B ];   emit O each R  end module

Advantages of Esterel

Disadvantages of Esterel

See also

Related Research Articles

Mercury is a functional logic programming language made for real-world uses. The first version was developed at the University of Melbourne, Computer Science department, by Fergus Henderson, Thomas Conway, and Zoltan Somogyi, under Somogyi's supervision, and released on April 8, 1995.

Interpreter (computing) Program that executes source code without a separate compilation step

In computer science, an interpreter is a computer program that directly executes instructions written in a programming or scripting language, without requiring them previously to have been compiled into a machine language program. An interpreter generally uses one of the following strategies for program execution:

  1. Parse the source code and perform its behavior directly;
  2. Translate source code into some efficient intermediate representation or object code and immediately execute that;
  3. Explicitly execute stored precompiled code made by a compiler which is part of the interpreter system.

Verilog, standardized as IEEE 1364, is a hardware description language (HDL) used to model electronic systems. It is most commonly used in the design and verification of digital circuits at the register-transfer level of abstraction. It is also used in the verification of analog circuits and mixed-signal circuits, as well as in the design of genetic circuits. In 2009, the Verilog standard was merged into the SystemVerilog standard, creating IEEE Standard 1800-2009. Since then, Verilog is officially part of the SystemVerilog language. The current version is IEEE standard 1800-2017.

In computer engineering, a hardware description language (HDL) is a specialized computer language used to describe the structure and behavior of electronic circuits, and most commonly, digital logic circuits.

In computer science, type safety is the extent to which a programming language discourages or prevents type errors. A type error is erroneous or undesirable program behaviour caused by a discrepancy between differing data types for the program's constants, variables, and methods (functions), e.g., treating an integer (int) as a floating-point number (float). Type safety is sometimes alternatively considered to be a property of a computer program rather than the language in which that program is written; that is, some languages have type-safe facilities that can be circumvented by programmers who adopt practices that exhibit poor type safety. The formal type-theoretic definition of type safety is considerably stronger than what is understood by most programmers.

In computer science, a deterministic algorithm is an algorithm that, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. Deterministic algorithms are by far the most studied and familiar kind of algorithm, as well as one of the most practical, since they can be run on real machines efficiently.

A synchronous programming language is a computer programming language optimized for programming reactive systems. Computer systems can be sorted in three main classes: (1) transformational systems that take some inputs, process them, deliver their outputs, and terminate their execution; a typical example is a compiler; (2) interactive systems that interact continuously with their environment, at their own speed; a typical example is the web; and (3) reactive systems that interact continuously with their environment, at a speed imposed by the environment; a typical example is the automatic flight control system of modern airplanes. Reactive systems must therefore react to stimuli from the environment within strict time bounds. For this reason they are often also called real-time systems, and are found often in embedded systems.

Lustre is a formally defined, declarative, and synchronous dataflow programming language for programming reactive systems. It began as a research project in the early 1980s. A formal presentation of the language can be found in the 1991 Proceedings of the IEEE. In 1993 it progressed to practical, industrial use in a commercial product as the core language of the industrial environment SCADE, developed by Esterel Technologies. It is now used for critical control software in aircraft, helicopters, and nuclear power plants.

Matthias Felleisen

Matthias Felleisen is a German-American computer science professor and author. He grew up in Germany and immigrated to the US when he was 21 years old. He received his PhD from Indiana University under the direction of Daniel P. Friedman.

Lola is designed to be a simple hardware description language for describing synchronous, digital circuits. Niklaus Wirth developed the language to teach digital design on field-programmable gate arrays (FPGAs) to computer science students while a professor at ETH Zurich.

Gérard Berry

Gérard Philippe Berry is a French computer scientist, member of the French Academy of Sciences, French Academy of Technologies, and Academia Europaea. He was the Chief Scientist Officer of Esterel Technologies from 2000 to 2009. He held the 2007-2008 yearly Liliane Bettencourt chair of Technological Innovation at the Collège de France. He is currently Director of Research at INRIA and is holding the 2009-2010 yearly Informatics and Digital Sciences chair at the Collège de France. Berry's work, which spans over more than 30 years, brought important contributions to three main fields:

Esterel Technologies

Esterel Technologies is a supplier of model-based design, validation, and code generation tools for safety-critical software and hardware applications. Esterel’s tools create formal specifications that produce control designs code in software and/or hardware.

FAUST is a domain-specific purely functional programming language for implementing signal processing algorithms in the form of libraries, audio plug-ins, or standalone applications. A FAUST program denotes a signal processor: a mathematical function that is applied to some input signal and then fed out.

Verilog-AMS is a derivative of the Verilog hardware description language that includes analog and mixed-signal extensions (AMS) in order to define the behavior of analog and mixed-signal systems. It extends the event-based simulator loops of Verilog/SystemVerilog/VHDL, by a continuous-time simulator, which solves the differential equations in analog-domain. Both domains are coupled: analog events can trigger digital actions and vice versa.

In computing, reactive programming is a declarative programming paradigm concerned with data streams and the propagation of change. With this paradigm, it's possible to express static or dynamic data streams with ease, and also communicate that an inferred dependency within the associated execution model exists, which facilitates the automatic propagation of the changed data flow.

Sawzall is a procedural domain-specific programming language, used by Google to process large numbers of individual log records. Sawzall was first described in 2003, and the szl runtime was open-sourced in August 2010. However, since the MapReduce table aggregators have not been released, the open-sourced runtime is not useful for large-scale data analysis of multiple log files off the shelf. Sawzall has been replaced by Lingo for most purposes within Google.

Reo Coordination Language

Reo is a domain-specific language for programming and analyzing coordination protocols that compose individual processes into full systems, broadly construed. Examples of classes of systems that can be composed with Reo include component-based systems, service-oriented systems, multithreading systems, biological systems, and cryptographic protocols. Reo has a graphical syntax in which every Reo program, called a connector or circuit, is a labeled directed hypergraph. Such a graph represents the data-flow among the processes in the system. Reo has formal semantics, which stand at the basis of its various formal verification techniques and compilation tools.

TNSDL stands for TeleNokia Specification and Description Language. TNSDL is based on the ITU-T SDL-88 language. It is used exclusively at Nokia Networks, primarily for developing applications for telephone exchanges.

SIGNAL is a programming language based on synchronized data-flow : a process is a set of equations on elementary flows describing both data and control.

Join-patterns provides a way to write concurrent, parallel and distributed computer programs by message passing. Compared to the use of threads and locks, this is a high level programming model using communication constructs model to abstract the complexity of concurrent environment and to allow scalability. Its focus is on the execution of a chord between messages atomically consumed from a group of channels.

References

  1. Berry, Gérard (1999). "The Constructive Semantics of Pure Esterel". CiteSeerX   10.1.1.46.2076 .Cite journal requires |journal= (help)
  2. Berry, Gérard (June 2000). "The Esterel v5 Language Primer". Ecole des Mines and INRIA. CiteSeerX   10.1.1.3.1177 .Cite journal requires |journal= (help)
  3. Berry, Gérard; Gonthier, Georges (November 1992). "The Esterel synchronous programming language: Design, semantics, implementation". Science of Computer Programming. 19 (2): 87–152. CiteSeerX   10.1.1.17.5606 . doi:10.1016/0167-6423(92)90005-V.