How to manage recursion in Common Lisp macros

0
votes

I need to write a Common Lisp macro that take a symbol and a list. The list is composed by lists of two elements: a symbol and a string, like this:

((X "foo") (Y "bar") (Z "qwerty"))

The macro works recursively, it search the symbol in the list, and if it found symbol return T, otherwise return NIL. I write this code:

(defmacro already-exist (symbol my-list)
  (cond ((null (eval my-list)) NIL)
        ((eql (caar (eval my-list)) symbol)
     T)
    (T `(already-exist symbol ,(cdr (eval my-list))))))

but the problem is in the recursive part. In fact, if I try to run the macro with a list that doesn't have symbol as part of the first element, I obtain an error. For example:

(defparameter listt '((X "foo") (Y "bar") (Z "qwerty")))

(already-exist Y listt)

The error I obtain is "illegal function call". I think it happens because the macro try to evaluate Y as a function call. How could I solve this problem? What is, in general, the best way to write recursive macros in Common Lisp?

3
recursionmacroslispcommon-lisp
You should use a function for this. Macros are used for generating code. You could also just use ASSOC (or (member ... :key #'first)) to see if the key already exists. – jkiiski
@jkiiski I need to pass an unquoted symbol to the macro, and I don't want the code evaluates that symbol, so for this reason I have choosen to write a macro instead a function. Is there any manner to obtain the same behavior in a function? If you know please tell me. Anyway, i didn't know ASSOC, so thanks! I'll keep in mind! – Jim
You should just quote the symbol or use keywords. Messing up the evaluation of a form that looks like a function would confuse people reading the code. – jkiiski
Unless you know the list at macroexpansion time you can't do this with a macro. You can do it by having a macro which expands to a function. However, I'm with jkiiski here: just use quote. – user5920214

3 Answers

3
votes

What is the actual error?

The actual error is this:

CL-USER 3 > (already-exist Y listt)

Error: Illegal car (Y "bar") in compound form ((Y "bar") (Z "qwerty")).

So you are trying to execute this expression, which is not valid Lisp code:

((Y "bar") (Z "qwerty")).

Error 1:

Your code gets a symbol for my-list, which you evaluate. The next time it gets a list, which you should not evaluate.

Error 2:

You create a form with symbol, instead of the value of symbol.

Attempt to repair that leads to an ugly solution

  • attempt to only evaluate my-list when it has a symbol as a value
  • pass the value of symbol by putting a comma in front of it

Example:

CL-USER 2 > (defmacro already-exist (symbol my-list)                            
              (when (symbolp my-list)                                           
                (setf my-list (eval my-list)))                                  
              (cond ((null my-list)                                             
                     NIL)                                                       
                    ((eql (caar my-list) symbol)                                
                     T)                                                         
                    (T `(already-exist ,symbol ,(cdr my-list)))))
ALREADY-EXIST

CL-USER 3 > (defparameter listt '((X "foo") (Y "bar") (Z "qwerty")))
LISTT

CL-USER 4 > (already-exist Y listt)
T

CL-USER 5 > (already-exist A listt)
NIL

But it makes little sense and creates new problems.

It's poor style to write recursive macro invocations which call eval. eval can't get the value of lexical bindings, because evaluation does not take place inside the lexical environment.

Use a function

CL-USER 10 > (member 'y listt :key #'car)
((Y "bar") (Z "qwerty"))

Which means true.

4
votes

I need to write a Common Lisp macro [...] The macro works recursively.

You don't really need a macro, in fact a macro cannot solve the problem if your values are only known at runtime. You need to quote symbols if you want them to be left unevaluated.

... (eval my-list) ...

Invoking eval from a macro is a big code smell. Your macro is working with code, the list symbol does not mean anything at this point except that it is a symbol. The macro is most likely not going to be expanded in an environment where list is bound to a meaningful value (besides, eval works in the null lexical environment).

It is possible to have a Recursive expansion, but macros by themselves are not recursive:

* (defmacro foo (x) (foo x))
; in: DEFMACRO FOO
;     (FOO X)
; 
; caught STYLE-WARNING:
;   undefined function: FOO
; 
; compilation unit finished
;   Undefined function:
;     FOO
;   caught 1 STYLE-WARNING condition
STYLE-WARNING:
   FOO is being redefined as a macro when it was previously assumed to be a function.
* (foo 3)

debugger invoked on a UNDEFINED-FUNCTION in thread
#<THREAD "main thread" RUNNING {100399C503}>:
  The function COMMON-LISP-USER::FOO is undefined.

Macroexpansion is applied in a fixpoint way: start from code X0, compute X1 as the macroexpansion of X0, and continue until nothing macroexpands anymore. Your macro does not call itself, the macroexpansion facility calls it as often as necessary after each pass (that's also why you can't establish dynamic bindings during macroexpansion, unless you call macroexpand manually).

You can macroexpand your macro into code that also calls your macro, though. But you have to be careful that it does not so unconditionally, otherwise you are going to have an infinite macroexpansion.

If list is going to be a value known only at runtime, you need to write a regular function. Basically, you want to do:

(member symbol list :key #'first)

See MEMBER, MACROEXPAND.

2
votes

recursive macros are not possible

Imagine you tried that:

(defmacro expand (&rest elements)
  (if (not (null (cdr elements)))
      `(+ ,(car elements) ,(expand (cdr elements)))
      (car elements)))

Now when the macro function is being compiled it expands all macros so it calls (expand (cdr elements)) in it..

(defmacro expand (&rest elements)
  (if (not (null (cdr elements)))
      `(+ ,(car elements) (+ (cdr elements) (+ (cdr elements) (+ (cdr elements) (+ (cdr elements) ...))))
      (car elements)))

Do you see it? Now imagine you instead just expand the first part and not recurse but leave a simpler expression with expandinstead:

(defmacro expand (&rest elements)
  (if (not (null (cdr elements)))
      `(+ ,(car elements) (expand ,@(cdr elements)))
      (car elements)))

This is completely different since the macro never uses the macro directly. However (expand 1 2 3) expands to (+ 1 (expand 2 3)) and lisp continues to expand the macros until there are none left, leaving (+ 1 (+ 2 3)) without recursion

recursive functions are ok in macros:

(defmacro expand (&rest elements)
  (labels ((recfun (elements)
             (if (not (null (cdr elements)))
                 `(+ ,(car elements) ,(recfun (cdr elements)))
                 (car elements))))
    (recfun elements)))

It doesn't need to be a locally defined function either. Usually I implement most of the functionality as a function and make a macro to delay evaluation of some arguments leaving the macro just calling the functions:

(defun make-env-fun (names)
  (mapcar (lambda (name) (cons name (symbol-function name))) names))

(defmacro make-env (&rest variables)
  `(make-env-fun ',variables))

(make-env cons car cdr)
; ==> ((cons . #<system-function cons>) 
;      (car . #<system-function car>)
;      (cdr . #<system-function cdr>))

So the macro exists since I didn't want to do (make-env 'cons 'car 'cdr) or (make-env '(cons car cdr)). The macro only fixes that problem and not the actual work the function is still doing.

So to relate to your problem you want a macro that allows (already-exist symbol ((symbol "bla"))) instead of (already-exist-fun 'symbol '((symbol "bla"))). Do you see it?