What is Generic Programming?

Over the course of my career I have strived to write reusable code, always looking for more general patterns and trying to refactor code to more flexible more generic versions sometimes with mixed success.  Lately it has become something of an obsession of mine in that I both try to employ it and have been endeavoring to learn more about it, what it really is, and how to do it right, as I have previously pondered I believe there is a complexity cost with increased reuse.  Over the last few years, which I have been programming in Java, generics has become a central tool in achieving reuse.  So such a concept comes to mind but it is just one idea in a larger framework of ideas on generic programming.

There is a fair amount of research and discussion of the ideas pertaining to generic programming, the title of this post is taken directly from a paper on the topic, which perhaps not so coincidently was presented at the same OOPSLA (2005) as the paper on Software Reuse and Entropy that I previously discussed.  It just seems like every idea I explore is super-interrelated to everything else and this post will be no exception, I can conceptually connect these two papers using a Kevin Bacon like approach using just two other research papers, ideas I have for other posts.  I will try to keep this one as focused as possible.  Also the referenced paper is, like the Software Framework paper, very math heavy but different math, Category Theory,Order Theory, Universal Algebra, etc. This post will focus on more high level concepts and not the details of math that I wish I could claim that I fully understand.

So back to our question, what is generic programming?   For me it is about reuse, and while the information entropy approach to understanding reuse was about reuse from perspective of measure and the reuse (measurable) variation on different domains, I feel that the generic programming concept is about the structure of reuse and how it is implemented in various programming paradigms but the concept itself transcends language specific interpretations and implementations.

As you can tell I am not sure how to exactly answer this question so I will defer to the experts.

"What is generic programming?" in part outlines the paradigmatic distinctions between mainstream OO languages (Java Generics, C++ with STL) and Functional languages (Haskel, Scheme):

As for most programming paradigms, there are several definitions of generic programming in use. In the simplest view generic programming is equated to a set of language mechanisms for implementing type-safe polymorphic containers, such as List<T> in Java. The notion of generic programming that motivated the design of the Standard Template Library (STL) advocates a broader definition: a programming paradigm for designing and developing reusable and efficient collections of algorithms. The functional programming community uses the term as a synonym for polytypic and type-indexed programming, which involves designing functions that operate on data-types having certain algebraic structures.

In "Generic Programming" written in 1988 by David A. Musser and Alexander A. Stepanov use Ada and Scheme and describe generic programming as:

By generic programming, the definition of algorithms and data structures at an abstract or generic level, thereby accomplishing many related programming tasks simultaneously.  The central notion is that of generic algorithms, which are parameterized procedural schemata that are completely independent of the underlying data representation and are derived from concrete efficient algorithms.

...

A discipline that consists of the gradual lifting of concrete algorithms abstracting over details, while retaining the algorithm semantics and efficiency.

That last sentence has a very Agile/Refactoring feel to it.

Ralf Hinze in "Generic Programs and Proofs" describes it as: 

A generic program is one that the programmer writes once, but which works over many different data types.

...

Broadly speaking, generic programming aims at relieving the programmer from repeatedly writing functions of similar functionality for different user-defined data types. A generic function such as a pretty printer or a parser is written once and for all times; its specialization to different instances of data types happens without further effort from the user. This way generic programming greatly simplifies the construction and maintenance of software systems as it automatically adapts functions to changes in the representation of data.

...

So, at first sight, generic programming appears to add an extra level of complication and abstraction to programming. However, I claim that generic programming is in many cases actually simpler than conventional programming.  The fundamental reason is that genericity gives you "a lot of things for free" ...

This last statement resonates with me as it parallels my thoughts on the desirability of using software frameworks and I feel that I continuously have this conversation (argument) with junior level programmers and also senior level cargo cult coders who don’t get it.

Design Patterns are a common generic concept in mainstream programming.  It turns out that a number of design patterns can be described in the framework laid out by these papers and a number of papers do exactly that including "Design Patterns as Higher-Order Datatype-Generic Programs " part of extensive research on the topic by Jeremy Gibbons:

