14582007
Adapting Big-Step Semantics to Small-Step Style: Coinductive Interpretations and "Higher-Order" Derivations
We adapt Kahn-style (“big-step”) natural semantics to take on desirable aspects of small-step and denotational semantics forms, more precisely: (i) the ability to express divergent computations; (ii) the ability to reason about the (length of a) computation of a derivation; and (Hi) the ability to compute upon and reason about higher-order values. To accomplish these results, we extend the classical, inductive interpretation of natural semantics with coinduction mechanisms and use “negative” rules to express divergence. A simple reformatting of the syntax of derivations allows a simple description of the “length” of a derivation. Finally, the receding of closure values into denotational-semantics-like functions lets one embed derivations within closures that embed within derivations; in this sense, the semantics becomes “higher order.” Examples are given to support the definitional developments.
37519260
Trace-Based Abstract Interpretation of Operational Semantics
We present trace-based abstract interpretation, a unification of severallines of research on applying Cousot-Cousot-style abstract interpretation a.i. tooperational semantics definitions (such as flowchart, big-step, and small-step semantics)that express a program‘s semantics as a concrete computation tree of trace paths. Aprogram‘s trace-based a.i. is also a computation tree whose nodes contain abstractions ofstate and whose paths simulate the paths in the program‘s concrete computation tree.Using such computation trees, we provide a simple explanation of the central concept of collecting semantics, and we distinguish concrete from abstract collectingsemantics and state-based from path-based collecting semantics. We also expose therelationship between collecting semantics extraction and results garnered from flow-analytic and model-checking-based analysis techniques. We adapt concepts fromconcurrency theory to formalize “safe” and “live” a.i.‘s for computation trees; in particular, coinduction techniques help extend fundamental results to infinite computation trees.Problems specific to the various operational semantics methodologies are discussed: Big-step semantics cannot express divergence, so we employ a mixture of induction andcoinduction in response; small-step semantics generate sequences of programconfigurations unbounded in size, so we abstractly interpret source language syntax.Applications of trace-based a.i. to data-flow analysis, model checking, closure analysis,and concurrency theory are demonstrated.
16028114
Modal Transition Systems: A Foundation for Three-Valued Program Analysis
We present Kripke modal transition systems (Kripke MTSs), a generalization of modal transition systems [27, 26], as a foundation for three-valued program analysis. The semantics of Kripke MTSs are presented by means of a mixed power domain of states; soundness and consistency are proved. Two major applications, model checking partial state spaces and three-valued program shape analysis, are presented as evidence of the suitability of Kripke MTSs as a foundation for three-valued analyses.
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.
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.
8854332
The design of the TAO real-time object request broker
Many real-time application domains can benefit from flexible and open distributed architectures, such as those defined by the CORBA specification. CORBA is an architecture for distributed object computing being standardized by the OMG. Although CORBA is well-suited for conventional request/response applications, CORBA implementations are not yet suited for real-time applications due to the lack of key quality of service (QoS) features and performance optimizations. This paper makes three contributions to the design of real-time CORBA systems. First, the paper describes the design of TAO, which is our high-performance, real-time CORBA 2.0-compliant implementation that runs on a range of OS platforms with real-time features including VxWorks, Chorus, Solaris 2.x, and Windows NT. Second, it presents TAO's real-time scheduling service that can provide QoS guarantees for deterministic real-time CORBA applications. Finally, the paper presents performance measurements that demonstrate the effects of priority inversion and non-determinism in conventional CORBA implementations and how these hazards are avoided in TAO.
169019
An Approach for Supporting Aspect-Oriented Domain Modeling
This paper describes a technique for improving separation of concerns at the level of domain modeling. A contribution of this new approach is the construction of support tools that facilitate the elevation of crosscutting modeling concerns to first-class constructs in a type-system. The key idea is the application of a variant of the OMG Object Constraint Language to models that are stored persistently in XML. With this approach, weavers are generated from domain-specific descriptions to assist a modeler in exploring various alternative modeling scenarios. The paper examines several facets of Aspect-Oriented Domain Modeling (AODM), including: domain-specific model weavers, a language to support the concern separation, an overview of code generation issues within a meta-weaver framework, and a comparison between AODM and AOP. An example of the approach is provided, as well as a description of several future concepts for extending the flexibility within AODM.
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.
7153761
Total quality of service provisioning in middleware and applications
Abstract Commercial off-the-shelf (COTS) middleware, such as real-time CORBA, is gaining acceptance in the distributed real-time and embedded (DRE) community. Existing COTS specifications, however, do not effectively separate quality of service (QoS) policy configurations and adaptations from application functionality. DRE application developers therefore often intersperse code that provisions resources for QoS guarantees and program adaptation mechanisms throughout DRE applications, making it hard to configure, validate, modify, and evolve complex DRE applications. This paper illustrates how (1) standard component-based middleware can be enhanced to flexibly compose static QoS provisioning policies with application logic, (2) adaptive middleware capabilities enable developers to abstract and encapsulate reusable dynamic QoS provisioning and adaptive behaviors, and (3) component-based middleware and adaptive middleware capabilities can be integrated to provide a total QoS provisioning solution for DRE applications.
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.