[racket] How to do binding analysis? Distinguishing identifiers: one that creates a binding, the other being bound to it

On 04/25/2011 07:39 AM, Zack Brannigan wrote:
> Hi, all:
>
> What's the best way to analyze a fully-expanded syntax object so that I
> can work out identifier bindings and their dependencies? I have in mind
> what the syncheck tool does: it shows dependencies (through arrows) of a
> variable from where it is used to where it is bound.
>
> However, looking through collects/drracket/private/syncheck/gui.rkt
> reveals very little how it works out those dependencies. At the very
> least, I want to be able to distinguish when an identifier is doing the
> binding and when an identifier is being used.

The code that implements the analysis part of Check Syntax is in 
collects/drracket/private/syncheck/traversals.rkt.

Whether an identifier is a binding occurrence or a reference is not 
something you can tell just by looking at the identifier itself. You 
have to check whether it's in a binding position.


> I also played around with syntax/id-table and syntax/boundmap, but they
> don't seem to reveal dependencies. (Unless I used them wrong.)

They're useful if you know how to use them. Here is a function that 
analyzes a fully-expanded expression and builds a table mapping 
references to their corresponding binding occurrences.

(require syntax/id-table)

;; compute-use=>def-table : syntax -> free-id-table
;; Result table maps reference to binding occurrence.
(define (compute-use=>def-table stx)
   (let ([binders (make-free-id-table)]
         [use=>def (make-hasheq)])

     ;; analyze : stx -> void
     (define (analyze stx)
       (syntax-case stx (#%expression
                         #%plain-lambda
                         #%plain-app
                         if
                         begin
                         quote)
         [(#%expression expr)
          (analyze #'expr)]
         [(#%plain-lambda formals body-expr ...)
          (begin (for-each (lambda (id)
                             (free-id-table-set! binders id id))
                           (get-formals #'formals))
                 (for-each analyze (syntax->list #'(body-expr ...))))]
         [(#%plain-app op-expr arg-expr ...)
          (for-each analyze
                    (syntax->list #'(op-expr arg-expr ...)))]
         [(if test-expr then-expr else-expr)
          (for-each analyze
                    (syntax->list #'(test-expr then-expr else-expr)))]
         [(begin expr ...)
          (for-each analyze (syntax->list #'(expr ...)))]
         [(quote datum)
          (void)]
         [var
          (identifier? #'var)
          (let ([binding (identifier-binding #'var)])
            (cond [(eq? binding 'lexical)
                   (hash-set! use=>def #'var
                              (free-id-table-ref binders #'var))]
                  [(eq? binding #f)
                   ;; top-level variable
                   (void)]
                  [(list? binding)
                   ;; module variable, imported via 'require'
                   (void)]))]))

     ;; get-formals : syntax -> (listof identifier)
     ;; Gets identifiers bound by lambda formals.
     (define (get-formals formals)
       (syntax-case formals ()
         [(id . formals-rest)
          (cons #'id (get-formals #'formals-rest))]
         [() null]
         [id (identifier? #'id) (list #'id)]))

     (analyze stx)
     use=>def))

;; Example
 > (define s (expand #'(lambda (x) (if x (+ x 1) 0))))
 > (hash-map (compute-use=>def-table s) list)
'((#<syntax::66 x> #<syntax::54 x>) (#<syntax::61 x> #<syntax::54 x>))


In fully-expanded code, a reference is free-identifier=? to its 
corresponding binding occurrence. So by mapping every binding occurrence 
to itself in the 'binders' table, the table automatically maps any 
reference to its binding occurrence also.

But the 'binders' table doesn't let us enumerate all of the references. 
To do that, we have the 'analyze' function build a hash table; by using 
'eq?' to compare keys we ensure that distinct references are not 
collapsed into one entry, as a free-id-table would do. (We also could 
have the 'analyze' function build a list of the references and return 
that along with the 'binders' table.)

Note that the code above only handles fully-expanded *expressions*, and 
only a few of the expression syntactic forms. For the full grammar see

http://docs.racket-lang.org/reference/syntax-model.html#%28part._fully-expanded%29

You don't have to type out the literals list for all of the core 
syntactic forms; see the docs for 'kernel-syntax-case'.

If you recur on the right-hand side of 'define-syntaxes', you need to 
change your comparisons from phase 0 (the default) to phase 1 (which 
means the "transformer environment"). See 'kernel-syntax-case/phase'. 
You'll also need a separate 'binders' table for phase-1 bindings; see 
the optional #:phase argument of 'make-free-id-table'.

Ryan