A systematic review of code generation proposals from state machine specifications

ContextModel Driven Development (MDD) encourages the use of models for developing complex software systems. Following a MDD approach, modelling languages are used to diagrammatically model the structure and behaviour of object-oriented software, among which state-based languages (including UML state machines, finite state machines and Harel statecharts) constitute the most widely used to specify the dynamic behaviour of a system. However, generating code from state machine models as part of the final system constitutes one of the most challenging tasks due to its dynamic nature and because many state machine concepts are not supported by the object-oriented programming languages. Therefore, it is not surprising that such code generation has received great attention over the years.ObjectiveThe overall objective of this paper is to plot the landscape of published proposals in the field of object oriented code generation from state machine specifications, restricting the search neither to a specific context nor to a particular programming language.MethodWe perform a systematic, accurate literature review of published studies focusing on the object oriented implementation of state machine specifications.ResultsThe systematic review is based on a comprehensive set of 53 resources in all, which we have classified into two groups: pattern-based and not pattern-based. For each proposal, we have analysed both the state machine specification elements they support and the means the authors propose for their implementation. Additionally, the review investigates which proposals take into account desirable features to be considered in software development such as maintenance or reusability.ConclusionsOne of the conclusions drawn from the review is that most of the analysed works are based on a software design pattern. Another key finding is that many papers neither support several of the main components of the expressive richness of state machine specifications nor provide an implementation strategy that considers relevant qualitative aspects in software development.     

Towards the uniform implementation of declarative languages

Current implementation techniques for functional languages differ considerably from those for logic languages. This complicates the development of flexible and efficient abstract machines that can be used for the compilation of declarative languages combining concepts of functional and logic programming. We propose an abstract machine, called the JUMP-machine, which systematically integrates the operational concepts needed to implement the functional and logic programming paradigm. The use of a tagless representation for heap objects, which originates from the Spineless Tagless G-machine, supports the integration of different concepts. In this paper, we provide a functional logic kernel language and show how to translate it into the abstract machine language of the JUMP-machine. Furthermore, we define the operational semantics of the machine language formally and discuss the mapping of the abstract machine to concrete machine architectures. We tested the approach by writing a compiler for the functional logic language GTML. The obtained performance results indicate that the proposed method allows to implement functional logic languages efficiently.     

Unification of the models for types, classes and state machines

The static model, specified formally, and the dynamic model, represented by hierarchical state machines, are intimately related. By defining a mapping between the two, we are able to provide a definition of inheritance, multiple inheritance and behavioral subtyping for state machines based on that for formally specified types and classes, and provide a graphical representation for formal specifications in terms of state machines. The state machine notation is based on statecharts. It, however, supports both a declarative style, appropriate for types, and an imperative style, appropriate for classes. State machines may be parameterized and may be viewed from different perspectives, based on an arbitrary choice of state predicates. And states are interpreted not as an expression of concurrency, but result from a choice of independent state predicates.     

Learning new programming languages: an analysis of the process and problems encountered

Abstract

Experienced programmers transferring to a new language have a far easier time than the novice learning a first language. However, they still experience considerable difficulties. The objective in this exploratory study was to characterize the kinds of learning and transfer that take place in the early stages of using a new programming language and where difficulties develop. ‘Think-aloud’ protocols were videotaped as subjects went about trying to write a program in a new programming language. Subjects used One of two unfamiliar languages, one similar to their known language (Pascal) and the other dissimilar. Three types of analyses were done on the recorded protocols: a procedural analysis showing the activities the subjects engaged in as they learned the new language, a programming knowledge analysis showing in which areas of program development difficulties were encountered, and a solutions analysis showing how successful the programmers were at using unique features of the new language. We found that the procedures programmers used to learn a new language were independent of the language being learned. The slight differences that existed in procedures were between levels of expertise. Programmers spent the majority of their time reading a language textbook. The programming knowledge analysis showed that programmers main area of concentration was planning how to implement their approach given the constructs available in the language. We observed many iterations of programmers trying to implement plans, failing and having to revise their plans. Examination of the subjects solutions and implementation approaches in Pascal led us to believe that programmers learning a new language are often biased by their implementation of algorithms in previous languages.     

