1.5 Related Work

This thesis work is done in the MSDL (Modeling, Simulation and Design Lab) of McGill University, headed by Prof. Hans Vangheluwe. It is closely related to other on-going projects in the MSDL:

• AToM$^3$ [1] [2] is a graphical modeling and meta-modeling environment. It is able to meta-model the syntax of many formalisms, as well as generate dedicated visual environments for the model design in those formalisms. The semantics of some of those formalisms, such as PetriNets, is usually modeled with graph grammars. In this way, AToM$^3$ can also be used as a simulation or execution environment, with graph grammars that transform the model from one state to another.

  A DCharts meta-model is built in AToM$^3$, which defines a subset of the DCharts syntax. This meta-model is discussed in later chapters. The semantics of DCharts is implemented in SVM, which can be loaded in AToM$^3$ as a simulation engine. It makes it possible to simulate DCharts models and at the same time highlight the current states and enabled transitions in the AToM$^3$ visual environment.

• PythonDEVS [11] [12] is a virtual-time DEVS simulator implemented by Hans Vangheluwe and Jean-Sébastien Bolduc. It provides a practical basis for DCharts simulation, as DCharts is a modular combination of statecharts and DEVS.

  PythonDEVS is a set of DEVS templates and a DEVS simulator class. Those templates must be extended by the model designers by means of inheritance. SVM takes one step further by accepting a textual language of DCharts model descriptions. The users can easily write model descriptions conforming to a rigorously defined syntax. They may also use the AToM$^3$ environment to graphically model DCharts, and then generate model descriptions by pressing a button.

• Real-time PythonDEVS is the real-time version of PythonDEVS. It is modified by Spencer Borland from non-real-time PythonDEVS.

• Spencer Borland in his Master's thesis [9] describes a way to transform statecharts into DEVS and hence proves that DEVS has at least the same expressive power as statecharts [13]. (Actually, DEVS is even more expressive than statecharts.) This provides another means to simulate DCharts other than simulating them directly in SVM: transform DCharts (which take a similar form as statecharts) into DEVS, and use Real-time PythonDEVS to simulate them.

• Alison Stewart has compared the functionality between Real-time PythonDEVS and SVM, and has built an MP3 player on both of them. In her report, she concludes that though neither of the two is perfect, SVM is much more user-friendly. The report is available on-line [14].

Information about the above projects can be obtained from the MSDL website:

http://msdl.cs.mcgill.ca/

This thesis work is also related to several research projects outside of McGill University.

• David Harel has created the statecharts formalism [4] [5], which has been the basis of DCharts. Many of the DCharts constructs, as they are defined in latter chapters, can be found in statecharts. The semantics of those common constructs is the same in both formalisms.

  DCharts have extended statecharts to make them more rigorous and expressive. The syntax of DCharts is a superset of the statecharts syntax. The semantics of DCharts is a superset of the semantics of David Harel's statecharts. Hence, SVM is also a simulator for statecharts.

• Bernard P. Zeigler has created DEVS [7] [8], a modular and expressive formalism. The idea of blocks and connections between them via ports is reused in DCharts. As a result, DCharts are much more modular than statecharts, which are not modular in their nature. Many other concepts in DEVS are useful for the creation of DCharts. In particular, the select function is invented in DEVS to solve transition conflicts. This idea is absorbed by DCharts, though they support a different mechanism based on transition priorities to solve those conflicts.

• Ptolemy II [15] [16] [17] is a heterogeneous modeling and simulation environment implemented by Prof. Edward A. Lee and his students at EECS, University of California at Berkeley. Its viewpoint of directors and actors in component-based models and its Java code generation have important impact on the design of DCharts and such tools as SVM and SCC.

  Unlike SVM, a dedicated simulator for DCharts, Ptolemy II is a modeling and simulation environment for multiple formalisms. Different formalisms may be used to model components (or actors) in a single model. Directors manage the interaction between those components. Discrete-time components and continuous-time components are allowed to coexist and communicate in a single system in this framework.

• The Parallel and Distributed Simulation (PADS) lab of Georgia Institute of Technology, headed by Prof. Richard Fujimoto, has implemented PDNS (Parallel and Distributed Network Simulator). It is an advanced distributed simulation environment.

  The research at the PADS lab is more oriented to distributed simulation than system design. Environments for high-performance distributed simulation are being built, which support the testing and analysis of complex and large systems, such as aircrafts and global troop deployment.

  Similar functionality will be supported by the future version of SVM. It will support the distributed timewarp simulation with DCharts.

• The research on model checking is active and advanced in the Model Checking group of Carnegie Mellon University, headed by Prof. Edmund Clarke. In particular, their research on explicit state model checking [18] [19] is interesting and useful.

  As SVM currently has very limited support for model checking, studying the research results of the Model Checking group will be helpful to the future of a model checker for DCharts. The checker will be able to formally prove properties of DCharts models without simulating or executing them in SVM.

• Prof. Joanne M. Atlee, Prof. Nancy A. Day and their WatForm (Waterloo Formal Methods) research group at University of Waterloo are seeking a way to enhance the power of statecharts and to make them more expressive and practitioner-friendly. [20] [21] [22] Their work is closely related to the creation of DCharts.

  In [23], they discussed a parametrized template capable of expressing the semantics of all the statecharts variants. It is meaningful to describe their framework in DCharts. This enables SVM to simulate models of any statecharts variant.

• Prof. Ivan Porres at Software Construction Laboratory of Åbo Akademi University in Finland has developed SMW (System Modeling Workbench), ``a collection of tools to edit, store, analyze and verify models.'' [24] [25] Those tools are reusable and comparable with AToM$^3$.

  SMW with appropriate extension can be used as a visual environment to design DCharts models. With a plugin that invokes SVM, DCharts simulation in SMW is also possible.