We are looking forward to working with you on your thesis project (in German or English)!
Our group offers a range of open thesis topics in the general area of software engineering or programming languages.
We also welcome your own ideas, especially if they are in scope of our research topics.
If you are interested in pursuing a thesis with our group, please send us an email with the following information:
a brief description of the kind of work you are interested in (e.g. more theoretical, more practical, a programming task, ...)
your level of knowledge of the theory or implementation of programming languages (if any)
a current transcript of your grades
potentially relevant skills you acquired outside of university
The Sequent Calculus Compiler (SCC) uses sequent-calculus-based intermediate representations to compile a functional programming language to native machine code.
Within the SCC, control flow is explicitly encoded using consumers.
A continuation is a consumer that represents the remainder of a computation.
In standard functional programs, each continuation is used linearly, i.e. exactly once.
However, the SCC also supports control operators that break this linearity assumption.
This thesis investigates how to statically track the linearity of continuations and exploit it to generate more efficient machine code, reducing both runtime overhead and memory usage.
To achieve that, the memory allocation mechanisms are extended for linear usage of data.
In this work, these improvements are only applied specifically to continuations, but serve as a foundation for more general use cases.
Efficient memory management is a central challenge for programs that allocate
and discard large data structures at runtime. In garbage-collected languages,
reclaiming such memory can introduce significant overhead, causing load spikes
and observable pauses in execution. To address this issue, we investigate
alternative memory management strategies using the Effekt programming language
as an experimental platform.
The Effekt language, a language supporting lexical effects and handlers, uses
several intermediate representations (IR) during compilation. One of them uses
continuation passing style (CPS). In this thesis, a new compilation strategy is
explored, using this CPS IR and compiling it to Chez Scheme. CPS relies heavily
on tailcalls, so we expect this strategy to lead to improved performance
compared to other backends of Effekt which use the CPS IR, due to Chez Scheme’s
support of tailcall optimization. Compared to backends using other IRs, we
expect better performance because of the optimizations allowed by the CPS IR.
All while supporting the same or more features as the other backends, including
bidirectional effects and reentrant continuations.
Array programming languages have become increasingly relevant in many domains,
especially in machine learning and scientific computing. Array programming
offers concise, declarative syntax with high-level operations on arrays.
High-level operations on arrays enable implicit parallelism of computations;
however, mainstream systems typically trade off compile-time shape guarantees
for performance on accelerators.
When choosing a compiler intermediate representation, both its intrinsic
properties and the availability of compilation targets must be considered. It
should admit an easy translation from a rich surface language, be type-safe, and
make strong meta-theoretical guarantees. AxCut has recently been proposed in
this field, meeting these requirements. It inherits the logical properties from
classical sequent calculus and can elegantly model complex control flow.
However, an intermediate representation is only relevant if it can be used to
generate machine code for the architectures of interest. While AxCut can already
be compiled to x86-64 and AArch64, one increasingly important target is
currently missing: the web. In this thesis, we enable users of AxCut to target
browsers. We therefore provide a translation from AxCut to WebAssembly.
WebAssembly strongly differs from the classical architec tures AxCut was
originally designed for. Despite this, we reproduce the semantics while matching
the native code in terms of the number and types of jumps. To ensure
correctness, our implementation was tested extensively and enforces certain
invariants using dependent types. Preliminary performance evaluations show that
performance is not yet comparable to the native code, but we provide potential
solutions for this.
The symmetrical properties of the sequent calculus make it an interesting base for functional programming languages. In contrast to the prevalent base lambda calculus, it allows for an equivalent treatment of terms producing information and evaluation contexts. In this thesis, we have constructed and implemented a term language for the sequent calculus, along with its cut-free fragment. We further present a normalization function that evaluates statements to their cut-free form, utilizing cut elimination and hereditary substitution. Thereby, it lends itself as a compiler intermediate language, shifting computation from runtime to compile-time, and optimizing program execution.
When evaluating functional programs, there are various strategies for reducing expressions. A strategy is Lévy-optimal if it never does unnecessary work such as duplicating terms that are later erased. To implement this efficiently, graphical representations like Interaction Nets can be used to encode the sharing of duplicated terms. Beyond optimality, Interaction Nets provide elegant solutions for parallelization and distributed computing, making them an attractive backend for programming languages. Side effects such as file I/O are rarely discussed in the context of optimal reduction, despite their necessity for real-world applications. In this thesis, we will therefore analyze and formalize existing implementations, and design and implement an optimal runtime with side effects.
Testing is one of the most important methods for ensuring software quality.
However, traditional example-based testing methods have inherent limitations: they are restricted to evaluating individual scenarios,
yet they are often used to justify broader claims than these scenarios can support.
In dieser Bachelorarbeit wird beschrieben wie Bend, eine Programmiersprache, die auf Interaktionskombinatoren basiert und noch in Entwicklung ist, als Backend des Effekt Kompilierers hinzugefügt wird. Bend kompiliert zu HVM, was für Higher-order Virtual Mashine steht. HVM implementiert die von Lafont [5] entworfenen Interaktionskombinatoren. Bend kann einige Lambda-Terme in von Levy [7] definierter optimaler Zeit berechnen und sehr leicht mehrere Berechnungen parallel durchführen. Deshalb hoffen wir mit Bend als Backend die Laufzeit von Effekt in einigen Programmen stark zu reduzieren.
This thesis aims to provide a way to translate classical sequent calculus to the LLVM intermediate representation to utilize the LLVM toolchain and achieve greater performance than compiling directly to machine code. We provide examples of how this translation works, what the resulting optimized version looks like and how and why we implemented a custom memory allocater to suit our needs. We show how to evaluate the resulting programs and how we test the validity of the translation. Finally we benchmark our approach against other programming languages and compare the resulting performance.
Concurrent programs are widely used in practice, but notoriously difficult to get right,
particularly when dealing with the locking and synchronization of shared memory between threads.
However, ensuring correctness becomes even more challenging when individual components,
which may function correctly in isolation, interact with each other.
Software Transactional Memory offers a solution by abstracting over the low-level details of concurrent programming,
providing atomic blocks that enable modular composibility of transactions.
Inference programming - the adaptation of inference algorithms to a particular model or problem - is difficult in languages that do not deal with side effects or do not handle side effects properly due to their nature of relying on effectful computation. In functional programming, monad transformers are the most common approach to control side effects. However, this makes it difficult to customise such algorithms. Effects and effect handlers on the other hand introduce another possibility to deal with programmable inference. This thesis will demonstrates this idea by developing three inference patterns (Metropolis-Hastings, slice sampling and rejection sampling) using the language Effekt. The result is a more user-friendly way to adapt and combine parts of these algorithms
Alle Programmiersprachen besitzen eine gemeinsame Schnittmenge der grundlegenden Abstraktionen. Durch einen Kompiler oder Interpreter werden die Abstraktionen in Maschinencode umgesetzt und dann ausgeführt. Je besser diese Umsetzung optimiert ist, desto performanter ist die Ausführung des Programmes. Im Paper Are-We-Fast-Yet [ 5 ] werden 9 Microbenchmarks entwickelt, welche in moderat komplexen Programmen jeweils bestimmte Bereiche dieser Core Language testen. Die Benchmarks werden in verschiedene Programmiersprachen implementiert und die Ausführung auf Zeit gemessen. Anhand der Ergebnisse lässt sich eine generelle Aussage über die Performanz einer Programmiersprache, beziehungsweise Kompilers/Interpreters machen.
Reactive systems are an important part of everyday programming. Still, the implementations of such reactive systems differ hugely, which has a major impact on the style and reliability of reactive programs. The main approach to implementing reactivity and parallelism in the industry is to use multi-threading. This approach often leads to non-deterministic behavior. Additionally, programming languages often need extra implementations for reactivity and parallelism to support multi-threading. Languages such as Effekt eradicate the need for additional reactive system language support, by implementing algebraic effects. With algebraic effects, it is possible to implement a vast amount of programs, including reactive systems.
In this work, we present Reactive, a library for the programming language Effekt. Reactive uses algebraic effects to implement reactivity and parallelism in direct style. The ability to write programs in direct style leads to more readable code, as it appears to be sequential, while the control flow is handled with algebraic effects. Reactive defines a synchronous execution model, by interleaving waiting parts of the program. The synchronous approach of the library makes decisions over the execution flow of the program deterministic. Parallelism and reactivity are decoupled by using different effects and handlers. With schedulers, Reactive creates the ability to run parts of a program in parallel. Reactive implements different schedulers, which handle the control flow of the program by enforcing rules. Such rules can be the termination of parts of the program when another has already stopped. The awaiting of an event is done by polling an environment in a busy wait loop, which can be interleaved with other parts of the program. Additional to the Effekt implementation, this thesis implements the ability to wait for JavaScript events inside the Effekt language.
Effekt is a functional programming language developed for research on algebraic effects and handlers. Aside from algebraic handlers, Effekt also features side effects in form of mutable state using region-based memory management.
The Effekt compiler has multiple backends, one of which targets the LLVM Intermediate Representation. The LLVM-IR can be compiled to an executable file with many optimization passes on the way.
The LLVM backend of Effekt covers only a subset of Effekt’s features. As part of this thesis, we extend the LLVM backend by support for mutable state.
Most IDEs for Python development follow traditional code analysis approaches that are known to work well for statically-typed languages such as Java or C++. A lot of modern Python code is untyped, and these conservative tools tend to assign the “Any” type for variables that do not have explicit type annotations. However, programmers are usually able to deduce types (and often concrete values) by looking at surrounding code and jumping through function definitions and call sites.
Handling resources, such as files or network sockets, in a language with control (such as exceptions) safely can become difficult. We need to make sure that all memory is eventually
freed and all file handles and sockets are closed; even in the case of an exception.
Viele der Lehrmaterialien welche wir in der Lehre verwenden bestehen aus nicht interaktiven Skripten und Foliensätzen.
Aber viele Inhalte der Informatik eignen sich besonders gut für eine interaktive Präsentation.
Durch eine interaktive Präsentation können auch sehr abstrakte Inhalte greifbar und verständlich gemacht werden.
So wird zum Beispiel häufig auf Animationen und interaktive Graphiken zurückgegriffen, um die Ausführung von Algorithmen zu veranschaulichen.
Good type errors are an important tool to improve programmer productivity.
Ideally, they can help to quickly localize and fix problems and help programmers
to not only better understand the error, but also the underlying program.
Effekt is a novel programming language featuring new ways to modularize software and structure complex control flow.
In particular, it includes lexical effect handlers as well as an advanced type- and effect system.
However, the language is yet lacking a full module system.
Static type systems help to avoid programming errors by indicating to the programmer
at compile time that a value potentially has a wrong type. This way, unsupported
operations (such as dividing two strings or calling a method on a number) are ruled
out before the program is executed.
Effekt is a research programming language that features a lightweight implementation of effects and handlers. As part of this thesis, the language was extended with second-class modules and related functionalities. These new features allow programmers to define modules and abstract them with interfaces. Also, the module system aims to strengthen the interplay between effects and modules. Both concepts share common characteristics, paving the way for potential future unification. This work examines those possibilities and provides insights into the relationship of modules and effects.
Package managers for programming languages are becoming more and more prevalent with only few languages not having one. The packages that one can add to a project with these tools are stored in an online repository, where users can share their work and make it available to other developers. This has led to huge increase in productivity. Fragnix is a prototype that is built around the idea of not sharing huge packages, that can contain several module files but rather the smallest possible unit of distribution: single functions. This thesis explains what was necessary to turn the Fragnix prototype from a tool, that could extract single definitions from Haskell modules into its own files, into a package manager, that transmits these files over the internet to integrate them in a user’s project.
Algebraic effect handlers have been gaining attention in programming language re-
search. They offer a new, abstract way of control flow. In this thesis we do a
case study on reproducing a Haskell framework for build systems in Effekt, a new
programming language with support for algebraic effect handlers.
Diese Bachelorarbeit befasst sich mit der Entwicklung eines Frontends für eine
Datenbank, die Codeausschnitte der Programmiersprache Haskell beinhaltet.
Das Frontend soll hier eine Webseite sein, die ein Nutzer im ersten Schritt
auf seinem System installieren kann und die in einem weiteren Schritt auch
öffentlich zugänglich gemacht werden kann.
Algebraic subtyping is a new approach which unifies parametric polymorphism, subtyping and complete type inference with principal types.
The presentations used in the literature illustrate the approach by considering systems with function types, record types and base types, since these form a minimal type theory which allows to illustrate contravariance (function types) and subtyping (record types).
User-defined data and codata types are two dual and complementary ways to specify types and their inhabitants.
Data types specify canonical producers which are built up by constructors, and non-canonical consumers which are formed by pattern matching on constructors.
Codata types specify canonical consumers which are built up by destructors, and non-canonical producers which are built up by copattern matching on destructors.
For example, using (indexed) codata types it is possible to replace a builtin (dependent) function type by a user defined type.
Building upon the existing Fragnix tool [fragnix], which slices a Haskell
program into its declarations and enriches them with metadata, this thesis
envisions a software sharing ecosystem based on sharing single declaration
slices. Such an ecosystem could offer improvements in terms of performance,
dependency tracking and maintenance and help with the prevention of effort
duplication. A declaration editor is chosen as the next step towards realizing
the tools for this slice sharing ecosystem. Using Haskell in the back-end and
Elm in the front-end, prototypes for navigating code in form of slices are
developed. A layout based on code-folding and in dentation proves to be most
promising and is used for implementing the back-end foundations for editing and
the ability to edit the text of declarations. The implementation of the
remaining editing features is left for future work.
The goal of this bachelor thesis was to investigate the differences between
probabilistic programming languages. Therefore a case study was performed.
We represented a hidden markov model and implemented inference on it
with two probabilistic programming languages, WebPPL and Pyro. WebPPL
following a functional approach as well as Pyro that sticks to an imperative
programming paradigm succeeded in representing the hidden Markov model.
Concerning the inference on the hidden markov model critical spots such as
dealing with state depending models were revealed. We came to the conclusion
that there exists a balancing problem between a generalization and a highly
individual implementation of inference algorithms for probabilistic program-
ming languages. The bachelor thesis is interesting for Bachelor or Master
students of computer science and related courses of studies. It is also in-
teresting for anybody dealing with probabilistic models and inference on them.
Um die kundenorientierte Reichweite eines Unternehmens zu vergrößern, welches
Softwareschnittstellen anbietet, ist es notwendig, diese Schnittstellen für verschie-
dene Programmiersprachen bereitzustellen. Um dabei den Aufwand gering zu
halten, soll großteils nur in einer Sprache entwickelt werden und die Software
soll anschließend automatisch in andere Sprachen übersetzt werden. Die Firma
yWorks entwickelt dafür das Übersetzungsprogramm Blunter. Unter Verwendung
des Blunters soll das von yWorks nach dem Model-View-Controller (MVC)-Pattern
programmierte Visualisierungs-Framework yFiles nach Python portiert werden.
Für die graphische Darstellung in Python wird ein externes Graphical User In-
terface (GUI)-Framework verwendet, welches bereits beim Übersetzungsprozess
automatisch in die Python-Portierung integriert wird.
Im Zuge des Tübinger Software-Projekts (TSPs) 2018/19 wurde in Zusammenarbeit
mit der yWorks GmbH (yWorks) die neue Version 3.0 des Quellcodeübersetzers
Blunter entwickelt. Dadurch ist das Programm nun in der Lage, ein gegebenes
C#-Projekt in ein Python-Projekt zu übersetzen.
Effect handlers as generalizations of exception handlers offer interesting
new ways to modularize software. Scala Effekt is an implementation of
effect handlers, based on capability passing. Instead of searching for
the correct handler in runtime, the handler is passed down to where the
effect is used.
This allows convenient implementations in languages like Scala
and Java and comes with performance improvements.
Scala 3 introduced the new feature of implicit function types, greatly
reducing the burden of explicit capability passing.
However, capabilities
can leak and leave the scope of the defining handler leading to
runtime errors.
The Language Server Protocol (LSP) defines a protocol used between an editor or IDE and a language server that provides language features like auto complete, go to definition, find all references etc.
The Language Server Protocol has to be implemented once for every programming language and once for every editor, instead of once for every combination of programming language and editor, thus reducing a m x n problem to a m + n problem.
In functional languages, such as Haskell, we find existing libraries for working with graphs. These libraries contain the definitions of the necessary datatypes and the functions working on them. Examples of such libraries (in Haskell) are the FGL library by Martin Erwig and the Data.Graph module in the containers package.
Program optimization by compilers is important - especially for functional programming languages. Yet at least parts of it remain a ”black art”, as Simon Peyton Jones describes the inlining technique in [0], full of compromises and heuristics. The problem, known as code bloat, is that optimization techniques might actually make performance worse by inlining too much, blowing up the code size.
In dieser Bachelorarbeit geht es um das automatische Testen einer eigens programmierten integrierten Entwicklungsumgebung. Die Applikation wird in Qt/C++ programmiert und mittels des Testframeworks Squish getestet. Dabei wird zuerst im Allgemeinen auf Qt und Squish eingegangen. Darauf folgen Vorgehensweise und Entwicklungswerkzeuge. Im Anschluss wird die Applikation, welche Hypertext Phoenix genannt wird, beschrieben. Das letzte und längste Kapitel widmet sich komplett dem Testen. Hier wird auf allgemeine Themen wie Tests von Hypertext Phoenix mit Beispielen eingegangen. Abschluss dieses Kapitels bildet der Nutzen von Tests.
Pianists perform a variety of exercises to improve the evenness and precision of their playing,
including scales, arpeggios, and octaves. The purpose of this thesis is to develop an application
that supports pianists in two ways: 1) Training the ear to identify uneven scales, arpeggios etc., and
2) Analyze the exercises of the pianist to identify flaws in the execution of the exercises.
Markdown is a lightweight and widespread way of structuring plain text documents. The layout rules that are used to structure the text make Markdown at the same time easy to read for humans but also difficult to write a grammar or a parser.
Das Ziel dieser Arbeit ist, eine Softwareproduktlinie der Firma Bosch, die mit C und CPP realisiert wurde, so zu transformieren, dass die Compile-Zeit Variabilität von CPP ersetzt wird durch Laufzeitvariabilität.
The purpose of this thesis is to develop a plug-in for the DrRacket development environment
that will monitor and log the activity of students. The (appropriately anonymized) collected
data will then be used for the scientific evaluation of how beginning programmers work.
The main focus of this work is on collecting and representing the developer activity in such
a way that interesting analyses can be defined on top of it.
Das im Rahmen des “Tübinger Softwareprojekts” entwickelte System für Schritt für Schritt Anleitungen soll in dieser Bachelor-Arbeit um eine neuartige Such-Funktionalität erweitert werden.
Wir gehen in Zukunft davon aus, dass Nutzer Projektbeschreibungen nicht mehr durch Texteingabe suchen, sondern eher nach Fotos oder Bildern im Internet.
Ein Ansatz zur Implementierung der Funktionalität besteht darin, zuerst das Bild zu Verschlagworten und die so erhaltenen Schlagwörter dann als Eingabe
einer „klassischen“ Suchmaschine zu verwenden. Hierzu gibt es bereits verschiedene Technologien. Die Aufgabe der Bachelor-Arbeit ist es nun, die vorhandenen
Technologien zu identifizieren, zu analysieren und geeignete Technologien auszuwählen. Auf Basis von zu entwickelnden System- und Interaktionskonzepten soll die
Implementierung bzw. Systemintegration erfolgen. Ziel ist die prototypische Darstellung einer Suche nach einer DIY-Projektbeschreibung mithilfe eines gemachten Fotos.
Das im Rahmen des “Tübinger Softwareprojekts” entwickelte System für Schritt für Schritt Anleitunge soll in dieser Bachelor-Arbeit
um eine Assistenz-Funktionalität erweitert werden. Im Allgemeinen sind Assistenten wie beispielsweise Apple Siri oder Microsoft Cortana
hinreichend bekannt. Die Herausforderungen bei diesen Assistenten liegen in der Modellierung der Domäne und in der Bereitstellung des
Domänenwissens. Zusätzlich muss der Assistent per API in das System eingebunden werden.
Numerical functions often need be invoked on views of vectors or matrixes,
derived by selecting some elements or by pre-transforming them. For instance,
one might want to prescale matrix elements before applying an existing FFT
algorithm on them. Often this must be done by copying the elements to a separate
array, and then invoking the original FFT algorithm, but this procedure is not
efficient because it uses additional space and therefore has higher impact on
data caches.
Literate programming blends the borders between source code and
documentation. The goal of existing tools like Docco and Scribble
is to create a uniform reading experience for documentation and
code.
These are grammar transformations useful in compiler construction
(Compilerbau): conversion to Chomsky normal form, left factoring,
left recursion elimination. Standard textbooks describe how these
transformations work on the production rules of grammars.
However, a real compiler works on syntax trees. For each of these
transformations between grammars, there exist forward and
backward transformations between syntax trees of the grammars. To
use grammar transformations in practice, we need the syntax tree
transformations.
Implement a set of program transformations between programs in
(subsets or all of) the language Uroboro that has recently been
proposed by the working group of programming languages and
software technology.
