Search

Expandable collections are collections whose size may vary as elements are added and removed. Hash maps and ordered collections are popular expandable collections. Expandable collection classes offer an easy-to-use API, however this apparent simplicity is accompanied by a significant amount of wasted resources. We describe some improvements of the collection library to reduce the amount of waste associated with collection expansions. We have designed two new collection libraries for the Pharo programming language that exhibit better resource management than the standard library. We improved the Pharo collection library using two complementary perspectives. First, across a basket of 5 applications, our optimized collection library significantly reduces the memory footprint of the collections: (i) the amount of intermediary internal array storage by 73%, (ii) the number of allocated bytes by 67% and (iii) the number of unused bytes by 72%. This reduction of memory is accompanied by a speedup of about 3% for most of our benchmarks. Second, we looked for an alternative to the classical expandable collection. The Lua programming language offers a unique abstract data type called table. We designed, implemented, and introduced this data type in the Pharo programming language and we ran a number of micro and macro-benchmarks. Overall, replacing the standard Pharo collection library by one inspired on Lua's table data type results in an execution speedup of up to 15% and a reduction of the memory consumption by up to 19%. We analyzed the collection implementations of Java, C#, Scala, and Ruby: these implementations largely behave like Pharo's, therefore with the same limitations. Our results are thus likely to benefit designers of future programming languages and collection libraries.

Much recent work on type-safe extensibility for Object-Oriented languages has focused on design patterns that require modest type system features. Examples of such design patterns include Object Algebras, Extensible Visitors, Finally Tagless interpreters, or Polymorphic Embeddings. Those techniques, which often use a functional style, can solve basic forms of the Expression Problem. However, they have important limitations. This paper presents Castor : a Scala framework for programming with extensible, generative visitors. Castor has several advantages over previous approaches. Firstly, Castor comes with support for (type-safe) pattern matching to complement its visitors with a concise notation to express operations. Secondly, Castor supports type-safe interpreters (a la Finally Tagless), but with additional support for pattern matching and a generally recursive style. Thirdly, Castor enables many operations to be defined using an imperative style, which is significantly more performant than a functional style (especially in the JVM platform). Finally, functional techniques usually only support tree structures well, but graph structures are poorly supported. Castor supports type-safe extensible programming on graph structures. The key to Castor 's usability is the use of annotations to automatically generate large amounts of boilerplate code to simplify programming with extensible visitors. To illustrate the applicability of Castor we present several applications and two case studies. The first case study compares the ability of Castor for modularizing the interpreters from the “Types and Programming Languages” book with previous modularization work. The second case study on UML activity diagrams illustrates the imperative aspects of Castor , as well as its support for hierarchical datatypes and graphs.

The Kiama language processing library is a collection of domain-specific languages for software language processing embedded in the Scala programming language. The standard Scala parsing library is augmented by Kiama's facilities for defining attribute grammars, strategy-based rewriting rules and combinator-based pretty-printing. We describe how we used Kiama to implement an Oberon-0 compiler as part of the 2011 LDTA Tool Challenge. In addition, we explain how Scala enabled a modular approach to the challenge. Traits were used to define components that addressed the processing tasks for each Oberon-0 sub-language. Combining the traits as mixins yielded the challenge artefacts. We conclude by reflecting on the strengths and weaknesses of Kiama that were revealed by the challenge and point to some future directions. The Kiama library implements language processing in Scala.Attribute grammars, strategy-based rewriting and pretty-printing are supported.We describe building an Oberon-0 compiler using Kiama.Trait-based mixins in Scala proved useful to modularise the compiler.Overall, our participation in the 2011 LDTA Tool Challenge was worthwhile.

We present a method for profiling programs that are written using domain-specific languages. Instead of reporting execution in terms of implementation details as in most existing profilers, our method operates at the level of the problem domain. Program execution generates a stream of events that summarises the execution in terms of domain concepts and operations. The events enable us to construct a hierarchical model of the execution. A flexible reporting system summarises the execution along developer-chosen model dimensions. The result is a flexible way for a developer to explore the execution of their program without requiring any knowledge of the domain-specific language implementation.These ideas are embodied in a new profiling library called dsprofile that is independent of the problem domain so it has no specific knowledge of the data and operations that are being profiled. We illustrate the utility of dsprofile by using it to profile programs that are written using our Kiama language processing library. Specifically, we instrument Kiama's attribute grammar and term rewriting domain-specific languages to use dsprofile to generate events that report on attribute evaluation and rewrite rule application. Examples of typical language processing tasks show how domain-specific profiling can help to diagnose problems in Kiama-based programs without the developer needing to know anything about how Kiama is implemented.

RDF forms the basis of the semantic web technology stack. It is based on a directed graph model where nodes and edges are identified by URIs. Occasionally, such graphs contain literals or blank nodes. The existential nature of blank nodes complicates the graph representation.In this paper we propose a purely functional representation of RDF graphs using a special form of inductive graphs called inductive triple graphs. We employ logical variables to represent blank nodes. This approach can be implemented in any functional programming language such as Haskell and Scala. We propose a purely functional representation of RDF graphs.We present two implementations in Haskell and Scala.We outline an algebra of RDF graphs with common operations like mapping, folding, or merging.We demonstrate the potential advantages of an inductive representation of RDF graphs.We outline some possible applications such as parallel programming among others.

