Let's start Scheme

2015-10-09

bound or free identifier

I've just fixed the bug of incorrect usage of free-identifier=? during macro expansion. As my memo and maybe good to share what I've learnt.

Firstly, have a look at this piece of code:
(import (rnrs))

(define-syntax foo
  (lambda (x)
    (syntax-case x ()
      ((_ (t1 t2))
       ;; what should be print?
       (begin (display (free-identifier=? #'t1 #'t2)) (newline)
              (display (bound-identifier=? #'t1 #'t2)) (newline))
       #''ok)
      ((_ (t* ...) a b ...)
       #'(foo (t* ... t) b ...))
      ((_ a ...)
       #'(foo () a ...)))))
(foo 1 2)
If you can immediately see what's printed, then you can skip the next paragraph :)

The difference between bound-identifier=? and free-identifier=? is that the first one only sees where the given 2 identifiers were  created and the second one sees the actual bindings are the same or not. In the above example, identifier ts are created in different places, more precisely different macro expansion process. If you expand the macro manually, then it would look like this:
(foo 1 2)
;; -> (foo () 1 2))
;; -> (foo (t) 2)) ;; <- where the first t is created 
;; -> (foo (t t))  ;; <- the second one is created here in the different macro expansion
;; 'ok
If 2 identifiers whose names are same are created in different macro expansion, then comparing bound-identifier=? should return #f.free-identifier=?, on the other hand, should return #t because those identifiers are not bound to anything thus they have the same binding (unbound variable) and also have the same name (t). (This is what I understood the behaviour of those 2 procedures. Correct me, if I'm wrong.)

Now the bug was related to this difference. The detail is here. In the description, it says free-identifier=? returns #t against pattern variables t but this is correct behaviour. What I did wrong was using free-identifier=? to compare pattern variables during expanding template variables. Moreover, compiler for syntax-case renamed pattern variables which must be preserved so that expander can use bound-identifier=? to compare pattern variables.

If I know what's wrong, then fixing it is not a big problem. Just adding extra check for pattern variable and use bound-identifier=?. Done! I hope this would be the last article related to macro bug... (feeling won't though)

No comments:

Post a Comment