2
$\begingroup$

According to A Study of Wheat and Chaff in Source Code, 95% of code is "chaff", or "non-core functionality", whatever that means. Is this really a sensible study? Does the IT World article correctly represent the original paper? It's hard to believe 95% of the code I write is "non-core". Maybe an example would help.

The original paper is A Study of “Wheat” and “Chaff” in Source Code by Martin Velez, Dong Qiu, You Zhou, Earl T. Barr and Zhendong Su.

$\endgroup$
7
  • 6
    $\begingroup$ Most likely better posted to programmers.stackexchange.com. $\endgroup$
    – Ryan
    Feb 12 '15 at 3:04
  • $\begingroup$ I always wondered how it can be that Java IDE's write code by themselves when you keep pressing Ctrl+Space. $\endgroup$ Feb 12 '15 at 6:10
  • 1
    $\begingroup$ Arguably, zip your sources and you get an upper bound on the "true" content. That's not a measure that's helpful for programmers, I guess. $\endgroup$
    – Raphael
    Feb 12 '15 at 7:35
  • $\begingroup$ @Ryan This is about a computer science paper, it's on-topic here. $\endgroup$ Feb 12 '15 at 10:36
  • 5
    $\begingroup$ Have you read the original paper? What are your thoughts, based on your reading of the research paper? We expect you to make a significant effort on your own before asking. It sounds like you are forming your judgements based on a news media article, which is never a good idea. You really need to read the paper, and you need to read the paper before you ask this question here. Once you've read the paper, then you might be in a better position to edit this post to ask a more focused, well-honed question. $\endgroup$
    – D.W.
    Feb 12 '15 at 12:35
5
$\begingroup$

First, note the IT World article grossly simplifies the paper. (This is partly inevitable — if you could summarize the paper in a few accessible paragraph, it wouldn't be a research paper). The 5% figure comes from a particular measure, but the paper considers multiple measures. That being said, I don't think the measures considered in the paper are particularly appropriate.

Let me summarize my understanding of the paper (I've skimmed it, I haven't read it in detail, so I may have made some mistakes or missed important points).

The paper seeks to measure the information density in source code. More precisely, they divide the source code into meaningful units (methods in Java), and they quantify how methods differ from each other, the idea being that if two methods aren't seen to differ then having those two methods instead of just one is content-free overhead (“chaff”).

To extract meaning from source code, they erase distinctions that they consider meaningless. They cut the code of a method into words (which they choose to be lexer tokens), then apply an abstraction function $a$ to each word (in other words, they consider words modulo an equivalence relation: $u \equiv v$ iff $a(u) = a(v)$). The abstraction function is the lexicon. I'll call the set of abstractions of the words in a method ($A(u_1\dots u_n) = \{a(u_i) \mid i \in [1,n]\}$ where $u_1 \ldots u_n$ are the tokens of a method) its abstraction set.

The choice of lexicon is crucial to the measure. At one extreme, you could stick all tokens into the same equivalence class ($\forall u, a(u) = \top$), and then every non-empty method would have the same minset. At another extreme, you could put all tokens in a separate equivalence class ($\forall u, a(u) = u$), and then the minset of a method would only ignore whitespace, comments, the amount of repetition of each token, and the order of token.

The minset of a method in a corpus captures how its set of words differ. A corpus is a set of abstraction sets for all the methods of a set of programs. The minset of a set $S$ in a corpus $C$ is a subset of $S$ (i.e. a subset of the set of words in a method) is a subset $S^* \subseteq S$ such that $S^*$ is not a subset of another element of $C$, and which is maximal under these constraints. Intuitively, anything you add to the minset will not help to distinguish that set from other elements of the corpus.

The 5% figure comes from a fine-grained lexicon where the equivalence between tokens is the trivial one ($u \equiv v$ iff $u = v$). The conclusion is that methods in a typical program are 95% similar.

I don't think the conclusions are particularly relevant for several reasons. The minset measure has major flaws.

If a corpus consists of a single method, then if I understand the definition correctly, its minset will be a singleton (it could be any element, the minset computation is non-deterministic). This shows that there is the correlation between the size of the minset and the complexity of the semantics that the code implements is dependent on the corpus. In order to be meaningful, the corpus has to include all the programs that one would possibly want to write, not just all the programs that were uploaded to a particular repository.

As seen above, the minset measure is also very sensitive to the choice of words and abstraction. To give an extreme example, consider binary code split into bytes, or Turing tarpit languages with a minimal set of primitives and no variables. These will have a very small lexicon, but the ways in which the primitives are combined are highly relevant to the semantics of the program. Even if we don't get into “exotic” languages, consider something like numerical code (built on top of a couple of dozen primitives like add, multiple, while, …), or symbolic processing (built on top of a few primitives like let-rec, cons, fold, …). These tend to express a lot of different behavior by combining a few primitives in rich way. The order and structure of the arrangement of primitives matters a lot, the semantics of a program is not given by the mere set of primitives that it uses.

The paper fundamentally lacks any justification for calling information that isn't captured in the minset “non-semantic” or “chaff”. Their analysis is very sensitive to language syntax and the intuitions are clearly wrong in common examples. The conclusion in the ITworld article is chosen for being sensational, not because it's a realistic measure of the semantic content of code.

$\endgroup$
1
$\begingroup$

The paper says:

The meaning of many sentences survives the loss of words Some words in a sentence, however, cannot be lost without changing the meaning of the sentence.

and:

For human understanding of the purpose and behavior of source code, we hypothesize that the same holds.

They introduce some techniques for digesting code, but I don't see any discussion of whether the results support the hypothesis, specifically, that the digested code retains it's meaning to a human reader.

Looking at the single sample in the paper, I'm skeptical that any person could reliably understand the purpose and behavior of the code. Try it for yourself, what does this code do:

int length = array . for ( i 0 < ; ++ ) { if [ j 1 - ] > temp }

While it's true that many languages are verbose, the approach they use to extract the meaning for human understanding is not effective, so I find their claim, which hinges on retaining the meaning, to be not well supported.

$\endgroup$
2
  • $\begingroup$ I don't see how this answers the question. Verbosity of the language constructs doesn't seem to have much to do with what percentage of code is "non-core functionality". $\endgroup$ Feb 12 '15 at 23:11
  • $\begingroup$ "Verbose" as in "Using or expressed in more words than are needed", or "containing non-semantic fluff", which is exactly the question. My answer is that the paper does a poor job of supporting it's hypothesis, so there is no reason to believe that "95% of code is non-semantic fluff", at least not until someone provides a better supporting argument. $\endgroup$
    – DaveK
    Feb 12 '15 at 23:24

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