Signatures: A language extension for improving type abstraction and subtype polymorphism in C++

C++ uses inheritance as a substitute for subtype polymorphism. We give examples where this makes the type system too inflexible. We then describe a conservative language extension that allows a programmer to define an abstract type hierarchy independent of any implementation hierarchies, to retroactively abstract over an implementation, and to decouple subtyping from inheritance. This extension gives the user more of the flexibility of dynamic typing while retaining the efficiency and security of static typing. With default implementations and views flexible mechanisms are provided for implementing an abstract type by different concrete class types. We first show how the language extension can be implemented in a preprocessor to a C++ compiler, and then detail and analyse the efficiency of an implementation we directly incorporated in the GNU C++ compiler.     

Implementation issues in optimization algorithms: do they matter?

Two factors that have a major impact on the performance of an optimization method are (1) formal algorithm specifications and (2) practical implementations. The impact of the latter is typically ignored, although it defines the results measured in experiments. We present an in-depth study of algorithm implementation issues and ask questions such as Does optimizing the implementation of an optimization algorithm pay off? Do bugs matter? and Is using more complicated but also more efficient data structures worth the effort? The intuitive answer to all of these questions is yes, but there is little published evidence. To bridge this gap, we use one of the most studied combinatorial optimization problems – the Traveling Salesman Problem – as a test bed and implement two state-of-the-art approaches for solving it – the Lin-Kernighan Heuristic and an Ejection Chain Method. We investigate implementation effort and performance gain, in order to provide further insights to the above questions.     

Transformation of SDF syntax definitions in the ASF+SDF Meta-Environment

We describe FST—a Framework for SDF Transformation. FST supports the adaptation (in a broad sense) of grammars based on the syntax definition formalism SDF. We further describe the prototype implementation of FST in the ASF+SDF Meta-Environment. Grammar transformations form an important concept of grammar reengineering, implementation, recovery and others. Tool support for grammar transformations is essential to automate the corresponding processes.     

The space complexity of unbounded timestamps

The timestamp problem captures a fundamental aspect of asynchronous distributed computing. It allows processes to label events throughout the system with timestamps that provide information about the real-time ordering of those events. We consider the space complexity of wait-free implementations of timestamps from shared read-write registers in a system of n processes. We prove an lower bound on the number of registers required. If the timestamps are elements of a nowhere dense set, for example the integers, we prove a stronger, and tight, lower bound of n. However, if timestamps are not from a nowhere dense set, this bound can be beaten: we give an implementation that uses n − 1 (single-writer) registers. We also consider the special case of anonymous implementations, where processes are programmed identically and do not have unique identifiers. In contrast to the general case, we prove anonymous timestamp implementations require n registers. We also give an implementation to prove that this lower bound is tight. This is the first anonymous timestamp implementation that uses a finite number of registers.     

The use of mTags for mandatory security: a case study

mTags is an efficient mechanism that augments inter‐thread messages with lightweight metadata. We introduce and discuss a case study that we have conducted in the use of mTags for realizing a kind of mandatory security. Although mTags can be implemented for any message passing thread‐based system, we consider an implementation of it in the POSIX‐compliant QNX Neutrino, a commercial microkernel‐based system. The approach to mandatory security that we adopt is Usable Mandatory Integrity Protection, which has been proposed in recent research. We call our adaptation of Usable Mandatory Integrity Protection using mTags, μMIP. We discuss the challenges we faced, and our design and implementation that overcomes these challenges. We discuss the performance of our implementation for well‐established benchmarks. We conclude with the observation that mTags can be useful and practical to realize mandatory security in realistic systems. Copyright © 2013 John Wiley & Sons, Ltd.     

Exact Minkowksi Sums of Polyhedra and Exact and Efficient Decomposition of Polyhedra into Convex Pieces

We present the first exact and robust implementation of the 3D Minkowski sum of two non-convex polyhedra. Our implementation decomposes the two polyhedra into convex pieces, performs pairwise Minkowski sums on the convex pieces, and constructs their union. We achieve exactness and the handling of all degeneracies by building upon 3D Nef polyhedra as provided by Cgal. The implementation also supports open and closed polyhedra. This allows the handling of degenerate scenarios like the tight passage problem in robot motion planning. The bottleneck of our approach is the union step. We address efficiency by optimizing this step by two means: we implement an efficient decomposition that yields a small number of convex pieces, and develop, test and optimize multiple strategies for uniting the partial sums by consecutive binary union operations. The decomposition that we implemented as part of the Minkowski sum is interesting in its own right. It is the first robust implementation of a decomposition of polyhedra into convex pieces that yields at most O(r ²) pieces, where r is the number of edges whose adjacent facets comprise an angle of more than 180 degrees with respect to the interior of the polyhedron. This work was partially supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.023.301.     

