Functional Refactoring and "You Can't Get There From Here" 17
I’ve been working in Haskell recently, and I find myself doing much less refactoring. In fact, I rewrite more than I refactor.
I’m not talking about massive refactoring, but rather the sort of micro-refactoring that I do to move from one algorithm to another. If you are working in an imperative language, you can often make micro waypoints – little testable steps along the way as you change your code from one shape to another. You can add a variable, confident that behavior won’t change because you haven’t used it yet, and you can move one statement down below another, changing the order of a calculation if (again) you are confident that the overall computation is order in variant. As I TDD my code, I do those sorts of things. I often refactor by introducing a parallel computation in the same method as the old one, and if the test passes, I knock out the old way of doing things and leave the shiny new one.
In Haskell, however, I don’t do that, and it reduces the amount of time that I spend refactoring. Yes, I rename variables, add parameters, and introduce where-clauses, etc. But, refactoring in Haskell seems different, and I think I know why now. There are two reasons and they sort of intermingle.
Imperative programs are built of little state changing variables, and one of the effects is that you can have lots of little bits changing independently. It’s rather easy to add mutating state variables and have “several calculations in the air” in a method while you are along the way toward reducing it to one. In functional programming, however, you use bigger pieces. Instead of looping, you use map or fold – you end up with terse code which packs a lot of punch.
Here’s a function which determines a position within a document from a column/row coordinate (affectionately named x and y here):
absPosition :: Buffer -> Int
absPosition (Buffer (x, y) contents) = x + lenPreviousLines contents
where lenPreviousLines = foldr ((+).length) 0 . take y . terminatedLines
The thing to get from this example if you don’t read Haskell is that it is fully compositional. Each of the dots in the definition of lenPreviousLines is a composition operation. We apply the terminatedLines function to a string, and take its output and pass it to the function ‘take y’, then we pass its output to ‘foldr ((+).length) 0’. The net effect (take my word for it) is that we end up with the sum of the lengths of a set of text lines.
That small piece of code performs a rather large chunk of work. It takes a string, splits it into lines, appends a newline to each line, takes y of the lines and then sums the count of their characters. But, to me, that’s not the interesting part. The interesting part is that it is tight. There is no space for a parallel computation, no place where you can perform some computation off to the side and progressively move toward a different algorithm. If you want to change the algorithm you essentially rewrite it – you replace some chunk of that code with another chunk of code.
One of the beautiful things about pure functional programming is that it eliminates side effects. That, by itself, might not impress you, but the thing that it enables is very powerful, when you remove side effects you lose all barriers to composability. It’s easy to make little tinker-toy-like parts which you piece together to do your work, and, in fact, that’s exactly what has happened in Haskell. Most of the time, you can find a little function which will do what you want. You don’t often have to drop down into primitive list operations or recursion. Instead, you have this substrate of little composable bits. We don’t have anything like that in traditional languages. We drop down to loops, assignment and mutable variables all the time.
The end result, I think, is that a lot of refactoring in Haskell is more like rewriting, or (to be precise) it is more like the ‘Substitute Algorithm’ refactoring in Martin Fowler’s Refactoring book. In pure code, there isn’t any extra bandwidth for building up parallel computations. The pieces are bigger, so many refactorings are more like leaps than micro-adjustments toward a goal.
Is this good or bad? I don’t know. I think it is just different. Personally, I’m happy to have higher level pieces, although, I have to admit, I sometimes miss the fluidity of work with more granular primitives. It’s a place you can always drop down to and build back up from. In Haskell, at the micro-level, you have to fix your sights on a new target and rebuild.
Refactoring in functional programming languages is different, I agree. However, it is possible to do it smoothly, rather than rewriting in big chunks. Paul Hudak has some awesome examples of smooth manipulations in his book “Haskell School of Expression”.
Don’t throw up your hands and say “it’s different”. Yes, it’s different, but that move is always available – it’s too easy.
Two of the primary moves in functional refactoring are expansion “replace a function with its (anonymous) definition”, and contraction “replace an (anonymous) function with a call to an existing procedure”. Elegant chains often look like “expand-expand-expand-contract-contract-contract”.
Johnicholas: Yes, I do that. The bit which I don’t do is build up a parallel computation in place, and use it to replace what was there. It also seems that when I add new functionality, I have to replace what I have for the next case rather than perform a minor refactoring. It’s manageable, but a bit different.
BTW, I like Hudak’s book quite a bit. I was my first Haskell book.
Can you talk a bit more about TDD in Haskell? I was having good luck on the bottom ‘layer’ of what I was working on, but trying to test-drive higher stuff (that composed those others) was quite hard for me – had to do a lot of setup. Maybe I am just going about things wrong – I still don’t have a good idea how to structure Haskell programs overall.
I think type-classes are underused in idiomatic Haskell. Working with those gives you both the ability to test with mocks, and often the ability to refactor. Particularly, classical FP tends to need a million little changes when you change the data definition, but accessing data through type-classes gives you protection.
I know you’re learning but a couple of statements are completely out of whack.
“Imperative programs are built of little state changing variables, and one of the effects is that you can have lots of little bits changing independently.”
Actually, imperative programs, by their very definition, have little bits that are not little bits after all, since they are not independent. This is the essence of the whole problem of imperative programming.
“when you remove side effects you lose all barriers to composability.”
No, quite the opposite, when you remove side-effects, you break down barriers to composability.
I think you’re one step before realising that “refactoring” is a bunk concept that (poorly) works around bad programming practices.
When you want to “change the behaviour” of that pure function, why the aversion to writing a new function? Why does the original one need to be “refactored”? The answer runs deep, so spare some time for yourself.
@Julian There is an enlightening example of this in RWH that demonstrates use of type-classes in a testing context for monadic code (but could be any typeclass of course). Nice thing about it is that it is deeply related to something that has become prominent in OO testing: test and mock to interfaces you own, thus creates your own abstraction that wrap standard or low-level interfaces.
But you may know it already :-)
@michael did you try to install/use HaRe ? it seems a little bit dormant (or so was it last time I checked…) but promised to offer some useful tools for doing simple refactorings. The ones I am missing most is the ability to rename and ‘extract function’.
““when you remove side effects you lose all barriers to composability.”
No, quite the opposite, when you remove side-effects, you break down barriers to composability.”
I think you don’t read so good. And you’re mean.
@Carl:
That’s Tony Morris for you. Do like we all do on the various FP mailing-lists: read his messages just to discover what other twisted wording he’ll come up with to make fun of the person he responds to but ignore the content of his messages, which is often wrong anyway (this one is no exception).
I think Tony Morris is saying something interesting: if you just write a second function then you have two parallel paths (the new one and the old one) which are much easier to test against each other than if you had two (heap-changing) algorithms in a single method. You could, for example, auto-generate test data and throw it at both versions pretty easily. When there are discrepancies you can look to see whether the new one or the old one handled it better.
Concerning both refactoring and rewriting a function, we Haskellers also rely a lot on the type checker to keep us on the right path. Of course, strong type checking cannot replace a rigorous testing discipline, but it makes you more confident to take bigger steps.
Oops .. for entering my email instead of the name.
You can always introduce a let and name those intermediate results, and then there’s plenty of room for parallel versions, if you really want to change things incrementally.
Not sure I’m adding much here, but when I was working with CAL (http://openquark.org/ – a Haskell-like language which compiles to Java bytecode) I found the same.
I’d solve the problem one way, learning much about it, then almost completely rewrite it. I guess this is much more akin to prototyping than refactoring, which isn’t itself a bad thing IMHO. Wasn’t it Brooks that said: “Plan to throw one away; you will anyway”?
I like to work in Lisp (functional programming) when ever I can. I originally learned it the 70s before we bothered with things like TDD. But I do things differently now. What I have learned to do now is create a stack of failing unit tests.
You drive your code from the top level by adding a test that fails. You go to fix your code and notice you need a new function. You stop and create another unit test for that function. Now as you create that function you notice you need yet another function. So you create a failing unit test for that.
Now you have 3 failing unit tests in a stack. When I get the current unit test done I will push another on the stack until my function is done, then pop the stack. Now I have the function I need to get the next test running. I can now test my function into existence and pop the stack again. I use the function I just created to get the last unit test running.
So, now to refactor. I decide to change some function by calling some new function, so I write unit tests to test that new function into existence then continue my refactoring. If I find a function not being used I delete it and all of its tests.
“If you want to change the algorithm you essentially rewrite it – you replace some chunk of that code with another chunk of code.”—that’s pretty much how I’d describe the activity of refactoring; you seem to be taking a more limited definition than I would use.
Using let or where bindings to pull out pieces of a computation and experiment with alternatives is very good advice. But also, I find myself coding large complex actions on lists on the first pass as big recursive loops, then pulling out bits of common structure into smaller pieces. I suppose the difference is that you can always step back and look at the whole chain of computations, so refactoring will tend to involve altering where/how the chain is broken up to make things more logical. Eliminating superfluous points and soforth as well.
foldr ((+).length) 0 . take y . terminatedLines for example could become (sum . map length . take y . terminatedLines)—moving from explicit folds up to more restricted combinators is an abstraction win i think, though your milage my vary.
At which point I’d probably decide the where clause was superfluous and inline it back into the function yielding: x + (sum . map length . take y . terminatedLines $ contents). I’d then turn the plus into a section, getting: (x+) . sum . map length . take y . terminatedLines $ contents.
At this point I’d see that adding x when I’m already summing is sort of silly, and maybe rewrite it as such: sum . (x:) . map length . take y . terminatedLines $ contents.
This now expresses that the sum is of the length of y terminated lines, along with the x position.
Your taste and mileage may vary of course.
sterl: Thanks for your suggestions. I incorporated them and added some musings here: http://blog.objectmentor.com/articles/2009/08/11/naming-and-body-language-in-functional-code