FP /

# 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.