Attribute grammars are a powerful specification paradigm for many language processing tasks, particularly semantic analysis of programming languages. Recent attribute grammar systems use dynamic scheduling algorithms to evaluate attributes on demand. In this paper, we show how to remove the need for a generator, by embedding a dynamic approach in a modern, object-oriented and functional programming language. The result is a small, lightweight attribute grammar library that is part of our larger Kiama language processing library. Kiama's attribute grammar library supports a range of advanced features including cached, uncached, higher order, parameterised and circular attributes. Forwarding is available to modularise higher order attributes and decorators abstract away from the details of attribute value propagation. Kiama also implements new techniques for dynamic extension and variation of attribute equations. We use the Scala programming language because of its support for domain-specific notations and emphasis on scalability. Unlike generators with specialised notation, Kiama attribute grammars use standard Scala notations such as pattern-matching functions for equations, traits and mixins for composition and implicit parameters for forwarding. A benchmarking exercise shows that our approach is practical for realistic language processing.

Java’s annotation mechanism allows us to extend its type system with non-null types. Checking such types cannot be done using the existing bytecode verification algorithm. We extend this algorithm to verify non-null types using a novel technique that identifies aliasing relationships between local variables and stack locations in the JVM. We formalise this for a subset of Java Bytecode and report on experiences using our implementation.

Parallel programming is difficult due to the complexity of dealing with conventional lock-based synchronization. To simplify parallel programming, there have been a number of proposals to support transactions directly in hardware and eliminate locks completely. Although hardware support for transactions has the potential to completely change the way parallel programs are written, initially transactions will be used to execute existing parallel programs. In this paper we investigate the implications of using transactions to execute existing parallel Java programs. Our results show that transactions can be used to support all aspects of Java multithreaded programs, and once Java virtual machine issues have been addressed, the conversion of a lock-based application into transactions is largely straightforward. The performance that these converted applications achieve is equal to or sometimes better than the original lock-based implementation.

We present FindLocks, an approach for automatically proving the absence of data races in multi-threaded Java programs, using a combination of dynamic and static analysis. The program in question is instrumented so that when executed it will gather information about locking relationships. This information is then used to automatically generate annotations needed to type check the program using the Race-Free Java type system. Programs that type check are sure to be free from races. We call this technique dynamic annotation inference. We describe the design and implementation of our approach, and our experience applying the tool to a variety of Java programs. We have found that when using a reasonably comprehensive test suite, which is easy for small programs but harder for larger ones, the approach generates useful annotations.

This paper presents a new approach to algorithm design and analysis that benefits from the OO characteristics of Java. It consists of first defining the inheritance structure of a collection of algorithms, at different levels of abstraction. Then, correctness proofs and complexity measures are designed for the various levels of abstraction. The goal is to prove as many properties as possible at each abstract level, assuming the implementations of the methods called upon will be correct. Thus, when a more specialized algorithm is derived from a more abstract one, proofs and complexity analysis can be reused, and simply need to be completed by proving that the properties assumed for the concrete methods indeed hold. The approach is illustrated with several inheritance trees: for sorting, graph algorithms, string matching, and network flow. Each tree, at the bottom of the hierarchy, yields well-known algorithms in the respective area. Instead of using pseudo-code to describe these trees, Java is used to make the process more precise and useful, encouraging the design and analysis of algorithms, and also experimentation with new variants. The implementation presented in this paper takes advantage of Java’s organization to build the inheritance trees for the classes, and Java’s interfaces, collections, comparators, and iterators.

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.

Extant Java Virtual Machines (JVMs) apply dynamic compiler optimizations adaptively, based on the partial execution of the program, with the goal of improving performance. Understanding and characterizing program behavior is of vital importance to such systems. Recent research, primarily in the area of computer architecture, has identified potential optimization opportunities in the repeating patterns in the time-varying behavior of programs. In view of this, we believe that by considering time-varying, i.e., phase, behavior in Java programs, adaptive JVMs can enable performance that exceeds current levels.To enable analysis and visualization of phase behavior in Java programs and to facilitate optimization development, we have implemented a freely available, offline, phase analysis framework within the IBM Jikes Research Virtual Machine (JikesRVM) for Java. The framework couples existing techniques into a unifying set of tools for data collection, processing, and analysis of dynamic phase behavior in Java programs. The framework enables optimization developers to significantly reduce analysis time and to target adaptive optimization to parts of the code that will recur with sufficient regularity. We use the framework to evaluate phase behavior in the SpecJVM benchmark suite and discuss optimizations that are enabled by the framework.

Most of the Java tutorials found on the Web are more or less well reformatted versions of lecture notes or textbooks. As a consequence these tutorials have just as little interactivity and adaptivity as the printed originals. The tutorial JOSH-online presented in this article enables students to learn Java programming step by step, by interactive trial and error. The tutorial not only provides exercises, but encourages students to consolidate and extend their newly acquired knowledge by means of own hypotheses and their experimental verification. In this paper we describe the design of the tutorial, the underlying interpreter and its integration.