Double dispatch in C++

Double dispatch is the ability to dynamically select a method not only according to the run‐time type of the receiver (single dispatch), but also according to the run‐time type of the argument. This mechanism unleashes the power of dynamic binding in object‐oriented languages, so enhancing re‐usability and separation of responsibilities. However, many mainstream languages, such as, e.g., C++ and Java, do not provide it, resorting only to single dispatch. In this paper we propose an extension of C++ (also applicable to other object‐oriented languages) that enables double dispatch as a language feature. This yields dynamic overloading and covariant specialization of methods. We define a translation from the new constructs to standard C++ and we present the preprocessor implementing this translation, called doublecpp . The translated code enjoys static type safety and implements the semantics of double dispatch by using only standard mechanisms of static overloading and dynamic binding, with minimal impact on the performance of the program. Copyright © 2006 John Wiley & Sons, Ltd.     

@Java: Bringing a richer annotation model to Java

The ability to annotate code and, in general, the capability to attach arbitrary meta-data to portions of a program are features that have become more and more common in programming languages.Annotations in Java make it possible to attach custom, structured meta-data to declarations of classes, fields and methods. However, the mechanism has some limits: annotations can only decorate declarations and their instantiation can only be resolved statically.With this work, we propose an extension to Java (named @Java) with a richer annotation model, supporting code block and expression annotations, as well as dynamically evaluated members. In other words, in our model, the granularity of annotations extends to the statement and expression level and annotations may hold the result of runtime-evaluated expressions.Our extension to the Java annotation model is twofold: (i) we introduced block and expression annotations and (ii) we allow every annotation to hold dynamically evaluated values. Our implementation also provides an extended reflection API to support inspection and retrieval of our enhanced annotations.     

Translating Double Dispatch into Single Dispatch

Goals of flexibility and re-usability in typed object-oriented languages suggest the requirement of double dispatch, i.e., the mechanism of dynamically selecting a method not only according to the run-time type of the receiver (single dispatch), but also to the run-time type of the argument. However, many mainstream languages, such as, e.g., C++ and Java, do not provide it, resorting to only single dispatch. In this paper we present a general technique for adding double dispatch as a type-safe language feature, so yielding dynamic overloading and covariant specialization of methods, without extending basic semantics. To this aim we introduce a toy core language, extended to a full form of (non encapsulated) multi methods. Then we define a translation algorithm from multi methods to the core language, that implements double dispatch by using only standard mechanisms of static overloading and single dispatch. As a main feature, our translation preserves type safety, it uses neither RTTI nor type downcasts and does not introduce crucial overhead during method selection.     

Delegation by object composition

Class inheritance and method overriding, as provided by standard class-based languages, are often not flexible enough to represent objects with some dynamic behavior. In this respect, object composition equipped with different forms of method body lookup is often advocated as a more flexible alternative to class inheritance since it takes place at run time, thus permitting the behavior of objects to be specialized dynamically. In this paper, we illustrate Incomplete Featherweight Java (IFJ), an extension of Featherweight Java with a novel linguistic construct, the incomplete object. Incomplete objects require some missing methods which can be provided at run time by composition with another (complete) object. Furthermore, we present two mechanisms for the method body lookup on (composed) objects, one based on delegation and the other based on consultation. Thanks to the design of the language, the consultation-based lookup is a simple extension of the delegation-based one. Both mechanisms are disciplined by static typing, therefore the language enjoys type safety (which implies no “message-not-understood” run-time errors) and avoids possible accidental overrides due to method name clashes.     

Static analysis of XML transformations in Java

XML documents generated dynamically by programs are typically represented as text strings or DOM trees. This is a low-level approach for several reasons: 1) traversing and modifying such structures can be tedious and error prone, 2) although schema languages, e.g., DTD, allow classes of XML documents to be defined, there are generally no automatic mechanisms for statically checking that a program transforms from one class to another as intended. We introduce XACT, a high-level approach for Java using XML templates as a first-class data type with operations for manipulating XML values based on XPath. In addition to an efficient runtime representation, the data type permits static type checking using DTD schemas as types. By specifying schemes for the input and output of a program, our analysis algorithm will statically verify that valid input data is always transformed into valid output data and that the operations are used consistently.     

