Progress in Theoretical Computer Science - Böcker

Equations occur in many computer applications, such as symbolic compu­ tation, functional programming, abstract data type specifications, program verification, program synthesis, and automated theorem proving. Rewrite systems are directed equations used to compute by replacing subterms in a given formula by equal terms until a simplest form possible, called a normal form, is obtained. The theory of rewriting is concerned with the compu­ tation of normal forms. We shall study the use of rewrite techniques for reasoning about equations. Reasoning about equations may, for instance, involve deciding whether an equation is a logical consequence of a given set of equational axioms. Convergent rewrite systems are those for which the rewriting process de­ fines unique normal forms. They can be thought of as non-deterministic functional programs and provide reasonably efficient decision procedures for the underlying equational theories. The Knuth-Bendix completion method provides a means of testing for convergence and can often be used to con­ struct convergent rewrite systems from non-convergent ones. We develop a proof-theoretic framework for studying completion and related rewrite­ based proof procedures. We shall view theorem provers as proof transformation procedures, so as to express their essential properties as proof normalization theorems.

This monograph studies the logical aspects of domains as used in de­ notational semantics of programming languages. Frameworks of domain logics are introduced; these serve as foundations for systematic derivations of proof systems from denotational semantics of programming languages. Any proof system so derived is guaranteed to agree with denotational se­ mantics in the sense that the denotation of any program coincides with the set of assertions true of it. The study focuses on two categories for dena­ tational semantics: SFP domains, and the less standard, but important, category of stable domains. The intended readership of this monograph includes researchers and graduate students interested in the relation between semantics of program­ ming languages and formal means of reasoning about programs. A basic knowledge of denotational semantics, mathematical logic, general topology, and category theory is helpful for a full understanding of the material. Part I SFP Domains Chapter 1 Introduction This chapter provides a brief exposition to domain theory, denotational se­ mantics, program logics, and proof systems. It discusses the importance of ideas and results on logic and topology to the understanding of the relation between denotational semantics and program logics. It also describes the motivation for the work presented by this monograph, and how that work fits into a more general program. Finally, it gives a short summary of the results of each chapter. 1. 1 Domain Theory Programming languages are languages with which to perform computa­ tion.

This book is a thoroughly revised edition of a monograph that presents an approach to the design and implementation of sequential programming languages based on the relationship between lambda-calculus and category theory. The foundations of a new "categorical" combinatory logic are laid down. Compilation and evaluation techniques are investigated. A simple abstract machine, called the Categorical Abstract Machine, is presented: it has served as the core of the implementation of the language CAML, of the ML family, developed at INRIA-Roquencourt and Ecole Normale Superieure, and first released in 1987. The main characteristics of this approach are conceptual simplicity and compactness, with bearings on portability, efficiency, and correctness proofs. A mathematical semantics of sequentiality is proposed, in which "sequential algorithms" rather than functions are used to interpret procedures. The theoretical investigation has led to the development of a programming language, CDSO, in which basic and functional types are not differentiated. The evaluation framework is a demand-driven data flow network.The model of sequential algorithms is fully abstract with respect to this language: two procedures have the same denotation if and only if they have the same behaviour. Background on full abstraction is given. The new edition covers new results, and introduces new connections, as suggested by the following non-exhaustive fist of keywords: confluence properties of categorical combinators, explicit substitutions, control operations, linear logic, geometry of interaction, strong stability.

This monograph is a slightly revised version of my PhD thesis [86], com­ pleted in the Department of Computer Science at the University of Edin­ burgh in June 1988, with an additional chapter summarising more recent developments. Some of the material has appeared in the form of papers [50,88]. The underlying theme of the monograph is the study of two classical problems: counting the elements of a finite set of combinatorial structures, and generating them uniformly at random. In their exact form, these prob­ lems appear to be intractable for many important structures, so interest has focused on finding efficient randomised algorithms that solve them ap­ proxim~ly, with a small probability of error. For most natural structures the two problems are intimately connected at this level of approximation, so it is natural to study them together. At the heart of the monograph is a single algorithmic paradigm: sim­ ulate a Markov chain whose states are combinatorial structures and which converges to a known probability distribution over them. This technique has applications not only in combinatorial counting and generation, but also in several other areas such as statistical physics and combinatorial optimi­ sation. The efficiency of the technique in any application depends crucially on the rate of convergence of the Markov chain.