Automatic differentiation in C++ using expression templates and. application to a flow control problem

This work deals with an implementation of automatic differentiation of C++ computer programs in forward mode using operator overloading and expression templates. We report on the efficiency of such implementation and its obvious advantage : the ability to perform sensitivity analysis without touching the source of the computer program by simply adding a library to it. We apply this tool to a flow control problem : minimize the drag of a cylinder, in subsonic unsteady turbulent flow, by controlling the boundary condition of the cylinder. Received: 1 June 1999 / Accepted: 29 May 2000     

Area and Perimeter Computation of the Union of a Set of Iso-rectangles in Parallel

Finding the area and perimeter of the union/intersection of a set of iso-rectangles is a very important part of circuit extraction in VLSI design. We combine two techniques, the uniform grid and the vertex neighborhoods, to develop a new parallel algorithm for the area and perimeter problems which has an average linear time performance but is not worst-case optimal. The uniform grid technique has been used to generate the candidate vertices of the union or intersection of the rectangles. An efficient point-in-rectangles inclusion test filters the candidate set to obtain the relevant vertices of the union or intersection. Finally, the vertex neighborhood technique is used to compute the mass properties from these vertices. This algorithm has an average time complexity of O(((n + k)/p) + log p) where n is the number of input rectangle edges with k intersections on p processors assuming a PRAM model of computation. The analysis of the algorithm on a SIMD architecture is also presented. This algorithm requires very simple data structures which makes the implementation easy. We have implemented the algorithm on a Sun 4/280 workstation and a Connection Machine. The sequential implementation performs better than the optimal algorithm for large datasets. The parallel implementation on a Connection Machine CM-2 with 32K processors also shows good results.     

A formal and sound transformation from Focal to UML: an application to airport security regulations

We propose an automatic transformation of Focal specifications to UML class diagrams. The main motivation for this work lies within the framework of the EDEMOI project, which aims to integrate and apply several requirements engineering and formal methods techniques to analyze airport security regulations. The idea is to provide a graphical documentation of formal models for developers, and in the long-term, for certification authorities. The transformation is formally described and an implementation has been designed. We also show how the soundness of our approach can be achieved.     

Mechanical theorem proving in projective geometry

We present an algorithm that is able to confirm projective incidence statements by carrying out calculations in the ring of all formal determinants (brackets) of a configuration. We will describe an implementation of this prover and present a series of examples treated by the prover, includingPappus' andDesargues' theorems, thesixteen point theorem, Saam's theorem, thebundle condition, theuniqueness of a harmonic point andPascal's theorem.     

Constraint elimination method for the committee problem

We introduce a method of reducing the q-Member p-Committee Problem for an arbitrary finite system of sets to the same problem for a system of sets of smaller size and with a smaller number of subsystems with nonempty intersection maximal with respect to inclusion. For p = 1/2, for an infeasible system of linear inequalities in ℝ ⁿ we give an efficient implementation of this method with complexity polynomial in the number of inequalities and the number of committee elements, but exponential in the dimension of the space. For this implementation, we give experimental results for n = 2, 3.     

Rule-based agents for the semantic web

Artificial agents, subsuming both robots and software agents, represent a new paradigm in software engineering and artificial intelligence. Depending on the technologies used in their implementation, they may exhibit various skills; in particular, they may act more or less autonomously, they may be able to learn and to adapt to a changing environment, and they may be able to pursue their goals pro-actively. An artificial agent is called rule-based, if its behaviour and/or its knowledge is expressed by means of rules. In this paper, we discuss a general architecture for rule-based agents and how it can be realized with the help of semantic web languages. We also show how such agents can go live on the web by presenting an implementation in Mandarax, a Java rule platform. The concept and implementation are complemented by a running example, the portfolio agent.     

Efficient Rendering of Local Subsurface Scattering

A novel approach is presented to efficiently render local subsurface scattering effects. We introduce an importance sampling scheme for a practical subsurface scattering model. It leads to a simple and efficient rendering algorithm, which operates in image space, and which is even amenable for implementation on graphics hardware. We demonstrate the applicability of our technique to the problem of skin rendering, for which the subsurface transport of light typically remains local. Our implementation shows that plausible images can be rendered interactively using hardware acceleration.     

Deduction, Strategies, and Rewriting

