Improving API Documentation for Java-like Languages

The Javadoc paradigm for displaying API documentation to users is quite popular, with similar variants existing for many mainstream languages. However, two user interface design properties of Javadoc may reduce its utility when displaying documentation for APIs that make use of inheritance and parametric polymorphism. First, Javadoc does not show a flattened view of all members of a class or interface, but rather only those defined directly in the type. Second, and as a consequence, any methods whose types contain type parameters of a superclass will always be shown in the context of the superclass. That is, if the method C.m returns type T, subclasses of C will always see this parent signature, even if they instantiate T to a concrete type such as Integer. We show that this situation arises often in some libraries, and present the results of a study that measures the usability consequences of these two Javadoc design decisions. Our results show that a user interface that shows instantiated type parameters for members is preferred over one that presents type parameters in the Javadoc style.

Compiling Scala for Performance

Iulian Dragos

Scala is a new programming language bringing together object-oriented and functional programming. Its defining features are uniformity and extensibility. Scala offers great flexibility for programmers, allowing them to grow the language through libraries. Oftentimes what seems like a language feature is in fact implemented in a library, effectively giving programmers the power of language designers. The downside of this flexibility is that familiar looking code may hide unexpected performance costs. It is important for Scala compilers to bring down this cost as much as possible. We identify several areas of impact for Scala performance: higher-order functions and closures, and generic containers used with primitive types. We present two complementary approaches for improving performance in these areas: optimizations and specialization. Compiler optimization can bring down the cost through a combination of aggressive inlining of higher-order functions, an extended version of copy-propagation and dead-code elimination. Both anonymous functions and boxing can be eliminated by this approach. We show on a number of benchmarks that these language features can be up to 5 times faster when properly optimized, on current day JVMs. We propose a new approach to compiling parametric polymorphism for performance at primitive types. We mix a homogeneous translation scheme with user-directed specialization for primitive types. Type parameters may be annotated to require specialization of code depending on them. We propose definition-site specialization for primitive types, achieving separate compilation and no boxing when both the definition and call site are specialized. Specialized classes are compatible with unspecialized code, and specialization agnostic code can work with specialized instances, meaning that specialization is opportunistic. We present a formalism of a small subset of Scala with specialization and prove that specialization preserves types. We implemented this translation in the Scala compiler and report on improvements on a set of benchmarks, showing that specialization can make programs more than two times faster.

EPFL2010

Call Graphs for Languages with Parametric Polymorphism

Martin Odersky, Dmytro Petrashko, Vlad Ureche

The performance of contemporary object oriented languages depends on optimizations such as devirtualization, inlining, and specialization, and these in turn depend on precise call graph analysis. Existing call graph analyses do not take advantage of the information provided by the rich type systems of contemporary languages, in particular generic type arguments. Many existing approaches analyze Java bytecode, in which generic types have been erased. This paper shows that this discarded information is actually very useful as the context in a context-sensitive analysis, where it significantly improves precision and keeps the running time small. Specifically, we propose and evaluate call graph construction algorithms in which the contexts of a method are (i) the type arguments passed to its type parameters, and (ii) the static types of the arguments passed to its term parameters. The use of static types from the caller as context is effective because it allows more precise dispatch of call sites inside the callee. Our evaluation indicates that the average number of contexts required per method is small. We implement the analysis in the Dotty compiler for Scala, and evaluate it on programs that use the type-parametric Scala collections library and on the Dotty compiler itself. The context-sensitive analysis runs 1.4x faster than a context-insensitive one and discovers 20% more monomorphic call sites at the same time. When applied to method specialization, the imprecision in a context-insensitive call graph would require the average method to be cloned 22 times, whereas the context-sensitive call graph indicates a much more practical 1.00 to 1.50 clones per method.

2016

Designable Visual Markers for Mobile Human-Computer Interaction

Enrico Costanza

Visual markers are graphic symbols designed to be easily recognised by machines. They are traditionally used to track goods, but there is increasing interest in their application to mobile human-computer interaction (HCI). By scanning a visual marker through a camera phone, users can retrieve localised information and access mobile services. In particular the dissertation examines the application of visual markers to physical tagging: practices of association of digital information with physical items. One missed opportunity in current visual marker systems is that the markers themselves cannot be visually designed; they are not expressive to humans, and thus fail to convey information before being scanned. To address this limitation, this dissertation introduces the idea of designable markers, visual markers that are both machine-readable and visually communicative to humans, and presents an investigation of the ways in which they can support mobile human-computer interaction. The application of designable visual markers to the creation of mobile interfaces is explored through a variety of methods: through formal usability experiments, through the creation and analysis of example designs, as well as through the qualitative analysis of two field trials. All three approaches were enabled by the engineering and development of d-touch, an actual recognition system that supports designable visual markers and by its integration in a variety of applications and experimental probes. D-touch is based on image topology, and its markers are defined in terms of constraints on the nesting of dark and light regions. The constraints imposed by d-touch are flexible enough to allow novice users to create markers which are visually expressive and at the same time machine readable. A user study demonstrates how such system enables people to design their own functional visual markers, determining their aesthetic qualities and what they visually communicate to others. A desktop application to support users in the creation of valid markers, the d-touch analyser, is presented and its usefulness is demonstrated through the same study. A formal usability experiment comparing five variations of marker-based interfaces on keypad and touch-screen phones shows that all of them allow users to reliably select targets within, on average, less than 4 seconds. Participants of the experiment reported a strong preference for interfaces that involve only marker scanning, compared to those that require a combination of marker scanning and key-presses or touch selections. Example designs of mobile interface generated by the author as well as others are presented to expose how the d-touch recognition system can be integrated in mobile applications. The examples illustrate a variety of ways in which markers can be used to augment printed materials such as cards, books and product packages, adding to them interactive capabilities. The examples show also different approaches to marker design, ranging from simple and recognisable iconic design, to symbols that integrate cues about the interactive functionality, to making them invisible by hiding them in existing graphics. Finally, the dissertation reports and analyses two field trials conducted to study what practices of physical tagging can emerge from, and be supported by, the use of markers. The trials were centred around the use of uWiki, a functional prototype based on d-touch, that allows users to associate digital content to markers printed on physical tags that can be affixed to objects or buildings. Observations show that a variety of practices emerge around the use of this technology, indicating that they provide a rich medium that has potential to attract the interest of real users. Though the results of this work are preliminary, they serve to demonstrate the range of potential for the future of such systems.

EPFL2010

Compiling Scala for Performance

Iulian Dragos

EPFL2010

Designable Visual Markers for Mobile Human-Computer Interaction

Enrico Costanza

EPFL2010