How does functional programming affect the structure of your code?
Posted by Brian on September 22, 2008
I recently listened to Ted and Amanda talking about F# on ".Net Rocks". Ted mentioned something about how with functional programming, some object-oriented (OO) design patterns (like ‘Command’) just disappear because you don’t need them when you have first-class functions. That’s a topic near and dear to my heart; back in school I co-authored a paper about this (see "FC++: Functional Tools for OO Tasks" on the FC++ page). It got me thinking about how "code comes out different" in F# versus C#, which in turn got me thinking about a conversation I had with Luke a couple months ago, where Luke argued convincingly that functional programming (FP) differentiates itself most obviously when programming "in the small". So I was thinking about all this stuff and it inspired me to write this blog entry where I try to get down all my thoughts on this.
Defining some terms
I want to discuss how functional programming techniques affect the structure of your code at three different levels, which today I will call "in the large", "in the medium", and "in the small". By "in the large" I mean a high level that affects and crosscuts multiple classes and functions throughout a program. By "in the medium" I mean the level of a single API or group of related APIs (e.g. a class, an interface, or a couple tightly-coupled classes or functions). By "in the small" I mean the level of individual method/function bodies – the actual code that "does stuff" as opposed to the structural/scaffolding/modularizing organization of that code. Functional programming in general (and F# in particular) affect the structure of code at all of these levels to various degrees, so I’ll talk about each level in turn.
Though I will cite a number of examples, I’m not showing any code in this blog entry. A catalog of "this is some code in C#, here’s the somehow-corresponding code in F#" could be interesting/useful, but is not my purpose today. I just want to talk about how code differs, and try to categorize and describe the essential differences I see, without getting too distracted by the details of any specific examples. So I’ll try to use examples "just enough" to get you thinking along the lines I’m thinking; you will need to follow hyperlinks in order to learn more about some examples I mention that you may not be familiar with.
In the large
I think that functional programming has the least influence on the structure of programs in the large, simply because when doing architecture or high-level design, you’re "too high up" for specific implementation techniques to matter too much. At this level, the strongest influence is the problem-domain itself; a good architecture decomposes a system into a set of modules and interactions that solve the problem under its key constraints (which may include performance/throughput of the system, distribution, reliability, etc.). This is true regardless of whether you’re wearing an FP hat or an OO hat; these styles can help shape your thinking about the problem, but don’t necessarily affect the final structure of the solution.
This is not to say that this level is completely free of FP influence. Though a now a quarter-century old, the oft-cited Why Functional Programming Matters has a great example here: section 5 talks about how laziness is essential to the architecture of a particular performant program and crosscuts whole API. The idea of using on-demand computations to decouple producers of data from their consumers is definitely useful, but it can be realized in myriad ways (coroutines, pipes, streams, IEnumerable<T>, …), so I’m not sure that FP can stake a complete claim here. But adding FP strategies to your mental bag of tricks can help diversify how you think about problems at a high level.
It bears mention that F# is a great tool for realizing a wide range of system architectures: whether your problem lends itself to service-orientation with stateless servers passing messages, or to high-performance computing that must take advantage of multiple cores, or to traditional OO modeling, decomposition, and encapsulation suitable to many desktop applications, the features in F# make for a natural implementation fit. By blending FP and OO, F# has the long reach to straightforwardly implement a wide range of designs, and its deep integration with .Net provides a very rich platform of libraries to build atop.
In the medium
Recall that by "in the medium", I mean program structure at the level of classes, interfaces, and individual method APIs. The good news here is that for a great many cases, OO design is just right. OO has dominated for the past couple of decades, and with good reason: decomposing a domain into classes (nouns) and methods (verbs and predicates) associated with those classes is an outstanding way to decompose a problem domain and structure a solution in source code.
However there are some cases where the OO strategy of "classes/nouns first" creates inferior solutions. The Command design pattern is a good example of such a case. The purely object-oriented solution realizes this pattern with a Command class or interface with a single method called "Execute". This is clearly just a function dressed up in "class" clothes. Whereas an OO solution requires lots of interacting named entities (a Command class or interface, an Execute method, concrete subtypes that fill in the method implementation and potentially capture extra state), a solution in a language with first-class functions requires none of these. A function type (e.g. "int->unit") is a sufficient description of the interface, and any named function or lambda with the right signature can be used as a concrete implementation. Closures make it trivial to capture any extra state that is needed. In short, all of the "structure" described by this pattern is unnecessary; first-class functions are a direct fit for the domains that "Command" tries to solve, and classes and interfaces are unnecessary. Similar observations can be made for a number of other design patterns, including Observer and Strategy.
There are other places where functional programming affects the structure of your code "in the medium". The Visitor pattern is another design pattern that can be handled differently using functional techniques; I discussed folds and catamorphisms at length in a prior blog entry. The availability of F# discriminated union (DU) types create opportunities to structure certain kinds of code more simply; a fixed class hierarchy can often be represented with a single DU type; I showed an example of this in a prior blog entry on DUs.
In C# (especially before C# 3.0), there were a number of situations where you would create named delegate types and/or classes (like FooEventArgs) to handle "events" or other customizations to the behavior of classes in a library. Again, these are best handled with function types (and the lambdas and "Func" delegates in C# 3.0 are progress towards reducing the extra needless friction that comes from some such APIs). Finally, sometimes in OO languages you are forced to package functions inside classes, when in fact the functions are happy to float free at the top level. Consider mathematical functions like "sqrt" or "pow" – whereas an OO languages typically forces you to stick these in a class and always qualify calls (e.g. "Math.Pow()"), in a language like F#, you can define functions like these in a open-able module or just at the top-level of your program, and access these by their short names (e.g. just "pow") or by defining operators (like "**").
In the small
By "in the small", I mean code at the level of individual method and function bodies. It’s here where functional programming in general, and using F# in particular, change the structure of your code most obviously. When "variables" are immutable by default, and you usually don’t need type annotations, and control is often expressed via expressions (if-then-else, pattern matching) and recursion, and you can define local/nested functions as easily as defining local variables… your code ends up looking pretty different at this level compared to typical code you’d see in other languages. The ability to author higher-order functions (like maps and folds) along with the ease of writing lambdas often means that code which you might typically write with a loop or recursion can be written with just a single call to a higher-order function; see this Joel on Software article for details on how and why this is so important and useful.
Examples here abound; just the other day I saw this blog post (check it out), which is a good example of the difference in styles "in the small". Sure, you can write the "List.min_by" function in C# and call it with a lambda, or use a LINQ query, but either of those C# solutions just highlights the FP style of programming. The point is that FP features like higher-order functions and currying are the enablers of this style of programming, and they can dramatically change and simplify the code you write in the small, down at the level of individual functions/methods or portions of method/algorithm implementations.
Furthermore, the "in the small" level is arguably the most important level of code, since it’s the only level that has to be there. There are plenty of times when you’re doing exploratory programming, or scripting, or writing glue code, when you simply won’t need to utilize any features for structuring/organizing programs "in the medium/large". Here, F# features, such as the ability to program directly at the top-level, type inference, and higher-order functions are huge wins that enable you to create shorter, simpler code. And most of these advantages still apply in larger programs, inside the bodies of individual functions and methods. The advantages of FP "in the small" accrue to programs of all sizes.
I think that functional programming affects the structure on a number of levels. FP’s influence is weakest "in the large"; at this level, the structure of the problem itself dominates, and FP’s influence comes mostly shaping one’s thinking about architectures or high-level designs. FP’s influence is more apparent "in the medium", where the design of some APIs can be simplified – sometimes dramatically in a few specific domains that are especially well-suited to FP. FP differentiates itself the most "in the small" – this is the level where computations happen, this is level where the majority of code (for programs of all sizes) is written, this is where most FP-specific constructs take hold.
I think it’s difficult to write convincing prose about programming without showing any code, but in this entry I linked to a number of examples that illustrated my points and matched my personal experience, in the hopes of causing you to recall similar examples from your own experiences programming in FP versus OO style. I expect that there are many other good examples out on the web that illustrate "how the code codes out differently" when you have your FP hat on… for those of you who don’t yet have much of your own FP experience to draw on, I’d encourage you to seek out more examples to see more of the concrete differences (and consider posting links to the best ones in the comments section of this blog entry, to make them easy for other readers to find).