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
_________________________________________________
For list-related administrative tasks:
http://lists.racket-lang.org/listinfo/users
