| CARVIEW |
Sebastian Fischer
I am currently a freelance computer scientist teaching computer science teachers in northern Germany and developing software for different companies. See my CV for a summary of what I did previously.
Contact
Research Interests
- functional and functional-logic programming languages
- programming with (free) algebraic structures
- languages to describe implicitly parallel computations
Open Source Projects
I maintain Haskell libraries for
- efficient regular expression matching (weighted-regexp),
- generation of bar charts from text files (barchart),
- monadic formulation of search problems (tree-monad, stream-monad, level-monad, explicit-sharing),
- and efficient computation of primes and fibonacci numbers.
See my github page for a complete list of my open source projects.
Scientific Activities
Program Commitee member of the 22nd International Workshop on Functional and (Constraint) Logic Programming, WFLP 2013 in Kiel, Germany
Program Commitee member of the 21st International Workshop on Functional and (Constraint) Logic Programming, WFLP 2012 in Nagoya, Japan
Program Commitee member of the Eleventh International Symposium on Functional and Logic Programming, FLOPS 2012 in Kobe, Japan
Program Commitee member of the ACM SIGPLAN 2012 Workshop on Partial Evaluation and Program Manipulation, PEPM 2012 in Philadelphia, Pennsylvania, USA
Program Commitee member of the 20th International Workshop on Functional and (Constraint) Logic Programming, WFLP 2011 in Odense, Denmark
Talks
A clear picture of lens laws
presented at MPC’15 in Königswinter, Germany (June 2015) [slides]
A lens is an optical device which refracts light. Properly adjusted, it can be used to project sharp images of objects onto a screen; a principle underlying photography as well as human vision. Striving for clarity, we shift our focus to lenses as abstractions for bidirectional programming. By means of standard mathematical terminology as well as intuitive properties of bidirectional programs, we observe different ways to characterize lenses and show exactly how their laws interact. Like proper adjustment of optical lenses is essential for taking clear pictures, proper organization of lens laws is essential for forming a clear picture of different lens classes. Incidentally, the process of understanding bidirectional lenses clearly is quite similar to the process of taking a good picture.
By showing that it is exactly the backward computation which defines lenses of a certain standard class, we provide an unusual perspective, as contemporary research tends to focus on the forward computation.
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:
Mountains.lcurrysolves a problem from a German computer science competition that the students have already been familiar with.Evaluator.lcurrydefines a type for arithmetic expressions which is used to demonstrate how to use Curry’s logic features to implement simplification in an elegant way.Parser.lcurrydefines parser combinators using Curry’s built-in nondeterminism.ExprParser.lcurryuses the defined parser combinators to parse expressions from strings and generate strings for expressions that evaluate to a certain number.Bridge.lcurrysolves a logic puzzle that we discussed over lunch.
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.
Lazy Functional Logic Programming and Encapsulated Search
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
- A clear picture of lens laws —Functional Pearl—. [BibTeX] Sebastian Fischer, Zhenjiang Hu, Hugo Pacheco. Proceedings of the 12th Conference on Mathematics of Program Construction (MPC 2015). Springer Verlag, 2015.
- ‘Putback’ is the Essence of Bidirectional Programming. [BibTeX] Sebastian Fischer, Hugo Pacheco, Zhenjiang Hu. National Institute of Informatics, 2012.
- Generate, Test, and Aggregate — A Calculation-based Framework for Systematic Parallel Programming with MapReduce. [BibTeX] Kento Emoto, Sebastian Fischer, Zhenjiang Hu. Proceedings of the 22nd European Symposium on Programming (ESOP 2012). Springer Verlag, 2012. [extended version]
- Purely functional lazy nondeterministic programming. [BibTeX] Sebastian Fischer, Oleg Kiselyov, Chung-chieh Shan. Journal of Functional Programming. 2011.
- Transforming Functional Logic Programs into Monadic Functional Programs. [BibTeX] Bernd Braßel, Sebastian Fischer, Michael Hanus, Fabian Reck. Proceedings of the 19th International Workshop on Functional and (Constraint) Logic Programming (WFLP 2010). Springer Verlag, 2011.
- A Play on Regular Expressions (Functional Pearl). [BibTeX] Sebastian Fischer, Frank Huch, Thomas Wilke. Proceedings of the 15th ACM SIGPLAN International Conference on Functional Programming (ICFP’10). ACM Press, 2010. [slides, video]
- On Functional Logic Programming and its Application to Testing. [BibTeX] Sebastian Fischer. Dissertation zur Erlangung des akademischen Grades Doktor der Naturwissenschaften (Dr.rer.nat.). Christian-Albrechts University of Kiel, Germany, 2010. [slides, notes]
- The Pull-Tab Transformation. [BibTeX] Abdulla Alqaddoumi, Sergio Antoy, Sebastian Fischer, Fabian Reck. Preproceedings of the Third International Workshop on Graph Computation Models (GCM’10). 2010.
- Reinventing Haskell Backtracking. [BibTeX] Sebastian Fischer. Informatik 2009, Im Fokus das Leben (ATPS’09). GI Edition, 2009. [abstract]
- Purely Functional Lazy Non-deterministic Programming. [BibTeX] Sebastian Fischer, Oleg Kiselyov, Chung-chieh Shan. Proceedings of the 14th ACM SIGPLAN International Conference on Functional Programming (ICFP’09). ACM Press, 2009. [video]
- Data-Flow Testing of Declarative Programs. [BibTeX] Sebastian Fischer, Herbert Kuchen. Proceedings of the 13th ACM SIGPLAN International Conference on Functional Programming (ICFP’08). ACM Press, 2008. [slides]
- EasyCheck – Test Data for Free. [BibTeX] Jan Christiansen, Sebastian Fischer. Proceedings of the 9th International Symposium on Functional and Logic Programming (FLOPS’08). Springer Verlag, 2008. [slides]
- From Functional Logic Programs to Purely Functional Programs Preserving Laziness. [BibTeX] Bernd Braßel, Sebastian Fischer. 2008.
- Lazy Call-By-Value Evaluation. [BibTeX] Bernd Braßel, Sebastian Fischer, Michael Hanus, Frank Huch, German Vidal. Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming (ICFP’07). ACM Press, 2007.
- Preserving Sharing in the Partial Evaluation of Lazy Functional Programs. [BibTeX] Sebastian Fischer, Josep Silva, Salvador Tamarit, German Vidal. Proceedings of the 17th International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR’07). Springer Verlag, 2007.
- Systematic Generation of Glass-Box Test Cases for Functional Logic Programs. [BibTeX] Sebastian Fischer, Herbert Kuchen. Proceedings of the 9th ACM SIGPLAN International Symposium on Principles and Practice of Declarative Programming (PPDP’07). ACM Press, 2007. [slides]
- Declaring Numbers. [BibTeX] Bernd Braßel, Sebastian Fischer, Frank Huch. Proceedings of the 16th Workshop on Functional and (Constraint) Logic Programming (WFLP’07). Elsevier, 2007. [slides]
- Implementing Relational Specifications in a Constraint Functional Logic Language. [BibTeX] Rudolf Berghammer, Sebastian Fischer. Proceedings of the 15th Workshop on Functional and (Constraint) Logic Programming (WFLP’06). Elsevier, 2006.
- Lazy Database Access with Persistent Predicates. [BibTeX] Sebastian Fischer. Proceedings of the 15th Workshop on Functional and (Constraint) Logic Programming (WFLP’06). Elsevier, 2006.
- Resource-Based Web Applications. [BibTeX] Sebastian Fischer. Proceedings of the 7th Symposium on Trends in Functional Programming (TFP’06). Intellect, 2006.
- A Program Transformation for Tracing Functional Logic Computations. [BibTeX] Bernd Braßel, Sebastian Fischer, Frank Huch. Proceedings of the 16th International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR’06). Springer Verlag, 2006.
- A Functional Logic Database Library. [BibTeX] Sebastian Fischer. Proceedings of the 2005 ACM SIGPLAN Workshop on Curry and Functional Logic Programming (WCFLP’05). ACM Press, 2005.
- Functional Logic Programming with Databases. [BibTeX] Sebastian Fischer. Diplomarbeit. Christian-Albrechts University of Kiel, Germany, 2005.