Formatted programming languages

This paper presents a systematic approach to formatted language design that incorporates formatting within the syntax of programming languages. The approach includes:

• 1 a metasyntax to ensure that program text is foldable, not only to avoid right margin overflow but also to preclude constructs which are visually confusing or ambiguous;
• 2 a set of guidelines for language designers to enhance readability within the constraints of the metasyntax; and
• 3 a folding algorithm which selectively folds a program text.

The resulting automatic formatting is consistent with current practice in program and text layout. The effect of this approach is to put program format decisions in the domain of the language's designer, rather than its several implementors or numerous users, which implies uniformly formatted programs of improved readability and therefore usability.     

Compile—time detection of aliasing in euclid programs

Aliasing of variables occurs when two or more identifiers accessible in the same scope refer to the same storage location. When aliasing is present, the meaning of assignments becomes obscure because assignment to one variable identifier may change the value of others. Some of the more obscure kinds of variable aliasing can be the cause of particularly insidious bugs in computer programs. Axiomatic proof systems, such as that used for the Euclid language, assume that no aliasing is present so that the meaning of assignment is clear. For this reason, Euclid requires that no aliasing be present in Euclid programs and requires the compiler to implement checks to ensure this. This paper discusses the features of Euclid that aid in the detection of aliasing. It enumerates the kinds of aliasing that can be present in Euclid programs and gives efficient one-pass algorithms for compile-time detection of potential aliases. Aliasing is related to interference between concurrent processes, and a similar algorithm for detection of inter-process interference in Concurrent Euclid programs is presented.     

Functional programming languages for verification tools: a comparison of Standard ML and Haskell

We compare Haskell with Standard ML as programming languages for verification tools based on our experience developing the verification platform Truth in Haskell and the Edinburgh Concurrency Workbench (CWB) in Standard ML. We review not only technical language features but also the worlds of the languages, for example, the availability of compilers, tools, and libraries. We also discuss the merits and difficulties of comparing programming languages in this wide sense and support our view that Truth and the CWB are similar enough to justify the conclusions drawn in this paper.     

Systems implementation languages and IRONMAN

The U.S. Department of Defense has recently issued a set of requirements, which it called IRONMAN, for the design of a programming language that it will use for embedded computer applications. To date four competing languages have been designed and, after considerable debate and scrutiny, these have been reduced to two. It is expected that the winning language will be selected during 1979. This report compares the IRONMAN requirements against the state-of-the-art in systems implementation language design in an attempt to see the extent to which IRONMAN can be met from existing technology. Particular emphasis is given to the areas of large-scale program structuring, parallel programming, exception handling and hardware interaction. Finally, Dijkstra's criticism of IRONMAN and the competing languages will be examined. It will be argued that he may be justified in doubting the viability of a language with such diverse features.     

A comparison of programming languages for software engineering

Four programming languages (Fortran, Cobol, Jovial and the proposed DoD standard) are compared in the light of modern ideas of good software engineering practice. The comparison begins by identifying a core for each language that captures the essential properties of the language and the intent of the language designers. These core languages then serve as a basis for the discussion of the language philosophies and the impact of the language on gross program organization and on the use of individual statements.     

Model checking, testing and verification working together

We present a symbolic model checking approach that allows verifying a unit of code, e.g., a single procedure or a collection of procedures that interact with each other. We allow temporal specifications that assert over both the program counters and the program variables. We decompose the verification into two parts: (1) a search that is based on the temporal behavior of the program counters, and (2) the formulation and refutation of a path condition, which inherits conditions constraining the program variables from the temporal specification. This verification approach is modular, as we do not require that all the involved procedures are provided. Furthermore, we do not request that the code is based on a finite domain. The presented approach can also be used for automating the generation of test cases for unit testing.A preliminary version of the paper, with the title Unit Checking: Symbolic Model Checking for a Unit of Code appears in the Lecture Notes in Computer Science volume 2772, Verification– Theory and Practice, celebrating Zohar Manna’s 64th birthdayThis research was partially supported by US Army Research Office Grant number DAAAD19-01-1-0473This research was partially supported by Subcontract UTA03-031 to The University of Warwick under University of Texas at Austin’s prime National Science Foundation Grant #CCR-0205483Received February 2004Revised September 2004 and April 2005Accepted April 2005 by M. Leuschel and D. J. Cooke     

Program testing by specification mutation

Both theoretical and empirical arguments suggest that specifications and implementations are equally important sources of information for generating test cases. Nevertheless, the majority of test generation procedures described in the literature deal only with the program source, ignoring specifications. In this paper we outline a procedure for measuring test case effectiveness using specifications given in predicate calculus form. This method is similar to the mutation analysis method of testing programs.     

A semantically-based formatting discipline for Pascal

The abstract (or semantic) syntax of the Pascal language is identified, and a linear representation for the trees so formed within the framework of the concrete syntax for that language is imposed. The indentation scheme so formed, augmented with a small number of pragmatic considerations, is compared with several previously proposed formatting schemes for Pascal and an example of the use of this new method is given.     

The definition of comments in programming languages

This paper examines the concept of comments in programming languages and answers the questions: Why are they needed? How are they defined and implemented in existing languages? What should be provided in future languages?     

Regular patterns, regular languages and context-free languages

