Dienstag, Januar 02, 2007

Does Functional Programming Matter?

More than 20 years ago, John Hughes wrote a seminal paper about "Why Functional Programming Matters" -- a paper still worth reading. He argues that functional programming provides new kinds of "glue", which enable a programmer to modularize code in a much better way than is possible in a "conventional" (imperative) language. He talks about "the importance of having the right glue". Hughes identifies two kinds of glue: lazy evaluation and higher-order functions.

Meanwhile, conventional languages have caught up -- I don't think that John Hughes' arguments still hold. Let me briefly explain, why I think so.

Lazy Evaluation

Lazy evaluation is a fascinating feature. It delays a computation until a result is really needed. Haskell, for instance, is based on this evaluation paradigm. In Lisp or Scheme, lazy evaluation can be simulated with so-called streams.

With lazy evaluation, code can be in fact highly modularized. One example in Hughes' paper is the Newton-Raphson algorithm for finding square roots. I re-wrote the code in Scheme (using DrScheme), which looks like this:

(require (lib "stream.ss" "srfi" "40"))

(define (next_c N)
(lambda (a)
(/ (+ a (/ N a)) 2.0)))

(define (repeat f init)
(stream-cons init (repeat f (f init))))

(define (within eps stream)
(let ((a (stream-car stream))
(b (stream-car (stream-cdr stream))))
(if (<= (abs (- a b)) eps)
(within eps (stream-cdr stream)))))

(define (my-sqrt guess eps N)
(within eps (repeat (next_c N) guess)))

The point is that the algorithm for approximating the square root ("next_c") is cleanly separated from "within". Even better, "within" is not specifically programmed for "next_c", it can be used generically! That's what Hughes means, when he talks about modularization. The concerns (approximating the square root and checking if the difference of two subsequent values of a stream lies within a threshold) are separately put in independent functions and used in combination by a combining function "my-sqrt".

If you take a language like Python, which offers generators as a language feature (see also here), you can easily modularize the code in the very same way. With generators, streams can be easily emulated. Here's my hack:

def next(N,a):
while True:
a = (a + N/a) / 2.0
yield a

def within(eps,generator,*args):
g = generator(*args)
a,b = g.next(), g.next()
while abs(a-b) > eps:
a,b = b, g.next()
return b

def my_sqrt(guess,eps,N):
return within(eps,next,N,guess)

The code is practical identical in structure and lines of code. Generators enable a programmer to modularize code in the very same way as is provided by streams and/or lazy evaluation.

Higher-Order Functions

Higher-Order Functions (HOFs) are functions, which can digest one or more functions and/xor return a function as a result. In pure functional programming, HOFs are a must, otherwise, function composition would be impossible.

Other languages are not built around the notion of a function. Their basic units of handling are, for instance, objects or components. In object-orientation or component-orientation you have other means of modularization. So, there is limited need to simulate HOFs. Despite this, most "conventional" languages provide some sort of support for HOFs. In Python, for example, there is a built-in "map" and "reduce" function. It's even possible to return functions as a result; Python supports lambda expressions.

Final Remark

Before someone misunderstands me: I would still agree that functional programming matters. But in a different way. It is just not a matter of "modularization glue" (in the sense of John Hughes) any more. The gap between functional and imperative languages is closing!


Anonym hat gesagt…

Note that in PLT Scheme there is now a Lazy Scheme language (which you can use as a module too). This is a real lazy language, much more than what you get with streams.

dh hat gesagt…

I wasn't aware of this module, thanks for the hint. Just about 720 lines of code are required to make Scheme lazy. I'm always stunned about the power of Scheme.

caracarn11 hat gesagt…

> Before someone misunderstands me: I would still agree that functional programming matters. But in a different way. It is just not a matter of "modularization glue" (in the sense of John Hughes) any more. The gap between functional and imperative languages is closing!

But you are specifically "distinguish" between functional & imperative languages - I don't think that was the intent of John Hughes. These "imperative" languages are actually multi-paradigm, but we are most familiar with their imperative side.

In languages that offers multiple paradigm - of course you can also choose functional programming or another style - showing your examples merely reaffirms such style has merits ;)

And in general it is difficult to immerse fully in functional style unless one is constraint from doing so, evident from many claiming Haskell being a hard language to learn.

P.S. And here lies the trouble for people who says best tool for the job unless they had a chance to immerse in a language like Haskell - when they say "best" they are simply saying what's most familiar to them ;)

Seun Osewa hat gesagt…

I wonder whether functional programming has real life benefits. Programs that were made easier through functional programming (versus, say, using imperative python) are too hard to find.

Marty White hat gesagt…

I respectfully disagree with your take on imperative languages "catching up":

Python's "generators" feature is a somewhat odd sort of beast that is
useful mainly insofar is it enables more functional programming, not imperative programming.

Imperative languages may, with these newer (and sometimes more awkward) features, be catching up to where functional programming was 20 years ago, but functional programming has moved further and is now providing features that imperative languages are nowhere near to getting, such as monadic and STM techniques for managing concurrency and statefulness.