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.
8 kommentarer:
I have considered this thought as well, trying to shoot holes in my own theory that's it's computationally possible to provide refactoring capabilities for a dynamic typed language. And I think I have an answer to your axiom: automated refactoring is not an instance of the halting problem.
True, it would be computationally expensive to provide automated refactoring using most methods. I'll illustrate one of those methods, and try to show how it doesn't require unknowable knowledge.
Say we have multiple classes that implement the same method foo, we'll call A, B, and C. The three are unrelated; they are not in the same object hierarchy, nor do they include each other or any modules that define foo. All three are used at various times to call foo.
Let's say we want to find all usages of A#foo. The most primitive method would just search for calls to foo, possibly including calls to B#foo and C#foo incorrectly in the results.
However it is possible to know, with a reasonable degree of accuracy, whether we're calling foo on an instance of A or B or C by backtracking. Take the following simple method.
def bar
x = A.new
y = B.new
z = C.new
# At this point, assuming that convention holds, we can know that x, y, and z hold instances of A, B, and C. Of course, you can define #new to return something other than the type it's called on, but that goes beyond what we can predict.
y = x
# Since we know what x was, we now know what y is from here on in.
z = x if condition
# Now here's where we avoid the halting problem; if a variable could be assigned a different type conditionally, we just associate that variable with *both types*. We don't need to branch predict...because for our purposes, both branches are equally likely, and both possibilities must be considered
x.foo
y.foo
z.foo
# At this point, we know for certain that x and y are both instances of A, because they were unconditionally assigned such. We know also that z could be an instance of either A or an instance of C. Do we have to know accurately? Not at all, and in fact we must *not* try to guess one way or the other. In duck typing, the one true interface is a method name. Both A and C implement that interface, and so tagging z as potentially being and instance of either A or C is absolutely correct.
end
Because we don't have to do precise analysis of the code, I believe we do not have the same issues as the halting problem. The vagaries of duck typing can be represented by treating a given variable as being any of the types it might be, since for refactoring purposes all those types must be considered. And this analysis is only required on a per-method basis; once we know all types instantiated in a given method, we can use that information to know what types are passed to other methods, and the types on which those methods are called.
It would be a computational chore, NP, perhaps, but not impossible.
Charles:
If I understand you, your argument boils down to performing type inference on variables.
This is belived to be undecidable in dynamic meta-programmed languages.
So I am not at all optimistic that we can perform automated refactoring in the sense that Ola describes.
We can, in the trivial example you give, identify that a variable will belong to a set of types.
A duck typed language is not equivalent to a language where every method forms its own interface/type. If it did, when we renamed foo in one class we would rename it in all classes.
Consider renaming 'A.foo' to 'A.fubar' while leaving 'B.foo' and 'C.foo' intact.
In that case, when we find z = x if condition followed by z.foo, we do not know whether the call to foo needs to be renamed fubar or not.
Maybe it does, maybe it doesn't. There are some conventions around how this works when A, B, and C are related types in the sense that languages like Java allow one type of extend another polymorphically.
But if thy are unrelatd types, what is the renaming convention here?
I think when you are saying "dynamically typed" you are thinking "statically but implicitly typed."
This is not the case for languages like Ruby that are fully dynamically typed. Inference strategies like the one you describe are undecidable in the presence of define_method and send_message.
You could easily have a class or object that only implements the foo method some of the time.
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.
Cedric isn't asking a relevant question - an IDE that performs a correct refactoring "most of the time" is massively better than an IDE which doesn't perform refactoring at all.
Java IDEs didn't start out with refactoring, they progressed to refactoring that works some of the time and then to refactoring that works "most of the time" - they were imperfect and very popular, and that answers Cedric's rhetorical question.
Reginald: I think you misread me. I'll try to answer your points.
I did not claim we can exactly infer the types of variables; rather I said we can make some determination as to a set of types variables may contain. There's a huge difference there. The nature of dynamic languages makes any exact determination impossible, but I would argue that specifics are not necessary.
As you mention in your rehashing of my z = x example, we don't know whether we can rename the foo on z or not because z could be an instance of either A or C. You are exactly correct, we can't know whether the renaming should occur. In this case, if a user asks to rename foo, the refactoring of A#foo alone would fail; because we have an intersection of two types, it is not possible to automatically rename foo on either A or C, without renaming foo on both. But then this gets to the heart of the matter...
Refactoring has typically been defined in terms of static languages. A "rename method" refactoring has traditionally meant that all callers of the method must be updated as well. However this is not applicable to a dynamic language. In a dynamic language, the method itself is just an arbitrary name and set of parameters. The types do in fact conform to an explicit interface...looking at it in Smalltalk terms, they respond to a given message named "foo". Without anything more specific, it's easy to see that all classes that implement a method called foo are potential targets for a rename, and such a renaming *would be completely valid*.
I'll give another example:
def append(other)
...
end
append has a much more specific meaning than foo; it means to take the given parameter and add it to the receiver. Strings can append, lists can append, and many other types support appending. So then, if I choose to rename append in one type, why shouldn't I be renaming it in all types?
The fact is, by renaming append, my custom type is now fulfilling a different contract. If I rename the method to "append_all", I'm creating behavior above and beyond the original definition of append, or at least making that behavior explicit. So then the traditional refactorings we've become used to must be looked at differently.
Renaming append to append_all would present in the simple case two options: rename all calls to append methods, throughout the code, or create a new method append_all that delegates to the old one. Without digging deeper, there's no more we can do...but this still pretty good. By examining a narrower field of code, we can be smarter...if, for example, my previous code didn't have a conditional assignment of z = x, we could safely rename y and x calls to A#foo. Even in the conditional case, there's another option: present the user with a choice.
Dynamic languages are predicated on the control and trust they give back to developers. Rather than using strict language features to ensure code is following the rules, developers use their own skills and development best practices to make the same assertions. It's probably the largest reason why dynamic-typed languages are so popular...they let you shoot yourself in the foot, but they also don't encumber you with restrictions you rarely need.
So why should refactoring tools for dynamic languages be any different? In the ambiguous cases, I'll grant there's no way to do an automated refactoring unless you rename both x#foo and z#foo (which is still a valid thing to do). However I believe any refactoring tools eventually created for dynamic languages would be best served by offering a choice to the user. Do you want to rename all potential calls to A#foo? If so, here is a list of ambiguities you must resolve, or accept renaming those other implementations of foo as well.
In reality, I think such collisions would be much more rare than you'd expect. foo may be a bad example; append is much more clear. There are only a very limited set of types we would expect to have append operations, and we're generally not using them interchangeably. Look at the following code:
x = "Hello, "
y = [1, 2, 3]
y.append(x)
# this makes sense, we're appending a new item to the list. A list's append can reasonably be expected to take any type of argument.
x.append(y)
# this doesn't make sense. Do we append the contents of the array or each element to x?
I would be very surprised if you see incompatible types used interchangeably for the same variable precisely because those types have very specific roles. It's not just that you can't interchange a string and a list for the append call above; it's that you won't. And so the collision will not occur for the methods you're most likely to refactor.
The inverse applies as well. If our code actually does use A and C interchangeably to call foo..then *why isn't renaming both A and C's implementations right?* I'll tell you the answer...it IS the right thing to do, since the example code expects "foo" behavior from both types. Renaming one, and thereby altering the contract, should cause an assertion during refactoring...because the semantics of the code have now changed for all callers. The programmer now must stop and consider whether changing only A's behavior is valid, given that A and C are both used in the same way.
And to address your thoughts about define_method and send_message...
Both define_method and send_message fall into metaprogramming. Metaprogramming alters the structure of code at runtime, and so by its very nature it's not refactorable ahead-of-time. Just like Java Reflection's runtime decisions about what types and methods to call, define_method, send_message, and all the other metaprogramming techniques break ahead-of-time refactoring. I don't think this point is in question, and it is perhaps the biggest risk of using reflection or metaprogramming heavily.
I guess my bottom line is that dynamic-typed languages are not so dynamic that we can't provide refactoring tools; we just have to think about those tools in a different way. Certain refactorings we've come to know on static-typed languages must be rethought or replaced. No, it's probably not possible to support all the refactorings static languages support with the exact same characteristics...but just as it's foolish to think about a dynamic language in static language terms, it's foolish to force static language refactorings on a completely different domain without expecting to change the rules a bit.
Charles Oliver Nutter wrote Even in the conditional case, there's another option: present the user with a choice.
And that's how rename-method refactoring works in Smalltalk - the Refactoring Browser will open a dialog listing all the methods with that name and all the methods with call sites. We can select a method from the list, and see the method text before and after the method-renaming. We can choose to exclude that method from the method-renaming by removing it from the list, and then go ahead and rename the other methods and call-sites.
You could always rely on your tests to tell you if your refactoring broke anything. It never hurts to have more reasons to make your tests more comprehensive.
(You could even use an rcov-like test piggy-back tool to try to determine the class of a given object as the tests run.)
But shooting for 100% is rather silly. As long as you have a system that leverages your test coverage, you should be in good shape.
Comment here: http://www.zwitserloot.com/2006/11/21/the-ola-bini-challenge/
Static typing helps you as a programmer to draw the line between when it's guaranteed to work by your IDE, and when you need to run all your integration tests again.
For a related experience in the Subtext programming language, see blog.
Skicka en kommentar