Types and trace effects for object orientation

Trace effects are statically generated program abstractions, that can be model checked for verification of assertions in a temporal program logic. In this paper we develop a type and effect analysis for obtaining trace effects of Object Oriented programs in Featherweight Java. We observe that the analysis is significantly complicated by the interaction of trace behavior with inheritance and other Object Oriented features, particularly overridden methods, dynamic dispatch, and downcasting. We propose an expressive type and effect inference algorithm combining polymorphism and subtyping/subeffecting constraints to obtain a flexible trace effect analysis in this setting, and show how these techniques are applicable to Object Oriented features. We also extend the basic language model with exceptions and stack-based event contexts, and show how trace effects scale to these extensions by structural transformations.     

Static semantics, types, and binding time analysis

Part 1 of this paper is an analysis of problems concerning type systems and static semantics relevant to designing and implementing new programming languages. Part 2 proposes and exemplifies a way to derive a static semantics from a language's dynamic semantics, using a technique known as binding time analysis known from partial evaluation (Ershov's “mixed computation”) [20, 21]. The goal is to analyze the language's type structure during the design process without the need for hand construction of a type system. Ideally, one might automate the construction of a type checker, given only the dynamic semantics as input. In particular, binding time analysis of the interpreter program can be used to distinguish statically detectable errors from dynamic ones, and a static semantics is seen as a mechanism for deciding whether the program to be interpreted can give rise to any of the static errors. Our basic viewpoint is operational: to see how and where in the interpreter immediately observable type errors manifest themselves; to classify them as static or dynamic; and to design the static semantics to detect all static errors in a given program.     

Statically safe program generation with SafeGen

SafeGen is a meta-programming language for writing statically safe generators of Java programs. If a program generator written in SafeGen passes the checks of the SafeGen compiler, then the generator will only generate well-formed Java programs, for any generator input. In other words, statically checking the generator guarantees the correctness of any generated program, with respect to static checks commonly performed by a conventional compiler (including type safety, existence of a superclass, etc.). To achieve this guarantee, SafeGen supports only language primitives for reflection over an existing well-formed Java program, primitives for creating program fragments, and a restricted set of constructs for iteration, conditional actions, and name generation. SafeGen’s static checking algorithm is a combination of traditional type checking for Java, and a series of calls to a theorem prover to check the validity of first-order logical sentences, constructed to represent well-formedness properties of the generated program under all inputs. The approach has worked quite well in our tests, providing proofs for correct generators or pointing out interesting bugs.     

Static verification of dynamically detected program invariants: Integrating Daikon and ESC/Java

This paper shows how to integrate two complementary techniques for manipulating program invariants: dynamic detection and static verification. Dynamic detection proposes likely invariants based on program executions, but the resulting properties are not guaranteed to be true over all possible executions. Static verification checks that properties are always true, but it can be difficult and tedious to select a goal and to annotate programs for input to a static checker. Combining these techniques overcomes the weaknesses of each: dynamically detected invariants can annotate a program or provide goals for static verification, and static verification can confirm properties proposed by a dynamic tool.We have integrated a tool for dynamically detecting likely program invariants, Daikon, with a tool for statically verifying program properties, ESC/Java. Daikon examines run-time values of program variables; it looks for patterns and relationships in those values, and it reports properties that are never falsified during test runs and that satisfy certain other conditions, such as being statistically justified. ESC/Java takes as input a Java program annotated with preconditions, postconditions, and other assertions, and it reports which annotations cannot be statically verified and also warns of potential runtime errors, such as null dereferences and out-of-bounds array indices.Our prototype system runs Daikon, inserts its output into code as ESC/Java annotations, and then runs ESC/Java, which reports unverifiable annotations. The entire process is completely automatic, though users may provide guidance in order to improve results if desired. In preliminary experiments, ESC/Java verified all or most of the invariants proposed by Daikon.     

The monadic second-order logic of graphs IX: Machines and their behaviours

