Sunday, January 20, 2019

Syntax for composition of functions

Whenever I see function composition in a new context, I make sure to look up its precise definition.  There is a choice that must be made in the definition that has always seemed arbitrary to me...at least until now.  I no longer think the choice is completely arbitrary, and I have an opinion about which choice is better.

The choice that I am referring to is about the order in which the two functions being composed appear next to the composition operator (which I find is always an infix operator).  Typically when defining function composition, the names given to the two function being composed are f and g.  Since I am trying to contrast two possible orderings, I don't want the implied alphabetic ordering between f and g to introduce bias.  So instead, I will use the symbols # and & to denote the two functions being composed.

For a set S, suppose # : S -> S and & : S -> S are two unary functions from S to S (i.e. they are endofunctions).  Furthermore, let's have the function composition operator be implicit, which just means that #& is a composition of these two functions.  The ambiguity is this: does #& mean that # is evaluated first and then & or is it the other way around?  More specifically, is the composition operator defined so that #&(s) = &(#(s)) or is it defined so that #&(s) = #(&(s))?

In my experience with mathematics, I have seen it defined both ways.  If I try to mentally convert my experiences to statistics, the anecdotal conclusion I reach is that I have seen it defined each way about half the time.  That is one reason why the choice seemed arbitrary to me.  If there was an overall advantage with one definition, I would expect to see more of a consensus.

The other reason that this choice seemed arbitrary to me is that I could think of exactly one argument in favor of each definition, and these two arguments seemed about equally strong to me.

The advantage of #&(s) = &(#(s)) is that the order in which the functions are evaluated is the order in which they appear in the composition syntax.  Technically, this latter ordering depends on the implicit assumption that we are encountering this notation in the context of a natural language like English where the implied ordering is left-to-right (and then top-to-bottom).

On the other hand, the advantage of #&(s) = #(&(s)) is that when expanding the left side into the right side, the order in which the functions appear does not need to change.

So until recently, I assumed that the first definition was likely used more often in situations that involved more functions being composed while the second definition was used more in situations that involved more functions being decomposed in order to evaluate them both one at a time.

But now I think the first choice of #&(s) = &(#(s)) is superior.

To explain why, let's start with just a single function f.  It is very common to see the evaluation of f on an input x written as f(x).  Sometimes the input to f is not a single value like x but an expression like a + b as in f(a + b).  In this case, a + b is computed first then f is evaluated on the resulting value.  But this means that the computation is not occurring in order implied by English: the computation is happening from right-to-left, but we read this expression from left-to-right.

The placement of the function (or operator) f before its input x as in f(x) is called prefix notation.  If f appears after its input x as in (x)f then it is called postfix notation.  If we were using postfix notation for function application (and kept using an implicit infix notation for function composition), then the two potential definitions for function composition would be (s)#& = ((s)#)& and (s)#& = ((s)&)#.  Now (s)#& = ((s)#)& is the obvious winner.  It has both of the advantages that we pointed out before (namely, the functions appear in the "English" left-to-right order in which they are evaluated and the order of the functions is unchanged when decomposing the composition) leaving no advantages for the other definition.

With this in mind, I can rephrase the advantage that preserves the syntactic ordering when decomposing.  A single function is written with its input using prefix notation.  So to define function composition as #&(s) = #(&(s)) is to be more consistent with the prefix notation for function evaluation.  I have to admit, that is a very convincing reason to go with this definition.

When I design a software application, I try break up the problem into several loosely coupled pieces.  One reason for this is to help isolate any bad choices.  In this case, I am suggesting that using prefix notation for function evaluation was a bad choice.  As such, I don't want to feel obligated to perpetuate that bad choice into the definition of function composition as well.  Instead, I want to reconsider the advantages and disadvantages and give #&(s) = &(#(s)) a reasonable chance at being the chosen definition.

C# doesn't have a function composition operator.  It is easy to define an extension method to do this, but I haven't found it to be that useful.  Instead, I often use an extension method called Apply that acts as an infix operator taking a unary function on its right and the input to the unary function on its left.  If you squint so that Apply disappears, then this is a way to expression function application in C# using postfix notation.  Then instead of first composing two functions f and g and then evaluating the result on an input x, I use Apply twice by writing x.Apply(f).Apply(g).  Now the computation occurs in essentially the same ordering implicit in English, namely left-to-right.

This is very similar to the way pipelines are created in Unix.  As such, I find piped Unix commands natural to read (well...expect for the abundant use of acronyms).

