Frequency Distribution of Error Messages
Which programming error messages are the most common? We investigate this question, motivated by writing error explanations for novices. We consider large data sets in Python and Java that include both syntax and run-time errors. In both data sets, after grouping essentially identical messages, the error message frequencies empirically resemble Zipf-Mandelbrot distributions. We use a maximum-likelihood approach to fit the distribution parameters. This gives one possible way to contrast languages or compilers quantitatively.
error-frequency.tex
\documentclass[10pt]{sigplanconf}

\usepackage[T1]{fontenc}
\newcommand{\tts}[1]{{\small \texttt{#1}}}


\def \Beta {\ensuremath{\mathsf{B}}}
\def \Pr {\ensuremath{\mathrm{Pr}}}
\def \E {\ensuremath{\mathrm{E}}}
\def \vF {\ensuremath{\mathbf{F}}}
\usepackage{balance}
\usepackage{times}
\usepackage{amsmath, amssymb}
%\usepackage{amsthm}
\usepackage{url}
\usepackage{prettyref}
%\usepackage{fullpage}
\usepackage{graphicx,xcolor}
%\definecolor{foocite}{rgb}{0,0.75,0}
%\usepackage[colorlinks=true,citecolor=foocite,linkcolor=blue,urlcolor=red]{hyperref}

%\usepackage[dvipsnames]{xcolor}
\usepackage{hyperref}
\usepackage{url}
\usepackage{pgfplots}
\usepackage{prettyref}

\let\proof\relax
\let\endproof\relax
\usepackage{amsthm}
\newtheorem{theoremm}{Theorem}



\newrefformat{theoremm}{Theorem \ref{#1}}
\newrefformat{section}{Section \ref{#1}}
\newrefformat{eq}{Equation \eqref{#1}}
\def\xtheorem[#1][#2][#3]{\newtheorem{#2}[theoremm]{#3} \newrefformat{#2}{#3 \ref{#11}}}
\def\ytheorem[#1][#2][#3]{\newtheorem{#2}{#3} \newrefformat{#2}{#3 \ref{#11}}}
\xtheorem[#][theorem][Theorem]
\xtheorem[#][claim][Claim]
\xtheorem[#][lemma][Lemma]
\xtheorem[#][conjecture][Conjecture]
\xtheorem[#][proposition][Proposition]
\xtheorem[#][eg][Example]
\xtheorem[#][fact][Fact]
\xtheorem[#][corollary][Corollary]
\xtheorem[#][app][Appendix]
\xtheorem[#][alg][Algoritheorem]
\xtheorem[#][step][Step]
\theoremstyle{definition}
\xtheorem[#][definition][Definition]

\makeatletter
\def\url@leostyle{%
  \@ifundefined{selectfont}{\def\UrlFont{\sf}}{\def\UrlFont{\small\bf\ttfamily}}}
\makeatother
\urlstyle{leo}

\newrefformat{sec}{Section~\ref{#1}}
\newrefformat{fig}{Figure~\ref{#1}}

\newcommand{\usanon}[2]{#1}

\begin{document}

\special{papersize=8.5in,11in}
\setlength{\pdfpageheight}{\paperheight}
\setlength{\pdfpagewidth}{\paperwidth}

\conferenceinfo{PLATEAU '15}{Month d--d, 20yy, City, ST, Country}
\copyrightyear{2015}
\copyrightdata{978-1-nnnn-nnnn-n/yy/mm}
\doi{nnnnnnn.nnnnnnn}

\title{Frequency Distribution of Error Messages}

\authorinfo{David Pritchard}
           {Center for Education in Math and Computing, University of Waterloo, Canada\thanks{Work started while located at Princeton University and completed at U.~Southern California. Currently located at Google Los Angeles.}}
           {dagpritchard@uwaterloo.ca}

\maketitle
\begin{abstract}
Which programming error messages are the most common? We investigate this question, motivated by writing error explanations for novices. We consider large data sets in Python and Java that include both syntax and run-time errors. In both data sets, after grouping essentially identical messages, the error message frequencies empirically resemble Zipf-Mandelbrot distributions. We use a maximum-likelihood approach to fit the distribution parameters. This gives one possible way to contrast languages or compilers quantitatively.
\end{abstract}

\category{D.3.4.}{Programming Language Processors}{Compilers, Run-time environments}

\keywords
	Error messages, empirical analysis, usability, education.


\section{Introduction}
This work started as an offshoot of Computer Science Circles (CS Circles) \cite{PV13,PGV15}, a website with 30 lessons and 100 exercises teaching introductory programming in Python. It contains a system where students can ask for help if they are stuck on a programming exercise. Often, students reported being stuck because they could not comprehend an error message, asking for a better explanation of what the compiler/runtime was trying to say. E.g., the message
$$\texttt{\small SyntaxError: can't assign to function call}$$
might not be understood by a novice who wrote \verb|sqrt(y)=x|.

Motivated by this, we decided to systematically improve the error messages that students received. There is copious literature on writing good error messages \cite{MM67,H74,S82,T10,MFK11a,MFK11b}, but how can this advice be incorporated into the programming ecosystem? One approach would be making upstream improvements to the compiler/runtime, but this can take a long time, and not all audiences would appreciate the changes that would most benefit novices. A second approach would be to write a tool that analyzes code from scratch, looking for common syntactic bugs or likely semantic mistakes. The literature includes many such tools: see \verb|checkstyle|, \verb|findbugs| and \cite{J85,S95,L02,HMRM03,FCJ04,LFGC07}.

We chose a more lightweight approach: augmenting the normal error messages with additional explanations. To wit, we compile and execute the code as usual, and then add a beginner-appropriate elaboration of the resulting error message, implemented by rendering the normal error with a clickable pop-up link to the explanation.
This augmenting-explanation approach has been previously used on a small scale with Java compiler errors \cite[\S 5.2]{Coull08}, Python runtime errors \cite[\S 5.2.1]{Hartz12}, and C++ STL compiler errors \cite{Zolman05}.

It has long been observed that ``a few types of errors account for most occurrences'' \cite{RD78}, see also \cite{Denny12}. In order to make sure that a small number of explanations would be useful as often as possible, we had to answer the following question: \emph{what error messages are the most common}? Counting error message frequencies has a long history, starting from assembler \cite{MM67,CH76} and \verb|SP/k| \cite{H74}, with renewed interest more recently, using much larger data sets \cite{JCC05,Jadud05,Denny12,BKMU14,SSEAB14}.

Using with the history of all previous submissions, we determined the essentially distinct error messages and their frequencies (see Section~\ref{sec:data}), available online at \url{http://daveagp.github.io/errors}. We wrote explanations for the 36 most common messages. Regular expressions were used to aid the implementation. At the most basic level, some errors were made more readable by elaborating them into a full paragraph of text rather than a one-line message. Some explanations include concrete examples of code that causes the same error message, and a description of how to fix it. See \cite{MM67,H74,S82,T10,MFK11a,MFK11b} for advice on writing error messages. %This was implemented in August 2013.
Given a large data set, the work involved in this group-and-explain approach is modest and not technically challenging, so we would recommend it in any beginner-facing system. Moreover, in internationalized settings, one can then add explanations in other languages (this has been implemented in CS Circles' Lithuanian translation).

% (Handle both compile-time and run-time errors uniformly. Regex. Keep examples and write to the examples. Use consistent version of compiler/runtime.)

This paper compares and contrasts the most common error messages in CS Circles with those in another programming language. The Blackbox project~\cite{KU12,BKMU14} is a large-scale data collection-and-sharing project using BlueJ, a Java programming environment oriented at beginners. We obtained the error messages from all recorded compilation and execution events, grouping and counting the essentially different messages like we did for the Python data set. Comparing the two data sets, we found that both error message frequency distributions resembled the same family of distributions, the Zipf-Mandelbrot distribution~\cite{Mandelbrot53}. For these data sets, this means that for any integer $k,$ the frequency of the $k$th most common error is approximately proportional to $1/(k+t)^\gamma$ where $t$ and $\gamma$ are parameters of the data set. In order to determine the best values for these parameters, we propose using a simple maximum-likelihood approach.

\subsection{Discussion and Other Related Work}\label{sec:related}

Orthogonal to purely quantitative analysis, a large body of work focuses on manual categorization of errors. This allows researchers to get more accurate results, and to precisely understand the psychological state of the user, rather than focus on the compiler-generated error messages themselves. Good reasons for doing this include that ``A single error may, in different context, produce different diagnostic messages'' and that ``The same diagnostic message may be produced by entirely different and distinct errors,'' see \cite{McCall14}. This analysis also helps measure whether a compiler's error messages are appropriate (e.g., see~\cite{RD78,Johnson90}). This analysis is  important for compiler designers, language designers and educational research, but it is not our focus. %Also, manually categorizing errors is not feasible at very large scales.
% manual categorization of errors: 1985 pascal; 1986 spohrer; 1990 prolog; 2007
% one or the other: 2011 effectiveness of error messages
% own categorization: 2014 brown, and 2015 jamie spacco, following 2003 hristova

The comparison of error message frequencies between different languages raises many interesting open-ended questions. Even within the same language, some compilers are significantly better or worse than others; see Brown's amusing crowdsourcing of Pascal error messages~\cite{Brown82,Brown83} as well as \cite{NPM08,T10}. One way to view different error message distributions is to imagine the extremes: the worst possible language would only ever say ``?'' without elaborating (this has been formally evaluated, see~\cite{S82}), while the best possible language would, like a human tutor, always give a perfectly adapted explanation. The exponent $\gamma$ in our work is one way to measure where a language sits between these extremes. However, simpler measures such as entropy could also be used. Also, a single quantitative measure should not be treated as paramount without context. When comparing languages/compilers (e.g., \cite{McIver00}), statistical fitness is less important than overall usability, including measures like time between errors and time to achieve user goals.

A notable alternative approach to improving student feedback based on large-scale data, rather than focusing on error messages, is the HelpMeOut system \cite{HMBK10}, which uses a detailed repository of past student work sessions to find old errors similar to new ones and make suggestions of how to fix them.

To our knowledge, this paper is the first one to examine any link between programming error messages and statistical distributions. The special case $t=0$ of the Zipf-Mandelbrot distribution is known as the power law distribution. It arises empirically in data sets such as the frequency of distinct words in books, of links in webpages, and of citations in literature. Caveats apply here~\cite{CSN09,GMY04,Newman05}, including: that generative explanations of how these distributions could arise are tenuous; that near-power-law data sets may be even closer still to other distributions; and that analyzing such data sets has common pitfalls like using linear regression. Another caveat for our work is that the distributions of error messages will depend on the nature of the users, and the kind of setting in which the work is collected. In our case, both data sets come from a very large, open project intended for beginners. We anticipate that a data set where students only work on a fixed set of exercises could be skewed in some way, but both BlueJ and the CS Circles ``console'' allow students to do any sort of open-ended programming.

See \cite{PNFB05} for discussion of power laws in runtime object-reference graphs of industry-scale computer programs.

%Newman~\cite{Newman05} gives an in-depth study of how to best determine $\gamma$ and applies these methods to a dozen diverse data sets including book sales, earthquake magnitudes, personal wealth and surname frequencies.

%It must be said that very few power law studies are able to give a completely satisfactory explanation as to \emph{why} their data could follow a power law. The problem is not that the power law is unnatural --- there are a number of simple mechanisms such as the Principle of Least Effort~\cite{Zipf49} (which obtains a word frequency power law from the constrained maximization problem of maximizing the entropy/communicative capacity of a language relative to the length of the words).
%that generate power laws \cite[\S IV]{Newman05}. However, amongst the many data sets in which approximate power laws appear, the majority have only a tenuous connection to any known generative model. Additionally, there are other distributions such as log-normal distributions that can be conflated with power laws. We do not try to solve these problems here and instead focus on finding a plausible overall shape for our error distributions.

\section{Data Sets}\label{sec:data}
Our first data set is the Python corpus from CS Circles. Amongst the first 1.6 million code submissions, %representing all usage until mid-February of 2013,
about 640000 resulted in an error.
%In more detail, the actual code at the time of submission was saved rather than saving each error message. Then, in a single batch, all submitted code was re-executed under Python 3.3.0, to remove the possibility that the corpus would mix error message behaviors from different versions of Python.
Our second data set is the Java corpus from BlueJ Blackbox. We specifically considered %data collected until the end of October 2013 from two sources:
the ``compile'' events, of which there were about 8 million, half of which produced an error, and the ``invoke'' events, of which there were about 5 million, about 260000 of which produced a syntax error and 180000 of which produced a run-time error. We did not include the codepad or unit test events, both of which are an order of magnitude smaller. %Within that data set, we used data collected during compilation events (\verb|compile| table rows, with only the first error per compilation event) and data collected during method invocations (\verb|invocations| table rows).

%\item A smaller Java data set (about 7000 messages) consisting of syntax and run-time errors from an online exercise system called ``Websheets."% (see Figure \ref{fig:websheets}).
%    This system is currently deployed in beta for optional practice exercises in an introductory computer science course. In this system, each exercise is presented in a text editor with a frame of some read-only code and several editable areas. The student must fill in the blanks, and upon submission their code is compiled, executed, and the results compared to correct reference solutions. For the purposes of this study it is meant as a close Java parallel to CS Circles in that (1) most students are using it with the express goal of completing specific exercises, (2) it presents compiler and run-time errors in a unified manner to the students, and (3) the curriculum is very similar to that of CS Circles. This data set is the only non-open one: it is only available to students at the university where it is deployed. It does not have any ``console" where arbitrary code can be entered.

%\end{enumerate}
%\begin{figure}
%\centering
%\includegraphics[width=9cm]{websheets.png}
%\caption{The Websheets user interface. The yellow indicates the editable regions. When the button is clicked the code is %submitted to the server and graded.}
%\label{fig:websheets}
%\end{figure}

In both cases, following \cite{NPM08}, we only counted the first error message. This tends to be the most accurate error (since a syntax error can cause new valid parts of the program below to be reported as errors) and it is also the error that the programmer is most likely to pay attention to and fix first. Moreover, CS Circles only shows the first error message in its user interface; and even for a UI like BlueJ that shows multiple errors, beginner students often (by habit or by instruction) fix only one at a time and then recompile/re-run.\footnote{It would not be invalid to investigate data sets where all errors are reported and counted, but a worry is that it might say more about the statistics of chain effects in syntax errors and less about the actual underlying bugs. Two other strategies, ``count-all'' and ``count-distinct,'' are used in~\cite{SSEAB14}, though their study participants were professionals and not novices.}

%Since the version of Python 3 used on CS Circles was upgraded over time, we re-ran all submissions again under the latest version of Python. This would remove any spuriously distinct errors whose handling or message wording changed between versions of Python. This was not possible with the Java corpus, although we are not aware of any specific deficits this caused.

After obtaining these raw data sets of hundreds of thousands of error messages, we had to count how many time each distinct message occurred.
It is necessary to ``sanitize'' the data by removing parts that pertained to specifics of user code rather than the kind of error. For instance,
\tts{NameError: name 'x' is not defined} should be understood by our system to be essentially the same error as \tts{NameError: name 'sum' is not defined} so that the same explanation will appear in either case. The sanitization was an iterative process. Simple heuristics handled most cases correctly, and in total we needed about 20 sanitization rules for Python and 50 for Java, implemented using regular expressions.

There is a question of how far one should sanitize. Should these two error messages be considered the same?
{\small \begin{verbatim}
RuntimeError: maximum recursion depth exceeded
   while getting the repr of a list
RuntimeError: maximum recursion depth exceeded
   while getting the repr of a tuple
\end{verbatim}}
Overall we tended to use fewer sanitization rules rather than more (considering the above to be different); a similar approach was used in \cite{SSEAB14}. Conceptually, to fix a single objective goal for sanitization, we imagined that each category should uniquely correspond to a single line of source code of the compiler/runtime where the error is first detected.

Another step in sanitization was to remove any non-English error messages, to avoid inadvertently seeing the same patterns repeated in multiple languages, which might affect the results. This was done by removing all messages with non-ASCII characters, and manual filtering.

% trying to write a function call with too many arguments in Java is always caught at compile time with message
%\\ {\small \texttt{Error:~no~suitable~method~found~for~\emph{func}(\emph{args})}},
%\\But in Python it is each function's responsibility to check its arguments, and while many functions use common mechanisms to do this they are not totally uniform, for example one sometimes sees {\small\texttt{func() takes at least \# arguments (\# given)}}, or {\small \texttt{func() expected at least \# arguments, got \#}}, or other variants.

%With the cautionary observation that the two languages might not be directly comparable, we proceed with our analysis.

%BluJ also does some minor reprocessing of error messages from the Java compiler before sending it to the user, and the Websheet system has a syntax preprocessor that does things like ensuring that each filled-in blank has matching parentheses before calling the Java compiler. This should be kept in mind when trying to compare the systems, although the data does not lead us to believe that they affect the overall characteristics of how the error messages are distributed.


\subsection{Overview of Data Sets}\label{sec:datasets}
The Python data set yielded 309710 syntax errors and 333538 compile-time errors. The Java data set yielded 4002822 compile-time errors and 129650 run-time errors.  %The Websheets data set yielded 6678 syntax errors (including preprocessor errors and Java compile-time errors) and 769 run-time errors (including limits enforced by the grader, like running longer than the time limit).
Note that the Java data set has a much smaller proportion of run-time errors than Python (only about 3\% rather than almost half). But to a degree, this difference is inherent in the language, since many errors that would occur at compile-type in Java's strict typing-and-scoping system are not encountered until run-time in Python. %Accordingly, to aid in comparison, we categorized errors not only according to whether they are run-time errors or syntax errors, but we also separately noted those types of errors that would occur at compile-time in Java and at run-time in Python.

After sanitization and grouping, the Python data set yielded 283 distinct error messages. Of these, 17 occurred exactly twice and 42 occurred only once (for example, ~\tts{ValueError: Format specifier missing precision} and \tts{SyntaxError: can't assign to Ellipsis}). The Java data set yielded 572 error messages in total; 65 occurred exactly twice and 127 occurred only once (for example, \tts{com.vmware.vim25.InvalidArgument} and \tts{cannot \\ create array with type arguments}).

Errors are not completely parallel for both languages. For example, Java allows function overloading, i.e.~two functions with distinct signatures but the same name. In Python, this must instead be implemented by a single function that takes different actions depending on the runtime number and type of its argument(s). It is the function's responsibility to generate the error message. It turns out that not all such functions generate identical messages and so the single Java error message \verb|no suitable method found| corresponds to more than one distinct Python error message:
\\ {\small \texttt{f~argument~must~be~a~string~or~number, not T}}
\\ and {\small \texttt{f~arg~1~must~be~a~type~or~tuple~of~types}}.

\eject

\begin{figure}[tb]
\centering
\includegraphics[width=8cm]{11-06-py-loglog.pdf}
\includegraphics[width=8cm]{11-06-bluej-loglog.pdf}
%\includegraphics[width=8cm]{11-05-websheet-loglog.pdf}
\caption{The two data sets for our study. The CS Circles data set is Python, while BlueJ is Java. The plots are log-log.}
\label{fig:rawdata}
\end{figure}

The 5 most common Python errors were:
{\small
\begin{verbatim}
179624 SyntaxError: invalid syntax
 97186 NameError: name 'NAME' is not defined
 76026 EOFError: EOF when reading a line
 26097 SyntaxError: unexpected EOF while parsing
 20758 IndentationError: unindent does not match
       any outer indentation level
\end{verbatim}}

The 5 most common Java errors were:
{\small
\begin{verbatim}
702102 cannot find symbol - variable NAME
407776 ';' expected
280874 cannot find symbol - method NAME
197213 cannot find symbol - class NAME
183908 incompatible types
\end{verbatim}}

%The 5 most common Websheets errors were:
%{\small
%\begin{verbatim}
%1351 * text area must not be empty
%1105 error: cannot find symbol
%416  * opening (/[/{ not followed by matching close
%398  error: ';' expected
%395  * must end with a semicolon (;) or a {block}
%\end{verbatim}}
%The asterisks indicate preprocessor errors rather than Java compiler errors.
%It had 75 errors in total; 4 occurred exactly twice and 8 occurred once (e.g. \tts{error: continue outside of loop}). The sanitization is slightly more coarse than for the BlueJ errors since only the first line of each error message was stored.


We plot both data sets in Figure~\ref{fig:rawdata}. The $x$-axis measures the rank of each error message (with 1 being the most frequent) and the $y$-axis measures the number of times each error occurred. Using a logarithmic scale is necessary for the changes in the $y$-axis to be visible, and we also use a logarithmic scale for the $x$-axis. Notice that both data sets give rise to similar distributions; in the rest of the paper we will try to describe them in a common framework.



\subsection{Notation}
For any given data set, we will use $N$ to denote the total number of errors logged, and $M$ for the number of distinct error types. For example, the Python data set has  $N=643248$ and $M=283$. Let $F_k$ denote the number of times that the $k$th-most common error occurred, e.g.~$F_1 = 179624$ for Python. We will also write $F_{\max} := F_1$ as an alternate symbol for the same value, when we wish to emphasize that it is the maximum frequency. The smallest frequency $F_M$ is 1 for both of our data sets. In lexicography, the items occurring just once are known as the \emph{hapax legomena} of the corpus. An \emph{$f$-legomenon} is any error message that appears exactly $f$ times. We will use the symbol
$$\#F^{-1}(f)$$
to denote the number of $f$-legomena. The first few counts of $f$-legomena in our data sets is listed in Table~\ref{table:legomena}.
\begin{table}
$$
\begin{array}{|c|c|c|c|c|c|c|}
\hline
\#F^{-1}(f) \textrm{ where } f \textrm{ is:}& 1 & 2 & 3 & 4 & 5 & 6 \\
\hline
\mathrm{Python}& 42 & 17 & 19 & 13 & 6 & 4\\
\hline
\mathrm{Java}& 127 & 65 & 31 & 17 & 18 & 15\\
%\hline
%\mathrm{Websheets}& 8 & 4 & 2 & 3 & 2 & 2\\
\hline
\end{array}
$$
\caption{Number of $f$-legomena in each data set.}
\label{table:legomena}
\end{table}

%Recall that our study was initiated due to wanting to write longer and more detailed versions of the most common error messages. How many error messages would we have to explain, if we wanted this help to apply to students 75\% of the time, or 95\% of the time, or 99\% of the time? These values are stated in Table~\ref{table:Pareto}.

%Note that there is a pattern: no matter how many more error messages we have explained, we will need to explain approximately 20-30 additional messages in order to cover 80\% of the remaining unexplained errors. This is a characteristic of \emph{power law} distributions.% and so we began to investigate whether our data followed such a distribution.


%\begin{table}
%$$
%\begin{array}{|c|c|c|c|}
%\hline
%& 75\% & 95\% & 99\% \\
%\hline
%\mathrm{Python}& 16 & 47 & 91\\
%\hline
%\mathrm{Java}& 12 & 41 & 75\\
%\hline
%\mathrm{Websheets}& 13 & 34 & 52\\
%\hline
%\end{array}
%$$
%\caption{Number $k$ of error message types for which the $k$ most common messages
%constitute 75\%, 95\%, or 99\% of the entire data set.}
%\label{table:Pareto}
%\end{table}

\section{Power Law Distributions}
When studying frequency counts of different objects, a discrete \emph{power law} distribution is one in which the frequency $F_k$ of the $k$th most common item is proportional to $1/k^\gamma$. As mentioned in the introduction, power law distributions provide good fits to many unrelated empirical distributions. A common example is that in the novel \emph{Moby Dick}, the frequency of the $k$th-commonest word is approximately proportional to $1/k^{1.05}$. ``Zipf's law'' is sometimes used as a synonym for the discrete power law, but sometimes also refers to the special case $F_k \propto 1/k$ where $\gamma=1$. There is also a large body of work on continuous power laws, where one sorts items by some magnitude that takes on continuous values, and examines the relationship between rank and magnitude. See many examples of both types in \cite{CSN09}.

Note that sanitization of error messages is particularly important because of the fact that many natural languages follow power-law curves. If we did absolutely no sanitization, then our error message distributions would have significant aspects determined by the frequency distribution of variable names chosen by users, and finding a power law describing the latter would be less surprising, given that natural language is already known to exhibit power law behaviour.

We now turn to analyzing our data sets from the power law perspective. Do they approximately satisfy a power law? This did not appear to be the case: a power law, when plotted on a log-log scale, should give a straight line, but it is clear from Figure~\ref{fig:rawdata} that this is not an accurate description of our data set.

\subsection{Zipf-Mandelbrot Distributions}\label{sec:zmd}
There is a generalization of power law distributions called the \emph{Zipf-Mandelbrot} family of distributions. These distributions are defined, using two parameters $t$ and $\gamma$, by
$$F_k \propto \frac{1}{(k+t)^\gamma}.$$
Such a sequence should appear linear on a log-log plot provided that along the $x$-axis, we plot the logarithmic positions of $(k+t)$ rather than of $k$. When we tested plotting these distributions in this modified way, for an appropriate value of $t$, we obtained a much more persuasive fit: in Figure~\ref{fig:rf}, which has the shift $t=60$, the points very nearly fall on a line. This shift was obtained by trial-and-error, and the line drawn in has slope $-\gamma = -6.3$. In the rest of the paper we aim to give a more principled way of estimating $t$ and $\gamma$.% and checking the quality of the fit.
\begin{figure}[b]
\centering
%\includegraphics[width=8cm]{10-27-py-rf}
\includegraphics[width=8cm]{10-27-py-srf}
\caption{%Left: a log-log rank-frequency plot for the Python data set, with $k$ on the $x$-axis and $F_k$ on the $y$-axis. Right:
The Python data set with the (pre-logarithmic) $x$-axis shifted by $t=60$, and a straight line with slope $-\gamma = -6.3$ that approximately fits most of the data.}
\label{fig:rf}
\end{figure}


%It does appear to us that the Zipf-Mandelbrot law gives at least a decent overall high-level description of our data sets.
Is a Zipf-Mandelbrot distribution plausible? Here is one argument that, if we accept that power laws can arise in natural settings, that there is reason to suspect that Zipf-Mandelbrot laws can too. It is not meant to give an exhaustive explanation, just an argument for plausibility. Suppose we start with a power law, and then coalesce several items together. I.e., replace several distinct error messages with a single unified message having the sum of their frequencies. (In a list of English words, the analogy would be that a single word has multiple meanings.) The effects of this message-merging would be twofold: the resulting new message would be an outlier to the original power law curve; and the remaining data points, when plotted on a rank-frequency scale, would be shifted several positions to the left, i.e.~they would follow a Zipf-Mandelbrot distribution instead of a power law distribution. This is indeed a plausible scenario for the Python data set! The most common error, \verb|SyntaxError: invalid syntax|, is very generic. It can be obtained by writing two tokens in a row (such as forgetting a comma or quote marks), using an assignment statement in place of a conditional expression (such as using \verb|if a=b:| instead of using \verb|==|), by mismatching parentheses, etc. %(We give this argument only for plausibility and not because we think it explains everything satisfactorily.)


\subsection{Consequences of a Zipf-Mandelbrot model}
What behaviour does a Zipf-Mandelbrot model predict? It postulates that there is some innate ordering of error messages, from most frequent to least frequent, so that the inherent probability $F^*_\ell$ of the $\ell$th most frequent error message is proportional to $(\ell+t)^{-\gamma}$. The reason that we use the subscript $\ell$ here is that our concrete data set arrives via sampling from the inherent distribution. So like a sampling error, the observed ordering of messages from most to least frequent is not necessarily the exact same as the innate ordering.

%In accordance with the apparent Zipf-Mandelbrot behaviourWe permit that there may some outliers when $\ell$ is small. This seems to be the case for our data, but these outliers are of no great consequence in terms of predicting what would happen in a larger data set --- to compute how many hapax legomena would have occurred in twice as large a corpus, only the ``long tail" matters.

An interesting aspect of this model is that it assumes $F_\ell^* \propto (\ell+t)^{-\gamma}$ continues to hold for arbitrarily large $\ell$. Can this be plausible: is the total number of possible errors infinite? We will accept this as a reasonable hypothesis, which if not literally true, could continue long enough to be consistent with the size of any measured data set, for the following reason, using Python as an example.  The most common errors we see are the ones in the Python core code (the syntax errors, and runtime errors from the ``builtins''). Less frequently we start to see errors from Python modules, such \tts{ValueError: math domain error} within the \verb|sqrt| function of the \verb|math| module. While this is the only module taught on the site, users have occasionally submitted code using other common modules like \verb|time|, \verb|random| and \verb|functools|, each of which comes with its own specific errors. Moving on, there would be errors from rarely-used modules, then even after this, modules that users may with more or less frequency import (or copy in) themselves. For example, we observed a \tts{mainfile: error: must provide name of pdb file} error caused by someone who copied in a Python program for use with the X-PLOR biomolecular structure determination software~\cite{SKTM03}. The same phenomenon happens in the Java data set. So errors with arbitrarily small inherent frequency are not unreasonable despite the finite size of the languages.

\section{Analysis}
To fit our data to a Zipf-Mandelbrot distribution, several approaches are possible. For power laws, the naive approach, using a least-squares fit to a linear log-log plot (c.f.~Figure~\ref{fig:rf}) is known to introduce errors~\cite{GMY04}. Rather, we will follow Newman~\cite{Newman05}, who considered maximum likelihood estimation methods for power laws. Some work will be needed to extend this to Zipf-Mandelbrot distributions.

The method in \cite{Newman05} involves a particular way of processing the data; let us mention the motivation. The direct approach to maximum likelihood estimation would be to determine the $\gamma$ and $t$ that maximize $\prod_k (C/(k+t)^{\gamma})^{F_k}$ where $C$ is the normalizing constant with $C \cdot \sum_{k=1}^\infty (k+t)^{-\gamma} = 1$. Izs{\'a}k~\cite{Izsak06} suggests this. But trying this approach gives unsatisfactory results with any of our data sets --- the curves produced fit the data very poorly except in the regime of $F_1$. The calculation goes wrong because it is too heavily biased by the highest-frequency errors. (For Zipf-Mandelbrot in particular, if the argument in Section~\ref{sec:zmd} were to be true, then it should be no surprise that fitting to $F_1$ would be problematic, since $F_1$ would be an outlier from the norm.)
Also, the most likely fit entails that the innate order exactly matches the observed frequency-ordering of error messages~\cite{Izsak06}, which is itself unlikely.

\subsection{Probabilities of Frequencies}
This motivates the maximum likelihood method on frequencies~\cite{Newman05,CSN09}. It starts by taking a different view of the data set. Using the Python data set as a concrete example, we imagine the frequency vector $\vF = (179624, 97186, \dotsc, 1, 1)$ itself as being an unordered set of $M$ data points from a parameterized distribution --- given a new error message, how frequent is it? This distribution-on-frequencies is a transformed version of the inherent distribution $F^*$, and also depends on the data set size. The goal, then, is to choose the parameters so as to maximize the likelihood of observing $\vF$.

The analysis in~\cite{Newman05,CSN09} primarily achieves rigor for continuous distributions. For discrete distributions, it turns out that the distribution-on-frequencies is actually given by another distribution which seems to have been first studied by Evert~\cite{Evert04}. To describe it we recall the $\Gamma$ function, which is the (shifted) analytic continuation of the factorial function, satisfying $\Gamma(n)=(n-1)!$ at positive integer values and $\Gamma(n)=(n-1)\Gamma(n-1)$ on its whole domain. The beta function, another standard function, is a continuous analogue of the binomial coefficient, defined by
$$\Beta(x, y) := \Gamma(x)\Gamma(y)/\Gamma(x+y).$$

Then, finally, the \emph{Evert distribution} is the frequency distribution, parameterized by one parameter $\alpha$, defined by
$$\textrm{frequency of $f$} \propto \Beta(f+1-\alpha, \alpha).\label{eq:evert}$$

It is involved in our analysis for the following reason:
\begin{proposition}\label{proposition:evert}
Suppose that we draw samples from a discrete Zipf-Mandelbrot distribution with parameters $\gamma$ and $t$.
If the number of samples is large, then for all small $f$, the expected number of $f$-legomena is proportional to $\Beta(f+1-\alpha, \alpha)$ where $\alpha = 1+1/\gamma$.
\end{proposition}

Paraphrasing, this says that the distribution-on-frequencies for a discrete Zipf-Mandelbrot distribution is the Evert distribution. This result was obtained by Evert~\cite{Evert04} though he expressed it in terms of ``type density functions.'' We re-prove it in \prettyref{app:b}.

We remark that the proof of \prettyref{proposition:evert} remains valid even if the discrete Zipf-Mandelbrot distribution is perturbed by altering some of the highest probabilities, which ensures that it is still valid even if outliers \`a la \prettyref{sec:zmd} occur.

\subsubsection{Remarks}
In~\cite{Newman05,CSN09}, the focus of the analysis is on continuous power law distributions, and for that, the analogue of \prettyref{proposition:evert} is to use a simple power law with exponent $\alpha$ instead of an Evert distribution. Though the Evert distribution is not mentioned in~\cite{Newman05}, it is remarked that the another distribution, the Yule distribution, is an ``an alternative and often more convenient form'' of the discrete power law. These conveniences are mathematical in nature: the normalizing constant, expectation, variance, and moments of the Yule distribution have nicer closed forms than a pure power law. (And it is reasonable to use in power law analysis because up to a scaling factor, the Yule distribution becomes a discrete power law in the limit.)
These conveniences holds for the Evert distribution too, since Evert and Yule differ only by a shift. For instance, our fitting code utilizes the identity
$\sum_{f=1}^{F_{\max}} \Beta(f+1-\alpha,\alpha) = \Beta(2-\alpha,\alpha-1) - \Beta(F_{\max}+2-\alpha,\alpha-1).$

\subsection{Maximum Likelihood}
The Evert distribution allows us to compute the most likely value of $\alpha$ for the collection of frequencies $\vF.$ Writing $E^\alpha_f$ for $\Beta(f+1-\alpha, \alpha)$, and $C^\alpha$ for the normalizing constant with $C^\alpha \cdot \sum_{f=1}^{F_{\max}} E^\alpha_f = 1$, we seek the $\alpha$ that maximizes $$\prod_{k=1}^M C^\alpha \cdot E^\alpha_{F_k}.$$
This can be determined numerically using binary search, using logarithms since the numbers involved are very small. Then we determine the parameter $\gamma$ using $\gamma = 1/(\alpha-1).$

The only remaining issue is how to determine the value of the shift parameter $t$ that has maximum likelihood. \prettyref{proposition:evert} does not help since $t$ plays no role in its conclusion. (The reason for this apparent paradox is that the approximation guarantee of \prettyref{proposition:evert} is only valid for small frequencies.) Nonetheless, we can determine a value for $t$ using some ideas from the analysis of the continuous case~\cite{Newman05,CSN09}.\footnote{The authors of \cite{Newman05,CSN09} note that the continuous model reasonably resembles the discrete model when thinking about larger frequencies; the smallest continuous variables are the ones that would have to be distorted the most in order to become quantized. Thus, the inaccuracies of \prettyref{proposition:t} are complementary to those of \prettyref{proposition:evert}.}

\begin{proposition}\label{proposition:t}
Let $\alpha = 1+1/\gamma$. Suppose we draw a sample from the bounded continuous power-law distribution with exponent $-\alpha$ and domain $(1, (\frac{t}{t+M+1})^{-\gamma})$.
Then the $(M+1)$-quantiles of this random variable are proportional to $(t+1)^{-\gamma}, (t+2)^{-\gamma}, \dotsc, (t+M)^{-\gamma}$. Furthermore, the choice of $t$ that maximizes the likelihood of observing $\vF$ is $t = (M+1)/(F_{\max}^{1/\gamma}-1)$.
\end{proposition}

The first conclusion says that a ``typical'' draw of $M$ items from this continuous distribution-on-``frequencies'' is a model for the Zipf-Mandelbrot distribution. The second conclusion gives us the rule that we use to compute $t$ in our statistical fitting. We prove the proposition in \prettyref{app:t}.


\section{Fitting the Data}
In Evert's paper \cite{Evert04}, rather than using maximum-likelihood, he proposes estimating $\alpha$ using a Chi-squared test on the first few $\#F^{-1}(1), \#F^{-1}(2), \dotsc$ values. This approach is implemented by the R library \verb|zipfR| of Evert and Baroni~\cite{EB07}.

%First, modified maximum likelihood \`a la Newman~\cite{Newman05,CSN09}: assume the frequencies were generated by a bounded Evert distribution \eqref{eq:evert} for $\alpha$; %compute the $\alpha$ which would maximize the likelihood of the observation $\mathbf{F}$; use \eqref{eq:shift} to compute $t$. This was implemented in Maple.
%Second, Chi-squared minimization~\cite{Evert04,EB07}: assume the frequencies were generated by an Evert distribution \eqref{eq:evert} for $\alpha$; compute the $\alpha$ and $t$ for which the Chi-squared test indicates maximum similarity of $\#F^{-1}(1), \#F^{-1}(2), \dotsc, \#F^{-1}(\ell)$ between the data and the expected distribution.
%    This was performed with the \verb|lnre| function in the \verb|zipfR| R library. %(This was implemented by using the \verb|lnre| function in the \verb|zipfR| R library. Its outputs, $\alpha_R$ and $B_R,$ are related to our parameters by $\alpha = \alpha_R + 1$ and $t = (\alpha_R-1)/(\alpha_RB_R)$. The tool automatically selected $\ell=12$ and $7$
     %5
     %automatically for the BlueJ and CS Circles %, and Websheets
     %data sets respectively.)
    %\url{http://www.r-bloggers.com/the-zipf-and-zipf-mandelbrot-distributions/}
%\end{enumerate}

\begin{table}[htb!]
$$
\begin{array}{|c|c|c|}
\hline
& \mathrm{Max.~likelihood} & \chi^2 ~ \mathrm{ min.} \\
\hline
\mathrm{Java} & \alpha=1.216, t=33.1 & \alpha=1.225, t=25.7 \\
\hline
\mathrm{Python} & \alpha=1.165, t=44.7 & \alpha=1.143, t=65.7 \\
\hline
\mathrm{Python}^\mathrm{w/o} & \alpha=1.131, t=99.8 & \alpha=1.133, t=92.9 \\
%\hline
%\mathrm{Websheets}& \alpha=1.042, t=212 & \alpha=1+9\cdot10^{-7}, t=10^7 \\
\hline
\end{array}
$$
\caption{Results of fitting our data sets to Zipf-Mandelbrot distributions with both methods. Python$^\mathrm{w/o}$ indicates the Python data set
with the 3 commonest messages removed.}
\label{table:fits}
\end{table}

\begin{figure}[htb!]
\centering
\includegraphics[width=6cm]{final-cscircles-wo.pdf}
\caption{Plot of the Python data set on shifted log-log axes, with shift $t$ from maximum likelihood estimation. Red: observed frequencies; blue: Chi-squared fitted Zipf-Mandelbrot distribution; green: maximum likelihood fitted Zipf-Mandelbrot distribution.}
\label{fig:finalcsc}
\end{figure}

\begin{figure}[htb!]
\centering
\includegraphics[width=6cm]{final-bluej.pdf}
\caption{Plot of the Java data set, analogous to Figure~\ref{fig:finalcsc}.}
\label{fig:finalj}
\end{figure}
%\medskip

We fit our data sets to the Zipf-Mandelbrot family of distributions, using both the Chi-squared approach, and the maximum-likelihood method of Propositions \ref{proposition:evert} and \ref{proposition:t} (implemented in Maple).
The results of the fitting are shown in Table~\ref{table:fits}. The fit for the Python data set improved greatly by treating the three most common errors as outliers (c.f.~Figure~\ref{fig:rawdata}). In Figures~\ref{fig:finalcsc} and~\ref{fig:finalj} we show shifted log-log plots of the observed fits (the Python plot omits the outliers). %data sets and of both fitted distributions --- these, the fitted ``inherent" distributions, are Zipf-Mandelbrot distributions with $\gamma = 1/(1-\alpha)$. The diagrams use a log-log plot with axis shift equal to the $t$ estimated by the maximum likelihood method.
For the Python-without-outliers data set, both methods give a good fit. For the Java data set, the maximum-likelihood method gives a significantly better fit than the Chi-squared method.

%Do different values of $\alpha$ correspond to
%getting better or worse feedback from the compiler/interpreter/JVM?

%\medskip

%\includegraphics[width=7cm]{final-websheet.pdf}
%\caption{Plots of the data sets on shifted log-log axes using the shift $t$ identified by the maximum likelihood estimation procedure. In all three plots, the red circles are the observed frequencies, the blue crosses are the Chi-squared fitted Zipf-Mandelbrot distribution, and the green dots are the maximum likelihood fitted Zipf-Mandelbrot distribution.}
%\label{fig:shiftedloglog}
%\end{figure}

%Before proceeding further, notice the unusual parameters $\alpha=1+9\cdot10^{-7}, t=10^7$ suggested for Websheets by the $\chi^2$ test. These seemingly huge numbers do, in fact, provide a decent fit. Because $\ln(t+x) \sim \ln(t)+x/t$ for $t \gg x$, what it suggests is that the frequencies are modelled by $F_k \propto 1/C^{k}$ for some constant $C$. Indeed, plotting the rank-frequency data on a semi-log scale gives something resembling a straight line, as we would expect from an exponential distribution.

%\begin{figure}
%\centering
%\includegraphics[width=7cm]{ws-semilog.pdf}
%\caption{A plot of the Websheets rank-frequency data on a semi-log plot.}
%\label{fig:websheetssemilog}
%\end{figure}

%The $\chi^2$ test also gives an estimate of how likely the given data would be to generate the $\#F^{-1}(1), \#F^{-1}(2), \dotsc, \#F^{-1}(\ell)$ values tested, if it truly came from the ideal distribution \eqref{eq:evert} (the $p$-value). These values were 0.25 for BlueJ, 0.01 for CS Circles, 0.02 for CS Circles without outliers, and 0.01 for Websheets. Only the 0.25 value would be normally considered as not a statistical rejection of good fit.

%For all of the data sets, we also checked whether the data set's likelihood was close to typical likelihoods for $\mathbf{F}$ vectors generated according to the Evert distribution \eqref{eq:evert}. In every case the data were within one standard deviation of the mean likelihood, i.e.~typical by this measure.

%\begin{figure}
%\centering
%\includegraphics[width=6cm]{fits.pdf}
%\caption{Comparing the actual data to the model $F_k \propto (F+44.5)^{-1/0.165}$ determined by the maximum likelihood estimate and the model $F_k \propto (F+65.6)^{-1/0.143}$ determined by the Chi-squared fit.}
%\label{fig:fits}
%\end{figure}
%
%It is known that with power law distributions, the standard deviation on the measured exponent $\alpha$ is $(\alpha-1)/\sqrt{M}$; see for example \cite[App. B]{Newman05}. If we try to use this also as an estimate on the exponent error for Zipf-Mandelbrot distributions, we get an error estimate of about $0.01$ on the exponent.

%In summary, the evidence from the tests that we performed suggests that the BlueJ error frequencies are Zipf-Mandelbrot, the CS Circles error frequencies look similar to Zipf-Mandelbrot but with significant deviation in the tail, and the Websheets data set does not have a compelling resemblance to the Zipf-Mandelbrot model.

%\subsection{Discussion}
%Comparing the two approaches, the Chi-squared test has the advantage of easily providing a $p$-value, but it has the drawback that it completely ignores the majority of the data set (all error messages with frequency $F_k > \ell$). The emerging tail part of the data used by the Chi-squared test is important, since it is where we can derive and check predictions about what happens in larger data sets. But it would be nice to have a similar test that considered all of the data together. For example, the fit of the CS Circles-without-outliers data set (\prettyref{fig:finalcsc} middle) seems much better than the value $p=0.02$ indicates.

%Note that Newman et al.~\cite{Newman05,CSN09} advise that in typical situations, one must throw out the part of the data with the lowest frequencies (their $x_{\min}$) and that these values are particularly troublesome for discrete distributions. This is in direct opposition to Evert's approach \cite{Evert04} where it is exclusively the lowest frequencies that are used to fit the data. We think this is an artefact of that the approach in \cite{Newman05,CSN09} is tailored for continuous distributions.

%\section{Comparing Two}
%$$Z = \frac{\mu_1-\mu_2}{\sqrt{\sigma_1^2+\sigma_2^2}}$$
%is normally distributed if the things don't differ
%if it's greater than 1.8551, marginally significant
% (for the particular group of users that used our site, and for Python 3.3.0)


%\subsection{Comparing Models}
%As mentioned earlier, since Python is interpreted and Java is compiled, there are some types of run-time errors in Python that would correspond to compile-type errors in Java. Thus the fact that the Python data set has many more run-time errors is not surprising. But if we try to correct for this, how do the languages compare? We deemed \verb|NameError|, \verb|TypeError|, \verb|ImportError| and \verb|AttributeError| as the Python run-time errors in our data set that would correspond to Java syntax errors (\emph{name-related errors} for short). For the Python data set, about two-thirds of the run-time errors were name-related errors. For both Java data sets, about half of the syntax errors were name-related errors. Overall, then, about 17\% of Python errors were non-name-related runtime errors, but only a few percent of Java errors (3\% in BlueJ, 7\% in Websheets) were non-name-related runtime errors. However, it may be possible to attribute this difference to the usage of standard input in CS Circles and Websheets. For example \tts{EOFError: EOF when reading a line} accounted for 12\% of all errors in CS Circles. It would be very interesting to see if other data sets have non-name-related runtime errors providing such a small fraction of errors.
%
%We considered removing the non-name-related run-time errors from each data set. This would more closely parallel previous work. Moreover, all data sets had many hapax legomena error messages that appeared to be users experimenting with the \verb|throw|/\verb|raise| keyword, and focusing on syntax errors would prevent this. On the other hand, the model involving an infinite number of possible error messages would no longer make sense. We re-ran both estimation procedures on the data sets with non-name-related runtime errors removed. This actually produced poorer fits (as measured by the $\chi^2$ $p$-value for all three of the data sets), as well as different values of $\alpha$ and $t$.

\section{Future Work}
%\section{Discussion}
A few very short questions for future work are:
(1) can the good fit be replicated in other Java/Python systems?
(2) if so, what properties of the user base or programming ecosystem affect the $\alpha$ and $t$ parameters?
(3) do error messages in other languages also follow a Zipf-Mandelbrot distibution?

%As mentioned earlier, \tts{SyntaxError: invalid syntax} was identified in our data set as having an unusually high number of different causes. It would be advantageous, especially for new users, to improve the compiler so that a slightly more specific messages are generated depending on the specifics of the invalid syntax. Perhaps other messages could benefit as well; after these improvements, would there be a measurable change in $\alpha$ and $t$?
In the context of the hypothetical extreme languages of Section~\ref{sec:related}, Python's slightly smaller value of $\alpha$ suggests that it tends to give more distinctive error messages. Is it actually giving more information in its errors? Could it alternatively be explained due to artefacts like the non-parallelism mentioned in Section~\ref{sec:datasets}?


It would be interesting to re-analyze the discrete data sets in \cite{Newman05} using the Evert maximum likelihood method. Specifically, this could be done for the data sets for word frequency, web hits, telephone calls, and citations, which are discrete distributions coming from a population that is large enough to be effectively infinite. Additionally, it would be interesting to apply the Kolmogorov-Smirnov test suggested in \cite{Newman05} to the Evert maximum likelihood method, to be more rigorous in our approach.

%It is tempting to try to compare the two programming languages, Java and Python, with regards to their $\alpha$ exponent. We cannot claim to do so reliably without fully analyzing the error in our measurements. But, one might imagine at opposite ends of the spectrum, the very worst programming language ever designed would be one where every mistake generates the single error message ``ERROR" ($\alpha=1, \gamma=+\infty$), while the best would have a different error message for every possible user mistake ever encountered ($\alpha=+\infty, \gamma=0$). Can using a modified language, or performing a controlled experiment within a single language, cause someone to program in a way that they are less likely to repetitively generate the same mistakes? %However, direct comparison of the two languages' $\alpha$ values is not useful since there are several confounding factors: statistical error in measuring $\alpha$, the differing user bases of the data sets, possible differences in sanitization, etc. %Controlled studies using variants of the same language or two IDEs with the same language may permit investigating whether the Zipf-Mandelbrot fit is affected by the user's environment.

%\subsection{Acknowledgments}

From a more practical perspective, it would be not hard, and of a great potential benefit, to release a systematic data set of good beginner-friendly explanations of the top errors in different programming languages. Further work could try to quantify if this improves the ability of beginner students to program independently.

\subsection*{Acknowledgment}
We thank the SIGCSE Special Projects committee, whose Summer 2013 grant for CS Circles provided funding when this work was initiated~\cite{PGV15}, and the Blackbox project for their work on providing accessible huge data sets. We thank undergraduate assistants Ayomikun (George) Okeowo and Pallavi Koppol for their work on sanitizing and writing explanations. Thanks to Jurgis Pralgauskis for translating the Python explanations to Lithuanian. We also thank the PLATEAU referees for their helpful suggestions.

\bibliographystyle{abbrvnat}
%\bibliographystyle{abbrv}
\bibliography{biblio}

\appendix

\section{Proof of \prettyref{proposition:evert}}\label{app:b}
Fix a constant $f$ and consider $N$ as growing to infinity. By linearity of expectation, the expected number $\E[\#F^{-1}(f)]$ of $f$-legomena is equal to the sum, over all $\ell$, of the probability that word $\ell$ occurs exactly $f$ times in our sample. For large $N$, any word with frequency bigger than a constant has vanishingly small probability of occurring only $f$ times. So for a word that may become an $f$-legomenon, its number of occurrences is well-approximated by a Poisson random variable, since it is a sum of many Bernoulli random variables, each with a small individual expectation. The expected number of occurrences of the $\ell$-th most common word is $NC(\ell+t)^{-\gamma}$, so the number of times we observe it is a Poisson variable with expectation $NC(\ell+t)^{-\gamma}$.

This means that for any constant $f$, by the definition of a Poisson variable,
$$\Pr[\textrm{word $\ell$ appears exactly $f$ times}] = \frac{(NC(\ell+t)^{-\gamma})^f}{f!\exp(NC(\ell+t)^{-\gamma})}.$$
Thus, the expected number of words appearing $f$ times is
$$\E[\#F^{-1}(f)] = \sum_{\ell=1}^\infty \frac{(NC(\ell+t)^{-\gamma})^f}{f!\exp(NC(\ell+t)^{-\gamma})}.$$
We approximate this infinite sum with the infinite integral
$$\E[\#F^{-1}(f)]=\int_{1}^\infty \frac{(NC(x+t)^{-\gamma})^f}{f!\exp(NC(x+t)^{-\gamma})}dx.$$
To evaluate it, we substitute $y = NC(x+t)^{-\gamma}$, i.e.~$x = (\frac{y}{NC})^{-1/\gamma}-t$ and so $dx = -\frac{1}{\gamma}(CN)^{1/\gamma}y^{-1-1/\gamma} dy$, giving
$$\E[\#F^{-1}(f)] = \frac{(CN)^{1/\gamma}}{f! \gamma} \int_0^{NC^{-1}t^{-\gamma}} \frac{y^{f-\frac{1}{\gamma}-1}}{\mathrm{e}^y} dy.$$
Again assuming $N$ large, the above integral is well-approximated by replacing the upper bound by $+\infty$. Therefore, taking the terms that do not depend on $f$ into the  constant of proportionality, we find that
\begin{align*}%\label{eq:evertdist}
\E[\#F^{-1}(f)] &\propto \frac{1}{f!} \int_0^{+\infty} \frac{y^{f-\frac{1}{\gamma}-1}}{\mathrm{e}^y} dy
\\ &= \frac{\Gamma(f-1/\gamma)}{\Gamma(f+1)} \\ &\propto \Beta(f-1/\gamma, 1+1/\gamma) = \Beta(f+1-\alpha, \alpha).
\end{align*}


\section{Proof of \prettyref{proposition:t}}\label{app:t}

Let $U(a, b)$ denote a random variable from the uniform distribution on $(a, b).$ Our starting observation is that the continuous power-law distribution with exponent $-\alpha$ and unbounded domain $(1, +\infty)$ is identical in distribution to $U(0, 1)^{-\gamma}$. See, for instance, \cite[App.~D]{CSN09}.

Therefore, adding the bound to get the continuous power-law in the hypothesis of the theorem, said distribution is identical in distribution to $U(\frac{t}{t+M+1}, 1)^{-\gamma}$.

The $(M+1)$-quantiles of $U(\frac{t}{t+M+1}, 1)^{-\gamma}$ are $((t+k)/(t+M+1))^{-\gamma}$ for $k=1, \dotsc, M$, so the first conclusion follows.

Finally, the smaller the domain $(1, (\frac{t}{t+M+1})^{-\gamma})$, the larger the probability density function at the observed $\vF$ values, except that we need $(\frac{t}{t+M+1})^{-\gamma} \geq F_{\max}$ for $F_{\max}$ to be observable at all. This proves the second conclusion.


%\section{Evert Distribution Sums}\label{app:c}
%
%
%
%Using the fact that $\Beta(x, y+1)=\Beta(x, y)-\Beta(x+1, y)$, we have the telescoping sum
%\begin{align*}&\sum_{f=1}^{F_{\max}} \Beta(f+1-\alpha,\alpha) \\ &= \sum_{f=1}^{F_{\max}} (\Beta(f+1-\alpha,\alpha-1) - \Beta(f+2-\alpha,\alpha-1))
%\\ &= \Beta(2-\alpha,\alpha-1) - \Beta(F_{\max}+2-\alpha,\alpha-1).\end{align*}
%This is useful for computing the normalizing constant in the maximum likelihood method, and for producing samples
%from Evert distributions.

\end{document}

error-frequency.bbl
\begin{thebibliography}{41}
\providecommand{\natexlab}[1]{#1}
\providecommand{\url}[1]{\texttt{#1}}
\expandafter\ifx\csname urlstyle\endcsname\relax
  \providecommand{\doi}[1]{doi: #1}\else
  \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi

\bibitem[Brown et~al.(2014)Brown, K{\"o}lling, McCall, and Utting]{BKMU14}
N.~C.~C. Brown, M.~K{\"o}lling, D.~McCall, and I.~Utting.
\newblock Blackbox: A large scale repository of novice programmers' activity.
\newblock In \emph{Proc. 45th SIGCSE}, pages 223--228, 2014.

\bibitem[Brown(1982)]{Brown82}
P.~Brown.
\newblock `{M}y system gives excellent error messages'---or does it?
\newblock \emph{Software: Practice and Experience}, 12\penalty0 (1):\penalty0
  91--94, 1982.

\bibitem[Brown(1983)]{Brown83}
P.~J. Brown.
\newblock Error messages: the neglected area of the man/machine interface.
\newblock \emph{Comm. ACM}, 26\penalty0 (4):\penalty0 246--249, 1983.

\bibitem[Chabert and Higginbotham(1976)]{CH76}
J.~M. Chabert and T.~Higginbotham.
\newblock An investigation of novice programmer errors in {IBM} 370 {(OS)}
  assembly language.
\newblock In \emph{Proc. 14th ACM-SE Southeast Regional Conference}, pages
  319--323, 1976.

\bibitem[Clauset et~al.(2009)Clauset, Shalizi, and Newman]{CSN09}
A.~Clauset, C.~R. Shalizi, and M.~E. Newman.
\newblock Power-law distributions in empirical data.
\newblock \emph{SIAM Review}, 51\penalty0 (4):\penalty0 661--703, 2009.

\bibitem[Coull(2008)]{Coull08}
N.~J. Coull.
\newblock \emph{{SNOOPIE}: development of a learning support tool for novice
  programmers within a conceptual framework}.
\newblock PhD thesis, University of St Andrews, 2008.

\bibitem[Denny et~al.(2012)Denny, Luxton-Reilly, and Tempero]{Denny12}
P.~Denny, A.~Luxton-Reilly, and E.~Tempero.
\newblock All syntax errors are not equal.
\newblock In \emph{Proc. 17th ITiCSE}, pages 75--80, 2012.

\bibitem[Evert(2004)]{Evert04}
S.~Evert.
\newblock A simple {LNRE} model for random character sequences.
\newblock In \emph{Proc. 7th JADT}, 2004.

\bibitem[Evert and Baroni(2007)]{EB07}
S.~Evert and M.~Baroni.
\newblock {zipfR}: Word frequency distributions in {R}.
\newblock In \emph{Proc. 45th Ann. Meeting ACL}, pages 29--32, 2007.

\bibitem[Flowers et~al.(2004)Flowers, Carver, Jackson, et~al.]{FCJ04}
T.~Flowers, C.~Carver, J.~Jackson, et~al.
\newblock Empowering students and building confidence in novice programmers
  through {Gauntlet}.
\newblock In \emph{Proc. 34th FIE}, pages T3H 10--13, 2004.

\bibitem[Goldstein et~al.(2004)Goldstein, Morris, and Yen]{GMY04}
M.~L. Goldstein, S.~A. Morris, and G.~G. Yen.
\newblock Problems with fitting to the power-law distribution.
\newblock \emph{Euro. Phys. J. B-Condensed Matter \& Complex Syst.},
  41\penalty0 (2):\penalty0 255--258, 2004.

\bibitem[Hartmann et~al.(2010)Hartmann, MacDougall, Brandt, and
  Klemmer]{HMBK10}
B.~Hartmann, D.~MacDougall, J.~Brandt, and S.~R. Klemmer.
\newblock What would other programmers do: suggesting solutions to error
  messages.
\newblock In \emph{Proc. 28th SIGCHI}, pages 1019--1028, 2010.

\bibitem[Hartz(2012)]{Hartz12}
A.~J. Hartz.
\newblock \emph{CAT-SOOP: A tool for automatic collection and assessment of
  homework exercises}.
\newblock PhD thesis, Massachusetts Institute of Technology, 2012.

\bibitem[Horning(1974)]{H74}
J.~J. Horning.
\newblock What the compiler should tell the user.
\newblock In {Brauer, F.L. et al.}, editor, \emph{Compiler Construction},
  volume~21 of \emph{Lecture Notes in Computer Science}, pages 525--548. 1974.

\bibitem[Hristova et~al.(2003)Hristova, Misra, Rutter, and Mercuri]{HMRM03}
M.~Hristova, A.~Misra, M.~Rutter, and R.~Mercuri.
\newblock Identifying and correcting {Java} programming errors for introductory
  computer science students.
\newblock \emph{ACM SIGCSE Bulletin}, 35\penalty0 (1):\penalty0 153--156, 2003.

\bibitem[Izs{\'a}k(2006)]{Izsak06}
F.~Izs{\'a}k.
\newblock Maximum likelihood estimation for constrained parameters of
  multinomial distributions --- application to {Zipf--Mandelbrot} models.
\newblock \emph{Comp. statistics \& data analysis}, 51\penalty0 (3):\penalty0
  1575--1583, 2006.

\bibitem[Jackson et~al.(2005)Jackson, Cobb, and Carver]{JCC05}
J.~Jackson, M.~Cobb, and C.~Carver.
\newblock Identifying top {J}ava errors for novice programmers.
\newblock In \emph{Proc. 35th FIE}, pages T4C 24--27, 2005.

\bibitem[Jadud(2005)]{Jadud05}
M.~C. Jadud.
\newblock A first look at novice compilation behaviour using {BlueJ}.
\newblock \emph{Comp. Sci. Ed.}, 15\penalty0 (1):\penalty0 25--40, 2005.

\bibitem[Johnson(1990)]{Johnson90}
W.~L. Johnson.
\newblock Understanding and debugging novice programs.
\newblock \emph{Artificial Intelligence}, 42\penalty0 (1):\penalty0 51--97,
  1990.

\bibitem[Johnson and Soloway(1985)]{J85}
W.~L. Johnson and E.~Soloway.
\newblock {PROUST}: Knowledge-based program understanding.
\newblock \emph{IEEE Transactions on Software Engineering}, SE-11\penalty0
  (3):\penalty0 267--275, 1985.

\bibitem[K{\"o}lling and Utting(2012)]{KU12}
M.~K{\"o}lling and I.~Utting.
\newblock Building an open, large-scale research data repository of initial
  programming student behaviour.
\newblock In \emph{Proc. 43rd SIGCSE}, pages 323--324, 2012.

\bibitem[Lang(2002)]{L02}
B.~Lang.
\newblock Teaching new programmers: a {Java} tool set as a student teaching
  aid.
\newblock In \emph{Proc. 1st PPPJ}, pages 95--100, 2002.

\bibitem[Lerner et~al.(2007)Lerner, Flower, Grossman, and Chambers]{LFGC07}
B.~S. Lerner, M.~Flower, D.~Grossman, and C.~Chambers.
\newblock Searching for type-error messages.
\newblock \emph{ACM SIGPLAN Notices}, 42\penalty0 (6):\penalty0 425--434, 2007.

\bibitem[Mandelbrot(1953)]{Mandelbrot53}
B.~Mandelbrot.
\newblock An informational theory of the statistical structure of language.
\newblock \emph{Comm.~theory}, 84:\penalty0 486--502, 1953.

\bibitem[Marceau et~al.(2011{\natexlab{a}})Marceau, Fisler, and
  Krishnamurthi]{MFK11a}
G.~Marceau, K.~Fisler, and S.~Krishnamurthi.
\newblock Measuring the effectiveness of error messages designed for novice
  programmers.
\newblock In \emph{Proc. 42nd SIGCSE}, pages 499--504, 2011{\natexlab{a}}.

\bibitem[Marceau et~al.(2011{\natexlab{b}})Marceau, Fisler, and
  Krishnamurthi]{MFK11b}
G.~Marceau, K.~Fisler, and S.~Krishnamurthi.
\newblock Mind your language: on novices' interactions with error messages.
\newblock In \emph{Proc. 10th SIGPLAN}, pages 3--18, 2011{\natexlab{b}}.

\bibitem[McCall and Kolling(2014)]{McCall14}
D.~McCall and M.~Kolling.
\newblock Meaningful categorisation of novice programmer errors.
\newblock In \emph{Proc. 44th FIE}, pages 1--8, 2014.

\bibitem[McIver(2000)]{McIver00}
L.~McIver.
\newblock The effect of programming language on error rates of novice
  programmers.
\newblock In \emph{Proc. 12th PPIG Workshop}, pages 181--192, 2000.

\bibitem[Moulton and Muller(1967)]{MM67}
P.~G. Moulton and M.~E. Muller.
\newblock {DITRAN} -- a compiler emphasizing diagnostics.
\newblock \emph{Commun. ACM}, 10\penalty0 (1):\penalty0 45--52, 1967.

\bibitem[Newman(2005)]{Newman05}
M.~E.~J. Newman.
\newblock Power laws, {Pareto} distributions and {Zipf}'s law.
\newblock \emph{Contemporary Physics}, 46\penalty0 (5):\penalty0 323--351,
  2005.

\bibitem[Nienaltowski et~al.(2008)Nienaltowski, Pedroni, and Meyer]{NPM08}
M.-H. Nienaltowski, M.~Pedroni, and B.~Meyer.
\newblock Compiler error messages: What can help novices?
\newblock \emph{ACM SIGCSE Bulletin}, 40\penalty0 (1):\penalty0 168--172, 2008.

\bibitem[Potanin et~al.(2005)Potanin, Noble, Frean, and Biddle]{PNFB05}
A.~Potanin, J.~Noble, M.~Frean, and R.~Biddle.
\newblock Scale-free geometry in {OO} programs.
\newblock \emph{Comm.~ACM}, 48\penalty0 (5):\penalty0 99--103, 2005.

\bibitem[Pritchard and Vasiga(2013)]{PV13}
D.~Pritchard and T.~Vasiga.
\newblock {CS} {Circles}: an in-browser {Python} course for beginners.
\newblock In \emph{Proc. 44th SIGCSE}, pages 591--596, 2013.

\bibitem[Pritchard et~al.(2015)Pritchard, Graham, and Vasiga]{PGV15}
D.~Pritchard, S.~Graham, and T.~Vasiga.
\newblock The state of {CS} {Circles}: Open source and outreach with an
  introductory {Python} website ({Poster}).
\newblock In \emph{Proc.~46th SIGCSE}, page 688, 2015.

\bibitem[Ripley and Druseikis(1978)]{RD78}
G.~D. Ripley and F.~C. Druseikis.
\newblock A statistical analysis of syntax errors.
\newblock \emph{Computer Languages}, 3\penalty0 (4):\penalty0 227--240, 1978.

\bibitem[Schorsch(1995)]{S95}
T.~Schorsch.
\newblock {CAP}: an automated self-assessment tool to check {Pascal} programs
  for syntax, logic and style errors.
\newblock \emph{ACM SIGCSE Bulletin}, 27\penalty0 (1):\penalty0 168--172, 1995.

\bibitem[Schwieters et~al.(2003)Schwieters, Kuszewski, Tjandra, and
  Marius~Clore]{SKTM03}
C.~D. Schwieters, J.~J. Kuszewski, N.~Tjandra, and G.~Marius~Clore.
\newblock The {Xplor-NIH NMR} molecular structure determination package.
\newblock \emph{J. Magnetic Resonance}, 160\penalty0 (1):\penalty0 65--73,
  2003.

\bibitem[Seo et~al.(2014)Seo, Sadowski, Elbaum, Aftandilian, and
  Bowdidge]{SSEAB14}
H.~Seo, C.~Sadowski, S.~Elbaum, E.~Aftandilian, and R.~Bowdidge.
\newblock Programmers' build errors: A case study (at {Google}).
\newblock In \emph{Proc.~36th ICSE}, pages 724--734, 2014.

\bibitem[Shneiderman(1982)]{S82}
B.~Shneiderman.
\newblock Designing computer system messages.
\newblock \emph{Communications of the ACM}, 25\penalty0 (9):\penalty0 610--611,
  1982.

\bibitem[Traver(2010)]{T10}
V.~J. Traver.
\newblock On compiler error messages: what they say and what they mean.
\newblock \emph{Adv.~Human-Computer Interaction}, 2010.

\bibitem[Zolman(2005)]{Zolman05}
L.~Zolman.
\newblock {STLFilt}: An {STL} error message decryptor for {C++}, 2005.
\newblock \url{http://www.bdsoft.com/tools/stlfilt.html}.

\end{thebibliography}
