Guy Cousineau - The Functional Approach to Programming

A programming course should concentrate as much as possible on a programs logical structure and design rather than simply show how to write code. The functional approach to programming achieves this aim because logical concepts are evident and programs are transparent so can be written quickly and cleanly. In this book the authors emphasise the notions of function and function application which relate programming to familiar concepts from mathematics and logic. They introduce functional programming via examples but also explain what programs compute and how to reason about them. They show how the ideas can implemented in the Caml language, a dialect of the ML family, and give examples of how complex programs from a variety of areas (such as arithmetic, tree algorithms, graph algorithms, text parsing and geometry) can be developed in close agreement with their specifications.

Many exercises and examples are included throughout the book; solutions are also available.

Guy Cousineau is professor at cole Normale Suprieure in Paris and head of the computer science laboratory.

Michel Mauny is Directeur de Recherche at INRIA-Rocquencourt, and head of the Cristal research team, where the Caml language is being developed.

Guy Cousineau

cole Normale Suprieure, Paris

and

Michel Mauny

INRIA-Rocquencourt

PUBLISHED BY THE PRESS SYNDICATE OF THE UNIVERSITY OF CAMBRIDGE

The Pitt Building, Trumpington Street, Cambridge CB2 1RP, United Kingdom

www.cambridge.org

Information on this title: www.cambridge.org/9780521571838

CAMBRIDGE UNIVERSITY PRESS

The Edinburgh Building, Cambridge CB2 2RU, UK http://www.cup.cam.ac.uk

40 West 20th Street, New York, NY 10011-4211, USA http://www.cup.org

10 Stamford Road, Oakleigh, Melbourne 3166, Australia

First published in French by Edisciences 1995 Edisciences 1995

English edition Cambridge University Press 1998

This book is copyright. Subject to statutory exception and to the provisions of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press.

First published in English 1998

Typeset by the author [CRC]

A catalogue record of this book is available from the British Library

ISBN 0 521 57183 9 hardback

ISBN 0 521 57681 4 paperback

Transferred to digital printing 2003

To the best of our knowledge, none of the code included in this book in itself contains any date sensitive elements that will cause Year 2000-related problems. However, this statement implies no warranty in this matter, on the part of the authors or the publisher.

This book has a number of objectives. First, it provides the concepts and a language to produce sophisticated software. Second, the book tries to make you step back a bit from programming as an activity by highlighting basic problems linked to programming as a discipline. In the end, we hope to share our own pleasure in programming.

The language we useCAMLmakes it possible to achieve all these goals. CAML belongs to the family of functional languages, all of which have the following qualities:

They are particularly well adapted to writing applications for symbolic computation"the kind of computing that concerns computer scientists as well as mathematiciansin software engineering, artificial intelligence, formal computation, computer-aided proof, and so forth.

Functional languages are built on a fundamental theory that derives from mathematical logic. This basis provides these languages with their semantics as well as their systems of types and proof.

By the very way in which they are designed, these languages support a certain aesthetic in programming, an aesthetic which, like the aesthetic of a mathematical proof, is often an indication of their quality.

This book grew primarily out of a programming course given by Guy Cousineau at the Ecole Normale Suprieure between 1990 and 1995. The book also benefited from the teaching experience of Michel Mauny, who wrote ) includes supplementary materials including solutions to the exercises.

The approach to functional programming in this book owes a great deal to the experience gained during the development of CAML, first by the Formel Project and then by the Cristal Project at INRIA (the French National Institute for Research in Computer Science and Automation) in collaboration with Universit Denis Diderot and the Ecole Normale Suprieure. Both authors thank all the members of the research teams involved as well as other people who helped us in writing this book, whether through their ideas or their comments about the preliminary drafts of the manuscript. We owe particular thanks to Gilles Bernot, Jean Berstel, Bruno Blanchet, Emmanuel Chailloux, Antoine Chambert-Loir, Lucky Chilian, Pierre Crgut, Pierre-Louis Curien, Vincent Danos, Roberto DiCosmo, Damien Doligez, Maribel Fernandez, Thrse Hardin, Robert Harley, Grard Huet, Xavier Leroy, Rodrigo Lopez, Valrie Mnissier, Giancarlo Nota, Jean-Franois Perrot, Laurence Puel, Daniel de Rauglaudre, Didier Rmy, Christian Rinderknecht, Emilie Sayag, Michle Soria, Ascnder Surez, Pierre Weis.

We also thank Kathleen Callaway who translated the book to English with great care and the anonymous referees who provided very useful suggestions.

The spectacular development of the computing industry depends largely on progress in two very different areas: hardware and software. Progress in hardware has been fairly quantitative: miniaturized parts, increased performance, cost cutting; whereas the progress in software has been more qualitative: ease of use, friendliness, etc.

In fact, most users see their computer only through interfaces that let them exploit the machine while ignoring practically all its structure and internal details, just as if we drove our cars without ever opening the hood, just like we enjoy the comfort of central heating without necessarily grasping thermodynamics.

This qualitative improvement was brought to us by progress in software as an independent discipline. It is based on a major research effort, in the course of which computer science has been structured little by little around its own concepts and methods. Those concepts and methods, of course, should be the basis for teaching computer science.

The most fundamental concept in computer science is computing, of course. A computation is a set of transformations carried out mechanically by means of a finite number of predefined rules. A computation impinges on formalized symbolic data (information) representing, for example, numbers (as in numeric computations) or mathematical expressions (as in formal computation) or data or even knowledge of all kinds. The only characteristics common to all computations is the discreteness of their data (that is, the information is finite) and the mechanical way in which the rules are applied.

The role of computer science is first of all to provide the means to specify and execute computations and, at a more theoretical level, to study the properties of those computations, such as, for example, their cost. Concretely, we specify computations with the help of programs written in a programming language. Computations can also be studied more abstractly through algorithms. These two approaches give rise to two disciplines in computer scienceprogramming and algorithmsdisciplines strikingly different in their aims and methods.