DFL: A Data Flow Language

Many novel computer architectures like array and multiprocessors which achieve high performance through the use of concurrency exploit variations of the von Neumann model of computation. The effective utilization of the machines makes special demands on programmers and their programming languages, such as the structuring of data into vectors or the partitioning of programs into concurrent processes. In comparison, the data flow model of computation demands only that the principle of structured programming be followed. A data flow program, often represented as a data flow graph, is a program that expresses a computation by indicating the data dependencies among operators. A data flow computer is a machine designed to take advantage of concurrency in data flow graphs by executing data independent operations in parallel. In this paper, we discuss the design of a high level language (DFL: Data Flow Language) suitable for data flow computers. Some sample procedures in DFL are presented. The implementation aspects have not been discussed in detail since there are no new problems encountered. The language DFL embodies the concepts of functional programming, but in appearance closely resembles Pascal. The language is a better vehicle than the data flow graph for expressing a parallel algorithm. The compiler has been implemented on a DEC 1090 system in Pascal.     

A metric towards evaluating understandability of state machines: An empirical study

ContextState machines are widely used to describe the dynamic behavior of objects, components, and systems. As a communication tool between various stakeholders, it is essential that state machines be easily and correctly comprehensible. Poorly understood state machines can lead to misunderstandings and communication overhead, thus adversely affecting the quality of the final product. Nevertheless, there is a lack of measurement research for state machines.ObjectiveIn this paper, we propose a metric, called SUM, to evaluate the understandability of state machines. SUM is defined on the basis of cohesion and coupling concepts.MethodTo validate SUM as a state machine understandability indicator, we performed an empirical study using five systems. We constructed five different state machines for each system, resulting in a total of 25 state machines being prepared. Two aspects of understandability, efficiency (UEff) and correctness (UCor), were obtained from 40 participants for the state machines. We then performed correlation and consistency analyses between the SUMs and the measured understandability values.ResultsThe results of the correlation analysis indicated that SUM was significantly correlated with UEff (p = 0.003) and UCor (p = 0.027). The consistency analysis results indicated that SUM was positively correlated with UEff in four of the systems and UCor in all five systems.ConclusionThese results confirm the possibility that SUM can be a useful understandability indicator for SMs. We believe that the proposed metric can be used as a guideline to construct quality state machines.     

A hybrid class- and prototype-based object model to support language-neutral structural intercession

ContextDynamic languages have turned out to be suitable for developing specific applications where runtime adaptability is an important issue. Although .Net and Java platforms have gradually incorporated features to improve their support of dynamic languages, they do not provide intercession for every object or class. This limitation is mainly caused by the rigid class-based object model these platforms implement, in contrast to the flexible prototype-based model used by most dynamic languages.ObjectiveOur approach is to provide intercession for any object or class by defining a hybrid class- and prototype-based object model that efficiently incorporates structural intercession into the object model implemented by the widespread .Net and Java platforms.MethodIn a previous work, we developed and evaluated an extension of a shared-source implementation of the .Net platform. In this work, we define the formal semantics of the proposed reflective model, and modify the existing implementation to include the hybrid model. Finally, we assess its runtime performance and memory consumption, comparing it to existing approaches.ResultsOur platform shows a competitive runtime performance compared to 9 widespread systems. On average, it performs 73% and 61% better than the second fastest system for short- and long-running applications, respectively. Besides, it is the JIT-compiler approach that consumes less average memory. The proposed approach of including a hybrid object-model into the virtual machine involves a 444% performance improvement (and 65% less memory consumption) compared to the existing alternative of creating an extra software layer (the DLR). When none of the new features are used, our platform requires 12% more execution time and 13% more memory than the original .Net implementation.ConclusionOur proposed hybrid class- and prototype-based object model supports structural intercession for any object or class. It can be included in existing JIT-compiler class-based platforms to support common dynamic languages, providing competitive runtime performance and low memory consumption.     

