At the Generic Haskell meetings there will be talks on Generic Haskell, generic programming, and related matters such as compiler tools, type systems, etc.
13:30 - 14:00
14:30 - 15:30
We enhance the "Scrap your boilerplate" approach to generic programming in Haskell by introducing a complementary technique for generic function customisation. The programmer can hand in type-specific cases in terms of Haskell's type classes, which implies that these cases can be scattered over different modules. Such modularity was out of reach for the preexisting customisation technique, which is based on type-safe cast and often combined with parameterisation. The new technique also improves on the preexisting technique in terms of efficiency: no runtime type checks have to be performed. Still the two techniques complement each other in terms of convenience and expressiveness. While the addition of modular customisation is a major improvement for the generic programmer, its implementation does not require any new language extension.
16:00 - 17:00
Structural polymorphism allows for generic functions to be defined by induction over the structure of types. In Generic Haskell, the structure of a type is perceived as a nested sum of products. Over the last few years it has been shown that a great amount of generic programs can be defined in terms of this perception. Still, there are applications for which viewing data types as sums of products limits the expressiveness of Generic Haskell. As it turns out, different perceptions of the structure of types enable the definition of generic programs that are more efficient, more elegant, and more expressive. We show how these different perceptions, which we call generic views, can be implemented and used in Generic Haskell.
Discussion meeting.
The Generic Haskell Compiler translates Generic Haskell to normal
Haskell by specializing type indexed functions to sets of normal haskell
functions. The compiler generates a specific instance of the type
indexed function for each type that is used as type index used in an
application of the type indexed function.
In this talk I will show a different approach, in which type indexed
functions are translated to overloaded functions (type classes).
Furthermore I will show how you can handle dependencies, local
redefinitions and type indexed types and show some problems we
encounter during the translation.
By doing this translation we hope to find out if the various extensions
of the class (and type) system of Haskell are powerfull enough to
support Generic Haskell and gain some insights in the relation between
type classes and generic functions.
After extending Generic Haskell to handle specific constructors, we noticed that we had gained some of the machinery necessary to write attribute grammars directly. Dependency-style Generic Haskell made this easier. But how far do we get? Synthesised attributes seem easy to account for. The difficulty comes with inherited attributes.
Dave Clarke will introduce the topic.
If you attend, please read the paper before the meeting. Ask me for a copy.
If you attend, please read the paper before the meeting.
If you attend, please read the paper before the meeting.
If you attend, please read the paper before the meeting.
Ralf Hinze introduced two styles of generic function definitions. In implict recursive style, the type arguments of generic functions are just type constructors. Extra arguments are passed to some cases of the function that can be used to simulate recursive calls.
equal {| :+: |} eqA eqB (Inl a1) (Inl a2) = eqA a1 a2
This style is currently implemented in Generic Haskell, because the translation into plain Haskell is straightforward and the implicit style allows generic functions for all types of all kinds. In contrast, explicit recursive style is the way one would normally write a generic function, having a type pattern as type argument which contains variables.
equal {| a :+: b |} (Inl a1) (Inl a2) = equal {| a |} a1 a2
The talk will show how support for explicit recursion can be added to Generic Haskell without losing the benefits that the current implicitly recursive style offers.
Several XML tools have been released over the last few years. Compressors, editors and database tools are examples of popular XML tools. We claim that most XML tools can be viewed as generic programs. This talk discusses the construction of three of such XML tools. First, a compressor based on XComprez is (which is written in Generic Haskell) is discussed: an adaptation of XComprez to a compressor using Huffman encoding. Secondly, a generic XML editor GenericEdit is discussed. The third tool is an XML to database converter. We briefly discuss some generic DOM functions. The results of the three tools and the DOM functions are used to construct a framework/library for generic XML tools.
and how to write generic programs when data types are represented in this way. You might want to think about the problem before you come to the meeting.
which will appear in the proceedings of WCGP'02. If you attend, please read the paper before the meeting.
A generic program is a program that works on values of a large class of data types (or DTD's, schemas, structures, class hierarchies). In this talk I will show how generic programming can be used to implement XML tools such as XML editors, databases, and compressors, that depend on the DTD of an input XML document. The resulting tools usually perform better because knowledge of the DTD can be used to optimise the tools, and are smaller, because all DTD handling is dealt with in the generic programming compiler. I will show how an XML compressor is implemented as a generic program, and discuss which other classes of XML would profit from an implementation as a generic program.
We provide the working functional programmer with a simple and effective generic programming method. The approach builds upon the standard notion of function combinators such as monadic function sequencing or monadic choice. We essentially integrate two concepts with ordinary monadic polymorphic programming, that is, type case to enable ad-hoc behaviour, and term traversal via heterogenous list folds over constructor applications. The crucial design principle is here that again combinators embody these concepts. In this way, the resulting kind of generic functions are first-class because they are constructed, updated, and composed by function combinators as opposed to static schemes of overloading or polytypism. The application domain of our approach is program transformation and program analysis.
This paper discusses, amongst others, theorems for free. We will dicuss whether or not, and how, we can implement theorems for free in Generic Haskell. Another relevant paper for this topic is Erik Meijer and Graham Huttons Bananas in space paper (available from Graham Huttons home page).
Generic programming allows programmers to define functions which can operate on a large number of data types, without changing code. Generic Haskell is a superset of Haskell 98 designed specifically for generic programming, adding a number of new features to the Haskell language such as type-indexed values, kind-indexed types and type-indexed types.
This thesis describes these features and the way they currently are translated to Haskell 98 by the Generic Haskell compiler developed at Utrecht University. We also present the Generic Haskell library and a example application of Generic Haskell: a simple generic structure editor, which can be used to interactively construct values of any datatype.
In this talk the current results of a small research project will be presented part of which has been conducted at the University of Utrecht, together with Dr. Ralf Hinze who spent his sabattical in Utrecht.
In this research project, named the genamics project, we have investigated the applicability and impact of generic (or polytypic) programming on dynamics. The context of this project is formed by functional languages. The aim of generic programming is conciseness: similar operations on different data structures should be defined in one single function definition. Dynamic types are all about serialisation: every functional value should be transformable to a `type neutral' form (called dynamic), and be extracted from such a form in a type safe way. Type safety is accomplished by matching the type of a dynamic with the type that is expected by the program. If this match succeeds, the corresponding alternative is evaluated, otherwise the next alternative is chosen.
Generics and dynamics are being incorporated in the functional programming language Clean. Clean offers an extensive library to create graphical user interfaces (GUIs), the Object I/O library. Rather than programming GUIs one would like to create them visually. For this purpose we are developing a visual editor. With this editor one can create GUI resources which, in essence, are serialised values describing a GUI component. This is were dynamics come in scope. Applications that read in such resources need to parameterise such values with behaviour functions. This is were generics come in scope. We have investigated if generic functions can be written for data structures that typically occur in the Object I/O library. In addition, we show how generics can increase the expressiveness of dynamics by allowing the dynamic creation of generic instances.
I explore how XML processing can benefit from generic programming. After describing how to model XML in Haskell, I will demonstrate how some common XML functions can be implemented using generic functions. These functions, however, require a few extensions to Generic Haskell to overcome some existing limitations. I will outline these extensions.
Andres will introduce the Generic Haskell compiler, will explain what you can and cannot do with it, and give several examples of applications of Generic Haskell. This will be an introductory talk, the technicalities of the compiler will be discussed at a later Generic Haskell meeting.
We will discuss the current status of the Generic Haskell compiler, and we will have a look at the remaining (non?)problems: fixed points, POPL versus MPC style, type-indexed functions that call other type-indexed functions, etc.
We will have a brief last meeting before the summer in which we will discuss project matters: who will work on what in the near future.
When I was a student, the language Simula was typically taught in programming language courses. While I have forgotten most of the details, I still a remember a sticker one of our instructors had attached to the door of his office, saying "Simula does it with class". I guess the same holds for Haskell except that Haskell replaces classes by type classes.
Armed with singleton types, multiple parameter type classes, functional dependencies we tackle the problem of simulating dependent types in Haskell. In particular, we show how to implement variable-argument functions and C's string-formatting function `printf'.
The talk is heavily inspired by recent work of Conor McBride.
We will discuss the paper:
If you attend, please read the paper before the meeting.
Generic Clean prototype is based on approach described in R. Hinze's paper at MPC 2000. The prototype code is a part of Clean compiler. It relies on features already present in the language: type checking and type classes. I will show how generic functions are translated into non-generic Clean. Unlike Haskell, Clean uses uniqueness typing to perform destructive updates in a pure functional way. After short introduction to uniqueness typing, it will be shown what happens with uniqueness when a generic function is specialized to a type. A way to handle arrays will also be presented. Additionally, I will tell about our plans to use generic functions to work with dynamic types (dynamics).
A polytypic function is a function that can be instantiated on many datatypes to obtain datatype specific functionality. Examples of polytypic functions are the functions that can be derived in Haskell, such as show, read, and (==). More advanced examples of polytypic functions are functions for digital searching, pattern matching, unification, rewriting, and structure editing. For each of these problems, we not only have to define polytypic functionality, but also a \emph{type-indexed datatype}: a datatype that is constructed in a generic way from an argument datatype. For example, in the case of digital searching we have to define a search tree type by induction on the structure of the type of search keys. This talk shows how to define type-indexed datatypes, and discusses several examples of type-indexed datatypes.
I will present a paper Ralf and I wrote last week (and earlier). It is not completely finished, but if you want to have a look at it, you can get it from here.
We will discuss naming issues in Generic Haskell. We will dicuss questions like: how do I refer to values of user-defined data types; how can I write a generic show function; if I define type-indexed types, how do I construct values of those types, etc.
We will discuss the current status of the Generic Haskell compiler, and we will discuss the language report that has to be written and maintained.
We will discuss the paper:
If you attend, please read the paper before the meeting. Unfortunately, I can't find this paper on the web anymore. However, I do have a paper copy of which I have made some copies. You can get them at my room. For a tutorial on Maude, see Tutorial on Maude. This is a tutorial given by N. Marti-Oliet at the last ETAPS.
We will pose a problem and some partial solutions. Hopefully the audience can give us some input.
MOA is a language (a datamodel, to be used at the "logical" level in between the "external" end-user level and the low-level "physical" level of the database system Monet) for defining data representations that exploit Monet's capabilities of efficiently traversing and aggregating entire columns at a time.
The objective of the theory is threefold: first it should provide insight in the principles of MOA, second it should provide a formal framework to formulate and prove various claims and properties of MOA, and third it should suggest generalisations. In order to achieve the right level of abstraction and generality, we will use some methods and notions from category theory.
In the initial algebra approach to generic programming (and hence in PolyP) there is a problem with defining reduce and similar functions on constant types. This problem has disappeared in Generic Haskell. In a short talk, Lambert will explain why this is the case.
Andres has extended Jan de Wit's prototype for Generic Haskell with kind-indexed types. He will briefly introduce kind-indexed types by means of some simple examples, and he will show what the prototype produces for datatypes of different kinds. Furthermore, we will discuss the next step to take in the prototype.
List of papers we plan to discuss:
and many more...
For information contact info@generic-haskell.org