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.
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.
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.
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:
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.
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.
11623434
Evaluating real-time Java features and performance for real-time embedded systems
This paper provides two contributions to the study of programming languages and middleware for real-time and embedded applications. First, we present the empirical results from applying the RTJPerf benchmarking suite to evaluate the efficiency and predictability of several implementations of the real-time specification for Java (RTSJ). Second, we describe some of the techniques used to develop jRate, which is an open-source ahead-of-time-compiled implementation of RTSJ we are developing. Our results indicate that RTSJ implementations are maturing to the point where they can be applied to a variety of real-time embedded applications.
14279635
Techniques for enhancing real-time CORBA quality of service
End-to-end predictability of remote operations is essential for many fixed-priority distributed real-time and embedded (DRE) applications, such as command and control systems, manufacturing process control systems, large-scale distributed interactive simulations, and testbeam data acquisition systems. To enhance predictability, the Real-time CORBA specification defines standard middleware features that allow applications to allocate, schedule, and control key CPU, memory, and networking resources necessary to ensure end-to-end quality of service support. This paper provides two contributions to the study of Real-time CORBA middleware for DRE applications. First, we identify potential problems with ensuring predictable behavior in conventional middleware by examining the end-to-end critical code path of a remote invocation and identifying sources of unbounded priority inversions. Experimental results then illustrate how the problems we identify can yield unpredictable behavior in conventional middleware platforms. Second, we present design techniques for ensuring real-time quality of service in middleware. We show how middleware can be redesigned to use nonmultiplexed resources to eliminate sources of unbounded priority inversion. The empirical results in this paper are conducted using TAO, which is widely used and open-source DRE middleware compliant with the Real-time CORBA specification.
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.
1160729
Applying model intelligence frameworks for deployment problem in real-time and embedded systems
There are many application domains, such as distributed real-time and embedded (DRE) systems, where the domain constraints are so restrictive and the solution spaces so large that it is infeasible for modelers to produce correct solution manually using a conventional graphical model-based approach. In DRE systems the available resources, such as memory, CPU, and bandwidth, must be managed carefully to ensure a certain level of quality of service. This paper provides three contributions to simplify modeling of complex application domains: (1) we present our approach of combining model intelligence and domain-specific solvers with model-driven engineering (MDE) environments, (2) we show techniques for automatically guiding modelers to correct solutions and how to support the specification of large and complex systems using intelligent mechanisms to complete partially specified models, and (3) we present the results of applying an MDE tool that maps software components to Electronic Control Units (ECUs) using the typical automotive modeling and middleware infrastructure.
398642
Supporting high‐performance I/O in QoS‐enabled ORB middleware
To be an effective platform for high‐performance distributed applications, off-the-shelf Object Request Broker (ORB) middleware, such as CORBA, must preserve communication-layer quality of service (QoS) properties both vertically (i.e., network interface ↔ application layer) and horizontally (i.e., end-to-end). However, conventional network interfaces, I/O subsystems, and middleware interoperability protocols are not well-suited for applications that possess stringent throughput, latency, and jitter requirements. It is essential, therefore, to develop vertically and horizontally integrated ORB endsystems that can be (1) configured flexibly to support high-performance network interfaces and I/O subsystems and (2) used transparently by performance-sensitive applications. This paper provides three contributions to research on high-performance I/O support for QoS-enabled ORB middleware. First, we outline the key research challenges faced by high-performance ORB endsystem developers. Second, we describe how our real-time I/O (RIO) subsystem and pluggable protocol framework enables ORB endsystems to preserve high-performance network interface QoS up to applications running on off-the-shelf hardware and software. Third, we illustrate empirically how highly optimized ORB middleware can be integrated with real-time I/O subsystem to reduce latency bounds on communication between high-priority clients without unduly penalizing low-priority and best-effort clients. Our results demonstrate how it is possible to develop ORB endsystems that are both highly flexible and highly efficient.