This article reviews a program that implements a parallelized algorithm, using a functional programming style made possible by a fantastic new language named Elixir. Along the way I very briefly introduce Elixir, review the relevance of functional programming in modern computing, and explain what parallel programming is all about. There’s a lot of ground to cover, so let’s get started!

The program

This programming exercise is based on finding what I refer to as a wordset. A wordset is a list of words that, when written on separate lines, read the same both horizontally and vertically. For example:

You can run the program from a command prompt, such as Terminal in OS X. Type in a word and it will find all wordsets starting with that word. The program uses a list of words included with OS X, though a different word list could easily be used instead.

The source code, along with instructions on how to run the program, is available on GitHub at https://github.com/ijoshsmith/elixir_wordsets

Why Elixir?

Over the past few months I studied various functional programming languages, as well as the concurrency and parallel programming models their practitioners espouse. While certainly seeing value in each language I studied, only Elixir jumped out at me as elegant and expressive yet simple. It is a so-called impure functional language, meaning that it is built to support a functional programming style but also allows for symbols that can change value (a.k.a. variables).

Elixir code runs on top of Erlang’s virtual machine, commonly known as BEAM, just like Erlang code has for decades. Elixir code is compiled down to BEAM bytecode, just like Erlang code. Elixir is a modern language that enables today’s mainstream developers to harness the highly concurrent, fault-tolerant, distributed, bulletproof Erlang virtual machine that undergirds much of the telecommunication infrastructure on which our society depends.

After a few days of writing Elixir code, I was impressed. Once I saw firsthand how Elixir and the Erlang VM simplify multi-core computing, I was sold. I don’t expect to write Elixir code for a living any time soon, if ever, but the lessons I learn from the language and platform can be adopted in my daily software development practices. I wrote this article to share those lessons with others.

To learn more about Elixir visit its homepage:
http://elixir-lang.org

Watch José Valim, the creator of Elixir, discuss the history and future of the language:
https://www.youtube.com/watch?v=aZXc11eOEpI

Watch a thought-provoking talk by Dave Thomas about the mental shift Elixir enables:
https://www.youtube.com/watch?v=5hDVftaPQwY

For a more in-depth introduction to the Elixir way of programming, I highly recommend the ‘Programming Elixir’ book by Dave Thomas:
https://pragprog.com/book/elixir/programming-elixir

Functional programming

For many years mainstream software developers considered object-oriented programming an oddball curiosity that only the academic computer science crowd seemed to take seriously. Procedural programming was the mainstay of professional software development; where functions were functions, data were data, and real men wrote in assembler. 😉

Once computing hardware became powerful and cheap enough to support the extra overhead object-oriented software requires, that approach to programming began influencing the design of languages used by mainstream developers, such as C++ and Java. This initiated a cultural shift and the Object-Oriented Era began. All hail the Great Superclass in the sky!

The story is essentially the same with functional programming. Granted, there have been functional programming languages used in production systems for a long time, such as Erlang and Haskell, just as there were languages that supported object-orientation before it became mainstream. But generally speaking, functional programming has been an uncomfortably weird way of thinking about software development, something most developers have probably heard of but never actually tried, like pole dancing.

Now that the free lunch is over and we must write programs that can effectively put multiple CPU cores to work at the same time in order to leverage hardware advancements, the functional programming style is moving from the incubator to the real world. Functional programming guides us toward writing code that can flourish in a multi-core world.

Instead of hiding variables in objects, functional programming avoids mutable state as much as possible. Rather than modeling software as a community of law abiding citizens who interact via socially acceptable protocols in public, but whose private lives are full of sins and secrets, functional programming is all about setting up pipelines that transform data from one shape to another. The focus shifts away from using objects to model a problem domain, and toward setting up data transformation pipelines. The developer’s time is not spent writing a detailed list of steps needed to make something happen; it’s spent describing at a high level how that thing should happen and letting the runtime worry about the nuts and bolts.

If you find this intriguing (I sure do!) be sure to watch the presentation I mentioned above by Dave Thomas.

Parallel programming

Now we’re getting into some really exotic and exciting territory. I first learned about parallel programming when studying General Purpose GPU programming, also known as GPGPU, while doing some CUDA programming. This article does not cover how to write code that runs on a graphics processing unit (GPU), though it’s a very interesting topic worth investigating.

Much of the parallel programming literature on the Web is either for computer scientists doing academic research, or it’s about using a GPU to crunch a ton of numbers at the same time for things like physics simulations and artificial intelligence. Very, very heady stuff. But don’t let the extreme nerd factor scare you off!

