main-content

## Über dieses Buch

This is a book about isomorphisms 0/ types, arecent difficult research topic in type theory that turned out to be able to have valuable practical applications both for programming language design and far more human­ centered information retrieval in software libraries. By means of a deep study of the syntax of the now widely known typed A-ca1culus, it is possible to identify some simple equations between types that on one hand allow to improve the design of the ML language, and on the other hand provide the basis for building radically new information retrieval systems for functional software libraries. We present in this book both the theoretical aspects of these researches and a fully functional implementation of some of their applications in such a way to provide interesting material both for the theoretician looking for proofs and for the practitioner interested in implementation details. In order to make it possible for these different types of readers to use this book effectively, some special signs are used to designate material that is particularly technical or applied or that represents a digression. When the symbol appears at the beginning of a section or a subsection, it warns that the material contained in such section is particularly technical with respect to the general level of the chapter or section where it is located. This material is generally reserved to theoreticians and does not need to be read by the casual reader.

## Inhaltsverzeichnis

### Chapter 1. Introduction

Abstract
In modern programming languages the notion of type has become so natural and widespread that it is easy to forget about its origins and its theoretical relevance. A type is simply seen as a useful means of classification of the objects that a program manipulates: types help to understand better what a program does, and they also provide a valuable firewall against many common programming errors.
Roberto Di Cosmo

### Chapter 2. Confluence Results

Abstract
In the λ-calculus there are plenty of programs (or λ-terms) where it is pos­sible to apply the reduction rule β, introduced in 1.3.4, in more than one position. The λ-calculus does not specify a unique evaluation order, or reduction strategy, that associates to each program or term a unique position where the reduction will proceed.
Roberto Di Cosmo

### Chaper 3. Strong normalization for subsystems of λ2 βηπ✻

Abstract
Our proof of confluence in Theorem 2.4.5 relies upon the strong normalization of $$\beta \underrightarrow {{\eta ^2}\pi * }$$ over the set of gentop normal forms, while we need the strong normalization of $$\beta \underrightarrow {^2{\eta ^2}\pi * }$$ less η top and SP top over the full set of terms in order to provide an effective weakly normalizing strategy for $$\beta \underrightarrow {^2{\eta ^2}\pi * }$$ in Theorem 2.5.2.
Roberto Di Cosmo

### Chapter 4. First-Order Isomorphic Types

Abstract
In this chapter we characterize the isomorphisms which hold in all models of λ1 βηπ✻ the simply typed lambda calculus with subjective pairing (and “terminal object”). Moreover, we show that it is decidable whether two types (built from type variables) are isomorphic in all models of this calculus. It is well known that these models are exactly the Cartesian Closed Categories (ccc).
Roberto Di Cosmo

### Chapter 5. Second-Order Isomorphic Types

Abstract
This chapter is dedicated to the proof of completeness of Th2 xT for iso­morphisms in λ2 βηπ✻. This proof is by far the most complex present in this book, because in the second-order case we have to face the problem of invertibility of terms almost anew, and we can no longer avoid it as we did for the first-order systems.
Roberto Di Cosmo

### Chapter 6. Isomorphisms for ML

Abstract
This chapter is a first attempt to a formal foundation for the theory of isomorphisms of types in the framework of type-assignment calculi similar to Milner’s ML [Mil78, MT91, CH88, MTH90]. The usual notion of isomorphism is not adequate for type assignment, because there a term M is no longer assigned a unique type, so that writing M : AB is not only ambiguous but also incorrect.
Roberto Di Cosmo

### Chapter 7. Related works, Future perspectives

Abstract
In this book we have shown at length how isomorphisms of types can be used either in collaboration with a human user to perform library searches based on types or to improve existing type-checkers. While the only other work that tries to incorporate type isomorphisms at the type-checker level is [Nip90], the library searches issue is probably the most active research topic today. This is clearly related with the rapidly growing size of pro­grams, systems and libraries used in the daily activity by programmers and also by simple users.
Roberto Di Cosmo

### Backmatter

Weitere Informationen