Flexible and Compositional Type Systems. In the GC environment, software fragments are frequently communicated and must be dynamically compiled and/or linked into already running programs. When doing this, it is very desirable to be able to verify via some analysis that the dynamic combinations are safe. It is desirable for the analysis to be compositional, i.e., when combining already analyzed fragments to make a larger system, the analysis for the larger system is obtained by combining the analyses for the fragments, without reanalyzing the fragments. When the analysis is compositional, it can be done in an incremental and modular fashion. Incremental analysis helps support dynamic software reconfiguration, because when just one component is replaced, as long as the analysis results for the other components have not been discarded, the other components do not need to be reanalyzed. Also relevant for the GC environment is the fact that a compositional analysis can also be distributed. To obtain compositional analysis for a type system, it seems to be necessary to have principal typings [Jim96]. Type systems consist of rules for associating terms, which represent fragments of programs, systems, etc., with typings, which represent properties that the terms can satisfy. Generally, a term can be associated with many different typings. It is desirable to find one typing for each term which in some sense represents all of the other typings for the same term (or at least all of the other typings which might ever be needed). A principal typing for some term t in some type system is a typing for t which represents a stronger statement about t than any other typing in the same type system. This means that, if a principal typing exists for some fragment, then reanalyzing the fragment can never yield a more useful result than the principal typing. It is important to avoid confusion with the much weaker principal type (note “type” instead of “typing”) property often mentioned in the context of the Hindley/Xxxxxx (HM) type system (used in languages like Xxxxxxx, Objective Caml, SML, etc.). ∃ W ∀ ∃ ∀ Unfortunately, the desire for compositional analysis conflicts with the way most commonly used type systems (e.g., HM, System F, etc.) support flexible code reuse. To be useful in practice, a type system must be flexible enough to allow significant code reuse, e.g., generic modules. This is supported via type polymorphism which has usually been provided using (“for all”) and (“there exists”) quantifiers in types. ...
