Using Functional Programming to Build a Better Breakfast Bagel.
With the recent buzz surrounding functional programming, I thought it would be good to elaborate on what functional programming means and what applying it can do for your code. Let's start by taking a look at some imperative style code for making breakfast.
Making Breakfast the Imperative Way
Let's talk about what you ate for breakfast this morning. You probably did some kind of preparation, even if you just threw a bagel in a toaster. That preparation probably occurred in a very specific sequence of steps: put the bagel in the toaster, turn the toaster on, wait for it to toast, take it out, spread cream cheese, etc.
If we coded this process, it might look like this:
toaster = power: false empty: true inside: null cook_breakfast = () -> bagel = get_bagel() toaster.inside = bagel toaster.empty = false toaster.power = true setTimeout(() -> toasted_bagel = toaster.inside toaster.inside = null toaster.empty = true toaster.power = false, 5000)
This is how an imperative language works. You tell the computer exactly how and when you want something done. There are a couple of things wrong with this code. It’s not modular; you can't break this into constituent parts to make it easier to understand. It is very tightly coupled with the interface to the toaster, so we need to know all about how a toaster works. It is also hard to change or maintain. The process needs to happen exactly as described in precisely the right order at precisely the right time. Object-oriented programming was invented to address some of these flaws.
Making Breakfast with Objects
It’s boring to eat the same bagel for breakfast every day right? So what do you do if you wanted to make an english muffin? As it happens, your kitchen came equipped with a robot chef. This robot chef comes with breakfast modules that let you customize each of the breakfast entrees it makes. The modules each come with and manage their own ingredients. Without the modules, the robot is fairly unintelligent. It knows the tasks it is capable of but not how to accomplish them. The modules provide that information. This is composition with objects. A robot chef is composed of the modules (objects) that provide breakfast recipes.
If we wanted to create our Robot Chef in code it might look like this:
class RobotChef constructor: (@modules) -> add_module: (name, module) -> @modules[name] = module remove_module: (module_name) -> delete @modules[name] make_breakfast: (name) -> @modules[name].cook # Simulate some breakfast functions that modules can use class Toasted constructor: (@thing) -> class Spreaded constructor: (@spread_on, @spreads...) -> class IngredientStash constructor: (@ingredients) -> get: (name) -> @ingredients.pop put: (name, ingredient) -> @ingredients[name] = ingredient
Our robot chef is composed of a hash of modules. We choose which one to use when we call the
cook method. This type of composition is useful because we don’t care what the internals of the module are. We only care that it responds to the API we require: the
cook method. It is an abstraction that allows us to reason about the robot chef without knowing about each module's structure.
One problem with the object composition approach is that there is not a good way to combine two breakfast modules together to create a new module. They are indivisible objects. This encourages code duplication. As an example, suppose you had two modules that made bagels. One adds cream cheese to the bagel, and the other adds jam. In code:
class BagelWithCheeseModule constructor: (ingredients) -> # IngredientStash does the bookkeeping for ingredients @ingredients = new IngredientStash(ingredients) cook: () -> bagel = @ingredients.get('bagel') cream_cheese = @ingredients.get('cream_cheese') toasted_bagel = new Toasted(bagel) new Spreaded(toasted_bagel, cream_cheese) class BagelWithJamModule constructor: (ingredients) -> @ingredients = new IngredientStash(ingredients) cook: () -> bagel = @ingredients.get('bagel') jam = @ingredients.get('jam') toasted_bagel = new Toasted(bagel) new Spreaded(toasted_bagel, jam)
The bagel toasting code is duplicated in both modules. One possible solution is to create a
BagelModule class and subclass that for each topping we need.
class BagelModule constructor: (ingredients) -> @ingredients = new IngredientStash(ingredients) cook: () -> bagel = @ingredients.get('bagel') new Toasted(bagel) class BagelWithJamModule extends BagelModule cook: () -> toasted_bagel = super jam = @ingredients.get('jam') new Spreaded(toasted_bagel, jam) class BagelWithCheeseModule extends BagelModule cook: () -> toasted_bagel = super cream_cheese = @ingredients.get('cream_cheese') new Spreaded(toasted_bagel, cream_cheese) class BagelWithCheeseAndJamModule extends BagelModule cook: () -> toasted_bagel = super cream_cheese = @ingredients.get('cream_cheese') jam = @ingredients.get('jam') new Spreaded(toasted_bagel, cream_cheese, jam)
While this does reduce the duplication, I am not satisfied with it as a solution. It encourages indirection through subclassing. By using the superclass's
cook method it moves that code, which is relevant to how we make our breakfast, to a place separate from where we use it. This means we need to hold both classes in our head to construct the mental model of how
BagelModule's descendents cook breakfast. This solution has also done nothing to allow us to compose our modules together to create new ones.
Breakfast, Made Horizontally
Previously we composed our breakfast modules vertically. We stacked abstractions (classes) on top of each other to come up with a final product. If we compose our breakfast modules horizontally, it might help us reduce some of the duplication and make it more understandable. Horizontal composition looks more like the composition involved in our
RobotChef class with respect to its contained modules.
The first thing I am going to do is redefine our
BreakfastModule class to take a list of instructions.
class Instruction constructor: (@fn) -> perform: (args...) -> @fn(args...) class BreakfastModule constructor: (@instructions) -> cook: (args...) -> instructions.reduce args, (memo, instruction) -> instruction.perform(memo...)
cook method is the interesting part. It performs each instruction in the list from left to right passing the return value of the left instruction into the arguments of the right instruction. This assumes that each instruction returns its values, wrapped in an array, to handle the splats. Next we will define two instructions to toast and spread things, and two utility instructions to help manipulate the
get_ingredient = (name) -> new Instruction (ingredientStash) -> [ingredientStash, ingredientStash.get(name)] put_ingredient = (name) -> new Instruction (ingredientStash, ingredient) -> ingredientStash.put(name, ingredient) [ingredientStash, ingredient] toast = new Instruction (ingredientStash, ingredient) -> [ingredientStash, new Toasted(ingredientStash.get(ingredient))] spread = (spreads) -> new Instruction (ingredientStash, spread_on) -> stashSpreads = spreads.map(ingredientStash.get) [ingredientStash, new Spreader(spread_on, stashSpreads...)]
The only thing that might strike you as odd is that we are explicitly passing our
ingredientStash around. We do this because our instructions cannot maintain any internal state of the ingredients, so we need to pass it as an argument. Note that creating instructions does not look much different than defining functions. We are also easily able to unit test the instructions because they are isolated. They do not rely on any external variables or state.
Now that we have our instructions let us put them to use!
BagelWithCheeseModule = new BreakfastModule([get_ingredient('bagel'), toast, spread('cream_cheese')]) MuffinWithJamModule = new BreakfastModule([get_ingredient('muffin'), toast, spread('jam')]) MuffinWithJamAndCheeseModule = new BreakfastModule([get_ingredient('muffin'), toast, spread('jam', 'cream_cheese')])
The power of this horizontal approach to composition is evident in the ease with which we were able to create four new modules and cook with them. Like before, this does not address the ability to compose modules together to create new ones. We can perform this composition fairly easily however with the addition of a helper function.
chainModules = (left, right) -> instruction = new Instruction (args...) -> left.cook(right.cook(args...)) new BreakfastModule([instruction])
This was not possible with the subclassing approach because our
cook methods did not take any arguments.
Now we can DRY out some of our module definitions:
ToastedBagelModule = new BreakfastModule([get_ingredient('bagel'), toast]) ToastedMuffinModule = new BreakfastModule([get_ingredient('muffin'), toast]) AddCheese = new BreakfastModule([spread('cream_cheese')]) AddJam = new BreakfastModule([spread('jam')]) AddCheeseAndJam = new BreakfastModule([spread('cream_cheese', 'jam')]) BagelWithCheeseModule = chainModules(ToastedBagelModule, AddCheese) MuffinWithJamModule = chainModules(ToastedMuffinModule, AddJam) MuffinWithCheeseAndJamModule = chainModules(ToastedMuffinModule, AddCheeseAndJam)
And make our breakfast:
BagelWithCheeseModule.cook(defaultIngredientStash) MuffinWithJamModule.cook(defaultIngredientStash) MuffinWithJamAndCheeseModule.cook(defaultIngredientStash)
There is clearly a lot of power in this approach. We can create new breakfast modules simply and easily. We can also individually test each one in isolation. There is one thing that still bothers me, though, which is that our instructions and our modules are separate concepts. This makes it awkward to compose modules even though it was simple to compose instructions. It is even more galling, because when you combine two instructions you get another instruction, so modules are really just one big instruction. In the next section we’ll look at how we can refactor this so that everything is actually a function, and composing functions is as easy as
Making Breakfast with Functions
If you look at the
Instruction class we used earlier, it is just a wrapper around a function. This will be our first point of refactoring. We can take that out so instructions are just functions. Our
cook method becomes:
cook: (args...) -> instructions.reduce args, (memo, instruction) -> instruction(memo...)
Next we will look at the
BreakfastModule class. What does it do? Other than the
cook method, It stores a list of instructions. We can extract the
cook method and pass the instructions as arguments:
cook: (instructions, args...) -> instructions.reduce args, (memo, instruction) -> instruction(memo...)
What does the
cook method do? It calls each instruction, passing the result of the previous instruction into the next instruction. Something like:
This looks similar to the way we were sequencing our instructions in the instructions array. We can actually get rid of the array and the cook method.
This is called function composition, and we can define a helper for it.
c = (left, right) -> (starting_arg) -> left(right(starting_arg)) # use like this c(f1, f2)('foo') == f1(f2('foo'))
Using this helper we remove the instructions array and the cook method. Instead of sequencing our instructions in an array to be chained together later, we will perform both steps at the same time like so:
c(instr_3, c(instr_2, instr_1))(some_args)
Generally when you see function composition defined, it is a function that takes a single argument and returns a single argument. So we are going to convert our instruction functions to take arrays instead of multiple arguments:
# Get an ingredient from the stash get_ingredient = (name) -> (args) -> [stash, _] = args [stash, stash[name].pop()] # Stash the incoming ingredient under the given name put_ingredient = (name) -> (args) -> [stash, ingredient] = args stash[name] = ingredient [stash, ingredient] # Toast an incoming ingredient toaster = (args) -> [stash, ingredient] = args [stash, new Toasted(ingredient)] # Spread any amount of spreads on the incoming ingredient, getting the spreads # from the stash. spreader = (spreads...) -> (args) -> [stash, ingredient] = args [stash, new Spreaded(ingredient, spreads.map((spread) -> stash[spread].pop())...)]
These four instructions are going to serve as our primitives that we chain together using function composition.
toast_ingredient = (ingredient) -> c(toaster, get_ingredient(ingredient)) toasted_bagel = c(put_ingredient('toasted_bagel'), toast_ingredient('bagel')) toasted_muffin = c(put_ingredient('toasted_muffin'), toast_ingredient('muffin')) toasted_bagel_with_cream_cheese = c(spreader('cream_cheese'), toasted_bagel) toasted_bagel_with_jam = c(spreader('jam'), toasted_bagel) toasted_muffin_with_cream_cheese_and_jam = c(spreader('jam', 'cream_cheese'), toasted_muffin)
Note that we previously applied our instruction sequence from left to right, while here we are going in the opposite direction to keep the first function we use and its arguments close together
Left to right:
Right to left:
This is solely a cosmetic difference, though, so we do not need to search too far to find the function that takes the starting arguments.
Now we just need some way to run these, and a default set of ingredients:
ingredients = cream_cheese: ['cream_cheese', 'cream_cheese', 'cream_cheese'] jam: ['jam', 'jam', 'jam'] bagel: ['bagel', 'bagel', 'bagel'] muffin: ['muffin', 'muffin', 'muffin'] cook = (recipe, initialStash) -> recipe(initialStash, null) cook(toasted_bagel, ingredients) cook(toasted_muffin, ingredients) cook(toasted_bagel_with_cream_cheese, ingredients) cook(toasted_bagel_with_jam, ingredients) cook(toasted_muffin_with_cream_cheese_and_jam, ingredients)
Bon Appetit! We now have a set of modules that we can compose ad infinitum to our heart's content. Each module is a self-contained and pure function. It does not operate on anything but its inputs. This makes it nice to unit-test because it will always return the same result given the same input. There is no implicit state or unknown mutations to worry about. This is a huge benefit on top of the already huge benefit of composability!
This article should serve as a good introduction to functional programming and the benefits it can bring you, but there is still a lot left to discuss. There is a strong grounding in formal theory behind functional programming that is interesting in its own right, but once grasped broadens our understanding of how we can combine functions together. Functors, monads, and arrows are techniques that help us simplify and abstract away common patterns such as our explicit state passing pattern above.
There are many more techniques, and each of them is worthy of their own article alone. I will be writing more about these concepts in the coming weeks, but I encourage you to learn about these on your own as well. The benefits are well worth it.
- Daniel Wilson is a Developer at MojoTech who writes an occasional series on programming philosophy.
Think MojoTech might be a good place for you? We're hiring!