Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

It seems logical to me that one could define a context for static source code analysis that included rules to produce a relative value of complexity. I know it is not like in the physical sense because souce code doesn't have "Energy" but I'm betting there have been efforts, at leat academic, to draw a parallel. Has anyone any knowledge of this and if so, to what end has it produced useful results?

share|improve this question
    
I don't have any specific knowledge on that. But as an engineer I do believe that you can apply this concept to anything you want in the universe. "Everything" is energy. Your code can be modeled as an entity, which has energy. –  wleao Aug 1 '11 at 18:07
3  
There are already measures of code complexity - cyclomatic complexity, class length (LOC), method length (LOC), number of fields, number of method parameters, n-path complexity, fan in/fan out, and data flow analysis (DU/DD chains). Work has been done to correlate these to defect density, effort to maintain, and ease of understanding. How does what you are looking for compare to these? –  Thomas Owens Aug 1 '11 at 18:22
    
@Thomas Owens: I think this is exactly what the OP was asking for, please post it as an answer! –  blubb Aug 1 '11 at 18:28
    
@Simon, ok, if you think so. I'm not 100% sure. –  Thomas Owens Aug 1 '11 at 18:29
1  
For a rather unconventional approach, you could either directly compute the data compression ratio for the source code, or compute the data compression ratio after normalization of some sort. (e.g. c2.com/doc/SignatureSurvey) - I do not know how meaningful or useful this would be, but it might give some insight when combined with more traditional metrics. –  William Payne Jun 20 '12 at 20:32
add comment

8 Answers 8

up vote 19 down vote accepted

There are already a number of measures of code complexity:

  • Cyclomatic complexity
  • Class length
  • Method length
  • Number of fields
  • Number of method parameters
  • N-path complexity
  • Fan-in and fan-out
  • Data flow analysis (DU/DD chains)

Work has been done to correlate these to defect density, effort to maintain, and ease of understanding. Some are more meaningful than others, depending on what you are trying to learn from your analysis. I'm not that familiar with the concept of entropy from the physical sciences, but I wonder if tracking measurements and metrics like the ones I named over time, and relating them to defects over time, would be similar to what you are looking for.

You might also be interested in Ivar Jacobson's definition of software entropy and software rot. The general idea of these topics is that over time, as the code as well as the execution environment changes, the software system begins to degrade. Refactoring is seen as a method of minimizing entropy or rot, and, at least in my experiences, the metrics and measurements that I mentioned above would be indicators that refactoring might be necessary in a system or subsystem.

share|improve this answer
add comment

I think you're trying to draw a parallel between thermodynamic entropy and "complexity." The thing is, entropy is a measure of disorder not complexity. I don't believe that the two are equivalent and interchangeable.

The closest analog to thermodynamic entropy is Shannon entropy which measures the amount of disorder in a random variable. This notion is primarily concerned with the amount of "information" in a message.

In that regard, a piece of code can have a lot of information (high entropy) but very low complexity. Think of a program that simply prints out a very long string of arbitrary characters. It has a lot of information, but low complexity.

share|improve this answer
1  
Entropy for source code wouldn't be computed from the same model as that for unstructured text. With a model suited for source code, it should be meaningful to compute an entropy which would not vary widely for arbitrary situations, such as the long string of characters you describe. –  Matthew Rodatus Aug 1 '11 at 18:48
    
So how would you rate the entropy and complexity in the given program? I would argue that it contains a lot of information no matter what model you use. Though the definition of complexity is much less clear. –  tskuzzy Aug 1 '11 at 18:52
1  
Just like it wouldn't make sense to compute thermodynamic entropy for natural language text, it doesn't make sense to use Shannon entropy for computer source code, since the meaning of a program is structured within a different set of rules and patterns (i.e. syntax). Natural language has its own syntax. The model must correspond to the syntax of the domain. Thermodynamic entropy is measured in joules per kelvin. Shannon entropy is measured in bits. Source code entropy would be measured in...different dimensions entirely. I took a stab at what the model would look like in my answer. –  Matthew Rodatus Aug 1 '11 at 19:24
    
I like your answer - i was thinking, for instance, when "bad" code is introduced, a the entropy of the entire environment it exists in increases, i.e. including the coders who have to work harder - in that way maybe there's a practical, if not scientific link to thermodynamics? –  Aaron Anodide Aug 1 '11 at 20:34
add comment

Entropy is a "measure of disorder [or] unpredictability." A wider range of unique patterns in the information (i.e. roughly "more meaning") indicate a higher degree of entropy.

Applied to computer source code, I think that this principle could be useful. However, it would be necessary to design a probabilistic model for source code with which to compute the entropy. (A data structure that comes readily to mind is a graph with different edge types: call, class inheritance, etc.)

Once the model is designed and then populated with the source code of a software application (i.e. frequencies for nodes/edges), the entropy could be computed.

I don't know of any research on this, but my intuition is that a low degree of entropy would mean that the source code reuses common patterns throughout the application (i.e. DRY). Conversely, a high degree of entropy would mean that the source code is high in complexity and has not been factored well.

share|improve this answer
add comment

