Why Functional Programming Matters

1 From Research Topics in Functional Programming ed. D. Turner, Addison-Wesley, 1990, pp 17 ProgrammingMattersJohn HughesThe University, GlasgowAbstractAs software becomes more and more complex, it is more and moreimportant to structure it well. Well-structured software is easy to writeand to debug, and provides a collection of modules that can be reusedto reduce future Programming costs. In this paper we show that two fea-tures of Functional languages in particular, higher-order functions and lazyevaluation, can contribute significantly to modularity. As examples, wemanipulate lists and trees, program several numerical algorithms, and im-plement the alpha-beta heuristic (an algorithm from Artificial Intelligenceused in game-playing programs). We conclude that since modularity is thekey to successful Programming , Functional Programming offers importantadvantages for software IntroductionThis paper is an attempt to demonstrate to the larger community of (non- Functional ) programmers the significance of Functional Programming , and alsoto help Functional programmers exploit its advantages to the full by making itclear what those advantages Programming is so called because its fundamental operation isthe application of functions to arguments.

2 A main program itself is written asa function that receives the program s input as its argument and delivers theprogram s output as its result. Typically the main function is defined in terms ofother functions, which in turn are defined in terms of still more functions, untilat the bottom level the functions are language primitives. All of these functionsare much like ordinary mathematical functions, and in this paper they will be1An earlier version of this paper appeared in theTheComputerJournal, 32(2):98 107,April 1989. Copyright belongs to The British Computer Society, who grant permission tocopy for educational purposes only without fee provided the copies are not made for directcommercial advantage and this BCS copyright notice by ordinary equations. We are following Turner s language Miranda[4]2here, but the notation should be readable without specific knowledge of special characteristics and advantages of Functional Programming areoften summed up more or less as follows.

3 Functional programs contain noassignment statements, so variables, once given a value, never change. Moregenerally, Functional programs contain no side-effects at all. A function callcan have no effect other than to compute its result. This eliminates a majorsource of bugs, and also makes the order of execution irrelevant since no side-effect can change an expression s value, it can be evaluated at any time. Thisrelieves the programmer of the burden of prescribing the flow of control. Sinceexpressions can be evaluated at any time, one can freely replace variables bytheir values and vice versa that is, programs are referentially transparent .This freedom helps make Functional programs more tractable mathematicallythan their conventional 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 functionalprogramming isn t (it has no assignment, no side effects, no flow of control) butnot much about what it is.

4 The Functional programmer sounds rather like amedi val monk, denying himself the pleasures of life in the hope that it willmake him virtuous. To those more interested in material benefits, these ad-vantages are totally programmers argue that therearegreat material benefits thata Functional programmer is an order of magnitude more productive than hisor her conventional counterpart, because Functional programs are an order ofmagnitude shorter. Yet why should this be? The only faintly plausible reasonone can suggest on the basis of these advantages is that conventional programsconsist of 90% assignment statements, and in Functional programs these can beomitted! This is plainly ridiculous. If omitting assignment statements broughtsuch enormous benefits thenFortranprogrammers would have been doing itfor twenty years. It is a logical impossibility to make a language more powerfulby omitting features, no matter how bad they may a Functional programmer should be dissatisfied with these so-calledadvantages, because they give no help in exploiting the power of Functional lan-guages.

5 One cannot write a program that is particularly lacking in assignmentstatements, or particularly referentially transparent. There is no yardstick ofprogram quality here, and therefore no ideal to aim this characterization of Functional Programming is inadequate. Wemust find something to put in its place something that not only explains thepower of Functional Programming but also gives a clear indication of what thefunctional programmer should strive is a trademark of Research Software An Analogy with Structured ProgrammingIt s helpful to draw an analogy between Functional and structured the past, the characteristics and advantages of structured Programming havebeen summed up more or less as follows. Structured programs contain nogotostatements. Blocks in a structured program do not have multiple entries or programs are more tractable mathematically than their unstructuredcounterparts. These advantages of structured Programming are very similar inspirit to the advantages of Functional Programming we discussed earlier.