The graph isomorphism problem belongs to the part of Complexity Theory that focuses on the structure of complexity classes involved in the classification of computational problems and in the relations among them. It consists in deciding whether two given graphs are isomorphic, i.e. whether there is a bijective mapping from the nodes of one graph to the nodes of the second graph such that the edge connections are respected. It is a problem of considerable practical as wen as theoretical importance that is, as of now, unresolved in the sense that no efficient algorithm for it has yet been found. Given this fact, it is natural to ask whether such an algorithm exists at an or whether the problem is intractable. -Be book focuses on this issue and presents several recent results that provide a better understanding of the relative position of the graph isomorphism problem in the class NP as well as in other complexity classes. It also uses the problem to illustrate important concepts in structural complexity, providing a look into the more general theory.'The book is basically self-contained; the only prerequisite for reading it is some elementary knowledge from Complexity Theory and Probability Theory. Its level of presentation makes it eminently suitable for a seminar or graduate course devoted to the problem, or as a rich source of examples for a standard graduate course in Complexity Theory.

The aim of this book is to extend the major finite-dimensional state-space results to a large class of distributed parameter systems. These distributed parameter systems contain models for delay systems, as well as partial differential equations, and allow for unbounded inputs and outputs.

This work, intended for researchers and advanced students in theoretical computer science and mathematics, is situated at the juncture of automata theory, logic, semigroup theory and computational complexity. The first part focuses on the algebraic characterization of the regular languages definable in many different logical theories. The second part presents the recently-discovered connections between the algebraic theory of automata and the complexity theory of small-depth circuits. The first seven chapters of this text are devoted to the algebraic characterization of the regular languages definable in many different logical theories, obtained by varying both the kinds of quantification and the atomic formulas that are admitted. This includes the results of Buchi and of McNaughton and Papert, as well as more recent developments that are scattered throughout research journals and conference proceedings. The two tables at the end of Chapter 7 summarize most of the important results of this first part of the book. Chapter 8 provides a brief account of the complexity theory of small-depth families of boolean circuits.Chapter 9 aims to tie all the threads together: it shows that questions about the structure of complexity classes of small-depth circuits are precisely equivalent to questions about the definability of regular languages in various versions of first-order logic.

1.1. What This Book is About This book is a study of * subrecursive programming systems, * efficiency/program-size trade-offs between such systems, and * how these systems can serve as tools in complexity theory. Section 1.1 states our basic themes, and Sections 1.2 and 1.3 give a general outline of the book. Our first task is to explain what subrecursive programming systems are and why they are of interest. 1.1.1. Subrecursive Programming Systems A subrecursive programming system is, roughly, a programming language for which the result of running any given program on any given input can be completely determined algorithmically. Typical examples are: 1. the Meyer-Ritchie LOOP language [MR67,DW83], a restricted assem- bly language with bounded loops as the only allowed deviation from straight-line programming; 2. multi-tape 'lUring Machines each explicitly clocked to halt within a time bound given by some polynomial in the length ofthe input (see [BH79,HB79]); 3. the set of seemingly unrestricted programs for which one can prove 1 termination on all inputs (see [Kre51,Kre58,Ros84]); and 4. finite state and pushdown automata from formal language theory (see [HU79]). lOr, more precisely, the collection of programs, p, ofsome particular general-purpose programming language (e.g., Lisp or Modula-2) for which there is a proof in some par- ticular formal system (e.g., Peano Arithmetic) that p halts on all inputs.

Matrix and polynomial computations are fundamental to the theory and practice of computing. The authors present here a systematic treatment of algorithms and complexity in these two related areas. Its study of computations with Toeplitz matrices and other dense structured matrices demonstrates the links between numerical and algebraic approaches to computation. The authors begin with classical fundamental problems and gradually introduce the reader to current research. In particular, the book provides improved parallel algorithms for computations with structured matrices and their further applications to some fundamental computations with matrices and polynomials. The book is designed as a text for advanced graduates in mathematics and computer science.

