Topics for bachelor and master thesis as well as projects

Topics for bachelor and master theses as well as projects come from the areas of software engineering and programming languages. The concrete topics for theses are oriented towards our research areas.  Basics are taught in the corresponding courses of the institute.

The following list offers a selection of topics and subject areas. More detailed information can be obtained from the respective contact persons. In addition, we are open to your own suggestions for topics.

(Legend - B: Bachelor Thesis, M: Master Thesis, P: Project)

Algorithm Detection

P/B/M: Scalability experiments with the prototype (Neumüller, Tichy)

Context
We are convinced that automatically detecting algorithm implementations in a code base can be helpful to gain knowledge about, which concerns are present in the code base, how they are solved and which components are involved. This knowledge can then support the tasks of software comprehension, software architecture recovery and software maintenance. Our java based prototype consists of a Domain Specific Language (DSL) designed to describe key features of an algorithm, a search algorithm to find these features and a set of “ready to use” descriptions for common algorithms.
Examples for algorithms which could be interesting to detect and some of the insights their detection provides:

  • Quicksort -> The application sorts data structure x.
  • A* -> The application does path search.
  • Raft (Consensus Algorithm) -> The application is a distributed, fault-tolerant system

Problem

We have evaluated the accuracy of the prototype and achieved good results, but more data is needed to:

  • Answer how the prototype scales with increasing size of the code base
  • Efficiently debug scaling and performance problems

Tasks

  • Create a database from open source projects / use an existing database
  • Implement runtime measurements with microbench
  • Create and run a few scalability experiments
  • Automate these as performance tests in the CI/CD pipeline
  • Implement “advanced” logging features
  • Analyze scalability issues

Possible Research Questions

  • How does the prototype scale on real-world data?
  • What are the reasons for performance problems of individual search patterns
  • Which data is usefull to analyze/debug the performance of search patterns?

Related Work

P/B/M Automatic generation of search-patterns (Neumüller, Tichy)

Context
We are convinced that automatically detecting algorithm implementations in a code base can be helpful to gain knowledge about, which concerns are present in the code base, how they are solved and which components are involved. This knowledge can then support the tasks of software comprehension, software architecture recovery and software maintenance. Our java based prototype consists of a Domain Specific Language (DSL) designed to describe key features of an algorithm, a search algorithm to find these features and a set of “ready to use” descriptions for common algorithms.
Examples for algorithms which could be interesting to detect and some of the insights their detection provides:

  • Quicksort -> The application sorts data structure x.
  • A* -> The application does path search.
  • Raft (Consensus Algorithm) -> The application is a distributed, fault-tolerant system

Problem

We want to make it as easy as possible for users to create search-patterns. A simple starting point is to automatically generate a search-pattern based on a piece of code as input. The user should be able to select different abstraction levels for the search pattern e.g.:

  • Match this code exactly.
  • Match this code but ignore types and identifier names.
  • Match this code but allow additional statements.
  • ....

Tasks

  • Implement the code to search-pattern generation
  • Implement existing already existing ideas for abstraction levels
  • Automate the generation as a pipeline:
    • Input: Selected abstractions + code
    • Create the search-pattern
    • Run the analysis to get the results
  • Develop and test new abstractions

Possible Research Questions

  • What influence do different abstraction rules have on the results?
  • Which abstraction rules can be combined in a useful way?

Related Work

  • Publications in the area of code search and code-to-code search also use abstractions.
  • Publications using transformation/abstraction rules on code.

P/B/M Search-pattern creator (Neumüller, Tichy)

Context
We are convinced that automatically detecting algorithm implementations in a code base can be helpful to gain knowledge about, which concerns are present in the code base, how they are solved and which components are involved. This knowledge can then support the tasks of software comprehension, software architecture recovery and software maintenance. Our envisioned solution consists of a Domain Specific Language (DSL) designed to describe key features of an algorithm, a search algorithm to find these features and a set of “ready to use” descriptions for common algorithms. Examples for algorithms which could be interesting to detect and some of the insights their detection provides:

  • Quicksort -> The application sorts data structure x.
  • A* -> The application does path search.
  • Raft (Consensus Algorithm) -> The application is a distributed, fault-tolerant system.

