43800980
Type Inference for Action Semantics
In a series of papers [11,12,13,14,15,25,26], Mosses and Watt defme action semantics, a metalanguage for high level, domain-independent formulation of denotational semantics definitions. Action semantics was designed to support readability, abstraction, modularity, and modifiability of language definitions [13,15]. In our recent work [5], we studied a combinator-based version of action semantics. We developed a typing system for actions based on types and k/nds. The types within a kind are partially ordered to reflect subtyping. We then defined a category-sorted algebra model [18,20] for the system where actions are natural transformations over interpretation functors (which map the type names and their ordering to predomains and coercion functions). Thus, an action is a family of continuous functions that behave consistently with respect to the subtyping relation. Coercion functions-even nonembeddings-disappear. The typing system and its interpretation support an ML-style type inference algorithm for action expressions. Type inference must respect the subtyping laws, so we encounter the problems discovered by Mitchell [10], Fuh and Mishra [6], and Wand [24] regarding constraints sets. But action notation and its model are formulated so that the major problems regarding constraints are "restricted away." In particular, the monotonic behavior of actions with respect to the subtyping ordering keeps the cardinality of constraints sets small and makes constraints on record types unnecessary, even in the presence of record union and concatenation operations. This paper presents our variant of action semantics and its typing system. We give the type inference algorithms, state properties that action semantics expressions satisfy, give soundness and completeness properties and explain why they hold for type inference on action semantics expressions. We also present a small example.
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.
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.
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.
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.
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:
15114120
Designing an Efficient and Scalable Server-side Asynchrony Model for CORBA
When the Asynchronous Method Invocation (AMI) model was introduced into the CORBA specification, client applications benefited from the ability to invoke non-blocking two-way requests. In particular, AMI improved the scalability of clients by removing the restrictions associated with Synchronous Method Invocations (SMI). Server request handling remained synchronous, however, which minimized the benefits of AMI for middle-tier servers, such as firewall gateways and front-end database servers.This paper describes our strategy for implementing a scalable server-side asynchrony model for CORBA. We first outline the key design challenges faced when developing an Asynchronous Method Handling (AMH) model for CORBA and then describe how we are resolving these challenges in TAO, our high-performance, real-time CORBA ORB. In general, AMH-based CORBA servers provide more scalability than existing concurrency models, with only a moderate increase in programming complexity. Although targeted for CORBA, similar techniques can also be used in other method-oriented middleware, such as COM+ and Java RMI.
2673038
Designing and Optimizing a Scalable CORBA Notification Service
Many distributed applications require a scalable event-driven communication model that decouples suppliers from consumers and simultaneously supports advanced quality of service (QoS) properties and event filtering mechanisms. The CORBA Notification Service provides a publish/subscribe mechanism that is designed to support scalable event-driven communication by routing events efficiently between many suppliers and consumers, enforcing various QoS properties (such as reliability, priority, ordering, and timeliness), and filtering events at multiple points in a distributed system.This paper provides several contributions to research on scalable notification services. First, we present the CORBA Notification Service architecture and illustrate how it addresses limitations with the earlier CORBA Event Service. Second, we explain how we addressed key design challenges faced when implementing the Notification Service in TAO, which is our high-performance, real-time ORB. We discuss the optimizations used to improve the scalability of TAO's Notification Service. Finally, we present empirical results of the performance of our implementation.
1095079
Controlling quality-of-service in distributed real-time and embedded systems via adaptive middleware
Computing systems are increasingly distributed, real-time, and embedded (DRE) and must operate under highly unpredictable and changeable conditions. A challenging problem for DRE systems is adaptation of behavior and reconfiguration of resources to maintain the best application performance in the face of changes in system load and available resources. To provide predictable mission-critical quality of service (QoS) end-to-end, QoS-enabled middleware services and mechanisms have begun to emerge, but they lack support for applications with stringent QoS requirements in changing, dynamic environments. This paper presents two contributions to research on adaptive and reconfigurable DRE systems. First, we describe the structure and functionality of an advanced middleware platform for developing applications that apply various techniques to adapt themselves to changes in resource availability to meet real-time QoS requirements. Second, we present results of a case study of a multimedia application for Unmanned Aerial Vehicle (UAV) video distribution we developed using this middleware platform in conjunction with QoS-enabledoperating systems and networking protocols. We describe the design of the multimedia application using our middleware platform and report empirical results showing how adaptive behavior and end-to-end resource management techniques are used to reconfigure the system dynamically to meet timeliness requirements. Copyright © 2006 John Wiley & Sons, Ltd.
32700814
Research Advances in Middleware for Distributed Systems
Apparatus for conditioning air of the constant volume type in which air gates are provided at the outlet ends of heat exchange passages and bypass passages to regulate the proportion of air passing through each of the pair of passages and therefore the temperature of air downstream from the air gates.
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.