We establish that every monadic second-order property of the behaviour of a machine (transition systems and tree automata are typical examples of machines) is a monadic second-order property of the machine itself. In this way, we clarify the distinction between “dynamic” properties of machines (i.e., properties of their behaviours), and their “static” properties (i.e., properties of the graphs or relational structures representing them). It is important for program verification that the dynamic properties that one wants to verify can be formulated statically, in the simplest possible way. As a corollary of our main result, we also obtain that the monadic theory of an algebraic tree is decidable.     

基于FJ的多版本类动态更新演算

针对面向对象软件在动态更新中遇到类型安全问题,定义了一个多版本类的动态更新演算(MCUFJ演算(multi-version class dynamic updamble calculus based on FJ calculus))来描述类动态更新.MCUFJ演算以FJ(featherweight Java)演算为核心,通过增加update操作表示类的动态更新,运用多版本技术使动态更新可以在保持新旧对象共存的情况下完成,讨论了类的数据域和方法进行增加、删除、修改以及类型变化对程序类型安全性的影响,并且指出MCUFJ上类型安全的动态更新需要满足的约束.定义了类的可动态更新限制,并且证明了在该条件下多版本类的动态更新在类型上的安全性.该演算可以用于指导Java语言和面向对象程序语言的类动态更新.     

A type system for static and dynamic checking of C++ pointers

Object-oriented programming is the most used programming paradigm when dealing with large-scale, modular software. In this field, the two leading languages are Java and C++. The former has superior qualities in terms of safety and ease of programming, whereas the latter is often considered an “old” language, too complex and potentially unsafe.In this paper, we describe a new type system designed to analyze the security problems derived from pointer manipulation in C++. This type system tries to trap the most common errors through static analysis, i.e., at compile-time, and only when static analysis fails it generates and embeds code fragments that apply runtime checks on specific instructions. The aim of this new type system is to give C++ the same safety of Java in the most important memory-related operations, without adding much runtime overhead. An experimental implementation of the type system is also presented, embedded in a C++ analysis tool called GPCC.     

Static type information to improve the IDE features of hybrid dynamically and statically typed languages

The flexibility offered by dynamically typed programming languages has been appropriately used to develop specific scenarios where dynamic adaptability is an important issue. This has made some existing statically typed languages gradually incorporate more dynamic features to their implementations. As a result, there are some programming languages considered hybrid dynamically and statically typed. However, these languages do not perform static type inference on a dynamically typed code, lacking those common features provided when a statically typed code is used. This lack is also present in the corresponding IDEs that, when a dynamically typed code is used, do not provide the services offered for static typing. We have customized an IDE for a hybrid language that statically infers type information of dynamically typed code. By using this type information, we show how the IDE can provide a set of appealing services that the existing approaches do not support, such as compile-time type error detection, code completion, transition from dynamically to statically typed code (and vice versa), and significant runtime performance optimizations. We have evaluated the programmer׳s performance improvement obtained with our IDE, and compared it with similar approaches.     

在静态编译器中实现Java异常机制的算法

将Java程序静态编译成可执行程序是使用Java虚拟机动态编译／解释执行Java程序的另一种运行Java程序的方式。针对Java异常机制的特点和静态编译的需求,在介绍Java异常处理逻辑的基础上,提出一种在静态编译器中实现Java异常机制的算法,结合Open64开源编译器,给出该算法的具体步骤以及实现方式,以SPECjvm98为测试集,验证该算法的有效性。     

Complexity of points-to analysis of Java in the presence ofexceptions

At each program point, points-to analysis for statically typed object oriented programming languages (e.g., Java, C++) determines those objects to which a reference may refer (or a pointer may point) during execution. Points-to analysis is necessary for any semantics based software tools for object oriented systems. Our new complexity results for points-to analysis distinguish the difficulty of intraprocedural and interprocedural points-to analyses for languages with combinations of single-level types (i.e., types with data members only of primitive type), exceptions with or without subtyping, and dynamic dispatch. Our results include: 1) the first polynomial-time algorithm for points-to analysis in the presence of exceptions that handles a robust subset of Java without threads and can be applied to C++; 2) proof that the above algorithm is safe, in general, and provably precise on programs with single-level types and exceptions without subtyping, but not dynamic dispatch, thus, this case is in P; 3) proof that an interprocedural points-to analysis problem with single-level types and exceptions with subtyping, but without dynamic dispatch, is PSPACE-hard, while the intraprocedural problem is PSPACE-complete. Other complexity characterizations of points-to analysis in programs without exceptions are presented, including an algorithm with worst-case bound of O(n⁵ ), which improves over the O(n⁷) worst-case bound achievable from previous approaches of T. Reps et al. (1995) and W.A. Landi and B.G. Ryder (1991)     

