Effective and Efficient Compilation of Run-Time Generics in Java

After several years from Sun Microsystems' call-for-proposals for adding generics to the Java Programming Language, JDK 1.5 will be finally shipped with a compile-time support for generics. However, differently e.g. from the current implementation of .NET Common Language Runtime, run-time support to generics — also commonly referred to as reification of type parameters — is not provided, leading to a number of well-known inadequacies which might potentially be critical. In this paper we present the EGO compiler (Exact Generics on Demand). This is the result of a project developed in collaboration with Sun Microsystems as an effort to provide run-time generics in a smooth way, without requiring any change on the JVM or on any other run-time support. The core solution is a sophisticated translation of code based on the type-passing style, where run-time type information is automatically created on a by-need basis, limiting as most as possible run-time overhead while retaining interoperability with legacy Java code.We present the main aspects of this development, from basic design to implementation and deployment issues. Many relevant aspects that typical raise when implementing advanced type systems over a mainstream programming language are discussed, shading light to some effective implementation techniques.     

The Java 5 generics compromise orthogonality to keep compatibility

In response to a long-lasting anticipation by the Java community, version 1.5 of the Java 2 platform - referred to as Java 5 - introduced generic types and methods to the Java language. The Java 5 generics are a significant enhancement to the language expressivity because they allow straightforward composition of new generic classes from existing ones while reducing the need for a plethora of type casts. While the Java 5 generics are expressive, the chosen implementation method, type erasure, has triggered undesirable orthogonality violations. This paper identifies six cases of orthogonality violations in the Java 5 generics and demonstrates how these violations are mandated by the use of type erasure. The paper also compares the Java 5 cases of orthogonality violations to compatible cases in C# 2 and NextGen 2 and analyzes the tradeoffs in the three approaches. The conclusion is that Java 5 users face new challenges: a number of generic type expressions are forbidden, while others that are allowed are left unchecked by the compiler.     

Adoption and use of Java generics

Support for generic programming was added to the Java language in 2004, representing perhaps the most significant change to one of the most widely used programming languages today. Researchers and language designers anticipated this addition would relieve many long-standing problems plaguing developers, but surprisingly, no one has yet measured how generics have been adopted and used in practice. In this paper, we report on the first empirical investigation into how Java generics have been integrated into open source software by automatically mining the history of 40 popular open source Java programs, traversing more than 650 million lines of code in the process. We evaluate five hypotheses and research questions about how Java developers use generics. For example, our results suggest that generics sometimes reduce the number of type casts and that generics are usually adopted by a single champion in a project, rather than all committers. We also offer insights into why some features may be adopted sooner and others features may be held back.     

A type-safe embedding of SQL into Java using the extensible compiler framework J%

J% is an extension of the Java programming language that efficiently supports the integration of domain-specific languages. In particular, J% allows the embedding of domain-specific language code into Java programs in a syntax-checked and type-safe manner. This paper presents J%׳s support for the sql language. J% checks the syntax and semantics of sql statements at compile-time. It supports query validation against a database schema or through execution to a live database server. The J% compiler generates code that uses standard jdbc api calls, enhancing runtime efficiency and security against sql injection attacks.     

A prolog constraint handling rules compiler and runtime system

The most recent and advanced implementation of constraint handling rules (CHR) is introduced in a logic programming language. The Prolog implementation consists of a runtime system and a compiler. The runtime system utilizes attributed variables for the realization of the constraint store with efficient retrieval and update mechanisms. Rules describing the interactions between constraints are compiled into Prolog clauses by a compiler, the core of which comprises a small number of compact code generating templates in the form of definite clause grammar rules.     

Generic operations and capabilities in the JR concurrent programming language

The JR concurrent programming language extends Java with additional concurrency mechanisms, which are built upon JR's operations and capabilities. JR operations generalize methods in how they can be invoked and serviced. JR capabilities act as reference to operations. Recent changes to the Java language and implementation, especially generics, necessitated corresponding changes to the JR language and implementation. This paper describes the new JR language features (known as JR2) of generic operations and generic capabilities. These new features posed some interesting implementation challenges. The paper describes our initial implementation (JR21) of generic operations and capabilities, which works in many, but not all, cases. It then describes the approach our improved implementation (JR24) uses to fully implement generic operations and capabilities. The paper also describes the benchmarks used to assess the compilation and execution time performances of JR21 and JR24. The JR24 implementation reduces compilation times, mainly due to reducing the number of files generated during JR program translation, without noticeably impacting execution times.     

