We introduce a new compile-time notion of type subsumption based on type simulation. We show how to apply this static subsumption relation to support a more intuitive, object oriented approach to generic programming of reusable, high performance container types. As a first step towards an efficient implementation of the resulting type system in a compiler we present a novel algorithm for bidirectional type inference over arbitrary syntax graphs. The algorithm uses the new static type subsumption relation to compress the data that has to be stored for each node in the typeflow graph. During typeflow analysis this means that the set of types for a given node can be symbolically represented using antichains instead of using bitvectors or some other explicit set representation. This results in a typing algorithm that is both flexible and precise and shows good performance on representative instances.
More recently other uses of types are being explored that enrich type systems in various ways with constraints and qualifiers that can express certain invariants and in this way further the role of types in writing safe and correct programs @cite_4 @cite_0 .
@cite_0 @cite_4
2096368963 1856452982 2166822586 2038461625
Programmers reason about their programs using a wide variety of formal and informal methods. Programmers in untyped languages such as Scheme or Erlang are able to use any such method to reason about the type behavior of their programs. Our type system for Scheme accommodates common reasoning methods by assigning variable occurrences a subtype of their declared type based on the predicates prior to the occurrence, a discipline dubbed occurrence typing. It thus enables programmers to enrich existing Scheme code with types, while requiring few changes to the code itself. Three years of practical experience has revealed serious shortcomings of our type system. In particular, it relied on a system of ad-hoc rules to relate combinations of predicates, it could not reason about subcomponents of data structures, and it could not follow sophisticated reasoning about the relationship among predicate tests, all of which are used in existing code. In this paper, we reformulate occurrence typing to eliminate these shortcomings. The new formulation derives propositional logic formulas that hold when an expression evaluates to true or false, respectively. A simple proof system is then used to determine types of variable occurrences from these propositions. Our implementation of this revised occurrence type system thus copes with many more untyped programming idioms than the original system. In the past, the creators of numerical programs had to choose between simple expression of mathematical formulas and static type checking. While the Lisp family and its dynamically typed relatives support the straightforward expression via a rich numeric tower, existing statically typed languages force programmers to pollute textbook formulas with explicit coercions or unwieldy notation. In this paper, we demonstrate how the type system of Typed Racket accommodates both a textbook programming style and expressive static checking. The type system provides a hierarchy of numeric types that can be freely mixed as well as precise specifications of sign, representation, and range information--all while supporting generic operations. In addition, the type system provides information to the compiler so that it can perform standard numeric optimizations. The aim of this work is largely a practical one. A widely employed style of programming, particularly in structure-processing languages which impose no discipline of types, entails defining procedures which work well on objects of a wide variety. We present a formal type discipline for such polymorphic procedures in the context of a simple programming language, and a compile time type-checking algorithm w which enforces the discipline. A Semantic Soundness Theorem (based on a formal semantics for the language) states that well-type programs cannot “go wrong” and a Syntactic Soundness Theorem states that if fl accepts a program then it is well typed. We also discuss extending these results to richer languages; a type-checking algorithm based on w is in fact already implemented and working, for the met alanguage ML in the Edinburgh LCF system, Dynamic languages, such as JavaScript, give programmers the freedom to ignore types, and enable them to write concise code in short time. Despite this freedom, many programs follow implicit type rules, for example, that a function has a particular signature or that a property has a particular type. Violations of such implicit type rules often correlate with problems in the program. This paper presents Type Devil, a mostly dynamic analysis that warns developers about inconsistent types. The key idea is to assign a set of observed types to each variable, property, and function, to merge types based in their structure, and to warn developers about variables, properties, and functions that have inconsistent types. To deal with the pervasiveness of polymorphic behavior in real-world JavaScript programs, we present a set of techniques to remove spurious warnings and to merge related warnings. Applying Type Devil to widely used benchmark suites and real-world web applications reveals 15 problematic type inconsistencies, including correctness problems, performance problems, and dangerous coding practices.