Why Functional Programming Matters
, Institutionen för Datavetenskap,
Högskola,
Copyright By PowCoder代写 加微信 powcoder
41296 Göteborg,
This paper dates from 1984, and circulated as a Chalmers memo for many
years. Slightly revised versions appeared in 1989 and 1990 as [Hug90] and
[Hug89]. This version is based on the original Chalmers memo nroff
source, lightly edited for LaTeX and to bring it closer to the published ver-
sions, and with one or two errors corrected. Please excuse the slightly old-
fashioned type-setting, and the fact that the examples are not in Haskell!
As software becomes more and more complex, it is more and more
important to structure it well. Well-structured software is easy to write,
easy to debug, and provides a collection of modules that can be re-used
to reduce future programming costs. Conventional languages place con-
ceptual limits on the way problems can be modularised. Functional lan-
guages push those limits back. In this paper we show that two features of
functional languages in particular, higher-order functions and lazy eval-
uation, can contribute greatly to modularity. As examples, we manipu-
late lists and trees, program several numerical algorithms, and implement
the alpha-beta heuristic (an algorithm from Artificial Intelligence used in
game-playing programs). Since modularity is the key to successful pro-
gramming, functional languages are vitally important to the real world.
1 Introduction
This paper is an attempt to demonstrate to the “real world” that functional
programming is vitally important, and also to help functional programmers
exploit its advantages to the full by making it clear what those advantages are.
Functional programming is so called because a program consists entirely of
functions. The main program itself is written as a function which receives the
program’s input as its argument and delivers the program’s output as its result.
Typically the main function is defined in terms of other functions, which in
turn are defined in terms of still more functions, until at the bottom level the
functions are language primitives. These functions are much like ordinary math-
ematical functions, and in this paper will be defined by ordinary equations. Our
notation follows Turner’s language Miranda(TM) [Tur85], but should be read-
able with no prior knowledge of functional languages. (Miranda is a trademark
of Research Software Ltd.)
The special characteristics and advantages of functional programming are
often summed up more or less as follows. Functional programs contain no
assignment statements, so variables, once given a value, never change. More
generally, functional programs contain no side-effects at all. A function call can
have no effect other than to compute its result. This eliminates a major source
of bugs, and also makes the order of execution irrelevant – since no side-effect
can change the value of an expression, it can be evaluated at any time. This
relieves the programmer of the burden of prescribing the flow of control. Since
expressions can be evaluated at any time, one can freely replace variables by
their values and vice versa – that is, programs are “referentially transparent”.
This freedom helps make functional programs more tractable mathematically
than their conventional counterparts.
Such a catalogue of “advantages” is all very well, but one must not be sur-
prised if outsiders don’t take it too seriously. It says a lot about what functional
programming is not (it has no assignment, no side effects, no flow of control) but
not much about what it is. The functional programmer sounds rather like a me-
dieval monk, denying himself the pleasures of life in the hope that it will make
him virtuous. To those more interested in material benefits, these “advantages”
are not very convincing.
Functional programmers argue that there are great material benefits – that
a functional programmer is an order of magnitude more productive than his
conventional counterpart, because functional programs are an order of magni-
tude shorter. Yet why should this be? The only faintly plausible reason one
can suggest on the basis of these “advantages” is that conventional programs
consist of 90% assignment statements, and in functional programs these can be
omitted! This is plainly ridiculous. If omitting assignment statements brought
such enormous benefits then FORTRAN programmers would have been doing it
for twenty years. It is a logical impossibility to make a language more powerful
by omitting features, no matter how bad they may be.
Even a functional programmer should be dissatisfied with these so-called
advantages, because they give him no help in exploiting the power of functional
languages. One cannot write a program which is particularly lacking in assign-
ment statements, or particularly referentially transparent. There is no yardstick
of program quality here, and therefore no ideal to aim at.
Clearly this characterisation of functional programming is inadequate. We
must find something to put in its place – something which not only explains the
power of functional programming, but also gives a clear indication of what the
functional programmer should strive towards.
2 An Analogy with Structured Programming
It is helpful to draw an analogy between functional and structured programming.
In the past, the characteristics and advantages of structured programming have
been summed up more or less as follows. Structured programs contain no goto
statements. Blocks in a structured program do not have multiple entries or exits.
Structured programs are more tractable mathematically than their unstructured
counterparts. These “advantages” of structured programming are very similar in
spirit to the “advantages” of functional programming we discussed earlier. They
are essentially negative statements, and have led to much fruitless argument
about “essential gotos” and so on.
With the benefit of hindsight, it is clear that these properties of structured
programs, although helpful, do not go to the heart of the matter. The most im-
portant difference between structured and unstructured programs is that struc-
tured programs are designed in a modular way. Modular design brings with
it great productivity improvements. First of all, small modules can be coded
quickly and easily. Secondly, general purpose modules can be re-used, leading to
faster development of subsequent programs. Thirdly, the modules of a program
can be tested independently, helping to reduce the time spent debugging.
The absence of gotos, and so on, has very little to do with this. It helps with
“programming in the small”, whereas modular design helps with “programming
in the large”. Thus one can enjoy the benefits of structured programming in
FORTRAN or assembly language, even if it is a little more work.
It is now generally accepted that modular design is the key to successful pro-
gramming, and languages such as Modula-II [Wir82], Ada [oD80] and Standard
ML [MTH90] include features specifically designed to help improve modularity.
However, there is a very important point that is often missed. When writing
a modular program to solve a problem, one first divides the problem into sub-
problems, then solves the sub-problems and combines the solutions. The ways
in which one can divide up the original problem depend directly on the ways
in which one can glue solutions together. Therefore, to increase ones ability
to modularise a problem conceptually, one must provide new kinds of glue in
the programming language. Complicated scope rules and provision for separate
compilation only help with clerical details; they offer no new conceptual tools
for decomposing problems.
One can appreciate the importance of glue by an analogy with carpentry.
A chair can be made quite easily by making the parts – seat, legs, back etc. –
and sticking them together in the right way. But this depends on an ability
to make joints and wood glue. Lacking that ability, the only way to make a
chair is to carve it in one piece out of a solid block of wood, a much harder
task. This example demonstrates both the enormous power of modularisation
and the importance of having the right glue.
Now let us return to functional programming. We shall argue in the remain-
der of this paper that functional languages provide two new, very important
kinds of glue. We shall give many examples of programs that can be modu-
larised in new ways, and thereby greatly simplified. This is the key to functional
programming’s power – it allows greatly improved modularisation. It is also the
goal for which functional programmers must strive – smaller and simpler and
more general modules, glued together with the new glues we shall describe.
3 Glueing Functions Together
The first of the two new kinds of glue enables simple functions to be glued
together to make more complex ones. It can be illustrated with a simple list-
processing problem – adding up the elements of a list. We define lists by
listof X ::= nil | cons X (listof X)
which means that a list of Xs (whatever X is) is either nil, representing a list
with no elements, or it is a cons of an X and another list of Xs. A cons represents
a list whose first element is the X and whose second and subsequent elements
are the elements of the other list of Xs. X here may stand for any type – for
example, if X is “integer” then the definition says that a list of integers is either
empty or a cons of an integer and another list of integers. Following normal
practice, we will write down lists simply by enclosing their elements in square
brackets, rather than by writing conses and nils explicitly. This is simply a
shorthand for notational convenience. For example,
[] means nil
[1] means cons 1 nil
[1,2,3] means cons 1 (cons 2 (cons 3 nil))
The elements of a list can be added up by a recursive function sum. Sum must
be defined for two kinds of argument: an empty list (nil), and a cons. Since the
sum of no numbers is zero, we define
sum nil = 0
and since the sum of a cons can be calculated by adding the first element of the
list to the sum of the others, we can define
sum (cons num list) = num + sum list
Examining this definition, we see that only the boxed parts below are specific
to computing a sum.
sum nil = | 0 |
sum (cons num list) = num | + | sum list
This means that the computation of a sum can be modularised by glueing
together a general recursive pattern and the boxed parts. This recursive pattern
is conventionally called reduce and so sum can be expressed as
sum = reduce add 0
where for convenience reduce is passed a two argument function add rather than
an operator. Add is just defined by
add x y = x + y
The definition of reduce can be derived just by parameterising the definition of
sum, giving
(reduce f x) nil = x
(reduce f x) (cons a l) = f a ((reduce f x) l)
Here we have written brackets around (reduce f x) to make it clear that it
replaces sum. Conventionally the brackets are omitted, and so ((reduce f x) l) is
written as (reduce f x l). A function of 3 arguments such as reduce, applied to
only 2 is taken to be a function of the one remaining argument, and in general,
a function of n arguments applied to only m(< n) is taken to be a function of
the n−m remaining ones. We will follow this convention in future.
Having modularised sum in this way, we can reap benefits by re-using the
parts. The most interesting part is reduce, which can be used to write down
a function for multiplying together the elements of a list with no further pro-
product = reduce multiply 1
It can also be used to test whether any of a list of booleans is true
anytrue = reduce or false
or whether they are all true
alltrue = reduce and true
One way to understand (reduce f a) is as a function that replaces all occurrences
of cons in a list by f, and all occurrences of nil by a. Taking the list [1,2,3] as
an example, since this means
cons 1 (cons 2 (cons 3 nil))
then (reduce add 0) converts it into
add 1 (add 2 (add 3 0)) = 6
and (reduce multiply 1) converts it into
multiply 1 (multiply 2 (multiply 3 1)) = 6
Now it is obvious that (reduce cons nil) just copies a list. Since one list can be
appended to another by consing its elements onto the front, we find
append a b = reduce cons b a
As an example,
append [1,2] [3,4] = reduce cons [3,4] [1,2]
= (reduce cons [3,4]) (cons 1 (cons 2 nil))
= cons 1 (cons 2 [3,4]))
(replacing cons by cons and nil by [3,4])
= [1,2,3,4]
A function to double all the elements of a list could be written as
doubleall = reduce doubleandcons nil
where doubleandcons num list = cons (2*num) list
Doubleandcons can be modularised even further, first into
doubleandcons = fandcons double
where double n = 2*n
fandcons f el list = cons (f el) list
and then by
fandcons f = cons . f
where “.” (function composition, a standard operator) is defined by
(f . g) h = f (g h)
We can see that the new definition of fandcons is correct by applying it to some
arguments:
fandcons f el = (cons . f) el
= cons (f el)
so fandcons f el list = cons (f el) list
The final version is
doubleall = reduce (cons . double) nil
With one further modularisation we arrive at
doubleall = map double
map f = reduce (cons . f) nil
where map applies any function f to all the elements of a list. Map is another
generally useful function.
We can even write down a function to add up all the elements of a matrix,
represented as a list of lists. It is
summatrix = sum . map sum
The map sum uses sum to add up all the rows, and then the left-most sum adds
up the row totals to get the sum of the whole matrix.
These examples should be enough to convince the reader that a little mod-
ularisation can go a long way. By modularising a simple function (sum) as a
combination of a “higher order function” and some simple arguments, we have
arrived at a part (reduce) that can be used to write down many other functions
on lists with no more programming effort. We do not need to stop with func-
tions on lists. As another example, consider the datatype of ordered labelled
trees, defined by
treeof X ::= node X (listof (treeof X))
This definition says that a tree of Xs is a node, with a label which is an X, and
a list of subtrees which are also trees of Xs. For example, the tree
would be represented by
(cons (node 2 nil)
(cons (node 3
(cons (node 4 nil) nil))
Instead of considering an example and abstracting a higher order function from
it, we will go straight to a function redtree analogous to reduce. Recall that
reduce took two arguments, something to replace cons with, and something to
replace nil with. Since trees are built using node, cons and nil, redtree must
take three arguments - something to replace each of these with. Since trees and
lists are of different types, we will have to define two functions, one operating
on each type. Therefore we define
redtree f g a (node label subtrees) =
f label (redtree’ f g a subtrees)
redtree’ f g a (cons subtree rest) =
g (redtree f g a subtree) (redtree’ f g a rest)
redtree’ f g a nil = a
Many interesting functions can be defined by glueing redtree and other functions
together. For example, all the labels in a tree of numbers can be added together
sumtree = redtree add add 0
Taking the tree we wrote down earlier as an example, sumtree gives
(add (add 2 0)
(add (add 3
(add (add 4 0) 0))
A list of all the labels in a tree can be computed using
labels = redtree cons append nil
The same example gives
(append (cons 2 nil)
(append (cons 3
(append (cons 4 nil) nil))
= [1,2,3,4]
Finally, one can define a function analogous to map which applies a function f
to all the labels in a tree:
maptree f = redtree (node . f) cons nil
All this can be achieved because functional languages allow functions which are
indivisible in conventional programming languages to be expressed as a combi-
nation of parts - a general higher order function and some particular specialising
functions. Once defined, such higher order functions allow many operations to
be programmed very easily. Whenever a new datatype is defined higher order
functions should be written for processing it. This makes manipulating the
datatype easy, and also localises knowledge about the details of its represen-
tation. The best analogy with conventional programming is with extensible
languages - it is as though the programming language can be extended with
new control structures whenever desired.
4 Glueing Programs Together
The other new kind of glue that functional languages provide enables whole
programs to be glued together. Recall that a complete functional program is
just a function from its input to its output. If f and g are such programs, then
(g . f) is a program which, when applied to its input, computes
g (f input)
The program f computes its output which is used as the input to program g.
This might be implemented conventionally by storing the output from f in a
temporary file. The problem with this is that the temporary file might occupy
so much memory that it is impractical to glue the programs together in this way.
Functional languages provide a solution to this problem. The two programs f
and g are run together in strict synchronisation. F is only started once g tries
to read some input, and only runs for long enough to deliver the output g is
trying to read. Then f is suspended and g is run until it tries to read another
input. As an added bonus, if g terminates without reading all of f’s output then
f is aborted. F can even be a non-terminating program, producing an infinite
amount of output, since it will be terminated forcibly as soon as g is finished.
This allows termination conditions to be separated from loop bodies - a powerful
modularisation.
Since this method of evaluation runs f as little as possible, it is called “lazy
evaluation”. It makes it practical to modularise a program as a generator which
constructs a large number of possible answers, and a selector which chooses the
appropriate one. While some other systems allow programs to be run together in
this manner, only functional languages use lazy evaluation uniformly for every
function call, allowing any part of a program to be modularised in this way.
Lazy evaluation is perhaps the most powerful tool for modularisation in the
functional programmer’s repertoire.
4.1 Newton-Raphson Square Roots
We will illustrate the power of lazy evaluation by programming some numerical
algorithms. First of all, consider the Newton-Raphson algorithm for finding
square roots. This algorithm computes the square root of a number N by starting
from an initial approximation a0 and computing better and better ones using
a(n+1) = (a(n) + N/a(n)) / 2
If the approximations converge to some limit a, then
a = (a + N/a) / 2
so 2a = a + N/a
a = squareroot(N)
In fact the approximations converge rapidly to a limit. Square root programs
take a tolerance (eps) and stop when two successive approximations differ by
less than eps.
The algorithm is usually programmed more or less as follows:
C N IS CALLED ZN HERE SO THAT IT HAS THE RIGHT TYPE
Y = A0 + 2.*EPS
C THE VALUE OF Y DOES NOT MATTER SO LONG AS ABS(X-Y).GT.EPS
100 IF (ABS(X-Y).LE.EPS) GOTO 200
X = (X + ZN/X) / 2.
200 CONTINUE
C THE SQUARE ROOT OF ZN IS NOW IN X
This program is indivisible in conventional languages. We will express it in a
more modular form using lazy evaluation, and then show some other uses to
which the parts may be put.
Since the Newton-Raphson algorithm computes a sequence of approxima-
tions it is natural to represent this explicitly in the program by a list of approx-
imations. Each approximation is derived from the previous one by the function
next N x = (x + N/x) / 2
so (next N) is the f
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com