Term Rewriting: Towards a more powerful macro language?
I started a thread recently at Lambda-the-Ultimate.org called Functions shouldn’t be lists, functions should be cast to lists, which was based on my previous blog entry The Types of Functions and Lists in Joy and Cat.
However, the discussion has moved into an area I am very interested in: the usage of term rewriting strategies to do data type selection. In general I am looking into more powerful and generalized forms of macro languages, related to the idea of term rewriting languages like Stratego. This is based on a large group of ideas and observations:
- Macro languages are useful but hygenic macros langauges languages are better.
- Programmers sometimes want to manipulate the abstract syntax tree (AST).
- A macro language should be aware of the AST.
- Many optimizations can be expressed using a simple declarative language (e.g. [A] map [B] map => [A B] map).
- Programmers know more than a compiler.
- Many optimizations are domain specific.
- A term rewriting language may be able to contain the type rules, and do the type-checking for the compiler. This would allow customized type systems for software.
- It might be advantageous to decouple the type system from the source code.
- Type systems are best expressed declaratively.
- Aspect oriented programming can be achieved easily using a term rewriting languages.
- Multi-stage programming seems inevitable in many areas non-trivial software whether it is a macro language, a C++ template based approach, a code generator, or custom language extension.
- There are useful pieces of information (e.g. function f is associative), which can be leveraged by compiler, but can’t be easily discovered.
- Extending the core programming language to express all desirable attributes is a never-ending battle: we can’t cover all kinds of information that a programmer could want in the future.
- C# use a declarative and open-ended attribute systems with considerable success.
- Declarative approaches make live programming more feasible, and more powerful.
- A sufficiently powerful term rewriting language may actually be able to take on the task of type-checking and type-inference.
- Allowing a piece of software to have its own novel type-system could be exceedingly powerful.
Sorry that my thoughts on the subject aren’t more coherent, but I thought a brain-dump in this case could still be useful and thought provoking. A great launch page for more related topics is the web page Refactoring Functional Programs.
When you say “term rewriting strategies”, are you referring to code transforming macros (like in Lisp or Scheme), or are you referring to runtime term rewriting (like in Q lang)?
When I saw your presentation of the Cat language at the .NET languages conference in the summer of last year, I thought the most promising feature of Cat was the ability it gave the programmer to directly specify transformation rules within the language itself. (I have not looked at your most recent specification to see if this is still a feature; indeed, I’ve been disappointed that this point has seldom come up in your blog.) I talked to an engineer from Borland who saw the same presentation of Cat as I did. He agreed with me that the greatest feature of your language is the ability to embed transformation rules directly in the language. Working for Borland, the engineer often has to write transformation rules in the C++ compiler, but rather than having a special syntax and semantics, the transformation rules are hidden behind explicit C code and visitor patterns.
Looking back on it, I guess your transformation rules are nothing more than a macro language for Cat. However, if CLI and Cat can be converted into each other easily, then I think Cat could act as an excellent optimization tier.
You said this point is a brain-dump. Here’s my contribution to the mess. :)
Comment by sciolizer — March 27, 2007 @ 1:14 am
Hi Sciolizer,
Thanks for your comments. I have been referring to static code transforming macros. However, I want to go a step further, and eventually allow type manipulations within the macro language.
The Cat specification (which will be rereleased in a couple of weeks) will specify several different levels of Cat, which are each easily transformed from one into another. So one level of Cat will have the term rewriting strategies embedded, while the most basic version won’t. I’ve tried to clarify a bit more in a recent post at: http://cdiggins.com/2007/03/27/so-does-cat-have-names-or-not-and-does-it-have-rewriting-rules-or-not/
Comment by cdiggins — March 27, 2007 @ 6:40 pm