Can the concept of Entropy be used to analyze source code in a useful way?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

I think this is not viable, one could argue that a well-written code base should have higher entropy (disorder). Think to a code base where code snippet is repeated over and over, it can be compressed with high compression ratio because of repeating part(lower entropy/file size), however if you move the code to a separate function the compression ratio will be lower (higher entropy/file size).

So one may think, then I can calculate something like Entropy/CodeLines using the compression ratio as coefficient, to measure code quality, however this has the problem that total random input would look like the best code in the world wich is obviously not.

Indeed compression ratio is a good meter for measuring entropy of code, however both are not good meters for code quality.

Answer 9

Well, the term entropy does not only appear in thermodynamics and information theory, it also appears in the real world of data compression. In that context, the entropy that the compressor sees is equal to the number of bits it produces. (Note that I said "the entropy that the compressor sees", because what is considered entropy depends on the model the compressor uses to describe the input data. This is the reason why different compressors produce files of different size: What is entropy to the one is exploitable structure to the other.)

This can, in principle, be beautifully applied to source code complexity: "Just" write a compressor that only works on fully standard compliant source code, and which compresses it actually parsing it like a compiler would, producing the corresponding syntax tree. Then it can walk this syntax tree, and decide at each node which nodes would have been possible at each point, encoding that node with that knowledge.

So, for instance, if the language allows either an existing identifier, or something enclosed in parentheses, or a product at a specific point, the compressor would count the possible existing identifiers, taking the type information into account (say you have 3 such identifiers), and add 2 for the two possible subexpressions, giving 5 possibilities. So the node would be encoded with lb 5 = 2.32 bits. In the case of the two possible subexpressions, more bits would be needed to encode their contents.

This would indeed give a very accurate measure for the complexity of the code as it is. However, this measure is still useless! It's useless for the same reason that all code complexity measurements are useless: They fail do draw the connection between measured code complexity (whatever that may be) and the complexity of the problem that the code solves. You can always find ridiculously complex solutions to your programming problems to impress your employer with your LOC counts, but no code complexity measure will tell you that the task could have been solved with a fraction of the effort.

Answer 10

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.