On the Lexical Distinguishability of Source Code

Martin Velez, Dong Qiu, You Zhou, Earl T. Barr, Zhendong Su

Abstract

Natural language is remarkably robust against noise; the core meaning of a sentence often survives even when many words are removed. We hypothesize that source code exhibits a similar property, containing essential "wheat" (unique information) and redundant "chaff" (boilerplate or common syntax). By analyzing a corpus of 100 million lines of Java code, we quantify this phenomenon using the Minimal Distinguishing Subset (Minset). Our findings reveal that most methods can be uniquely identified by a tiny fraction of their lexical content—averaging just 1.56 words—providing quantitative evidence for the feasibility of keyword-based programming and advanced code summarization.

Introduction: The Wheat and the Chaff

In natural language, some words are indispensable (like "not" in "I do not like rain"), while others provide structural support but less unique information. Modern software engineering implicitly relies on this concept through tools like code search and completion. However, the extent to which a small subset of words can uniquely represent a complex executable block of code has remained largely unquantified. This study investigates lexical distinguishability: the minimum amount of information required to differentiate one function from millions of others in a massive corpus.

Methodology: Finding the Minset

We treat Java methods as the fundamental unit of code, analogous to sentences. To isolate the "wheat," we define the MINSET (Minimal Distinguishing Subset) as the smallest set of words within a method that does not appear in any other method in the entire corpus.

Finding the absolute smallest subset is an NP-hard problem. To address this, we developed a greedy approximation algorithm. This algorithm iteratively selects the most "distinguishing" words—those appearing in the fewest other methods—until the target method is uniquely identified.

The greedy algorithm iteratively selects tokens to form a Minset, distinguishing a target method from the rest of the corpus.

We evaluated this across several lexicons:

  • LEX: Raw text, including all variable names and literals.
  • LTT: Abstract token types (e.g., IDENTIFIER, INTLIT).
  • MIN1–MIN4: Custom abstractions that progressively filter noise (like local variable names) while retaining structural elements (method names, operators, control keywords).

Dataset and Scale

The study utilized a diverse corpus of approximately 1,000 popular open-source projects (GitHub, Apache, Eclipse, SourceForge), totaling 100 million lines of code and roughly 9 million Java methods. To ensure meaningful results, we focused on methods with at least 50 tokens, filtering out trivial "scaffolding" code like simple getters and setters. A random sample of 10,000 methods was used for intensive MINSET computations.

Key Results: The Sparsity of Information

Our analysis confirms that source code is incredibly sparse in terms of unique information. Most of a program consists of "chaff"—syntactic requirements and common patterns.

  • Average MINSET Size: In the raw LEX lexicon, the average MINSET size is only 1.56 words.
  • Extreme Compression: No method in our sample required more than 6 words to be uniquely identified. On average, MINSETs comprise only 4% of the total words in a method.
  • Yield and Abstraction: In our most refined model (MIN4), over 60% of methods in the 100M LOC corpus could be uniquely identified by a small, meaningful set of keywords.
Distribution of Minset sizes for a 10,000 method sample using the LEX lexicon, showing that most methods are uniquely identified by 1 or 2 words.

Discussion and Implications

One surprising finding is that the size of the "wheat" does not scale linearly with code complexity; even large methods often have tiny MINSETs. Furthermore, while raw text (LEX) is the most distinguishable, it can be noisy due to typos or unique variable names. More abstract lexicons (like MIN4) produce MINSETs that resemble human-readable summaries, suggesting that these mathematical "wheat" subsets align with semantic essence.

Conclusion

This research provides the first large-scale quantitative evidence that source code is highly redundant. The fact that a typical method can be uniquely indexed by fewer than two words has significant implications for the development of alternative programming models, more efficient code search engines, and automated documentation tools. Future work will explore whether these findings extend to other programming paradigms and how to bridge the gap between lexical distinguishability and functional behavior.

Summary updated

Abstract

Natural language is robust against noise. The meaning of many sentences survives the loss of words, sometimes many of them. Some words in a sentence, however, cannot be lost without changing the meaning of the sentence. We call these words "wheat" and the rest "chaff". The word "not" in the sentence "I do not like rain" is wheat and "do" is chaff. For human understanding of the purpose and behavior of source code, we hypothesize that the same holds. To quantify the extent to which we can separate code into "wheat" and "chaff", we study a large (100M LOC), diverse corpus of real-world projects in Java. Since methods represent natural, likely distinct units of code, we use the ~9M Java methods in the corpus to approximate a universe of "sentences." We extract their wheat by computing the function's minimal distinguishing subset (Minset). Our results confirm that functions contain work offers the first quantitative evidence for recent promising work on keyword-based programming and insight into how to develop a powerful, alternative programming model.
BibTeX
@misc{velez2015lexical,
  author = {Martin Velez and Dong Qiu and You Zhou and Earl T. Barr and Zhendong Su},
  title = {{On the Lexical Distinguishability of Source Code}},
  year = {2015},
  eprint = {1502.01410},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1502.01410},
}
Figure