The purpose of the programme in combinatory logic is to rework the mathematical foundations of computer science on a theory of pure thought. It begins from the idea that, if logic is to be the science of correctly dealing with thought-objects, the underlying theory must be in some sense a part of, or at least a preliminary to, its structure, ie, a protologic. From this idea a combinatory algebra is constructed, using a programmatic mixture of the classical axiomatic and set-theoretic approaches. This text shows that sufficiently rich combinatory algebras can serve as a platform from which to develop the algorithmic aspects of many areas in computer science, mathematics and their applications. It should be of interest to those studying universal algebra, logic and computer algebra.

In recent years there has been a remarkable convergence of interest in programming languages based on ALGOL 60. Researchers interested in the theory of procedural and object-oriented languages discovered that ALGOL 60 shows how to add procedures and object classes to simple imperative languages in a general and clean way. And, on the other hand, researchers interested in purely functional languages discovered that ALGOL 60 shows how to add imperative mechanisms to functional languages in a way that does not compromise their desirable properties. Unfortunately, many of the key works in this field have been rather hard to obtain. The primary purpose of this collection is to make the most significant material on ALGoL-like languages conveniently available to graduate students and researchers. Contents Introduction to Volume 1 1 Part I Historical Background 1 Part n Basic Principles 3 Part III Language Design 5 Introduction to Volume 2 6 Part IV Functor-Category Semantics 7 Part V Specification Logic 7 Part VI Procedures and Local Variables 8 Part vn Interference, Irreversibility and Concurrency 9 Acknowledgements 11 Bibliography 11 Introduction to Volume 1 This volume contains historical and foundational material, and works on lan­ guage design. All of the material should be accessible to beginning graduate students in programming languages and theoretical Computer Science.

by Luea Cardelli Ever since Strachey's work in the 1960's, polymorphism has been classified into the parametric and overloading varieties. Parametric polymorphism has been the subject of extensive study for over two decades. Overloading, on the other hand, has often been considered too ad hoc to deserve much attention even though it has been, in some form, an ingredient of virtually every programming lan­ guage (much more so than parametric polymorphism). With the introduction of object-oriented languages, and in particular with multiple-dispatch object-oriented languages, overloading has become less of a programming convenience and more of a fundamental feature in need of proper explanation. This book provides a compelling framework for the study of run-time over­ loading and of its interactions with subtyping and with parametric polymorphism. The book also describes applications to object-oriented programming. This new framework is motivated by the relatively recent spread of programming languages that are entirely based on run-time overloading; this fact probably explains why this subject was not investigated earlier. Once properly understood, overloading reveals itself relevant also to the study of older and more conventional (single­ dispatch) object-oriented languages, clarifying delicate issues of covariance and contravariance of method types, and of run-time type analysis. In the final chapters, a synthesis is made between parametric and overloading polymorphism.

During the last three decades several different styles of semantics for program­ ming languages have been developed. This book compares two of them: the operational and the denotational approach. On the basis of several exam­ ples we show how to define operational and denotational semantic models for programming languages. Furthermore, we introduce a general technique for comparing various semantic models for a given language. We focus on different degrees of nondeterminism in programming lan­ guages. Nondeterminism arises naturally in concurrent languages. It is also an important concept in specification languages. In the examples discussed, the degree of non determinism ranges from a choice between two alternatives to a choice between a collection of alternatives indexed by a closed interval of the real numbers. The former arises in a language with nondeterministic choices. A real time language with dense choices gives rise to the latter. We also consider the nondeterministic random assignment and parallel composition, both couched in a simple language. Besides non determinism our four example languages contain some form of recursion, a key ingredient of programming languages.

To construct a compiler for a modern higher-level programming languagel one needs to structure the translation to a machine-like intermediate language in a way that reflects the semantics of the language. little is said about such struc­ turing in compiler texts that are intended to cover a wide variety of program­ ming languages. More is said in the Iiterature on semantics-directed compiler construction [1] but here too the viewpoint is very general (though limited to 1 languages with a finite number of syntactic types). On the other handl there is a considerable body of work using the continuation-passing transformation to structure compilers for the specific case of call-by-value languages such as SCHEME and ML [21 3]. ln this paperl we will describe a method of structuring the translation of ALGOL-like languages that is based on the functor-category semantics devel­ oped by Reynolds [4] and Oles [51 6]. An alternative approach using category theory to structure compilers is the early work of F. L. Morris [7]1 which anticipates our treatment of boolean expressionsl but does not deal with procedures. 2 Types and Syntax An ALGOL-like language is a typed lambda calculus with an unusual repertoire of primitive types. Throughout most of this paper we assume that the primi­ tive types are comm(and) int(eger)exp(ression) int(eger)acc(eptor) int(eger)var(iable) I and that the set 8 of types is the least set containing these primitive types and closed under the binary operation -.

