Conclusions/Minutes Kick off days, October 23 - 26, 2000
People present: Frank Atanassow (FA), Roland Backhouse (RCB), Ralf Hinze (RH),
Patrik Jansson (PJ), Johan Jeuring (JJ), Andres Löh (AL), Doaitse Swierstra (SDS),
Eelco Visser (EV), Jan de Wit (JdW).
Notes by Roland Backhouse and Johan Jeuring
Monday, October 23
Programming languages & tools - SDS
(Source) Language issues in Generic Haskell.
The aim of this first discussion was to construct a prioritised list
of features that should be included in the language.
Johan kicked off the discussion by stating that a must was the
1. type-indexed values and kind-indexed types.
Discussion followed on whether or not to include
2. type-indexed types and kind-indexed kinds.
Patrik claimed that these were not as well understood as 1.
Ralf claimed that both 1 and 2 were still not well understood.
The problem was one of interfacing an ideal language [Generic
Haskell -- ed]
with a real language [Haskell -- ed].
Roland asked how generic programs differed from type-dependent
programs. Ralf replied that in generic programming values depend on
types whereas in a dependent type system types depend on values. In a
dependent type system, programs parameterised by types must be
polymorphic in the types. Patrik explained that in Cayenne
(Augusston's dependent type program language) it was possible to map a
string to a type but not vice-versa.
The problem of merging Haskell's class system with a generic type
system was discussed. It was agreed that Haskell's classes form a
proper subset of generic definitions. Johan was, however, not in
favour of building on the existing Haskell language. The language to
be developed should be Haskell-like but not Haskell++.
There was some discussion about the extent to which use should be made
of existing modules of the GHC compiler. Options mentioned were
writing a preprocessor as in the current PolyP system, using the
back-end of GHC and/or Clean. There was general agreement that it was
a good idea to get something working quickly with which to experiment
Johan's notes on the conclusions:
We will pursue two paths: F-omega+ type-indexed values, etc. (really a new language), and
extensions of Haskell a la derivable type classes/Polyp. The first prototype will be
based on Jan de Wit's prototype, and will be further developed by Andres (in cooperation
with Jan, Ralf and Johan). The second track will be investigated by Patrik (in cooperation
with Ralf). The target language of both tracks will be Haskell. At a later stage this
might be replaced by some intermediate language (for example GHC's intermediate language).
We will try to submit a paper to the special issue of JFP on Haskell (Ralf, ... deadline
A first implementation of Generic Haskell,
demo - JdW.
Tools (to be) used in the compiler.
We agreed to try to use the UU Parser combinators, pretty printers, and the AG system.
We expect that using these tools will make it simpler to build Generic Haskell.
It has the additional advantage that building Generic Haskell using these tools will
very likely lead to improved tools. Doaitse has promised support for these tools.
Generic Haskell will be implemented using the tools mentioned above, and Haskell98
with polymorphic parameters.
Eelco and Johan will try to set up a cvs server and a wiki server for supporting
the work of the group.
Tuesday, October 24
PJ: Components of generic programming systems:
Generic definitions language
A language for using generic definitions.
Type checking generic definitions.
Generate instances of generic definitions.
Generate instances of built-in glue.
Polyp has all of these components right now, the presented demo
the last two of the generic definitions language.
Type check uses of generic definitions.
Locate uses of generic definitions.
Replace uses of generic definitions by instances.
Applications of Generic Programming. We would like to see implementations
in Generic Haskell for the following functionality:
We also discussed implementing cata's in Generic Haskell. We did not know how
to do this for mutual recursive, multiple argument datatypes in a typed way.
Data conversion problems such as
toXML/fromXML (DTD to datatype parser? XML Tools?)
A Generic Editor
Grammar/data analysis problems? (Enumerate finite values of the datatype, ...)
We discussed whether or not this problem
is `generic' in the sense used until now. If the result type of the analysis
does not depend on the datatype, analysis problems can be factored by translating
the datatype to a value in a representation type for data types (generic),
and analysing this value (not generic). However, many grammar analysis problems
return tree walks, maps, etc. and for these problems the functions are
The compiler itself? Most people thought that only a small part of the compiler
will make use of generic definitions.
Wednesday, October 25
Thursday, October 26
We discussed many organisational matters; here is the list:
We will organise biweekly meetings of the Generic Haskell project in Utrecht,
starting from November 15. Wednesday at 12:00. At these meetings we will discuss
our research, but also papers relevant to the project. We will
create a website with a list of papers and talks. (Action: JJ)
We will have international meetings (the UU people with PJ, RCB+GH+..., JG+OdM+RSB,
more?) at least once a year, preferably a bit more often. Next meeting in spring 2001.
Since the IFIP2.1 WG meeting will take place in September in the NL (many of the involved
people will probably attend this meeting), maybe it is an idea to meet around April
in Nottingham? We should also meet in Sweden at some point. (Action: JJ+RCB)
We will organise a summerschool on Generic Programming, not before 2002.
RCB thought Oxford was a very good location for such a school, maybe the Nott./Oxford
people can organise such a school later in the project. (Action: JJ+RCB)
Should we try to organise an Advanced Functional Programming summer school after the
IFIP WG2.1 meeting on Ameland?
Put JdW's prototype on the web. (Done)
Install several Haskell compilers (in particular GHC, but preferably also HBC, NHC)
and Cayenne on the Utrecht machines. This amounts installing the compilers and updating
Pablo's page about them.
Extend the Generic Haskell emaillist with several people that might be interested
in the Generic Haskell project, and send an email about the start of the project on
the Generic Haskell list. (Action: JJ)
Topics we or MSc students have to or can work on:
Build a clearly documented, simple, extendable F-Omega system.
Have a look at Ponder from Jon Fairbairn.
There are currently 3 ways to implement compositional cata's (catamorphisms for
mutual recursive, multiple argument datatypes, or AG's). Investigate their
respective (dis)advantages, and try to obtain a combination of the three. This
might be related to implementing cata's for mutual recursive, multiple argument
Generalise non-generic programs as a way of specifying generic programs.
How much type annotation can be left out in F-Omega, Generic Haskell, Martin Löf
type theory (see also some talks at Chalmers about this topic).
How to define generic programs on n-ary sums and products. Or: How do we represent
data types. Or: "The semantics of 1...n". Have a look at Tullsen's zip calculus (MPC'00).
Termination of programs comes for free in F-Omega. Investigate how a fixed point
combinator can be defined in the language.
Add or encode properties in the type language. Verify them. Construct strategies
for veryfing them.
What exactly does the data type language look like? Add forall?
Fetch a Haskell parser/type checker. Put them in CVS.
Questions we have to discuss are:
should we try to focus on Generic Haskell at the next IFIP 2.1 meeting,
can we make a list of MSc topics (warm fusion in Generic Haskell?, generic
function generation, subtyping, zip-calculus),
For information contact Johan Jeuring