An Introduction to Functional Programming Through Lambda Calculus

by Greg Michaelson

Overview

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:	9780486280295
Publisher:	Dover Publications
Publication date:	03/13/2013
Series:	Dover Books on Mathematics
Sold by:	Barnes & Noble
Format:	eBook
Pages:	336
File size:	17 MB
Note:	This product may take a few minutes to download.

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

---

CHAPTER 1

Introduction

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
Summary

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:

FUNCTION F(X, Y, Z:INTEGER):INTEGER;
BEGIN ... END
FUNCTION A(P:INTEGER):INTEGER;

BEGIN ... END
FUNCTION B(Q:INTEGER):INTEGER;
BEGIN ... END
FUNCTION C(R:INTEGER):INTEGER;
BEGIN ... END

In a functional language, in the function call:

F(A(D),B(D),C(D))

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;
WHILE I N DO
BEGIN
I := 1 + 2;
SUM := SUM + A[I]
END

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:

FUNCTION SUM(A:ARRAY [1..N] OF INTEGER;
I,N:INTEGER):INTEGER;
BEGIN
IF I > N THEN
SUM := 0
ELSE
SUM := A[I] + SUM(A,I + 1,N)
END

Thus, for the function call:

SUM(B,1,M)

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:

TYPE OPTYPE = (ADD,SUB,MULT,QUOT);

FUNCTION ARITH(OP:OPTYPE):FUNCTION;
FUNCTION SUM(X,Y:INTEGER):INTEGER;
BEGIN SUM := X+Y END;
FUNCTION DIFF(X,Y:INTEGER):INTEGER;
BEFIN DIFF := X-Y END.
FUNCTION TIMES(X,Y:INTEGER):INTEGER;
BEGIN TIMES := X+Y END;
FUNCTION DIVIDE(X,Y:INTEGER):INTEGER;
BEGIN DIVIDE := X DIV Y END;
BEGIN
CASE OP OF
ADD: ARITH := SUM;
SUB: ARITH := DIFF;
MULT: ARITH := TIMES;
QUOT: ARITH := DIVIDE;
END
END

Thus:

ARITH(ADD)

returns the FUNCTION:

SUM

and:

ARITH(SUB)

returns the FUNCTION:

DIFF

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

ARITH(ADD)3,4)

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.

(Continues...)

---

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

Preface1. Introduction2. Lambda Calculus3. Conditions, booleans, and numbers4. Recursion and arithmetic5. Types6. Lists and Strings7. Composite values and trees8. Evaluation9. Functional programming in Standard ML10. Functional programming and LISPAnswers to exercisesBibliographyIndex

Editorial Reviews

A textbook for computer science students, providing an accessible introduction to functional programming concepts and techniques. Assumes no prior knowledge of mathematics or functional programming. Annotation c. Book News, Inc., Portland, OR (booknews.com)

Booknews