Informal minutes of IFIP Working Group 2.1
59th meeting, Nottingham, UK
Monday 2004-09-06 to Friday 2004-09-10

Contents of this page:    Administrative matters  |  Technical presentations
(Last updated 17th December 2004.)

Organizational and administrative matters

List of attendees

Members: Observers:

Membership (Fri 2004-09-10, 09:00)

This discussion was for members only, and is not recorded in these public minutes.

Next meetings (Fri 2004-09-10, 09:45)

Meeting 60
This will be organized by Allen Goldberg, between 22nd and 26th May 2005. (Note that this is a Sunday to a Thursday. This is both to facilitate staying a Saturday night to obtain a cheap flight, but also to steer clear of the Memorial Day public holiday the following weekend.) It will be held somewhere in the Bay Area of Northern California, probably near Lake Tahoe.

Meeting 61
This will be held around February 2006. Richard Bird will explore possibilities for hosting it in the South of England.

Meeting 62
This should be held around November 2006. The Secretary will ask whether Michel Sintzoff would be prepared to organize it.

Publications in honour of Bob Paige (Fri 2004-09-10, 10:00)

Alberto Pettorossi informs the Group that the second special issue of the journal Higher Order and Symbolic Computation in honour of Bob Paige will soon be published. After that appears, he will edit a book containing the papers from the two special issues and a few other contributions.

He hopes that the Group could then find an opportunity to present the book to Bob's widow, as a sign of our friendship and appreciation for Bob, as was Bob's wish.

Opportunities to speak (Fri 2004-09-10, 10:05)

Alberto Pettorossi made a request that the scheduling procedure be adapted to ensure that every participant who wants to is given the opportunity to speak at least once every few meetings. The group discussed this request, but could think of no sensible way to formalize a procedure for it. It was decided to leave this matter to the discretion of the Chair: as always, he may bypass the scheduling procedure if he feels it right to do so.

Influential papers (Fri 2004-09-10, 10:10)

Fermin Reig has initiated a column in SIGPLAN Notices presenting reminiscences by programming language researchers of papers and other publications that have influenced their careers. He is looking for more contributions; members and observers are encouraged to get in contact with him if they would like to participate.

Formal resolution (Fri 2004-09-10, 11:00)

The members of WG2.1 and the observers present at the 59th meeting in Nottingham wish to express their gratitude to Roland Backhouse and his Merry Men* - fellows familiar with both the forests of algorithmics and the fields of mathematics - for providing sunshine and towels, and a congenial atmosphere in which the Group could conduct its operations. We learned how to capture chickens, which subsequently were cooked to perfection and beyond.

Cunningly isolated from outside communication, the group had no choice but to exchange many a chat's worth of ideas: making its way through a coal tunnel of darkness and a maze of box hedges to emerge with a gravity-powered Revelation.

* not forgetting Maid Hilary

Technical presentations

Note: presentation summaries were prepared by the speakers.

Presentation: Bird, The Celebrity Clique Problem (Mon 2004-09-06, 11:00)

No abstract provided.

Presentation: Jeuring, Generic Views on Data Types (Mon 2004-09-06, 11:30)

A generic function is defined by induction on the structure of types. The structure of a data type can be defined in several ways. For example, in PolyP a pattern functor gives the structure of a data type viewed as a fixed point, and in Generic Haskell a structural representation type gives an isomorphic type view of a data type in terms of sums of products. Depending on this generic view on the structure of data types, some generic functions are easier, more difficult, or even impossible to define. Furthermore, the efficiency of some generic functions can be improved by choosing a different view. This paper introduces generic views on data types, and shows why they are useful. Furthermore, it shows how to add new generic views to Generic Haskell, an extension of the functional programming language Haskell that supports the construction of generic functions. The separation between inductive definitions on type structure and generic views allows us to view many approaches to generic programming in a single framework.

Presentation: Altenkirch, Functional Quantum Programming (Mon 2004-09-06, 14:00)

We introduce the language QML, a functional language for quantum computations on finite types. Its design is guided by its categorical semantics: QML programs are interpreted by morphisms in the category FQC of finite quantum computations, which provides a constructive semantics of irreversible quantum computations realizable as quantum gates. QML integrates reversible and irreversible quantum computations in one language, using first order strict linear logic to make weakenings explicit. Strict programs are free of decoherence and hence preserve entanglement which is essential for quantum parallelism.
(A paper is available.)

