Programming Tools Group

Research Meetings (Michaelmas Term '98)

Topics we discussed during Michaelmas '98 include: pattern matching in code generation, higher-order matching, mechanized data refinement, an abstract model of editing, intentions in WordPad, non-standard type analyses of legacy code.

week 0, Oct 5: Charles Simonyi. Plans for the first 6 months of IP at Oxford. Charles also filled us in on current developments at Redmond, in particular the plan to roll out IP for internal use within MS next summer. In that release the focus will be on IP as a programming environment rather than a full-blown program transformation system.

week 1, Oct 12: Mike Spivey. Pattern matching and code generation. Mike showed us how good code generators work by "tiling" the abstract syntax tree with patterns. The lcc compiler of Hanson and Fraser makes use of this technique. Mike also discussed good algorithms for doing such pattern matching, in particular two algorithms (one top-down and another bottom-up) by Hoffman and O'Donnell. Clearly one can do still better, and we agreed to read some papers on yet faster matching algorithms.

week 2, Oct 19: Ganesh Sittampalam. Higher-order pattern matching. In program transformation systems, we often need to match patterns that contain function variables against actual code. Ganesh introduced us to the formal definitions, quickly surveyed existing work, and then proceeded to sketch the algorithm that he recently invented himself. That algorithm is simple, but perhaps not very efficient: the techniques discussed in the previous week might help.

week 3, Oct 26: Ivan Sanabria.Mechanised data refinement. Ivan introduced us to a system called Polya, developed at Cornell, for the mechanisation of data refinement, the technique of representing an abstract data type in concrete terms. In Polya a program is split into its abstract description, and a number of "transforms", which are essentially sets of rewrite rules. The mechanism for application of transforms seemed rather ad hoc, and the examples are somewhat ad hoc. We think we might be able to better by using rewriting based on higher-order matching, as described in the previous week.

week 4, Nov 2: Oege de Moor. Attribute grammars as a collection of language features. Oege introduced attribute grammars as a way of describing syntax-directed translations, which allows the programmer to ignore the number of passes and order of computation. He briefly explained that attribute grammar systems did not become popular because they are too restrictive: the whole translation process must be described in a rather restrictive functional programming language. Attribute grammars could however be viewed as a style of programming, also in imperative languages. All we need is lazy data structures. He illustrated this by fragments of ML. Oege went on to speculate that to gain all advantages of dedicated ag systems, but without the restrictions, we need type system that allows some form of record concatenation. He also mentioned the connection to R5, the new model of reduction in IP.

public seminar: Richard Bornat (QMW). What should the UI of a Programming tool be like? Richard told us about the golden rules of UI design, and how he and Bernard applied them in the design of the Jape proof editor.

week 5, Nov 9:: Kevin Backhouse. Programming with MFC, and WordPad. Kevin gave an introduction to programming with MFC, and in particular to the WordPad example. A lively discussion on MFC's architecture ensued, and on the pros and cons of message maps (as opposed to a purely object oriented design). Kevin proceeded to discuss one particular code fragment in some detail, which deals with reading various file formats, while reporting progress on the screen. It was generally agreed that this piece of code is a prime candidate for a more abstract, intentional description.

Public seminar, Nov 10: Lex Augusteijn, Philips Research Labs.: "The Elegant Compiler System". Lex talked about Philips' in-house tool for implementing domain-specific languages. It is based on attribute grammars implemented through lazy evaluation (Oege's discussion was a preparation for this). Rather surprisingly, it would appear that an attribute grammar evaluator based on these very simple primitives outperforms the highly sophisticated systems that do careful scheduling of the computations. We agreed that we should verify this claim for ourselves. It's highly relevant to the new model of reduction in IP, which is also based on demand-driven evaluation.

week 6, Nov 16: Bernard Sufrin. Polymorphic type checking; non-standard uses. Bernard gave an introduction to polymorphic type checking, and how it can be used for non-standard applications, for example pinpointing Unicode problems. He illustrated the basic ideas via an interactive session with Jape. He went on to describe some of the components in a generic "type-checking toolkit" that may become part of IP's meta-language.

week 7, Nov 23: Ivan Sanabria. Abstraction mechanisms in Attribute Grammars. Following on from the discussion in week 4, Ivan described various abstraction mechanisms that are available in the meta-language of dedicated attribute grammar systems. Oege argued that these could all be mimicked in a sufficiently rich host language, and that there's no need for a dedicated preprocessor. He also claimed that unless you think of AGs as a collection of features in a host language, you're bound to run into the kind of ad hoc restrictions that sunk AGs as a mainstream technology. There was some disagreement on these points; Mike argued the contrary. Ivan is continuing to scour the literature for language features that the AG community have found useful, and perhaps prototype them in OCaml.

Public seminar, Nov 24: Morten Heine Sorenson, DIKU. "A Typing solution to the Y2K problem" Morten described one of the great success stories fo programming language research, namely a polymorphic type checker for Cobol programs, that can be used for pinpointing potential Y2K problems. The software is now commercially marketed; Morten gave an in-depth demonstration of its operation.

week 8, Nov 30: Bernard Sufrin. Invariants to describe user interfaces. Using some features of WordPad as a guiding example, Bernard showed how certain user interface aspects are nicely described as invariants between view and document. In one instance where he had tried to do this (font changes) he had run into a number of unfortunate design decisions in WordPad's UI. There was a heated discussion on how we should cope with such features when "intentionalising" WordPad, and the best route seems to build an idealised model, and wrap a modifying layer around that which faithfully reproduces the current behaviour in WordPad. The meeting was cut short by other commitments of several team members.