At it’s heart, parallel programming is just about doing a lot of stuff at the same time by running your code on multiple processor cores. The more work that can be done at the same time, the faster the overall task will complete (in theory). Not every task lends itself to being parallelized, so it’s not a silver bullet to solve all of your performance woes. Many people refer to problems that can and should be parallelized as “embarrassingly parallel.” I’m not sure what there is to be embarrassed about, but that’s the expression.

Functional and parallel programming are BFF’s

Functional programming and parallel programming go together like peanut butter and jelly. Mutable state is concurrent software’s kryptonite. If multiple instances of your code are running at the same time on several of a CPU’s cores, any changes made to shared memory must be done with extreme care and caution. Ideally you wouldn’t do it at all!

Many of today’s most popular languages and platforms equip developers with hardly more than threads and locks to cope with multi-core computing. That’s like giving someone a musket and bayonet before parachuting them into a modern battlefield. Functional languages encourage immutability and, in the case of Elixir, provide a battle-tested virtual machine whose concurrency model effortlessly scales across cores and machines.

The parallelized algorithm

I’m not going to walk through every line of code in the Elixir program that I wrote. If you want to see the whole thing, it’s on GitHub here. Instead, let’s focus on the most interesting part: the parallelized algorithm that finds all wordsets beginning with the same word. That code is in the Engine module, which you can see below or view in GitHub here.

The search function on line 8 is passed three parameters:

• word – the word for which wordsets are found
• find_words – a function that the engine calls to get all available words of a certain length that have a specified prefix
• publish – a function that the engine calls when it finds a complete wordset that should be remembered for later

By Elixir convention, the search function has a helper function named do_search. It might look as if there are two do_search functions, on lines 11 and 15, but in Elixir one function can have multiple “heads” that specify different parameter states and conditions. The Erlang virtual machine evaluates these function heads at run-time to determine which one to invoke based on the parameters it will pass. In this example, the function on line 11 is called only if the number of strings in the words list is equal to the size parameter, which means the wordset is complete. The function on line 15 is called when the wordset is missing at least one word. And that’s where the magic happens.

Let’s review that function line by line. Here it is again, for quick reference:

Line 15: The parameters are the same as we saw for the search function above, but there is also a size parameter now. That represents the number of words in a complete wordset.

Line 16: This is called a guard clause. It contains conditions that must be true at run-time for this function to be called. In this case, it expresses that this function is called when a complete wordset is not yet available to publish.

Line 17: Call the make_prefix function to determine the sequence of letters with which the next word in the wordset must start.

Line 18: Call the find_words closure (i.e. function) to get a list of all available words that start with the prefix and are the right length for the wordset being built.

Line 19: Use the |> pipe operator to pass the word list retrieved on line 18 into a utility function I wrote in an EnumEx module called to_lists, which splits the list into N sub-lists of equal size. This enables me to break up the list of words into as many sub-lists as my computer has available processors. Note that the @sublist_count module attribute is used to determine how many sub-lists to create. I set that attribute to the number of “logical processors” available on the host computer, as reported by the Erlang runtime:

Line 20: This is where the magic happens! Pipe the list of sub-lists of words into the Parallel module’s each function, which is a simple utility function I wrote based on some code in the ‘Programming Elixir’ book by Dave Thomas. The standard Enum.each in Elixir executes a function for every item in a collection, one at a time. My Parallel.each executes a function for every item in a collection at the same time, by farming the calls out to the CPU’s available processors. The function call on line 20 does not complete until all of the parallel function calls it spawns off are complete.

Line 21: Get ready to pass the current sub-list of words through a pipeline…

Line 22: Filter out the words in the sub-list that cannot possibly be part of a valid wordset (refer to the “adaptive tail-sniffing optimization” area of Engine.ex to see how that works).

Line 23: Recurse into another do_search function call but this time put the current word from the sub-list into the words list. This is how the algorithm progresses through the available words. The &1 symbol refers to the current word, which is the first parameter of the function called by Enum.each. This is standard Elixir syntax.

Line 24: The end of the closure passed into Parallel.each on line 20.

Line 25: The end of the do_search function.

Parting thoughts

Regardless of whatever languages and platforms you might currently identify with, or are paid to write software for, it’s important to investigate and learn from what other technologies have to offer. The overall shape of software development’s future is the same for all of us, whether we write mobile apps or Web sites or desktop programs, etc. We must learn to embrace and utilize multi-core processors. Many of our beloved technologies, and the mindsets they engender, are simply insufficient for what’s coming next. I hope that this brief excursion into functional and parallel programming has helped sparked an interest in preparing yourself for the future of software development. Or, at least I hope you liked the Simpsons pictures!