October 7th, 2006
Effectiveness of automated refactoring.
The last few weeks have seen some discussion regarding refactoring tools for dynamic languages. The basic questions are if it is possible, and if so, how effective it would be. More information about the debate in question can be found here, here and here. I’m not really going into the fray here; I just wanted to provide my hypothesis on something tangential to the issue.
The interesting point is something Cedric said in his blog:
And without this, who wants an IDE that performs a correct refactoring “most of the time”?
The underlying assumption here is that there can actually exist a refactoring tool that works all the time. So, my question is this: “Can a Refactoring tool be 100% effective, (where effectiveness is defined as completely fulfilling the refactoring preconditions, postconditions and invariants and without introducing dangers or errors in the code).”
My hypothesis (and there will be no rigorous proof of my position) is based on one axiom:
Automated refactoring is a subset of the Church-Turing halting problem.
I have no direct proof for this position, but it seems intuitive to me, that for a refactoring to always be completely correct, you would need to know things about the program that isn’t always entirely possible to predict only from code. In this case, test runs would be necessary, and in those cases the halting problem enters. Now, for a strongly, statically typed language you would have to go to some effort to actually produce a program that couldn’t be safely refactored, but the possibility is still there.
One commenter on one of the blog entries above said that a precondition for 100% refactoring of Java would be that you didn’t use reflection and other meta-tricks. But the problem is, to avoid the halting problem you would have to remove enough features of Java to make it into a Turing-incomplete language. And by then it wouldn’t be usable for general purpose programming.
I see no way out of this dilemma, unless my axiom is wrong. But if it is correct, there can never ever be a 100% effective refactoring tool.
