Contents of this page: Photos | Local information | Proposed topics for discussion | Proposed talksMinutes of the meeting are now available (last updated 7th November 2005).
At Meeting 58 in Rome, I talked about Streaming algorithms or metamorphisms: the fused composition of an unfold after a fold, and useful for various change-of-representation problems. However, the theory I had then was specific to lists. I think I now see how to generalize it; the key observation is that the fold stage should be tail-recursive. I propose to report on this generalization.
Program inversion is a fundamental concept in program transformation. We describe the principles behind an automatic program inverter for a first-order functional language and show the inversion of several programs produced by our system. The core of the system uses a stack-based language, local inversion, and eliminates nondeterminism by applying methods from LR(0) parsing. Joint work with M.Kawabe.Related Reference: Glück R., Kawabe M., Derivation of deterministic inverse programs based on LR parsing. In: Kameyama Y., Stuckey P.J. (eds.), Functional and Logic Programming. Proceedings. LNCS 2998, 291-306, 2004.
In many occasions would one encounter the task of maintaining the consistency of two pieces of structured data that are related by some transform. In some XML editors, for example, a source XML document is transformed to a user-friendly, editable view through a transform defined by the document designer. The editing performed by the user on the view needs to be reflected back to the source document. Similar techniques can also be used to synchronise several bookmarks stored in formats of different browsers, to maintain invariance among widgets in an user interface, or to maintain the consistency of data and view in databases.This paper proposes a formal model of such tasks, basing on a functional language allowing injective functions only. The programmer designs the transformation as if she is writing a functional program, while the synchronisation behaviour is automatically derived by algebraic reasoning. The main advantage is being able to deal with duplication and structural changes. Non-injective programs, on the other hand, can be embedded into the injective language.
We now have a prototype editor based on the technique. I will give an overview of the framework, as well as current problems waiting to be solved.
I shall present 2-3 finger trees, a functional representation of sequences supporting access to the ends in amortised constant time, and concatenation and splitting in time logarithmic in the size of the smaller piece. Representations achieving these bounds have appeared previously, but finger trees are much simpler, as are the operations on them. Further, by defining the split operation in a general form, we obtain a general purpose data structure that can serve as a sequence, priority queue, search tree, priority search queue and more.A paper and slides are available. This is joint work with Ross Paterson.
Object abstraction supports the separation of what operations are provided by systems and components from how the operations are implemented, and is essential in enabling the construction of complex systems from components. Unfortunately, clear and modular implementations have poor performance when expensive query operations are repeated, while efficient implementations that incrementally maintain these query results are much more difficult to develop and to understand, because the code blows up significantly and is no longer clear or modular.(This work continued from a talk I gave in the NYC meeting but it has grown significantly: starting with a simple high-level language, completely free of complicated Java stuff; with transformations specified in a powerful rule language; with analysis worked out for sets and objects; and with a prototype, exciting applications and experiements. I will mainly discuss these new apsects. The tech report version has been accepted by OOPSLA 2005.)This paper describes a powerful and systematic method that first allows the ``what'' of each component to be specified in a clear and modular fashion and implemented straightforwardly in an object-oriented language; then analyzes the queries and updates, across object abstraction, in the straightforward implementation; and finally derives the sophisticated and efficient ``how'' of each component by incrementally maintaining the results of repeated expensive queries with respect to updates to their parameters. Our implementation and experimental results for example applications in query optimization, role-based access control, etc. demonstrate the effectiveness and benefit of the method.
This talks presents a novel language for querying complex graphs where graph edges may have labels that may have parameters. These graphs easily and naturally capture complex interrelated objects in object-oriented systems and XML data. The language is built on extended regular path expressions, and is easier to use and has greater expressive power than previous query languages. We also describe how to transform queries in this language into Datalog with limited extensions, and how to generate specialized algorithms and complexity formulas from Datalog programs with these extensions.(I wanted to have a discussion on XML and all that in some previous meeting, but I knew nothing then. Now after teaching DB and XML in undergrad, grad, and special topics courses and doing some research, I found that they are limited in various ways. Hence this work. This ongoing work also generalizes our work on parametric regular path queries that appeared in PLDI 2004, but we do not yet have extensive applications and experiments like in the PLDI paper. See techreport.)
Wherever software designers refer to the relational calculus, what they usually mean is the set-theoretic kernel of relational database design «ŕ la Codd» and not the calculus of binary relations which was initiated by De Morgan in the 1860s.A draft paper is available.Contrary to the intuition that a binary relation is just a particular case of n-ary relation, this paper shows the effectiveness of the former in «explaining» and reasoning about the latter. The theory of functional dependencies, which is central to such database design techniques, is addressed in a pointfree style instead of reasoning in the standard set-theoretic model «ŕ la Codd».
It turns out that the theory becomes more general and considerably simpler. Elegant expressions replace lengthy formulae and easy-to-follow calculations replace pointwise proofs with lots of «...» notation, case analyses and natural language explanations for «obvious» steps.