A Design for Type-Directed Programming in Java

Type-directed programming is an important and widely used paradigm in the design of software. With this form of programming, an application may analyze type information to determine its behavior. By analyzing the structure of data, many operations, such as serialization, cloning, adaptors and iterators may be defined once, for all types of data. That way, as the program evolves, these operations need not be updated—they will automatically adapt to new data forms. Otherwise, each of these operations must be individually redefined for each type of data, forcing programmers to revisit the same program logic many times during a program's lifetime.The Java language supports type directed programming with the instanceof operator and the Java Reflection API. These mechanisms allow Java programs to depend on the name and structure of the run-time classes of objects. However, the Java mechanisms for type-directed programming are difficult to use. They also do not integrate well with generics, an important new feature of the Java language.In this paper, we describe the design of several expressive new mechanisms for type-directed programming in Java, and show that these mechanisms are sound when included in a language similar to Featherweight Java. Basically, these new mechanisms pattern-match the name and structure of the type parameters of generic code, instead of the run-time classes of objects. Therefore, they naturally integrate with generics and provide strong guarantees about program correctness. As these mechanisms are based on pattern matching, they naturally and succinctly express many operations that depend on type information. Finally, they provide programmers with some degree of protection for their abstractions. Whereas instanceof and reflection can determine the exact run-time type of an object, our mechanisms allow any supertype to be supplied for analysis, hiding its precise structure.     

Optimizing Java: theory and practice

The enormous popularity of the Internet has made an instant star of the Java programming language. Java's portability, reusability, security and clean design has made it the language of choice for Web-based applications and a popular alternative to C++ for object-oriented programming. Unfortunately, the performance of the standard Java implementation, even with just-in-time compilation technology, is far behind the most popular languages today. The need for an aggressive optimizing compiler for Java is clear. Building on preliminary experience with the JavaSoft bytecode optimizer, this paper explores some of the issues that arise in building efficient implementations of Java. A number of interesting problems are presented by the Java language design, making classical optimization strategies much harder to implement. On the other hand, Java presents the opportunity for some new optimizations, unique for this language. © 1997 John Wiley & Sons, Ltd.     

The Hydra Parallel Programming System

The Hydra Parallel Programming System, a new parallel language extension to Java, and its supporting software are described. It is a fairly simple yet powerful language designed to address a number of areas that have not received much attention. One of these areas is the recompilation of parallel programs at runtime to allow a parallel program to adapt to the architecture it is executing on. The first version of this software system focuses on smaller Symmetric Multiprocessing and compatible architectures which are becoming more common. This particular class of machines has a great need for more options in the area of parallel programming among the vastly popular Java language programmers. Hydra programs will run as sequential Java on machines that do not have the parallel support or do not have an implemented Hydra runtime system without requirement of any modifications to the program. This paper describes the language, compares it with other languages (specifically with JOMP, an OpenMP implementation for Java), presents a brief discussion on compiling and executing Hydra programs, presents some sample benchmarks and their performance on three platforms, and concludes with a discussion of issues and future directions for Hydra. Copyright © 2007 John Wiley & Sons, Ltd.     

基于Java的泛型编程

泛型编程是面向对象的进一步发展,从更高的角度对世界进行抽象,为面向对象的不足之处提供了解决之道.它可让你重复运用既有的算法,而不必在环境类似的情况下再重新撰写相同代码,使得处理的问题更加抽象化,是一种优美而又不失效率的通用型程序设计方法.JDK 1.5中引入了对Java语言的多种扩展,泛型(generics)即其中之一.本文讨论JDK 1.5的泛型实现.     

基于Java的编译原理课程案例教学方法初探

针对编译原理教学实际,在分析和修改工业级开源编译器实现代码的基础上,提出一个基于Java的编译原理课程案例教学过程,结合Java这种日益普及的面向对象程序设计语言,这种教学过程在编译原理课程教学方面取得良好效果。     

Java supervenience

