Implementation of Programming Languages

Implementation of Programming Languages

Modern programming languages like Java offer the programmer many advanced concepts: automatic memory management, dynamic class loading and linking, powerful type systems, and efficient just-in-time compilation. Typically, such features are partly implemented by the language's compiler (checking whether a program is well-typed), partly by the runtime environment (collecting garbage, i.e., objects no longer reachable). Consequently, we offer numerous topics concerned with both the front- and back-ends of modern language implementations.

This course is complemented by a seminar: Design and Implementation of Modern Programming Languages. Attending the seminar is not mandatory, although there may exist synergies between topics offered here and in the seminar.

Course Information

TUCaN-ID

20-00-0306-pr

Course Type

P4 / 6 CPs

Advisors

Andreas Sewe, Jan Sinschek, Ralf MItschke

Sign-up

Please sign up in advance by mail: . Sign up in TUCaN only after you have been assigned a topic.

Kick-off

Friday, 20 April 2012, 15:15 - 16:15 in S2|02-A313

Language

Both Englisch and German are accepted for documentation purposes.

Topics (preliminary)

The following list of topics is preliminary; it will likely grow until the kick-off.

Method-Fingerprinting in a JVM

In a research context (e.g., when using replay compilation), it is often necessary to identify a method across multiple runs of a program. Unfortunately, on-the-fly code generation makes this difficult on the JVM. Even if a method is virtually the same across runs, it often bears different, seemingly random names.

The goal of this project is to address this problem by adding a facility to the Jikes Research VM (a meta-circular JVM, i.e., one written in Java) which computes a stable fingerprint based on a method's content and makes this information available to all replay-compilation subsystems. This facility will likely be similar to the one used by TamiFlex.

Students: 1 (good knowledge of Java is required)

Advisor:Andreas Sewe

Parallel static whole-program analysis

Soot is one of the most widely used program-analysis frameworks for Java, both in academia and industry. Recently, we have implemented a so-called IFDS solver that allows users to rapidly implement entire whole-program analyses. Task of this lab will be to parallelize this algorithm implementation so that it can be run efficiently and correctly on multiple cores. In the past, researchers have already designed a parallel version of the IFDS algorithm for Scala's actor framework.

Your task in this project will be to find and implement an appropriate design for pure Java. In this lab students will learn (1) how to use state-of-the-art tools for Java program analysis, (2) how to implement program-analysis algorithms and (3) how to use Java's concurrency APIs. (1-3 students)

Students: 1-3

Advisor:Eric Bodden

A JavaScript frontend for Soot

Soot is one of the most widely used program-analysis frameworks for Java, both in academia and industry. Soot analyzes Java programs by first transforming those programs (given in the form of source code or bytecode) to an intermediate representation (IR) called Jimple. This IR looks similar to Java source code, but only contains very simple statements that, unlike in Java, are never nested. All control-constructs are expressed as conditional or unconditional gotos. This simplicity of the language makes it very easy for programmers to express static program analysis. Any Java program can be translated to Jimple and the other way around – the translation is complete.

Task of this lab will be to design and implement a JavaScript frontend for Soot, i.e., a mechanism that will allow Soot to also process JavaScript source code. This code is to be parsed and converted into equivalent Jimple code. Students may use existing open-source JavaScript parsers for this purpose. In this lab students will learn (1) the syntax and semantics of JavaScript, (2) how to use parsers, and (3) how to use state-of-the-art tools for Java program analysis.

Students: 1-3

Advisor:Eric Bodden

An IFDS-based information flow analysis for Android and Java

Static information-flow analysis determines insecure information-flow in a piece of software by analyzing this software's code. The analysis generally tries to find so-called sources of secret information from which information can leak to certain pre-determined “sinks”. Soot is one of the most widely used program-analysis frameworks for Java, both in academia and industry. Recently, we have implemented a so-called IFDS solver that allows users to rapidly implement entire whole-program analyses such as information-flow analyses. In addition, we have extended Soot to support the analysis of Android apps.

Task of this lab will be to implement an information-flow analysis using Soot. In the past, researchers have implemented an IFDS-based information flow analysis for JavaScript; students should be able to reuse many ideas of this implementation. The implemented analysis is to be evaluated on some security sensitive real-world Java program such as a crypto library. In this lab students will learn (1) how to design and implement information-flow analyses, (2) how to use state-of-the-art tools for Java and Android program analysis and (3) how to find and report information-flow violations in real-world programs.

Students: 1-3

Advisor:Eric Bodden

Dalvik Executable Support for Jikes RVM

The Jikes Research VMis a Java virtual machine popular with researchers. It contains two compilers (a fast baseline compiler and a slow optimizing compiler), which translate Java bytecode into native machine code. Now, despite re-using the Java class library the Android's Dalvik virtual machine uses a different, register-based bytecode format, which Jikes RVM cannot yet comile.

The goal of this project is thus to extends Jikes RVM such that it can read in methods written in Davlik bytecode and compile them at least with the baseline compiler, if not the optimizing compiler. You will learn about both Java and Dalvik bytecode and just-in-time compilers.

Students: 1-3 (good knowledge of Java is required)

Advisor:Andreas Sewe

Applying Scala to Jikes RVM

The Scala programming language has recently become popular, as it offers many features that Java lacks, e.g.,first-class functions and mixin inheritance. These features are paricularily useful when the software system is large and consists of many concerns that cross-cut each other. This is, for example, the case in modern virtual machines, of which the Jikes RVM is one example. As this particular VM is written in Java and Scala compilers to Java bytecode, it becomes possible to selectively implement parts of the JVM in Scala.

The goal of this project is to assess the feasibility of written (parts of) a VM in Scala. To that end, one subsystem (e.g., the memory manager) will be refactored and ported to Scala.

Students: 1-2 (good knowledge of Java is required; Scala can be learned on the job)

Advisor:Andreas Sewe