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.
@cite_18: We present the implementation of a type inference algorithm for untyped object-oriented programs with inheritance, assignments, and late binding. The algorithm significantly improves our previous one, presented at OOPSLA'91, since it can handle collection classes, such as List, in a useful way. Abo, the complexity has been dramatically improved, from exponential time to low polynomial time. The implementation uses the techniques of incremental graph construction and constraint template instantiation to avoid representing intermediate results, doing superfluous work, and recomputing type information. Experiments indicate that the implementation type checks as much as 100 lines pr. second. This results in a mature product, on which a number of tools can be based, for example a safety tool, an image compression tool, a code optimization tool, and an annotation tool. This may make type inference for object-oriented languages practical.
@cite_9: One of the aims of combinatory logic is to study the most basic properties of functions and other concepts, with as few restrictions as possible; hence in the simplest form of combinatory logic there is nothing to stop a function being applied to itself; thus XX is an ob for all obs X. However it is also natural to look at the consequences of introducing type-restrictions, formulated by assigning types to the obs according to certain rules, to be described later. Each type is a linguistic expression representing a set of functions, and for any type a the statement " X has type a" is intended to mean that the ob X represents a member of the set represented by a. Given types a and , the set of all functions from the set a into the set 8 is represented by the type " Fa 3" (using Curry's notation). Now consider the ob l; if X has type a, then the ob I X must also have type a. Hence I represents a function from a into a, and so it must be given the type Faa, for each type a. Thus I has not just one type, but a whole class of types. This might seem strange, but it comes from the fact that I represents the abstract notion of " identity-function", rather than one particular identity-function for a particular set. The identity-function involves basically the same concept, no matter what we are applying it to. Similarly the other two basic combinators S and K (see later, or [1, ?5A]) represent certain simple operations which can be performed on almost any functions, and thus they too have an infinite class of types (see ?1 later for details, and ?5 for comment). To denote classes of types, we can use variables a, b, c; then the fact that I has every type of form Faa can be expressed by assigning to I the type-scheme
@cite_1: We present a simple and powerful type inference method for dynamically typed languages where no type information is supplied by the user. Type inference is reduced to the problem of solvability of a system of type inclusion constraints over a type language that includes function types, constructor types, union, intersection, and recursive types, and conditional types. Conditional types enable us to analyze control flow using type inference, thus facilitating computation of accurate types. We demonstrate the power and practicality of the method with examples and performance results from an implementation.
@cite_6: A polymorphic, constraint-based type inference algorithm for an object-oriented language is defined. A generalized form of type, polymorphic recursively constrained types, are inferred. These types are expressive enough for typing objects, since they generalize recursive types and F-bounded polymorphism. The well-known tradeoff between inheritance and subtyping is mitigated by the type inference mechanism. Soundness and completeness of type inference are established.
@cite_5: SETL is a set-theoretically oriented language of very high level whose repertoire of semantic objects includes finite sets, ordered n-tuples, and sets of ordered n-tuples usable as mappings. This paper describes the structure of an optimizer for this language. Among other methods of interest, the optimizer uses techniques which allow relations of inclusion and membership to be established, the domains and ranges of (tabulated) mappings to be estimated from above and below, and the single-valuedness of (tabulated) mappings to be proved. Once facts of this kind have been established, automatic choice of data structures becomes possible. The methods employed are based upon, and extend, known techniques of data flow analysis.
@cite_15: Many type inference and program analysis systems include notions of subtyping and parametric polymorphism. When used together, these two features induce equivalences that allow types to be simplified by eliminating quantified variables. Eliminating variables both improves the readability of types and the performance of algorithms whose complexity depends on the number of type variables. We present an algorithm for simplifying quantified types in the presence of subtyping and prove it is sound and complete for non-recursive and recursive types. We also show that an extension of the algorithm is sound but not complete for a type language with intersection and union types, as well as for a language of constrained types.
@cite_16: Publisher Summary This chapter highlights an automatic technique for selection of data representations in SETL programs. SETL is a very-high-level programming language supporting set-theoretic syntax and semantics. It allows algorithms to be programmed rapidly and succinctly without requiring data-structure declarations to be supplied. The chapter describes a new technique for automatic selection of appropriate data representations during compile time for programs with omitted declarations. It also presents an efficient data representation selection algorithm, whose complexity is comparable with those of the fastest known general data-flow algorithms of Tarjan and Reif. The level of a programming language is determined by the power of its semantic primitives, which influence the ease and speed of programming in the language profoundly. The chapter also describes how the SETL compiler chooses data structure implementations. SETL supports logical quantifiers and the abstract data type set as the prominent high-level features of the language. Programmers are intended to use these features as much as possible and leave more specific data structure and control structure decisions to the SETL compiler. Most other very high-level languages start by incorporating these same features. SETL is a very-high-level programming language supporting set-theoretic syntax and semantics. It allows algorithms to be programmed rapidly and succinctly without requiring data-structure declarations to be supplied. Such declarations can be manually specified later, without recoding the program, to improve the efficiency of program execution. We describe a new technique for automatic selection of appropriate data representations during compile time for programs with omitted declarations and present an efficient data representation selection algorithm, whose complexity is comparable with those of the fastest known general data-flow algorithms of Tarjan and Reif.
@cite_12: 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,
It was found independently by Hindley @cite_9 and Milner @cite_12 that polymorphic types were useful for structuring programs. Since the early contributions of Hindley and Milner many alternatives and extensions to their approach have been suggested in the literature @cite_5 @cite_16 @cite_18 @cite_1 @cite_6 @cite_15 .