This paper reports on the development of a language construct designed to solve certain problems in composability at the level of object-oriented programming languages. Features were chosen to investigate how much compositional functionality could be added to core Java with as small a change as possible and in an additive manner. A fairly elegant and effective syntax on core Java resulted in reducing the clutter of the "mechanics" of composition. This construct features eliminating runtime cast and null exceptions within the construct, and the option of parametric covariant override. It does so while avoiding undesirable restrictions or new frameworks. Recently, new techniques intended to improve the composability of software components in the Java ecosystem have been vigorously pursued. Proposals take on the objectives of composition in largescale systems and enterprise applications but often implement on conventional object-oriented languages which face the same kinds of problems from the ground up. Benefitting from those experiences, the present work seeks to provide core Java-level solutions to problems that are analogous to those at the higher-levels. The supervenience construct described in this paper is based on a well-established formulation for composing a relationship over classes with some common behavioral elements, their behavioral intersection. The narrow concern of this construct is the sound composition of components across class families while eliminating certain barriers to runtime type-safety in core Java. The supervenience construct has been applied to certain classic problems and key case studies in composability and extensibility which represent fundamental issues that emerge at every level. The implementation requires no installed runtime frameworks and no changes to the JVM or type system of core Java. It is designed to deploy stand-alone or later integrate with the standard Java compiler and IDEs. The continuing research is now focusing on a more formal proof of its type-safety, applying the reference implementation to mid-scale and distributed applications.     

Accurate garbage collection in uncooperative environments revisited

Implementing a concurrent programming language such as Java by means of a translator to an existing language is attractive as it provides portability over all platforms supported by the host language and reduces development time—as many low‐level tasks can be delegated to the host compiler. The C and C++ programming languages are popular choices for many language implementations due to the availability of efficient compilers on a wide range of platforms. For garbage‐collected languages, however, they are not a perfect match as no support is provided for accurately discovering pointers to heap‐allocated data on thread stacks. We evaluate several previously published techniques and propose a new mechanism, lazy pointer stacks, for performing accurate garbage collection in such uncooperative environments. We implemented the new technique in the Ovm Java virtual machine with our own Java‐to‐C/C++ compiler using GCC as a back‐end compiler. Our extensive experimental results confirm that lazy pointer stacks outperform existing approaches: we provide a speedup of 4.5% over Henderson's accurate collector with a 17% increase in code size. Accurate collection is essential in the context of real‐time systems, we thus validate our approach with the implementation of a real‐time concurrent garbage collection algorithm. Copyright © 2009 John Wiley & Sons, Ltd.     

Name analysis for modern languages: a general solution

Classical strategies for matching identifier uses with declarations cannot handle the complexities of modern languages: arbitrarily qualified superclass names, cyclic dependence among lookup operations, and contextual access constraints. We have developed a language‐independent algorithm and supporting data structure that overcome these problems. A well‐defined interface allows introduction of arbitrary code to enforce language‐specific constraints within the basic lookup operations. This paper explains the limitations of the classical strategies, presents the concepts on which our approach is based, and showcases an implementation based on attribute grammars. We explore the major issues through a series of examples and show how one can deal with those issues in a general framework. Many of the issues are specific to a particular language, and in those cases, we explain the solutions that our general interface supports. Although attribute grammars simplify the task of incorporating the model into a compiler, the model itself is completely independent of attribute grammars. We validated our model by using an implementation to process programs in several representative languages. In particular, we mechanically compared the results produced by that implementation with those produced by the Java SE 8 compiler on complete Java programs that are in general use. Performance data obtained during this processing show that our implementation is efficient. Copyright © 2017 John Wiley & Sons, Ltd.     

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.     

嵌入式Java编译器的研究与设计

提出用编译的方法设计一款能直接生成 MCS-51系列单片机的目标代码,不依赖操作系统和JVM的嵌入式Ja-va编译器,使得Java语言在低档嵌入式系统中应用更加广泛,实现成本低廉的工业环境及家庭电器与 Internet 相结合实现远程监测和控制.详细分析了Java语言与嵌入式系统的特点,以实时版jRate及 sun公司的GJC编译系统为参考,采用单遍扫描语法制导翻译模式,以语法分析程序单元为核心,构建嵌入式Java 编译器的词法分析器、语法/语义分析器和代码生成器,并对测试方法进行了探讨.     

XQuery语言Hotspot编译系统的支撑框架

设计并实现XQuery语言Hotspot编译系统的支撑框架,通过对XQuery程序进行Hotspot分析,将执行频率高的程序模块编译为Java字节码,以提高程序执行效率。实验结果证明,Hotspot编译系统在执行效率上相比解释系统有一定提高,与静态编译系统相比,能更有效地处理网络上动态生成的XQuery查询。