Is it possible to rewrite recursive function as macro in lisp?

Question

I wrote this quicksort function:

(defun quicksort (lst)
  (if (null lst)
      nil
      (let ((div  (car lst))
            (tail (cdr lst)))
        (append (quicksort (remove-if-not (lambda (x) (< x div)) tail))
                (list div)
                (quicksort (remove-if     (lambda (x) (< x div)) tail))))))

but I can't rewrite it as macro, it does not work, nor does, for example, this simple foo (recursive sum - I know, a little silly, but just as example):

(defun Suma (lst)
  (if (cdr lst) 
      (+ (Suma (cdr lst))
         (car lst))
      (car lst)))

works properly, but the macro:

(defmacro SumaMacro (lst)
  '(if (cdr lst)
       '(+ (prog (SUMAMACRO (cdr lst)))
           (prog (car lst)))
       '(car lst)))

seems to be wrong. Does someone have any suggestions about rewriting recursive functions as macro?

Answer 1

You're mixing macro and runtime; or in other words, you're mixing values and syntax. Here's a very simple example:

(defmacro while (condition &body body)
  `(when ,condition ,@body (while ,condition ,@body)))

The bad thing here is that the macro doesn't execute the body, it just constructs a piece of code with the given body in it. So, when there's that kind of a loop in a function, it's protected by some conditional like if which will prevent an infinite loop. But in this macro code there is no such condition -- you can see that the macro expands into the exact original form, which means that it's trying to expand into some infinite piece of code. It's just as if you've written

(defun foo (blah)
  (cons 1 (foo blah)))

then hooked that generator function into the compiler. So to do these kinds of runtime loops, you'll have to use a real function. (And when that's needed, you can use labels to create a local function to do the recursive work.)

Answer 2

It makes no sense to write recursive functions like SUM or QUICKSORT as macros. Also, no, in general it is not possible. A macro expands source code. At compile time the macro sees only the source code, but not the real arguments the code is being called with. After compilation the macros is gone and replaced with the code it produces. This code then later gets called with arguments. So the macro can't do computation at compile time, based on argument values that are known only at runtime.

The exception is: when the argument value is known at compile time / macro expansion time, then the macro can expand to a recursive macro call to itself. But that is really advanced macro usage and nothing that one would add to code to be maintained by other programmers.

Rule of thumb: If you want to do recursive computations, then use functions. If you want to process source code, then use a macro.

Also, try to use Lisp-like formatting. The editor counts the parentheses, does highlighting and indentation. Don't put parentheses on their own lines, they feel lonely there. The usual Lisp style is more compact and uses also the horizontal space more. If you work with lists, then use FIRST and REST, instead of CAR and CDR.

Your 'suma' function would look like this:

(defun suma (list) 
  (if (rest list)
      (+ (suma (rest list))
         (first list))
    (first list)))

Forget about the macro. But, if you want to learn more about macros, then the book 'On Lisp' by Paul Graham (available as a download) is a good source of knowledge.