42747855
Action Semantics-Directed Prototyping
We present a methodology for compiler synthesis based on Mosses-Watt's action semantics. Each action in action semantics notation is assigned specific ''analysis functions'', such as a typing function and a binding-time function. When a language is given an action semantics, the typing and binding-time functions for the individual actions compose into typing and binding-time analyses for the language; these are implemented as the type checker and static semantics processor, respectively, in the synthesized compiler. Other analyses can be similarly formalized and implemented. We show a sample language semantics and its synthesized compiler, and we describe the compiler synthesizer that we have developed.
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.
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.
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.
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.
207550710
Induction, Domains, Calculi: Strachey's Contributions to Programming-Language Engineering
In collaboration with his colleagues at Oxford, Christopher Strachey pioneered the analysis of programming languages in terms of semantic features. Three of Strachey's contributions—inductive definition of semantics, semantic-domain definitions, and calculi for semantic description—are presented, and their consequences on languages research are described. Strachey's impact, present and future, on the computer programming “mainstream” is also outlined.
19268575
Enhancing Real-Time CORBA Predictability and Performance
Distributed real-time and embedded (DRE) applications possess stringent quality of service (QoS) requirements, such as low latency, bounded jitter, and high throughput. An increasing number of DRE applications are developed using QoS-enabled middleware, such as Real-time CORBA and the Real-time Specification for Java (RTSJ), to ensure predictable end-to-end QoS. Real-time CORBA is an open middleware standard that allows DRE applications to allocate, schedule, and control the QoS of CPU, memory, and networking resources. The RTSJ provides extensions to Java that enable it to be used as the basis for Real-time CORBA middleware and applications.
11437113
The Design and Performance of a Scalable ORB Architecture for CORBA Asynchronous Messaging
Historically, method-oriented middleware, such as Sun RPC, DCE, Java RMI, COM, and CORBA, has provided synchronous method invocation (SMI) models to applications. Although SMI works well for conventional client/server applications, it is not well-suited for highperformance or real-time applications due to its lack of scalability. To address this problem, the OMG has recently standardized an asynchronous method invocation (AMI) model for CORBA. AMI provides CORBA with many of the capabilities associated traditionally with messageoriented middleware, without incurring the key drawbacks of messageoriented middleware.
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.
209399239
Model driven development for distributed real-time and embedded systems
Despite advances in standards-based commercial-off-the-shelf (COTS) technologies, key challenges must be addressed before COTS software can be used to build mission-critical DRE systems effectively and productively. For example, developers of DRE systems continue to use ad hoc means to develop, configure, and deploy their applications and middleware due to the lack of formally analyzable and verifiable building block components. This talk will describe how Model Driven Development (MDD) techniques and tools can be used to specify, analyze, optimize, synthesize, validate, and deploy product-line architectures (PLAs) and standards-compliant middleware platforms that can be customized for the needs of next-generation DRE systems. MDD is an emerging paradigm that combines: - Domain-specific modeling languages (DSMLs), which provide programming notations that formalize the process of specifying application logic and quality of service (QoS)-related requirements in a PLA. - Metamodeling, which define type systems that precisely express key characteristics and constraints associated with DSMLs for PLAs in particular application domains, such as software defined radios, avionics, vehtronics, and process automation. - Model transformations and synthesis techniques that automate and ensure the consistency of software implementations with analysis information associated with functional and QoS requirements captured by models of PLA structure and behavior. This talk will compare and contrast various model-based approaches (e.g., MIC, MDD, MDA, etc) to developing PLA-based DRE systems. It will also illustrate how MDD techniques and tools have been successfully integrated with standards-based QoS-enabled component middleware to develop PLAs that significantly improve the quality and productivity associated with developing next-generation mission-critical DRE systems. Concrete examples from avionics, process control, software defined radios, and warehouse management systems will be used to illustrate key points.
34634690
The Design and Performance of MedJava
The Java programming language has gained substantial popularity in the past two years. Java’s networking features, along with the growing number of Web browsers that execute Java applets, facilitate Internet programming. Despite the popularity of Java, however, there are many concerns about its efficiency. In particular, networking and computation performance are key concerns when considering the use of Java to develop performance-sensitive distributed applications. This paper makes three contributions to the study of Java for performance-sensitive distributed applications. First, we describe an architecture using Java and the Web to develop MedJava, which is a distributed electronic medical imaging system with stringent networking and computation requirements. Second, we present benchmarks of MedJava image processing and compare the results to the performance of xv, which is an equivalent image processing application written in C. Finally, we present performance benchmarks using Java as a transport interface to exchange large medical images over high-speed ATM networks. For computationally intensive algorithms, such as image filters, hand-optimized Java code, coupled with use of a JIT compiler, can sometimes compensate for the lack of compiletime optimization and yield performance commensurate with identical compiled C code. With rigorous compile-time optimizations employed, C compilers still tend to generate more efficient code. However, with the advent of highly optimizing Java compilers, it should be feasible to use Java for the This research is supported in part by a grant from Siemens Medical Engineering, Erlangen, Germany. performance-sensitive distributed applications where C and C++ are currently used.