Arc Forum | Implementation Question: Macros?

Arc Forum

5 points by PieSquared 5855 days ago | 5 comments

I've been thinking lately about how Lisp-like languages could implement macros, and it's confused me on one point:

How can recursive macros work? What I was thinking of is that the macro code can be expanded, then converted to a function, and then used later on. But you can't expand the code if you're using a recursive macro...

Same for mutually recursive macros. I know they're possible, because I've tried them and they work!

Can someone enlighten me as to how this works? Is this a special case which has to be treated as such, or what?

7 points by drcode 5855 days ago | link

the way macros are expanded, the code is searched for references of the macro. If a referenence is found, the macro is executed and the code altered with the results of the macro.

The macroexpander will then "stupidly" rerun against the code, over and over again, until there are no more macros to expand.

This crude behavior allows you to have recursive macros, but it's not actually doing anything all that "smart"- I think you're reading more into the complexities of recursive macros than is probably there.

-----

3 points by PieSquared 5854 days ago | link

This is what I originally had in mind. As far as I can tell, this doesn't work for bytecode-compiled Lisp, correct? (Since it would compile it as a function call, although it's a macro...) So does that mean every implementation of Lisp has to have a single-pass interpreter in it?

-----

2 points by cchooper 5854 days ago | link

Well, every implementation of Lisp does indeed contain an interpreter: eval!

But the way Lisp compilers deal with recursive macros is to not allow them. From the Common Lisp spec:

"All macro and symbol macro calls appearing in the source code being compiled are expanded at compile time in such a way that they will not be expanded again at run time."

That rules out recursive macros. I think they're allowed when Lisp is being interpreted, but you should probably just not use them.

http://www.lisp.org/HyperSpec/Body/sec_3-2-2-2.html

-----

2 points by Jesin 5839 days ago | link

Basically, as long as it has a termination condition that is always reached, it works. For example (this may not match arc.arc as I'm making this up on the spot):

  (mac aif (test . body)
    (if body
        `(let it ,test
           (if it
               ,(car body)
               (aif ,@(cdr body))))
        test))

Now, let's expand this (I won't bother expanding let, just aif):

  (aif a b c d e)

  ; expand aif

  (let it a
    (if it
        b
        (aif c d e)))

  ; expand aif

  (let it a
    (if it
        b
        (let it c
          (if it
              d
              (aif e)))))

  ; expand aif

  (let it a
    (if it
        b
        (let it c
          (if it
              d
              e))))

If you feed in an even number of terms, this happens:

  (aif a b)

  ; expand aif

  (let it a
    (if it
        b
        (aif nil)))

  ; expand aif

  (let it a
    (if it
        b
        nil))

That works because (car nil) is nil. Convenient!

Also, I'm something of a perfectionist, and sometimes when I get bored I've been cleaning up some of the macros in arc.arc. I've been able to work out cleaner implementations that produce cleaner expansions for some of them. For example, I don't know why while is implemented as:

  (mac while (test . body)
    (w/uniq (gf gp)
      `((rfn ,gf (,gp)
          (when ,gp ,@body (,gf ,test)))
        ,test)))

when this should also work:

  (mac while (test . body)
    (w/uniq g
      `((rfn ,g ()
          (when ,test ,@body (,g))))))

-----

2 points by kens 5855 days ago | link

"On Lisp" section 10.4 discusses recursive macros. The brief explanation is that the recursion must be something that can be computed and terminated at compile time.

See http://www.bookshelf.jp/texi/onlisp/onlisp_11.html#SEC81

-----