Recursive Macros generating Definitions

[Frank Terbeck <ft@bewatermyfriend.org>]

Good day, good people!

There might  be a bug  in recursive macro  expansion, at least  when the
definition of parameters, using (define …) and similar is involved. Here
is a slightly simplified example.

The purpose  of this macro  is to define a  couple of short-hands  for a
generic encoder/decoder pair  of functions. The intention is  to call it
like this:

  (generate-shorthands (unsigned-integer twos-complement zig-zag)
                       (32 64 128 256 512))

…to generate 5*3*2 = 30 functions,  that call the generic functions with
the proper concrete  arguments. The macro is  implemented recursively to
generate all desired combinations.

If called like that, this implementation generates names like:

  varint:sint32-decode-ea351ae5fca3566

This seems to be connected to the recursiveness of the macro. If calling
the base case manually (see example at the end to reproduce), the inten-
ded name is generated:

  varint:sint32-decode

This happens  with guile 3.0.5,  3.0.8 as well  as the current  git main
branch HEAD. It does not seem to happen in 2.0.0.

I've bisected this down to:

    commit de41e56492666801078e73860a358e1c63cbc8c2
    Author: Andy Wingo <wingo@pobox.com>
    Date:   Fri Nov 4 19:34:22 2011 +0100

    hygienically rename macro-introduced bindings, reproducibly

    * module/ice-9/psyntax.scm (chi-top-sequence): Detect bindings to
    identifiers introduced by macros.  In that case, in order to preserve
    hygiene, uniquify the variable's name, but in a way that is
    reproduceable (i.e., yields the same uniquified name after a
    recompile).

    module/ice-9/psyntax.scm | 22 ++++++++++++++++++++--
    1 file changed, 20 insertions(+), 2 deletions(-)


When looking at  this, I also saw the following,  which might be related
if ‘syntax-rules’ is implemented using  ‘syntax-case’ (I didn't check if
this is the case):

    (define-syntax-rule (foobar n) (define quux n))
    ,exp (foobar 23)
  → (define quux-ea7bdcf8675f4a4 23)

Here's the code, that  can be loaded into a REPL  and example REPL macro
expansion calls to reproduce the issue:


(use-modules (ice-9 match))

(define-syntax generate-shorthands
  (lambda (x)
    ;; This is a helper that makes a name depending on semantics and width. It is
    ;; completely inconsequential to the issue and can be ignored.
    (define (make-base-name s w)
      (symbol-append 'varint:
                     (match (syntax->datum s)
                       ('unsigned-integer 'uint)
                       ('twos-complement  'int)
                       ('zig-zag          'sint))
                     (string->symbol (number->string (syntax->datum w)))))

    ;; The first two cases of this syntax-case recur on generate-shorthands, to
    ;; iterate on the list input to generate all desired combinations.
    (syntax-case x ()
      ;; (_ LIST-OF-SEMANTICS-SYMBOLS LIST-OF-WIDTH-LITERALS)
      ((_ (sems ...) (widths ...))
       (format #t "# Outer~%")  ;; (format #t …) returns #t, so it can be
                                ;; called in guard position to get a trace.
       #'(begin (generate-shorthands sems (widths ...)) ...))

      ;; (_ SEMANTICS-SYMBOL LIST-OF-WIDTH-LITERALS)
      ((_ sem (widths ...))
       (and (format #t "# Middle~%")
            (identifier? #'sem))
       #'(begin (generate-shorthands sem widths) ...))

      ;; Base case:
      ;; (_ SEMANTICS-SYMBOL WIDTH-LITERAL)
      ((_ s w)
       (and (format #t "# Inner~%")
            (identifier? #'s)
            (integer? (syntax->datum #'w)))
       (let ((base (make-base-name #'s #'w)))
         (with-syntax ((enc (datum->syntax x (symbol-append base '-encode)))
                       (dec (datum->syntax x (symbol-append base '-decode))))
           #'(begin (define (dec bv) (varint-decode bv w s))
                    (define (enc  n) (varint-encode  n w s)))))))))


;; Example expansions:

;; ,exp (generate-shorthands (zig-zag) (32))
;; # Outer
;; # Middle
;; # Inner
;; (begin (define (varint:sint32-decode-ea351ae5fca3566 bv) (varint-decode bv 32 zig-zag))
;;        (define (varint:sint32-encode-e47ba11af8c0627  n) (varint-encode  n 32 zig-zag)))

;; ,exp (generate-shorthands zig-zag (32))
;; # Middle
;; # Inner
;; (begin (define (varint:sint32-decode-ea351ae5fca3566 bv) (varint-decode bv 32 zig-zag))
;;        (define (varint:sint32-encode-e47ba11af8c0627  n) (varint-encode  n 32 zig-zag)))


;; ,exp (generate-shorthands zig-zag 32)
;; # Inner
;; (begin (define (varint:sint32-decode bv) (varint-decode bv 32 zig-zag))
;;        (define (varint:sint32-encode  n) (varint-encode  n 32 zig-zag)))