Implementing a Language for Just-in-Time Data Structures

Master's Programming Project 2016-2017

Department of Computer Science, Vrije Universiteit Brussel
Software Languages Lab (SOFT)

Instructor: Jennifer B. Sartor

Instructor email: jsartor@soft.vub.ac.be

Project Problem Statement

Today's software is so large and complex, it's hard for a developer to choose one particular data structure for the lifetime of the application, and often one data structure is not optimal in terms of performance. Because applications have different phases -- building up data structures and populating them with data versus searching the data structure and accessing elements, for example -- we believe that the programmer should be relieved of the burden of choosing just one data representation. The building up phase could benefit from having data laid out in a linked list data structure, whereas accessing elements sequentially from a list performs better if the data is represented by an array. We propose a concept called Just-in-Time Data Structures (JIT DS) that lets the programmer choose one universal list data structure, while the runtime dynamically changes the underlying representation to give the best performance in terms of memory accesses and execution time.

A PhD student has introduced JIT DS and built a language called JITds to implement them. A JIT data structure class combines a number of other classes - the potential data representations - and holds the pointer to the current (only one) representation at a particular point in time. In fact the JIT DS class is a sub-class of all of its different representations, as any of the representations' methods can be called on a JIT DS class instance. The JIT DS class also defines transition functions, which define how to transition from one representation to another, and swap functions, which define when to transition to another data representation.

Project Goal

The goal of this master's project would be to implement a better version of JITds (the language to implement JIT data structures) based on two existing, but limited, language implementations. A PhD student implemented JIT DS in both Java and C, but the Java version (a transpiler from JIT DS to Java) suffered from the escaping pointers problem, and the C version was a small prototype. You would analyze and understand the existing implementations and implement a new fully-fledged JITds in a language of your choice. Then we could go on to explore new ideas with this implementation, including exploring various language aspects such as whether the swap statements that trigger a data representation change should be part of the inheritance hierarchy or not. However, the focus of the project would be to first have a more full-fledged implementation that does not suffer from the same limitations of the existing ones.

To get started with this master's thesis, you should read background research on JIT data structures, namely Mattias De Wael's ONWARD paper and his dissertation.