Selected Topics in Programming Languages and Virtual Machines
Professor: Walter Binder
Course type: Corso per dottorandi
Value in ECTS: 1
Academic Year 2010/2011 - Spring semester
In 8 seminar talks, some recent advances in the area of programming languages and virtual machines are presented by leading researchers.
An Overview of ALIA4J - An Execution Model for Advanced-Dispatching Languages
by Christoph Bockisch, University of Twente, The Netherlands
July 5, 2011, 14:30; room SI-006
New programming languages that allow to reduce the complexity of software solutions are frequently developed, often as extensions of existing languages. Many implementations thus resort to transforming the extension´s source code to the imperative intermediate representation of the parent language. But approaches like compiler frameworks only allow for re-use of code transformations for syntactically-related languages; they do not allow for re-use across language families. The ALIA4J approach brings such re-use to language families with advanced dispatching mechanisms like point cut-advice or predicate dispatching. It introduces a meta-model of dispatching as a rich, extensible intermediate language. By implementing language constructs from four languages as refinements of this meta-model, we show that a significant amount of them can be re-used across language families. Another building block of ALIA4J is a framework for execution environments that automatically derives an execution model of the program´s dispatching from representations in our intermediate language. This model enables different execution strategies for dispatching; we have validated this by implementing three execution environments whose strategies range from interpretation to optimizing code generation.
Da Capo con Scala: Design and Analysis of a Scala Benchmark Suite for the Java Virtual Machine
by Andreas Sewe, Technische Universität Darmstadt, Germany
July 5, 2011, 15:45; room SI-006
Originally conceived as the target platform for Java alone, the Java Virtual Machine (JVM) has since been targeted by other languages, one of which is Scala. This trend, however, is not yet reflected by the benchmark suites commonly used in JVM research. In this talk, we present the results of a joint research effort with the Dynamic Analysis Group at the University of Lugano: the design and analysis of the first full-fledged benchmark suite for Scala. We furthermore compare the benchmarks contained therein with those from the well-known DaCapo 9.12 benchmark suite and show where the differences are between Scala and Java code - and where not.
Revisiting Register Allocation
by Nigel Horspool, University of Victoria, Canada
July 21, 2011, 11:00; room SI-006
Where execution performance is concerned, memory accesses are expensive. A good register allocation strategy will help reduce the number of memory accesses by maintaining frequently used values in registers. In a traditional compiler, register allocation algorithms based on graph colouring techniques are typically used. The register allocator has to map a set of values onto a set of registers, usually smaller in size, so as to minimize the number of memory accesses. However these algorithms do not fully take execution frequency into account, and may make some choices which turn out to be bad at run-time. In a JIT-based compiler, the speed at which code can be generated is an issue and quick-and-dirty register allocation schemes based on a linear scan have become popular. However, the JIT environment makes it possible to obtain information about the executing program; perhaps in the form of execution traces or perhaps in the form of execution frequencies for basic blocks. In JIT systems where hot regions of code may be successively recompiled to apply increasing levels of optimization, it makes sense to apply more and more sophisticated register allocation strategies. Perhaps traces or execution frequencies are useful when allocating registers? This talk will explore some possibilities for trace-based and frequency-based register allocation strategies, with references to some work by others. This is ongoing work and any experimental results will be very preliminary.
Optimal Code Generation for Explicitly Parallel Processors
by Andreas Krall, Technische Universität Wien, Austria
July 22, 2011, 11:00; room SI-006
In this talk ongoing work from a research project with the talk title is presented. The aim of this project is to develop techniques for optimal and heuristic integrated code generation for explicitly parallel processors (EPIC). First results on register reuse scheduling are presented where spilling of registers during register allocation is minimized by a local reordering of independent operations. On average 8.9% less values are spilled resulting in 3.4% reduction of static spill cost. Other ongoing work on scheduling for clustered architectures is discussed.
Summarized Trace Indexing and Querying for Scalable Back-in-Time Debugging
by Eric Tanter, University of Chile, Chile
July 22, 2011, 14:30; room SI-006
Back-in-time debuggers offer an interactive exploration interface to execution traces. However, maintaining a good level of interactivity with large execution traces is challenging. Current approaches either maintain execution traces in memory, which limits scalability, or perform exhaustive on-disk indexing, which is not efficient enough. We present a novel scalable disk-based approach that supports efficient capture, indexing, and interactive navigation of arbitrarily large execution traces. In particular, our approach ensures strong guarantees in terms of query processing time, ensuring an interactive debugging experience. The execution trace is divided into bounded-size execution blocks about which summary information is indexed. Blocks themselves are discarded, and retrieved as needed through partial deterministic replay. For querying, the index provides coarse answers at the level of execution blocks, which are then replayed to find the exact answer. Benchmarks on a prototype for Java show that the system is fast in practice, and outperforms existing back-in-time debuggers.
The Sixth Sense: Programming with Ghosts
by Eric Tanter, University of Chile, Chile
July 25, 2011, 11:00; room SI-008
Development environments do not really support the kind of incremental development that programmers rely on. Frequently, either following test-driven development principles or incrementally refining an existing class, programmers code against a class or interface that is not (fully) defined yet. IDEs get in the way by showing off many error messages, especially in the case of statically-typed languages like Java and C#. On the one hand, ignoring these messages prevents the programmer from getting feedback from the IDE regarding potential inconsistencies and typing errors. On the other hand, attending these error messages breaks the workflow of the programmer. We recognize that these not-yet-defined entities actually exist (in the programmer´s mind) before they exist (in the IDE): like ghosts, only few gifted ones can see them. In order to smoothly support incremental development, we propose to extend IDEs with support for ghost classes and members. Ghosts are reified in the IDE, where they are built transparently and non-intrusively. A dedicated ghost view allows programmers to check their ghosts and bust them into actual code when ready. At the programming language level, we show how to extend traditional type systems to support ghosts and report inconsistencies among ghosts early on.
High-level Caching in Optimization Aspects
by Karl Lieberherr, PRL / CCIS / Northeastern University, USA
July 25, 2011, 14:30; room SI-008
Caches can be used to avoid running the same intermediate computation more than once, to speed up subsequent computations, and to reorganize computations by precomputing and storing certain intermediate computations, etc. All these techniques can lead to improved asymptotic runtime complexity of programs or to reduced constant factors. There are two main drawbacks to expressing cache-based optimization aspects in AspectJ-like general purpose aspect-oriented programming languages, reduced safety and low-level of abstraction. In this paper we propose an AspectJ extension for expressing cache-based optimization aspects more safely at a higher level of abstraction. We illustrate the language with well-known examples: Dijkstra´s shortest path algorithm, topological ordering and the closest pair algorithm. We noticed that in algorithm textbooks a clean but not so efficient algorithm description is followed by an implementation paragraph which refines the algorithm into an efficient implementation. Our cache-based optimization aspects formalize the "implementation paragraphs" by expressing them in a programming language. We hope that our new language will encourage software developers to think more systematically about how to speedup their software while keeping it easy to read and understand. Joint work with Ahmed Abdelmeged.
Computational Contracts: Grey Box Verification and Blame Assignment in a Higher-Order Setting
by Eric Tanter, University of Chile, Chile
July 25, 2011, 15:45; room SI-008
Pre/post contracts for higher-order functions, as proposed by Findler and Felleisen and provided in Racket, allow run-time verification and blame assignment of higher-order functions. However these contracts treat contracted functions as black boxes, allowing verification of only input and output. It turns out that many interesting concerns about the behavior of a function require going beyond that black-box approach, in order to control the actual computation that follows from a function. Examples are prohibiting or verifying that certain functions are called, checking access permissions, time or memory constraints, interaction protocols, etc. To address this need for grey-box verification, while preserving support for higher-order programming and blame assignment, we introduce the notion of computational contracts. A computational contract is a contract over the execution of a contracted entity. We show various applications of computational contracts, and explain how to assign blame in case of a violation. Computational contracts have been integrated with the existing contract system of Racket. Computational contracts is the first contract model with blame assignment in a higher-order setting that provides a systematic way to perform grey box verification.
In order to receive credits, PhD students must register for the course until July 4, 2011, and attend at least 7 of the 8 seminar talks. Students must arrive 5 minutes before the begin of each seminar, as attendance will be controlled (late arrival does not count). Active participation in the discussions following the presentations is expected.
References may be given in each seminar talk by the speaker.