One way to think of entropy is "average information to be gained", so I think it is better to go back to modeling information. I know of two basic approaches to mathematically modeling information. (Forgive me for giving Wikipedia references, but IMHO they're not bad.)

  • Shannon Information, which looks at symbol sets, probability distributions on those, codes that can transfer information between symbols sets, and lengths of those codes. The general concepts of code efficiency, noise, error detection and correction via redundancy, etc. are couched in terms of Shannon information theory. One way to express information is to say it is the length of the shortest binary code that could represent a symbol. This is based on probability, which is a numerical value assigned to a symbol or event by some observer.

  • Solomonoff (or Kolmogorov) information. Here's another explanation. In this formulation, the information content of a symbol or event is represented by the length of the shortest program that could compute it. Here again, it is relative, not to an observer assigning probability, but to a universal machine that can execute the program. Since every universal machine can be simulated by a universal Turing machine, that means, in some sense, that the information content of the symbol or event is not relative, but absolute.

If I can take the liberty of telling what I think this means in everyday terms, about which I wrote a book, it simply means the complexity of a program is its length, when things like the functional spec and language are held constant, with appropriate allowances for things like comments and name lengths. But there's a problem with this - the "APL tarpit", where conciseness equals incomprehensibility.

It's much better to consider (as I did while studying AI) that the functional spec of the program consists of a mental model, which is not only real, but encoded efficiently, that is, with small enough redundancy that changing one's mind about the requirements can be done without too much danger of making it internally inconsistent - i.e. having a "bug". Then the process of programming is an information channel that takes as input the mental model, and its output is the working source code. Then when a change is made in the mental model, that delta must be fed through the programming process and turned into a corresponding delta in the source code. That delta is easily measured. Diff the source between before applying that delta, and after applying it (completely, with all bugs worked out), and count the number of code blocks inserted, deleted, and replaced. The smaller that is, the better the source code language represents the language the mental model is represented in (in terms of nouns, verbs, and structure). If that measure is somehow averaged over the space of likely functional changes, that is a concept of entropy of the source language, and less is better. There's a term for this - Domain Specific Language (DSL)

I'm sorry if the references are weak / personal, but I think this overall question is a very important one.

share|improve this answer
    
+1 for Shannon and Kolmogorov, both of which are relevant... –  Alex Feinman Aug 3 '11 at 14:01
    
@Alex: I think of Shannon as being applicable at run-time. So for example, you can understand the performance of algorithms in terms of the entropy of decision points, and you can understand normalization of data structure in terms of minimal code. Algorithmic information seems much more linguistic, applying to the suitability of a language for it's expressive purpose, and the algorithm you're trying to make efficient is the mysterious one that cranks in your head when you program. –  Mike Dunlavey Aug 3 '11 at 20:35
add comment

I studied under a professor who used entropy as a measure of the complexity of programs (our textbook was an older edition of this one, some of his pubs are here). There were a number of dissertations at FAU where this was one of the major measures, but the school's website has changed since I last looked, and I am unable to locate where the student thesis/dissertations are now located.

One such dissertation is Information Theory and Software Measurement.

share|improve this answer
add comment

Jon Jagger and Olve Maudal have a slightly different view of Code Entropy, as can be seen in their 2011 Accu conference session Code Entropy and Physics of Software.

They talk about the stability of code being related to whether future developers/maintainers are likely to change that code.

To demonstrate this, they performed a survey with a number of code snippets and the results were quite interesting.

  • There seemed to be a strong bias against one-true-brace style.
  • But a strong bias for embracing single statement if's.
  • There was a strong bias against using temporary variables.
  • There was a strong bias for adding parentheses to make operator precedence obvious.

plus 16 others.

The general trend seemed to be towards making code easier to comprehend, and more difficult to mis-comprehend.

They also look at some of the changes made to a large codebase over the years.

Although the slides on their own suffer from not being a transcript of the session, there are still some interesting points in there.

share|improve this answer
add comment

If you want a definition that is "mathy" in the way entropy is, you might want to look at Kolmogorov complexity, which measures complexity by the minimum amount of code something could possibly be done in. However, this is not complexity of code, but of what you are trying to do with the code. But you might think it's relevant because you could theoretically compare a particular piece of code with the minimal one. However, this is not presently a useful technique for measuring complexity of real world code.

share|improve this answer
add comment

Code has exactly as much entropy as the number π.

Code maintenance and change may introduce entropy (because there's a possible state change involved).

But code is just a big number. With a binary representation.

share|improve this answer
    
thinking that way couldn't you say all code has the same entropy when gzip'd? –  Aaron Anodide Aug 1 '11 at 20:06
    
@Gabriel: That's a different thing. That entropy is the amount of noise among the bits when viewing that number as a sequence of bits. Not viewing at as a single, static number. Source code is a single static number, like 42. Only with a lot more bits. –  S.Lott Aug 1 '11 at 20:07
    
just curious, in this view do decimal 42 and binary 42 have equal entropy or is that comment saying that numbers don't have entropy, and thats the point of it? –  Aaron Anodide Aug 1 '11 at 20:26
    
"numbers don't have entropy". They just are. A representation, viewed as a stream of symbols may have entropy, but the number as a whole is just a number. –  S.Lott Aug 1 '11 at 20:36
    
thanks for taking the time to help me get it. –  Aaron Anodide Aug 1 '11 at 20:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.