Is it possible to rewrite a recursive function as a 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 a macro, it doesn’t work and doesn’t, for example, it is a simple foo (recursive sum - I know, a little stupid, but exactly the same):

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

works correctly, but the macro:

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

seems wrong. Does anyone have any suggestions for rewriting recursive functions as a macro?

Answer 1

You mix macro and runtime; or, in other words, you mix values ​​and syntax. Here is a very simple example:

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

The bad thing is that a macro does not execute the body, it just creates a piece of code with the given body in it. Thus, when there is such a loop in a function, it is protected by some conditional if types that prevent an infinite loop. But there is no such condition in this macro codec - you can see that the macro expands to the exact original form, which means that it is trying to expand to some infinite piece of code. It's as if you wrote

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

then connected this generator function to the compiler. Therefore, to execute such runtime cycles you will need to use a real function. (And when necessary, you can use labels to create a local function to do recursive work.)

Answer 2

It makes no sense to write recursive functions like SUM or QUICKSORT like macros. Also, no, generally speaking, this is not possible. The macro extends the source code. At compile time, the macro only sees the source code, but not the real arguments that the code calls. After compilation, the macros disappear and are replaced by the code that it produces. Then this code is called with arguments. Thus, a macro cannot perform calculations at compile time based on argument values ​​that are known only at run time.

The exception is: when the value of the argument is known during compilation / macro distribution time, the macro can expand to recursively invoke the macro on its own. But this is really an extended use of macros and nothing that could be added to code supported by other programmers.

Rule of thumb: If you want to perform recursive calculations, use functions. If you want to process the source code, use a macro.

Also, try using Lisp formatting. The editor counts parentheses, makes selections and indents. Do not put parentheses on your lines; they feel lonely. The usual Lisp style is more compact and uses horizontal space even more. If you work with lists, use FIRST and REST instead of CAR and CDR.

Your suma function will 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 know more about macros, then the book " On Lisp ", written by Paul Graham (available for download), is a good source of knowledge.