_{Photograph by Noel Feansderivative work: Snowmanradio, CC BY 2.0, via Wikimedia Commons}

The S-Combinator

Combinators are functional patterns that glue (AKA compose) together functions. These patterns promote single responsibility and decoupling. Today's story is the story of my journey into learning and using the S-Combinator in a functional code base. I'll be using pseudo-code to explain.

The problem I had to solve was to generate 2D thumbnails from a 3D volume. The 3D volume itself was made up of a three dimensional container of 2D images, so each 2D image could be found by it's axis and index. If you're familiar with medical imaging, this is a DICOM image.

Several functions were required to get this job done:

A function to get the number of images along an axis
A function to get the index of the image in the middle of an axis
A function to extract the image by index

The implementation details of each of these aren't important (they're also very specific to medical imaging). However, the interfaces are extremely important when it comes to gluing things together.

Pro-tip: Always design your interfaces first and keep them as simple and symmetrical as possible. It'll reveal patterns that you won't see if you do the implementation first.

The functional interfaces for this problem were defined as follows:

// Using lambda notation
let CountSlices = (axis: Axis) => (image: Image) => (count: uint)
let GetMidSliceIndex = (axis: Axis) => (image: Image) => (index: uint)
let Slice2D = (axis: Axis) => (index: uint) => (image: Image) 
  => (image: Image)

// Using object oriented notation
function uint CountSlices(Axis axis, Image image) {...}
function uint GetMidSliceIndex(Axis axis, Image image) {...}
function Image Slice2D(Axis axis, uint index, Image image) {...}

Looking at these functional interfaces a few things jumped out to me:

CountSlices and GetMidSliceIndex are tightly coupled and feed into Slice2D.
The input parameters are almost symmetrical - all requiring an Axis and an Image

Are there any other things that stand out for you?

Compose/Pipe

From my previous post, we discussed that the Compose and Pipe Combinators are used to glue successive functions together. In this case, CountSlices needs to be calculated before GetMidSliceIndex. Whenever I see the word before, it almost always refers to the Pipe Combinator. Using the Pipe Combinator, GetMidSliceIndex turned into the following composition:

let DivideBy = denominator => numerator => int(numerator) / denominator
let GetMidSliceIndex = axis => Pipe (CountSlices(axis)) (DivideBy(2))

// Another implementation
let GetMidSliceIndex = axis => image => int(CountSlices(axis)(image)) / 2

The Pipe Combinator returns a function that takes in an Image and passes it to the first function CountSlices axis and then it divides the result by 2. Whether or not one implementation is better than the other is up for debate, but in this case, it's an example of the Pipe Combinator in action.

Enter the S-Combinator

The S-Combinator is also known as the Substitution Combinator or Starling Combinator. As it's other name implies, The S-Combinator is used to substitute arguments in a function by computing them with other functions. This is really handy when one or more of your arguments depend on the value of another argument.

In this case, Slice2D depends on GetMidSliceIndex to compute the index. Both of these functions also have dependencies to the axis and image. There are several S-Combinators, but here are the two that I used:

// AKA the Chain Combinator
let S_ = f => g => x => f(g(x))(x)

// AKA the Converge Combinator
let S2 = f => g => h => x => f(g(x))(h(x))

The S_-Combinator (From now on referred to as the Chain Combinator) basically computes the first argument for the function f with g using the input argument x. It then applies x as the second argument.

The S2-Combinator (From now on referred to as the Converge Combinator) is almost the same except that it takes in a third function h to compute the second argument for f.

Chain Combinator in Practice

So how does this work in practice. Let's first consider the Chain Combinator. If we assume that GetMidSliceIndex already has it's axis applied, we essentially get a function with the signature (image: Image) => (index: uint). Using the Chain Combinator as a base, we can see the following:

let Chain = f => g => x => f(g(x))(x);

let CreateThumbnail = axis => image 
  => Chain(Slice2D(axis))(GetMidSliceIndex(axis))(image)

In the above example Slice2D(axis) represents f, GetMidSliceIndex(axis) represents g, and image represents x. With those in place, we can see that Chain applies image to GetMidSliceIndex(axis) and pass that into Slice2D as the second argument because axis is partially applied. Finally, image is then applied to Slice2D to create the thumbnail.

This was good, but I didn't like how axis had to be partially applied. If you're keen enough, you can see that the we end up with three functions here: Chain, Slice2D and GetMidSliceIndex. What's more coincidental is that the argument for Slice2D and GetMidSliceIndex are both axis. This matches the functional interface of the Converge Combinator! Coincidence? I think not!

Converge Combinator in Practice

Given the following:

Chain as f
Slice2D as g
GetMidSliceIndex as h
axis as x

the above code can be refactored to the following:

let Chain = f => g => x => f(g(x))(x);
let Converge = f => g => h => x => f(g(x))(h(x))

let CreateThumbnail = axis => image =>
  Converge(Chain)(Slice2D)(GetMidSliceIndex)(axis)(image)

The project I'm working on uses F#, so there's even more interesting things that can be done. Two things that F# will give us:

We can remove the brackets
Since image is an argument that gets applied, we can drop this argument as the result of Converge will return a function

The final implementation in F# is as follows:

let Pipe f g x = g(f x)
let Chain f g x = f(g x)(x)
let Converge f g h x = f(g x)(h x)
...
let DivideBy denominator numerator = int(numerator) / denominator
let GetMidSliceIndex axis = Pipe (CountSlices axis) (DivideBy 2)
let CreateThumbnail axis = Converge Chain Slice2D GetMidSliceIndex axis

Conclusions

So what are the pro's and con's of this? By having the individual functions fully unit tested and using commonly known functional patterns to compose this logic together, the compositions of these functions are guaranteed to work. This kind of programming produces extremely robust code with very little code. Less code usually leads to fewer bugs.

For this project, I'm the sole owner and supporter of it, but if this was a team effort, this code probably wouldn't fly. Is the code robust? Hell, yeah! Is the code maintainable? Yes, it is! Is the code readable? That depends. For a team of senior functional programmers, this would be fine, but if the team is made up of non-functional programmers, then this probably wouldn't work.

Combinator patterns exist in pretty much all the code we write. Recognizing these patterns are extremely useful and can help you design better interfaces. However, at the end of the day, if the code doesn't communicate well with your team, it doesn't matter how robust or well proven the patterns are because your team won't support it.

The Rampage