207196655
Programming language semantics
A programming language possesses syntax and semantics. Syntax refers to the spelling of the language’s programs, and semantics refers to the meanings of the programs. A language’s syntax is formalized by a grammar or syntax chart; such formalizations are found in the back of language manuals. A language’s semantics should be formalized, too, and this is the topic of this chapter. Before we begin, we might ask, “What do we gain by formalizing the semantics of a programming language?” Consider the related question, “What was gained when language syntax was formalized with BNF?” • A language’s syntax definition standardizes the official syntax. This is crucial to users, who require a guide to writing syntactically correct programs, and to implementors, who must write a correct parser for the language’s compiler. • The syntax definition permits a formal analysis of its properties, such as whether the definition is LL(k), LR(k), or ambiguous. • The syntax definition can be used as input to a compiler front-end generating tool, such as YACC; it becomes, in effect, the implementation. We derive similar benefits from a formal semantics definition: • The semantics definition standardizes the official semanticsof the language. This is crucial to users, who require a guide to understanding the programs that they write, and to implementors, who must write a correct code generator for the language’s compiler. • The semantics definition permits a formal analysis of its properties, such as whether the definition is strongly typed, block structured, uses single-threaded data structures, is parallelizable, etc. • The semantics definition can be used as input to a compiler back-end generating tool [26, 31]; it becomes, in effect, the implementation. Programming-language syntax was studied intensively in the 1960’s and 1970’s, and programming language semantics is undergoing similar intensive study. Unlike the acceptance of BNF as the standard for syntax definition, it is unlikely that a single definition method will take hold for semantics—semantics is harder to formalize than syntax, and it has a wider variety of applications. Semantics-definition methods fall roughly into three groups:
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:
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.
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.
14166028
The Design and Performance of a Pluggable Protocols Framework for Real-Time Distributed Object Computing Middleware
To be an effective platform for performance-sensitive real-time and embedded applications, off-the-shelf CORBA middleware must preserve the communication-layer quality of service (QoS) properties of applications end-to-end. However, the standard CORBA GIOP/HOP interoperability protocols are not well suited for applications that cannot tolerate the message footprint size, latency, and jitter associated with general-purpose messaging and transport protocols. It is essential, therefore, to develop standard pluggable protocols frameworks that allow custom messaging and transport protocols to be configured flexibly and used transparently by applications. 
 
This paper provides three contributions to research on pluggable protocols frameworks for performance-sensitive distributed object computing (DOC) middleware. First, we outline the key design challenges faced by pluggable protocols developers. Second, we describe how we resolved these challenges by developing a pluggable protocols framework for TAO, which is our high-performance, real-time CORBA -compliant ORB. Third, we present the results of benchmarks that pinpoint the impact of TAO's pluggable protocols framework on its end-to-end efficiency and predictability. 
 
Our results demonstrate how the application of optimizations and patterns to DOC middleware can yield both highly flexible/reusable designs and highly efficient/predictable implementations. In particular, the overall roundtrip latency of a TAO two-way method invocation using the standard inter-ORB protocol and using a commercial, off-the-self Pentium II Xeon 400 MHz workstation running in loopback mode is ~189 µsecs. The ORB middleware accounts for approximately 48% or ~90 µsecs of the total roundtrip latency. Using the specialized POSIX local IPC protocol reduces roundtrip latency to ~125 µsecs. These results illustrate that (1) DOC middleware performance is largely an implementation detail and (2) the next-generation of optimized, standards-based CORBA middleware can replace ad hoc and proprietary solutions.
2537488
Techniques for optimizing CORBA middleware for distributed embedded systems
The distributed embedded systems industry is poised to leverage emerging real-time operating systems, such as Inferno Windows CE, EPOC, and Palm OS to support mobile communication applications, such as electronic mail, Internet browsing, and network management. Ideally, these applications can be developed using standard middleware components like CORBA to improve their quality and reduce their cost and cycle time. However, stringent constraints on memory available in embedded systems imposes a severe limit on the footprint of CORBA middleware. This paper provides three contributions to the study and design of small footprint, embedded CORBA middleware. First, we describe the optimizations used to develop the protocol engine and CORBA IDL compiler provided by TAO, which is our real-time CORBA implementation. TAO's IDL compiler produces stubs that can use either compiled and/or interpretive marshalling. Second, we compare the performance and footprint of TAO IDL compiler-generated stubs and skeletons that use compiled and/or interpretive marshalling for a wide range of IDL data types. Third, we illustrate the benefits of the small footprint and efficiency of TAO IDL compiler-generated stubs and skeletons for CORBA object services implemented using TAO. The results comparing the performance of the compiled and interpretive stubs and skeletons indicate that the interpretive stubs and skeletons perform between 75-100% of the compiled stubs and skeletons for a wide range of data types. However the code size for the interpreted stubs and skeletons was between 26-45% and 50-80% of the compiled stubs and skeletons, respectively. These results indicate a positive step towards implementing high performance, small footprint middleware for distributed embedded systems.
15679644
The J3 Process for Building Autonomic Enterprise Java Bean Systems
Autonomic computer systems aim to reduce the configuration, operational, and maintenance costs of distributed enterprise applications. This paper provides two contributions to the development of autonomic computing systems using Enterprise Java Beans (EJBs). First, we describe a model-driven development (MDD) tool that formally captures the design of EJB systems, their quality of service (QoS) requirements, and the autonomic properties that will be applied to the EJBs to support the rapid development of autonomic EJB applications. Second, we describe how this MDD tool can generate code to plug EJBs into a Java component framework that provides an autonomic structure to monitor, configure, and execute EJBs and their adaptation strategies at run-time
2571822
Towards Real-Time Fault-Tolerant CORBA Middleware
An increasing number of applications are being developed using Distributed Object Computing (DOC) middleware, such as CORBA. Many of these applications require the underlying middleware, operating systems, and networks to provide dependable end-to-end Quality of Service (QoS) support to enhance their efficiency, predictability, scalability, and reliability. The Object Management Group (OMG), which standardizes CORBA, has addressed many of these application requirements individually in the Real-Time CORBA (RT-CORBA) and Fault-Tolerant CORBA (FT-CORBA) specifications. Though the implementations of RT-CORBA are suitable for mission-critical commercial or military distributed Real-Time and Embedded (DRE) systems, the usage of FT-CORBA with RT-CORBA implementations are not yet suitable for systems that have stringent simultaneous dependability and predictability requirements.This paper provides three contributions to the study and evaluation of dependable CORBA middleware for performance-sensitive DRE systems. First, we provide an overview of FT-CORBA and illustrate the sources of unpredictability associated with conventional FT-CORBA implementations. Second, we discuss the QoS requirements of an important class of mission-critical DRE systems to show how these requirements are not well served by FT-CORBA today. Finally, we empirically evaluate new dependability strategies for FT-CORBA that can help make the use of DOC middleware for mission-critical DRE systems a reality.
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.