Humanity's most basic intellectual quest to decipher nature and master it has led to numerous efforts to build machines that simulate the world or communi­ cate with it [Bus70, Tur36, MP43, Sha48, vN56, Sha41, Rub89, NK91, Nyc92]. The computational power and dynamic behavior of such machines is a central question for mathematicians, computer scientists, and occasionally, physicists. Our interest is in computers called artificial neural networks. In their most general framework, neural networks consist of assemblies of simple processors, or "neurons," each of which computes a scalar activation function of its input. This activation function is nonlinear, and is typically a monotonic function with bounded range, much like neural responses to input stimuli. The scalar value produced by a neuron affects other neurons, which then calculate a new scalar value of their own. This describes the dynamical behavior of parallel updates. Some of the signals originate from outside the network and act as inputs to the system, while other signals are communicated back to the environment and are thus used to encode the end result of the computation.

This monograph develops techniques for equational reasoning and declarative programming based on higher-order logic. The author presents a framework for the full integration of declarative programming models and shows its application. On the technical side, he integrates the main results of both worlds. The book presents completeness results as common in logic programming and also generalizes evaluation strategies found in current functional programming languages to this setting. The book includes a thorough introduction to higher-order equational logic, higher-order rewriting, and unification. This followed by a stepwise development from general equational reasoning toward effective methods for declarative programming in higher-order logic and lambda-calculus. Another important, complementing, result shows that higher order unification, the basic inference engine in logic programming, is decidable for programming applications. The text is aimed at researchers and advanced students in computer science and mathematics with interests in declarative programming, symbolic computation, term rewriting, equational reasoning, and theorem proving.It can provide a firm basis for a variety of graduate course in logic and theoretical computer science.

The study of spline functions is an outgrowth of basic mathematical concepts arising from calculus, analysis and numerical analysis. Spline modelling affects a number of fields: statistics; computer graphics; CAD programming, and other areas of applied mathematics.

1.1. What This Book is About This book is a study of * subrecursive programming systems, * efficiency/program-size trade-offs between such systems, and * how these systems can serve as tools in complexity theory. Section 1.1 states our basic themes, and Sections 1.2 and 1.3 give a general outline of the book. Our first task is to explain what subrecursive programming systems are and why they are of interest. 1.1.1. Subrecursive Programming Systems A subrecursive programming system is, roughly, a programming language for which the result of running any given program on any given input can be completely determined algorithmically. Typical examples are: 1. the Meyer-Ritchie LOOP language [MR67,DW83], a restricted assem- bly language with bounded loops as the only allowed deviation from straight-line programming; 2. multi-tape 'lUring Machines each explicitly clocked to halt within a time bound given by some polynomial in the length ofthe input (see [BH79,HB79]); 3. the set of seemingly unrestricted programs for which one can prove 1 termination on all inputs (see [Kre51,Kre58,Ros84]); and 4. finite state and pushdown automata from formal language theory (see [HU79]). lOr, more precisely, the collection of programs, p, ofsome particular general-purpose programming language (e.g., Lisp or Modula-2) for which there is a proof in some par- ticular formal system (e.g., Peano Arithmetic) that p halts on all inputs.

Our Subjects and Objectives. This book is about algebraic and symbolic computation and numerical computing (with matrices and polynomials). It greatly extends the study of these topics presented in the celebrated books of the seventies, [AHU] and [BM] (these topics have been under-represented in [CLR], which is a highly successful extension and updating of [AHU] otherwise). Compared to [AHU] and [BM] our volume adds extensive material on parallel com­ putations with general matrices and polynomials, on the bit-complexity of arithmetic computations (including some recent techniques of data compres­ sion and the study of numerical approximation properties of polynomial and matrix algorithms), and on computations with Toeplitz matrices and other dense structured matrices. The latter subject should attract people working in numerous areas of application (in particular, coding, signal processing, control, algebraic computing and partial differential equations). The au­ thors' teaching experience at the Graduate Center of the City University of New York and at the University of Pisa suggests that the book may serve as a text for advanced graduate students in mathematics and computer science who have some knowledge of algorithm design and wish to enter the exciting area of algebraic and numerical computing. The potential readership may also include algorithm and software designers and researchers specializing in the design and analysis of algorithms, computational complexity, alge­ braic and symbolic computing, and numerical computation.

