Search

In this paper, we identify a subset of types in the rank 2 intersection type system, where types do not contain positive occurrences of intersections. We extend the notion of pre-grammar of a type and address the type-inhabitation problem for types in this subset, as well as their intersections. [ABSTRACT FROM AUTHOR]

We characterize β -strongly normalizing λ -terms by means of a non-idempotent intersection type system. More precisely, we first define a memory calculus K together with a non-idempotent intersection type system K , and we show that a K-term t is typable in K if and only if t is K-strongly normalizing. We then show that β -strong normalization is equivalent to K-strong normalization. We conclude since λ -terms are strictly included in K-terms. [ABSTRACT FROM AUTHOR]

Abstract: We present a system of refinement types for LF in the style of recent formulations where only canonical forms are well-typed. Both the usual LF rules and the rules for type refinements are bidirectional, leading to a straightforward proof of decidability of type-checking even in the presence of intersection types. Because we insist on canonical forms, structural rules for subtyping can now be derived rather than being assumed as primitive. We illustrate the expressive power of our system with several examples in the domain of logics and programming languages. [Copyright &y& Elsevier]

Abstract: A model characterising strong normalisation for Klop''s extension of λ-calculus is presented. The main technical tools for this result are an inductive definition of strongly normalising terms of Klop''s calculus and an intersection type system for terms of Klop''s calculus. [Copyright &y& Elsevier]

Abstract: This paper presents a notion of intersection and union type assignment for the calculus , a substitution free language that can be used to describe the behaviour of functional programming languages at a very low level of granularity, and has first been defined in [Stéphane Lengrand. Call-by-value, call-by-name, and strong normalization for the classical sequent calculus. In Bernhard Gramlich and Salvador Lucas, editors, Electronic Notes in Theoretical Computer Science, volume 86. Elsevier, 2003, S. van Bakel, S. Lengrand, and P. Lescanne. The language §: computation and sequent calculus in classical logic. Submitted, 2004]. has been designed to give a Curry-Howard-de Bruijn correspondence to the sequent calculus for classical logic. In this paper we will define a notion of sequent-style intersection type assignment on that needs union types, and show that this notion is closed for both subject-reduction and subject-expansion. We will also show that it is an extension of the Strict system for lc. [Copyright &y& Elsevier]

Abstract: The operation of expansion on typings was introduced at the end of the 1970s by Coppo, Dezani, and Venneri for reasoning about the possible typings of a term when using intersection types. Until recently, it has remained somewhat mysterious and unfamiliar, even though it is essential for carrying out compositional type inference. The fundamental idea of expansion is to be able to calculate the effect on the final judgement of a typing derivation of inserting a use of the intersection-introduction typing rule at some (possibly deeply nested) position, without actually needing to build the new derivation. Recently, we have improved on this by introducing expansion variables (E-variables), which make the calculation straightforward and understandable. E-variables make it easy to postpone choices of which typing rules to use until later constraint solving gives enough information to allow making a good choice. Expansion can also be done for type constructors other than intersection, such as the ! of Linear Logic, and E-variables make this easy. There are no significant new technical results in this paper; instead this paper surveys and explains the technical results of a quarter of a century of work on expansion. [Copyright &y& Elsevier]

Abstract: Light Affine Lambda Calculus is a term calculus for polynomial time computation ([K. Terui. Light affine lambda calculus and polytime strong normalization. In Proceedings of LICS''01, pages 209–220, 2001]). Some of the terms of Light Affine Lambda Calculus must however be regarded as errors. Intuitionistic Light Affine Logic (ILAL) types only terms without errors, but not all of them. We introduce two type assignment systems with intersection types : in the first one, typable pseudo-terms are exactly the terms without errors ; in the second one, they are exactly those that reduce to normal terms without errors. [Copyright &y& Elsevier]

Abstract: The original of Curien and Herbelin has a system of simple types, based on sequent calculus, embodying a Curry-Howard correspondence with classical logic. We introduce and discuss three type assignment systems that are extensions of with intersection and union types. The intrinsic symmetry in the calculus leads to an essential use of both intersection and union types. [Copyright &y& Elsevier]

Abstract: We introduce channel sequence types to study finitary polymorphism in the context of mobile processes modelled in the π-calculus. We associate to each channel a set of exchange types, and we require that output processes send values of one of those types, and input processes accept values of any type in the set. Our type assignment system enjoys subject reduction and guarantees the absence of communication errors. We give several examples of polymorphism, and we encode the λ-calculus with the strict intersection type discipline. [Copyright &y& Elsevier]

Abstract: Inferring types for polymorphic recursive function definitions (abbreviated to polymorphic recursion) is a recurring topic on the mailing lists of popular typed programming languages. This is despite the fact that type inference for polymorphic recursion using ∀-types has been proved undecidable. This report presents several programming examples involving polymorphic recursion and determines their typability under various type systems, including the Hindley-Milner system, an intersection-type system, and extensions of these two. The goal of this report is to show that many of these examples are typable using a system of intersection types as an alternative form of polymorphism. By accomplishing this, we hope to lay the foundation for future research into a decidable intersection-type inference algorithm. We do not provide a comprehensive survey of type systems appropriate for polymorphic recursion, with or without type annotations inserted in the source language. Rather, we focus on examples for which types may be inferred without type annotations, with an emphasis on systems of intersection- types. [Copyright &y& Elsevier]

Abstract: We show how to use intersection types for building models of a λ-calculus enriched with recursive terms, whose intended meaning is of minimal fixed points. As a by-product we prove an interesting consistency result. [Copyright &y& Elsevier]

A general reducibility method is developed for proving reduction properties of lambda terms typeable in intersection type systems with and without the universal type Ω. Sufficient conditions for its application are derived. This method leads to uniform proofs of confluence, standardization, weak head normalization of terms typeable in the system with the universal type Ω. The method extends Tait''s reducibility method for the proof of strong normalization of the simply typed lambda calculus, Krivine''s extension of the same method for the strong normalization of intersection type system without Ω, and Statman-Mitchell''s logical relation method for the proof of confluence of β-η-reduction on the simply typed lambda terms. As a consequence, the confluence and the standardization of all (untyped) lambda terms is obtained. [Copyright &y& Elsevier]

This paper defines reduction on derivations in the strict intersection type assignment system of [2] by generalising cut-elimination, and shows a strong normalisation result for this reduction. Using this result, new proofs are given for the approximation theorem and the characterisation of normalisability using intersection types. [Copyright &y& Elsevier]