14.9.3 Counting function definitions

Our immediate goal is to generate a list that tells us how many function definitions contain fewer than 10 words and symbols, how many contain between 10 and 19 words and symbols, how many contain between 20 and 29 words and symbols, and so on.

With a sorted list of numbers, this is easy: count how many elements of the list are smaller than 10, then, after moving past the numbers just counted, count how many are smaller than 20, then, after moving past the numbers just counted, count how many are smaller than 30, and so on. Each of the numbers, 10, 20, 30, 40, and the like, is one larger than the top of that range. We can call the list of such numbers the top-of-ranges list.

If we wished, we could generate this list automatically, but it is simpler to write a list manually. Here it is:

(defvar top-of-ranges
 '(10  20  30  40  50
   60  70  80  90 100
  110 120 130 140 150
  160 170 180 190 200
  210 220 230 240 250
  260 270 280 290 300)
 "List specifying ranges for `defuns-per-range'.")

To change the ranges, we edit this list.

Next, we need to write the function that creates the list of the number of definitions within each range. Clearly, this function must take the sorted-lengths and the top-of-ranges lists as arguments.

The defuns-per-range function must do two things again and again: it must count the number of definitions within a range specified by the current top-of-range value; and it must shift to the next higher value in the top-of-ranges list after counting the number of definitions in the current range. Since each of these actions is repetitive, we can use while loops for the job. One loop counts the number of definitions in the range defined by the current top-of-range value, and the other loop selects each of the top-of-range values in turn.

Several entries of the sorted-lengths list are counted for each range; this means that the loop for the sorted-lengths list will be inside the loop for the top-of-ranges list, like a small gear inside a big gear.

The inner loop counts the number of definitions within the range. It is a simple counting loop of the type we have seen before. (See A loop with an incrementing counter.) The true-or-false test of the loop tests whether the value from the sorted-lengths list is smaller than the current value of the top of the range. If it is, the function increments the counter and tests the next value from the sorted-lengths list.

The inner loop looks like this:

(while length-element-smaller-than-top-of-range
  (setq number-within-range (1+ number-within-range))
  (setq sorted-lengths (cdr sorted-lengths)))

The outer loop must start with the lowest value of the top-of-ranges list, and then be set to each of the succeeding higher values in turn. This can be done with a loop like this:

(while top-of-ranges
  body-of-loop…
  (setq top-of-ranges (cdr top-of-ranges)))

Put together, the two loops look like this:

(while top-of-ranges

  ;; Count the number of elements within the current range.
  (while length-element-smaller-than-top-of-range
    (setq number-within-range (1+ number-within-range))
    (setq sorted-lengths (cdr sorted-lengths)))

  ;; Move to next range.
  (setq top-of-ranges (cdr top-of-ranges)))

In addition, in each circuit of the outer loop, Emacs should record the number of definitions within that range (the value of number-within-range) in a list. We can use cons for this purpose. (See cons.)

The cons function works fine, except that the list it constructs will contain the number of definitions for the highest range at its beginning and the number of definitions for the lowest range at its end. This is because cons attaches new elements of the list to the beginning of the list, and since the two loops are working their way through the lengths’ list from the lower end first, the defuns-per-range-list will end up largest number first. But we will want to print our graph with smallest values first and the larger later. The solution is to reverse the order of the defuns-per-range-list. We can do this using the nreverse function, which reverses the order of a list.

たとえば

(nreverse '(1 2 3 4))

produces:

(4 3 2 1)

Note that the nreverse function is destructive—that is, it changes the list to which it is applied; this contrasts with the car and cdr functions, which are non-destructive. In this case, we do not want the original defuns-per-range-list, so it does not matter that it is destroyed. (The reverse function provides a reversed copy of a list, leaving the original list as is.)

Put all together, the defuns-per-range looks like this:

(defun defuns-per-range (sorted-lengths top-of-ranges)
  "SORTED-LENGTHS defuns in each TOP-OF-RANGES range."
  (let ((top-of-range (car top-of-ranges))
        (number-within-range 0)
        defuns-per-range-list)

    ;; Outer loop.
    (while top-of-ranges

      ;; Inner loop.
      (while (and
              ;; Need number for numeric test.
              (car sorted-lengths)
              (< (car sorted-lengths) top-of-range))

        ;; Count number of definitions within current range.
        (setq number-within-range (1+ number-within-range))
        (setq sorted-lengths (cdr sorted-lengths)))

      ;; Exit inner loop but remain within outer loop.

      (setq defuns-per-range-list
            (cons number-within-range defuns-per-range-list))
      (setq number-within-range 0)      ; Reset count to zero.

      ;; Move to next range.
      (setq top-of-ranges (cdr top-of-ranges))
      ;; Specify next top of range value.
      (setq top-of-range (car top-of-ranges)))

    ;; Exit outer loop and count the number of defuns larger than
    ;;   the largest top-of-range value.
    (setq defuns-per-range-list
          (cons
           (length sorted-lengths)
           defuns-per-range-list))

    ;; Return a list of the number of definitions within each range,
    ;;   smallest to largest.
    (nreverse defuns-per-range-list)))

The function is straightforward except for one subtle feature. The true-or-false test of the inner loop looks like this:

(and (car sorted-lengths)
     (< (car sorted-lengths) top-of-range))

instead of like this:

(< (car sorted-lengths) top-of-range)

The purpose of the test is to determine whether the first item in the sorted-lengths list is less than the value of the top of the range.

The simple version of the test works fine unless the sorted-lengths list has a nil value. In that case, the (car sorted-lengths) expression function returns nil. The < function cannot compare a number to nil, which is an empty list, so Emacs signals an error and stops the function from attempting to continue to execute.

The sorted-lengths list always becomes nil when the counter reaches the end of the list. This means that any attempt to use the defuns-per-range function with the simple version of the test will fail.

We solve the problem by using the (car sorted-lengths) expression in conjunction with the and expression. The (car sorted-lengths) expression returns a non-nil value so long as the list has at least one number within it, but returns nil if the list is empty. The and expression first evaluates the (car sorted-lengths) expression, and if it is nil, returns false without evaluating the < expression. But if the (car sorted-lengths) expression returns a non-nil value, the and expression evaluates the < expression, and returns that value as the value of the and expression.

This way, we avoid an error.

Here is a short test of the defuns-per-range function. First, evaluate the expression that binds (a shortened) top-of-ranges list to the list of values, then evaluate the expression for binding the sorted-lengths list, and then evaluate the defuns-per-range function.

;; (Shorter list than we will use later.)
(setq top-of-ranges
 '(110 120 130 140 150
   160 170 180 190 200))

(setq sorted-lengths
      '(85 86 110 116 122 129 154 176 179 200 265 300 300))

(defuns-per-range sorted-lengths top-of-ranges)

The list returned looks like this:

(2 2 2 0 0 1 0 2 0 0 4)

Indeed, there are two elements of the sorted-lengths list smaller than 110, two elements between 110 and 119, two elements between 120 and 129, and so on. There are four elements with a value of 200 or larger.