Why Functional Programming Matters by John Hughes

Why Functional Programming Matters

• As software becomes more and more complex, it is more and more important to structure it well.
• Well-structured software is easy to write and to debug, and provides a collection of modules that can be reused to reduce future programming costs.
• In this paper we show that two features of functional languages in particular, higher-order functions and lazy-evaluation, can contribute significantly to modularity.
• Functional programming is so called because its fundamental operation is the application of functions to arguments.
• 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 an expression's value, it can be evaluated at any time. This relieves the programmer of the burden of prescribing the flow of control. Since expression 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.
• It is a logical impossibility to make a language more powerful by omitting features, no matter how bad they may be.
• In the past, the characteristics an 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.
• The most important difference between structured and unstructured programs is that structured programs are designed in a modular way.
• When writing a modular program to solve a problem, one first divides the problem into sub problems, then solves the sub problems, and finally 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 one' ability to modularize a problem conceptually, one must provide new kinds of glue in the programming language.
• This is the key to functional programmings power--it allows improved modularization.
• Recall that a complete functional program is just a function from its input to its output.
• Lazy evaluation is perhaps the most powerful tool of modularization in the functional programmer's repertoire.
• We have argued that functional languages are powerful primarily because they provide two new kinds of glue: higher-order functions and lazy evaluation.
• The heart of the alpha-beta [pruning] algorithm is the observation that one can often compute the value returned by maximize or minimize without looking at the whole tree.
• In this paper, we've argued that modularity is the key to successful programming. Languages that aim to improve productivity must support module programming well.
• Our ability to decompose a problem into parts depends directly on our ability to glue solutions together.
• To support modular programming, a language must provide good glue.
• Functional programming languages provide two new kinds of glue--higher-order functions and lazy-evaluation.