3 Functional Programming

Functional programming is a style of writing software that can be practiced in many different programming languages. Some language features are necessary to fully practice, and reap the benefits of, functional programming. Certain concepts however can be applied in virtually any language.

There are languages that are considered functional because they give you the tools to program in a functional way comfortably, and in such a way that the end result performs well. Languages that make it impossible to program in any other way are called purely functional.

This chapter will go through the features and concepts that you will typically find in a functional programming language. There is a lot of non-obvious terminology associated with functional programming, which hampers its adoption. Hopefully after this chapter you will be able to walk into a room of functional enthusiasts confidently and hold your water.

3.1 What vs how

If a programming language is not “functional”, then what is it instead? Most non-functional languages, including object-oriented ones like Ruby, are imperative.

The word “imperative” comes from the Latin for “to command”, in grammar sentences like “Wait for me!”, or “Make me a sandwich!” are in the “imperative mood”. It’s what you use to tell someone what to do.

Similarly in imperative programming we tell the computer, step by step, what to do. Here are a few lines from a once popular Ruby library.

if names.empty?
  traverse_all_element(&block)
else
  name_set = {}
  names.each {|n| name_set[n] = true }
  traverse_some_element(name_set, &block)
end

Notice how it’s saying: “Computer, traverse those elements!”. It’s imperative code, commanding the computer step by step.

Functional programming is more about declaring what you want, and how it’s computed, and let the compiler and run-time system figure out the exact step by step instructions. It’s more like saying, “Computer, given these elements, please return me a list of the ones that have a name set, applying a certain operation to each along the way.” The fact that they need to be traversed one by one is a detail you don’t care about, as long as you get the list you asked for.

3.2 Functions as first class citizens

Let’s recap the definition we tentatively gave at the start of the book, “Functional programming is programming with values (and functions are values)”.

Values come in types, the ones we have seen so far are numbers and functions (lambdas). We have also touched upon the value nil, and you are probably familiar with booleans (true and false), characters and strings.

Apart from these atomic, scalar values, there are composed values like arrays, hashes and objects.

Different as all of these are, they do have some things in common

• they can be created by the running programming (as opposed to having to be specified beforehand)
• they can be passed into functions
• they can be returned by functions

When you can do these things with functions, as easily as you do with numbers or strings, then functions are first class citizens.

Not all programming languages are created equal. In many languages there is a strict border between “program code land” and “value land”. You define functions in code, and call them from other functions, passing values in and out. But it isn’t possible to pass functions around, or create new functions at run-time.

In languages with lambdas this distinction blurs. A lambda is effectively a little chunk of program code that has yet to be executed, and that behaves as any other value. Ruby lies in this camp.

Ruby does still make a distinction between lambdas and regular methods. The former are first-class citizens, the latter aren’t.

A language that takes it all the way is Javascript, all functions are as value-like as any other, whether declared with a name or anonymous. This is also how things work in purely functional languages like Haskell.

3.3 Higher Order Functions

We already met some higher order functions, functions that either accept or return other functions. When functions are first class citizens, it follows that you can have higher order functions.

Higher order functions come in various kinds. We already mentioned function decorators, which take a function and turn it into a slightly different function.

Another kind are those used for iterating over collections. If you have done Ruby programming at any length you have already used these, you just might not realize it.

[3, 9 ,7].map do |num|
  num * num
end
# => [9, 81, 49]

Can you spot the lambda in there? It’s ->(num) { num * num }.

The “block” syntax in Ruby is just a handy shorthand for the case where you want to pass a single lambda to a function. We will come across many more higher order functions as our story progresses.

3.4 Lack of mutable state

Back in maths class you might have come across equations like these,

x = 5
y = x + 2

But the following lines would presumably not get the approval of your maths teacher:

x = 5
x = x + 2

Either x equals 5, or it equals 7. It can’t be both! But in imperative languages, from C and C++ all the way to Ruby and Python, we have been writing such things in our code without blinking.

In functional programming this is a big no-no!

The effect is that x has a certain value at one point, and a different value at another. Any part of the program that has access to x can change it. When you read out the value of x, do you know (proverbially) who touched it? Be mindful of your code’s hygiene!

We don’t necessarily have to reassign a variable to change it. If the object it holds is mutable, we can simply change that.

In the olden days, back when forests were still enchanted and computer screens showed orange text on a black background, people would program with global variables and gotos. At the top of their programs they would declare a long list of all the variables that would be used throughout the program. Then the program began executing line by line, top to bottom, until an occasional goto would cause the execution to continue on some other line later or earlier in the program.

This lead to what is known as “spaghetti code”. A messy hodgepodge of control flow that was impossible to disentangle.

What makes this programming style so hard to reason about is that different parts of the program communicate by altering shared state. One part of the program will change some variables to influence what another part of the program does.

