Affiliated with FSCD 2024, 10-13 July 2024, Tallinn
ITRS past events: http://itrs.di.unito.it/workshops.html
Intersection types were introduced near the end of the 1970s to overcome the limitations of Curry's type assignment system and to provide a characterization of the strongly normalizing terms of the Lambda Calculus. The key idea is to introduce an intersection type constructor ∧ such that a term of type t ∧ s can be used at both type t and s within the same context. This provides a finite polymorphism where various, even unrelated, types of the term are listed explicitly, differently from the more widely used universally quantified types where the polymorphic type is the common schema that stands for its various type instances. As a consequence, more terms (all and only the normalizing terms) can be typed than with universal polymorphism.
Although intersection types were initially intended for use in analyzing and/or synthesizing lambda models as well as in analyzing normalization properties, over the last twenty years the scope of the research on intersection types and related systems has broadened in many directions. Restricted (and more manageable) forms have been investigated, such as refinement types. Type systems based on intersection type theory have been extensively studied for practical purposes, such as program analysis and higher-order model checking. The dual notion of union types turned out to be quite useful for programming languages. Finally, the behavioural approach to types, which can give a static specification of computational properties, has become central in the most recent research on type theory.
The ITRS 2024 workshop aims to bring together researchers working on both the theory and practical applications of systems based on intersection types and related approaches. Possible topics for submitted papers include, but are not limited to:
ITRS workshops have been held every two years (with the exception of 2020, because of COVID-19 outbreak). Information about the previous events is available on the ITRS home page.
Submission should be between 3 and 5 pages, excluding bibliography. We welcome original results or surveys about ongoing research, short versions of recently published articles, papers submitted elsewhere, and surveys of ongoing work. Communications should be written in English, using LaTeX, and will appear on the workshop website.
The submission Web page for ITRS24 is on Easychair: https://easychair.org/conferences/?conf=itrs24
Andrej Dudenhefner: From Normalization to Typability via Subject Expansion.
In the early 1980s Coppo and Dezani-Ciancaglini presented an intersection type assignment system (CD) as an extension
of the simple type system. In their seminal work, CD is shown to assign types to strongly normalizing terms
in the λ-I-calculus. Afterwards, Pottinger has shown that any strongly normalizing term is typable in CD.
As keenly remarked by Barendregt, Dekkers, and Statman, there are many proofs of this fact in literature,
most of which (including Pottinger’s) are incorrect.
The present work gives an alternative approach to show that strongly normalizing terms are typable in CD.
The key idea is to use a recently developed notion of IK′-reduction, which allows for subject expansion properties.
Any strongly normalizing term M reduces to a typable normal form via the IK′-reduction. Therefore,
subject expansion properties imply typability of M. In order to eliminate any doubt, the proof is mechanized
in constructive logic using the Coq proof assistant.
Giulio Manzonetto: Coloring Intersection Types. We review the key findings on intersection type systems by comparing two main approaches: the qualitative analysis of termination properties and the quantitative evaluation of resource consumption. We will expose the relationship between the underlying systems of approximants, based on Böhm trees and Taylor expansions, and observational equivalences. We will then introduce the "yinyang calculus", an annotated lambda-calculus that allows to track the interaction between a lambda-term and its environment. By appropriately coloring an intersection type system, we prove that the usual Böhm tree equality can be characterized in terms of a quantitative equivalence where we observe the termination in a certain number of interaction steps.
Viviana Bono: Types for (Slow) AI. Reasoning on knowledge bases is often done by machine learning models fed with W3C Resource Description Framework data rather than by applying formal inference techniques. On the one hand, this use of machine learning certainly provides a faster mechanism than any formal (run time) inference technique, but, on the other hand, it may lead to an impoverishment of the expressivity of the properties proven. Statically typed languages can help to attenuate the performance issue: they offer the possibility of checking or inferring certain properties of interest statically, meaning that they do not slow down run time. In this talk, we will survey some already-present applications of types to knowledge representation and give a hint about open problems.
Ugo de'Liguoro, Università di Torino, Italy
Riccardo Treglia, King’s College London, UK