Mythbusting - Part 3 (The Inherent Paradox)

This is the third part in this mini series whose goal is to show why static dependency analysis is largely useless.

Part 1 primarily used reasoning and essay-like arguments.
Part 2 provided hard data --- that is: actual dependency graphs --- showing that tangled packages (let alone tangled classes) are common in very successful libraries and tools.

This part will probably be much more entertaining: It shows the logical flaw underlying static dependency analysis.

So, here is a Java program with two classes. The code itself is silly. I just wanted to have a program with cyclic dependency that is doing something (no matter how silly).


package p1;
import p2.B;

public class A {
private B b;

public void setB(B b) { this.b = b; }
public void f(String s) {
b.g(s);
}
}

package p2;
import p1.A;

public class B {
private A a;

public void setA(A a) { this.a = a; }
public void g(String s) {
if(s.length() != 0)
a.f(s.substring(1));
}
}


As expected, the dependency graph of packages p1, p2 is a cycle:



Now, let's rewrite this program by applying the following rules:
  1. All variables, parameters, fields, return types will have the type "Object"
  2. Every method invocation such as x.m(y,z) will be rewritten as: Util.call(x, "m", y, z). The Util class itself is shown in the fragment below.

(Reservation: I've intentionally left out rules for the handling of overloading, static members, and object creation as these are not needed for the example shown here)

Here is how the program looks like (to avoid confusion I now use packages pp1, pp2 rather than p1, p2).

package pp1;

import pp2.B;
import static pp0.Util.call;

public class A {
private Object b;

public void setB(Object b) { this.b = b; }
public void f(Object s) {
call(b, "g", s);
}
}

package pp2;
import static pp0.Util.call;

public class B {
private Object a;

public void setA(Object a) { this.a = a; }
public void g(Object s) {
if(!call(s, "length").equals(0))
call(a, "f", call(s, "substring", 1));
}
}

Of course, we also need to write the static method Util.call (in package pp0). Here it is:

package pp0;

import java.lang.reflect.Method;

public class Util {
public static Object call(Object r, String s,
Object... args) {
for(Method m : r.getClass().getMethods()) {
if(!m.getName().equals(s))
continue;

if(m.getParameterTypes().length != args.length)
continue;

try {
return m.invoke(r, args);
} catch(Exception e) {
throw new RuntimeException(e);
}
}
return null;
}
}


We can now take a look at this dependency graph of pp0, pp1, pp2:



(Irony mode on) Wow! No tangles! This technique is awesome. No matter how big and tangled your program is, you can apply these two very simple transformation rules and you will get this nice-, loosely coupled-, code, where each class depends only on Util.call(). Amazing! (Irony mode off)

Do you see the paradox? Tools that detect cyclic-dependencies are using type information from your source code to help you find highly coupled modules. However, these tools encourage you to eradicate the information on which they rely. In a sense, they want you to make them blind. This makes no sense.

Clearly, the transformation rules that we applied did not really eliminate coupling. They just swept it under the rug. The coupling is still there, waiting for run-time to raise its head. If one claims that cyclic dependency analysis is not valid *after* the transformation, due to inability to determine the run-time dependencies, one should also acknowledge that cyclic dependency analysis was not valid *before* the transformation due to the same reason: inability to determine run-time dependencies.

Is there a morale here? I guess there is. Think about dynamically typed languages:

  • If you believe in static analysis of dependencies you should start developing in a dynamically typed language and you will immediately boost your static analysis score through the roof: no cycles, no coupling of packages/classes/methods.

  • (otherwise) you don't believe in static analysis. You know that the static picture is only a distorted reflection of the dynamic behavior. Hence, you know that you cannot trust a tool that tells you that your program is OK. If this is what you think, then you are already writing in Smalltalk, Self, Javascript or Ruby.


Update 1: Added "(Turning irony on)"

Update 2: Added the reservation

29 comments :: Mythbusting - Part 3 (The Inherent Paradox)

  1. Did what you just say imply that writing dependencies in xml configurations, or others untyped syntax, lets us hide real dependencies from static analysis programs such as structure 101 and jdepend ?

    Wow, that should be more known from people blindly using jdepend. (I do not pretend that struture 101 or others are not usefull).

    It seems that dependencies and cyclic dependencies are not so bad as some people have said, and examples of this blog shows the contrary.
    And certainly, it is not a crime to do less coding in xml as in spring, and more in java; at least we would have type checking.

  2. There is nothing wrong with using those tools, the solution you offer for eliminating the issues they find is wrong.
    It's not because a tool does not find all issues that it can't be used to find some of them. The danger is believing that it does finds them all.

  3. Emeric, Anonymous:

    In most disciplines, a metric/tool that has some blind spots is something that people can usually live with (depending on the exact context, of course).

    However, here we have something else. A metric that gives you bonus points for these blind spots, is something which is pretty close to worthless.

    In a sense, this is similar to your airline giving you extra miles for flights that you didn't take.

  4. Your argument is spurious and incorrect. You imply that the only way to get the loose coupling is using reflection?! Are you kidding? Interfaces and basic OO principles provide you with a much simpler, strongly typed alternative. I'm wondering whether perhaps you don't actually realize how to do this cleanly?

    E.g. put interfaces IA and IB in package pp0.

    have a look at the abstract server and abstract client concepts in Bob Martin's work: http://www.objectmentor.com/resources/articles/Principles_and_Patterns.pdf

  5. Your correction to the tangle problem is INCORRECT. Thus, your argument fails.

  6. Andrew, masteromd:

    I am sorry to disappoint you guys, but you were so anxious to say that interfaces can be used here that you missed the irony, and consequently, this post's main point.

    This post never said that reflection is the only way to solve tangled packages issues. On the contrary. The post says that (a) tangles can be solved using reflection, which clearly is an awkward solution (b) Static analyzers cannot distinguish between the clean solution and the awkward solution.

    Hence, the credibility of techniques for static dependency analysis is highly questionable.

  7. Two comments:

    1) Java is not a very "strong" static language. Other languages could perhaps grant better help with refactoring/analyzing your code. You're also using dynamic features of java that ignore static typing information. You have to help the compiler out sometimes to get better results. The nice thing here is that even in java, it can inform you of potential issues, even if (given some simple, arbitrary rules), it cannot fix them to your liking. I like Matthew Wilson's comment in Imperfect C++, "Make the compiler your batman." (Translated, use the compile to prevent you from screwing up)

    2) The java compiler can warn you were doing something stupid, just not something really stupid when you were trying to be clever (i.e. using dynamic features). I don't see this as invalidating the entirety of static analysis, just because you used reflection and casting. It would be better to take a "good" example of static analysis and prove how dynamic casting will always beat this "good" example.

    What you're really complaining about is how people "game the system" to make their metrics look good (according to automated tools) even when their not. People are lazy. That doesn't mean static analysis is not useful to programmers, it just means you shouldn't judge performance from automated metrics.

    Perhaps I'll make a post doing something clearly silly in Javascript/Groovy/Ruby/Python to prove how dynamic typing is useless....

  8. @J. Suereth
    "Java is not a very "strong" static language. Other languages could perhaps grant better help with refactoring/analyzing"

    As you know, no compiler will be able to statically detect infinite loops, breach of contracts, array-index-out-of-bounds errors, etc. There will always be a great deal of dynamic complexity about which the compiler is completely ignorant.


    "The java compiler can warn you were doing something stupid, just not something really stupid when you were trying to be clever (i.e. using dynamic features)"

    Reflection is an extreme example of a programming techniques that has a dynamic nature (in the sense that it hides a lot of the semantics from the compiler).

    Here's a partial list of viable, non awkward, techniques that has the same dynamic nature:
    data driven programming
    DSL
    The Properties Patterns

    People who use these techniques are not trying to "game the system". They just want to have simpler, robust code. Static analysis of such programs is as meaningless as with reflection-based programs.

  9. @ITay
    "Static analyzers cannot distinguish between the clean solution and the awkward solution."
    ...
    "Hence, the credibility of techniques for static dependency analysis is highly questionable."

    This argument is a non-sequitur. Yes, the static analysis can be gamed. However, the static analysis is a guide to help programmers. That doesn't make it useless. For a programmer looking to static analysis to make their code better, it's very helpful. For a team lead hoping to find bad structure, combine it with reflection inspections (which are static also).

  10. @Andrew
    "Yes, the static analysis can be gamed."

    (Please see my my reply to J. Suereth, above).

    There are legitimate, mainstream, techniques (which, by the way, seem to be gaining popularity) which will game the static analyzer in the same manner as the reflection-based code.

  11. [i]However, these tools encourage you to eradicate the information on which they rely. In a sense, they want you to make them blind. This makes no sense.[/i]

    There is one thing here making no sense and that's that line. You could also say that Cobertura "encourages" you to evaluate a method and not check its return value just to see the code coverage percent go up.

  12. In the first parts you argue that tangles pose no problems. In this part, you argue that tooling that detects tangles pose additional problems. Sure, a stupid reaction to prevent tangles will only make the problem worse, but that is a very weak argument. If you really think that tangles are not a problem, stick to that argument, instead of blaming the tools as well.

    I am also lost on how Spring would encourage reflection based programming and would throw off tools like Structure101. Since all you do is injecting dependencies you still program to statically typed interfaces and classes. In fact, your example seems to prove exactly this, as the dependencies are injected using setters.

  13. I do think there is a delicious irony here, so forgive me if I spell out Andrew McVeigh's last point in a little more detail.

    Your main argument here seems to be that you can trick static analysis tools like Structure101 by writing gruesome, verbose, unmaintainable code using reflection rather than static typing. Yet if the team leady type discovers that one of their junior programmers is producing such garbage, they can swiftly choose to outlaw it. Using ... yep you've guessed it ... static analysis: a rule to say that no-one except {exception-list} may use java.lang.reflect.*.

    The wider issue of static analysis and e.g. dynamic languages is much more interesting. My basic tenet in the findbugs post (which prompted your's here) was that there is clear evidence that architectural decisions were taken at various points in the evolution of the code, only for these to become blurred and ultimately lost over time. The architecture eroded.

    This process (design entropy) seems to me almost inevitable as long as all we have is code/IDE on the one hand, and notional design on the other (the architect's head here, a Word doc there), but never the twain shall meet. Seems to me that this phenomenon is likely to become even more prevalent in a dynamic language code-base, though there is doubtless a counter-argument that overall progress in terms of languages, methodologies and paradigms may serve to counter-act this. For an overview of some of the questions here (albeit without the time dimension), see this post by Ted Neward and specifically the bit about "complexity budget".

    Finally, it is not quite true to say that static analysis on dynamic languages is impossible, though I'll grant you it's harder. I think there is widespread recognition that advances here will lead to lots of useful tooling (code completion, refactoring support, bug hunting, and, of course, Structure101 and its ilk). See PyStructure for an example research project (type inferencing on Python).

  14. "As you know, no compiler will be able to statically detect infinite loops, breach of contracts, array-index-out-of-bounds errors"

    Let's ignore that fact that most people don't use arrays anymore, and that with real Collections you don't need an index to iterate...

    The crux of this argument is that "static analysis can't find x% of my problems so it's useless". A side argument is that "I program in a style that makes static analysis useless".

    To the latter, I say, don't use static analysis if your coding style is that strange. Also, know where static analysis fails and understand what it tells you.

    To the former, I don't know what to say. If static analysis fails to find x% of programming issues at compile time, then dynamic typing means you fail to find 100% of potential issues. Which would you prefer?

    (BTW you can still test staticly-typed code, so you end up with much better coverage with the "x%" guaranteed to work and "y%" tested vs. *JUST* "y%" tested)

  15. It's worth mentioning 2 points:

    1. static analysis won't find every problem (even structural) but it returns no false +ve's
    2. things such as spring (which push the dependencies into XML say) are also able to be statically analysed

    your argument was a non-sequitur because you argue that because static analysis can't find all problems, then it is useless. this is patently not true, because every problem it finds is a real coupling problem.

    Your argument about spring is spurious also. you argue in a previous article that because most things that integrate with spring have tangles, then if you want to integrate with spring you will need tangles. This thinking is so muddy. Have a look at the Spring core with S101 and you'll find that it had literally no tangles in 125kloc of code. It's astonishingly good quality. The Spring guys use s101 also, by the way.

    I've got a bit angry with all of this, which is relatively rare for me. I'm a comp sci phd student with 20 yrs s/w experience including full-time work in Smalltalk and Python, and i have no commercial ties back to S101. My anger comes from poor and presumptive titling (you are so certain with little and flawed evidence), and so many of your conclusions are clearly wrong.

    Andrew

  16. @Anonymous:
    "You could also say that Cobertura "encourages" you to evaluate a method and not check its return value just to see the code coverage percent go up."

    I believe that most people are aware of shortcomings of test coverage tools. On the other hand, the shortcomings of static structural analysis are not that well understood. The most popular (false) assumption is that two unrelated packages can be changed independently.

    @Peter: "stick to that argument, instead of blaming the tools as well.".

    When you rely on a false premise (first argument) you get the justification to do all sorts of mistakes (second argument).

    @Suereth: "Let's ignore that fact that most people don't use arrays anymore, and that with real Collections you don't need an index to iterate..."

    The list is endless. synchronization, null, IllegalArgumentException, UnsupportedOperationException. When you call LinkedList.removeFirst() is your compiler telling you the list is not empty?


    On a more general note. I have no problem with statements such as: "well, we know the shortcomings of the technique we are using, hence its we use it only under the following restrictions".

    However, this does not seem to be the case WRT static structural analysis. (over) generalized claims seem to be common. Here are few of the trade-offs and issues that users of tools such as Structure 101 will have to consider:

    (a) How much more time do I put in making my code bullerproof vs writing tests?

    (b) When I introduce a an interface I loose some of the (static) guarantees of a class. Here's an example:

    public class IntList {
    private final int h;
    private final IntList t;

    public IntList(int h, IntList t) {
    this.h = h;
    this.t = t;
    }
    public final int getHead() { return h; }
    public final IntList getTail() { return t; }
    }

    This list makes the static promise of being non-cyclic. If you extract an interface out of it you will loose this guarantee. What's the trade-off between safety (using IntList) and reusability (using the interface)?

    (c) To what degree do I rely on an analysis technique which cannot distinguish between gruesome code (Reflection) and legitimate code (e.g.: DSL)?

    (d) Acknowledging the blind spots of static structural analysis, how do I prevent my programmers from gaming the system using *legitimate* techniques (e.g.: using DSLs all over the place)?

    It all boils down to the fact that we don't have a single-, absolute-, objective-, metric of software quality (we all wish we had). Hence, we are constantly looking for approximation techniques. We must be careful not to mistake the approximation for the real thing.

    Finally, here is a little thought experiment. Suppose you should decide on a reward plan for the programmer's in your company. The reward should be based on the quality of the code that each programmer produces. What's the weight that should be given to the "Lack of tangled packages" criteria?

  17. @Andrew : "static analysis won't find every problem (even structural) but it returns no false +ve's"

    It's not clear what "positive" means in this context (can be either a compiled program or an error message) so here are two counter examples, one for each case:

    1. x.f() may fail at run-time with a Null pointer exception.

    2.

    void f() {
    LinkedList<Object> ll = new LinkedList<Object>();
    ll.add(1);
    g(ll);
    }
    void g(List<Object> lst) {
    lst.removeFirst();
    }

    This program is dynamically correct. But it will not compile unless lst is downcsted into a LinkedList.

  18. Itay Maman,
    In face of opposition, I should say that I agree with you and the irony of your article.

    I see lots of projects where:
    - The client's manager wants an application while minimizing cost
    - The client's technical manager wants an application maximizing technical quality (I suppose to minimize maintenance cost)
    - And so, when such project is large or risky enough, a technical check is done by the client. And sometimes the client tries to use jdepend or structure101 to assess a theoretical level of quality, but these people rarely do coding and rarely understand the severity of a dependency. They do not understand limits of jdepend or structure101: for example, they give severe remarks on some static dependencies while ignoring totally runtime dependencies. The technical check is finally done with unknown criteria chosen by a tool, forgetting the initial goal.

    That leads us to the irony as I understand it from client vs provider point of view (enhanced from the programmer vs architect one):
    Good but incomplete products such as structure101 or jdepend are often used by providers such as me to assess a technical quality, only based on what is visible in the tool and with the minimal cost. And clients check the same result without understanding what is a problem and what they do not see.

    I know that there is not much of progress when I finally argue with a client about a bit of cyclic dependencies displayed in a tool (by the way, cyclic dependencies are common in libraries used everywhere as shown in this blog)

    And yes there is no objective metric of software quality.

  19. Those who agree with me and those who don't: There's a follow-up post which reflects on this discussion from a somewhat philosophical stand.

  20. @Itay
    "It's not clear what "positive" means in this context (can be either a compiled program or an error message) so here are two counter examples, one for each case:"

    The 1st example you cite can be solved quite easily by the type system in Nice. The problem here is the weakness of Java's type system.

    Your 2nd example compiles fine. Did you mean instead putting something like LinkedList of Integer? Then we get into the limitations of the java generics where this is not a subtype of LinkedList of Object. Again, a more powerful type system would solve this.

    I'm not denying that there exists things outside of the scope of static analysis, i'm saying that I find these types of analysis to be extremely useful (even given that they miss things or have to defer to runtime checks), and that your examples are generally not making the point you want to make.

    Andrew

    p.s. apologies for the rudeness of my previous post. I got a bit worked up about it all. I still feel the same way, but that's no excuse for me not to be polite.

  21. @Andrew

    "The 1st example you cite can be solved quite easily by the type system in Nice"

    Of course, optional types could be of some help, but they cannot solve the general case.

    LinkedList.removeFirst() will throw an exception if the list is empty.

    Can you devise a type system that will ensure the removeFirst() call never fails? Even on a list whose content I just read from an external data source?

    "Your 2nd example compiles fine"

    The List interface does not have a removeFirst() method. We will get a "method not defined" compilation error on method g().

  22. @Itay
    "The List interface does not have a removeFirst() method. We will get a "method not defined" compilation error on method g()."

    Ok, i assumed you'd made a mistake and wanted remove(0). I see your point in this case.

    We've now moved into a discussion about the utility of static typing rather than a discussion of the utility of dependency analysis.

    The reason that I feel that you haven't made a case against dependency analysis is that the examples you showed in s101 represented real (conceptual) dependency issues that existed in the various systems presented. The s101 examples you put fwd didn't do any analysis of the tangles in any way. They just showed that tangles were prevalent. This means (amongst other things) that Java packages are not strong enough to detect bad dependencies. This actually makes dependency analysis more useful in Java, as we are constrained in Java to work within the type system. Ideally dep analysis would be built into the core Java language (a la modules). And bad dependencies in those programs prevent reuse of layers and cause programs to be harder to maintain and understand.

    So, we move onto a discussion of static typing in general, i agree that it does place some constraints on developers. True, it does give false +ves (unlike what i earlier claimed), as all static type systems must necessarily present an approximated (bounded) version of what is acceptable and what is not. It walks a line between convenience (automated checks) and unnecessarily constraining legitimate behaviour. Opinions obviously vary on the utility of this -- i've personally never found it to be an onerous constraint. In fact, one of the worst experiences of my life was being dumped into the middle of a large (and actually well designed) Smalltalk program. I literally had to track back through 20 methods in the calling hierarchy to determine if some of the calls should be valid. Very nasty, and it made me seriously appreciate the benefit of static typing.

    I can't help but feel that part of the problem here is purely presentational. You've raised fair points about whether static typing overly constrains programs, but they come at the very end of a large set of examples that don't seem to support that point because you've done no actual analysis on whether they represent conceptual problems or just problems with static typing.

    Further, you haven't shown that the legitimate cases of static overconstraining you've listed are more than side issues. i.e. it's my view that static typing provides mostly correct enforcement, leaving reflection as a way to express the small % that sits outside this. That's in the main an enormous benefit.

    Andrew

  23. There's a widely held management belief:

    "You get the behavior you incentivize."

    For evidence of the truth of this statement, look at the internet bubble, or the current mortgage/banking situation.

    It seems that the debate covered in the 3 parts of mythbusting is focused on the extremes of the right and wrong of "if" tools like s101 should be applied.

    It seems to me that everyone would be better served talking about how best to apply tools - unless your position is that we're better off not having data/information about our code.

    I agree with the point that data produced by tools is frequently misinterpreted or misused, but I find it is better to battle against those specific situations than to paint everything with a broad brush.

    In my experience, s101 has been an extremely helpful tool at finding design or implementation defects, and at finding opportunities for design enhancements that allowed for greater reuse of existing code.

    An underlying reason for why the code was not as good as it could have been was that our engineering community was lacking information about the structure of the code. Tools like s101 allowed us to dig thru very complex code and accomplish long standing goals by working smarter, not harder.

  24. Dude, you made your point two articles ago: a) static analysis doesnt catch all the problems, and b) results of static analysis are misuses/misinterpreted/overrated. but that's stating the obvious - unless your posts are intended for a non-technical audience that sees static analysis as a silver bullet.

    It is indeed ironic that s101 gives you the visualizations to make this case(no connection to headway, just a happy user).

    anyhow, you're definitely talking in 2 voices - one in the posts thats all fire and brimstone on not just static analysis, but s101 as a poster child of that vile creed; and the other in the comments thats moderate and conciliatory. I'd suggest you let them both meet and post something more coherent, and (as suggested by others) with better examples to buttress your arguments.

    Even better would be to come up with your answer for: If not static analysis, what? You've hinted that that's testing, and I'd like to see you expand that hint to an essay on how testing can completely supplant a priori analysis (of any kind), especially in the same real-world situations where approximations will be made to certify code as "tested", and true coverage is as impossible to achieve as truly untangled code :)

  25. @vinod
    "you're definitely talking in 2 voices - one in the posts thats all fire and brimstone on not just static analysis, but s101 as a poster child of that vile creed; and the other in the comments thats moderate and conciliatory."

    Good phrasing, summarises the discord I felt nicely.

  26. It may very well be the case that a lot of the debate is about presentation. I tried to make my arguments non religious, but evidently it didn't work very well.

    Anyway, to clarify things, I made my claim precise in this post. I believe you'll find it interesting.

  27. I've used static analyzers very successfully in the past.

    JDepend to find cylces (those are contrary to your post a problem. If you want to split tangled classes into different JARs, building and deploying those can be rather hard - you have to deploy all of them)

    FindBugs to find bugs, mostly null pointer exceptions.

    PMD to find lots of general problems with Java code.

    Peace
    -stephan

  28. Hi Stephan,

    As I wrote this piece I hoped that I clearly defined the context and the terms I am using. Obviously, I did a poor job.

    So, I think that Lint-like tools are useful. However, if I have to choose between writing one more test vs. running PMD/Findbugs, I would go with testing.

    As for cycle detection in order to allow decomposition - this is a valid usage, but my feeling is that in most cases it does not always work as expected. First, In the integration test you'd still have to test the decomposed parts together. Second, the resulting boundary lines do not always correspond to conceptual decomposition of functionality.

    I feel that a tool that works in the opposite direction will be more useful: the user will draw the boundaries and the tool will decompose/refactor accordingly.

  29. Hi Itay,

    Much as I am loath to re-open this particular nest of viper, I think it is only fair to let you know that I did revisit some of these issues in my recent Travelin'
    Lite
    post. Long gap I know but, well, I had some other stuff to be doing...

    I'd tentatively like to think that you could agree with all the general points (e.g. distinction between conceptual baggage and statically detectable dependency), though you may well to choose to draw different conclusions. Also, I suspect you may find it helpful e.g. in understanding the difference between static and runtime views of the world.

    For the dubious sake of posterity, I should also mention that it makes the same point on reflection as in my garbled comment above, but
    (hopefully) in much clearer fashion.

    Cheers,
    Ian

Post a Comment