Article

On efficient program synthesis from statecharts

Author:

Andrzej WasowskiAuthors Info & Claims

LCTES '03: Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems

Pages 163 - 170

https://doi.org/10.1145/780732.780755

Published: 11 June 2003 Publication History

Abstract

Program synthesis from hierarchical state diagrams has for long been discussed in various communities. My aim is to provide an efficient, lightweight code generation scheme suitable for resource constrained microcontrollers.I describe an initial implementation of SCOPE---a hierarchical code generator for a variant of the statechart language. I shall discuss several techniques implemented in the tool, namely imposing and exploiting a regular hierarchy structure, labeling schemes for fast ancestor queries, improvements in exiting states, compile-time scope resolution for transitions, and various details of compact runtime representation.The resulting algorithm avoids the exponential code growth exhibited by tools based on flattening of hierarchical state machine. At the same time it demonstrates that it is possible to maintain reasonable speed and size results even for small models, while preserving the hierarchy at runtime. SCOPE currently produces code that is comparable with that of industrial tools (IAR visualSTATE) for small models and clearly wins for bigger ones.

References

[1]

J. Ali and J. Tanaka. Converting statecharts into Java code. In Proceedings of the 5th International Conference on Integrated Design and Process Technology (IDPT'99), Dallas,Texas, June 1999.

[2]

G. Behrmann, K. Kristoffersen, and K. G.Larsen. Code generation for hierarchical systems. In NWPT'99 -- The 11th Nordic Workshop on Programming Theory, Uppsala, Sweden, Sept. 1999.

[3]

D. Bjorklund, J. Lilius, and I. Porres. Towards efficient code synthesis from statecharts. In A. Evans, R. France, and A. M. B. Rumpe, editors, Practical UML-Based Rigorous Development Methods - Countering or Integrating the eXtremists. Workshop of the pUML-Group., Lecture Notes in Informatics P-7, Toronto,Canada, October 1st, 2001. GI.

Digital Library

[4]

D. Drusinsky and D. Harel. On the power of cooperative concurrency. In Proceedings of Concurrency '88, volume 335 of Lecture Notes in Computer Science, pages 74--103, New York, 1985. Springer-Verlag.

[5]

D. Drusinsky and D. Harel. Using statecharts for hardware description and synthesis. IEEE Transactions on Computer Aided Design, 8(7):798--807, 1989.

Digital Library

[6]

D. Drusinsky-Yoresh. A state assignment procedure for single-block implementation of state charts. IEEE Transactions on Computer-Aided Design, 10(12):1569--1576, 1991.

[7]

E. Erpenbach. Compilation, Worst-Case Execution Times and Schedulability Analysis of Statecharts Models. PhD thesis, Department of Mathematics and Computer Science of the University of Paderborn, Apr. 2000.

[8]

D. Harel. Statecharts: A visual formalism for complex systems. Science of Computer Programming, 8:231--274, 1987.

Digital Library

[9]

IAR Inc. IAR visualSTATE™ http://www.iar.com/Products/VS/.

[10]

International standard. Programming Languages - C. Ref. ISO/IEC 9899:1999(E).

[11]

A. Knapp and S. Merz. Model checking and code generation for UML state machines and collaborations. In D. Haneberg, G. Schellhorn, and W. Reif, editors, Proceedings of 5th Workshop on Tools for System Design and Verification, Technical Report 2002-11, pages 59--64. Institut fur Informatik, Universitat Augsburg, 2002.

Digital Library

[12]

S. Ramesh. Efficient translation of statecharts into hardware circuits. In 12th International Conference on VLSI Design, pages 384--389. IEEE Computer Society Press, Jan. 1999.

Digital Library

[13]

SCOPE: A statechart compiler. http://www.mini.pw.edu.pl/~wasowski/scope.

[14]

E. Sekerinski and R. Zurob. iState: A statechart translator. In M. Gogolla and C. Kobryn, editors, UML 2001 - The Unified Modeling Language, Toronto, Canada, October 2001, volume 2185 of Lecture Notes in Computer Science, pages 376--390. Springer-Verlag, 2001.

Digital Library

[15]

A. Wasowski and P. Sestoft. Compile-time scope resolution for statecharts transitions. In Proceedings of Workshop on Critical Systems Development with UML (CSDUML), Dresden, Germany, Sept. 2002. TR of Munich University of Technology.

[16]

A. Wasowski and P. Sestoft. On the formal semantics of visualSTATE statecharts. Technical Report TR-2002-19, IT University of Copenhagen, Sept. 2002.

[17]

A. Zundorf. Rigorous object oriented software development with Fujaba. Unpublished Draft, 2000.

Cited By

Han GDi Natale MZeng HLiu XDou W(2013)Optimizing the implementation of real-time Simulink models onto distributed automotive architecturesJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2013.08.00959:10(1115-1127)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.1016/j.sysarc.2013.08.009
Charfi AMraidha CBoulet P(2012)An Optimized Compilation of UML State MachinesProceedings of the 2012 IEEE 15th International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing10.1109/ISORC.2012.30(172-179)Online publication date: 11-Apr-2012
https://dl.acm.org/doi/10.1109/ISORC.2012.30
Al Dallal JSaleh K(2012)Synthesizing Distributed Protocol Specifications from a UML State Machine Modeled Service SpecificationJournal of Computer Science and Technology10.1007/s11390-012-1293-127:6(1150-1168)Online publication date: 15-Nov-2012
https://doi.org/10.1007/s11390-012-1293-1
Show More Cited By

Index Terms

On efficient program synthesis from statecharts
1. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Software system models
        State systems

Recommendations

On efficient program synthesis from statecharts
Special Issue: Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool support for embedded systems (San Diego, CA).

Program synthesis from hierarchical state diagrams has for long been discussed in various communities. My aim is to provide an efficient, lightweight code generation scheme suitable for resource constrained microcontrollers.I describe an initial ...
Flattening statecharts without explosions
LCTES '04: Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems

We present a polynomial upper bound for flattening of UML statecharts. An efficient flattening technique is derived and implemented in SCOPE---a code generator targeting constrained embedded systems. Programs generated with this new technique are both ...
Flattening statecharts without explosions
LCTES '04

We present a polynomial upper bound for flattening of UML statecharts. An efficient flattening technique is derived and implemented in SCOPE---a code generator targeting constrained embedded systems. Programs generated with this new technique are both ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

LCTES '03: Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems

June 2003

304 pages

ISBN:1581136471

DOI:10.1145/780732

General Chair:
Frank Mueller
North Carolina State University
,
Publications Chair:
Uli Kremer
Rutgers University

ACM SIGPLAN Notices Volume 38, Issue 7
Special Issue: Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool support for embedded systems (San Diego, CA).
July 2003
293 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/780731
Issue’s Table of Contents

Copyright © 2003 ACM.

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 ACM 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

LCTES03

Sponsor:

LCTES03: ACM SIGPLAN Symposium on Languages, Compilers, and Tools for Embedded Systems

June 11 - 13, 2003

California, San Diego, USA

Acceptance Rates

LCTES '03 Paper Acceptance Rate 29 of 128 submissions, 23%;

Overall Acceptance Rate 116 of 438 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
737
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Han GDi Natale MZeng HLiu XDou W(2013)Optimizing the implementation of real-time Simulink models onto distributed automotive architecturesJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2013.08.00959:10(1115-1127)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.1016/j.sysarc.2013.08.009
Charfi AMraidha CBoulet P(2012)An Optimized Compilation of UML State MachinesProceedings of the 2012 IEEE 15th International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing10.1109/ISORC.2012.30(172-179)Online publication date: 11-Apr-2012
https://dl.acm.org/doi/10.1109/ISORC.2012.30
Al Dallal JSaleh K(2012)Synthesizing Distributed Protocol Specifications from a UML State Machine Modeled Service SpecificationJournal of Computer Science and Technology10.1007/s11390-012-1293-127:6(1150-1168)Online publication date: 15-Nov-2012
https://doi.org/10.1007/s11390-012-1293-1
Prout AAtlee JDay NShaker P(2012)Code generation for a family of executable modelling notationsSoftware and Systems Modeling (SoSyM)10.1007/s10270-010-0176-611:2(251-272)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1007/s10270-010-0176-6
Traulsen CAmende Tvon Hanxleden R(2011)Compiling SyncCharts to Synchronous C2011 Design, Automation & Test in Europe10.1109/DATE.2011.5763284(1-4)Online publication date: Mar-2011
https://doi.org/10.1109/DATE.2011.5763284
von Hanxleden RChakraborty SHalbwachs N(2009)SyncCharts in CProceedings of the seventh ACM international conference on Embedded software10.1145/1629335.1629366(225-234)Online publication date: 12-Oct-2009
https://dl.acm.org/doi/10.1145/1629335.1629366
Guo LRoychoudhury A(2008)Debugging Statecharts Via Model-Code TraceabilityLeveraging Applications of Formal Methods, Verification and Validation10.1007/978-3-540-88479-8_21(292-306)Online publication date: 2008
https://doi.org/10.1007/978-3-540-88479-8_21
Wasowski A(2004)Flattening statecharts without explosionsACM SIGPLAN Notices10.1145/998300.99720039:7(257-266)Online publication date: 11-Jun-2004
https://dl.acm.org/doi/10.1145/998300.997200
Wasowski AWhalley DCytron R(2004)Flattening statecharts without explosionsProceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems10.1145/997163.997200(257-266)Online publication date: 11-Jun-2004
https://dl.acm.org/doi/10.1145/997163.997200
Glesner SBlech J(2004)Coalgebraic semantics for component systemsProceedings of the 2004 international conference on Architecting Systems with Trustworthy Components10.1007/11786160_14(245-261)Online publication date: 12-Dec-2004
https://dl.acm.org/doi/10.1007/11786160_14
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents