Chalmers Functional Programming Workshop 2010

Date: Wednesday, June 2.
Time: 9.00 - 16.00
Place: Valdemar, student union building

Presenters: Feel free to upload your slides and link from the schedule below. (Or mail them to Emil.)

Schedule:

09.00-09.15		Welcome
		Session 1: Chair: Alejandro
09.15-09.20	Koen Claessen	A puzzle
09.20-09.50	Niklas Broberg	Extended Menu - Data Types a la Carte revisited
09.50-10.20	David Sands	Improvement Theory: A Retrospective
10.20-10.50		Coffee break
		Session 2: Chair: Josef
10.50-11.15	Patrik Jansson	Simple Pure Type System examples
11.15-11.45	Jean-Philippe Bernardy	Parametricity and American Dependent Types
11.45-12.15	Ramona Enache	Machine Translation using Functional Programming and Type Theory
12.15-13.15		Lunch at Hyllan
		Session 3: Chair: Hans
13.15-13.45	Hans Svensson	Mutation testing for Erlang, what are the interesting mutants?
13.45-14.15	Gábor Páli	Measuring Software Complexity by Types
14.15-14.45	Ulf Norell	Making sense of circular programs
14.45-15.15		Coffee break
		Session 4: Chair: Ulf
15.15-15.45	Josef Svenningsson	LR parsing is the derivative of context free grammars
15.45-16.15	Alejandro Russo	Implementing Software Product Lines in Python
16.15-16.30	Koen Claessen	A solution
16.30-16.45		Conclusion

Title: Extended Menu - Data Types a la Carte revisited
Presenter: Niklas Broberg
Abstract: In the JFP paper "Data Types a la Carte", Wouter Swierstra showcased an elegant way to achieve open and composible datatypes and functions through composition of basic functors. In this talk I will explore this idea further, testing its limitations and general applicability. I will discuss polymorphic datatypes as bifunctors, the problem of unfolding, and functions as natural transformations between different (bi-)functors. And none of this will be half as dangerous as the categorical lingo would have you believe.

Links: Wadler's mail about The Expression Problem

Title: Improvement Theory: A Retrospective
Presenter: David Sands
Abstract: One program fragment is an improvement of another if its execution is more efficient in any program context. In this talk we give an overview of our work on the theory and applications of improvement. Applications include reasoning about time and space properties of functional programs, and proving the correctness of program transformation methods.
Title: Simple Pure Type System examples
Presenter: Patrik Jansson
Abstract: I present a little demo / tutorial on pure type systems defining simple lambda terms using the tool Henk2000 implemented by J-W Roorda in 2000 and comparing with current Agda.
Title: Parametricity and American Dependent Types
Presenter: Jean-Philippe Bernardy
Abstract: Parametricity is usually seen as a way to automatically turn types into propositions. In earlier work, we have shown that the same procedure can also turn terms into proofs; and proofs and programs can be expressed in the same (dependently typed) type system. In this talk, I will explore how to use parametricity to enrich the structure of programs and types; such that the type reflects the behaviour of the program. This procedure can live inside a type system with a restricted form of dependent typing. Such type systems are in programming languages such as Omega, She, and recent versions of GHC (via encodings). They are informally known as American Dependent Types.
Title: Machine Translation using Functional Programming and Type Theory
Presenter: Ramona Enache
Co-author: Aarne Ranta
Abstract: We give a brief comparative study of the existing machine translation techniques, and a more comprehensive introduction of GF and its connections to functional programming and more advanced features of type theory, and the advantage that they give over other techniques. An overview on the ongoing European project MOLTO will be given, along with some highlights on its first application and a demo of it.
Title: Mutation testing for Erlang, what are the interesting mutants?
Presenter: Hans Svensson
Co-authors: John Hughes, Michal Palka
Abstract: Mutation testing is a popular topic for Java, C/C++, etc, but it is not used for Erlang. When listening to some presentations at this years ICSE, we got inspired to try it for Erlang. As soon as one starts thinking about the problem however, the question arise, what are interesting mutations for Erlang? It would be (almost) trivial to implement the standard set of mutations (from the C/C++ work), considering arithmetic operations, relational operations,etc. But are those really interesting operations for Erlang, or are there a better choice?
Title: Measuring Software Complexity by Types
Presenter: Gábor Páli
Co-author: Tamás Kozsik
Abstract: In typed programming languages, types play an important role in many aspects of a program, therefore it is very likely that types can be also used as a tool of measuring software complexity. We discuss a potential approach to software measurement techniques for software written in strongly typed, especially functional programming languages. Although there are initiatives for establishing metrics for functional programs, measuring their complexity is still a topic to be explored. We believe it is worth focusing on types themselves when trying to say something about the quality of a software product. We examine the possibilities of describing program quality and complexity through a static analysis of the employed types and derive metrics from them.
Title: Making sense of circular programs
Presenter: Ulf Norell
Author: Conor McBride
Abstract: Lazy languages allows you to write circular programs where the result of a function application appears as an argument in the application. This is different from a recursive program where a function calls itself on different arguments. A famous example of a circular program is the repMin function that replaces all values stored in a tree by the minimum value, only traversing the tree once. A simpler example is the standard fixed point combinator "fix f = x where x = f x". Understanding why a certain circular program works and another one doesn't is a craft akin to magic. In this talk I will introduce the simple concept of the Tomorrow functor, which will let us write circular programs that we can actually understand. We'll look at a few examples, including the repMin function, to see how they actually work. This talk is based on a presentation by Conor McBride.
Title: LR parsing is the derivative of context free grammars
Presenter: Josef Svenningsson
Abstract: In this talk I will show that LR parsing can be seen as the derivative of context free grammars in much the same way as regular expression matching is the derivative of regular expressions as demonstrated by Brzozowski. To this end I will present a new representation for context free grammars which will make the connection to derivatives much clearer. This new representation is interesting in its own right, for instance it is much more compositional than how context free grammars are normally represented.
Title: Implementing Software Product Lines in Python
Presenter: Alejandro Russo
Abstract: A Software product line (SPL) is a set of software systems with well-defined commonalities and variabilities that are early identified in order to reuse as much code as possible. Clear examples of SPL include automotive and mobile phone systems. It is often referred as a limitation to implement SPL in object-oriented languages due to the presence of inheritance. For example, it might occur that some class, in a particular product of the SPL, should not inherit some methods of its super class. It might also be possible that, depending on the product constructed, some methods of a given class should be named differently. I propose a small set of decorators (high-order functions) to precisely control inheritance in Python. By precisely controlling inheritance as well as providing a set of combinators to express relations between software products, it is rather simple the assembly of software characterize by the SPL. This talk shows a library in Python to handle SPL as well as a case study that illustrates how it works. This talk is based on a work-in-progress.