The Shape of Code

The source code of individual functions is written a particular way by individuals to solve particular problems. When source code use of programming constructs are counted, in a sufficiently large quantity of source code, various patterns emerge. The most common patterns involve power laws and exponentials. The plot below shows the number of functions containing a given number of lines of code, expression-statements (e.g., assignments, calls whose return value is not used), function calls (which includes calls within an expression), and return-statements for 176,172 C functions, along with fitted power laws (data obtained using GitHub’s CodeQL variant analysis; code+data):

The power law exponents are: LOC 1, expression-statements 3.4, calls 3.2, if-statements 3.6, and return-statements 4.6.

This plot counts uses across all functions, to provide a global perspective. Given the quantity of data available, it’s possible to focus on the characteristics of functions containing a given number of lines of code (LOC), to study patterns of behavior that emerge as functions get longer (it was once thought that there was an optimal function length that minimised the likelihood of fault reports).

Given a function containing LOC, what is the probability that it will contain if-statements, or for-statements, or expression-statements, etc? The plots below show the number of if-statements that occur in 176,172 C functions containing each of 4, 5, …, 19 LOC, along with fitted regression lines (code+data):

The fitted model is the probability mass function of the negative binomial distribution. The blue/green lines are individual fits to the data in each plot.

The negative binomial distribution is usually described in terms of the probability of events occurring (or not occurring) in a sequence of tries, e.g., rolling two 6’s in five attempts. In a function context, this can be interpreted as the probability that there will be occurrences of a particular statement in the LOC of the function’s code.

There are various ways of specifying a negative binomial distribution. The data was fitted using R’s gamlss package, which uses the two parameters: mean () and dispersion ().

As functions get longer (i.e., LOC increases), they are more likely to contain more of each kind of statement (i.e., the mean will increase), and the variability is also likely to increase. In other words, the parameters and will increase with LOC. The red line in each plot are derived from a fitted negative binomial distribution with: and , where the values , , , and are returned by the fitting process (this equation was found by inspired guessing/some trial and error; another possibility is:, and ). This LOC dependent fits (in red) closely follow the bespoke fits (in blue/green), and for larger LOC are not affected by noisy data points.

Being able to fit a single model to the data over a range of LOCs shows that a consistent pattern of behavior exists. Similar models can be built for number of calls, while-statements, expression-statements and number of local variables. The model of for-statements suffered from high variability counts, and return-statements counts grew too slowly over the range of LOC analysed.

If the number of if-statements, say, within functions of a given size has a negative binomial distribution, then adding together all these distributions, weighted by the number of functions at a given size, should produce a power law whose exponent matches that found in the first plot (i.e., 3.6).

I asked ChatGPT: “If $y(k, x)=a*x^{-b}*NB(k; mu=log(x), sigma=log(x))$ where: $NB$ is the probability mass of the negative binomial distribution, $mu$ is its mean and $x$ takes positive integer values, $a$ is a positive constant, and $1 < b < 3$.  Show that the series $sum_{x=3}^14 y(k, x)$i for $0 < k < 10$ is approximately a power law." and obtained the response that the exponent was approximately (i.e., about 2), which is not close.

The responses from other LLMs were not any better. The calculation requires various simplifying assumptions (all the models resorted to numerical simulation at some point), and these need to be checked.