Writing efficient functional programs is challenging. While immutable data structures make it easier to reason about code correctness, special care has to be taken to not deteriorate performance:
Lists, for example, are the most natural representation of collections of data in functional programming. However, their functional implementation does not allow for fast random access, removal or insertion. Depending on the use case, one has to be clever about how to utilize lists, or select alternative (functional) data structures.

Together with colleagues at the University of Tartu, we develop and maintain the static analyzer Goblint, based on Abstract Interpretation. Goblint itself is written in OCaml, a functional programming language. While OCaml supports some imperative features, it gives a clear preference to immutability. The tool is capable of analyzing real-world C programs and show properties such as the absence of buffer overruns or data races in multi-threaded code.
C projects may consist of tens of thousands, or even hundreds of thousands lines of code. Consequently, a static analyzer like Goblint has to deal with large input programs, and explore and maintain abstract states for hundreds of thousands of program points, making it of particular interest for optimization.

In the course of this practical, you will work in a team of three to five people. Your task is to profile Goblint, identify performance bottlenecks and tune the implementation.

This will:

• Give you insights into profiling programs
• Deepen your skills in functional programming and writing performant code
• Help your understanding of the performance impact of high level design decisions
• Give you insights into developing a research prototype

Requirements:

• Proficient knowledge of a functional programming language (we use OCaml, but the basics are not so different from other functional programming languages)
• Having completed the Program Optimization Course (IN2053) (or a similar course) is helpful, but not required
• Be an advanced Bachelor student or in your Master's

Schedule

This course will stretch over most of the lecture time. On top of working in your team, you will have weekly to biweekly meetings with us. At the end of the practical all teams will present their results. We expect you to attend and participate in the Q&A.

There will be a joint pre-meeting for both Goblint practicals on July 19th, 2 p.m. at: https://bbb.rbg.tum.de/mic-dya-2x9