February 18, 2017

Functional Programming and Software Design

So I read John Hughes' paper "Why Functional Programming Matters" and his argument really resonated with me.

In my view, software developers are problem solvers. When I design a solution, I first try to understand the problem as best as possible. I then attempt to split it into smaller subproblems, which I can solve independently, then put the partial solutions back together to form a complete one. Often I do not get it right the first time, so I may have to do several rounds of adjustment.

For example, I want to write my blog in markdown and render it as a static website. The blog consists of posts and static pages, an RSS feed, an archive page and a tag list. These components can be rendered by extracting information from markdown files. The different renderers can be implemented as individual modules. Putting them together creates a static site compiler.

This heuristic of decomposing and recombining works well for most non-trivial problems we solve with software. It naturally leads to modularization, which is the basis for effective cooperation in software development.

How we can decompose a problem, however, depends on the available options for recombining partial solutions. How we can modularize depends on the ways we have to put the modules back together. Within an application, the ways to recombine, and so the possibilities to decompose depend on the programming language.

This is where Hughes makes his argument for functional languages: they offer two additional ways to easily glue modules together. These are higher-order functions and lazy evaluation.

Higher-Order Functions

Higher-order functions are functions that take other functions as arguments. We can use them to glue together a general function (e.g. for recursion over a list) and some problem-specific functions. Amazingly, this obviates a number of object-oriented design patterns, such as Command, Strategy, Factory or Template Method.

Let's look at an example: we use Strategy to modify behavior at runtime. Say we want to send notifications to customers, either via email or SMS. In Java, we can implement a class NotificationSender:

public class NotificationSender {

   private NotificationTransport notificationTransport;

   public NotificationSender(NotificationTransport notificationTransport) {
      this.notificationTransport = notificationTransport;

   // ...

   public void sendNotification(CustomerId customerId) {
      Notification notification = createNotification(customerId);
      notificationTransport.send(customerId, notification);

    // ...

NotificationSender delegates the actual transport to a NotificationTransport, which is just an interface:

interface NotificationTransport {

    void send(CustomerId customerId, Notification notification);


We then can implement this interface as EmailNotificationTransport and SmsNotificationTransport. The client class NotificationSender never has to know about the actual implementation.

We need all this scaffolding, because it enables us to pass different implementations of the NotificationTransport::send method around in an object. In a functional language, we can pass functions around directly. In Clojure we can write the following higher-order function:

(defn send-notification [transport-fn customer-id]
  (let [notification (create-notification)]
    (transport-fn customer-id notification)))

send-notification simply receives a transport function, not knowing whether it is one for sending email or SMS. We can also partially apply it to that transport function, to keep configuration of transport and actual sending separate:

(let [notify (partial send-notification send-sms)]
  (notify "123"))

partial is just another higher-order function, which in this case takes send-notification and the transport function send-sms and returns a new function, which takes the remaining customer-id parameter and then calls send-notification.

Lazy Evaluation

Lazy evaluation means that calculating a result is deferred to the moment it is needed, potentially never. In Hughes' words, lazy evaluation

[...] makes it practical to modularize a program as a generator that constructs a large number of possible answers, and a selector that chooses the appropriate one.

This form of decomposition is rarely practical in an object-oriented language. I have seen it used in the context of ReactiveX and had fun with it using the Java 8 Streams API, but in functional languages it comes more natural.

Let me give another example. FizzBuzz is a short kata where we want to count from 1 to 100, but we will call all multiples of 3 fizz and all multiples of 5 buzz. In Clojure we can implement this using lazy sequences:

(defn fizz-buzz [n]
  (let [fizzes     (cycle ["" "" "fizz"])
        buzzes     (cycle ["" "" "" "" "buzz"])
        fizzbuzzes (map str fizzes buzzes)
        numbers    (map (comp str inc) (range))
        select     (fn [n f] (if (empty? f) n f))]
    (take n (map select numbers fizzbuzzes))))

Here, fizzes and buzzes are sequences which contain "fizz" in every third and "buzz" in every fifth position respectively, and otherwise consist of empty strings. They are combined using string concatenation to another sequence fizzbuzzes. Note that at the time of declaration, not a single element is concatenated or evaluated. Another lazy sequence of numbers contains natural numbers as strings.

The select function takes an element of numbers and an element of fizzbuzzes. If the latter is an empty string, it returns the former, otherwise the fizzbuzzes element, which has to be either "fizz", "buzz" or even "fizzbuzz". We use select to combine fizzbuzzes and numbers into a single lazy sequence. Still, not one element has been evaluated.

We then take the first n elements from the resulting fizzbuzz sequence, and only now are elements of all the previously declared lazy sequences calculated.

Mapping this to Hughes explanation, fizzbuzzes and numbers are generators, select is a selector, picking the right solution from the generated ones, and take acts as a terminator, limiting the number of evaluated fizzbuzz values to n. We now can treat generation of candidate solutions, the decision problem of picking the right solution and the termination of the program as separate concerns.

What about the new functional features of Java 8?

It is possible in Java 8 to use lambdas to simplify some implementations of the Strategy pattern. And the Stream API does come with some generator functions. The point here is not that you can't have higher-order functions or lazy evaluation in an object-oriented language like Java. After all, Clojure is written in Java, so it is clearly possible. The point is, that in a functional language, higher order functions and lazy evaluation come naturally and are easy to use. They are viable design options.

Tags: Design, Clojure