Functional programming has been around for a while. McCarthy envisioned LISP in the 1950’s, but you could even argue that the Lambda Calculus, a mathematical device to reason about computation that predates LISP by a few decades, was the first functional programming language.
Despite it’s ripe, old age, FP isn’t planning to leave us any time soon. Scala, F#, and Clojure are all functional languages that appeared roughly in the last decade. All of these “new” languages are still gaining followers. The functional paradigm seems more alive than ever.
There are good reasons for this. We live in a world of multicores and big data, a time of massively concurrent, distributed systems. Coordinating concurrent processes is hard, but functional programming can make it a bit easier.
Working with immutable data is a requirement for functional programming. This poses some challenges, but it provides new opportunities as well. The price of memory and storage is at an all-time low and, once you start to see the benefit of immutability, in-place editing of data seem like an optimization from an age long past.
As Rubyists, what do we make of this? Do we jump ship and start learning Haskell or Clojure instead? I don’t think that’s necessary, but it’s still a great idea. Spend some time with a functional language until things start to “click”, and you are bound to bring some interesting ideas back home to Rubyland. You don’t need a functional language to program in a functional style, nor do you need to be a purist or a pedant to reap the benefits.
Values and Functions
In object orientated programming, an object encapsulates state. It groups data fields, which Ruby calls instance variables, and methods. Only an object’s methods can directly access and alter its fields. Object orientation hides state in objects, so objects can guarantee internal consistency. It also ties behavior to state, in order to hide implementation details.
In functional programming values and functions are clearly separated. These form two distinct aspects, each with their own constraints and properties, and we can take lessons from both.
Values are immutable bits of data. Once a value exists, everything about it is known and constant. Values can be atomic, like the number 7, or composed, like a list with the location of every item in a game. We can never change a value once it is created, but we can derive new values from those that already exist. Say you want to move a game item. You are not allowed to take the item in the original list and update its location, but you can derive a new list from the old one, where one element has a new location.
Values or Variables
Have you ever tried to explain “a variable” to a beginner? For programmers, it’s so obvious, but explaining it in simple terms can be tricky. Let’s give it a try
A variable is when you give something a name.
That’s a good start, and in “purely functional” languages without mutability, like Haskell we could end there. But for Ruby, that’s not good enough. Let’s try again.
A variable is a box, the box has a name. You use the name to refer to the thing in the box. The box can contain different things at different times.
That’s more accurate, but it’s lot less intuitive. We need to keep in mind that there’s a level of indirection: the box, and its contents. But if we agree that we never change what’s inside a box, then the box disappears, and we can treat the name as referring to the contents. This greatly simplifies the mental model of how your program works.
Objects hide their state, so they can guarantee no one messes things up. Values can always be shared, so encapsulation is not such a concern in functional programming.
Building objects that are values is something you can start doing today. It can be as simple as not creating setters, and returning a new updated instance instead of updating existing instance variables in place.
Instead of doing those things manually, I’ll demonstrate some handy gems in the examples that follow. The first one is Anima. Think of it as Ruby’s
Struct class, but for values. It creates a hash-based constructor, read-only attribute methods, and equality tests (
class Ukulele include Anima.new(:color, :tuning) end u1 = Ukulele.new(color: 'green', tuning: [:G, :C, :E, :A]) u2 = Ukulele.new(color: 'green', tuning: [:G, :C, :E, :A]) u1 == u2 # => true
Your value object isn’t worth much yet, however, because the array it uses is still mutable.
u.tuning << :F u # => #<Ukulele color="green" tuning=[:G, :C, :E, :A, :F]>
To make sure the objects you create are truly immutable, including any components, Adamantium can be used.
class Ukulele include Anima.new(:color, :tuning) include Adamantium end u.tuning = :F # ~> -:6:in `=': can't modify frozen Array (RuntimeError)
To be able to tune your ukulele, you can write a method that derives a new ukulele from the old one. This may seem weird, changing the tuning doesn’t give you a second ukulele in the real world. However, when you think of values as facts bound to a certain point in time, then it starts to makes sense. We can’t go back and change the past. In a sense, the ukulele I’m holding now is a different one than before. It has to be, its tuning is different, so they are distinguishable.
class Ukulele def tune(string, note) self.class.new( color: color, tuning: tuning.take(string) + [note] + tuning.drop(string+1) ) end end u = Ukulele.new(tuning: [:G, :C, :E, :A]) u.tune(0, :F) # => #<Ukulele tuning=[:F, :C, :E, :A]> u # => #<Ukulele tuning=[:G, :C, :E, :A]>
Having to repeat the fields that don’t change gets repetitive, so Anima::Update can help you there.
class Ukulele include Anima::Update def tune(string, note) update( tuning: tuning.take(string) + [note] + tuning.drop(string+1) ) end end
An interesting side effect of immutable objects is that the result of method calls can be cached safely. This is a technique known as memoization and is built-in to Adamantium.
class Ukulele def snares tuning.count end memoize :snares end
Adamantium will also freeze the memoized value, just like it does with instance variables. By default, it deep freezes nested structures. You can tell it to only freeze the outer object, or to memoize a method without freezing its return value. The README has good info.
Functional Data Structures
A downside of this approach is that, for each “change”, a lot of data needs to be copied. This becomes a real problem when dealing with large collections. Imagine an immutable array with a million entries. To add or remove a single element, the whole thing needs to be duplicated first. This led to the idea of Functional Data Structures. These behave like values, but through a technique called structural sharing they minimize the amount of data that needs to be copied, saving memory as well as CPU cycles.
To understand the concept think of a linked list. Adding an element to the front of the list does not invalidate the original, both lists simply share the same “tail”. Popping the “head” off the list works the same way.
The same concept can be used with tree structures, reusing large parts, and only changing the path from the altered node to the root. This is how complex random-access data types, like sets and vectors, can be implemented. A type of tree structure that has particularly attractive properties is the “Hash Array Mapped Trie”, also known as an “Ideal Hash Tree”. The Hamster gem has implementations of vectors and sets based on Hash Array Mapped Tries, and several other functional data structures.
With that you should have quite a toolbox to start programming with values. In the next article in this series we’ll put the F in FP by exploring pure functions.