Compositional message sequence charts

A message sequence chart (MSC) is a standard notation for describing the interaction between communicating objects. It is popular among the designers of communication protocols. MSCs enjoy both a visual and a textual representation. High-level MSCs (HMSCs) allow specifying infinite scenarios and different choices. Specifically, an HMSC consists of a graph, where each node is a finite MSC with matched send and receive events, and vice versa. In this paper we demonstrate a weakness of HMSCs, which disallows one to model certain interactions. We will show, by means of an example, that some simple finite state communication protocol cannot be represented using HMSCs. We then propose an extension to the MSC standard which allows HMSC nodes to include unmatched messages. The corresponding graph notation will be called HCMSC, which stands for high-level Compositional message sequence charts. With the extended framework, we provide an algorithm for automatically constructing an MSC representation for finite state asynchronous message passing protocols.     

Modeling and verification of a telecommunication application using live sequence charts and the Play-Engine tool

We apply the scenario-based approach to modeling, via the language of live sequence charts (LSCs) and the Play-Engine tool to a real-world complex telecommunication service, . It allows a user to call for help from a doctor, the fire brigade, a car maintenance service, etc. These kinds of services are built on top of an embedded platform, using both new and existing service components, and their complexity stems from their distributed architecture, the various time constraints they entail, and their rapidly evolving underlying systems. A well known problem in this class of telecommunication applications is that of feature interaction, whereby a new feature might cause problems in the execution of existing features. Our approach provides a methodology for high-level modeling of telecommunication applications that can help in detecting feature interaction at early development stages. We exhibit the results of applying the methodology to the specification, animation and formal verification of the Depannage service.

Model‐based code generation for HLA federates

This paper addresses the problem of automated code generation for a High Level Architecture compliant federate application given its behavior model. The behavior model is a part of the architectural model of a federation that the federate can participate in. The federate behavior model is based on Live Sequence Charts, adopted as the behavioral specification formalism in the Federation Architecture Metamodel (FAMM). FAMM serves as a formal language for describing federation architectures. An objective is to help the testing of federation architecture by means of its prototype implementation early in the development lifecycle. A further objective is to help developers construct complete federate applications that are well modularized. The approach to achieve these objectives is aspect‐oriented in that the generated code, which handles the federate's interactions with a federation execution, serves as the base code, where the computation logic is to be weaved as an aspect. Copyright © 2009 John Wiley & Sons, Ltd.     

Optimising code generation with haggies

This article describes haggies, a program for the generation of optimised programs for the efficient numerical evaluation of mathematical expressions. It uses a multivariate Horner-scheme and Common Subexpression Elimination to reduce the overall number of operations.The package can serve as a back-end for virtually any general purpose computer algebra program. Built-in type inference that allows to deal with non-standard data types in strongly typed languages and a very flexible, pattern-based output specification ensure that haggies can produce code for a large variety of programming languages.We currently use haggies as part of an automated package for the calculation of one-loop scattering amplitudes in quantum field theories. The examples in this articles, however, demonstrate that its use is not restricted to the field of high energy physics.

Program summary

Program title: haggiesCatalogue identifier: AEGF_v1_0Program summary: URL: http://cpc.cs.qub.ac.uk/summaries/AEGF_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: GNU GPL v3No. of lines in distributed program, including test data, etc.: 56 220No. of bytes in distributed program, including test data, etc.: 579 010Distribution format: tar.gzProgramming language: Java, JavaCCComputer: Any system that runs the Java Virtual MachineOperating system: Any system that runs the Java Virtual MachineRAM: Determined by the size of the problemClassification: 4.14, 5, 6.2, 6.5, 11.1Nature of problem: Generation of optimised programs for the evaluation of possibly large algebraic expressionsSolution method: Java implementationRunning time: Determined by the size of the problem     

The design and implementation of a code generation tool

