Monday, February 07, 2011

My essence of functional programming

Functional programming is about working with pure "low level computational constructions" in order to sustain "higher level computational abstractions" across an algorithm or program.
You may remember from your computer science education that there are three ways a function (lambda expression) can be rewritten (or reduced):
  • Alpha reduction: renaming variables
  • Beta reduction: applying functions to their arguments
  • Eta reduction: moving independent code out a scope's function
Functional languages typically have more features than simple lambda expressions. For example, functions can have multiple arguments, type and type inference is available, and possibly also classes and objects. Yet functional programming is really about "pulling" the low level concepts of the function, especially beta and eta rewrites, upwards into higher and higher abstractions of concepts.

For example, an immediate application of beta reduction is lazyness: a "smart" control of the function application to implement something like a "compute on demand" logic in order to be able to deal with non terminating computational structure. Other flavors of Beta rewriting

Eta reduction is possibly even more important than beta reduction. It is the rule that allows your code to "change its focus" by swiveling the order of the arguments of functions and bringing in new arguments. Working with functions can at first seem horribly constrictive because they have only one input (their arguments) and one output (their result). Worse than that, the order of the arguments is very important because only the last argument(s) can be moved from a left side formulation to a right side formulation; From f x y = to f x = fun y -> ... Nevertheless, eta reduction is saying that f x y can be rewritten as f' y x, or even f '' y x z as long as x and y are still used in the same fashion. One of the first things to learn in functional programming is how to order arguments to make functions fit together. My basic rule is that there are three types of arguments:
  1. Parametric: they are generally constant over the life time of the function
  2. Stateful: 'environmental' parameters that represent some form of state being passed around
  3. Primary or type centric: the main arguments of the function, the ones the function has been written for
The magic of the eta rewrite property is that the parameters can be reordered so that the parametric parameters come first, then the stateful ones and finally the primary ones. Doing so allows the following:
  • Functions can directly be "specialized" by instantiating their parametric arguments. For example, a function f n x can be be initialized as f100 = f 100. (This is example is meant to show the concept, in reality what is usually done is that f n x is defined and another function is called that calculates n and then proceeds to create fn as f n for a fixed value of n. And typically n is not numeric but often a function!)
  • Stateful parameters can all be regroup into a single argument and wrapped up into a standardized calling pattern. We have just reinvented the state monad!
  • The primary parameters being last then can often be omitted in a combinatorial programming style. The simplest of these is the use of function composition: if we have f x and g y, we can compose f and g without "mentioning" the arguments. (In F# f |> g)
Having now defined these three "characters" of arguments, we can go a little deeper:
  • Parametric arguments can be normalized so as to support modularity. The concept is a little bit like virtual look-up tables under OO: introducing an indirection provides flexibility. An additional pattern I favor is to bootstrap the parametric arguments with fix-point combinators.
  • As I mentioned: the stateful argument is very much what the state monad is all about. Therefore I favor always using monads to carry around the stateful parameter(s).
  • The primary parameter can also be normalized. For example, it may be supporting an iteration, a mapping or a join like operation. Another example is that it may have sub-types and combinatorial operations may be defined to work only on specific sub-types.
I'll stop here for today but there are definitely a few other key constructions of the essence of functional programming worth mentioning.

No comments: