Question: check duplicated terms/alts/nonterms/meta-vars, compares symbolically?

[lijinpei]

Currently, there are several issues concerning checking duplicated terminals, alternatives and non-terminals. To check duplicates, we need a procedure to check whether two things compare equal. But with only a equal? procedure, we can only use O(n^2) algorithms to de-duplicate (n being the number of terms/alts/nonterms/meta-vars). If we could have another procedure to hash terms/alts/nonterms, we can de-duplicate in O(n) on average with hash-tables. But the current specification of nanopass prevents us from doing this, because two term's type/name/predicate should be compared by free-identifier=?.
Perhaps we can strengthen the requirements to require two term's type/name to be symbolically equal as well as free-identifier=?, or we can allow the user to specify a symbolic name(compared by eq?) and a predicate (compared by free-identifier=?), only when the two things are both equal can two terminals be considered equal.
I think when terms become hashable, alts also become hashable.
Is this approach acceptable?

[akeep]

Actually, I think most of these cases have already been fixed.

There are basically two types of duplication:

1. The same meta-variable used for more than one terminal or nonterminal.
2. The same variable name used for more than one field in a production.

Your pull request #22 fixed the missing loop in the check-meta! (thanks!) that ensures the metavariables are unique, and I believe the names used in productions have been checked for uniqueness correctly for a while.

In both cases you are correct that these are O(n^2) operations, though generally, these will be very short lists, and the overhead of the hash table is likely to overwhelm the benefit of its use.

That said, I've been thinking about using a prefix-trie implementation for the metavariables, where the prefix-trie would be stored as part of the language definition to use for lookup. The benefit to this is that we could allow for a wider variety of acceptable metavariable names and allow for some flexibility on the suffixes allowed, with the added benefit that lookup would be O(log(n)), instead of the current O(n), and we would effectively get uniqueness checking as part of the construction process for O(n log n). (As you note, not as cheap as a hash table, but I think the other benefits make it worth the cost in this case, though you may disagree.)

The other source of non-uniqueness in the language definitions currently is the productions themselves. There is actually a more serious bug hiding here than just duplication. Things with similar "shape" will also alias each other. For instance in the definition:

(define (operator? x) (memq x '(+ - *)))
(define-language L
  (terminals
    (symbol (x))
    (fixnum (n))
    (operator (op)))
  (Program (prog)
    (begin e* ... e))
  (Expr (e)
    (set! x0 x1)
    (set! x0 n1)
    (set! x0 (op x1 x2))
    (set! x0 (op x1 n2))))

All of the set! forms have the same "shape" being a list of three elements that starts with the set! keyword. This is not checked, and nanopass framework will treat these as though they are all unique cases, but will generate code where both the parser and meta-parser will only ever match which ever of these comes first.

I think in these cases, it should, as you say, be using the types to help distinguish these. I've thought about trying to approach this using tree automata or something similar, but I've not spent the time to figure out exactly how to apply this, and I believe it will require rewriting the parser and meta-parser, but should put the code in a little bit better algorithmic class as well.

These are definitely on my todo list!

[liampwll]

I have been thinking about combining this with something like Racket's PEG package and allowing passes to be defined on rules within that, which would avoid the shape related problem, but I'm not entirely sure of the feasibility of that idea.