In this paper we consider two questions. First we consider whether every pattern language which is regular can be generated by a regular pattern. We show that this is indeed the case for extended (erasing) pattern languages if alphabet size is at least four. In all other cases, we show that there are patterns generating a regular language which cannot be generated by a regular pattern. Next we consider whether there are pattern languages which are context-free but not regular. We show that, for alphabet size 2 and 3, there are both erasing and non-erasing pattern languages which are context-free but not regular. On the other hand, for alphabet size at least 4, every erasing pattern language which is context-free is also regular. It is open at present whether there exist non-erasing pattern languages which are context-free but not regular for alphabet size at least 4.     

A survey of recent advances in SAT-based formal verification

Dramatic improvements in SAT solver technology over the last decade and the growing need for more efficient and scalable verification solutions have fueled research in verification methods based on SAT solvers. This paper presents a survey of the latest developments in SAT-based formal verification, including incomplete methods such as bounded model checking and complete methods for model checking. We focus on how the surveyed techniques formulate the verification problem as a SAT problem and how they exploit crucial aspects of a SAT solver, such as application-specific heuristics and conflict-driven learning. Finally, we summarize the noteworthy achievements in this area so far and note the major challenges in making this technology more pervasive in industrial design verification flows.     

Union and intersection types to support both dynamic and static typing

Although static typing provides undeniable benefits for the development of applications, dynamically typed languages have become increasingly popular for specific scenarios. Since each approach offers different benefits, the StaDyn programming language has been designed to support both dynamic and static typing. This paper describes the minimal core of the StaDyn programming language. Its type system performs type reconstruction over both dynamic and static implicitly typed references. A new interpretation of union and intersection types allows statically gathering the type information of dynamic references, which improves runtime performance and robustness. The evaluation of the generated code has shown how our approach offers an important runtime performance benefit.     

Enzymatic competition: Modeling and verification with timed hybrid petri nets

The formalism of hybrid functional petri nets (HFPN) has proved its convenience for simulating biological systems. The drawback of the noticeable expressiveness of HFPN is the difficulty to perform formal verifications of dynamical properties. In this article, we propose a model-checking procedure for timed hybrid petri nets (THPN), a sub-class of HFPN. This procedure is based on the translation of the THPN model and of the studied property into real-time automata. It is applied to model enzymatic competitions existing in amphibian metamorphosis.     

Automated formal verification of visual modeling languages by model checking

Graph transformation has recently become more and more popular as a general, rule-based visual specification paradigm to formally capture (a) requirements or behavior of user models (on the model-level), and (b) the operational semantics of modeling languages (on the meta-level) as demonstrated by benchmark applications around the Unified Modeling Language (UML). The current paper focuses on the model checking-based automated formal verification of graph transformation systems used either on the model-level or meta-level. We present a general translation that inputs (i) a metamodel of an arbitrary visual modeling language, (ii) a set of graph transformation rules that defines a formal operational semantics for the language, and (iii) an arbitrary well-formed model instance of the language and generates a transitions system (TS) that serve as the underlying mathematical specification formalism of various model checker tools. The main theoretical benefit of our approach is an optimization technique that projects only the dynamic parts of the graph transformation system into the target transition system, which results in a drastical reduction in the state space. The main practical benefit is the use of existing back-end model checker tools, which directly provides formal verification facilities (without additional efforts required to implement an analysis tool) for many practical applications captured in a very high-level visual notation. The practical feasibility of the approach is demonstrated by modeling and analyzing the well-known verification benchmark of dining philosophers both on the model and meta-level.     

An integrated verification and testing environment

A verification and testing environment that includes static analysis, symbolic execution, and dynamic analysis capabilities is presented. Tool integration and co-operation are promoted through use of an intermediate program representation and a system data manager. A substantial user interface aids application of the tools. Their use is guided by a verification and testing methodology on which the system's design is based. The environment has been engineered to support the production of flight control software written in HAL/S. The environment itself is written in Pascal and is designed to be portable. Several development experiences are described. The environment demonstrates that a strong, unified verification and testing environment can be built; it serves as a basis for future investigations.     

Efficient verification of timed automata with BDD-like data structures

We investigate the effect on efficiency of various design issues for BDD-like data structures of TA state space representation and manipulation. We find that the efficiency is highly sensitive to decision atom design and canonical form definition. We explore the two issues in detail and propose to use CRD (Clock-Restriction Diagram) for TA state space representation and present algorithms for manipulating CRD in the verification of TAs. We compare three canonical forms for zones, develop a procedure for quick zone-containment detection, and present algorithms for verification with backward reachability analysis. Three possible evaluation orderings are also considered and discussed. We implement our idea in our tool Red 4.2 and carry out experiments to compare with other tools and various strategies of Red in both forward and backward analysis. Finally, we discuss the possibility of future improvement.     

Approximate verification in an open source world

This article details advances in a lightweight technology we have evolved to handle post hoc verification in the very large, uncontrolled and rapidly evolving code-bases exemplified by C language open source projects such as the Linux kernel. Successful operation in this context means timeliness, and we are currently treating millions of lines of unrestricted mixed C and assembler source code in a few hours on very modest platforms. The technology is soundly based, in that it delivers false alarms (in a ratio of about 8 to 1 in practice), rather than misses true alarms. Speed of operation is traded off against accuracy via configuration of a program logic tailored to each analysis. The program logic specification language and the theory behind it will be described here.