[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

SCEst: Sequentially Constructive Esterel

Published: 07 December 2017 Publication History

Abstract

The synchronous language Esterel provides determinate concurrency for reactive systems. Determinacy is ensured by the signal coherence rule, which demands that signals have a stable value throughout one reaction cycle. This is natural for the original application domains of Esterel, such as controller design and hardware development; however, it is unnecessarily restrictive for software development. Sequentially Constructive Esterel (SCEst) overcomes this restriction by allowing values to change instantaneously, as long as determinacy is still guaranteed, adopting the recently proposed Sequentially Constructive model of computation. SCEst is grounded in the minimal Sequentially Constructive Language (scl), which also provides a novel semantic definition and compilation approach for Esterel.

References

[1]
Joaquín Aguado, Michael Mendler, Reinhard von Hanxleden, and Insa Fuhrmann. 2014. Grounding synchronous deterministic concurrency in sequential programming. In Proceedings of the 23rd European Symposium on Programming (ESOP’14), LNCS 8410. Springer.
[2]
Sidharta Andalam, Partha Roop, Alain Girault, and Claus Traulsen. 2009. PRET-C: A new language for programming precision timed architectures. In Proceedings of the Workshop on Reconciling Performance with Predictability (RePP’09), Embedded Systems Week.
[3]
Charles André. 2003. Semantics of SyncCharts. Technical Report ISRN I3S/RR--2003--24--FR. I3S Laboratory, Sophia-Antipolis, France.
[4]
Andrew W. Appel. 1998. SSA is functional programming. SIGPLAN Not. 33, 4 (April 1998), 17--20.
[5]
Albert Benveniste, Paul Caspi, Stephen A. Edwards, Nicolas Halbwachs, Paul Le Guernic, and Robert de Simone. 2003. The synchronous languages twelve years later. In Proc. IEEE (Special Issue on Embedded Systems), 91, 64--83.
[6]
Gérard Berry. 2000. The foundations of Esterel. In Proof, Language, and Interaction: Essays in Honour of Robin Milner, Gordon Plotkin, Colin Stirling, and Mads Tofte (Eds.). MIT Press, Cambridge, MA, 425--454.
[7]
Frédéric Boussinot. 2006. FairThreads: Mixing cooperative and preemptive threads in C. Concurr. Comput.: Pract. Exper. 18, 5 (April 2006), 445--469.
[8]
Paul Caspi, Jean-Louis Colaço, Léonard Gérard, Marc Pouzet, and Pascal Raymond. 2009. Synchronous objects with scheduling policies: Introducing Safe Shared Memory in Lustre. In Proceedings of the ACM International Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES’09). ACM, 11--20.
[9]
Jean-Louis Colaço, Grégoire Hamon, and Marc Pouzet. 2006. Mixing signals and modes in synchronous data-flow systems. In Proceedings of the ACM International Conference on Embedded Software (EMSOFT’06). ACM, 73--82.
[10]
Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. 1991. Efficiently computing static single assignment form and the control dependence graph. ACM Trans. Program. Lang. Syst. 13, 4 (October 1991), 451--490.
[11]
Stephen A. Edwards. 2003. Tutorial: Compiling concurrent languages for sequential processors. ACM Trans. Design Automat. Electron. Syst. 8, 2 (April 2003), 141--187.
[12]
M. Fuchs and M. Mendler. 1995. A functional semantics for delta-delay VHDL based on FOCUS. In Formal Semantics for VHDL, C. D. Kloos and P. Breuer (Eds.). Kluwer, 9--42.
[13]
Insa Fuhrmann, David Broman, Steven Smyth, and Reinhard von Hanxleden. 2014. Towards Interactive Timing Analysis for Designing Reactive Systems. In Proceedings of the Conference on Reconciling Performance and Predictability (RePP’14).
[14]
Alain Girault. 2005. A survey of automatic distribution method for synchronous programs. In Proceedings of the International Workshop on Synchronous Languages, Applications and Programs (SLAP’05) (Electronic Notes in Theoretical Computer Science), F. Maraninchi, M. Pouzet, and V. Roy (Eds.). Elsevier Science, Edinburgh, UK.
[15]
C. A. R. Hoare. 1985. Communicating Sequential Processes. Prentice Hall, Upper Saddle River, NJ.
[16]
Luciano Lavagno and Ellen Sentovich. 1999. ECL: A specification environment for system-level design. In Proceedings of the 36th ACM/IEEE Conference on Design Automation (DAC’99). ACM, 511--516.
[17]
Edward A. Lee. 2006. The problem with threads. IEEE Comput. 39, 5 (2006), 33--42.
[18]
Dumitru Potop-Butucaru, Stephen A. Edwards, and Gérard Berry. 2007. Compiling Esterel. Springer.
[19]
Karsten Rathlev. 2015. From Esterel to SCL. Master thesis. Kiel University, Department of Computer Science. Retrieved from http://rtsys.informatik.uni-kiel.de/ biblio/downloads/theses/krat-mt.pdf.
[20]
Karsten Rathlev, Steven Smyth, Christian Motika, Reinhard von Hanxleden, and Michael Mendler. 2015. SCEst: Sequentially constructive Esterel. In Proceedings of the 13th ACM-IEEE International Conference on Formal Methods and Models for System Design (MEMOCODE’15).
[21]
K. Schneider. 2001. Embedding imperative synchronous languages in interactive theorem provers. In Conference on Application of Concurrency to System Design (ACSD’01). IEEE Computer Society, 143--156.
[22]
P. Sewell, S. Sarkar, S. Owens, F. Zappa Nardelli, and M. O. Myreen. 2010. x86-TSO: A rigorous and usable programmers model for x86 multiprocessors. Commun. ACM (2010), 89--97.
[23]
Steven Smyth, Christian Motika, and Reinhard von Hanxleden. 2015. A data-flow approach for compiling the sequentially constructive language (SCL). In Proceedings of the 18th Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS’15).
[24]
J.-P. Talpin, J. Brandt, M. Gemünde, K. Schneider, and S. K. Shukla. 2014. Constructive polychronous systems. Sci. Comput. Program. 96, 3 (Dec. 2014), 377--394.
[25]
Olivier Tardieu. 2004. Goto and concurrency—Introducing safe jumps in Esterel. In Proceedings of Synchronous Languages, Applications, and Programming (SLAP’04).
[26]
Olivier Tardieu and Stephen A. Edwards. 2006. Scheduling-independent threads and exceptions in SHIM. In Proceedings of the International Conference on Embedded Software (EMSOFT’06). ACM. 142--151.
[27]
Olivier Tardieu and Stephen A. Edwards. 2007. Instantaneous transitions in Esterel. In Proceedings of the Conference on Model Driven High-Level Programming of Embedded Systems (SLA++P’07).
[28]
Reinhard von Hanxleden. 2009. SyncCharts in C—A proposal for light-weight, deterministic concurrency. In Proceedings of the International Conference on Embedded Software (EMSOFT’09). ACM. 225--234.
[29]
Reinhard von Hanxleden, Björn Duderstadt, Christian Motika, Steven Smyth, Michael Mendler, Joaquín Aguado, Stephen Mercer, and Owen O’Brien. 2014a. SCCharts: Sequentially constructive statecharts for safety-critical applications. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI’14). ACM.
[30]
Reinhard von Hanxleden, Michael Mendler, Joaquín Aguado, Björn Duderstadt, Insa Fuhrmann, Christian Motika, Stephen Mercer, Owen O’Brien, and Partha Roop. 2014b. Sequentially constructive concurrency—A Conservative extension of the synchronous model of computation. ACM Trans. Embed. Comput. Syst. (Special Issue on Applications of Concurrency to System Design) 13, 4s (July 2014), 144:1--144:26.
[31]
Eugene Yip, Partha S. Roop, Morteza Biglari-Abhari, and Alain Girault. 2013. Programming and timing analysis of parallel programs on multicores. In Proceedings of the 13th International Conference on Application of Concurrency to System Design (ACSD’13). 160--169.
[32]
Fang Yu, Shun-Ching Yang, Farn Wang, Guan-Cheng Chen, and Che-Chang Chan. 2012. Symbolic consistency checking of OpenMP parallel programs. In Proceedings of the 13th ACM International Conference on Languages, Compilers, Tools and Theory for Embedded Systems (LCTES’12). ACM, 139--148.