The study of the connections between mathematical automata and for­ mal logic is as old as theoretical computer science itself. In the founding paper of the subject, published in 1936, Turing showed how to describe the behavior of a universal computing machine with a formula of first­ order predicate logic, and thereby concluded that there is no algorithm for deciding the validity of sentences in this logic. Research on the log­ ical aspects of the theory of finite-state automata, which is the subject of this book, began in the early 1960's with the work of J. Richard Biichi on monadic second-order logic. Biichi's investigations were extended in several directions. One of these, explored by McNaughton and Papert in their 1971 monograph Counter-free Automata, was the characterization of automata that admit first-order behavioral descriptions, in terms of the semigroup­ theoretic approach to automata that had recently been developed in the work of Krohn and Rhodes and of Schiitzenberger. In the more than twenty years that have passed since the appearance of McNaughton and Papert's book, the underlying semigroup theory has grown enor­ mously, permitting a considerable extension of their results. During the same period, however, fundamental investigations in the theory of finite automata by and large fell out of fashion in the theoretical com­ puter science community, which moved to other concerns.

This book is a revised edition of the monograph which appeared under the same title in the series Research Notes in Theoretical Computer Science, Pit­ man, in 1986. In addition to a general effort to improve typography, English, and presentation, the main novelty of this second edition is the integration of some new material. Part of it is mine (mostly jointly with coauthors). Here is brief guide to these additions. I have augmented the account of categorical combinatory logic with a description of the confluence properties of rewriting systems of categor­ ical combinators (Hardin, Yokouchi), and of the newly developed cal­ culi of explicit substitutions (Abadi, Cardelli, Curien, Hardin, Levy, and Rios), which are similar in spirit to the categorical combinatory logic, but are closer to the syntax of A-calculus (Section 1.2). The study of the full abstraction problem for PCF and extensions of it has been enriched with a new full abstraction result: the model of sequential algorithms is fully abstract with respect to an extension of PCF with a control operator (Cartwright, Felleisen, Curien). An order­ extensional model of error-sensitive sequential algorithms is also fully abstract for a corresponding extension of PCF with a control operator and errors (Sections 2.6 and 4.1). I suggest that sequential algorithms lend themselves to a decomposition of the function spaces that leads to models of linear logic (Lamarche, Curien), and that connects sequentiality with games (Joyal, Blass, Abramsky) (Sections 2.1 and 2.6).

This monograph is a slightly revised version of my PhD thesis [86], com­ pleted in the Department of Computer Science at the University of Edin­ burgh in June 1988, with an additional chapter summarising more recent developments. Some of the material has appeared in the form of papers [50,88]. The underlying theme of the monograph is the study of two classical problems: counting the elements of a finite set of combinatorial structures, and generating them uniformly at random. In their exact form, these prob­ lems appear to be intractable for many important structures, so interest has focused on finding efficient randomised algorithms that solve them ap­ proxim~ly, with a small probability of error. For most natural structures the two problems are intimately connected at this level of approximation, so it is natural to study them together. At the heart of the monograph is a single algorithmic paradigm: sim­ ulate a Markov chain whose states are combinatorial structures and which converges to a known probability distribution over them. This technique has applications not only in combinatorial counting and generation, but also in several other areas such as statistical physics and combinatorial optimi­ sation. The efficiency of the technique in any application depends crucially on the rate of convergence of the Markov chain.

Recently, a variety ofresults on the complexitystatusofthegraph isomorphism problem has been obtained. These results belong to the so-called structural part of Complexity Theory. Our idea behind this book is to summarize such results which might otherwise not be easily accessible in the literature, and also, to give the reader an understanding of the aims and topics in Structural Complexity Theory, in general. The text is basically self contained; the only prerequisite for reading it is some elementary knowledge from Complexity Theory and Probability Theory. It can be used to teach a seminar or a monographic graduate course, but also parts of it (especially Chapter 1) provide a source of examples for a standard graduate course on Complexity Theory. Many people have helped us in different ways III the process of writing this book. Especially, we would like to thank V. Arvind, R.V. Book, E. May­ ordomo, and the referee who gave very constructive comments. This book project was especially made possible by a DAAD grant in the "Acciones In­ tegrada" program. The third author has been supported by the ESPRIT project ALCOM-II.

