Isomorphisms of Types: From Lambda-calculus to Information Retrieval and Language DesignThis 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. |
Contents
II | 12 |
III | 13 |
IV | 14 |
V | 15 |
VI | 19 |
VII | 20 |
VIII | 21 |
IX | 23 |
LI | 119 |
LII | 120 |
LIV | 121 |
LV | 123 |
LVI | 124 |
LVIII | 125 |
LIX | 130 |
LX | 137 |
XI | 24 |
XIII | 25 |
XIV | 27 |
XVI | 28 |
XVII | 30 |
XVIII | 34 |
XIX | 35 |
XX | 36 |
XXI | 37 |
XXII | 38 |
XXIII | 41 |
XXIV | 43 |
XXV | 45 |
XXVI | 46 |
XXVIII | 49 |
XXIX | 50 |
XXX | 57 |
XXXI | 58 |
XXXII | 61 |
XXXIII | 62 |
XXXIV | 67 |
XXXVI | 71 |
XXXVII | 72 |
XXXVIII | 74 |
XXXIX | 79 |
XL | 81 |
XLII | 85 |
XLIII | 86 |
XLIV | 89 |
XLV | 96 |
XLVI | 101 |
XLVII | 103 |
XLVIII | 105 |
XLIX | 112 |
L | 116 |
Other editions - View all
Isomorphisms of Types: from ?-calculus to information retrieval and language ... Roberto DiCosmo No preview available - 2011 |
Common terms and phrases
¹ẞn abstraction allows apply axioms bijection CAML Caml Light canonical bijection cartesian closed categories category theory characterization completeness Computer Science confluence contain coordinates critical pairs Curry-Howard isomorphism defined Definition equality equational theory explicitly typed finite free variables functional programming gentop normal form hence induction hypothesis invertible terms Iso(T isomorphic types isomorphisms of types lambda calculus Lemma logic M₁ ML types modulo monomorphic n-tuple Newman's Lemma nf(A nf(B occurrence P₁ permutation problem programming languages proof Proposition prove reducibility candidate regular types rep(U result rewriting system rules second-order sequence split normal forms SPtop strongly normalizing substitution subterm surjective surjective pairing Swap syntactic terminal object terms of type Theorem theory of isomorphisms ThML type expressions type isomorphisms type system type variables type-assignment type-check typed A-calculus typed lambda calculus U₁ U₂ unification uniform isomorphism unit type variable renaming VX.A X¹ẞn