VCluster: a thread‐based Java middleware for SMP and heterogeneous clusters with thread migration support

Clusters, composed of symmetric multiprocessor (SMP) machines and heterogeneous machines, have become increasingly popular for high‐performance computing. Message‐passing libraries, such as message‐passing interface (MPI) and parallel virtual machine (PVM), are de facto parallel programming libraries for clusters that usually consist of homogeneous and uni‐processor machines. For SMP machines, MPI is combined with multithreading libraries like POSIX Thread and OpenMP to take advantage of the architecture. In addition to existing parallel programming libraries that are in C/C++ and FORTRAN programming languages, the Java programming language presents itself as another alternative with its object‐oriented framework, platform neutral byte code, and ever‐increasing performance. This paper presents a new parallel programming model and a library, VCluster, which implements this model. VCluster is based on migrating virtual threads instead of processes to support clusters of SMP machines more efficiently. The implementation uses thread migration, which can be used in dynamic load balancing. VCluster was developed in pure Java, utilizing the portability of Java to support clusters of heterogeneous machines. Several applications are developed to illustrate the use of this library and compare the usability and performance of VCluster with other approaches. Copyright © 2007 John Wiley & Sons, Ltd.     

An extensive empirical study on C++ concurrency constructs

ContextNowadays concurrent programming is in large demand. The inherent support for concurrency is therefore increasingly important in programming languages. As for C++, an abundance of standard concurrency constructs have been supported since C++11. However, to date there is little work investigating how these constructs are actually used in developing real software.ObjectiveIn this paper, we perform an extensive empirical study to investigate the actual adoption of C++ concurrency constructs in open-source applications, with the goal to provide useful information for language designers and practitioners to improve the design and use of concurrency constructs.MethodWe first conduct a survey to understand the developers’ perception of concurrency constructs. Then, we analyze 492 open-source concurrent applications, comprising 131 million lines of C++ code, to collect the data of the practical adoption of concurrency constructs. Finally, we perform statistical analysis on the collected data and get the quantitative analysis results.ResultsUsing the experimental data, we uncover many interesting findings with respect to the usage of concurrency constructs, the management of synchronization, the relationship between standard concurrency constructs and third-party concurrency constructs, and the difference of applications in using concurrency constructs. For example, we find that: (1) thread-based constructs are significantly more often used to write concurrent programs than atomics-based constructs and task-based constructs; (2) lock-based constructs are significantly more often used to manage synchronization than lock-free constructs and blocking constructs; (3) developers in most projects do not move from third-party concurrency constructs to standard concurrency constructs; and (4) small-size applications introduce concurrency constructs more intensively and more quickly than medium-size applications and large-size applications.ConclusionsThis is the first extensive empirical study on C++ concurrency constructs. The results of this paper should be helpful for designing, teaching, and using C++ concurrency constructs.     

Protocol modelling: A modelling approach that supports reusable behavioural abstractions

We describe a behavioural modelling approach based on the concept of a “Protocol Machine”, a machine whose behaviour is governed by rules that determine whether it accepts or refuses events that are presented to it. We show how these machines can be composed in the manner of mixins to model object behaviour and show how the approach provides a basis for defining reusable fine-grained behavioural abstractions. We suggest that this approach provides better encapsulation of object behaviour than traditional object modelling techniques when modelling transactional business systems. We relate the approach to work going on in model driven approaches, specifically the Model Driven Architecture initiative sponsored by the Object Management Group. Communicated by August-Wilhelm Scheer Ashley McNeile is a practitioner with over 25 years of experience in systems development and IT related management consultancy. His main areas of interest are requirements analysis techniques and model execution and in 2001 he founded Metamaxim Ltd. to pioneer new techniques in these areas. He has published and presented widely on object oriented development methodology and systems architecture. Nicholas Simons has been working with formal methods of system specification since their introduction, and has over 20 years experience in building tools for system design, code generation and reverse engineering. In addition, he lectures on systems analysis and design, Web programming and project planning. He is a co-founder and director of Metamaxim Ltd.     

