I’d like to explore a way of looking at programming by analogy to nouns and verbs. This provides a framework for categorising languages and functionality, and I believe also gives insight into some of the causes for impedance mismatches that so complicate apparently trivial tasks such as transparent database persistence or dependency injection. Perhaps it also gives us a hint as to why some people are naturally drawn to Object Oriented Programming (OOP) and others to Functional Programming (FP), in all their varied forms.
Foundations of OOP and FP
OOP is pervasive in contemporary programming. It conceptualises programming in terms of objects that provide fields and methods, where fields are data associated with that object and methods are procedures which run within the context of that object. OOP languages can further be divided into those that organise objects by a class hierarchy or through the use of prototypes. The process of OOP design is centred around designing class hierarchies or prototypes that enable the application domain to be modelled. In pure OOP, everything is an object, although most main-stream OO languages provide a base set of primitives with efficient hardware representation. So, the integer 3 is an object that has methods to perform common arithmetic operations. For example, it may expose a method `-(x: Int): Int` for negation and `+(x: Int): Int` for addition.
FP is the new (old) thing. It conceptualises programming in terms of functions, including higher-order functions acting upon other functions. Although all main-stream FP languages extend this primitive model with data types for common things like numbers and strings, in its purest form even data is represented as functions. Let’s consider the integers from a FP perspective. In pure FP, remember we are representing things as functions, including higher-order functions. So, what would be a natural way to represent the number 3? Well, the Church encoding takes the rather elegant option of making 3 a function that takes a value and another function, and returns the value after the function has been applied 3 times. The numbers 0 and 1 have interesting Church encodings. 0 can be represented as the higher-order function that just returns the value without applying the function at all: , which happens to coincide with the church encoding of and also the combinator from various logics. 1 can be represented as the higher-order function that applys the function exactly once: , which is just with the arguments swapped.
Where as OOP is all about objects, FP is all about functions. Objects have a life-cycle. They come into existence, change over time and then go away. They have identity that persists throughout the life of the object. As fields are updated or methods invoked, the same object persists. Functions transform inputs to outputs. They can stand in for each other if they embody the same transformation from inputs to outputs. They only exist to act on things. In short, objects behave like items we’d name with nouns, and functions behave like items we’d name with verbs.
Design patterns for nouns and verbs
In practice, does this dichotomy between coding with nouns and coding with verbs have an impact upon the day-to-day business of programming? Let’s start by looking at the common design patterns used in OOP and FP. I contend that OO design patterns tend towards mechanisms for composing nouns, while FP design patterns tend towards mechanism for composing verbs. In both cases, the aim is to maximise decoupling and encapsulation.
A design pattern is a software design that addresses a repeated need in an elegant fashion. It usually will enable code-reuse, both allowing new code to use old, but more importantly, old code to use new. Design patterns are typically expressed as a series of types with particular webs of relationships, where each realisation will elaborate and rename to fit it to the application domain. They embody a programming principle or rule-of-thumb, and often can not be cleanly represented as a re-usable library.
The seminal work on Design Patterns in OOP is “Design Patterns: Elements of Reusable Object-Oriented Software”, commonly named GOF. They divide their design patterns into three broad classes; creational, structural and behavioural.
Creational patterns decouples client code which requires new instances from the process of instantiating them. This allows the identical client code to be parametrised at compile-time or run-time with the object graph and even object types that will be instantiated. An algorithm that needs a new Vehicle could be parametrized to instantiate a Car in one case and a Lorry in another.
Structural patterns address how objects can be aggregated so as to present uniform interfaces but allow a rich variety in internal structure and behaviour. It abstracts the internals from this interface, allowing each to vary to some extent without the other needing to track. For example, the Component interface for an object-graph representing a GUI will provide methods such as draw() and handleClick(MouseEvent). A particular GUI will be built up from many kinds of components including containers, buttons and scroll bars. All of these form a part-whole hierarchy, with the dynamic behaviour exposed through this core interface. At any point, the toolkit of components can be extended by providing either a new atomic widget, or composing existing widgets and containers into a new re-usable component, and all without any changes to the Component interface.
Behavioural patterns address object communication, decoupling what to do from what to do it to. They fall into two broad groups, the first of which concentrates on abstracting the ‘what to do’ and the second upon ‘what to do it to’. In ‘what to do’ abstraction, variable behaviour is encapsulated in an interface, and clients can use one of several instantiations of this interface. For example, there may be several back-ends for logging, all of which implement the logging interface. Client code can request messages to be logged by sending requests to an object that implements this interface without needing to know if the messages will be sent to a file, a relational database or a GUI. In ‘what to do it to’ abstraction, items are presented to the client for processing without the client needing to know any of the details about the internal storage of those items. A client could loop over all Books in a Library, one after the other, without needing to know if the Book instances are stored in a List or a relational table.
A lot of these OO design patterns deal with noun-composition. Some creator patterns encapsulate a ‘create’ verb and of the behaviour patterns, strategy particularly stands out as being about abstracting over verbs. However, this and the other patterns with a verb-like feel to them are all about provisioning objects with behaviour. They are not design patterns for composing verbs into richer verbs, but rather about abstracting nouns over a choice of verbs.
I am not aware of a seminal work on design patterns in functional programming. This may represent cultural differences or perhaps deeper technical differences in the ease of expression of FP languages compared to OO languages. However, there are components that are continually re-discovered by FP communities. Perhaps the most common of these are structures intimately related to mathematics; equals, ordering, monoid, functor, monad. These common structures capture mathematical relationship, and like the encoding of 3 we saw earlier, capture it as a bundle of functions embodying the relationship, called a typeclass. These typeclasses look a lot like strategies, but the emphasis is different. To illustrate this we will work through two typeclasses; monoid and monad.
Monoid is some type, together with a zero value and an addition operator that comply to the monoid laws:
Any combination of type, zero and addition that conform to the monoid laws is a monoid. This includes , and .
Using a monoid typeclass, a variety of algorithms can be developed, abstracted away from how they combine items. As a trivial example, given a monoid typeclass for the items of a list, we can reduce that list to a single item like this:
We can build up monoids for more complex data types from those for simpler ones. Let’s consider the type Option that models an optional value:
If we have a monoid for the element type, we can derive a monoid for the corresponding Option type:
The details of how the typeclass is provided vary from language-to-language with both Haskell and Scala having dedicated syntax for declaring that functions with typeclass dependencies.
Where as the monoid typeclass abstracts combining values, the monad typeclass abstracts applying functions within some environment or container. The definition looks like this:
There are, of course, associated monad laws but I’m not going to show them here. The pure operation takes a raw value and projects it into the monad environment. The bind operation takes an environment, a function from elements to a new environment, and returns a new environment built by applying that function to the input environment. To make this more concrete, here’s a monad instance for lists:
This monad lets us abstract over functions that may return multiple results, letting us chain them together. There are many other monads for other datatypes, including ones that track probabilities, encapsulate mutable state, model transactions and so on. They are all built around capturing single steps that map single values into the monadic environment and then composing these.
These two typeclasses illustrate the way that common components of FP design enable ad-hoc composition of verbs. We saw how a list could be reduced down into a single item given a monoid encapsulating how to combine pairs of items. We where able to derive the monoid from the optional type by wrapping a monoid for the optional element type. With monads, we where able to encapsulate composing functions in a variety of environments. These and other common FP patterns are all about abstracting, composing and deriving verbs from other verbs.
The hinterland, or: No language is pure
In practice, all widely-used OO and FP languages include some non-OO features, wether it is the presence of first-class functions in Java 8 or primitive types in just about everything.
It is technically possible to write functional code in Java. You can introduce generic interfaces for functions and typeclasses, and manually pass around all the typeclass instances everywhere they are needed. However, this is painful. As soon as you compose typeclasses from one-another, the overhead of plumbing it manually goes through the roof. With good compiler support, it is free. This means that in practice, OO code tends to remain very noun-heavy, with verb-polymorphism being carefully factored out, and the verbs themselves being written monolithically rather than composed. If you have ever written a Comparator instance for a multi-field class that delegates on to other Comparator instances to compare individual fields, you will know what I mean. The corollary is that in FP, there’s a tendency to loose sight of the domain objects in all the verbage. The functions for manipulating data have a tendency to become so abstracted from what the data means in your application that it can be difficult to keep track of what is actually happening in your domain.
As always, sanity lies somewhere between these extremes. Real-world application domains are rich mixtures of nouns and verbs. Capturing these domains in a natural form means respecting this and not trying to shoe-horn everything into nouns-only or verbs-only representations, but picking languages and tools that allow the flexibility to mix & match as it makes sense.
A diversion: My potted recent history of trends in programming languages