Cited By

View all
  • (2023)Synchronous Deterministic Parallel Programming for Multi-Cores with ForeCACM Transactions on Programming Languages and Systems10.1145/359159445:2(1-74)Online publication date: 26-Jun-2023
  • (2020)From Lustre to Graphical Models and SCCharts2020 Forum for Specification and Design Languages (FDL)10.1109/FDL50818.2020.9232944(1-8)Online publication date: 15-Sep-2020

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems
ACM Transactions on Embedded Computing Systems  Volume 17, Issue 2
Special Issue on MEMCODE 2015 and Regular Papers (Diamonds)
March 2018
640 pages
ISSN:1539-9087
EISSN:1558-3465
DOI:10.1145/3160927
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

Publication History

Published: 07 December 2017
Accepted: 01 March 2017
Revised: 01 September 2016
Received: 01 January 2016
Published in TECS Volume 17, Issue 2

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Synchronous languages
  2. esterel
  3. sequential constructiveness

Qualifiers

  • Research-article
  • Research
  • Refereed

Funding Sources

  • German Science Foundation
  • PRETSY project

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)7
  • Downloads (Last 6 weeks)1
Reflects downloads up to 12 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2023)Synchronous Deterministic Parallel Programming for Multi-Cores with ForeCACM Transactions on Programming Languages and Systems10.1145/359159445:2(1-74)Online publication date: 26-Jun-2023
  • (2020)From Lustre to Graphical Models and SCCharts2020 Forum for Specification and Design Languages (FDL)10.1109/FDL50818.2020.9232944(1-8)Online publication date: 15-Sep-2020

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media