Design patterns, as the subtitle of the seminal book has it, are ‘elements of reusable object-oriented software’. However, within the confines of existing mainstream programming languages, these supposedly reusable elements can only be expressed extra-linguistically: as prose, pictures, and prototypes. We believe that this is not inherent in the patterns themselves, but  evidence of a lack of expressivity in the languages of today. We expect that, in the languages of the future, the code parts of design patterns will be expressible as directly-reusable library components. The benefits will be considerable: patterns may then be reasoned about, typechecked, applied and reused, just as any other abstractions can. Indeed, we claim that the languages of tomorrow will suffice; the future is not far away. All that is needed, in addition to what is provided by essentially every programming language, are higher-order (parametrization by code) and datatype-generic (parametrization by type constructor) features. Higher-order constructs have been available for decades in functional programming languages such as ML and Haskell. Datatype genericity can be simulated in existing programming languages [2], but we already have significant experience with robust prototypes of languages that support it natively [2]. We argue our case by capturing as higher-order datatypegeneric programs a small subset ORIGAMI of the Gang of Four (GOF) patterns. (For the sake of rhetorical style, we equate ‘GOF patterns’ with ‘design patterns’.) These programs are parametrized along three dimensions: by the shape of the computation, which is determined by the shape of the underlying data, and represented by a type constructor (an operation on types); by the element type (a type); and by the body of the computation, which is a higher-order argument (a value, typically a function).  Although our presentation is in a functional programming style, we do not intend to argue that functional programming is the paradigm of the future (whatever we might feel personally!).  Rather, we believe that functional programming languages are a suitable test-bed for experimental language features - as evidenced by parametric polymorphism and list comprehensions, for example, which are both now finding their way into mainstream programming languages such as Java and C#.  We expect that the evolution of programming languages will continue to follow the same trend: experimental language features will be developed and explored in small, nimble laboratory languages, and the successful experiments will eventually make their way into the outside world. Specifically, we expect that the mainstream languages of tomorrow will be broadly similar to the languages of today — strongly and statically typed, object-oriented, with an underlying imperative mindset — but incorporating additional features from the functional world — specifically, higher-order operators and datatype genericity

Lately I have been making more of an effort to learn Scala. Bruno Oliveira and Jeremy Gibbons make the case in "Scala for Generic Programmers" that it might be one of or even the best language for expressing Generic Programming concepts in part due to its hybridization of object oriented and functional paradigms. Here is the abstract in its entirety:

Datatype-generic programming involves parametrization by the shape of data, in the form of type constructors such as ‘list of’.  Most approaches to datatype-generic programming are developed in the lazy functional programming language Haskell. We argue that the functional object-oriented language Scala is in many ways a better setting. Not only does Scala provide equivalents of all the necessary functional programming features (such parametric polymorphism, higher-order functions, higher-kinded type operations, and type- and constructor-classes), but it also provides the most useful features of object-oriented languages (such as subtyping, overriding, traditional single inheritance, and multiple inheritance in the form of traits). We show how this combination of features benefits datatype-generic programming, using three different approaches as illustrations.

So far for me Scala has been a joy.  Its features and flexibility are beautifully elegant of course I am tainted coming from the clumsy, clinking, clanking, clattering caliginous world of Java, BTW Java we need to talk, it’s not you, it’s me. I’ve met someone else.

Jeremy Gibbons Makes the following point in "Datatype-Generic Programming":

Generic programming is about making programming languages more flexible without compromising safety. Both sides of this equation are important, and becoming more so as we seek to do more and more with computer systems, while becoming ever more dependent on their reliability.

This idea is similar to ideas that Gerald Sussman explores in his talk at Strangeloop 2011 "We Really Don’t Know How To Compute".  However, his general and perhaps philosophical approach to the idea of generic programming is very different from the previous ideas:    

[8:40]We spend all of our time modifying existing code, the problem is our code is not adequately evolvable it is not adequately modifiable to fit the future in fact what we want is to make systems that have the property that they are good for things that the designer didn’t even think of or intend.  ... That’s the real problem. ...  The problem is that when we build systems whatever they are we program ourselves into holes. ...  It means that we make decisions early in some process that spread all over our system the consequences of those decisions such that the things that we want to change later are very difficult to change because we have to change a very large amount of stuff.  ... I want to figure ways that we can organize systems so that the consequence of the decisions we make are not expensive to change, we can’t avoid making decisions but we can try to figure out ways to minimize the cost of changing decisions we have made.

