An Introduction to Functional Programming Through Lambda Calculus

Greg Michaelson

• Éditeur: Dover Publications
• Année: 2013
• ISBN:
  9780486280295
• Sujet: Mathematics
• Sous-sujet: Calculus

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.

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 imperative languages, the same name may be associated with different values.

---

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.

---

In functional languages, a name is only ever associated with one value.

---

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’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:

sets X to Y and:

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.

---

In general, imperative languages have fixed command execution orders.

---

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.

---

In functional languages, there is no fixed execution order.

---

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:

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:

---

In imperative languages, new values may be associated with the same name through command repetition.

---

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...