Approach Bash Like a Developer - Part 36 - Functional Programming
This is part 36 and the last of a series on how to approach bash programming in a way that’s safer and more structured than your basic script.
See part 1 if you want to catch the series from the start.
Last time, we discussed recursion and memoization. This time, let’s talk about functional programming, or fp.
Functional programming is a philosophy that centers around immutability, functions as first-class entities, lack of side effects and deterministic results for given inputs to functions. Long story short, it’s way more than I’m ready to explore in a single short blog post, especially with a language like bash.
If you want to learn a bit more about functional principles, here’s a good blog entry on the basics.
So I’ll call this “light” functional programming in bash. If you’re interested in something heavier in bash, you can do a google search which will turn up some much more fleshed-out functional bash libraries.
That said, there are a few tools which are popularly borrowed from fp by non-functional languages. In particular, most languages implement the following list-oriented functions:
map - iterate over an array of items, applying a unary function to each item and returning the results in a new array
filter - a.k.a. select, iterate over an array, applying a unary function, returning items for which the function returns true in a new array
reduce - a.k.a. fold, iterate over an array of items, applying a binary function to an accumulator and each term, returning the result from the accumulator
Let’s learn a little bit about how we might implement these ourselves.
There are two ways we could approach the input to map. We could either accept an array or operate on a stream on stdin.
Ideally, we’d be able to do both, but for our purposes I’m going to choose the stream method so we can easily pipeline functions together, which is a hallmark of these tools.
Here we’re feeding some items to the uppercase function we’ve created for this purpose. The only argument that map requires is the name of the function that it will apply to the terms. It takes its input from the pipeline. In this case, that’s two strings.
Since we’re dealing with a pipeline, the result has to be on stdout. We’re capturing it with command substitution here so we can validate it against the expected result.
Fortunately, bash makes this easy. We’ve already seen the streaming read pattern in a number of my earlier posts. The while loop continues line by line so long as there is input to be had.
Each time, map applies whatever function was requested to the current argument. Even though the function to apply is provided as a string, bash expands the argument before attempting to run the command. No eval nor other magic is required.
As it so happens, since function names are strings and bash makes strings and variable expansions first-class citizens, by extension it makes functions first-class citizens. They can easily be stored in variables and invoked without a lot of extra syntax. Whod’ve thunk that bash is so forward-looking when it comes to fp?
Map with a Lambda
Anonymous functions, or “lambdas”, are another typical feature of functional programming. Lambdas are functions which don’t have a name assigned to them. They are typically passed as arguments to other functions.
Most languages allow full-featured functions as lambdas, although others only allow limited expressions. We’ll be doing a little bit of both, but I’ll call them expressions because that’s what they’ll be in bash. Don’t worry though, you can actually have full-fledged functions in the bargain because of bash’s command substitution capability.
We’ll start with just a lambda expression which evaluates to a string.
We’re reproducing the same test case as the uppercase one, just with a lambda expression this time. We’ll evaluate the lambda as a string expression and echo it on stdout.
Here we’ve just added the test for $ in the function string. If it’s not supplied, we do the same as before. Any expression which is a lambda will need to contain a $ somewhere, as we’ll see.
If it is present, we instead turn the read argument into the
positional argument $1 with
set --. Then we evaluate the function
string, and add an echo to put the result on stdout.
An expression is great, but if we want the full capability of a function, we’ll need something else. Fortunately, bash provides a means for evaluating a command in a string context…command substitution.
This test passes with our existing implementation. Notice that the expression has a dollar-sign leading it off.
In addition, since the command substitution takes place in a subshell, you can do things like set shell settings or change variables such as IFS without having to reset them, since they won’t affect the parent shell. That can make lambda expressions shorter and easier to use instead of full function definitions.
Finally, let’s look at a mathematical expression.
This also passes since arithmetic expansion is another form of string expression. Notice again it also starts with a $, so we’re covered with the difference between a function name and lambda.
map is the most straightforward of the three. Let’s look at filter next.
filter takes a boolean function and returns the items of the input array for which the function returns true.
Here we define a test for even numbers, then employ filter with it on a few integers, expecting the evens back.
Much the same as map, we invoke the function with the argument, only this time if it results in true, then we echo the argument on stdout.
Here’s a test for a lambda expression.
Not much to explain here. We’ve just changed the eval from map to evaluate the function then use the result to decide to echo the argument.
Last, let’s do reduce.
Reduce is an accumulation function. It takes an initial value for an accumulator, then iterates over an array. It takes a binary (two-argument) function and applies it to each array item along with the current value of the accumulator, accumulator first.
A simple example is string concatenation.
The accumulator needs an initializer, as it isn’t normally part of the sequence. It’s typically initialized to what’s considered an identity value for the kind of operation the function represesents. For things like multiplication, that’s the number 1. For addition, it’s the number 0.
This is a bit different because we’re only returning one value. Instead of echoing each time through the loop, we capture the result in the accumulator and feed it to the function once more. There are more efficient ways to do this, but we’re going for clarity here.
Alternatively, you can leave out an initial value for the accumulator, in which case the function can take the first element of the array as its initial value. We’ll get to that next.
Nothing surprising here, just the same test minus the initializer.
For our last trick, we’ll use a lambda.
One test for each initializer style.
I think I’ll leave this last analysis up to you. If you’ve made it this far through the entire series, you’re certainly up to it by now.
Congratulations, you’ve approached bash like a developer. Happy bashing!