Greg Michaelson - An Introduction to Functional Programming Through Lambda Calculus

An Introduction to FUNCTIONAL PROGRAMMING Through LAMBDA CALCULUS Greg Michaelson Heriot-Watt University DOVER PUBLICATIONS, INC. Mineola, New York Copyright Copyright 1989, 2011 by Greg Michaelson
All rights reserved. Bibliographical Note This Dover edition, first published in 2011, is an unabridged republication of the work originally published in 1989 by Addison-Wesley Publishing Company, Wokingham, England. The author has provided a new Preface for this edition. Library of Congress Cataloging-in-Publication Data Michaelson, Greg, 1953 An introduction to functional programming through Lambda calculus / Greg Michaelson. p. cm. cm.

Originally published: Workingham, England : Addison-Wesley, 1989. Includes bibliographical references and index. ISBN-13: 978-0-486-47883-8 ISBN-10: 0-486-47883-1 1. Functional programming (Computer science). 2. I. Title. Title.

QA76.6.M4854 2011
005.1'14dc22 2010031017 Manufactured in the United States by Courier Corporation
47883101
www.doverpublications.com Context When I started to write this book in 1986, functional programming seemed on an upward trajectory, out of academia into real-world computing. Spurred by the Japanese 5th Generation programme, many other nations initiated research and development schemes around stateless declarative programming languages. The Japanese projects laid great stress on hardware and software to support logic programming. In contrast, the UK Alvey programme gave equal emphasis to functional languages. Thus, major British multi-University and industry projects sought to develop viable functional computing platforms at all levels, from VLSI and multi-processor hardware for graph reduction and combinators, like Cobweb, Alice and GRIP, through novel programming languages, like Hope, Standard ML and Haskell, to fully integrated systems like the Flagship. Despite lasting research successes, overall the 5th Generation programmes utterly failed to make any impact on the von Neumann/imperative language status quo, and are now largely forgotten.

In particular, declarative languages were oversold as the solution to the software crisis. The core claim was that the absence of state provided a model that greatly simplified high levels of abstraction, component based software construction, parallel implementation and proof of correctness. My original Introduction to this book is one such example of Zeitgeist enthusiasm. While declarative languages have many advantages for problems which are highly compositional in their data, the lack of state is a major hindrance for most substantive applications which do things in rather than beyond time. Similarly, while proving properties of declarative programs may, for small exemplars, be somewhat easier than for imperative code, this again depends on highly compositional program structure. The bottom line is that constructing and proving correct programs is hard, be it in a declarative or imperative language.

Nonetheless, research in functional programming has remained buoyant and its industrial significance is steadily growing, if somewhat more slowly than anticipated 25 years ago. Most strikingly, Ericssons Erlang, originally used for telecommunications, is gaining wider currency for general multi-process systems. Furthermore, Microsoft Research supports the development of the Haskell language and has integrated its own Standard ML-derivedF# into the core .NET framework. Constructs from functional languages have also found their way into mainstream imperative languages. Thus, functional abstraction is supported in Microsofts system language C#, the general purpose Ruby, the scripting language Python and the Java-derived Groovy. Finally, cheap high performance computing on tens of thousands of commodity platforms has enabled international Internet businesses to build services on standardised parallel frameworks, based explicitly on higher order constructs.

For example, Googles search engines are driven by their proprietary Map-Reduce, and Yahoo deploys Apaches open source Hadoop. , calculus remains central to Computing education and research. Functional programming is a routine component of many Computer Science undergraduate programmes, as are computability theory, and, to a lesser extent, formal semantics. Functional techniques are being used in novel approaches to constructing scalable heterogeneous multi-processor systems and to developing mission and safety critical systems requiring strong assurances that requirements are met. New calculi building on 1 calculus have been systematically developed for modelling multi-process systems, for example Milners Communicating Concurrent Systems, Calculus and bigraphs. Content Looking at this book from a markedly older and greyer perspective, by and large I feel happy with it.

In particular, I remain firmly wedded to the pedagogy of learning by abstraction from concrete examples, of understanding calculus through actually doing it in an explicitly operational manner, and of gaining oversight of the layers between a simple, foundational system and a rich language of variegated constructs and structures. The books major eccentricity remains my reformulation of classic calculus syntax. In Churchs notation, applications in function bodies are unbracketed, but functions are bracketed except where there is no ambiguity. I chose instead to bracket applications in function bodies but to not bracket functions except where there is ambiguity, as I felt these were more in keeping with programming language conventions. In retrospect, I suspect that this may prove unduly confusing to novices trying to use this book to complement other sources. I now think that the account of lazy evaluation could be simplified.

There is also merit in one reviewers suggestion that a pure lazy polymorphic language might have been described given that both Lisp and SML are strict and impure. However, when the book was written, Miranda was a commercial product and Haskell had not been standardised. Finally, my favourite chapter remains that on recursion. Conclusion When I was wee, my parents had lots of Dover books: Charles Babbage, Lewis Carroll, Gustave Dore ... I am tickled pink to be in the company of such authors. So, I would very much like to thank: John Crossley for suggesting that I approach Dover; John Grafton at Dover for reprinting this book, and for all his support.

Greg Michaelson, Edinburgh, May 2011.

It is based on the premise that functional programming provides pedagogic insights into many aspects of computing and offers practical techniques for general problem solving. The approach taken is to start with pure calculus, Alonzo Churchs elegant but simple formalism for computation, and to add syntactic layers for function definitions, booleans, integers, recursion, types, characters, lists and strings to build a fairly high level functional notation. Along the way, a variety of topics are discussed including arithmetic, linear list and binary tree processing, and alternative evaluation strategies. Finally, functional programming in Standard ML and Common LISP, using techniques developed throughout the book, are explored. Readership This book is intended for people who have taken a first course in an imperative programming language like Pascal, FORTRAN or C and have written programs using arrays and subprograms. There are no mathematical prerequisites and no prior experience with functional programming is required.

The material from this book has been taught to third year undergraduate Computer Science students and to postgraduate Knowledge-Based Systems MSc students. Using the book The material is presented sequentially. Each chapter depends on previous chapters. Within chapters, substantial use is made of worked examples. Each chapter ends with exercises which are based directly on ideas and techniques from that chapter. Specimen answers are included at the end of the book.