Typing plays an important role in software development. Types can be consid­ ered as weak specifications of programs and checking that a program is of a certain type provides a verification that a program satisfies such a weak speci­ fication. By translating a problem specification into a proposition in constructive logic, one can go one step further: the effectiveness and unifonnity of a con­ structive proof allows us to extract a program from a proof of this proposition. Thus by the "proposition-as-types" paradigm one obtains types whose elements are considered as proofs. Each of these proofs contains a program correct w.r.t. the given problem specification. This opens the way for a coherent approach to the derivation of provably correct programs. These features have led to a "typeful" programming style where the classi­ cal typing concepts such as records or (static) arrays are enhanced by polymor­ phic and dependent types in such a way that the types themselves get a complex mathematical structure. Systems such as Coquand and Huet's Calculus of Con­ structions are calculi for computing within extended type systems and provide a basis for a deduction oriented mathematical foundation of programming. On the other hand, the computational power and the expressive (impred­ icativity !) of these systems makes it difficult to define appropriate semantics.

This monograph studies the logical aspects of domains as used in de­ notational semantics of programming languages. Frameworks of domain logics are introduced; these serve as foundations for systematic derivations of proof systems from denotational semantics of programming languages. Any proof system so derived is guaranteed to agree with denotational se­ mantics in the sense that the denotation of any program coincides with the set of assertions true of it. The study focuses on two categories for dena­ tational semantics: SFP domains, and the less standard, but important, category of stable domains. The intended readership of this monograph includes researchers and graduate students interested in the relation between semantics of program­ ming languages and formal means of reasoning about programs. A basic knowledge of denotational semantics, mathematical logic, general topology, and category theory is helpful for a full understanding of the material. Part I SFP Domains Chapter 1 Introduction This chapter provides a brief exposition to domain theory, denotational se­ mantics, program logics, and proof systems. It discusses the importance of ideas and results on logic and topology to the understanding of the relation between denotational semantics and program logics. It also describes the motivation for the work presented by this monograph, and how that work fits into a more general program. Finally, it gives a short summary of the results of each chapter. 1. 1 Domain Theory Programming languages are languages with which to perform computa­ tion.

Humanity's most basic intellectual quest to decipher nature and master it has led to numerous efforts to build machines that simulate the world or communi­ cate with it [Bus70, Tur36, MP43, Sha48, vN56, Sha41, Rub89, NK91, Nyc92]. The computational power and dynamic behavior of such machines is a central question for mathematicians, computer scientists, and occasionally, physicists. Our interest is in computers called artificial neural networks. In their most general framework, neural networks consist of assemblies of simple processors, or "neurons," each of which computes a scalar activation function of its input. This activation function is nonlinear, and is typically a monotonic function with bounded range, much like neural responses to input stimuli. The scalar value produced by a neuron affects other neurons, which then calculate a new scalar value of their own. This describes the dynamical behavior of parallel updates. Some of the signals originate from outside the network and act as inputs to the system, while other signals are communicated back to the environment and are thus used to encode the end result of the computation.

This monograph develops techniques for equational reasoning in higher-order logic. Due to its expressiveness, higher-order logic is used for specification and verification of hardware, software, and mathematics. In these applica­ tions, higher-order logic provides the necessary level of abstraction for con­ cise and natural formulations. The main assets of higher-order logic are quan­ tification over functions or predicates and its abstraction mechanism. These allow one to represent quantification in formulas and other variable-binding constructs. In this book, we focus on equational logic as a fundamental and natural concept in computer science and mathematics. We present calculi for equa­ tional reasoning modulo higher-order equations presented as rewrite rules. This is followed by a systematic development from general equational rea­ soning towards effective calculi for declarative programming in higher-order logic and A-calculus. This aims at integrating and generalizing declarative programming models such as functional and logic programming. In these two prominent declarative computation models we can view a program as a logical theory and a computation as a deduction.

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.