...

[11:40]Dynamically extensible generic operations  ...  I want to dynamically extend things while my program is running  ... I want a program to compute up what it is going to do.

He shows an example[19:00] which is "the definition of the method of computing Lagrange Equations from a Lagrangian given a configuration space path". This is apparently easy stuff, to him at least.  Fortunately you don’t really need to understand the details of this math to understand his points here:

[20:45]This is a little tiny feeling of what is it needed to make things more flexible consider the value here, the value is that I am dynamically allowed to change the meaning of all my operators to add new things that they can do. Dynamically. Not at compile time, at runtime.

...

[21:15]It gives me tremendous flexibility. Flexibility because the program I wrote to run on  a bunch of numbers with only a little bit of tweaking suddenly runs on matrices so long as I didn’t make mistake of commuting something wrong. ... So this makes proving the theorems very hard In fact maybe impossible the cost and the benefits are very extreme. I can pay  correctness or proofs of correctness or belief in correctness, I can pay that for tremendous flexibility. ... Is correctness the essential thing I want, I am not opposed to proofs, I love proofs I am an old mathematician. The problem is that putting us into the situation that Mr. Dijkstra got us into ... where you are supposed to prove everything to be right before you write the program getting into that situation puts us in a world where we have to make the specifications for the parts as tight as possible because it’s hard to prove general things, except occasionally it’s easier but it’s usually harder to prove a general theorem about something so you make a very specialized thing that works for a particular case you build this very big tower of stuff and boy is that brittle change the problem a little and it all falls over.

His ideas tend towards adaptable and self modifying code at one point he talks about self modifying code in both assembly language and the use of eval in Lisp.  He also touches on a number of parallels in the biological world including genetics and the adaptability of the human immune system to fight off mutating parasites.  Interestingly some of his ideas seem similar to work done by Stephanie Forrest on using evolutionary/genetic algorithms for program repair which she speaks about at the keynote of SPLASH 2010, formerly known as OOPSLA.  The genetic repair approach at the conceptual level is striving for the same results as what Gerald Sussman describes.  Also did you notice that the Levenshtein Distance between "generic programming" and "genetic programming" is (one substitution), pretty weird!

Seriously though, the objectives of all of these approaches are the same: building better more flexible software that handles more situations. These ideas are reflected in how Glenn Vanderburg describes software engineering:

Software engineering is the science and art of designing and making, with economy and elegance, systems so that they can readily adapt to situations which they may be subjected.

I feel this Software Engineering insight reinforces my opinion that we will eventually see a real math backed discipline of software engineering and I think that the research work discussed  here both supports my conjecture on this point and most likely lays part of that foundation.  I also think some of these ideas reflect ideas I discussed in "The Software Reuse Complexity Curve" which implies that programmers will need to become more aware and more adept at more advanced theoretically based concepts like for example GADT’s (Generalized algebraic datatypes), etc. and of course math in general such as Abstract Algebra.

Clearly the idea of Generic programming has some very specific ideas and some very general objectives. There seem to be two approaches here which might described Predictive vs. Adaptive, much like the idea of Separation of Design and Construction described by Martin Fowler.  The Gibbons et al more calculational approach is predictive whereas the Sussman/Forrest ideas describe an adaptive approach. I suspect that this will just be another dimension of program design that will have to be considered and assessed as a tradeoff in its application, which Sussman also mentions.

The Software Design Debate and the Futility of Opinion

A Tale of Two Classes

A while back when I was at a previous contract this article showed up on various link sites and one of the architects at that company sent it out. As a result, another developer and I, with the help of a googled code snippet, came up with the following code and added it to the common library:

public class ServiceResponse <ERROR extends ErrorReturn,

