How to write a recursive macro call on a &REST parameter in Lisp?

Question

I've been writing some simple test cases for one of my assignments, and have built up a bit of a test suite using macros. I have run-test and run-test-section and so on. I'd like run-test-section to take a number of parameters which are run-test invocations and count up the number of PASSes and FAILs.

run-test returns T on PASS, and NIL on FAIL.

What I'm looking to do right now is write a macro that takes a &REST parameter, and invokes each of the elements of this list, finally returning the number of TRUE values.

This is what I currently have:

(defmacro count-true (&rest forms)
`(cond
    ((null ,forms)
      0)
    ((car ,forms)
      (1+ (count-true (cdr ,forms))))
    (T
      (count-true (cdr ,forms)))))

However this puts my REPL into an infinite loop. Might someone be able to point out how I can more effectively manipulate the arguments. Is this even a good idea? Is there a better approach?

edit:

As is noted in responses, a macro is not needed in this case. Using the inbuilt COUNT will suffice. There is useful information in the responses on recursive macro calls, however.

Tallula

Answer 1

At macro expansion time, cdr is not evaluated. So (count-true t t nil) hits an infinite expansion like this:

(count-true t t nil)
=>
(1+ (count-true (cdr (t t t nil))))
=>
(1+ (1+ (count-true (cdr (cdr (t t t nil))))))
=>
(1+ (1+ (1+ (count-true (cdr (cdr (cdr (t t t nil))))))))
=> ...

Well, actually this happens for both recursive branches at once. So it blows up even faster than the example.

A better idea?

1. Trying writing the same thing as a function first. Figure out where you have to put the lambdas to delay evaluation. Then abstract the function into a macro so you can leave out the lambdas.

   The point of writing a function first, by the way, is that sometimes you'll find that a function is good enough. Writing a macro where a function would do is a mistake.

2. Generally, when you write macros in Common Lisp, start with a loop rather than recursion. Recursive macros are tricky (and usually wrong :).

Edit:

Here is a more correct (but much longer) example:

(count-true t nil) =>
(cond
  ((null '(t nil)) 0)
  ((car '(t nil)) (1+ (count-true (cdr '(t nil)))))
  (T (count-true (cdr '(t nil)))))
=>
(cond
  ((null '(t nil)) 0)
  ((car '(t nil)) (1+ (1+ (count-true (cdr (cdr '(t nil)))))))
  (T (count-true (cdr (cdr '(t nil))))))
=>
(cond
  ((null '(t nil)) 0)
  ((car '(t nil)) (1+ (1+ (1+ (count-true (cdr (cdr (cdr '(t nil)))))))))
  (T (count-true (cdr (cdr (cdr '(t nil)))))))
=>
(cond
  ((null '(t nil)) 0)
  ((car '(t nil)) (1+ (1+ (1+ (1+ (count-true (cdr (cdr (cdr (cdr '(t nil)))))))))))
  (T (count-true (cdr (cdr (cdr (cdr '(t nil))))))))

Materialist

thanks for the explanation. i see now my faulty understanding of macro expansion. good tip on using LOOP instead. ive since figured out how to use just a function for this task. – Tallula

Answer 2

Forget recursive macros. They are a pain and really only for advanced Lisp users.

A simple, non-recursive version:

(defmacro count-true (&rest forms)
  `(+
    ,@(loop for form in forms
            collect `(if ,form 1 0))))

CL-USER 111 > (macroexpand '(count-true (plusp 3) (zerop 2)))
(+ (IF (PLUSP 3) 1 0) (IF (ZEROP 2) 1 0))

Well, here is a recursive macro:

(defmacro count-true (&rest forms)
  (if forms
      `(+ (if ,(first forms) 1 0)
          (count-true ,@(rest forms)))
    0))

Discant

Why not count ,form instead of + and collect? – Salim

Because the LOOP does not count the results. It generates code. It is gone after expansion. – Discant

thanks for the response. its direct and answers the question of working with &rest parameters in a recursive macro. – Tallula

Answer 3

The problem is that your macro expands to an infinite form. The system will try to expand it all during the macro expansion phase and thus must run out memory.

Note that the test for the end of the forms list is never evaluated but expressed as code. It should be outside the backtick expression. And aas the other person explained, the (cdr forms) needs to be evaluated at macro expansion time as well, not left as code to be compiled.

I.e. something like this (untested):

(defmacro count-true (&rest forms)
  (if forms
      `(if (car ',forms)
           (1+ (count-true ,@(cdr forms)))
         (count-true ,@(cdr forms)))
    0))

Vickeyvicki

Answer 4

I believe that you are under two false impressions regarding what macros are.

Macros are written for expansion, functions for execution. If you write a recursive macro, it will recursively expand, without executing anything of the code it produces. A macro is not at all something like an inlined function!

When you write a macro, it can expand to function calls. When you write a macro, you do not venture into "macro land" where functions would be unavailable. It makes no sense at all to write count-true as a macro.

Salim

the idea of a recursive macro is usually that it expands into code, which uses that macro again, but on simpler/smaller arguments. The macro expansion halts when the macro is used in its simplest form. So the recursion is done via the macro expansion mechanism... – Discant

thanks for getting my head straight. i figured out how to accomplish what i was looking for using just a function. i was under the impression i had to use a macro because of the way i thought i was interacting with evaluated expressions. now i see how i was mistaken. – Tallula

Answer 5

This is a nice application for easy macro recursion:

(defmacro count-true (&rest forms)
  (cond
    ((null forms) 0)
    ((endp (rest forms)) `(if ,(first forms) 1 0))
    (t `(+ (count-true ,(first forms)) (count-true ,@(rest forms))))))

Tests:

[2]> (count-true)
0
[3]> (count-true nil)
0
[4]> (count-true t)
1
[5]> (count-true nil t)
1
[6]> (count-true t nil)
1
[7]> (count-true t t)
2
[8]> (count-true nil nil)
0
[9]> (macroexpand '(count-true))
0 ;
T
[10]> (macroexpand '(count-true x))
(IF X 1 0) ;
T
[11]> (macroexpand '(count-true x y))
(+ (COUNT-TRUE X) (COUNT-TRUE Y)) ;
T
[12]> (macroexpand '(count-true x y z))
(+ (COUNT-TRUE X) (COUNT-TRUE Y Z)) ;
T

The macro has to reason about the input syntax and generate the code which does the counting; you must not get mixed up between generating the code and evaluating.

You're going wrong right off the bat when you're doing this:

`(cond ((null ,forms ...) ...)

you're pushing the meta-syntactic calculation (how many forms do we have in the syntax?) into the generated code template be evaluated at run-time. You have the right pieces in this base case, but they are staged wrong. In my solution, I have the cond just in the macro body itself, not in a backquote:

(cond ((null forms) ...) ...)

Basically:

(cond (<if the syntax is like this> <generate this>)
      (<if the syntax is like that> <generate that>)
      ...)

If you don't know what to do, write out the code that you want the macro to write. For instance:

;; I want this semantics:
(if (blah) 1 0)   ;; count 1 if (blah) is true, else 0

;; But I want it with this syntax:
(count-true (blah))

Okay, so for this exact case, we would write:

(defmacro count-true (single-form)
  `(if ,single-form 1 0))

Done! Now suppose we want to support (count-true) with no forms at all.

Wanted Syntax                   Translation

(count-true)                    0
(count-true x)                  (if x 1 0)

When there is a form, the if expansion stays, but when there are no forms, we just want a constant zero. Easy, make the argument optional:

(defmacro count-true (&optional (single-form nil have-single-form))
   (if have-single-form
     `(if ,single-form 1 0)  ;; same as before
      0))                    ;; otherwise zero

Finally, extend to N-ary form:

Wanted Syntax                   Translation

(count-true)                    0
(count-true x)                  (if x 1 0)
(count-true x y)                (+ (if x 1 0) (if y 1 0))
                                   ^^^^^^^^^^ ^^^^^^^^^^

But! now we note that the underlined terms correspond to the output of the single case.

(count-true x y)                (+ (count-true x) (count-true y))

Which generalizes

(count-true x y z ...)          (+ (count-true x) (count-true y z ...))

That corresponds in a straightforward way to the code generation template with car/cdr recursion:

`(+ (count-true ,CAR) (count-true ,*CDR))  

Uriah

Answer 6

As others have said, avoid recursive macros. If you're willing to do this in a function, you can use apply:

(defun count-true (&rest forms)
  (cond
    ((null forms) 0)
    (t (+ 1 (apply #'count-true (cdr forms))))))

Phototypography