Presentation: Hutton, Calculating an Exceptional Machine (Mon 2004-09-06, 15:15)

At the last meeting, I showed how to verify a compiler for a simple language with exceptions. I have since discovered how to calculate, as opposed to verify, an abstract machine for this language. The key step is the use of John Reynolds' "defunctionalisation" technique from 1972, which seems to have been largely forgotten by the program transformation community, but has recently been re-popularised by Olivier Danvy. In this talk I will review defunctionalisation, and show how it can be use to calculate an abstract machine for exceptions that is both simple and efficient.

Presentation: Jones, Program Transformation by Interpreter Specialization (Mon 2004-09-06, 16:40)

A program may be transformed by specialising an interpreter for the language in which it is written. Efficiency of the transformed program is determined by the efficiency of the interpreter's dynamic operations; the efficiency of its static operations is irrelevant, since all will be ``specialised away''. This approach is automatic (as automatic as the specialiser is); general, in that it applies to all of the interpreter's input programs; and flexible, in that a wide range of program transformations are achievable since the transformed program inherits the style of the interpreter. The chief practical challenge is understanding cause and effect: How should one write the interpreter so that specialisation produces efficient transformed programs? The core of this paper is a series of examples, both positive and negative, showing how the way the interpreter is written can influence the removal of interpretational overhead, and thus the efficiency and size of the target programs obtained by specialisation.

Presentation: Gibbons, Model-Driven Architecture and Model-Based Transformations (Tue 2004-09-07, 09:00)

One prediction for the Next Big Thing in mainstream software engineering is Model-Driven Architecture. This takes the current standard approach of manually implementing a UML design one step further: code is derived with some degree of automation from a platform-specific model, which is in turn derived from a platform-independent model. This kind of model transformation is a topic WG2.1 ought to be able to help with.

My interest in this is that my group has recently been awarded a large grant for a project called CancerGRID, to develop software infrastructure for managing distributed cancer medical trials around the UK. My hope is that model-driven techniques can help in this development.

Presentation: Bird, The Celebrity Clique Problem (continued) (Tue 2004-09-07, 09:35)

No abstract provided.

Presentation: Bird, Online List Labelling (Tue 2004-09-07, 09:50)

No abstract provided.

Presentation: McBride, Epigram (Tue 2004-09-07, 11:10)

No abstract provided.

Presentation: Backhouse, Sam Loyd's Chicken-Chasing Problem (Tue 2004-09-07, 14:00)