Safe locking for multi-threaded Java with exceptions

There are many mechanisms for concurrency control in high-level programming languages. In Java, the original mechanism for concurrency control, based on synchronized blocks, is lexically scoped. For more flexible control, Java 5 introduced non-lexical lock primitives on re-entrant locks.These operators may lead to run-time errors and unwanted behavior; e.g., taking a lock without releasing it, which could lead to a deadlock, or trying to release a lock without owning it. This paper develops a static type and effect system to prevent the mentioned lock errors for a formal, object-oriented calculus which supports non-lexical lock handling and exceptions.Based on an operational semantics, we prove soundness of the effect type analysis. Challenges in the design of the effect type system are dynamic creation of threads, objects, and especially of locks, aliasing of lock references, passing of lock references between threads, and reentrant locks as found in Java. Furthermore, the exception handling mechanism complicates the control-flow and thus the analysis.     

Static vulnerability detection in Java service-oriented components

Extensible component-based platforms allow dynamic discovery, installation and execution of components. Such platforms are service-oriented, as components may directly interact with each other via the services they provide. Even robust languages such as Java were not designed to handle safe code interaction between trusted and untrusted parties. Dynamic installation of code provided by different third parties leads to several security issues. The different security layers adopted by Java or component-based platforms cannot fully address the problem of untrusted components trying to tamper with other components via legitimate interactions. A malicious component might even use vulnerable ones to compromise the whole component-based platform. Our approach identifies vulnerable components in order to prevent them from threatening services security. We use static analysis to remain as exhaustive as possible and to avoid the need for non-standard or intrusive environments. We show that a static analysis through tainted object propagation is well suited to detect vulnerabilities in Java service-oriented components. We present STOP, a Service-oriented Tainted Object Propagation tool, which applies this technique to statically detect those security flaws. Finally, the audit of several trusted Apache Felix bundles shows that nowadays component-based platforms are not prepared for malicious Java interactions.     

Improving static resolution of dynamic class loading in Java using dynamically gathered environment information

In Java software, one important flexibility mechanism is dynamic class loading. Unfortunately, the vast majority of static analyses for Java treat dynamic class loading either unsoundly or too conservatively. We present a novel semi-static approach for resolving dynamic class loading by combining static string analysis with dynamically gathered information about the execution environment. The insight behind the approach is that dynamic class loading often depends on characteristics of the environment that are encoded in various environment variables. Such variables are not static elements; however, their run-time values typically remain the same across multiple executions of the application. Thus, the string values reported by our technique are tailored to the current installation of the system under analysis. Additionally, we propose extensions of string analysis to increase the number of sites that can be resolved purely statically, and to track the names of environment variables. An experimental evaluation on the Java 1.4 standard libraries shows that a state-of-the-art purely static approach resolves only 28% of non-trivial sites, while our approach resolves 74% of such sites. We also demonstrate how the information gained from resolved dynamic class loading can be used to determine the classes that can potentially be instantiated through the use of reflection. Our extensions of string analysis greatly increase the number of resolvable reflective instantiation sites. This work is a step towards making static analysis tools better equipped to handle the dynamic features of Java. This material is based upon work supported by the National Science Foundation under CAREER grant CCF-0546040.     

Annotation inference for modular checkers

This paper presents a general approach to annotation inference for a given static program checker. The approach reuses the checker as a subroutine. The approach has been used to implement annotation inference systems for two static program checkers, ESC/Java and rccjava. The paper describes the approach formally and shows how it applies to ESC.