Macros That Write Macros - Compile Error

Question

When I compile the following code, SBCL complains that g!-unit-value and g!-unit are undefined. I'm not sure how to debug this. As far as I can tell, flatten is failing.

When flatten reaches the unquoted part of defunits, it seems like the entire part is being treated as an atom. Does that sound correct?

The following uses code from the book Let over Lambda:

Paul Graham Utilities

(defun symb (&rest args)
  (values (intern (apply #'mkstr args))))

(defun mkstr (&rest args)
  (with-output-to-string (s)
    (dolist (a args) (princ a s))))

(defun group (source n)
  (if (zerop n) (error "zero length"))
  (labels ((rec (source acc)
             (let ((rest (nthcdr n source)))
               (if (consp rest)
                   (rec rest (cons (subseq source 0 n) acc))
                   (nreverse (cons source acc))))))
    (if source (rec source nil) nil)))

(defun flatten (x)
  (labels ((rec (x acc)
             (cond ((null x) acc)
                   ((atom x) (cons x acc))
                   (t (rec (car x) (rec (cdr x) acc))))))
    (rec x nil)))

Let Over Lambda Utilities - Chapter 3

(defmacro defmacro/g! (name args &rest body)
  (let ((g!-symbols (remove-duplicates
               (remove-if-not #'g!-symbol-p
                              (flatten body)))))
    `(defmacro ,name ,args
       (let ,(mapcar
              (lambda (g!-symbol)
                `(,g!-symbol (gensym ,(subseq
                                       (symbol-name g!-symbol)
                                       2))))
              g!-symbols)
         ,@body))))

(defun g!-symbol-p (symbol-to-test)
  (and (symbolp symbol-to-test)
       (> (length (symbol-name symbol-to-test)) 2)
       (string= (symbol-name symbol-to-test)
                "G!"
                :start1 0
                :end1 2)))

