Inference of static types for local variables in Java bytecode is the first step of any serious tool that manipulates bytecode, be it for decompilation, transformation or analysis. It is important, therefore, to perform that step as accurately and efficiently as possible. Previous work has sought to give solutions with good worst-case complexity.

Certain variants of object-oriented Datalog can be compiled to Datalog with negation. We seek to apply optimisations akin to virtual method resolution (a well-known technique in compiling Java and other OO languages) to improve efficiency of the resulting Datalog programs. The effectiveness of such optimisations strongly depends on the precision of the underlying type inference algorithm. Previous work on type inference for Datalog has focussed on Cartesian abstractions, where the type of each field is computed separately. Such Cartesian type inference is inherently imprecise in the presence of field equalities. We propose a type system where equalities are tracked, and present a type inference algorithm. The algorithm is proved sound. We also prove that it is optimal for Datalog without negation, in the sense that the inferred type is as tight as possible. Extensive experiments with our type-based optimisations, in a commercial implementation of object-oriented Datalog, confirm the benefits of this non-Cartesian type inference algorithm.

The magic-sets transformation is a useful technique for dramatically improving the performance of complex queries, but it has been observed that this transformation can also drastically reduce the performance of some queries. Successful implementations of magic in previous work require integration with the database optimiser to make appropriate decisions to guide the transformation (the sideways information passing strategy, or SIPS).

The analysis and verification of higher-order programs raises the issue of control-flow analysis for higher-order languages. The problem of constructing an accurate call graph for a higher-order program has been the topic of extensive research, and numerous methods for flow analysis, varying in complexity and precision, have been suggested.

In aspect-oriented programming, one can intercept events by writing patterns called pointcuts. The pointcut language of the most popular aspect-oriented programming language, AspectJ, allows the expression of highly complex properties of the static program structure.We present the first rigorous semantics of the AspectJ pointcut language, by translating static patterns into safe ( i.e. range-restricted and stratified) Datalog queries. Safe Datalog is a logic language like Prolog, but it does not have data structures; consequently it has a straightforward least fixpoint semantics and all queries terminate.The translation from pointcuts to safe Datalog consists of a set of simple conditional rewrite rules, implemented using the Stratego system. The resulting queries are themselves executable with the CodeQuest system. We present experiments indicating that direct execution of our semantics is not prohibitively expensive.

An aspect observes the execution of a base program; when certain actions occur, the aspect runs some extra code of its own. In the AspectJ language, the observations that an aspect can make are confined to the current action: it is not possible to directly observe the history of a computation.Recently, there have been several interesting proposals for new history-based language features, most notably by Douence et al. and by Walker and Viggers. In this paper, we present a new history-based language feature called tracematches that enables the programmer to trigger the execution of extra code by specifying a regular pattern of events in a computation trace. We have fully designed and implemented tracematches as a seamless extension of AspectJ.A key innovation in our tracematch approach is the introduction of free variables in the matching patterns. This enhancement enables a whole new class of applications in which events can be matched not only by the event kind, but also by the values associated with the free variables. We provide several examples of applications enabled by this feature.After introducing and motivating the idea of tracematches via examples, we present a detailed semantics of our language design, and we derive an implementation from that semantics. The implementation has been realised as an extension of the abc compiler for AspectJ.