Automated Refactoring

This post will translate eventually into my blog. I will put back a reference back to this thread to give credit for those joining in the conversation.

Informally, given a method, can we break it up into smaller parts that are more comprehensible to the programmer. I want to define this problem formally so that I can come up with a solid algorithmic solution that can be worked out by hand or even possibly becoming automated. In either way, it has to be completely mechanical.
And since we don't have a model of human comprehension, or can't afford evolutionary techniques against people (which as I am writing this, makes even more sense, and could actually be possible). My best bet is to define some constraints that will guarantee a more simple method is output from a more complex one.

The most naive thing the refactorer will do is to return the method as is. The other naive thing it can do is to encapsulate each statement into a new method. Both of these are utterly useless. None the less, we have defined the 'range' of the algorithm, and actually have already bounded the solution (even without having totally defined the problem yet).

The algorithm stability and sanity pivots around another point. If a method is refactored into atomic methods, the algorithm applied to these methods will be an identity operation (will leave them unchanged).

To simplify the whole thing, so that I can start with some lead, we will assume that all the methods we define are actually context-less functions. The form of these functions is: function (input1, input2, input3, ...) => (output1, output2, output3, ...).
This all should be taken into a functional context (there are no state variables, only symbols that are bound to expressions or values).

Using pseudo code, here goes

naive_example: (x1, x2) => (y1, y2)
   y1 <= x2;
   y2 <= x1 * x2;

The output from the algorithm must come out like the following:

naive_example: (x1, x2) => (y1, y2)
   y1 <= atomic1(x2);
   y2 <= atomic2(x1, x2);

atomic1: (x) => (y)
   y <= x;

atomic2: (x1, x2) => (y)
   y <= x1 * x2;

This is the most naive example I could think of at the moment, and I already spotted a lot of problems with the rigidity of the definition of a function that I am using. Additionally there is a problem with singly bound variables that I do want to avoid having. I need variables to be more than once assignable, which can be solved by using multiple instances of a variable (x becomes x1, x2, x3...)

Share your thoughts, I will think more about all of this and expand on this later.

http://en.wikipedia.org/wiki/Static_single_assignment_form
This should create the bind between the two paradigms.

Refactor code to seperate concerns, to understand where there is possible parallelism-exploitable hot spots, and to make code more reusable and understandable.
Refactor a method onto the most rigidly connected components.

This thread deals with refactoring at the function level, there is research and thesis'es on the internet about class hierarchy refactoring as I quickly skimmed through the first few Google results.

nablaux wroteWhat would be nice to do is a system similar to doxygen but for refactoring.
When a programmer is coding he/she specifies each connected component of code inside a certain function. Then the automated refactoring will take that code and re-write it.
Does this make any sense or is it appealing to anyone else?

Example please.
This might be interesting though it incurs a change on the problem domain. (Human Hints)

Some new revelations on the rigidity of the problem:
Given a list of expressions (mainly function calls), what are the permutations that would leave the output intact?

Example:

(x, y, z) => (u, v, w):
   u = func1(x, y);
   v = func2(u, z);
   w = func3(u, v);

In this example, there are no permutations to the above that would not change the meaning of the program. (Assuming that we are not in control of func1, 2, 3.. or in the case we don't want to inspect them, or want to change them in the future..).

This example however:

(x, y, z) => (u, v, w):
   x = u;
   y = v;
   z = w;

Any permutation of the list will lead to the same meaning when the function returns.

The cream resides in dependencies.
In the first example:
'u' depends on 'x' and 'y'.
'v' depends on 'u' and 'z'.
'w' depends on 'u' and 'v'.

A dependency topological sorter would quickly show that this is the order of operations that must happen, and the only one that has this particular meaning.

What if we changed the last statement into simply:

w = func3(z);

The dependency is lost, and this statement becomes only dependent on the last input. A simple dependency flood fill like operation on the list of statements (not pertaining even to their order) would show the different operations in this function that can go in parallel and are indeed separable.

@xterm: I refuse to believe this is mathematically impossible. It may be impossible to apply to some context-full languages, but perhaps is extremely applicable to functional languages, or a subset of of some language (const functions with const inputs in C++ for example).

mrmat wroteJust another example of pure laziness. period. :)

I too believe that this is somehow impossible to achieve. The results will not be as good as doing it the human way. The only thing this can help with is time, but i'd prefer quality over that.

This tool is specifically for code analysis. I am even sure that it has been implemented somewhere (be it in the compiler, or even in the CPU itself).

Breaking up a method into its separable components is invaluable. It's as much laziness as the laziness involved in not wanting to write ASM code.

I too believe that this is somehow impossible to achieve. The results will not be as good as doing it the human way. The only thing this can help with is time, but i'd prefer quality over that.

If you have a mechanical solution for a mathematical problem, there is no human way any more. At most it would be repeated application of an algorithm manually. Hardly smart.

Somehow impossible to achieve
What the fuck? Where are you getting this from?

@rahmu: Writing style is hardly an issue here. It's the just the fact that I am thinking about imperative functions without access to global scope or class scope.

if you passed in a single method what would be a possible automatic refactoring technique; you can simply take apart the code path's that are independent of each other and they'll automatically become readable and parallel ready.
it would not take much to alter the mathematical technique into a context-full imperative technique that takes into account the existence of references rather than just read-only input and write-only output.

I still need to figure out two huge aspects before moving into full imperative refactoring techniques. You should know that mathematically what I described so far is pretty possible to factor, automatically and algorithmically efficiently.
The issues are: branching/jumps (while, if, ..) and recursion (consider if it causes any problem).

Perhaps I will write a parser for a simple purely-computational language (integer/double are the only data types) and implement the auto factoring on top of it. Arrays should prove problematic as well to work with.

I guess I am just wishing to do my Masters Degree in Computer Science with all of this theoretical work.