RTA Dinner Speech, Utrecht, May 23, 2001, by Paul Klint

Ladies and Gentlemen,

The organizers of RTA have invited me to address you this evening and I have gladly accepted. Why? I am an outsider to the RTA community. I am also a heavy user and supporter of term rewriting. This gives me an ideal opportunity to match my views on term rewriting with yours. Be also assured that, although I will be critical, my attitude towards term rewriting is positive. This is a complicated way to say:   Hi, I am a stranger but I come in peace.

This is going to be a good news and bad news story. I will not ask you what you want to hear first. I will start with the bad news and end in a positive tone since I would not dare to disturb this nice dinner at this very nice location.

So what is the bad news? Matching the title "Rewriting Techniques and Applications" with the programme is disappointing from my point of view. Only very few presentations are related to applications. A good exception is the invited talk by Arvind on the use of term rewriting for hardware design. Most other presentations deal with inward-looking, self-centered research questions without any consideration for applications. ``Rewriting Theory'' would much better cover the programme.

Is this bad? No and Yes. No, since every research community has, of course, the right to follow its self-declared research agenda. Yes, since it emphasizes the isolation and lack of visibility of the term rewriting community that is also clear from other signals:

  1. The positioning of term rewriting relative to mathematics, logic and computer science is unclear. Personally, I would strongly favor inclusion of the field of term rewriting in Computer Science.
  2. The profiling and PR of term rewriting are clearly inferior to that of logic programming and functional programming. I should immediately add those communities are also having hard times.
  3. Elementary and popular books on term rewriting are scarce. I am not aiming at technical books like the ones from Baader and Nipkov and Klop c.s but books under the heading ``Term Rewriting for Dummies''.
  4. There is no generally accepted rewriting tool that is used for teaching.
  5. The impact of rewriting theory on term rewriting applications is not big to say it politely. Ask yourself the question what rewriting theory has to offer to, once again, a topic like hardware design.

After these, may be sobering, observations let's turn to the good news.

Let's start with an anecdote. Here in Holland we are always a bit suspicious and some of us believe that the largest, daily life, application of confluent systems is household garbage collection. The collection of the garbage is disjoint, glass, green stuff, etc. but all garbage ends up at the same garbage belt.

But seriously, if we look at term rewriting primary application areas are symbolic computation in mathematics (exemplified by Mathematica), and in theorem proving. Unfortunately both areas are also in need of defense and need "real" applications themselves. From this perspective term rewriting is at distance 2 from "real" applications. Can we reduce this application-distance to 1? Yes, by looking at and truly contributing to computer science applications like

  1. Expression simplification in optimizing compilers
  2. Code generation
  3. Program transformations
  4. Software renovation

About software renovation I want to elaborate a bit. For many years we have been working in Amsterdam on the ``ASF+SDF Meta-Environment'' which uses first-order, many-sorted, rewriting as its execution model. We introduced several features for pragmatic reasons that could benefit from further theoretical investigations:

  1. Default rules
  2. Negative conditions
  3. List matching
  4. Local strategies
  5. Memo functions
  6. Traversal functions

Last year, we have created a company called the ``Software Improvement Group'' that commercially applies these techniques for the renovation of COBOL systems. Imagine, gigantic terms corresponding to systems of millions of lines of code that are being rewritten. The result are restructured COBOL programs that can be better maintained. What were the issues to achieve this:

  1. Efficient and compact representation of terms
  2. Efficient compilation of rewrite rules

Interesting and not so easy engineering problems. I suspect that in many applications of term rewriting engineering questions will dominate. The bottom line is: yes, there are commercially viable applications of term rewriting.

Let me close, with two further suggestions.

  1. You will be aware that an XML revolution is going on outside. Now it happens, that XML comes with its own term rewriting language called XSLT. This has surely not been designed by term rewriting experts and there is work to be done by real experts.
  2. In compiler code generation the combination of term rewriting with dynamic programming is in use. Every rule has a numeric cost factor associated with it, and the objective is to find the cheapest set of rule applications for a given input term. The further investigation of the relation between term rewriting and optimization seems also promising to me.
Both problem areas may also place term rewriting at distance 1 from real applications.

Time to wrap up. Term rewriting is a highly useful research area that is lacking real life applications and public visibility. I am not suggesting that you all should be re-educated into Java programmers and that research on theory should be stopped. I am suggesting that the whole field of term rewriting would benefit if it would open up to the needs of applications and that theoretical research uses these applications as inspiration for research questions.

In my opinion the future of term rewriting is bright and I hope that some of the questions I have raised will trigger useful discussions.

Paul Klint

Vincent van Oostrom (oostrom @ hilbert.staff.phil.uu.nl)
Last modified: Mon Jul 9 18:09:38 MET DST 2001