Automated deduction methods should be specified not procedurally, but declaratively, as inference systems which are proved correct regardless of implementation details. Then, different algorithms to implement a given inference system should be specified as strategies to apply the inference rules. The inference rules themselves can be naturally specified as (possibly conditional) rewrite rules. Using a high-performance rewriting language implementation and a strategy language to guide rewriting computations, we can obtain in a modular way implementations of both the inference rules of automated deduction procedures and of algorithms controling their application. This paper presents the design of a strategy language for the Maude rewriting language that supports this modular decomposition: inference systems are specified in system modules, and strategies in strategy modules. We give a set-theoretic semantics for this strategy language, present its different combinators, illustrate its main ideas with several examples, and describe both a reflective prototype in Maude and an ongoing C++ implementation.     

Facetons: face primitives for building 3D architectural models in virtual environments

We present facetons, geometric modeling primitives designed for building architectural models especially effective for a virtual environment where six degrees of freedom input devices are available. A faceton is an oriented point floating in the air and defines a plane of infinite extent passing through the point. The polygonal mesh model is constructed by taking the intersection of the planes associated with the facetons. With the simple interaction of faceton, users can easily create 3D architecture models. The faceton primitive and its interaction reduce the overhead associated with standard polygonal mesh modeling, where users have to manually specify vertexes and edges which could be far away. The faceton representation is inspired by the research on boundary representations (B‐rep) and constructive solid geometry, but it is driven by a novel adaptive bounding algorithm and is specifically designed for 3D modeling activities in an immersive virtual environment. We describe the modeling method and our current implementation. The implementation is still experimental but shows potential as a viable alternative to traditional modeling methods. Copyright © 2014 John Wiley & Sons, Ltd.     

The Elmwood multiprocessor operating system

Elmwood is an object-oriented, multiprocessor operating system designed and implemented during a graduate seminar. It consists of a minimal kernel and a collection of user-implemented services. The kernel provides two major abstractions: objects, which consist of code and data, and processes, which represent asynchronous activity. Objects, like programs, are passive. To operate on an abstraction or to request a service, processes invoke an entry procedure defined by the corresponding object. Objects implement their own protection and synchronization policies using minimal kernel mechanisms. We describe the Elmwood kernel interface, an implementation on the BBN Butterfly parallel processor, and our experiences in developing a multiprocessor operating system under rigid time constraints. These experiences illustrate several general lessons regarding kernel design and trade-offs for implementation expedience.     

On the Complexity of Verifying Concurrent Transition Systems

In implementation verification, we check that an implementation is correct with respect to a specification by checking whether the behaviors of a transition system that models the program's implementation correlate with the behaviors of a transition system that models its specification. In this paper, we investigate the effect of concurrency on the complexity of implementation verification. We consider trace-based and tree-based approaches to the verification of concurrent transition systems, with and without fairness. Our results show that in almost all cases the complexity of the problem is exponentially harder than that of the sequential case. Thus, as in the model-checking verification methodology, the state-explosion problem cannot be avoided.     

Formal Verification of Out-of-Order Execution with Incremental Flushing

We present an approach for formally verifying that a high-level microprocessor model behaves as defined by an instruction-set architecture. The technique is based on a specialization of self consistency called incremental flushing and reduces the need and effort required to create manually-generated implementation abstractions. Additionally, incremental flushing reduces the computational complexity of the proof obligations generated when reasoning about out-of-order execution. This is accomplished by comparing the functional behavior of the implementation abstraction over two sets of inputs: one that represents normal operation and one that is simpler, but functionally equivalent. The approach is illustrated on a simple out-of-order microprocessor core.     

A Computational Framework for Practical Social Reasoning

This article describes a framework for practical social reasoning designed to be used for analysis, specification, and implementation of the social layer of agent reasoning in multiagent systems. Our framework, called the expectation strategy behavior (ESB) framework, is based on (i) using sets of update rules for social beliefs tied to observations (so‐called expectations), (ii) bounding the amount of reasoning to be performed over these rules by defining a reasoning strategy, and (iii) influencing the agent's decision‐making logic by means of behaviors conditioned on the truth status of current and future social beliefs. We introduce the foundations of ESB conceptually and present a formal framework and an actual implementation of a reasoning engine, which is specifically combined with a general (belief–desire–intention‐based) practical reasoning programming system. We illustrate the generality of ESB through select case studies, which show that it is able to represent and implement different typical styles of social reasoning. The broad coverage of existing social reasoning methods, the modularity that derives from its declarative nature, and its focus on practical implementation make ESB a useful tool for building advanced socially reasoning agents.