In the context of teaching algorithmic problem solving (see talk at Meeting #58) I was recently alerted to Sam Loyd's Chickens in the Corn problem.

The problem is interesting because the combination of invariants and making progress in a well-formulated algorithm to solve the problem is non-trivial.

I would like to discuss a solution to the problem. Others may have better solutions, which I would like to hear about.

Presentation: Löh, Dependencies: By Case or by Function? (Tue 2004-09-07, 14:35)

No abstract provided, but slides are available.

Presentation: Clenaghan, Uniform Random Generation from a Context-Free Grammar (Tue 2004-09-07, 15:20)

No abstract provided.

Presentation: Lindsey, Five Minutes on Chickens (Tue 2004-09-07, 16:50)

No abstract provided.

Presentation: Oliveira, Calculate Databases with Simplicity (Wed 2004-09-08, 09:05)

This talk will address my attempts to replace current semi-formal database schema design (à la Codd, based on normalization etc) by an inequational calculus based on simple (dually, injective) relations and their transposes. Many results generalize to other relations, the 'simple' ones being more relevant in practice just because database entities can always be modelled as finite simple relations. I find it much "simpler" to use this (pointfree) calculus than the standard theory. It includes a generic result which enables the refinement of recursive data models and which is the basis for a XML <-> SQL conversion tool which we are currently developing at Minho in Haskell/Strafunski.
A copy of the slides is available.

Presentation: McBride, Idioms (Wed 2004-09-08, 10:00)

No abstract provided, but the scanned slides are available.

Presentation: Hofstedt, Strategies for the Efficient Solution of Constraint Programs (Wed 2004-09-08, 11:20)

Meta-S is a system for defining the cooperation and coordination of constraint solvers to attack hybrid constraint problems. Considering language evaluation mechanisms as constraint solvers and integrating these particular solvers into our system allows to combine arbitrary declarative languages and constraints. The talk exemplarily discusses these ideas for a logic language which yields a CLP language with support for solver cooperation.

We use the strategy definition framework of Meta-S and define classical search strategies as well as new ones for an efficient evaluation of hybrid constraint logic programs.

This talk is a follow-up on the presentation Integration of Declarative and Constraint Programming at the 58th Meeting of the IFIP Working Group 2.1.

A paper is available.

Presentation: Reig, Reasoning Methods for a Class of Generic Programs (Thu 2004-09-09, 09:00)

No abstract provided.

Presentation: Swierstra, Linear, Online, Functional Pretty-Printing (A non-algebraic derivation) (Thu 2004-09-09, 09:45)

We present an implementation of Oppen's pretty-printing solution in Haskell. The algorithm is linear in the size of the input, independent of the line width, uses limited look ahead, and has online behaviour.

Presentation: Löh, About lhs2TeX (Thu 2004-09-09, 09:00)

No abstract provided, but slides are available.

Presentation: Backhouse, Deriving MEX Sum (Thu 2004-09-09, 11:55)

At the Rome meeting (#58), I showed how the specification of the MEX function on games is derived. In this talk, I will show how the MEX sum is derived. The derivation centres on the observation that MEX numbers form a vector space over GF(2) (the field of booleans with xor as addition and conjunction as multiplication); the problem is solved by constructing a basis of this space.

The talk describes recent joint work with Diethard Michaelis.

A paper is available.

Presentation: Pardo, A Program Fusion Tool (Thu 2004-09-09, 14:40)

No abstract provided, but slides are available.

Presentation: Wada, fifol (Thu 2004-09-09, 16:20)

The fictitious programming language fifol was designed anew for the purpose of a programming contest held in 2001. fifol (first in first out language) is similar to PostScript. fifol is a queue machine while PostScript is a stack machine. Operations are performed on items removed from the front end of the current fifo and the result is inserted to the rear end. Computation must be done solely in the queue, no memory storage was available.

In this talk, I will present my experience on programming in the rather peculiar and unfriendly language.

  1. Rules of the language fifol.
  2. Snapshots of executions for sample programs.
  3. Designing a program for computing square root of an integer.
Some notes are available.

Presentation: Swierstra, Type-Safe Self-Inspecting Code (Thu 2004-09-09, 17:00)

We present techniques for representing typed abstract syntax trees in the presence of observable recursive structures. The need for this arose from the desire to cope with left-recursion in combinator based parsers. The techniques employed can be used in a much wider setting however, since it enables the inspection and transformation of any program structure, which contains internal references. The hard part of the work is to perform such analyses and transformations in a setting in which the Haskell type checker is still able to statically check the correctness of the program representations, and hence the type correctness of the transformed program.

Presentation: Pardo, Generic Accumulations (Fri 2004-09-10, 11:05)

No abstract provided.

Presentation: Möller, Algebra of Probabilistic Predicative Programming (Fri 2004-09-10, 11:20)

No abstract provided.

Working documents

846 NOT-1
Thorsten Altenkirch and Jonathan Grattage. A Functional Quantum Programming Language

847 NOT-2
Eiiti Wada. Some notes on fifol, and a fifol simulator in scheme.

848 NOT-3
Conor McBride. Idioms (copy of slides).

849 NOT-4
José Nuno Oliveira. Calculate databases with `simplicity' (copy of slides).

850 NOT-5
Stephan Frank, Petra Hofstedt and Dirk Reckmann. Strategies for the Efficient Solution of Hybrid Constraint Logic Programs. In MultiCPL 04: Third International Workshop on Multiparadigm Constraint Programming Languages, Saint-Malo, France, 2004.

851 NOT-6
Roland Backhouse and Diethard Michaelis. A Calculational Presentation of the Theory of Impartial Two-Person Games.

852 NOT-7
Alberto Pardo. A Program Fusion Tool (copy of slides).

853 NOT-8
Andres Löh. Dependencies: By case or by function? (copy of slides).

854 NOT-9
Andres Löh. Typesetting Haskell and more with lhs2TeX (copy of slides).

Jeremy Gibbons (email: