Warm fusion in Stratego: A case study in generation of program transformation systems

Stratego is a domain-specific language for the specification of program transformation systems. The design of Stratego is based on the paradigm of rewriting strategies: user-definable programs in a little language of strategy operators determine where and in what order transformation rules are (automatically) applied to a program. The separation of rules and strategies supports modularity of specifications. Stratego also provides generic features for specification of program traversals. In this paper we present a case study of Stratego as applied to a non-trivial problem in program transformation. We demonstrate the use of Stratego in eliminating intermediate data structures from (also known as deforesting) functional programs via the warm fusion algorithm of Launchbury and Sheard. This algorithm has been specified in Stratego and embedded in a fully automatic transformation system for kernel Haskell. The entire system consists of about 2600 lines of specification code, which breaks down into 1850 lines for a general framework for Haskell transformation and 750 lines devoted to a highly modular, easily extensible specification of the warm fusion transformer itself. Its successful design and construction provides further evidence that programs generated from Stratego specifications are suitable for integration into real systems, and that rewriting strategies are a good paradigm for the implementation of such systems. This revised version was published online in June 2006 with corrections to the Cover Date.     

Automatic Generation of Language-based Tools

Many tools can be automatically derived from formal language definitions, such as compilers/interpreters, editors, analyzers, visualizers/animators, etc. Some examples of language-based tools generated automatically by the LISA system are described in the paper. In addition the specification of an algorithm animator and program visualizer, Alma, generated from an extended LISA input-grammar is discussed; LISA principles and code are reused in Alma implementation.     

一个面向对象软件自动测试框架的设计和实现

介绍了一个测试用例驱动的面向对象软件自动化测试框架(简称为TCDA).TCDA使用UML作为形式化的分析和设计规格说明,从UML的体系结构视图中自动获取测试用例,并以XML的形式保存这些测试用例.TCDA可以根据具体编程语言,将测试用例翻译成由一系列源文件组成的测试脚本.测试执行过程中,测试脚本首先会被编译和链接,生成可执行文件,接着这些可执行文件将被运行,同时测试结果将被记录和分析,并最终生成一个结果分析报告.TCDA的原型系统使用Java实现.该系统包括测试配置、测试用例生成、测试脚本生成、测试执行和结果分析五个模块,分别支持以上描述的过程.     

Domain-specific program profiling and its application to attribute grammars and term rewriting

We present a method for profiling programs that are written using domain-specific languages. Instead of reporting execution in terms of implementation details as in most existing profilers, our method operates at the level of the problem domain. Program execution generates a stream of events that summarises the execution in terms of domain concepts and operations. The events enable us to construct a hierarchical model of the execution. A flexible reporting system summarises the execution along developer-chosen model dimensions. The result is a flexible way for a developer to explore the execution of their program without requiring any knowledge of the domain-specific language implementation.These ideas are embodied in a new profiling library called dsprofile that is independent of the problem domain so it has no specific knowledge of the data and operations that are being profiled. We illustrate the utility of dsprofile by using it to profile programs that are written using our Kiama language processing library. Specifically, we instrument Kiama's attribute grammar and term rewriting domain-specific languages to use dsprofile to generate events that report on attribute evaluation and rewrite rule application. Examples of typical language processing tasks show how domain-specific profiling can help to diagnose problems in Kiama-based programs without the developer needing to know anything about how Kiama is implemented.     

Verification of schedulability for real-time programs

Assume that a real-time programP ^T consisting of a number of parallel processes is executed on a system having a setPr of processors which are shared between the processes by a real-time schedulerS ^T. Assume that P^T must meet some timing deadlines. We show that such an implementation ofP ^T can be represented as a transformationL(P ^T) and that the deadlines ofP ^T will be met if they are satisfied by the timing properties of the transformed program. The condition for feasibility of a real-time program executed under a scheduler is formalized and rules are provided for verification. The schedulerS ^T can be specifiedgenerically and applied to different programs, making it unnecessary to introduce low-level operations such as scheduling primitives into the programming language. Thus real-time program specification and Schedulability can be considered in the same framework and the timing properties of a program can be determined at the specification level. By separating the specification of the scheduler from that of the program, the feasibility of an implementation can be proved by considering a scheduling policy rather than its implementation details.     

Requirements simulation for early validation using Behavior Trees and Datalog

ContextThe role of formal specification in requirements validation and analysis is generally considered to be limited because considerable expertise is required in developing and understanding the mathematical proofs. However, formal semantics of a language can provide a basis for step-by-step execution of requirements specification by building an easy to use simulator to assist in requirements elicitation, validation and analysis.ObjectiveThe objective of this paper is to illustrate the usefulness of a simulator that executes requirements and captures system states as rules and facts in a database. The database can then be queried to carry out analysis after all the requirements have been executed a given number of timesMethodBehavior Trees (BTs)¹ are automatically translated into Datalog facts and rules through a simulator called SimTree. The translation process involves model-to-model (M2M) transformation and model-to-text (M2T) transformation which automatically generates the code for a simulator called SimTree. SimTree on execution produces Datalog code. The effectiveness of the simulator is evaluated using the specifications of a published case study – Ambulatory Infusion Pump (AIP)².ResultsThe BT specification of the AIP was transformed into SimTree code for execution. The simulator produced a complete state-space for a predetermined number of runs in the form of Datalog facts and rules, which were then analyzed for various properties of interest like safety and liveness.ConclusionQueries of the resultant Datalog code were found to be helpful in identifying defects in the specification. However, probability values had to be manually assigned to all the events to ensure reachability to all leaf nodes of the tree and timely completion of all the runs. We identify optimization of execution paths to reduce execution time as our future work.     

A generic LSTM neural network architecture to infer heterogeneous model transformations

Models capture relevant properties of systems. During the models’ life-cycle, they are subjected to manipulations with different goals such as managing software evolution, performing analysis, increasing developers’ productivity, and reducing human errors. Typically, these manipulation operations are implemented as model transformations. Examples of these transformations are (i) model-to-model transformations for model evolution, model refactoring, model merging, model migration, model refinement, etc., (ii) model-to-text transformations for code generation and (iii) text-to-model ones for reverse engineering. These operations are usually manually implemented, using general-purpose languages such as Java, or domain-specific languages (DSLs) such as ATL or Acceleo. Even when using such DSLs, transformations are still time-consuming and error-prone. We propose using the advances in artificial intelligence techniques to learn these manipulation operations on models and automate the process, freeing the developer from building specific pieces of code. In particular, our proposal is a generic neural network architecture suitable for heterogeneous model transformations. Our architecture comprises an encoder–decoder long short-term memory with an attention mechanism. It is fed with pairs of input–output examples and, once trained, given an input, automatically produces the expected output. We present the architecture and illustrate the feasibility and potential of our approach through its application in two main operations on models: model-to-model transformations and code generation. The results confirm that neural networks are able to faithfully learn how to perform these tasks as long as enough data are provided and no contradictory examples are given.

     

XML-based Specification of Diagram Editors

This paper describes a graphical specification tool for Dia Gen, a diagram editor generator based on hypergraph grammars and hypergraph transformation. The specification tool greatly simplifies the process of specifying and generating diagram editors. It uses an XML-based specification language, and it is an extension of a generic XML editor which offers syntax-directed editing based on the DTD, i.e, syntax specification, of the underlying XML-based language.     

Promondia: a Java-based framework for real-time group communication in the Web

The World Wide Web has evolved from a distributed hypertext system to a platform-independent graphical user interface that integrates many network services. So far, its technology has restricted it mainly to applications for information retrieval.As networks become ubiquitious and more and more users have a permanent connection, there is an increasing demand for other network services, such as real-time data feeds, group communication, and teleconferencing. So far, these services have been provided by various proprietary software systems, which were hard to set up and use, and thus not very successful.Integrating real-time group communication services into the World Wide Web is a natural way to make them more accessible and will take the Web a step further on its way to becoming the universal network application.In this paper, we describe functionalities required for these services and present an implementation based on Sun Microsystem's Java² programming language. We focus on the high-level functionalities and abstractions, but also describe an object-oriented programming model for group communication systems.     

Typical examples of using the atoment language

Atoment is a domain-specific language of executable specifications applied to describe methods and techniques of program verification. In this paper, a series of typical examples of using the Atoment language covering program models; the operational, transformational, and axiomatic semantics; and the formal specification of programming languages is presented.     

BDL: a specialized language for per-object reactive control

The problem of describing the concurrent behavior of objects in object oriented languages is addressed. The approach taken is to let methods be the behavior units whose synchronization is controlled separate from their specification. Our proposal is a domain-specific language called BDL for expressing constraints on this control and actually implementing its enforcement. We propose a model where each object includes a so-called “execution controller”, programmed in BDL. This separates cleanly the concepts of what the methods do, the object processes, from the circumstances in which they are allowed to do it, the control. The object controller ensures that scheduling constraints between the object's methods are met. Aggregate objects can be controlled in terms of their components. This language has a convenient formal base. Thus, using BDL expressions, behavioral properties of objects or groups of interesting objects can be verified. Our approach allows, for example, deadlock detection or verification of safety properties, while maintaining a reasonable code size for the running controller. A compiler from BDL has been implemented, automatically generating controller code in an Esterel program, i.e., in a reactive programming language. From this code, the Esterel compiler, in turn, generates an automaton on which verifications are done. Then this automaton is translated into a C code to be executed. This multistage process typifies the method for successful use of a domain-specific language. This also allows high level concurrent programming     

A model checking-based approach for security policy verification of mobile systems

