Common lisp macro not calling function

Question

I am working on a complicated macro and have run into a roadblock.

(defmacro for-each-hashtable-band (body vars on &optional counter name)
  `(block o
     (with-hash-table-iterator (next-entry ,on)
       (destructuring-bind
            ,(apply #'append vars)
            (let ((current-band (list ,@(mapcar #'not (apply #'append vars)))))
              (for (i 1 ,(length (apply #'append vars)) 2)
                (multiple-value-bind
                      (succ k v) (next-entry)
                  (if succ
                      (progn
                        (setf (nth i current-band) k)
                        (setf (nth (+ 1 i) current-band) v))
                      (return-from o nil))))
              current-band)
          ,@body))))

im getting "Evaluation aborted on #<UNDEFINED-FUNCTION NEXT-ENTRY {100229C693}>" i dont understand why next-entry appears to be invisible to the macro i have created.

I've tried stripping down this to a small replicable example but i couldnt find a minimal scenario without the macro i created where next-entry would be invisible besides this scenario no matter what I tried, i've always managed to find a way to call next-entry in my other examples so im stumped as to why i cannot get it working here

I've tested the for macro ive created and it seems to generally work in most cases but for some reason it cannot see this next-entry variable. How do i make it visible?

Answer 1

In your code there are multiple places where the macro generates bindings in a way that is subject to variable capture (pdf).

(defmacro for-each-hashtable-band (body vars on &optional counter name)
  `(block o ;; VARIABLE CAPTURE
     (with-hash-table-iterator (next-entry ,on) ;; VARIABLE CAPTURE
       (destructuring-bind ,(apply #'append vars)
           (let ((current-band ;;; VARIABLE CAPTURE
                   (list ,@(mapcar #'not (apply #'append vars)))))
             (for
                 (i ;;; VARIABLE CAPTURE
                  1 ,(length (apply #'append vars)) 2)
                 (multiple-value-bind (succ k v) ;;; VARIABLE CAPTURE
                     ,(next-entry) ;;; WRONG EVALUATION TIME
                   (if succ
                       (progn
                         (setf (nth i current-band) k)
                         (setf (nth (+ 1 i) current-band) v))
                       (return-from o nil))))
             current-band)
         ,@body))))

A simplified example of such a capture is:

`(let ((x 0)) ,@body)

Here above, the x variable is introduced, but if the code is expanded in a context where xis already bound, then body will not be able to reference that former x binding and will always see x bound to zero (you generally don't want this behavior).

Write a function instead

Instead of writing a big macro for this, let's first try understanding what you want to achieve and write instead a higher-order function, ie. a function that calls user-provided functions.

If I understand correctly, your function iterates over a hash-table by bands of entries. I assume vars holds a list of (key value) pairs of symbols, for example ((k1 v1) (k2 v2)). Then, body works on all the key/value pairs in the band.

In the following code, the function map-each-hashtable-band accepts a function, a hash-table, and instead of vars it accepts a size, the width of the band (the number of pairs).

Notice how in your code, you only have one loop, which builds a band using the hash-table iterator. But then, since the macro is named for-each-hashtable-band, I assume you also want to loop over all the bands. The macro with-hash-table-iterator provides an iterator but does not loop itself. That's why here I have two loops.

(defun map-each-hashtable-band (function hash-table band-size)
  (with-hash-table-iterator (next-entry hash-table)
    (loop :named outer-loop :do
      (loop
        :with key and value and next-p
        :repeat band-size
        :do (multiple-value-setq (next-p key value) (next-entry))
        :while next-p
        :collect key into current-band
        :collect value into current-band
        :finally (progn
                   (when current-band
                     (apply function current-band))
                   (unless next-p
                     (return-from outer-loop)))))))

For example:

(map-each-hashtable-band (lambda (&rest band) (print `(:band ,band)))
                         (alexandria:plist-hash-table
                          '(:a 0 :b 1 :c 2 :d 3 :e 4 :f 5 :g 6))
                         2)

NB. Iterating over a hash-table happens in an arbitrary order, there is no guarantee that you'll see the entries in any particular kind of order, this is implementation-dependant.

With my current version of SBCL this prints the following:

(:BAND (:A 0 :B 1)) 
(:BAND (:C 2 :D 3)) 
(:BAND (:E 4 :F 5)) 
(:BAND (:G 6)) 

Wrap the function in a macro

The previous function might not be exactly the behavior you want, so you need to adapt to your needs, but once it does what you want, you can wrap a macro around it.

(defmacro for-each-hashtable-band (vars hash-table &body body)
  `(map-each-hashtable-band (lambda ,(apply #'append vars) ,@body)
                            ,hash-table
                            ,(length vars)))

For example:

(let ((test (alexandria:plist-hash-table '(:a 0 :b 1 :c 2 :d 3 :e 4 :f 5))))
  (for-each-hashtable-band ((k1 v1) (k2 v2)) test
    (format t "~a -> ~a && ~a -> ~a ~%" k1 v1 k2 v2)))

This prints:

A -> 0 && B -> 1 
C -> 2 && D -> 3 
E -> 4 && F -> 5 

Macro-only solution, for completeness

If you want to have only one, single macro, you can start by inlining the body of the above function in the macro, you don't need to use apply anymore, but instead you need to establish bindings around the body, using destructuring-bind as you did. A first draft would be to simply as follows, but notice that this is not a proper solution:

(defmacro for-each-hashtable-band (vars hash-table &body body)
  (let ((band-size (length vars)))
    `(with-hash-table-iterator (next-entry ,hash-table)
       (loop :named outer-loop :do
         (loop
           :with key and value and next-p
           :repeat ,band-size
           :do (multiple-value-setq (next-p key value) (next-entry))
           :while next-p
           :collect key into current-band
           :collect value into current-band
           :finally (progn
                      (when current-band
                        (destructuring-bind ,(apply #'append vars) current-band
                          ,@body))
                      (unless next-p
                        (return-from outer-loop))))))))

In order to be free of variable capture problems with macros, each temporary variable you introduce must be named after a symbol that cannot exist in any context you expand your code. So instead we first unquote all the variables, making the macro definition fail to compile:

(defmacro for-each-hashtable-band (vars hash-table &body body)
  (let ((band-size (length vars)))
    `(with-hash-table-iterator (,next-entry ,hash-table)
       (loop :named ,outer-loop :do
         (loop
           :with ,key and ,value and ,next-p
           :repeat ,band-size
           :do (multiple-value-setq (,next-p ,key ,value) (,next-entry))
           :while ,next-p
           :collect ,key into ,current-band
           :collect ,value into ,current-band
           :finally (progn
                      (when ,current-band
                        (destructuring-bind ,(apply #'append vars) ,current-band
                          ,@body))
                      (unless ,next-p
                        (return-from ,outer-loop))))))))

When compiling the macro, the macro is supposed to inject symbols into the code, but here we have a compilation error that says undefined variables:

;; undefined variables: CURRENT-BAND KEY NEXT-ENTRY NEXT-P OUTER-LOOP VALUE

So now, those variables should be fresh symbols:

(defmacro for-each-hashtable-band (vars hash-table &body body)
  (let ((band-size (length vars)))
    (let ((current-band (gensym))
          (key (gensym))
          (next-entry (gensym))
          (next-p (gensym))
          (outer-loop (gensym))
          (value (gensym)))
      `(with-hash-table-iterator (,next-entry ,hash-table)
         (loop :named ,outer-loop :do
           (loop
             :with ,key and ,value and ,next-p
             :repeat ,band-size
             :do (multiple-value-setq (,next-p ,key ,value) (,next-entry))
             :while ,next-p
             :collect ,key into ,current-band
             :collect ,value into ,current-band
             :finally (progn
                        (when ,current-band
                          (destructuring-bind ,(apply #'append vars) ,current-band
                            ,@body))
                        (unless ,next-p
                          (return-from ,outer-loop)))))))))

This above is a bit verbose, but you could simplify that. Here is what the previous for-each-hashtable-band example expands into with this new macro:

(with-hash-table-iterator (#:g1576 test)
  (loop :named #:g1578
        :do (loop :with #:g1575
                  and #:g1579
                  and #:g1577
                  :repeat 2
                  :do (multiple-value-setq (#:g1577 #:g1575 #:g1579) (#:g1576))
                  :while #:g1577
                  :collect #:g1575 into #:g1574
                  :collect #:g1579 into #:g1574
                  :finally (progn
                            (when #:g1574
                              (destructuring-bind
                                  (k1 v1 k2 v2)
                                  #:g1574
                                (format t "~a -> ~a && ~a -> ~a ~%" k1 v1 k2
                                        v2)))
                            (unless #:g1577 (return-from #:g1578))))))

Each time you expand it, the #:gXXXX variables are different, and cannot possibly shadow existing bindings, so for example, the body can use variables named like current-band or value without breaking the expanded code.