7376459
State transition machines for lambda calculus expressions
The process of compiler generation from formal definitions of the lambdacalculus is studied. The compiling schemes developed utilize as an object language the set of state transition machines (STMs): automata-like transition sets using first order arguments. An intermediate definition form, the STM_interpreter, is defined and treated as central to the formulation of state transition code. Three compiling schemes are produced: one derived directly from an STM-interpreter; one formulated from a version of Landin's SECD-machine; and one defined through meaning preserving transformations upon a denotational definition of the lambda-calculus itself. The results are compared and some tentative conclusions are made regarding the utility of compiler generation with the use of the STM forms.
7872163
Closed and Logical Relations for Over- and Under-Approximation of Powersets
We redevelop and extend Dams’s results on over- and under-approximation with higher-order Galois connections:
105294
Structure-Preserving Binary Relations for Program Abstraction
An abstraction is a property-preserving contraction of a program's model into a smaller one that is suitable for automated analysis. An abstraction must be sound, and ideally, complete. Soundness and completeness arguments are intimately connected to the abstraction process, and approaches based on homomorphisms and Galois connections are commonly employed to define abstractions and prove their soundness and completeness.This paper develops Mycroft and Jones's proposal that an abstraction should be stated as a form of structure-preserving binary relation. Mycroft-Jones-style relations are defined, developed, and employed in characterizations of the homomorphism and Galois-connection approaches to abstraction.
484422
A domain equation for refinement of partial systems
A reactive system can be specified by a labelled transition system, which indicates static structure, along with temporal-logic formulas, which assert dynamic behaviour. But refining the former while preserving the latter can be difficult, because:(i) Labelled transition systems are ‘total’ – characterised up to bisimulation – meaning that no new transition structure can appear in a refinement.(ii) Alternatively, a refinement criterion not based on bisimulation might generate a refined transition system that violates the temporal properties.In response, Larsen and Thomson proposed modal transition systems, which are ‘partial’, and defined a refinement criterion that preserved formulas in Hennessy–Milner logic. We show that modal transition systems are, up to a saturation condition, exactly the mixed transition systems of Dams that meet a mix condition, and we extend such systems to non-flat state sets. We then solve a domain equation over the mixed powerdomain whose solution is a bifinite domain that is universal for all saturated modal transition systems and is itself fully abstract when considered as a modal transition system. We demonstrate that many frameworks of partial systems can be translated into the domain: partial Kripke structures, partial bisimulation structures, Kripke modal transition systems, and pointer-shape-analysis graphs.
6204500
Underapproximating Predicate Transformers
We study the underapproximation of the predicate transformers used to give semantics to the modalities in dynamic and temporal logic. Because predicate transformers operate on state sets, we define appropriate powerdomains for sound approximation. We study four such domains — two are based on “set inclusion” approximation, and two are based on “quantification” approximation — and we apply the domains to synthesize the most precise, underapproximating $\widetilde{pre}$ and pre transformers, in the latter case, introducing a focus operation. We also show why the expected abstractions of post and $\widetilde{post}$ are unsound, and we use the powerdomains to guide us to correct, sound underapproximations.
36184751
Abstract Interpretation of Small-Step Semantics
The techniques of classical abstract interpretation are extended to the big- and small-step operational semantics of higher-order and communicative languages: Well-known techniques, such as memoization, and lesser-known ones, such as abstraction on program syntax, are employed to generate finite abstract interpretations of source programs based on their formal operational semantic definitions. The result is a clear methodology for generating semantically safe (and live) abstract, regular trees for programs that do not possess obvious, finite, state-transition diagram depictions. The primary application of the research is to the validation of program properties; in particular, the application of model checking to validate safety properties in the box-mu calculus and liveness properties in the diamond-mu calculus is discussed.
7135801
Experience Using Design Patterns to Evolve Communication Software Across Diverse OS Platforms
Design patterns help to improve communication software quality since they address a fundamental challenge in large-scale software development: communication of architectural knowledge among developers. This paper makes several contributions to the study and practice of design patterns. It presents a case study that illustrates how design patterns helped to reduce development effort and project risk when evolving an object-oriented telecommunication software framework across UNIX and Windows NT OS platforms. Second, the paper discusses the techniques, benefits, and limitations of applying a design pattern-based reuse strategy to commercial telecommunication software systems.
8465192
Towards predictable real-time Java object request brokers
Distributed real-time and embedded (DRE) applications often possess stringent quality of service (QoS) requirements. Designing middleware for DRE applications poses several challenges to object request broker (ORB) developers. This paper provides the following contributions to the study of middleware for DRE applications. First, we outline the challenges present in one of the principal ORB components - the portable object adapter (POA) focusing on predictable and scalable demultiplexing. Second, we describe how these challenges are addressed in ZEN, which is an implementation of Real-time CORBA that runs atop jRate, an ahead-of-time compiler that implements most of the Real-Time Specification for Java (RTSJ). Third, we qualitatively and quantitatively compare ZEN's demultiplexing strategies with those of other popular Java ORBs, including JacORB, Sun JDK ORB, and ORBacus. Our results show that ZEN and jRate incorporate the strategies necessary to enable predictability using standards-based middleware and also provide a baseline for what can be achieved by combining Real-time CORBA and RTSJ.
10426622
Object-Oriented Components for High-speed Network Programming
This paper makes two contributions to the development and evaluation of object-oriented communication software. First, it reports performance results from benchmarking several network programming mechanisms (such as sockets and CORBA) on Ethernet and ATM networks. These results illustrate that developers of bandwidth-intensive and delay-sensitive applications (such as interactive medical imaging or teleconferencing) must evaluate their performance requirements and the efficiency of their communication infrastructure carefully before adopting a distributed object solution. Second, the paper describes the software architecture and design principles of the ACE object-oriented network programming components. These components encapsulate UNIX and Windows NT network programming interfaces (such as sockets, TLI, and named pipes) with C++ wrappers. Developers of object-oriented communication software have traditionally had to choose between high-performance, lower-level interfaces provided by sockets or TLI or less efficient, higher-level interfaces provided by communication frameworks like CORBA or DCE. ACE represents a midpoint in the solution space by improving the correctness, programming simplicity, portability, and reusability of performance-sensitive communication software.
447257
Techniques and processes for improving the quality and performance of open-source software
Open-source development processes have emerged as an effective approach to reduce cycle-time and decrease design, implementation, and quality assurance (QA) costs for certain types of software, particularly systems infrastructure software, such as operating systems (OS), compilers and language processing tools, text and drawing editors, and middleware. This article presents two contributions to the study of open-source software processes. First, we describe key challenges of open-source software and illustrate how QA processes—specifically those tailored to open-source development—help mitigate these challenges better than traditional closed-source processes do. Second, we summarize results of empirical studies that evaluate how our Skoll distributed continuous quality assurance (DCQA) techniques and processes help to resolve key challenges in developing and validating open-source software. Our results show that: (a) using models to configure and guide the DCQA process improves developer understanding of open-source software, (b) improving the diversity of platform configurations helps QA engineers find defects missed during conventional testing, and (c) centralizing control of QA activities helps to eliminate redundant work. Copyright © 2006 John Wiley & Sons, Ltd.
1313476
Design and Performance of Asynchronous Method Handling for CORBA
This paper describes the design and performance of a new mechanism, called asynchronous method handling (AMH), that allows CORBA servers to process client requests asynchronously. AMH decouples the association of an incoming request from the run-time stack that received the request, without incurring the context-switching, synchronization, and data movement overhead of conventional CORBA multithreading models.This paper provides two contributions to the study of asynchrony for CORBA servers. First, it describes the design and implementation of AMH in The ACE ORB (TAO), a C++ CORBA ORB. The syntax and semantics of AMH are defined using the CORBA Interface Definition Language (IDL), the forces that guided the design of AMH are described, and the patterns and C++ idioms used to resolve these forces are presented. Second, we empirically compare a middle-tier server implemented using AMH against other CORBA server concurrency models and show the advantages of the AMH mechanism against the other models.