A practical approach to the development of a high-quality, re-usable code generator is described in this paper. This code generator produces code for the Prime 64V mode architecture, but the methodology used is generally applicable to the construction of compilers for most architectures. The code generator accepts a tree-structured intermediate form, linearized and represented as a file of integers. This intermediate form uses high-level operators, minimizing work by compiler front-ends that use it and providing a number of advantages in the code generation process. The output of the code generator is assembly language. This tool was found to considerably extend the capabilities of students in a graduate compiler class and has been used in the construction of Pascal and C compilers.     

Separating sequence overlap for automated test sequence generation

Finite state machines have been used to model a number of classes of system and there has thus been much interest in the automatic generation of test sequences from finite state machines. Many finite state machine based test techniques utilize sequences that check the final states of transitions, the most general such sequence being a separating sequence: an input sequence that distinguishes between two states of an FSM. When using such techniques the test sequence length can be reduced by utilizing overlap. This paper investigates overlap for separating sequences and shows how this can be incorporated into test sequence generation.     

Assert and negate revisited: Modal semantics for UML sequence diagrams

Live Sequence Charts (LSC) extend Message Sequence Charts (MSC), mainly by distinguishing possible from necessary behavior. They thus enable the specification of rich multi-modal scenario-based properties, such as mandatory, possible and forbidden scenarios. The sequence diagrams of UML 2.0 enrich those of previous versions of UML by two new operators, assert and negate, for specifying required and forbidden behaviors, which appear to have been inspired by LSC. The UML 2.0 semantics of sequence diagrams, however, being based on pairs of valid and invalid sets of traces, is inadequate, and prevents the new operators from being used effectively. We propose an extension of, and a different semantics for this UML language—Modal Sequence Diagrams (MSD)—based on the universal/existential modal semantics of LSC. In particular, in MSD assert and negate are really modalities, not operators. We define MSD as a UML 2.0 profile, thus paving the way to apply formal verification, synthesis, and scenario-based execution techniques from LSC to the mainstream UML standard. Preliminary version appeared in SCESM '06: Proc. of the 2006 Int. workshop on Scenarios and State Machines, Shanghai, China (May 2006) [15]. This research was supported by the Israel Science Foundation (grant No.287/02-1), and by The John von Neumann Minerva Center for the Development of Reactive Systems at the Weizmann Institute of Science.     

Interpretation and code generation based on intermediate languages

The possibility of supporting high level languages through intermediate languages to be used for direct interpretation and as intermediate forms in compilers is investigated. An accomplished project in the construction of an interpreter and a code generator using one common intermediate form is evaluated. The subject is analysed in general, and a proposal for an improved design scheme is given.     

Producing good code for the case statement

After summarizing different ways of generating selection code for the case statement, the execution speed of each type of selection code is described using the RISC machine model. A method for combining the selection code schemes is proposed. The method, part of the PL.8 compiler, is flexible enough to handle case-selector data-types that have a large range of values, such as the character-string or floating-point datatypes, and can be fine-tuned when the probabilities of the case selector taking on particular values are known.     

Decision support for sequence generation in an assembly oriented design environment

Traditionally, defining the sequence of assembly tasks is not completed until after the product design phase, thus, missing a crucial opportunity to realise the benefits of simultaneous consideration. This paper proposes an approach, which realises the benefits of this simultaneous consideration. It has its origins in observations of industrial assembly planning processes and is based upon conventional design processes. Tools and techniques provide support for the necessary assembly sequencing and assembly definition decisions, including assistance to construct the sequence, choose the most appropriate parts and define liaison attributes. A constraint-based approach is used to confirm that the resulting assembly sequence is both feasible and practical and also gives guidance on the quality of the sequence. An industrial case study is presented which illustrates the practical implementation of this methodology.     

Broadcast MSCs

Message sequence charts (MSCs) have proven to be a useful modeling technique especially within the requirements analysis phase of software development. MSCs, however, do not support the concept of broadcast communication, which is frequently used in technical applications. In this paper, we present an extension to MSCs for the modeling of broadcast interaction scenarios. Based on the mathematical framework of timed streams we also introduce a semantics for broadcast MSCs. We thoroughly discuss methodological benefits and semantic properties of this approach, consider alternative solutions, and address its scaleability with respect to complex real-time systems applications.Our research was supported, in part, by the DFG within the priority program SoftSpez (SPP 1064) under project name InTime, and by the California Institute for Telecommunications and Information Technology (CAL-(IT)²).Received October 2002Accepted in revised form November 2003 by M. Broy, G. Lüttgen and M. Mendler     

