Statecharts in the making: a personal account

ABSTRACT

This paper is a highly personal and subjective account of how the language of statecharts came into being. The main novelty of the language is in being a fully executable visual formalism intended for capturing the behavior of complex real-world systems, and an interesting aspect of its history is that it illustrates the advantages of theoreticians venturing out into the trenches of the real world, "dirtying their hands" and working closely with the system's engineers. The story is told in a way that puts statecharts into perspective and discusses the role of the language in the emergence of broader concepts, such as visual formalisms in general, reactive systems, model-driven development, model executability and code generation.

REFERENCES

• 1: {BHM04} D. Barak, D. Harel and R. Marelly, "InterPlay: Horizontal Scale-Up and Transition to Design in Scenario-Based Programming", Lectures on Concurrency and Petri Nets (J. Desel, W. Reisig and G. Rozenberg, eds.), Lecture Notes in Computer Science, Vol. 3098, Springer-Verlag, 2004, pp. 66--86.
• 2: {B+03} A. Benveniste, P. Caspi, S. A. Edwards, N. Halbwachs, P. Le Guernic and R. de Simone, "The Synchronous Languages Twelve Years Later", Proc. of the IEEE <b>91</b> (2003), 64--83.
• 3: {BG90} A. Benveniste and P. Le Guernic, "Hybrid Dynamical Systems Theory and the Signal Language", IEEE Trans. on Automatic Control, AC-<b>35</b> (1990), 535--546.
• 4: Gérard Berry , Georges Gonthier, The ESTEREL synchronous programming language: design, semantics, implementation, Science of Computer Programming, v.19 n.2, p.87-152, Nov. 1992 [doi>10.1016/0167-6423(92)90005-V ]
• 5: Grady Booch, Object-oriented analysis and design with applications (2nd ed.), Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1993
• 6: Frederick P. Brooks, Jr., No Silver Bullet Essence and Accidents of Software Engineering, Computer, v.20 n.4, p.10-19, April 1987 [doi>10.1109/MC.1987.1663532]
• 7: P. Caspi , D. Pilaud , N. Halbwachs , J. A. Plaice, LUSTRE: a declarative language for real-time programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.178-188, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41641]
• 8: Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
• 9: Werner Damm , David Harel, LSCs: Breathing Life into Message Sequence Charts, Formal Methods in System Design, v.19 n.1, p.45-80, July 2001 [doi>10.1023/A:1011227529550 ]
• 10: Doron Drusinsky , David Harel, On the power of cooperative concurrency, International Conference on Concurrency on Concurrency 88, p.74-103, October 1988, Hamburg, Germany
• 11: Doron Drusinsky , David Harel, On the power of bounded concurrency I: finite automata, Journal of the ACM (JACM), v.41 n.3, p.517-539, May 1994 [doi>10.1145/176584.176587]
• 12: {EHC03} S. Efroni, D. Harel and I. R. Cohen, "Towards Rigorous Comprehension of Biological Complexity: Modeling, Execution and Visualization of Thymic T Cell Maturation", Genome Research <b>13</b> (2003), 2485--2497.
• 13: Sol Efroni , David Harel , Irun R. Cohen, Reactive Animation: Realistic Modeling of Complex Dynamic Systems, Computer, v.38 n.1, p.38-47, January 2005 [doi>10.1109/MC.2005.31]
• 14: {EHC07} S. Efroni, D. Harel and I. R. Cohen, "Emergent Dynamics of Thymocyte Development and Lineage Determination", PLOS Computational Biology <b>3:</b>1 (2007), 127--136.
• 15: {HZ76} M. Hamilton and S. Zeldin, "Higher Order Software: A Methodology for Defining Software", IEEE Transactions on Software Engineering <b>SE-2</b>:1 (1976), 9--36.
• 16: David Harel, And/Or Programs: A New Approach to Structured Programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.1, p.1-17, Jan. 1980 [doi>10.1145/357084.357085]
• 17: {H84&87} D. Harel, "Statecharts: A Visual Formalism for Complex Systems", Science of Computer Programming <b>8</b> (1987), 231--274. (Preliminary version: Technical Report CS84--05, The Weizmann Institute of Science, Rehovot, Israel, February 1984.)
• 18: David Harel, On visual formalisms, Communications of the ACM, v.31 n.5, p.514-530, May 1988 [doi>10.1145/42411.42414]
• 19: David Harel, Biting the Silver Bullet: Toward a Brighter Future for System Development, Computer, v.25 n.1, p.8-20, January 1992 [doi>10.1109/2.161283 ]
• 20: David Harel , Eran Gery, Executable object modeling with statecharts, Proceedings of the 18th international conference on Software engineering, p.246-257, March 25-29, 1996, Berlin, Germany
• 21: David Harel , Chaim-arie Kahana, On statecharts with overlapping, ACM Transactions on Software Engineering and Methodology (TOSEM), v.1 n.4, p.399-421, Oct. 1992 [doi>10.1145/136586.136589]
• 22: {HK04} D. Harel and H. Kugler, "The Rhapsody Semantics of Statecharts (or, On the Executable Core of the UML)", Integration of Software Specification Techniques for Applications in Engineering, (H. Ehrig et al., eds.), Lecture Notes in Computer Science, Vol. 3147, Springer-Verlag, 2004, pp. 325--354.
• 23: David Harel , Orna Kupferman , Moshe Y. Vardi, On the complexity of verifying concurrent transition systems, Information and Computation, v.173 n.2, p.143-161, March 15, 2002 [doi>10.1006/inco.2001.2920 ]
• 24: D. Harel , H. Lachover , A. Naamad , A. Pnueli , M. Politi , R. Sherman , a. Shtul-Trauring, Statemate: a working environment for the development of complex reactive systems, Proceedings of the 10th international conference on Software engineering, p.396-406, April 11-15, 1988, Singapore
• 25: David Harel , Rami Marelly, Come, Let's Play: Scenario-Based Programming Using LSC's and the Play-Engine, Springer-Verlag New York, Inc., Secaucus, NJ, 2003
• 26: David Harel , Amnon Naamad, The STATEMATE semantics of statecharts, ACM Transactions on Software Engineering and Methodology (TOSEM), v.5 n.4, p.293-333, Oct. 1996 [doi>10.1145/235321.235322]
• 27: D. Harel , A. Pnueli, On the development of reactive systems, Logics and models of concurrent systems, Springer-Verlag New York, Inc., New York, NY, 1989
• 28: {HPSR87} D. Harel, A. Pnueli, J. Schmidt and R. Sherman, "On the Formal Semantics of Statecharts", Proc. 2nd IEEE Symp. on Logic in Computer Science, Ithaca, NY, 1987, pp. 54--64.
• 29: {HP91} D. Harel and M. Politi, The Languages of STATEMATE, Technical Report, I-Logix, Inc., Andover, MA (250 pp.), 1991.
• 30: David Harel , Michal Politi, Modeling Reactive Systems with Statecharts: The Statemate Approach, McGraw-Hill, Inc., New York, NY, 1998
• 31: David Harel , Bernhard Rumpe, Meaningful Modeling: What's the Semantics of "Semantics"?, Computer, v.37 n.10, p.64-72, October 2004 [doi>10.1109/MC.2004.172]
• 32: Derek J. Hatley , Imtiaz A. Pirbhai, Strategies for real-time system specification, Dorset House Publishing Co., Inc., New York, NY, 1987
• 33: {HKSP78} K. L. Heninger, J. W. Kallander, J. E. Shore and D. L. Parnas, "Software Requirements for the A-7E Aircraft", NRL Report 3876, November 1978, 523 pgs.
• 34: John E. Hopcroft , Rajeev Motwani , Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (3rd Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2006
• 35: Cornelis Huizing , Rob Gerth , Willem P. de Roever, Modeling Statecharts Behaviour in a Fully Abstract Way, Proceedings of the 13th Colloquium on Trees in Algebra and Programming, p.271-294, March 21-24, 1988
• 36: {I-L} I-Logix, Inc. Products Web page, http://www.ilogix.com.
• 37: Na'aman Kam , Irun R. Cohen , David Harel, The Immune System as a Reactive System: Modeling T Cell Activation With Statecharts, Proceedings of the IEEE 2001 Symposia on Human Centric Computing Languages and Environments (HCC'01), p.15, September 05-07, 2001
• 38: Nancy G. Leveson , Mats Per Erik Heimdahl , Holly Hildreth , Jon D. Reese, Requirements Specification for Process-Control Systems, IEEE Transactions on Software Engineering, v.20 n.9, p.684-707, September 1994 [doi>10.1109/32.317428 ]
• 39: James Martin , Carma McClure, Diagramming techniques for analysts and programmers, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 40: {MS88} K. Misue and K. Sugiyama, "Compound graphs as abstraction of card systems and their hierarchical drawing," Inform. Processing Soc., Japan, Research Report 88-GC-32-2, 1988, (in Japanese).
• 41: Amir Pnueli , M. Shalev, What is in a Step: On the Semantics of Statecharts, Proceedings of the International Conference on Theoretical Aspects of Computer Software, p.244-264, September 24-27, 1991
• 42: Wolfgang Reisig, Petri nets: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 43: James Rumbaugh , Ivar Jacobson , Grady Booch, The Unified Modeling Language reference manual, Addison-Wesley Longman Ltd., Essex, UK, 1998
• 44: James Rumbaugh , Michael Blaha , William Premerlani , Frederick Eddy , William Lorensen, Object-oriented modeling and design, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• 45: {SeCH06} Y. Setty, I. R. Cohen and D. Harel, in preparation, 2006.
• 46: {SM91} K. Sugiyama and K. Misue, "Visualization of Structural Information: Automatic Drawing of Compound Digraphs", IEEE Trans. Systems, Man and Cybernetics <b>21:</b>4 (1991), 876--892.
• 47: {SwCH06} N. Swerdlin, I. R. Cohen and D. Harel, "Towards an in-silico Lymph Node: A Realistic Approach to Modeling Dynamic Behavior of Lymphocytes", submitted, 2006.
• 48: Bran Selic , Garth Gullekson , Paul T. Ward, Real-time object-oriented modeling, John Wiley & Sons, Inc., New York, NY, 1994
• 49: Michael von der Beeck, A Comparison of Statecharts Variants, Proceedings of the Third International Symposium Organized Jointly with the Working Group Provably Correct Systems on Formal Techniques in Real-Time and Fault-Tolerant Systems, p.128-148, September 19-23, 1994
• 50: Paul T. Ward , Stephen J. Mellor, Structured Development for Real-Time Systems, Yourdon Press, Upper Saddle River, NJ, 1986

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: State diagrams

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Flow charts

  K. Computing Milieux
  K.2 HISTORY OF COMPUTING
      Subjects: Software

General Terms:
Design