This article describes an approach for the automated verification of mobile systems. Mobile systems are characterized by the explicit notion of location (e.g., sites where they run) and the ability to execute at different locations, yielding a number of security issues. To this aim, we formalize mobile systems as Labeled Kripke Structures, encapsulating the notion of location net that describes the hierarchical nesting of the threads constituting the system. Then, we formalize a generic security-policy specification language that includes rules for expressing and manipulating the code location. In contrast to many other approaches, our technique supports both access control and information flow specification. We developed a prototype framework for model checking of mobile systems. It works directly on the program code (in contrast to most traditional process-algebraic approaches that can model only limited details of mobile systems) and uses abstraction-refinement techniques, based also on location abstractions, to manage the program state space. We experimented with a number of mobile code benchmarks by verifying various security policies. The experimental results demonstrate the validity of the proposed mobile system modeling and policy specification formalisms and highlight the advantages of the model checking-based approach, which combines the validation of security properties with other checks, such as the validation of buffer overflows.     

Code generators

Code generators, which take a programmer's inputs in the form of some abstraction, design, or direct interaction with the system and write out a source program that implements the details of the application, are reviewed. After a brief overview, four separate presentations cover examples of such systems from four domains. The Tags tools uses abstraction to specify real-time control systems. In this tool, the details of synchronization code are hidden from the designer, but some functionality must still be provided in detail. Microstep is a similar kind of tool for data-processing applications. One can view both Tags and Microstep as high-level specification languages. PSG generates programming environments, i.e. one gives it a nonprocedural specification of a language's syntax and it generates an integrated programming environment for that language. While one must specify the environment in detailed form, the actual code generation is hidden. Escort is a similar system specialized for telecommunications applications. It lets one build, execute, and test specifications for telecommunication systems. Both PSG and Escort illustrate the power of domain-specific tools     

A System for Generating Reverse Engineering Tools: A Case Study of Software Modularisation

The paper presents a case study in the development of software modularisation tools. The tools are produced by using a system for developing code analysers that uses a database to store both a no-loss fine-grained intermediate representation and the analyses' results. The analysers are automatically generated from a high-level specification of the desired analyses expressed in a domain-oriented language. We use a program intermediate representation, called F(p), as the user-visible data base conceptual model. Analysers are specified in a declarative language, called F(p) – , which allows the specification of an analysis in the form of a traversal of an algebraic expression, with accesses to, and stores of, the database information the algebraic expression indexes. A foreign language interface allows the analysers to be embedded into C programs. This is useful, for example, to implement the user interface of an analyser or to facilitate interoperation of the generated analysers with pre-existing tools.     

Transformation of GRAFCET to PLC code including hierarchical structures

GRAFCET is an advantageous modelling language for the specification of controllers in discrete event systems. It allows for hierarchically structuring a control program's specification based on the elements enclosing steps, partial-Grafcets and forcing orders. A method is already available for the automatic transformation of Grafcets¹ into PLC code but this method cannot keep the hierarchical structures due to limitations of the PLC language SFC. In this contribution a systematic approach to automatically transform Grafcets into PLC code while retaining the hierarchical structures is described.     

Software maintenance: An approach to impact analysis of objects change

The maintenance of a software system requires a tool for impact analysis and the propagation of change. This paper presents a knowledge-based model for both. This model is generic because it is not based on any language or design method. Therefore, it can be applied on the basis of ‘problem’ to be solved. It also captures four life-cycle phases: requirement, specification, design and programming. We also provide a domain-specific view that allows the dependency analysis of fine-grain objects. Two kinds of dependencies are identified: inter-phase dependencies, these are dependency relations between the objects of the one phase and another; and intra-phase dependencies, these are dependency relations between the objects of the same phase. In order to validate this model, we also present a prototype based on two life-cycle phases: design and programming.     

Concurrent runtime monitoring of formally specified programs

A methodology for continuously monitoring a program for specification consistency during program execution is described. Prior development of the formal specification and program is assumed. The program is annotated with constructs from a formal specification language, and the formal specification constructs are transformed into checking code, which is then inserted into the underlying program. Calls to this checking code are inserted into underlying program wherever it can potentially become inconsistent with its specification. If an inconsistency does in fact occur, diagnostic information is provided. The implementation of such a system for Anna (annotated Ada) subtype annotations is presented     

A type-safe embedding of SQL into Java using the extensible compiler framework J%

J% is an extension of the Java programming language that efficiently supports the integration of domain-specific languages. In particular, J% allows the embedding of domain-specific language code into Java programs in a syntax-checked and type-safe manner. This paper presents J%׳s support for the sql language. J% checks the syntax and semantics of sql statements at compile-time. It supports query validation against a database schema or through execution to a live database server. The J% compiler generates code that uses standard jdbc api calls, enhancing runtime efficiency and security against sql injection attacks.