Automatically propagating changes from reference implementations to code generation templates

ContextCode generators can automatically perform some tedious and error-prone implementation tasks, increasing productivity and quality in the software development process. Most code generators are based on templates, which are fundamentally composed of text expansion statements. To build templates, the code of an existing, tested and validated implementation may serve as reference, in a process known as templatization. With the dynamics of software evolution/maintenance and the need for performing changes in the code generation templates, there is a loss of synchronism between the templates and this reference code. Additional effort is required to keep them synchronized.ObjectiveThis paper proposes automation as a way to reduce the extra effort needed to keep templates and reference code synchronized.MethodA mechanism was developed to semi-automatically detect and propagate changes from reference code to templates, keeping them synchronized with less effort. The mechanism was also submitted to an empirical evaluation to analyze its effects in terms of effort reduction during maintenance/evolution templatization.ResultsIt was observed that the developed mechanism can lead to a 50% reduction in the effort needed to perform maintenance/evolution templatization, when compared to a manual approach. It was also observed that this effect depends on the nature of the evolution/maintenance task, since for one of the tasks there was no observable advantage in using the mechanism. However, further studies are needed to better characterize these tasks.ConclusionAlthough there is still room for improvement, the results indicate that automation can be used to reduce effort and cost in the maintenance and evolution of a template-based code generation infrastructure.     

VPM: A visual,precise and multilevel metamodeling framework for describing mathematical domains and UML (The Mathematics of Metamodeling is Metamodeling Mathematics)

As UML 2.0 is evolving into a family of languages with individually specified semantics, there is an increasing need for automated and provenly correct model transformations that (i) assure the integration of local views (different diagrams) of the system into a consistent global view, and, (ii) provide a well-founded mapping from UML models to different semantic domains (Petri nets, Kripke automaton, process algebras, etc.) for formal analysis purposes as foreseen, for instance, in submissions for the OMG RFP for Schedulability, Performance and Time. However, such transformations into different semantic domains typically require the deep understanding of the underlying mathematics, which hinders the use of formal specification techniques in industrial applications. In the paper, we propose a multilevel metamodeling technique with precise static and dynamic semantics (based on a refinement calculus and graph transformation) where the structure and operational semantics of mathematical models can be defined in a UML notation without cumbersome mathematical formulae.     

Automating the selection of code templates

A new methodology for code generation in compilers is advanced. The underlying principle is a simple one—that machine memory resources must be matched to intermediate code values. It is possible to view the methodology as a generalization of the Graham-Glanville approach, but where there is a wider-ranging search for the best code sequences. This new approach has been implemented for the IBM/370, the VAX-11 and the Intel 8086 instruction sets.     

Code generation for a systolic computer

An experiment of a mechanical code generation for a programmable systolic computer is reported. Two-dimensional systolic arrays are automatically reduced to one dimension, and code is generated for the one-dimensional processor array Warp. The technique is demonstrated with two examples: matrix multiplication and LU decomposition.     

应用UML顺序图的联锁测试用例生成方法

计算机联锁软件是安全完善度等级最高的软件, 因此, 在投入使用前对联锁软件的测试是必不可少的。为生成联锁软件测试用例, 结合包含有充分测试信息的UML模型, 提出一种以UML顺序图为主要模型的软件测试用例生成方法。通过提出有向图SG生成算法, 将顺序图转换为SG; 然后基于特定的覆盖准则和采用深度优先搜索算法遍历SG, 得到场景的输入、预期输出、约束条件以及场景环境, 生成测试用例; 最后, 以进路建立过程为例验证了该方法的可行性和正确性。     

Correction to ‘producing good code for the case statement’

An O(n²) algorithm for splitting a case statement's jump table into the minimum number of subtables (of a given density) is presented. Previously, the problem was thought to be NP-complete.