DI Breakdown

I’m having a philosophical breakdown of the software engineering variety. I’m writing a register allocation library for my current project at work, referencing a not-too-complex algorithm which, however, has many degrees of freedom.  Throughout the paper they talk about making various modifications to achieve different effects — tying variables to specific registers, brazenly pretending that a node is colorable when it looks like it isn’t (because it might work out in its favor), heuristics for choosing which nodes to simplify first, categorizing all the move instructions in the program to select from a smart, small set when the time comes to try to eliminate them.  I’m trying to characterize the algorithm so that those different selections can be made easily, and it is a wonderful puzzle.

I also feel aesthetically stuck.   I am feeling too many choices in Haskell — do I take this option as a parameter, or do I stuff it in a reader monad?  Similarly, do I characterize this computation as living in the Cont monad, or do I simply take a continuation as a parameter?  When expressing a piece of a computation, do I return the “simplest” type which provides the necessary data, do I return a functor which informs how the piece is to be used, or do I just go ahead and traverse the final data structure right there?  What if the simplest type that gives the necessary information is vacuous, and all the information is in how it is used?

You might be thinking to yourself, “yes, Luke, you are just designing software.”  But it feels more arbitrary than that — I have everything I want to say and I know how it fits together.  My physics professor always used to say “now we have to make a choice — which is bad, because we’re about to make the wrong one”.  He would manipulate the problem until every decision was forced.  I need a way to constrain my decisions, to find what might be seen as the unique most general type of each piece of this algorithm.  There are too many ways to say everything.

6 thoughts on “DI Breakdown

  1. I think it’s more about the shape of the space of choices rather than simply the quantity. If the space was somehow “convex”, it would be easy to slide around between different choices as advantages and disadvantages present themselves. However, switching ambient monads typically involves a large number of small changes throughout a code base. Convex may not be the right word, though.

  2. The advice I struggle to follow myself is that if you get stuck like that you must pick one and go on. If you really are that undecided you need some new evidence and the most obvious experiment to get it is to try one of the alternatives.

  3. Hi Luke.

    I’m afraid I don’t have a very good answer to your question. But it’s a great question to ask!

    I recently taught a course on object-oriented programming. I have to admit that there is much better literature on software design in this community than there is in the FP world. Many functional programmers take design for granted and focus on technology: once you use the right programming language/monad/whatever, your software will be easy to maintain and free of bugs! In practice, it doesn’t work that way.

    I used the book ‘Design Patterns Explained’ by Shalloway and Trott. There are a few good chapters on Commonality-Variability Analysis. The idea is fairly simple: start by finding commonalities in your design (there are heuristics for finding X; the algorithm is parameterized by Y; etc.). Next figure out what variation you have between (the algorithm uses the heuristics A, B, and C to find X). Only when you have a good idea about your domain, can you start to think about code.

    There are plenty of ways to encapsulate this kind variation in Haskell. Design a datatype that controls which heuristic to use. Or define a type class overloading the operations that each heuristic supports. Or pass a function argument that corresponds to the different heuristics. And probably lots of other techniques that I’m forgetting. I can’t speak for you, but it sounds like this may be where your confusion is coming from – you’re overwhelmed by the different technology you could use to solve a problem, before you fully understand which problem you’re trying to solve on a more abstract level.

    Anyhow, sorry for the long rant. I hope it is useful somehow.

  4. “Now we have to make a choice — which is bad, because we’re about to make the wrong one”

    This is cute. (And I’ll be stealing it for my own use).

    Interesting note. This is essentially why the ideas of limits and colimits are so important in category theory. Category theory is, of course, the classification of things based solely on their morphisms to and from other things. Given a particular setup (a commutative diagram), a limit is a particular solution (a cone) such that all other solutions (all other cones) have not just a morphism from the limit, but a UNIQUE morphism.

    Why does it matter that it’s unique? Because you can’t screw things up that way :)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s