VALUE extends ValueReturn> {

private ServiceResponse() {

}

public ERROR error() {

return null;

}

public VALUE value() {

return null;

}

public final static class Error<ERROR extends ErrorReturn>

extends ServiceResponse<ERROR, ValueReturn> {

private final ERROR error;

public Error(ERROR error) {

this.error = error;

}

public ERROR error() {

return error;

}

public boolean isError() {

return true;

}

}

public final static class Value<VALUE extends ValueReturn>

extends ServiceResponse<ErrorReturn, VALUE> {

private final VALUE value;

public Value(VALUE value) {

this.value = value;

}

public VALUE value() {

return value;

}

public boolean isError() {

return false;

}

}

}

To be fair the original code was not documented, like this snippet, and there were a few other things that were a little less elegant but not hugely so, also all code here has been changed as not to infringe on intellectual property and to ensure anonymity.  As a result of the architecture and project schedule the other developer who needed the class ended not using it and also due to the aggressive project schedule there was no other follow up such as finishing the documentation or writing tests, this was partially my fault.

A few months later the architect needed this class and discovered our implementation he rewrote it as follows:

public class ServiceResponse<ERROR extends ErrorReturn,

VALUE extends ValueReturn> {

private ERROR error;

private VALUE value;

private boolean isError;

public ServiceResponse(ERROR error, VALUE value,

boolean isError) {

this.value = value;

this.error = error;

this.isError = isError;

}

public ERROR error() {

return this.error;

}

public VALUE value() {

return this.value;

}

public boolean isError() {

return isError;

}

}

Upon committing it he sent out an email to announce that he felt the original code was too complicated and he had simplified it to the above code.  I responded explaining that I felt that there were some issues with the instantiation of his new implementation and the real issue here was the lack of documentation.  I was shocked by his response in which he stuck to his argument that the new class was simpler to implement and didn’t require a lot of thought and we just need a wrapper class.  I confess I was initially perturbed by this as I felt that he was both wrong and taking a cargo cult attitude which was atypical for him, I later found out that he had been suffering through a bad cold.  Since I knew I would soon be leaving the project, I left it there even though I was pretty sure that his new design was significantly worse than the original.   I am intentionally omitting the details of the debate because I want to explore these in more detail momentarily. 

Throughout my career I have all too often found myself in these types of debates, and the thing I find so frustrating about it is the lack of real ways to accurately analyze these types of situations and the lack of any formal structure to the arguments themselves, they frequently become as constructive as a political or religious debate.  So it got me thinking, these are two pretty simple classes, how can we constructively analyze this situation and perhaps establish dispassionately and objectively which solution is better and what opportunities can this exploration present in a larger context?

First let’s look at the problem in the context of the current prominent thinking, let’s start with Joshua Bloch’s API ideas, which I have and will continue to reference.  Now remember the class in question is part of an API so these points are very relevant.  One point he makes is that an API:

• Easy to use, even without documentation
• Hard to misuse

So let’s assume that we have the following two classes and references:

ErrorReturn error;

ValueReturn value;

The original design has the two correct ways of creating it, omitting for the moment creating each with null:

new ServiceResponse.Error<ErrorReturn>(error);

new ServiceResponse.Value<ValueReturn>(value);

The new design has the following correct instantiations:

new ServiceResponse<ErrorReturn, ValueReturn>(error, null, false);

new ServiceResponse<ErrorReturn, ValueReturn>(null, value, true);

Also it is pretty obvious that the new design opens up several other ways that this object can be created.  It seems that new design more easily allows value and error to be mixed up.  The new design puts the responsibility of setting the Boolean isError on the user which opens it up to possibly being set incorrectly.  This breaks the hard to misuse rule.  In the old design it is an artificial value that created by a pure function.   So from the API design perspective it seems that the original design is better. 

Now another piece of conventional wisdom is the minimizing the number of parameters, in Clean Code Bob Martin talks about how you really shouldn’t have more than three parameters, well both instantiations fall under that, but by this logic is not the old design with one parameter then preferable to the new design with three? 

Another possible pro argument for the original design is the use of the "Disjoint Union" Either pattern, now this is not a GOF pattern but it is a pattern, perhaps an even more mathematical pattern, but regardless it is a specific pattern with precedence.

So that’s three pro arguments for the original design based on the current conventional software design wisdom promulgated by the leading software engineers of the field. So the original design is probably better.  Unfortunately I have found that even these arguments can be thwarted by the most recalcitrant cargo cult coder who doesn’t read and will always invoke arguments like "it’s too complex, it’s too abstract".

