Saturday, February 23, 2013

Why functional code is shorter

Was rereading John Carmack's Functional Programming in C++ post. For the most part, it's an excellent discussion of FP and its benefits, but there are a few points I wanted to dissect. Here, Carmack suggests the conciseness of functional programs has more to do with features like pattern matching and list comprehensions:

The process of refactoring towards purity generally involves disentangling computation from the environment it operates in, which almost invariably means more parameter passing. This seems a bit curious – greater verbosity in programming languages is broadly reviled, and functional programming is often associated with code size reduction. The factors that allow programs in functional languages to sometimes be more concise than imperative implementations are pretty much orthogonal to the use of pure functions — garbage collection, powerful built in types, pattern matching, list comprehensions, function composition, various bits of syntactic sugar, etc. For the most part, these size reducers don’t have much to do with being functional, and can also be found in some imperative languages.

Features like pattern matching and list comprehensions can indeed make code shorter, and they are convenient, but they're just constant factors. Like Carmack says, imperative programs could have access to these features too. The real decrease in code size when using FP comes from there being exponentially more code reuse possible due to the compositionality of pure code. I don't mean compositionality in the narrow sense of function composition, I mean it in the sense of being able to assemble complex functionality by sticking together simpler components in various ways. And compositionality dwarfs all other factors affecting our ability to write complex software.

The 'convenience' features are important more because they reduce the friction of composition (for instance, if your syntax for function literals are too heavyweight you are discouraged from writing your list-processing code by composing use of higher-order functions like map and filter, and you are discouraged from ever writing higher-order functions yourself).

We have only just begun to appreciate how compositionality can change the nature of software. I keep getting surprised by it. The progression of functional programming shows the rabbit hole goes very deep--yes, we can write loops with less boilerplate using map and filter, but we can also write combinator libraries, which let us assemble programs compositionally within a domain. Going further, we can abstract over commonalities across libraries, letting us assemble libraries for a domain from a preexisting suite of compositional library construction components (typeclasses like Monad, Applicative, and so on). And further patterns emerge from there--FP has now discovered patterns of architecture, like stream processing libraries, in which the typeclasses themselves are simply building blocks.

Moving on, another point Carmack mentioned was that we can't maintain purity throughout our programs since we eventually have to interact with the outside world:

Not everything can be pure; unless the program is only operating on its own source code, at some point you need to interact with the outside world. It can be fun in a puzzly sort of way to try to push purity to great lengths, but the pragmatic break point acknowledges that side effects are necessary at some point, and manages them effectively.

One of the big discoveries of FP is that while effects need to occur, observable side effects are not necessary. This is more than an accounting trick; we can indeed write programs that have effects on the outside world and which mutate data, etc, all while preserving referential transparency of the overall system and letting us program in a nice compositional style. FP is not in any way a restriction on what can be expressed, only a restriction on how it is expressed. It only requires us to be 'honest' about what is occurring, not limiting what functionality is expressible.


DevonMcC said...

I agree that functional composition helps make code more succinct. For example, in the functional language J (see, we have the notion of function (what we call a "verb") insertion across an array, represented by the adverb "/".

So, to sum an array along its first dimension, we combine the adverb with the verb "+", giving us "+/array". If, instead of the sum we want the product, we use "*/array". This extends to user-defined verbs, so "foo/array" inserts our "foo" verb between elements of the array.

However, there's also an aspect to thinking functionally that can shorten code. I recently encountered some Java script with numerous case statements like this one:

windowY += 10;
if( windowY > photo.height - windowHeight)
{ windowY = photo.height - windowHeight;

We can shorten and simplify this logic with a functional variant like this:

windowY = min( windowY+10, photo.height - windowHeight);

This seems to me to be conceptually much simpler than the typical "if...then" logic it replaces.

Shmulik said...

I'm a functional programming beginner, and I was piqued by your last paragraph, could you give an example or link to an appropriate resource that exemplify this property.