Arc Forumnew | comments | leaders | submitlogin
5 points by rntz 5822 days ago | link | parent

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 5822 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 5821 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 5821 days ago | link

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

-----