An Introduction to Functional Programming Through Lambda Calculus

An Introduction to Functional Programming Through Lambda Calculus

by Greg Michaelson
4.0 1


$20.59 $25.95 Save 21% Current price is $20.59, Original price is $25.95. You Save 21%.
View All Available Formats & Editions
Eligible for FREE SHIPPING
  • Get it by Wednesday, May 30 , Order now and choose Expedited Delivery during checkout.


An Introduction to Functional Programming Through Lambda Calculus by Greg Michaelson

Functional programming is rooted in lambda calculus, which constitutes the world's smallest programming language. This well-respected text offers an accessible introduction to functional programming concepts and techniques for students of mathematics and computer science. The treatment is as nontechnical as possible, and it assumes no prior knowledge of mathematics or functional programming. Cogent examples illuminate the central ideas, and numerous exercises appear throughout the text, offering reinforcement of key concepts. All problems feature complete solutions.

Product Details

ISBN-13: 9780486478838
Publisher: Dover Publications
Publication date: 08/18/2011
Series: Dover Books on Mathematics Series
Pages: 336
Sales rank: 625,401
Product dimensions: 6.40(w) x 9.20(h) x 0.70(d)

About the Author

Gregory Michaelson is a Professor of Computer Science and Mathematics at Heriot-Watt University in Edinburgh, Scotland.

Read an Excerpt

An Introduction to Functional Programming Through Lambda Calculus

By Greg Michaelson

Dover Publications, Inc.

Copyright © 2011 Greg Michaelson
All rights reserved.
ISBN: 978-0-486-28029-5



1.1 Names and values in programming
1.2 Names and values in imperative and functional languages
1.3 Execution order in imperative and functional languages
1.4 Repetition in imperative and functional languages
1.5 Data structures in functional languages
1.6 Functions as values
1.7 The origins of functional languages
1.8 Computing and the theory of computing
1.9 λ calculus

Functional programming is an approach to programming based on function calls as the primary programming construct. It provides practical approaches to problem solving in general and insights into many aspects of computing. In particular, with its roots in the theory of computing, it forms a bridge between formal methods in computing and their application. In this chapter we are going to look at how functional programming differs from traditional imperative programming. We will do this by directly contrasting the imperative and functional approaches to various aspects of programming. We will then consider the origins of functional programming in the theory of computing and survey its relevance to contemporary computing theory and practice. Finally, we will discuss the role of lambda (λ) calculus as a basis for functional programming.

1.1 Names and values in programming

We write computer programs to implement solutions to problems. First, we analyse the problem. Then, we design a solution and implement it using a programming language. Solving a problem involves carrying out operations on values. Different values are used to solve different instances of a problem. If the values for a particular instance were built into the program, then they would have to be changed when the program was used to solve a different instance.

A fruitful approach to problem analysis is to try to identify a general case of the problem. Programming languages enable the implementation of general case solutions through the use of names to stand for arbitrary values. Thus, we write a program using names to stand for values in general. We then run the program with the names taking on particular values from the input for particular instances of the problem. The program does not have to be changed to be used with different values to solve a different instance of the problem: we simply change the inputs and the computer system makes sure that they are used with the right names in the program.

As we will see, the main difference between imperative programming languages, like Pascal, FORTRAN and COBOL, and functional programming languages, like SML and Miranda, lies in the rules governing the association of names and values.

1.2 Names and values in imperative and functional languages

Traditional programming languages are based around the idea of a variable as a changeable association between a name and values. These languages are said to be imperative because they consist of sequences of commands:


Typically, each command consists of an assignment which changes a variable's value. This involves working out the value of an expression and associating the result with a name:


In a program, each command's expression may refer to other variables whose values may have been changed by preceding commands. This enables values to be passed from command to command.

Functional languages are based on structured function calls. A functional program is an expression consisting of a function call which calls other functions in turn:

()( ...) ...)

Thus, each function receives values from and passes new values back to the calling function. This is known as function composition or nesting.

In imperative languages, commands may change the value associated with a name by a previous command so each name may be and usually will be associated with different values while a program is running.

In functional languages, names are only introduced as the formal parameters of functions and given values by function calls with actual parameters. Once a formal parameter is associated with an actual parameter value there is no way for it to be associated with a new value. There is no concept of a command which changes the value associated with a name through assignment. Thus, there is no concept of a command sequence or command repetition to enable successive changes to values associated with names.

1.3 Execution order in imperative and functional languages

In imperative languages, the order in which commands are carried out is usually crucial. Values are passed from command to command by references to common variables and one command may change a variable's value before that variable is used in the next command. Thus, if the order in which commands are carried out is changed then the behaviour of the whole program may change. For example, in the program fragment to swap X and Y:

T := X;
X := Y;
Y := T

T's value depends on X's value, X's value depends on Y's value and Y's value depends on T's value. Thus, any change in the sequence completely changes what happens. For example:

X := Y;
T := X;
Y := T

sets X to Y and:

T := X;
Y := T;
X := Y

sets Y to X.

Of course, not all command sequences have fixed execution orders. In many imperative languages, the order in which expressions are executed may not be defined. Thus, for expressions which involve function calls, the order in which the functions are called may not be defined. Functions have blocks of commands for bodies. Thus, the order in which the different command blocks are executed may not be defined.

This may lead to problems when imperative languages allow side effects – changes to variables made by expressions, for example, when a function changes a non-local variable by assignment to one of its parameters or to a global variable. If the order in which subexpressions are evaluated is unpredictable, then the order in which side effects occur is unpredictable. This makes it very hard to understand, develop and debug programs which utilize them.

If commands' expressions do not refer to each other, then the command execution order does not matter. However, programs usually depend on the precise order in which commands are carried out.

Pure functional languages lack assignment and so the values associated with names never change. Thus, there are no side effects and function calls cannot change the values associated with common names. Hence, the order in which nested function calls are carried out does not matter because function calls cannot interact with each other. For example, suppose we write functions in a style similar to Pascal:



In a functional language, in the function call:


the order in which A(D), B(D) and C(D) are carried out does not matter because the functions A, B and C cannot change their common actual parameter D.

Of course, functional programs must be executed in some order – all programs are – but the order does not affect the final result. As we shall see, this execution order independence is one of the strengths of functional languages and has led to their use in a wide variety of formal and practical applications.

1.4 Repetition in imperative and functional languages

In imperative languages, commands may change the values associated with a name by previous commands so a new name is not necessarily introduced for each new command. Thus, in order to carry out several commands several times, those commands need not be duplicated. Instead, the same commands are repeated. Hence, each name may be, and usually will be, associated with different values while a program is running. For example, in order to find the sum of the N elements of array A, we do not write:

SUM1 ;+ A[1];
SUM2 := SUM1 + A[2];
SUM3 := SUM2 + A[3];

Instead of creating N new SUMs and referring to each element of A explicitly, we write a loop that reuses one name for the sum, say SUM, and another that indicates successive array elements, say I:

I := 0;
SUM := 0;
I := 1 + 2;
SUM := SUM + A[I]

In functional languages, because the same names cannot be reused with different values, nested function calls are used to create new versions of the names for new values. Similarly, because command repetition cannot be used to change the values associated with names, recursive function calls are used repeatedly to create new versions of names associated with new values. Here, a function calls itself to create new versions of its formal parameters which are then bound to new actual parameter values. For example, we might write a function, in a style similar to Pascal, to sum an array:

SUM := 0
SUM := A[I] + SUM(A,I + 1,N)

Thus, for the function call:


the sum is found through successive recursive calls to SUM:

B[1] + SUM(B,2,M) =
B[1] + B[2] + SUM(B,3,M) =
B[1] + B[2] + ... + B[M] + SUM(B,M+1,M) =
B[1] + B[2] + ... + B[M] + 0

Here, each recursive call to SUM creates new local versions of A, I and N, and the previous versions become inaccessible. At the end of each recursive call, the new local variables are lost, the partial sum is returned to the previous call and the previous local variables come back into use.

1.5 Data structures in functional languages

In imperative languages, array elements and record fields are changed by successive assignments. In functional languages, because there is no assignment, substructures in data structures cannot be changed one at a time. Instead, it is necessary to write down a whole structure with explicit changes to the appropriate substructure.

Functional languages do not provide arrays because without assignment there is no easy way to access an arbitrary element. Writing out an entire array with a change to one element would be ludicrously unwieldy. Instead, nested data structures like lists are provided. These are based on recursive notations where operations on a whole structure are described in terms of recursive operations on substructures. The representations for nested data structures are often very similar to the nested function call notation. Indeed, in LISP (LISt Programming) the same representation is used for functions and data structures.