So I started to think, how could one look at this situation more analytically?  Going back to Joshua Blocks API talk, at some point and I don’t have this documented anywhere, he makes reference to an object’s state space, but he doesn’t go into detail about the concept.  This got me thinking, in this case we could pretty easily enumerate, at least at high level, the state space for each object and then compare them.  I am not sure if this is a known technique, I wouldn’t be surprised if someone has thought of or done this before.  In this case I am going to refer to this as "Enumerative Object State Space Analysis" or just "Object State Space Analysis" for lack of a better name.

So for this exercise we will interest ourselves in the possible values of a value or null for each parameter, where the error value is an instance of ErrorReturn and the value parameter is an instance of ValueReturn or true or false for the Boolean parameters, this is the following sets: {<Error>, null}, {<Value>, null}, and {true, false}. 

For the old design the possible instantiations are:

new ServiceResponse.Error<ErrorReturn>(error);

new ServiceResponse.Value<ValueReturn>(value);

new ServiceResponse.Error<ErrorReturn>(null);

new ServiceResponse.Value<ValueReturn>(null);

There are 2 possible Error instantiations and 2 possible Value instantiations leading to an object state space of 2 + 2 = 4 possible states, this is an application of the Sum Rule.  The new class has 2 possible values per constructor parameter, similarly from the Product Rule of combinatorics we can calculate that this leads to 2*2*2 = 8 possible states in the object state space.

We can enumerate (list them out) the states for the original class as follows:

Object State	Comment	Correctness Status
{Value, false}	Return state for successful operation	Correct intended state
{Error, true}	Return state for operation with an error.	Correct intended state
{null, false}	Return for a successful operation with no return value	State is a side effect of design, allows null, could be correct or could be considered a degenerate state.
{null, true}	Return for an operation with an error with no information	State is a side effect of design, allows null, could be correct or could be considered a degenerate state.

We can enumerate the states for the new class as follows:

Object State	Comment	Correctness Status
{null, Value, false}	Return state for successful operation	Correct intended state
{Error, null, true}	Return state for operation with an error.	Correct intended state
{null, null, false}	Return for a successful operation with no return value	State is a side effect of design, allows null, could be correct or could be considered a degenerate state.
{null, null, true}	Return for an operation with an error with no information	State is a side effect of design, allows null, could be correct or could be considered a degenerate state.
{Error, Value, false}	Return state for successful operation	State is correct from a usage standpoint but ambiguous from a programmer maintenance standpoint is this what was intended or is it reversed?
{Error, Value, true}	Return state for operation with an error.	State is correct from a usage standpoint but ambiguous from a programmer maintenance standpoint is this what was intended or is it reversed?
{null, Value, true}	Incorrect Usage	This is incorrect but the design allows this state to exist.
{Error, null, false}	Incorrect Usage	This is incorrect but the design allows this state to exist.

Assuming a uniform distribution the probability for each state in the original class is 25% and 12.5% in the new class, this means that the first design has 50% correct states and 50% null states.  The new design has 25% correct states, 25% null states, 25% ambiguous states, and 25% incorrect states. Of course a uniform distribution would probably not be the case as the correct usage would always be more likely and the incorrect usage would be the most unlikely.  Still, based on this analysis I am inclined to further conclude that the original design is better, perhaps even definitively so as the old design has no incorrect states and the expanded state space, which is twice as large, exponentially larger, also increases the complexity. 

Another possibility would be to eliminate the setting of the Boolean flag on the new design and allow it to be determined by a pure function as in the original design, but that opens up problems with respect to the ambiguous states that would exist.  In reflecting I also realized that the one of ambiguous states of the new design allow a state {Error, Value, false} which might be construed as success with information, which leads me to think that both designs are lacking and it might be better to always return an object that contains the value and some type of status object that allows error or success with info.

Now I know this is a lot and I am probably over thinking this, but I am treating this as an experiment:  Is it possible to come up with more analytical approaches using Enumerative and Combinatorial techniques to guide object design or other aspects of software design in a practical way?