(defmacro defmacro! (name args &rest body)
  (let* ((o!-symbols (remove-if-not #'o!-symbol-p args))
         (g!-symbols (mapcar #'o!-symbol-to-g!-symbol o!-symbols)))
    `(defmacro/g! ,name ,args
       `(let ,(mapcar #'list (list ,@g!-symbols) (list ,@o!-symbols))
          ,(progn ,@body)))))

(defun o!-symbol-p (symbol-to-test)
  (and (symbolp symbol-to-test)
       (> (length (symbol-name symbol-to-test)) 2)
       (string= (symbol-name symbol-to-test)
                "O!"
                :start1 0
                :end1 2)))

(defun o!-symbol-to-g!-symbol (o!-symbol)
  (symb "G!" (subseq (symbol-name o!-symbol) 2)))

Let Over Lambda - Chapter 5

(defun defunits-chaining (u units prev)
  (if (member u prev)
      (error "~{ ~a~^ depends on~}"
             (cons u prev)))
  (let ((spec (find u units :key #'car)))
    (if (null spec)
        (error "Unknown unit ~a" u)
        (let ((chain (second spec)))
          (if (listp chain)
              (* (car chain)
                 (defunits-chaining
                     (second chain)
                     units
                   (cons u prev)))
              chain)))))

(defmacro! defunits (quantity base-unit &rest units)
  `(defmacro ,(symb 'unit-of- quantity)
       (,g!-unit-value ,g!-unit)
     `(* ,,g!-unit-value
         ,(case ,g!-unit
                ((,base-unit) 1)
                ,@(mapcar (lambda (x)
                            `((,(car x))
                              ,(defunits-chaining
                                (car x)
                                (cons
                                 `(,base-unit 1)
                                 (group units 2))
                                nil)))
                          (group units 2))))))

Asdic

For some reason the function g!-symbol-p does not compile in Clozure Common Lisp Version 1.11 (DarwinX8664)! – Smear

Is the something similar to what SBCL was doing? – Asdic

Answer 1

This is kind of tricky:

Problem: you assume that backquote/comma expressions are plain lists.

You need to ask yourself this question:

What is the representation of a backquote/comma expression?

Is it a list?

Actually the full representation is unspecified. See here: CLHS: Section 2.4.6.1 Notes about Backquote

We are using SBCL. See this:

* (setf *print-pretty* nil)

NIL


* '`(a ,b)

(SB-INT:QUASIQUOTE (A #S(SB-IMPL::COMMA :EXPR B :KIND 0)))

So a comma expression is represented by a structure of type SB-IMPL::COMMA. The SBCL developers thought that this representation helps when such backquote lists need to be printed by the pretty printer.

Since your flatten treats structures as atoms, it won't look inside...

But this is the specific representation of SBCL. Clozure CL does something else and LispWorks again does something else.

Clozure CL:

? '`(a ,b)
(LIST* 'A (LIST B))

LispWorks:

CL-USER 87 > '`(a ,b)
(SYSTEM::BQ-LIST (QUOTE A) B)

Debugging

Since you found out that somehow flatten was involved, the next debugging steps are:

First: trace the function flatten and see with which data it is called and what it returns.

Since we are not sure what the data actually is, one can INSPECT it.

A debugging example using SBCL:

* (defun flatten (x)                                                                                         
    (inspect x)                                                                                              
    (labels ((rec (x acc)                                                                                    
               (cond ((null x) acc)                                                                          
                     ((atom x) (cons x acc))                                                                 
                     (t (rec (car x) (rec (cdr x) acc))))))                                                  
      (rec x nil)))
STYLE-WARNING: redefining COMMON-LISP-USER::FLATTEN in DEFUN

FLATTEN

Above calls INSPECT on the argument data. In Common Lisp, the Inspector usually is something where one can interactively inspect data structures.

As an example we are calling flatten with a backquote expression:

* (flatten '`(a ,b))

The object is a proper list of length 2.
0. 0: SB-INT:QUASIQUOTE
1. 1: (A ,B)

We are in the interactive Inspector. The commands now available:

> help

help for INSPECT:
  Q, E        -  Quit the inspector.
  <integer>   -  Inspect the numbered slot.
  R           -  Redisplay current inspected object.
  U           -  Move upward/backward to previous inspected object.
  ?, H, Help  -  Show this help.
  <other>     -  Evaluate the input as an expression.
Within the inspector, the special variable SB-EXT:*INSPECTED* is bound
to the current inspected object, so that it can be referred to in
evaluated expressions.

So the command 1 walks into the data structure, here a list.

> 1

The object is a proper list of length 2.
0. 0: A
1. 1: ,B

Walk in further:

> 1

The object is a STRUCTURE-OBJECT of type SB-IMPL::COMMA.
0. EXPR: B
1. KIND: 0

Here the Inspector tells us that the object is a structure of a certain type. That's what we wanted to know.

We now leave the Inspector using the command q and the flatten function continues and returns a value:

> q

(SB-INT:QUASIQUOTE A ,B)

Harwilll

Thank you. Wow, it's a structure. I don't suppose anyone has made a portable quasiquote library, have they? – Asdic

This is precisely the explanation I was looking for to understand why the defmacro/g! macro defined in chap 3 of LOL (letoverlambda.com/index.cl/guest/chap3.html) is not working! Thanks – Smear

Answer 2

For anyone else who is trying to get defmacro! to work on SBCL, a temporary solution to this problem is to grope inside the unquote structure during the flatten procedure recursively flatten its contents:

(defun flatten (x)
  (labels ((flatten-recursively (x flattening-list)
             (cond ((null x) flattening-list)
                   ((eq (type-of x) 'SB-IMPL::COMMA) (flatten-recursively (sb-impl::comma-expr x) flattening-list))
                   ((atom x) (cons x flattening-list))
                   (t (flatten-recursively (car x) (flatten-recursively (cdr x) flattening-list))))))
    (flatten-recursively x nil)))

But this is horribly platform dependant. If I find a better way, I'll post it.

Asdic

Answer 3

In case anyone's still interested in this one, here are my three cents. My objection to the above modification of flatten is that it might be more naturally useful as it were originally, while the problem with representations of unquote is rather endemic to defmacro/g!. I came up with a not-too-pretty modification of defmacro/g! using features to decide what to do. Namely, when dealing with non-SBCL implementations (#-sbcl) we proceed as before, while in the case of SBCL (#+sbcl) we dig into the sb-impl::comma structure, use its expr attribute when necessary and use equalp in remove-duplicates, as we are now dealing with structures, not symbols. Here's the code:

(defmacro defmacro/g! (name args &rest body)
  (let ((syms (remove-duplicates
               (remove-if-not #-sbcl #'g!-symbol-p
                              #+sbcl #'(lambda (s)
                                         (and (sb-impl::comma-p s)
                                              (g!-symbol-p (sb-impl::comma-expr s))))
                              (flatten body))
               :test #-sbcl #'eql #+sbcl #'equalp)))
    `(defmacro ,name ,args
       (let ,(mapcar
              (lambda (s)
                `(#-sbcl ,s #+sbcl ,(sb-impl::comma-expr s)
                         (gensym ,(subseq
                                   #-sbcl
                                   (symbol-name s)
                                   #+sbcl
                                   (symbol-name (sb-impl::comma-expr s))
                                   2))))
              syms)
         ,@body))))

It works with SBCL. I have yet to test it thoroughly on other implementations.

Chug

Thanks a lot for this fix. Was quite perplexed while trying to play with some examples from Let Over Lambda. – Flinty