The Calculus of Context Relations

We present the theory of context relations. Context relations are a method for incremental semantic analysis in language-specific editors, which is able to handle incomplete program fragments. The algorithm is generated from the definition of a language's static semantics and is based on inference rules and order-sorted unification. The paper presents the underlying mathematical theory, optimal incremental analysis algorithms, handling of user-defined polymorphism and overloading, and implementation issues. It is intended as the concluding report on a by now mature concept, which has successfully been used to generate efficient incremental type inferencers for languages like ADA and Fortran 8x.