Comparing techniques for authorship attribution of source code

Attributing authorship of documents with unknown creators has been studied extensively for natural language text such as essays and literature, but less so for non‐natural languages such as computer source code. Previous attempts at attributing authorship of source code can be categorised by two attributes: the software features used for the classification, either strings of n tokens/bytes (n‐grams) or software metrics; and the classification technique that exploits those features, either information retrieval ranking or machine learning. The results of existing studies, however, are not directly comparable as all use different test beds and evaluation methodologies, making it difficult to assess which approach is superior. This paper summarises all previous techniques to source code authorship attribution, implements feature sets that are motivated by the literature, and applies information retrieval ranking methods or machine classifiers for each approach. Importantly, all approaches are tested on identical collections from varying programming languages and author types. Our conclusions are as follows: (i) ranking and machine classifier approaches are around 90% and 85% accurate, respectively, for a one‐in‐10 classification problem; (ii) the byte‐level n‐gram approach is best used with different parameters to those previously published; (iii) neural networks and support vector machines were found to be the most accurate machine classifiers of the eight evaluated; (iv) use of n‐gram features in combination with machine classifiers shows promise, but there are scalability problems that still must be overcome; and (v) approaches based on information retrieval techniques are currently more accurate than approaches based on machine learning. Copyright © 2012 John Wiley & Sons, Ltd.     

Online hierarchical scheduling: An approach using mathematical programming

This paper considers an online hierarchical scheduling problem on parallel identical machines. We are given a set of m machines and a sequence of jobs. Each machine has a different hierarchy, and each job also has a hierarchy associated with it. A job can be assigned to a machine only if its hierarchy is no less than that of the machine. The objective is to minimize the makespan, i.e., the maximum load of all machines. Two models are studied in the paper. For the fractional model, we present an improved algorithm and lower bounds. Both the algorithm and the lower bound are based on solutions of mathematical programming. For any given m, our algorithm is optimal by numerical calculation. For the integral model, we present both a general algorithm for any m, and an improved algorithm with better competitive ratios of 2.333 and 2.610 for m=4 and 5, respectively.     

Minimization of mealy finite-state machines by internal states gluing

A problem of minimization of Mealy finite-state machines that is common in synthesizing digital devices on programmable logic devices is considered. The proposed approach uses an operation of gluing two states and represents the finite-state machine as a list of transitions. Cases when gluing two states generates wait states are described. Algorithms that minimize the number of internal states, the number of transitions and input variables of Mealy finite-state machines are given. The experimental results showed that when used to implement finite-state machines on programmable logic devices, the proposed method helps decrease the implementation cost 1.31 times on average and 3 times at best. Topical directions for further study of finite-state machines minimization methods are given.     

The implementation of concurrency for a PL/I-like language

The formulation of concurrency and synchronization has been recognized as a matter of growing importance in system programming languages in order to achieve well-structured, reliable and easy to understand system software such as operating systems. Unfortunately, only experimental languages, such as Concurrent Pascal or MODULA, contain adequate linguistic constructs for support of such concepts as processes and monitors. The compilers for those languages are available only on a few machines and are devoted primarily to education. In this paper a simple method of extending a PL/I-like programming language by concurrency features is described which is based on the usage of an existing compiler. The method has proven to be a cost effective way of adopting recent research results in existing software engineering tools, thus avoiding the need of switching over to a completely new programming environment.     

On the expressiveness of the approach to constructing PLC-programs by LTL-specification

The article is devoted to an approach to constructing and verification of discrete PLC-programs by LTL-specification. This approach provides a possibility of analysing the correctness of PLCprograms by using the model checking method. The linear temporal logic LTL is used as a language of specification of the program behavior. The correctness analysis of LTL-specification is automatically performed by the symbolic model checking tool Cadence SMV. The article demonstrates the consistency of the approach to constructing and verification of PLC programs by LTL-specification from the point of view of Turing power. It is proved that in accordance with this approach for any Minsky counter machine an LTL-specification can be built, which is used for machine implementation in any PLC programming language of standard IEC 61131-3. Minsky machines are equipollent to Turing machines, and the considered approach also has the Turing power. The proof focuses on representation of a counter machine behavior in the form of a set of LTL-formulas and matching these formulas to constructions of ST and SFC languages. SFC is interesting as a specific graphical language. ST is considered as a basic language because the implementation of a counter machine on IL, FBD/CFC and LD languages is reduced to rewriting blocks of an ST-program. The idea of the proof is demonstrated by an example of a Minsky 3-counter machine, which implements a function of squaring.     

Robustness testing for software components

Component-based development allows one to build software from existing components and promises to improve software reuse and reduce costs. For critical applications, the user of a component must ensure that it fits the requirements of the application. To achieve this, testing is a well-suited means when the source code of the components is not available. Robustness testing is a testing methodology to detect the vulnerabilities of a component under unexpected inputs or in a stressful environment. As components may fail differently in different states, we use a state machine based approach to robustness testing. First, a set of paths is generated to cover transitions of the state machine, and it is used by the test cases to bring the component into a specific control state. Second, method calls with invalid inputs are fed to the component in different states to test the robustness. By traversing the paths, the test cases cover more states and transitions compared to stateless API testing. We apply our approach to several components, including open source software, and compare our results with existing approaches.     

The evolution of stochastic regular motifs for protein sequences

Stochastic regular motifs are evolved for protein sequences using genetic programming. The motif language, SRE-DNA, is a stochastic regular expression language suitable for denoting biosequences. Three restricted versions of SRE-DNA are used as target languages for evolved motifs. The genetic programming experiments are implemented in DCTG-GP, which is a genetic programming system that uses logic-based attribute grammars to define the target language for evolved programs. Earlier preliminary work tested SRE-DNA’s viability as a representation language for aligned protein sequences. This work establishes that SRE-DNA is also suitable for evolving motifs for unaligned sets of sequences. Brian J. Ross, Ph.D.: He is an associate professor of computer science at Brock University, where he has worked since 1992. He obtained his BCSc at the University of Manitoba, Canada, in 1984, his MSc at the University of British Columbia, Canada, in 1988, and his PhD at the University of Edinburgh, Scotland, in 1992. His research interests include evolutionary computation, machine learning, language induction, concurrency, and logic programming.     

Efficient virtual machine support of runtime structural reflection

Increasing trends towards adaptive, distributed, generative and pervasive software have made object-oriented dynamically typed languages become increasingly popular. These languages offer dynamic software evolution by means of reflection, facilitating the development of dynamic systems. Unfortunately, this dynamism commonly imposes a runtime performance penalty. In this paper, we describe how to extend a production JIT-compiler virtual machine to support runtime object-oriented structural reflection offered by many dynamic languages. Our approach improves runtime performance of dynamic languages running on statically typed virtual machines. At the same time, existing statically typed languages are still supported by the virtual machine.We have extended the .Net platform with runtime structural reflection adding prototype-based object-oriented semantics to the statically typed class-based model of .Net, supporting both kinds of programming languages. The assessment of runtime performance and memory consumption has revealed that a direct support of structural reflection in a production JIT-based virtual machine designed for statically typed languages provides a significant performance improvement for dynamically typed languages.