Saturday, January 17, 2009

W3R-7: Summary and Assessment

In the What's Wrong With Reduce series, I've attempted to resolve contrasting views of the usefulness of higher order function called reduce or fold. By examining the origins of reduce, we saw that it is an abstraction over a particular recursive pattern of control flow. Further, reduce can be readily defined in Python.

However, it is easy to find cases where reduce works well for a functional programming language but poorly in Python. In essence, reduce is an abstraction over a common pattern for functional programming languages that is uncommon in imperative programming languages like Python. Instead, a much narrower selection of Python procedures map well onto the reduce control abstraction.

By examining control flow patterns actually used in Python, a more appropriate higher order procedure1, app, was identified as an alternative to reduce. Several common control flow patterns cannot be captured by app, so a dual gen procedure was also defined.

Between app and gen, we can define many functions to process or create iterators. However, an important question remains: should we use app or gen? I'd have to say that it isn't worthwhile. Both app and gen are abstractions over imperative patterns, depending crucially on side effects. As a consequence, it is of equal importance to understand the order in which, say, app processes the elements of an iterator. Thus, app fails to provide any conceptual benefit over just using a for loop—in contrast, functional programming with reduce, map, and other higher order functions lets you ignore the order in which things are done.

That said, I use and define higher order procedures all the time in Python. I just define them as (generator) functions using imperative constructs like for or while loops. Also, like the itertools module, my higher order procedures typically take iterators as arguments or return them as results. So long as iterators only need to be used once, this looks a lot like functional programming. Really, it is closer to dataflow programming.

Having an effective alternative to reduce is relatively unimportant for this iterator-intensive programming style. Far more useful would be higher order procedures that simplify composing multiple procedures taking and returning iterators. The overall result should be more like constructing a shell pipeline instead of the extensive nesting of procedure calls currently seen.

1 For clarity, I distinguish here between higher order functions and higher order procedures. Functions should really be mathematical functions, i.e., no side effects, while procedures are more general.

No comments: