From “Research Topics in Functional Programming” ed. D. Turner, Addison-Wesley, 1990, pp 17–42. 1WhyFunctional ProgrammingMattersJohn HughesThe University, GlasgowAbstractAs software becomes more and more complex, it is more and moreimp ortant 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 development.1 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 are.Functional programming is so called because its fundamental operation isthe application of functions to arguments. 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 primitive s. All of these functionsare much like ordinary mathematical functions, and in this paper they will be1An earlier version of this paper appeared in the The Computer Journal, 32(2):98–107,April 1989. Copyright belon gs 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 appears.defined by ordinary equations. We are following Turner’s language Miranda[4]2here, but the notation should be readable without specific knowledge of this.The s pecial characteristics and advantages of functional programming areoften summed up more or less as follows. Functional programs contain noassignment stateme nts, 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 re sult. 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 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 functionalprogramming isn’t (it has no assignment, no side effects, no flow of control) butnot much about what it is. 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 unconvincing.Functional programmers argue that there are great 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 then Fortran programmers 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 be.Even a functional programmer should be dissatisfied with these so-calledadvantages, because they give no help in exploiting the power of functional lan-guages. 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 at.Clearly 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 towards.2Miranda is a trademark of Research Software Ltd.22 An Analogy with Structured ProgrammingIt’s helpful to draw an analogy between functional and structured programming.In the past, the characteristics and advantages of structured programming havebeen summed up more or less as follows. Structured programs contain no gotostatements. Blocks in a structured program do not have multiple entries or exits.Structured 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. Theyare essentially negative statements, and have led to much fruitless argumentabout “essential gotos” and so on.With 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 debugging.The absence of gotos, and so on, has very little to do with this. It helps with“programming in the small”, whereas