This is the danger of using mutable state, taken to its most extreme. But even in clean, object-oriented Ruby code we might have many micro-violations, small gourmet portions of hand made spaghetti that all add up until your code comes crashing down with indigestion.

Completely abandoning mutable state might seem an extreme stance to hold. The world changes constantly after all, isn’t it vital that your application can keep track of change? What about user input, network traffic, scheduled jobs?

Obviously we need to keep track of application state. What we try to avoid however, is changing things in place. Since people seem to be capable of writing complex applications in languages that don’t have the concept of changeable variables we will assume for now that this is not just crazy talk. Much of this book will be figuring out how to program given these constraints.

To recap, here are some of the things when it comes to programming “in the small” that from here on will be frowned upon,

array << :wen

array.concat([:lobsang, :sweeper])

str << "hello"

x += 1

str.upcase!

options[:verbose] = true

object.attribute = new_value

Purely functional languages do not allow mutable state. Once a value is set, it stays set. You can derive a new value from the old one, but you can’t change it in place. So these are all allowed,

array + [:lobsang, :sweeper]

str + "hello"

x + 1

str.upcase

options.merge(verbose: true)

Ruby’s strings deserve an honorable mention here. They behave more like string buffers in other languages, where you can append to, shorten or replace content inside the buffer. Some of the methods on String come in two variants, a regular one and a “destructive” variant that changes the string in place. They are called destructive because after they complete the original string value is gone. You can recognize the destructive versions because their names end in an exclamation mark, signaling like a warning flag their dangerous character. For example upcase!, downcase!, delete! and gsub!

3.5 Pure functions

Once we’ve decided to stick to immutable values, the concept of pure functions follows quite naturally. A function is pure when its output (return value) is completely determined by its inputs (arguments), and it doesn’t do anything “on the side” besides coming up with a return value.

For example ->(x,y) { x * y } is a pure function. If we call it with the arguments 3 and 4, it will always return 12. The only way we can get a different output is by giving different inputs. To contrast, take this function

x = 3
fn = ->(y) { x * y }

fn.(4)
# => 12

x = 5
fn.(4)
# => 20

Here we have executed fn.(4) twice, but we did not get the same result back. fn is clearly not a pure function.

Side effects

A function has side effects if it interacts in some way with the world outside the function. For example, apart from calculating its return value it could also write to some output to the screen.

fn = ->(x,y) do
  puts "#{x}, #{y}"
  x * y
end

We still get identical output for identical input, but there is also the side effect of writing to the screen. Similarly interacting with files, the network or connected devices are all considered side effects, and thus not allowed in pure functions.

There is another type of side effects, which comes from having mutable state. Take this function

suffixify = ->(str) { str << "icious" }

w = "awesome"
suffixify.(w)
# => "awesomeicious"
w
# => "awesomeicious"

Here again our function does more then is necessary to come up with its output. It also changes the string we pass to it. Perhaps this wasn’t even the programmer’s intention. Luckily making it pure again requires only a small change

suffixify = ->(str) { str + "icious" }

Where before we were changing an object, now we create a new object and return that, leaving the old one unchanged.

Here are some more examples of non-pure functions, can you say why they aren’t pure?.

counter = 0
->(x,y) { counter += 1 ; x * y }
->(x,y) { counter + x * y }
->(x) { x * readline.to_i }

Referential Transparency

The great thing with pure functions is that it doesn’t really matter whether we execute them once or a million times. It also doesn’t matter so much in what order we execute them. All that matters is that we can calculate the values we need from the values we have available by combining the right functions. We have the freedom to decide which intermediate calculations we do first. With side-effecting functions reordering the execution will almost certainly change how the program behaves.

Anywhere a pure function is used, we can replace the function call with its result, and the program still works the same as before. This property is called referential transparency. The function in itself is not so important. If we can get the same return value through any other means that’s fine as well, because the function doesn’t have side effects that we would skip.

So this is great, we can forego calling the function at all! Simply replace the function call with its return value. Or to phrase it in a less chicken-and-egg way, we only have to calculate the result once and can then reuse it everywhere. This pattern is called memoization.

3.6 Strict and Lazy Evaluation

Given a program that computes a certain result, a computer will have to evaluate this program, one way or another, so that in the end it finds the correct computed result.

There are several ways to go about this, but it’s likely something you never consciously thought about. All common imperative programming languages approach this the same way, including Ruby, so it likely just seems the logical thing to do.

The evaluation strategy of Ruby is called call-by-value, and it is considered a strict evaluation strategy. Let’s spell out exactly how that works.

Given this function call

def add_if(condition, list, v1, v2)
  if condition
    list + [v1]
  else
    list + [v2, v2]
  end
end

add_if(true, [], 7*7, 2**99 / 131)

Before entering add_if, Ruby will need the value of all the arguments. It will go over the argument list from left to right, evaluating each produce its value. When all the argument values have been computed, in this case true, [], 49 and 4838361069573394662201157272, the program enters add_if, checking condition and adding one of the two elements to the list.