This ability to represent entire data structures has a number of advantages. It provides a standard format for displaying structures which greatly simplifies program debugging and final output as there is no need to write special printing subprograms for each distinct type of structure. It also provides a standard format for storing data structures which can remove the need to write special file I/O subprograms for distinct types of structure.

A related difference lies in the absence of global structures in functional languages. In imperative languages, if a program manipulates single distinct data structures, then it is usual to declare them as globals at the top level of a program. Their substructures may then be accessed and modified directly through assignment within subprograms without passing them as parameters. In functional languages, because there is no assignment, it is not possible to change substructures of globalstructures independently. Instead, entire data structures are passed explicitly as actual parameters to functions for substructure changes and the entire changed structure is then passed back again to the calling function. This means that function calls in a functional program are larger than their equivalents in an imperative program because of these additional parameters. However, it has the advantage of ensuring that structure manipulation by functions is always explicit in the function definitions and calls. This makes it easier to see the flow of data in programs.

1.6 Functions as values

In many imperative languages, subprograms may be passed as actual parameters to other subprograms but it is rare for an imperative language to allow subprograms to be passed back as results. In functional languages, functions may construct new functions and pass them on to other functions.

For example, the following contrived, illegal, Pascal-like function returns an arithmetic function depending on its parameter:





returns the FUNCTION:




returns the FUNCTION:


and so on. Thus, we might add two numbers with:


and so on. This is illegal in many imperative languages because it is not possible to construct functions of type 'function'. As we shall see, the ability to manipulate functions as values gives functional languages substantial power and flexibility.

1.7 The origins of functional languages

Functional programming has its roots in mathematical logic. Informal logical systems have been in use for over 2000 years but the first modern formalizations were by Hamilton, De Morgan and Boole in the mid nineteenth century. Within their works we now distinguish the propositional calculus and the predicate calculus.

Propositional calculus is a system with true and false as basic values and with and, or, not and so on as basic operations. Names are used to stand for arbitrary truth values. Within propositional calculus, it is possible to prove whether or not an arbitrary expression is a theorem (always true), by starting with axioms (elementary expressions which are always true), and applying rules of inference to construct new theorems from axioms and existing theorems. Propositional calculus provides a foundation for more powerful logical systems. It is also used to describe digital electronics where on and off signals are represented as true and false respectively, and electronic circuits are represented as logical expressions.

Predicate calculus extends propositional calculus to enable expressions involving non-logical values like numbers, sets or strings. This is achieved through the introduction of predicates which generalize logical expressions to describe properties of non-logical values, and functions to generalize operations on non-logical values. It also introduces the idea of quantifiers to describe properties of sequences of values, for example, universal quantification, for all of a sequence having a property, or existential quantification, for one of a sequence having a property. Additional axioms and rules of inference are provided for quantified expressions. Predicate calculus may be applied to different problem areas through the development of appropriate predicates, functions, axioms and rules of inference. For example, number theoretic predicate calculus is used to reason about numbers. Functions are provided for arithmetic and predicates are provided for comparing numbers. Predicate calculus also forms the basis of logic programming in languages like PROLOG, and of expert systems based on logical inference.


Excerpted from An Introduction to Functional Programming Through Lambda Calculus by Greg Michaelson. Copyright © 2011 Greg Michaelson. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

Table of Contents

Preface to the Dover Edition iii

Preface v

Chapter 1 Introduction 1

1.1 Names and values in programming 2

1.2 Names and values in imperative and functional languages 2

1.3 Execution order in imperative and functional languages 3

1.4 Repetition in imperative and functional languages 5

1.5 Data structures in functional languages 7

1.6 Functions as values 8

1.7 The origins of functional languages 9

1.8 Computing and the theory of computing 11

1.9 ? calculus 13

Summary 14

Chapter 2 λ calculus 15

2.1 Abstraction 16

2.2 Abstraction in programming languages 19

2.3 Introducing λ calculus 20

2.4 λ expressions 21

2.5 Simple λ functions 23

2.6 Introducing new syntax 30

2.7 Notations for naming functions and reduction 31

2.8 Functions from functions 31

2.9 Argument selection and argument pairing functions 33

2.10 Free and bound variables 33

2.11 Name clashes and α conversion 43

2.12 Simplification through η reduction 44

Summary 45

Exercises 47

Chapter 3 Conditions, booleans and numbers 49

3.1 Truth values and conditional expression 50

3.2 NOT 51