Recall that Apply is a binary function and f and g are unary functions.  We can improve readability (by reducing the noise) with bit more work.  If we turn f and g in to extension methods (and capitalize them as is convention), then we can write x.F().G().  And now we can increases the expressiveness by passing in additional values to F and G.  This type of syntax is called method chaining and is used to create fluent interfaces.  In his book Functional Programming in C#, Enrico Buonanno recommends this style saying
The method chaining syntax...provides a more readable way of achieving function composition in C#.
[Section 5.1.2 on Page 104]
Notice that sometimes the method chaining is written with x, F, and G each on their own lines.  This is still consistent with the implicit ordering in English since we read top-to-bottom.

As a final example, consider the function composition operators $ and . in Haskell.  (These operators just vary in precedence.)  When writing code in Haskell that uses these operators, you will tend to write code that effectively executes in the "wrong" order, i.e. from right-to-left.  As an alternative, you can compose the functions in the opposite order using the >>> operator.

The ultimate goal here is to write readable code.  We often say things like "this code is readable" or "that code is not readable" as though readability is a binary condition.  In fact is in a continuum for each person and also varies between people.  What we all (well, many of us) have in common is fluency with a natural language like English that reads left-to-right and top-to-bottom.  By tapping into that common shared experience, we can design programming languages and write code that is more readable for all of us.

Saturday, January 19, 2019

Minimal and intuitive type parameter naming

I would like to suggest an alternative to the standard ways of naming type parameters when nothing is known about the types being identified.

In C#, type parameter names typically start with T and are written in PascalCase.  When nothing (or almost nothing) is known about the type identified by the type parameter, it is common to see the single letter T as the identifier.  When many type parameters show up and nothing is known about any of them, then I usually see one of two conventions for naming them.

One way is to stick with T as the first letter and simply append a number to distinguish it.  A good example of this is multi-parameter versions of Func.  The problem with this approach is that the initial T becomes noise.  When every type parameter in this densely packed space starts with T, this letter doesn't convey anything.  It is clear from context that we are dealing with type parameters, so the T becomes redundant information.  Syntactically, it is merely allowing the name to be a legal identifier; in this case, to start with a letter or underscore.  Removing each T results in a number, which is not a legal identifier.  The names for the variables of each type are equally bad.  In the Func example, they are named arg1, arg2, etc.  Another common naming convention for this is t1, t2, etc.

Another approach to this naming is to stick with single letters like T and then pick surrounding letters such as S, T, U, etc. or T, U, V, etc.  I like style better.  These single letter identifiers are getting closer to the essential need here, which is merely to distinguish themselves from each other.  The identifiers for the variables follow suit and are the lowercase equivalents.  Both this style and the previous one convey order: the previous one did so explicitly with numbers while this style does so more intuitively by using a subsequence of letter from the alphabet.  The downside with this convention though is that it can be difficult to remember where the sequence starts (is it at S or T?) as well as have a good intuition for how far along the sequence a particular letter is.

The approach that I prefer makes an additional improvement that removes the downsides of the previous approach.  Instead of starting with S or T, start with A.  If four type parameters are needed, then in this conversion, they would be A, B, C, and D.  Now suppose that you just glanced at the last type parameter without scanning though the whole list.  You would instantly know that there are four type parameters involved; no conscious mental effort is required.

Now that we have sufficiently defined these three type parameter naming conventions, let's give them identifiers of their own.  Let's call the first one the numeric convention, the second one the mid-alphabetic convention, and the last one the alphabetic convention.  (I just made these names up as I am writing this.  If these type parameter naming conventions have, well, conventional names, I would love to hear about that.)

Often there is one crucial difference among the type parameters: one is the return type and the rest are input types.  In the numeric convention, the return type is often called TResult.  In the other two conventions, I usually see the return type identified with R.  This leads to another advantage of the alphabetic convention over the mid-alphabetic convention.  If R is the return type, then there is some cognitive dissonance with seeing the inputs type names be letters that come after R in the alphabet.  Instead, when starting with A in the alphabetic convention, all of the input types names come before R in the alphabet (even in the case of 16 input type parameters that last name is the letter Q, which still leaves a gap of size one before R).

Here is an example of me standardizing a file to use the alphabetic type parameter naming convention.  In fact, I first encountered the alphabetic convention in that GitHub project, which is called language-ext.  The author Paul Louth has used multiple type parameter naming conventions while developing that project but currently prefers the alphabetic convention as well.

I am a strong advocate for the alphabetic convention over the other two.  It uses a minimal amount of characters to distinguish the types while also being intuitively clear by relaying on our deeply seeded memory of the alphabet.  I hope I see this convention used more often.