Dynamic Typing

We present an extension of a statically typed language with a special type Dynamic and explicit type tagging and checking operations (coercions). Programs in run-time typed languages are viewed as incomplete programs that are to be completed to well-typed programs by explicitly inserting coercions into them. Such completions are generally not unique. If the meaning of an incomplete program is to be the meaning of any of its completions and if it is too be unambiguous it is necessary that all its completions are coherent (semantically equivalent). We characterize with an equational theory the properties a semantics must satisfy to be coherent. Since \naive " coercion evaluation does not satisfy all of the coherence equations we ex-clude certain \unsafe " completions from consideration that can cause avoidable type errors at run-time. Various classes of completions may be used, parameterized by whether or not coercions may only occur at data creation and data use points in a program and whether only primitive coercions or also induced coercions. For each of these classes any term has a minimal com-pletion that is optimal in the sense that it contains no coercions that could be avoided by a another coercion in the same class. In particular, minimal completions contain no coercions at all whenever the program is statically typable. If only primitive type operations are admitted we show that minimal completions can be computed in almost-linear time. If induced coercions are also allowed the minimal completion can be computed in time O(nm) where n is the size of the program and m is the size of the value ow graph of the program, which may be of size O(n2), but is typically rather sparse. Finally, we sketch how this explicit dynamic typing discipline can be extended to let-polymorphism by parameterization with respect to coercions. The resulting language framework leads to a seamless integration of statically typed and dynamically typed languages by relying on type inference for programs that have no type information and no explicit coercions whatsoever.