Arc Forumnew | comments | leaders | submitlogin
Comparision
4 points by aquagnu 5586 days ago | 7 comments
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?


3 points by cchooper 5585 days ago | link

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 points by rntz 5585 days ago | link

3. I'm mystified as to why you think this makes recursive macros impossible. Many arc macros are recursive. 'withs, for example:

    (mac withs (parms . body)
      (if (no parms) 
          `(do ,@body)
          `(let ,(car parms) ,(cadr parms) 
             (withs ,(cddr parms) ,@body))))
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.

-----

1 point by cchooper 5584 days ago | link

To clarify those points:

They're not recursive in the same way functions are:

  (mac foo (x)
    (if x '( ...)
        (foo ...)))
> Even using macros and some non-turing-complete subset

But macros on their own aren't. By comparison, Pure can do everything with rules.

-----

6 points by rntz 5584 days ago | link

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.

-----

1 point by cchooper 5584 days ago | link

On the other hand, it's debatable whether being non-recursive in this way is a difference from Pure.

-----

2 points by aquagnu 5582 days ago | link

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) ?

-----

2 points by cchooper 5579 days ago | link

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.

-----