6 Theyare essentially negative statements, and have led to much fruitless argumentabout essentialgotos and so the benefit of hindsight, it s clear that these properties of structuredprograms, 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 withit great productivity improvements. First of all, small modules can be codedquickly and easily. Second, general-purpose modules can be reused, leading tofaster development of subsequent programs. Third, the modules of a programcan be tested independently, helping to reduce the time spent absence ofgotos, and so on, has very little to do with this. It helps with Programming in the small , whereas modular design helps with programmingin the large . Thus one can enjoy the benefits of structured Programming inFortranor assembly language, even if it is a little more is now generally accepted that modular design is the key to successfulprogramming, and recent languages such asModula-II[6] and Ada [5] includefeatures specifically designed to help improve modularity.

7 However, there is avery important point that is often missed. When writing a modular program tosolve a problem, one first divides the problem into subproblems, then solves thesubproblems, and finally combines the solutions. The ways in which one candivide up the original problem depend directly on the ways in which one can gluesolutions together. Therefore, to increase one s ability to modularize a problemconceptually, one must provide new kinds of glue in the Programming scope rules and provision for separate compilation help only withclerical details they can never make a great contribution to shall argue in the remainder of this paper that Functional languages pro-vide two new, very important kinds of glue. We shall give some examples ofprograms that can be modularized in new ways and can thereby be is the key to Functional Programming s power it allows improved mod-ularization. It is also the goal for which Functional programmers must strive smaller and simpler and more general modules, glued together with the newglues we shall Gluing Functions TogetherThe first of the two new kinds of glue enables simple functions to be gluedtogether to make more complex ones.

8 It can be illustrated with a simple list-processing problem adding the elements of a list. We can define lists3bylistof ::=Nil|Cons (listof )which means that a list of s (whatever is) is eitherNil, representing a listwith no elements, or aConsof a and another list of s. AConsrepresentsa list whose first element is the and whose second and subsequent elementsare the elements of the other list of s. Here may stand for any type forexample, if is integer then the definition says that a list of integers is eitherempty or aConsof an integer and another list of integers. Following normalpractice, we will write down lists simply by enclosing their elements in squarebrackets, rather than by writingConses andNils explicitly. This is simply ashorthand for notational convenience. For example,[ ]meansNil[1]meansCons1 Nil[1,2,3] meansCons1 (Cons2 (Cons3 Nil))The elements of a list can be added by a recursive functionsum. The functionsummust be defined for two kinds of argument: an empty list (Nil), and aCons.

9 Since the sum of no numbers is zero, we definesumNil= 0and since the sum of aConscan be calculated by adding the first element ofthe list to the sum of the others, we can definesum(Consn list) =num+sum listExamining this definition, we see that only the boxed parts below are specificto computing a (Consn list) =n+sum listThis means that the computation of a sum can be modularized by gluingtogether a general recursive pattern and the boxed parts. This recursive patternis conventionally calledfoldrand sosumcan be expressed assum=foldr(+) 03In Miranda, lists can also be defined using the built-in constructor (:), but the notationused here is equally definition offoldrcan be derived just by parameterizing the definition ofsum, giving(foldrf x)Nil=x(foldrf x) (Consa l) =f a((foldrf x)l)Here we have written brackets around (foldrf x) to make it clear that it replacessum. Conventionally the brackets are omitted, and so ((foldrf x)l) is writtenas (foldrf x l).

10 A function of three arguments such asfoldr, applied to onlytwo, is taken to be a function of the one remaining argument, and in general,a function ofnarguments applied to onlymof them (m < n) is taken to be afunction of then mremaining ones. We will follow this convention in modularizedsumin this way, we can reap benefits by reusing theparts. The most interesting part isfoldr, which can be used to write down afunction for multiplying together the elements of a list with no further program-ming:product=foldr( ) 1It can also be used to test whether any of a list of booleans is trueanytrue=foldr( )F alseor whether they are all truealltrue=foldr( )TrueOne way to understand (foldrf a) is as a function that replaces all occurrencesofConsin a list byf, and all occurrences ofNilbya. Taking the list [1,2,3]as an example, since this meansCons1 (Cons2 (Cons3 Nil))then (foldr(+) 0) converts it into(+) 1 ((+) 2 ((+) 3 0)) = 6and (foldr( ) 1) converts it into( ) 1 (( ) 2 (( ) 3 1)) = 6 Now it s obvious that (foldr Cons Nil) just copies a list.