Recursive macros

[mabu77]

Hi all,

while studying the 99 Lisp Problems (http://www.ic.unicamp.br/~meidanis/cour ... blems.html) Joao Meidanis derived from the 99 Prolog Problems, I came across a case where the argument of a predicate should not be evaluated to save the user the quoting (P54). It's a test if a given term is a valid binary tree. I was able to code a recursive function which does this without a problem and thought transforming this to a macro would be the solution to get ride of the quoting.

So, I had this function working:

Code: Select all

(defun istreep (tree)
  "Predicate for checking if `tree' is a valid binary tree."
  (cond ((null tree) 't)
	((and (= (length tree) 3) (atom (first tree)) (istreep (second tree)) (istreep (third tree))) 't)
	(t nil)))

CL-USER> (istreep '(a (b (d nil nil) (e nil nil)) (c nil (f (g nil nil)))))
NIL
CL-USER> (istreep '(a (b (d nil nil) (e nil nil)) (c nil (f (g nil nil) nil))))
T

Simply converting this to a macro is obviously not working.

Code: Select all

(defmacro istreem (tree)
  "Predicate for checking if `tree' is a valid binary tree."
  `(cond ((null ,tree) 't)
	((and (= (length ,tree) 3) (atom (first ,tree)) (istreem (second ,tree)) (istreem (third ,tree))) 't)
	(t nil)))

And sbcl gives me the following warnings:

CL-USER> (istreem (a (b (d nil nil) (e nil nil)) (c nil (f (g nil nil) nil))))

; in: ISTREEM (A (B (D NIL NIL) (E NIL NIL)) (C NIL (F (G NIL NIL) NIL)))
; (B (D NIL NIL) (E NIL NIL))
;
; caught STYLE-WARNING:
; undefined function: B

; (D NIL NIL)
;
; caught STYLE-WARNING:
; undefined function: D

; (E NIL NIL)
;
; caught STYLE-WARNING:
; undefined function: E
;
; compilation unit finished
; Undefined functions:
; B D E
; caught 3 STYLE-WARNING conditions

and quits:

The function COMMON-LISP-USER::D is undefined.
[Condition of type UNDEFINED-FUNCTION]

Restarts:
0: [RETRY] Retry SLIME REPL evaluation request.
1: [*ABORT] Return to SLIME's top level.
2: [TERMINATE-THREAD] Terminate this thread (#<THREAD "repl-thread" RUNNING {1003208211}>)

Backtrace:
0: ("bogus stack frame")
1: ((EVAL (ISTREEM (A (B (D NIL NIL) (E NIL NIL)) (C NIL (F (G NIL NIL) NIL))))))
2: (SB-INT:SIMPLE-EVAL-IN-LEXENV (B (D NIL NIL) (E NIL NIL)) #<NULL-LEXENV>)
3: (SB-INT:SIMPLE-EVAL-IN-LEXENV (A (B (D NIL NIL) (E NIL NIL)) (C NIL (F # NIL))) #<NULL-LEXENV>)
4: (SB-INT:SIMPLE-EVAL-IN-LEXENV (NULL (A (B # #) (C NIL #))) #<NULL-LEXENV>)
5: (SB-INT:SIMPLE-EVAL-IN-LEXENV (ISTREEM (A (B # #) (C NIL #))) #<NULL-LEXENV>)
6: (EVAL (ISTREEM (A (B # #) (C NIL #))))
--more--

I thought I found the solution of my problem in chapter 10 of "On lisp" in the example of defining nth as a recursive macro, etc. So I tried a macro calling the recursive function istreep which worked fine before:

Code: Select all

(defmacro istree (tree)
  "Predicate for checking if `tree' is a valid binary tree."
  `(when (listp ,tree)
     (istreep ,tree)))

But I end up with the same error:

The function COMMON-LISP-USER::D is undefined.
[Condition of type UNDEFINED-FUNCTION]

Restarts:
0: [RETRY] Retry SLIME REPL evaluation request.
1: [*ABORT] Return to SLIME's top level.
2: [TERMINATE-THREAD] Terminate this thread (#<THREAD "repl-thread" RUNNING {1003208211}>)

Backtrace:
0: (SYMBOL-FUNCTION D)
1: (SB-INT:SIMPLE-EVAL-IN-LEXENV (D NIL NIL) #<NULL-LEXENV>)
2: (SB-INT:SIMPLE-EVAL-IN-LEXENV (B (D NIL NIL) (E NIL NIL)) #<NULL-LEXENV>)
3: (SB-INT:SIMPLE-EVAL-IN-LEXENV (A (B (D NIL NIL) (E NIL NIL)) (C NIL (F # NIL))) #<NULL-LEXENV>)
4: (SB-INT:SIMPLE-EVAL-IN-LEXENV (LISTP (A (B # #) (C NIL #))) #<NULL-LEXENV>)
5: (SB-INT:SIMPLE-EVAL-IN-LEXENV (ISTREE (A (B # #) (C NIL #))) #<NULL-LEXENV>)
6: (EVAL (ISTREE (A (B # #) (C NIL #))))

Before this all happened, I was thinking that I am starting to see how macros, expansion and quoting work. But now I am just thrown back at the beginning Could anyone give me a short hint or whatever it needs to get back on track?

Best regards
Martin

[ramarren]

I came across a case where the argument of a predicate should not be evaluated to save the user the quoting (P54).

That is not a good motivation to use a macro. A macro should be use to create a custom syntax extension or do some calculation at compile time.

Simply converting this to a macro is obviously not working.

It works, since simply converting it to a macro would look like, assuming there is a function isteep defined at compile time:

Code: Select all

(demacro istreepm (tree)
  "Predicate for checking if `tree' is a valid binary tree."
  (cond ((null tree) 't)
   ((and (= (length tree) 3) (atom (first tree)) (istreep (second tree)) (istreep (third tree))) 't)
   (t nil)))

or even:

Code: Select all

(defmacro istreepm (tree) (istreep tree))

Since you only allow constant literal trees, the check can be performed at compilation time and the result can be used directly as macro expansion. That doesn't really sound very useful, though.

So I tried a macro calling the recursive function istreep which worked fine before:

You need to quote the function argument in macro expansion. Expansion is evaluated using standard evaluation rules, and without a quote the tree is evaluated as code, which obviously doesn't work:

Code: Select all

(defmacro istree (tree)
  "Predicate for checking if `tree' is a valid binary tree."
  `(when (listp ',tree)
     (istreep ',tree)))

But since only literal trees are allowed you might just as well get rid of the backquote and call the function directly, as long as it is defined at compile time.

Edit: a way to define this macro recursively using just macros would be

Code: Select all

(defmacro istreepm2 (tree)
  "Predicate for checking if `tree' is a valid binary tree."
  (cond ((null tree) 't)
        ((and (= (length tree) 3) (atom (first tree))) `(and (istreepm2 ,(second tree)) (istreepm2 ,(third tree))))
        (t nil)))

but that doesn't really make sense. Don't use macros where functions make more sense.

[mabu77]

Thanks a lot for you reply. I do understand that I got something wrong in my understanding how evaluation works. I assume I just have to got back to the beginning and re-think everything carefully.

Regards
Martin