Extending Attribute Grammar and Type Inference Algorithms

Gated attribute grammars and error-tolerant unification expand upon the usual views of attribute grammars and unification. Normally, attribute grammars are constrained to be noncircular; gated attribute grammars allow fairly general circularities. Most unification algorithms do not behave well when given inconsistent input; the new unification paradigm proposed here not only tolerates inconsistencies but extracts information from them. The expanded views prove to be useful in interactive language-based programming environments. Generalized unification allows the environment to help the user find the sources of type errors in a program, while gated attribute grammars allow the environment to provide an interpreter for incremental reevaluation of programs after small changes to the code. The defining feature of gated attribute grammars is the appearance of a gate attribute (indicating where cycle evaluation should begin and end) within every cycle. Attributes are ordered by collapsing strongly connected components in the dependency graph and topologically sorting the result. The smaller dependency graph for each component (ignoring edges leading to the gate) can be recursively collapsed to provide further ordering. use of the evaluation order defined in this manner allows gated attribute grammars to do without the restrictions on functions within a component needed by the other varieties of circular attribute grammars. Initial and incremental evaluation algorithms are given, as well as a sample grammar allowing an editor for a small language to become an incremental interpreter. Counting unification defines unique solutions to sets of input equations that contain conflicting type information. These solutions are derived from the potential variable constraints implied by the input equations. For each type variable, each branch (a portion of a constraint) is assigned a weight indicating the number of times the input set implied such a constraint. When the input equations are derived from the static analysis of a program, the relative branch weights for a conflicting variable give the overall pattern of uses of that variable and can direct attention to parts of the program that disagree with the majority of uses. A number of error-tolerant unification algorithms are presented