Problem

The prototype is a currently a command line based and offers no user interface. We want to support the creation of search-patterns by users with such an interface. A possible starting point is the creation of a search-pattern based on a piece of source code as reference.

Tasks

  • Develop a solution design
    • (Web App, IDE Plugin …)
    • Interfacing Prototype
  • Implement existing feature ideas:
    • Splitview: code <-> search-pattern
    • Highlighting
    • Generation
    • Test runs on a subset of the code base
  • Devise other usefull features

Possible Research Questions

  • How can the creation of search-patterns by users be supported?
  • How helpful are certain features?

Related Work

  • Publications in the area of code search and code-to-code search which present their UI and features for supporting the creation of search patterns.
  • Publications in the area of DSL engineering focussing on these aspects.

P/B/M Debugging Visualizer (Neumüller, Tichy)

Context
We are convinced that automatically detecting algorithm implementations in a code base can be helpful to gain knowledge about, which concerns are present in the code base, how they are solved and which components are involved. This knowledge can then support the tasks of software comprehension, software architecture recovery and software maintenance. Our envisioned solution consists of a Domain Specific Language (DSL) designed to describe key features of an algorithm, a search algorithm to find these features and a set of “ready to use” descriptions for common algorithms. Examples for algorithms which could be interesting to detect and some of the insights their detection provides:

  • Quicksort -> The application sorts data structure x.
  • A* -> The application does path search.
  • Raft (Consensus Algorithm) -> The application is a distributed, fault-tolerant system.

Problem

Understanding why a search-pattern does not match a piece of code can be difficult because:

  • ASTs get large quickly
  • Backtracking in the matching process is a mental load
  • The matching can fail for different reasons

We want to improve the debugging support for search-patterns. Currently the initial version of a standalone Visualizer exists. The Visualizer uses information logged in the matching process to visualize the matching in a step-wise manner.

Tasks

  • Improve the existing Visualizer
  • Improve the logging inside the prototype
  • Feature ideas:
    • Incorporate Filter options, e.g., by node type
    • Highlighting
      • Code <-> search-pattern
      • Rightclick->jump to
    • Backtracking Tree-View
      • One entry for each Backtracking

Possible Research Questions

  • How can the debugging/explainability of the matching process be supported?
  • Which features are especially useful for this?

Related Work

  • Publications in the area of debugging/explaining of subtree or graph matching approaches:

 

M: User study: code search (Neumüller, Tichy)

Context
We are convinced that automatically detecting algorithm implementations in a code base can be helpful to gain knowledge about, which concerns are present in the code base, how they are solved and which components are involved. This knowledge can then support the tasks of software comprehension, software architecture recovery and software maintenance. Our envisioned solution consists of a Domain Specific Language (DSL) designed to describe key features of an algorithm, a search algorithm to find these features and a set of “ready to use” descriptions for common algorithms. Examples for algorithms which could be interesting to detect and some of the insights their detection provides:

  • Quicksort -> The application sorts data structure x.
  • A* -> The application does path search.
  • Raft (Consensus Algorithm) -> The application is a distributed, fault-tolerant system.

Problem
In order to further underpin the necessity/usefulness of our algorithm detection approach we want to investigate how students would otherwise search for algorithms implemented in a code base with a user study. Additionally, the study will help us to gain insights into which expectations/requirements users have towards algorithm detection in order to be useful for them.

Tasks

  • Design a user study
    • Specify research questions and a procedure
    • Select algorithms
  • Prepare the user study
    • Gather code bases implementing the algorithms and "control" code bases
    • Select tools provided to the users (eg. the IDE and a specialized search tool)
  • Trial-run the user study
  • Conduct the user study
  • Analyze the results (encode, transcribe, statistics ...)

Possible Research Questions

  • How do developers search for algorithms contained in a code base?
    • Which search strategies are employed?
    • How long did users search till ... (they found one | they found x algorithms | they stopped looking.)
  • Demographic Question:
    • Which tool are/have been used in the past?
    • Have participants searched for algorithms in the past?
    • Which kind of assistance would users find helpful?

Related Work

  • Literature on case studies:
    • Yin, R. K. (2009). Case study research: Design and methods
    • Case Study Research in Software Engineering - Guidelines and Examples. Wiley 2012, ISBN 978-1-118-10435-4
    • Experimentation in Software Engineering, https://doi.org/10.1007/978-3-642-29044-2
  • Literature on code search:

Contact

Denis Neumüller

Domain Specific Languages

Context
Feature-modeling tools use several different formats which induces addtional effort for researchers and practitioners. Within the MODEVAR initiative, researchers around the globe develop the Universal Variability Language (UVL) which is a textual format for specifying feature models.

Problem
UVL should be readable and editable in text format. To make editing more of a breeze, edit support, such as syntax highlighting is required. One prevalent way for language support are Language Server Protocols (LSPs) which can be more easily embedded in modern IDEs.

Tasks

  • Implement Language Server Protocol (LSP)
  • Embed in your favorite IDE
  • Allow syntax highlighting
  • Classify errors and provide readable messages

Related Work

Contact

Chico Sundermann, Thomas Thüm

Graphs

Context

Representing information in a graph like manner has become the norm for many application domains. Be it “social graphs”, as used by Facebook and other social media platforms, or “knowledge graphs” used to connect words and meanings for search engines and question-answer systems like Amazon Alexa, Siri or WolphramAlpha, or the standard path graphs used for routeplaning.
As a result, querying and manipulating graph structures is an ever present task in many software systems. Many domain specific languages (DSLs) have thus been developed to tackle this task such as GraphQL, Gremlin or Cipher in neo4j.
Domain specific languages have the advantage of having a concise syntax tailored to the task at hand.

Problem

Current approaches are either stand-alone tools or integrate poorly into the general purpose programming languages (GPLs) used to develop complete software systems. This hampers development where data from graphs needs to be integrated into the control flow of the developed system. There is therefore a need to bridge the gap between graph querying DSLs and GPLs that allows seamless integration of the domain expressiveness of DSLs into the host programming languages. Much like LINQ in C# does this for SQL.

Task/Goal

  • Design 1-3 approaches for representing graph queries in a 3rd gen GPL
  • Implement integration approaches in prototypes
  • Evaluate usability and performance of the prototypes against each other

Contact

Stefan Höppner

Enhancing Collaborative Modeling

Context
We are convinced that (graphical) modeling is a cooperative and explorative process done by domain experts. However, several studies identified an insufficient collaboration support of graphical modeling tools. Therefore, we develop a new collaboration approach for graphical modeling tools that is based on the persistence of sequential edit operations (also called operation-based approach). We aim to enable both synchronous as well as asynchronous collaboration and improve the comprehensibility of evolving models.

Problem
At the present stage of our research we persist every kind of edit operation a user has performed to alter the model and present the result in a simple directed acyclic graph (DAG). We are able to filter the edit history by the type of operation or the target of an operation. However, we can not formulate more advanced queries. For instance: "Show only refactoring operations performed by Alice during the last two weeks within this area of the model."

Tasks

  • Develop or extend query language (QL) covers the following dimensions:
    • Syntax, e.g., type of element
    • Semantic, e.g., fulfilment of a requirement
    • Meta information, e.g., time or user
    • Edit operations, e.g., type of edit operation
  • QL should be interactive and should provide live feedback.
  • Conduct a user study to evaluate the user experience of your implementation.

Related Work

Contact

Jakob Pietron

M: Query language for model edit histories (Pietron, Tichy)

Context
We are convinced that (graphical) modeling is a cooperative and explorative process done by domain experts. However, several studies identified an insufficient collaboration support of graphical modeling tools. Therefore, we develop a new collaboration approach for graphical modeling tools that is based on the persistence of sequential edit operations (also called operation-based approach). We aim to enable both synchronous as well as asynchronous collaboration and improve the comprehensibility of evolving models.

Problem
In the context of synchronous collaboration it can happen that two or more users make changes within the same area of a graphical model. This might lead to visually interfering edit operations, e.g., Alice edits the value of a property Prop1 while Bob moves BlockA which contains Prop1. Also semantically conflicting edit operations, such as Bob deletes BlockA instead of moving it, can have a negative impact to the user experience.