3.3 AND 52

3.4 OR 54

3.5 Natural numbers 55

3.6 Simplified notations 59

Summary 61

Exercises 62

Chapter 4 Recursion and arithmetic 65

4.1 Repetitions, iteration and recursion 66

4.2 Recursion through definitions? 68

4.3 Passing a function to itself 69

4.4 Applicative order reduction 72

4.5 Recursion function 73

4.6 Recursion notation 77

4.7 Arithmetic operations 78

Summary 82

Exercises 84

Chapter 5 Types 87

5.1 Types and programming 88

5.2 Types as objects and operations 89

5.3 Representing typed objects 91

5.4 Errors 92

5.5 Booleans 94

5.6 Typed conditional expression 97

5.7 Numbers and arithmetic 98

5.8 Characters 101

5.9 Repetitive type checking 104

5.10 Static and dynamic type checking 107

5.11 Infix operators 107

5.12 Case definitions and structure matching 108

Summary 111

Exercises 113

Chapter 6 Lists and strings 115

6.1 Lists 116

6.2 List representation 119

6.3 Operations on lists 122

6.4 List notation 124

6.5 Lists and evaluation 127

6.6 Deletion from a list 127

6.7 List comparison 129

6.8 Strings 131

6.9 String comparison 132

6.10 Numeric string to number conversion 134

6.11 Structure matching with lists 139

6.12 Ordered linear lists, insertion and sorting 140

6.13 Indexed linear list access 142

6.14 Mapping functions 146

Summary 150

Exercises 151

Chapter 7 Composite values and trees 153

7.1 Composite values 154

7.2 Processing composite value sequences 155

7.3 Selector functions 157

7.4 Generalized structure matching 160

7.5 Local definitions 164

7.6 Matching composite value results 164

7.7 List inefficiency 167

7.8 Trees 168

7.9 Adding values to ordered binary trees 169

7.10 Binary tree traversal 173

7.11 Binary tree search 174

7.12 Binary trees of composite values 176

7.13 Binary tree efficiency 178

7.14 Curried and uncurried functions 179

7.15 Partial application 181

7.16 Structures, values and functions 183

Summary 183

Exercises 184

Chapter 8 Evaluation 187

8.1 Termination and normal form 188

8.2 Normal order 189

8.3 Applicative order 190

8.4 Consistent applicative order use 191

8.5 Delaying evaluation 193

8.6 Evaluation termination, the halting problem, evaluation equivalence and the Church-Rosser theorems 196

8.7 Infinite objects 197

8.8 Lazy evaluation 199

Summary 204

Exercises 205

Chapter 9 Functional programming in Standard ML 207

9.1 Types 208

9.2 Lists 209

9.3 Tuples 210

9.4 Function types and expressions 211

9.5 Standard functions 212

9.6 Comparison operators 218

9.7 Functions 218

9.8 Making bound variables' types explicit 219

9.9 Definitions 220

9.10 Conditional expressions 221

9.11 Recursion and function definitions 221

9.12 Tuple selection 222

9.13 Pattern matching 223

9.14 Local definitions 225

9.15 Type expressions and abbreviated types 226

9.16 Type variables and polymorphism 227

9.17 New types 230

9.18 Trees 234

9.19 λ calculus in SML 237

9.20 Other features 238

Summary 238

Exercises 238

Chapter 10 Functional programming and LISP 243

10.1 Atoms, numbers and symbols 244

10.2 Forms, expressions and function applications 245

10.3 Logic 245

10.4 Arithmetic and numeric comparison 246

10.5 Lambda functions 248

10.6 Global definitions 250

10.7 Conditional expressions 251

10.8 Quoting 252

10.9 Lists 253

10.10 List selection 255

10.11 Recursion 256

10.12 Local definitions 257

10.13 Binary trees in LISP 257

10.14 Dynamic and lexical scope 259

10.15 Functions as values and arguments 261

10.16 Symbols, quoting and evaluation 263

10.17 λ calculus in LISP 265

10.18 λ calculus and Scheme 266

10.19 Other features 268

Summary 268

Exercises 268

Answers to exercises 273

Bibliography 305

Index 313

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews

An Introduction to Functional Programming Through Lambda Calculus 4 out of 5 based on 0 ratings. 1 reviews.
Anonymous More than 1 year ago
The lambda expressions are too small to read on my Nook. Comparisons to languages such as Pascal are lost on me.