What do you think about comparison between Arc and Pure/Q-lang (http://code.google.com/p/pure-lang/)? Is term rewriting is similar (or another way?) to Lisp/Arc macros? What is difference?
Macros are similar to term rewriting rules. However, the Arc macro system is less powerful than the the term rewriting of Pure (and Q) for the following reasons:
1. Symbols are not evaluated at macro-expansion time.
2. Most Arc operators are functions or special forms (e.g. if, set, +), so they will not be evaluated until after all macros have been expanded.
3. Macros are expanded leftmost-outermost, which makes recursive macros impossible (Pure uses leftmost-innermost evaluation). On the other hand, this makes macros better for code transformation.
4. Pure expresses rules using equations. Arc expresses macros as functions on code, which is less convenient (but more consistent with the way Arc expresses normal functions).
5. Arc macros do not form a Turing complete language, but Pure is Turing complete. This is because of the leftmost-outermost order of evaluation, which causes recursive macros to expand infinitely, rather than converge.
I once tried to create a language that would use both full term rewriting and macros together. It was very difficult, but I can't remember why.
5. Macro bodies are written in Arc; of course they're Turing complete! Even using macros and some non-turing-complete subset of the rest of Arc, it should be possible to write a Turing-complete language using recursive macros, albeit not one that you'd really want to use. It's true that recursion without a base case won't terminate, but a Turing complete language whose evaluation always terminates is a contradiction.
Actually, I apologize. My earlier statement about macros plus some turing-incomplete subset of arc being turing-complete makes no sense. There is no such thing as "macros on their own". Macros are just Arc code that gets evaluated before what we like to think of as "runtime". Arc macros sans the rest of arc are nothing. The "difference" here is not that macros are (or rather, macroexpansion is) turing-incomplete. The difference is that Arc delineates macroexpansion from normal evaluation, whereas Pure doesn't have a distinction; everything is term rewriting.
OK. Well, one of the famous and evident "powers" of Lisp - is the Lisp's macros. Does language like Pure (Q) is "Lisp macros's killer" (language based on term rewriting rules) ?
Well term rewriting languages have been around for over 40 years and Lisp isn't dead yet! :)
The reason term rewriting can't replace macros is that the power of macros doesn't come from their similarity to rules, but from the fact that they run before normal execution. This two-step process makes macros an extension to the language's syntax. Pure doesn't have that ability. Pure's rules are more like a replacement to Lisp's functions, rather than Lisp's macros.
Ultimately, term rewriting and normal functional programming (lambda calculus) are very similar. I don't think either of them have much of an advantage over the other.