We assume that the negative impact of those interfering edit operations can be avoided be implicitly create a temporary branch that delays interfering edit operations of other users.

Tasks

  • Systematically identify different types of be interfering edit operations
  • Develop an algorithm to detect interfering edit operations
  • Implement a solution that uses your algorithm and is able to temporary delay other users edit operations.
  • Conduct a user study that evaluates the impact of your approach on the user experience.

Related Work

Contact

Jakob Pietron

P/B: Reducing of visually interfering edit operations (Pietron, Tichy)

Relaxed Conformance Editing

Context

Graphical modeling is a widely used task in software and systems engineering. Similar to how an IDE assists with programming, graphical modeling tools are intended to help create models as efficiently as possible.
Basically, two types of graphical modeling tools can be distinguished: Either the tool is tailored to a graphical language and restricts the user in drawing in such a way that only syntactically correct models can be drawn (correct-by-constructionn approach), or one has a pure drawing tool that offers no language-specific support but allows maximum freedom. As so often, the optimum lies somewhere in between.

Problem

In this master thesis, a prototypical implementation of a graphical modeling tool in React is to be adapted in such a way that it is possible to turn various support mechanisms (and also restrictions) on or off.
A user study will then be conducted with this customizable tool, with the goal of finding the sweet spot between maximum restriction and maximum freedom. In order not to make the study too large, only a few useful combinations will be compared.

Task/Goal

  • Familiarization with the corresponding tool
  • Development and implementation of meaningful support or restriction options
  • Conducting a user study (study design, creating user tasks, implementation, evaluation)

Needed skills

  • Javascript/Typescript knowledge
  • Experiences with React
  • Interest in usability and study design

Further reading

Contact

Alexander Raschke

Context

Probably everyone has had to create graphical models as part of their studies. Class diagrams, ER diagrams, state machines or sequence diagrams are popular. There are also a variety of modeling tools for this purpose, although the usability usually "takes some getting used to". Among other things, this is due to the fact that many modeling tools only allow the creation of correct models. This means, for example, that arrows must always be connected to a start and end node. However, this type of modeling often limits you or makes it more cumbersome to use.

In graphic drawing tools like Illustrator, Inkscape but also Powerpoint this restriction does not exist. However, the drawn shapes cannot be recognized as model elements and processed if necessary. One idea to counter this problem is the so-called "Relaxed Conformance Editing", which, as the name suggests, does not always require metamodel-conform graphical representations.

Problem

As part of a master's thesis, an implementation of the concepts of relaxed conformance editing has been developed. This implementation, called CouchEdit, consists of a backend that implements the basic concepts and a prototypical frontend that serves to demonstrate the functions of the backend. This backend takes arbitrary graphical elements and attempts to abstract or parse the model from them, for example by considering spatial positions relative to each other. The gathered information is used to generate suggestions such as "Make this a component of other element". Currently, these suggestions can only be accessed via the context menus of the elements. There are no visual hints that suggestions are available and there also is no visualization of which elements are referred to by a suggestion. So if there are multiple equal suggestions, the context menu has the same entry multiple times and there's no way to tell what effect each of them would have. So in summary there's a lack of proper visualizations for interacting with suggestions.

Task / Goal

  • Develop visualization concepts for the interaction with relaxed conformance editing
  • Implement the developed visualization concepts as a prototype or into the frontend of CouchEdit
  • Evaluate the developed visualization concepts

Related Work

  • Leander Nachreiner, Alexander Raschke, Michael Stegmaier, Matthias Tichy
    CouchEdit: A Relaxed Conformance Editing Approach
    MLE ’20: 2nd International Workshop on Modeling Language Engineering and Execution 
    DOI 10.1145/3417990.3421401

Contact

Michael Stegmaier

Self-adaptive Systems

Context

Today, software engineers are developing systems with the ability to autonomously make decisions about their structure and behaviour at runtime – so-called self-adaptive systems. Decisions that these systems make range from provisioning and releasing compute nodes in cloud or container systems, such as Googles container orchestration system Kubernetes, to selecting collision-free flight trajectories of drone swarms.
Reconfigurations are typically designed as rules containing preconditions on when to react and a execution component that defines how the system is supposed to restructure when the preconditions are met.

Problem

Most current approaches consider reconfiguration rules independently of each other. This may lead to contradictory or non-optimal behaviour, e.g., oscillations between rule applications or downstream execution that could just as well be executed earlier. Moreover the opaqueness of the decision making process within the system is a impediment during both development and operation.

To combat these limitations, we are currently developing a self-adaptive system based on the Palladio-Slingshot platform. The system aims to improve on the state of the art by providing coordination between rules and explanations of reconfiguration decisions.

Task/Goal

  • Extend Palladio to allow the implementation of rule coordination
  • Design interfaces for communication between system components (coordination and explanation)
  • Implement basic rule analysis for rule coordination
  • Implement first and second level rule coordination

Contact

Stefan Höppner

Context

Today, software engineers are developing systems with the ability to autonomously make decisions about their structure and behaviour at runtime – so-called self-adaptive systems. Decisions that these systems make range from provisioning and releasing compute nodes in cloud or container systems, such as Googles container orchestration system Kubernetes, to selecting collision-free flight trajectories of drone swarms.
Reconfigurations are typically designed as rules containing preconditions on when to react and a execution component that defines how the system is supposed to restructure when the preconditions are met.

Problem

The opaqueness of the decision making process within the system is a impediment during both development and operation.

To combat these limitations, we are currently extending a self-adaptive system based on the Palladio-Slingshot platform. The system aims to improve on the state of the art by providing understandable explanations (through text or graphical visualisations) of reconfiguration decisions.

Task/Goal

  • Extend Palladio with a component for generating post-mortem explanations
  • Design suitable explanation representations
  • Implement basic data extraction for explanations
  • Implement first explicit explanations based on extracted data

Contact

Stefan Höppner

Software Configuration

Analyzing Product Lines with #SAT

Context
A #SAT solver computes the number of satisfying assignments of a propositional formula. This number is required for a variety of problems in different domains. For example, #SAT solvers enable a high number of analyses on feature models. However, #SAT is a computationally complex task and widely regarded as harder than SAT.

Problem
For many feature-model analyses dependent on counting, a high number of #SAT invocations is required. For instance, some analyses require the count for every single feature (up-to ten thousands in the industry). With current #SAT solvers, a computation is reqiured for each of those features. Reusing information between such invocations may reduce the required runtime.

Tasks

  • Develop concept for variational #SAT
  • Possible options:
  1. Develop your own tooling
  2. Adapt existing solver
  • Empirically evaluate variational #SAT solver

Related Work

Contact

Chico Sundermann, Thomas Thüm

 

Context
A #SAT solver computes the number of satisfying assignments of a propositional formula. This number is required for a variety of problems in different domains. For example, #SAT solvers enable a high number of analyses on feature models. However, #SAT is a computationally complex task and widely regarded as harder than SAT.

Problem
#SAT solvers perform differently depending on the given feature model. There seems to be no one-solver-fits-them-all solution. Thus, it is beneficial to switch between solvers according to the input which have been applied to regular SAT with large sucess. However, it is not trivial to determine which solver is the most efficient given a feature model.

Tasks

  • Gather promising #SAT solvers
  • Analyze structural properties of feature models
  • Develop heuristic(s) to select solvers depending on structure
  • Empirically evaluate heuristic(s)

Related Work

Contact

Chico Sundermann, Thomas Thüm

 

Feature Model Analysis

Context

A feature model of a configurable system can contain several anomalies, such as dead features, false-optional feature, or redundant constraints. There exist automated analyses for detecting these kinds of faults.

Problem

While many anomalies can be detected automatically, fixing them often requires a decision by a user on how to resolve the problem. The aim of this thesis is to investigate how and to what degree this process can be automatize.

Tasks

  • Compare and discuss suitable strategies for cleaning (e.g., which redundant constraints to remove)
  • Implement promising strategies in FeatureIDE

Contact

Sebastian Krieter

Knowledge Compilation

Context
Propositional formulas are prevalent in a variety of computer science domains.  Such formulas are typically evaluated with SAT solvers which commonly operate on conjuctive normal form (CNF) due to its beneficial properties.

Problem
A large variety of translation techniques to CNF have been considered in the literature which typically result in semantically equivalent but different CNFs. It has been shown that the performance of SAT/#SAT solvers are heavily dependent on the resulting CNF. The goal of this work is to compare several CNF translation techniques. Furthermore, the runtime of SAT and #SAT solvers when given the different CNFs shall be examined.

Tasks

  • Research on CNF translation techniques
  • Implement CNF translation techniques
  • Implement comparison benchmark for CNFs

Related Work

Contact

Chico Sundermann, Thomas Thüm

Context
A d-DNNF is a normal form for propositional formulas that allows faster queries for certain analyses. For example, a d-DNNF representing a feature model allows to compute the number of valid configurations within polynomial time. However, compiling any formula and, thus, a feature model to d-DNNF is computationally expensive.

Problem
Feature models are typically evolving over time. After a change, it may be beneficial to adapt the existing d-DNNF instead of compiling the entire formula again. Your task is to incrementally adapt an existing d-DNNF according to changes in the feature model.

Tasks

  • Handle changes performed on CNF incrementally
  • Handle changes performed on feature model incrementally
  • Implement prototype
  • Empirically evaluate the benefits


Related Work

Contact

Chico Sundermann, Thomas Thüm

Context
A d-DNNF is a target format of knowledge compilation that can be used, inter alia, for linear-time counting.

Problem
While the compilation to d-DNNF is well researched, algorithms for exploitation of d-DNNFs are mostly limited to counting. Therefore, it is currently unknown which feature-model analyses are generally tractable (i.e., have a polynomial time complexity) for d-DNNFs.

Tasks

  • Collect existing feature-model analyses
  • Analyze applicability of analyses on d-DNNFs
  • Develop algorithms that exploit the structure of d-DNNFs
  • Implement algorithms
  • Empirically evaluate your implementation

Related Work

Contact

Chico Sundermann, Thomas Thüm

ddueruem-web is a RESTful (web)service for ddueruem, which acts as an interface to (legacy) BDD libraries. FeatureIDE is an IDE for model-driven software development that is principially developed by our working group.
The goal of this project is the integration of the two tools via the RESTful API of ddueruem-web. Work on this project may also be conducted as part of a Bachelor's thesis.

Individual points of emphasis and own ideas are highly appreciated.

The project can be conducted as a 8, 12, or 16 LP project,.

Contact
Tobias Heß, Thomas Thüm

Constraint-Programmierung und Constraint Handling Rules

Constraint Handling Rules

We are developing a rule-based implementation of a tool to analyse and generate graphs. It is used in the domain of mason’s marks. For thousands of years, stonemasons have been inscribing these symbolic signs on dressed stone. Geometrically, mason’s marks are line drawings. They consist of a pattern of straight lines, sometimes circles and arcs. We represent mason’s marks by connected planar graphs. Our prototype tool for analysis and generation of graphs is written in the rule-based declarative language Constraint Handling Rules. One or several of following features could be improved in this proposed work:

Goals/Tasks

  • improve the vertex-centric logical graph representation, i.e. adding arcs, colors, labels,
  • encode existing mason marks either by hand, from images or import from existing databases,
  • recognize (sub)graphs and patterns in a graph, in particular (self-)similarities and correlations between graphs,
  • perform classical algorithms on graphs like shortest paths,
  • derive properties and statistics from graphs,
  • generate (randomly or exhaustively) and draw graphs from given constrained subgraphs based on properties and statistics.

References

Prerequesites

  • Good knowledge of Prolog and CHR
  • Lecture Rule-based Programming

Contact

Thom Frühwirth, Sascha Rechenberger

P/B/M: Graph Tool for Mason Marks (Rechenberger, Frühwirth)

When algorithms are written in CHR, constraints represent both data and operations. CHR is already incremental by nature, i.e. constraints can be added at runtime. Logical retraction adds decrementality. Hence any algorithm written in CHR with justifications will become fully dynamic. Operations can be undone and data can be removed at any point in the computation without compromising the correctness of the result.

A straightforward source-to-source transformation can introduce justifications for user-defined constraints into the CHR. Then a scheme of two rules suffices to allow for logical retraction (deletion, removal) of constraints during computation. Without the need to recompute from scratch, these rules remove not only the constraint but also undo all consequences of the rule applications that involved the constraint.

Goal

Further work should investigate implementation, dynamic algorithms and application domains of CHR with justifications:

  • research how logical as well as classical algorithms implemented in CHR behave when they become dynamic.
  • improve the implementation, optimize and benchmark it.
  • support detection and repair of inconsistencies (for error diagnosis), - support nonmonotonic logical behaviors (e.g. default logic, abduction, defeasible reasoning).

References

Prerequisites

  • Good knowledge of Prolog and CHR
  • Lecture Rule-based Programming
  • Interest to learn about formal analysis methods of rule-based languages

Contact

Thom Frühwirth, Sascha Rechenberger

P/B/M: Justifications in CHR for Logical Retraction in Dynamic Algorithms (Rechenberger, Frühwirth)

Extend the analysis techniques and/or the associated tool from the following two research papers:


A dynamic program analysis of the non-termination problem for recursion in the Constraint Handling Rules (CHR) language: A simple program transformation for recursive rules in CHR was introduced that produces one or more adversary rules. When the rules are executed together, a non-terminating computation may arise. It was shown that any non-terminating computation of the original rule contains this witness computation.

References


A static program analysis of the non-termination problem for recursion in the Constraint Handling Rules (CHR) language: Theorems with so-called misbehavior conditions for potential non-termination and failure (as well as definite termination) of linear direct recursive simplification rules are given. Logical relationships between the constraints in a recursive rule play a crucial role in this kind of program analysis.

References


Prerequesites

  • Lecture "Rule-Based Programming"

Contact

Thom Frühwirth, Sascha Rechenberger

B/M: Non-Termination Analysis of Recursive Rules (Rechenberger, Frühwirth)

In distributed computation, data and processes are distributed over a network of stores and processing units. In a constraint-based programming language paradigm this means that constraints have to be annotated with spatial information defining their whereabouts. Obvious topologies are a distinction between global and local stores as well as trees. Localized constraints can also be used for so-called reified (or meta-)constraints (e.g. https://sicstus.sics.se/sicstus/docs/4.0.8/html/sicstus/Reified-Constraints.html), to store justifications and for spatial reasoning.

In Constraint Handling Rules (CHR), there is a simple source-to-source program transformation that adds local annotations to constraints.

The scope of the work includes implementation of such a transformation, their application and/or static program analysis to derive distribution patterns, i.e. to localize constraint computation while minimizing communication overhead.

References

Prerequesites

  • Lecture "Rule-Based Programming"

Contact

Thom Frühwirth, Sascha Rechenberger

P/B/M: Localized Constraint Stores (Rechenberger, Frühwirth)

Invariants (or assertions, properties, conditions) annotate program text and express static and dynamic properties of a program's execution. Invariants can be expressed as logical relations (predicates) over the program's variables. In the context of constraint-programming and Constraint Handling Rules (CHR), they amount to constraints. These can be readily added to the program to enforce the invariants. By comparing the program with and without invariants expressed as constraints using established program analysis techniques for CHR, namely confluence and program equivalence, we can check if the invariants hold in the program.

Furthermore, invariants can be strenghened and even be generated by adapting the so-called completion method (that is normally used to generate additional rules to make a CHR program confluent).

References

Prerequisites

Contact

Thom Frühwirth, Sascha Rechenberger

Program slicing is a program anaylsis technique whereby one extracts properties and relationships of variables in a program by removing from the program all statements that do not effect the assignments of the variables. In the context of constraint programming and Constraint Handling Rules that deal with logical relations (predicates) this amounts to the logical operation of variable projection. This means that we remove unwanted variables that are not of interest from the program by program transformation. This transformation can be accomplished by adapting the technique of "completion". It is usually used to make a non-confluent program confluent.

References

Prerequisites

  • Lecture "Rule-based Programming

Contact

Thom Frühwirth, Sascha Rechenberger

B/M: Program Slicing by Confluence and Completion (Rechenberger, Frühwirth)

Prolog (WAM) and then Java (JVM) popularized the concept of an abstract (or virtual) machine to implement programming languages in a systematic, portable yet efficient way. Such a machine shall be developed for CHR.

Goals

Define the abstract code instructions for CHR and to implement them.

Prerequesites

  • Good knowledge of Prolog and CHR
  • Lecture Rule-based Programming
  • Lecture Compiler Construction (Compilerbau) (optional but very helpful)

Contact

Thom Frühwirth, Sascha Rechenberger

Repeated recursion unfolding is a new approach that repeatedly unfolds a recursion with itself and simplifies it while keeping all unfolded rules. Each unfolding doubles the number of recursive steps covered. This reduces the number of recursive rule applications to its logarithm at the expense of introducing a logarithmic number of unfolded rules to the program. Efficiency crucially depends on the amount of simplification inside the unfolded rules. A super-linear speedup is provably possible in the best case, i.e. speedup by more than a constant factor. The optimization can lower the time complexity class of a program.

Goals

The goal is to implement this optimization scheme as a program transformation in the programming language of choice. If necessary, the scheme should be transferred from recursion to iteration constructs such as loops.

References

Prerequisite

  • Excellent knowledge and programming skills in the choosen programming language.

Contact

Thom Frühwirth, Sascha Rechenberger

The declarative programming language Constraint Handling Rules (CHR) is designed as a language extension to other, not necessarily declarative programming languages. There are existing implementations for Prolog, C, Java, JavaScript, and others. Since there still plenty of languages for which there is no implementation, or at least no maintained one, and since the problems that can be tackled using CHR are plentiful (think of any problem including the simplification of constraints, or derivation of new from existing information), we want to work on spreading CHR to those languages as well, by designing and (prototypically) implementing runtime environments (RTEs) for CHR in those languages still lacking a CHR implementation.

Goals

  • Design a runtime environment for CHR, which is able to deal with the specific features of the language of your choice. This may includes implementing logical variables, if they are not already a feature of the language.
  • Design translations schemes from CHR to your language of choice
  • Implement a prototype of your RTE, and test it extensively with (manually) translated CHR programs, as well as unit tests.
  • (additionally for Masters theses/projects) Implement an embedding of CHR into your language of choice. This may be a compiler, a macro system, or an embedded domain specific language (EDSL); whatever your language offers in this regard.

References

Prerequesites

  • Interest in programming language design and (to some extend) compiler construction.
  • Good programming skills and knowledge of the inner workings of CHR and the programming language of your choice.

Contact

Sascha Rechenberger

Data-Oriented Programming (DOP) is a programming paradigm that evolved from Object-Oriented Programming (OOP) and Functional Programming (FP). The main principles of DOP are

  • the separation of code and data (in contrast to OOP), i.e, functions are not rigidly linked to a user-defined data-type
  • data is always immutable
  • the use of generic data structures, instead of user-defined data-types. E.g., instead of defining a data-type (class) with different fields, dictionaries (heterogenous maps) are used

Those principles make dynamically typed languages like LISP-dialects or JavaScript-derivates ideal for this paradigm, and in fact, a major representative of data-oriented languages is the fairly modern LISP-dialect Clojure. On the other hand, it is almost impossible to keep true to all of those principles in most statically typed languages like Java or Haskell (mostly because of the use of generic data structures).

This comes with a price, though: since we use dynamic-typing, we can never guarantee at compile time, that a dictionary, for example, has the field a function needs to work with it. Languages like TypeScript or PureScript solve this, by beeing able to give partial type annotations for JSON-like objects. Such an approach can be interpreted as a constraint-based type system, where a data-object has to satisfy constraints of the kind "has field X of type T" where X is a key of some sort, and T a data-type.

Since Prolog also offers dictionaries, is a dynamically typed language, and offers a powerful macro-system, it is a perfect playground to experiment with such an approach. Thus, we want to implement an annotation system for Prolog predicates, that gives the programmer the option to add type-annotations to a predicate, that are checked at compile time, and then, if successfully checked, removed.

Goals

  • Design a contraint-based type-system for DOP in Prolog
  • Implement a type-checker for said type-system using Prolog and Constraint Handling Rules
  • Desing user-friendly type-annotations for this type-system

Prerequesites

  • Lecture Rule-Based Programming (strongly recommended)

References

Contact

Sascha Rechenberger