Sebastian Fischer

I am currently a freelance computer scientist teaching computer science teachers in northern Germany and working on improving the Darcs version control system for factis research. See my CV for a summary of what I did previously.

Contact

(encryption)

Research Interests

Open Source Projects

I maintain Haskell libraries for

See my github page for a complete list of my open source projects.

Scientific Activities

Talks

Curry Crash Course

presented at University of Bonn, Germany (January 2013) [slides, programs]

I have presented the functional-logic programming language Curry to students at the University of Bonn. My slides are accompanied by Curry programs that we discussed (and partially wrote) during my lecture. The programs archive linked above contains the following Literate Curry files:

On the Laws of Bidirectional Transformations

presented at National Institute of Informatics in Tokyo, Japan (November 2012) [slides]

Bidirectional Transformations (BX), programs that come with an automatic way to reconstruct their input based on their output, are gaining interest in the programming language community. This community has developed laws to accompany BX for programmers to reason about transformations without knowledge of the underlying automatisms. These laws capture intuitions about BX but lack theoretical background beyond such intuitions.

We aim at developing a systematic foundation for BX by relating it to existing mathematical concepts. We investigate the connections between existing laws for BX and standard mathematical concepts, such as injectivity and surjectivity. We find that a certain class of BX is uniquely determined by their backwards transformations which suggests to let programmers specify BX by defining backwards transformations and getting forward transformations for free.

Generate, Test, and Aggregate: An Algebraic Method for Developing Divide-and-Conquer Algorithms

presented at National Institute of Informatics in Tokyo, Japan (March 2012) [slides]

Divide-and-Conquer is an important algorithm design paradigm where a problem is divided into sub-problems that can be conquered individually. Recent opportunities to parallelize computations draw new interest to this paradigm as individual sub-problems can be solved in parallel. For example, the MapReduce framework allows to distribute massively parallel computations based on associative combining operations that leave the necessary freedom to be executed in parallel.

Unfortunately, associative combining operations are often non-trivial and there is little support helping programmers to define them. I will present a method that facilitates the implementation of parallel algorithms in divide-and-conquer style by helping programmers to define complex associative combining operations based on more intuitive specifications in generate-test-and-aggregate style. The method has firm algebraic roots and functional programming will be helpful in explaining it based on program calculation.

presented at University of Tsukuba, Japan (March 2012) [slides]

Functional Logic Programming (FLP) combines features from functional programming such as first-class functions and algebraic datatypes with features from logic programming such as unbound logic variables and nondeterministic search. I will introduce lazy (call-by-need) FLP using the Curry language and review different ways to encapsulate search, that is, to access different results of nondeterministic computations deterministically. The interaction of laziness and encapsulated search is an old problem with some new solutions in the FLP community. By talking about both the problem and some existing solutions, I hope to motivate discussion on the topic from the perspective of control operators in the presence of call-by-need.

A Haskell EDSL for (Parallel) Programming in Generate-Test-and-Aggregate Style

presented at Chalmers University of Technology in Gothenburg, Sweden (November 2011) [slides]

MapReduce is a popular and successful framework to implement massively parallel algorithms. It can be used to distribute the execution of data intensive tasks and hide implementation details of parallelization and data distribution. However, it is often difficult to define MapReduce programs because realistic problems do not match its simple divide and conquer form. Although many case studies are being published that show non-trivial applications of MapReduce, no generalized theory has been developed that captures underlying common ideas.

I will present a framework for systematic parallel programming with MapReduce that generalizes existing implementation ideas for parallel algorithms and is applicable to a wide class of search problems. Parallel algorithms can be specified as generate-and-test problems combined with result aggregation and we provide two theorems that allow to implement such specifications efficiently using MapReduce. Our approach brings MapReduce programming, which is inspired by the map and reduce primitives available in many functional languages, back to its roots by providing a calculation-based framework for program development. It makes expert knowledge applicable for a broader group of programmers by automatically bridging the gap between intuitive specifications and efficient implementations.

Publications

BibTeX entries