You are here

An Introduction to Functional Programming through Lambda Calculus

Greg Michaelson
Dover Publications
Publication Date: 
Number of Pages: 
[Reviewed by
Tom Schulte
, on

This Dover reprint of Michaelson’s classic text keeps available an accessible introduction to functional programming concepts. Light on theory, this text is aimed at beginning students of computer science. The largely nontechnical presentation assumes no prior knowledge of mathematics or functional programming. With lots of examples and exercises with complete solutions, this work is an excellent, standalone resource for independent study or classroom use. The 2011 reprint includes a preface by Michaelson, giving an honest appraisal not only of the book, but of the (lack of) success declarative programming has had in the marketplace while remaining an important research area.

As one who has trained and hired software engineers over the years, I have seen that a mindset of iteration and conditional statements can often lead to inefficient designs. Someone with an introductory knowledge of LISP or Haskell, or simply aware of general declarative principles as outlined here, often can come up with more compact and efficient designs in object-oriented programming (OOP). The excellent chapter here on recursion highlights a key concept I find taught better through functional programming. I recommend that those serious about OOP read this as a “mind hack” to spark innovation and a fresh assessment of the tools at hand.

The book is generally very easy to understand. The background required here for understanding the practical basics of lambda calculus is less than in, say, Hankin’s An Introduction to Lambda Calculi for Computer Scientists.

There are often a great many examples of the same narrow topic, such as with comparison operators or string to number conversion. Yet, this excess of explanation makes the text excellent for self-study of functional programming approaches to types, list and string manipulation, trees, evaluation order, and more. The book includes an overview of functional programming implemented in Standard ML and LISP.

Tom Schulte is the Business Intelligence Engineer for ERP provider Plex Systems in Auburn Hills, Michigan.

1. Introduction
2. Lambda Calculus
3. Conditions, booleans, and numbers
4. Recursion and arithmetic
5. Types
6. Lists and Strings
7. Composite values and trees
8. Evaluation
9. Functional programming in Standard ML
10. Functional programming and LISP
Answers to exercises