The fact that all arguments are fully evaluated to values before calling the function makes this a strict evaluation strategy.

What is not so cool about this is that the value of the second expression 2**99 / 131 is actually never used. We have computed that large number, and then simply discarded it! Granted, arithmetic is pretty fast, but this could have been any kind of complex calculation taking forever to finish, all for nothing.

So is it possible to do it any other way? Turns out there is! We could substitute the arguments as they are right in the function body. This would yield something like this

if condition
  list + [7*7]
else
  list + [2**99 / 131, 2**99 / 131]
end

What we have accomplished now is non-strict evaluation. We have postponed the evaluation of the arguments until we actually need them. Now only one of the two expressions will actually be calculated. This is also called “call-by-need”. Only when we actually need the value of an expression before we can continue, we evaluate it.

Notice though that with the above substitution we risk calculating 2**99 / 131 twice. That certainly defeats the purpose. Languages with support for lazy evaluation will be smart about this, they will evaluate each expression only once, and share the result. This “calculate and remember” strategy is known as memoization.

Ruby’s evaluation strategy is strict, so we normally won’t be able to rely on laziness much. But there are some ways to trick ruby in postponing evaluation, so we have a kind of “optional laziness”. We’ll explore that later when we dive deep into what Ruby can and can’t do.

An important requirement for lazy evaluation is that the functions involved are pure. Take this example

add_if(true, [], increase_counter(foo), log_and_return(bar))

Here the two expressions that might or might not be evaluated are increase_counter(foo), which presumably changes the value of a counter, and log_and_return(bar), which appends something to a log file. In these cases we don’t call these methods just for their return values, but only for the side effects they cause. Having a system that decides for us if these need to be evaluated or not can really come back to bite us. If all functions involved are strict however, then it’s really not important if they are actually evaluated or not, so the system can optimize them away as it sees fit.

Laziness isn’t just about optimization though. A common pattern in languages with lazy evaluation is to construct infinite sequences, for instance the list of all prime numbers. Each element is only actually computed as it is used, so as long as you only end up needing a finite amount of them you’re all good. But the implementation of the algorithm doesn’t care. It just knows how to compute the next prime, whether you need a few, or a few million.

Ruby 2.0 added lazy enumerators, which provides similar functionality. We’ll talk about them later in the book.

3.7 Pros and Cons

Nouns vs Verbs

When I learned how to computer, we had a course called “Object Oriented Analysis”. We were taught to approach programming by creating diagrams of the various “things” that your program will need to deal with. It was called “modeling the domain”.

For instance, suppose you need to make a system for scheduling hospital visitor hours. The “things” in your domain would be the Hospital, Patients, Time Slots, Rooms, Doctors, etc. These relate to each other in certain ways. A hospital would be associated with one or more doctors, for instance.

Finally you added behavior to these “objects”. A patient can register, or pay. Perhaps a room can find a time slot in which it is free. (You end up making surreal statements about inanimate objects when modeling reality through the lens of Object Orientation.)

While this technique certainly has some merit, it also has a very big drawback. You only start thinking about what the system has to do until very late in the process. The reason is that the most prominent items in your modeling, classes and objects, all tend to be nouns. They are the things that make up this world, they are not what those things do.

Luckily times have changed, and smart people will tell you that it’s not about the objects themselves, it’s about how they interact. The dynamic behavior of a system is more important than its static structure.

Functional programming takes this one step further, by focusing on the verbs first. It allows the programmer to concisely declare what needs to happen. In the extreme this leads to what is called “point-free” style, in which functions are combined to form composed behavior, which is only at the end applied to actual values.

Ruby is an object-oriented programming language at heart, but that does not prevent you from doing some things in a functional way. It even has some nice features to help you along, giving you the best of both worlds.

Moving parts

To indicate that a software system is complex and difficult to manage, it is sometimes described as having “too many moving parts”. This metaphore is apt. When building software we layer and compose various abstractions. As more of these start interacting it becomes harder to keep a clear mental image how the system as a whole functions.

When parts start interacting the complexity does not go up linear, every part added has a multiplying effect on the number of relations that play a part in the final behavior.

When different parts of your program read and write to shared data you need to keep track of which part is altering what, at what time. The ordering in which things happen is vital, yet this ordering is never specified explicitly. It comes about from carefully constructing an algorithm.

Contrast this with programming in a functional style. When all your code is data-in data-out, dealing with immutable values, then every context, every function, is completely localized. You can forget about the rest of the system for a moment, just make sure that each function does what it is supposed to do, and then compose those into bigger, more complex functions.

I have found that every single time when my code is becoming complex and hard to reason about, taking a step back and rephrasing things in a functional way cleared up the confusing and led to more clear, simple and maintainable code.