Research Projects

Current Projects

Change Theory and Variation Representation
Managing variation is an important problem in software engineering that takes different forms, ranging from version control and configuration management to software product lines. Our recent work in this area focuses on the choice calculus, a fundamental representation for software variation that can serve as a common language of discourse for variation research, filling a role similar to lambda calculus in programming language research. The goal of this project is to develop a theory of change for structured objects that provides principles for sound change management and serves as a foundation for more sophisticated versioning tools.

Explanation-Oriented Programming
The goal of this project is to investigate the concept of explanation and to derive from it principles for explanation-oriented programming, which can be applied in three major ways. First, we can design domain-specific languages to build explanations for specific domains that are traditionally hard to understand. Second, we can identify the notion of "explainability" as a language design criterion in the sense of the cognitive dimensions framework. The language designer can then use this principle in designing basic language structures and constructs in a way that lead to programs that have a higher degree of explainability. Third, we can think about changing the objective in the design of general-purpose languages. Currently, the purpose of a program is to compute a value or an effect. Whenever a program fails to meet the expectations of a user, the question is "Why did this happen?", and "What went wrong?". In such a situation we typically have to recourse to debuggers to understand how the value or effect was produced, which is often a very tedious process. The idea od explanation-oriented programming is to design languages in a way so that the language constructs produce not only values, but also explanations of how and why the values are obtained.

Adapdation-Based Programming
The goal of this project is to enable a programmer to write code that learns to "do the right thing" after repeated executions. This ability is necessary when the program is complex and optimal program behavior is hard to encode. In other words, we want to make it easy for programmers to write adaptive code that learns to solve complex problems optimally. Our focus is on usability and performance, which for the programmer means getting the benefits of cutting-edge ideas from Machine Learning without having to learn any of it.

Recent Projects

Gencel/ClassSheets: Automatic Generation of Correct Spreadsheets
We have created an extension to Excel, called Gencel, that is based on the concept of a spreadsheet template, which captures the essential structure of a spreadsheet and all of its future evolutions. Such a template ensures that the spreadsheet can be changed only in the the anticipated ways, so that spreadsheets evolving from templates will provably never contain any reference, range, or type errors. Gencel can help to reduce maintenance costs while at the same time it dramatically increases the level of correctness and reliability of spreadsheets.

GoalDebug: Goal-Directed Debugging of Spreadsheets
The idea behind GoalDebug is to allow the spreadsheet user to express expectations about cell values using a simple interface. The system uses this information to compare the expected data with the data computed by formulas in the spreadsheet and creates a ranked list of suggestions for how to change cell formulas.

UCheck: A Spreadsheet Type Checker for End Users
The goal of this project is to develop type systems for spreadsheets that (i) offer the advantages of static typing and are (ii) still usable by end users. To this end we have defined a unit system for spreadsheets that allows to reason about the correctness of formulas in concrete terms, which is achieved by using concrete values from the spreadsheet, for example, headers, as types (or units). A particular focus of our work is the flexibility of the unit system, both in terms of error reporting and adaptability of reasoning rules, to achieve a high acceptance among end users.

Probabilistic Functional Programming
The PFP library is a collection of modules for Haskell that facilitates probabilistic functional programming, that is, programming with stochastic values. The probabilistic functional programming approach is based on a data type for representing distributions. A distribution represent the outcome of a probabilistic event as a collection of all possible values, tagged with their likelihood. A nice aspect of this system is that simulations can be specified independently from their method of execution. That is, we can either fully simulate or randomize any simulation without altering the code which defines it.

Older Projects

Update Programming
This project is concerned with the application of program transformationand meta programming techniques to the problem of software maintenance and reuse. Our goal is to develop languages in which update programs can be written that can perform software changes automatically. An important aspect is that these update programs should preserve properties of the programs they change, such as syntax or type correctness.

Program Generation for Ocean Modeling
We are developing a program generator that can create simulation programs for ocean models depending on a characterization of these models in form of a set of parameters. To this end, we have designed and implemented a domain-specific language (DSL) to describe ocean modeling tools. Tool descriptions are translated into Fortran 90 programs. One focus in the design of the DSL is safety, that is, the DSL compiler guarantees that generated Fortran programs are syntactically correct and, to a large degree, also type correct.

Spatiotemporal Query Languages
We have designed a data model to represent spatiotemporal data, that is, geometric information that changes over time. Based on an abstract data type modeling approach, we have designed query languages to express inquiries about such data. Adding a temporal dimension to spatial data creates a huge space of possible relationships and dependencies between spatiotemporal objects that offers a wealth of different language designs that are still to be explored. In addition to traditional textual query languages, we are also developing visual query languages to simplify the construction of queries for end users.

XML for End Users
We are developing an XML query and transformation language that is particularly targeted at end users who have no formal training in databases or programming. The language is based on a document metaphor and allows simple selections in the style of "query-by-forms" as well as more sophisticated transformations that are expressed by so-called document rules. We are currently developing a graphical user interface to aid the construction of queries. We also investigate the automatic generation of XML transformations to help users to integrate different XML data sources.

Functional Programming with Graphs
Taking an inductive view of graphs facilitates the recursive definition of graph algorithms. One advantage of this approach over others is that the design of algorithms can proceed in a more declarative fashion; in particular, we do not have to care about node markings that are inherent in the imperative style of graph algorithms and that complicate the reasoning about programs considerably. The convenient formulation of recursive graph algorithms builds on a special kind of pattern matching that allows to extract particular representations from an abstract data type.

Semantics of Visual Languages
In this project we have investigated formalisms to formally define the meaning of visual languages. A key step is the identification of an appropriate level of abstract visual syntax. We have also investigated ways to specify the semantics of visual languages visually.

Folds for Abstract Data Types
Generalized fold operations were originally introduced for data types as found in Haskell or ML (which correspond to free term algebras). The scope of folds can be extended to abstract data types if an ADT is represented by a pair consisting of a constructor and a destructor, which are essentially functions to/from a common representation. Then a fold can work on an ADT by applying parameter functions to values that are delivered by the ADT's destructor. Fold operations that use as a parameter the constructor of another ADT, called ADT transformers,play an important role and offer a concise programming style. Several laws for ADT folds and transformers exist that can be used for program optimization and verification.

Data Models for Spatial Databases
This project is concerned with the development of data models and query languages to support the representation of spatial data in databases. We have investigated models based on partitions that can serve as a fundamental core model for spatial data. We have also investigated representations for imprecise data and graphs.

last change: January 26, 2012 Martin Erwig