Метрики Холстеда. 
Критерии качества программного обеспечения

Метрика Холстеда относится к метрикам, вычисляемым на основании анализа числа строк и синтаксических элементов исходного кода программы.

Основу метрики Холстеда составляют четыре измеряемые характеристики программы:

• · NUOprtr (Number of Unique Operators) — число уникальных операторов программы, включая символы-разделители, имена процедур и знаки операций (словарь операторов);
• · NUOprnd (Number of Unique Operands) — число уникальных операндов программы (словарь операндов);
• · Noprtr (Number of Operators) — общее число операторов в программе;
• · Noprnd (Number of Operands) — общее число операндов в программе.

Метрики Холстеда отражают лексический подход к измерению характеристик программного обеспечения, основанный на измеримых свойствах алгоритмов. Свойства любого описания алгоритма (или программы для ЭВМ), по мнению Холстеда, могут быть измерены или вычислены на основе следующих метрических характеристик (оценочных элементов):

n1 — количество различных операторов программы;

n2 — количество различных операндов программы;

N1 — общее количество операторов программы;

N2 — общее количество операндов программы.

На их основе Холстед определяет следующие метрики:

· словарь программы (в условных единицах).

n = n1+n2, (1).

· теоретический словарь программы, т. е. словарный запас, необходимый для написания программы, с учетом того, что необходимая функция уже реализована в данном языке и, следовательно, программа сводится к вызову этой функции.

n^* = n1^* + n2^*

· длина программы (в условных единицах).

N = N1+N2 (2).

· теоретическая длина программы (в условных единицах) С = (n1 log₂ n1)+(n2log₂ n2), (3).

Вводя эту оценку, Холстед исходит из основных концепций теории информации, по аналогии с которыми частота использования операторов и операндов в программе пропорциональна двоичному логарифму количества их типов. Таким образом, выражение (3) представляет собой идеализированную аппроксимацию (2), т. е. справедливо для потенциально корректных программ, свободных от избыточности или несовершенств (стилистических ошибок).

Несовершенствами можно считать следующие ситуации:

• o последующая операция уничтожает результаты предыдущей без их использования;
• o присутствуют тождественные выражения, решающие совершенно одинаковые задачи;
• o одной и той же переменной назначаются различные имена и т. п.

Подобные ситуации приводят к изменению N без изменения n.

Холстед утверждает, что для стилистически корректных программ отклонение в оценке теоретической длины С от реальной N не превышает 10%.

Предлагается использовать С как эталонное значение длины программы со словарем n. Длина корректно составленной программы N, т. е. программы, свободной от избыточности и имеющей словарь n, не должна отклоняться от теоретической длины программы С более чем на 10%. Таким образом, измеряя n1, n2, N1 и N2 и сопоставляя значения N и С для некоторой программы, при более чем 10%-ном отклонении можно говорить о наличии в программе стилистических ошибок, т. е. несовершенств.

На практике N и С часто существенно различаются.

· объем программы (в битах, определение объема программы предполагает, что обозначение операндов и операторов требует не более одного символа).

V = N log₂(n) (4).

· потенциальный объем программы (полагая, что в программах, идеальных с точки зрения экономии затрат памяти, во-первых: операторы и операнды не повторяются, во-вторых: все операнды являются либо входными, либо выходными параметрами и в-третьих: для записи текста программы достаточно двух операторов (описания заголовка процедуры-функции и присваивания значения)).

V^* = n^* log₂ n^* (5).

где n2* - общее число входных и выходных параметров.

· уровень качества программы (в условных единицах, если n2*=2).

L = V^*/ V (6).

Исходным для введения этой характеристики является предположение о том, что при снижении стилистического качества программирования уменьшается содержательная нагрузка на каждый компонент программы и, как следствие, расширяется объем реализации исходного алгоритма. Учитывая это, можно оценить качество программирования на основании степени расширения текста относительно потенциального объема V*. Очевидно, для идеальной программы L=1, а для реальной — всегда L<1.

Нередко целесообразно определить уровень программы, не прибегая к оценке ее теоретического объема, поскольку список параметров программы часто зависит от реализации и может быть искусственно расширен. Это приводит к увеличению метрической характеристики качества программирования. М. Холстед предлагает аппроксимировать эту оценку выражением, включающим только фактические параметры, т. е. параметры реальной программы:

L^* = 2 n2 / (n1 N2).

· уровень языка — это коэффициент пропорциональности изменения объема программы при переводе с одного языка на другой так, что обеспечивается постоянство произведения уровня программы на потенциальный объем.

=L V^* (7).

· интеллектуальное содержание программы (инвариантное по отношению к используемым языкам реализации, в условных единицах).

I=L^* V (8).

Преобразуя выражение (8) с учетом (6), получаем.

I = L^* V = LV = V^*V/V = V^*.

Эквивалентность I и V* свидетельствует о том, что мы имеем дело с характеристикой информативности программы.

Введение

характеристики I позволяет определить умственные затраты на создание программы. Процесс создания программы условно можно представить как ряд операций:

• 1) осмысление предложения известного алгоритма;
• 2) запись предложения алгоритма в терминах используемого языка программирования, т. е. поиск в словаре языка соответствующей инструкции, ее смысловое наполнение и запись.

Используя эту формализацию в методике Холстеда, можно сказать, что написание программы по заранее известному алгоритму есть N^-кратная выборка операторов и операндов из словаря программы n, причем число сравнений (по аналогии с алгоритмами сортировки) составит log2(n).

Если учесть, что каждая выборка-сравнение содержит, в свою очередь, ряд мысленных элементарных решений, то можно поставить в соответствие содержательной нагрузке каждой конструкции программы сложность и число этих элементарных решений. Количественно это можно характеризовать с помощью характеристики L, поскольку 1/L имеет смысл рассматривать как средний коэффициент сложности, влияющий на скорость выборки для данной программы. Следовательно можно рассчитать оценку необходимых интеллектуальных усилий.

· оценка интеллектуальных усилий (в условных единицах).

E = N^* log₂ (n / L) (9).

E характеризует число требуемых элементарных решений при написании программы.

Однако следует заметить, что E адекватно характеризует лишь начальные усилия по написанию программ, поскольку при построении E не учитываются отладочные работы, которые требуют интеллектуальных затрат иного характера.

Суть интерпретации этой характеристики состоит в оценке не затрат на разработку программы, а затрат на восприятие готовой программы. При этом вместо теоретической длины программы N^* используется ее реальная длина:

E^* = N log₂ (n / L).

Характеристика E^* введена, исходя из предположения, что интеллектуальные усилия на написание и восприятие программы очень близки по своей природе. Однако если при написании программы стилистические погрешности в тексте практически не должны отражаться на интеллектуальной трудоемкости процесса, то при попытке понять такую программу их присутствие может привести к серьезным осложнениям. Эта посылка достаточно хорошо согласуется с нашими выводами относительно взаимосвязи N и N^, изложенными выше.

Преобразуя формулу (9) с учетом выражений (4) и (6), получаем.

E = V V / V^*

Такое представление E', а соответственно и E, так как E=E', наглядно иллюстрирует целесообразность разбиения программ на отдельные модули, поскольку интеллектуальные затраты оказываются пропорциональными квадрату объема программы, который всегда больше суммы квадратов объемов отдельных модулей.

· время на программирование (в условных единицах).

T = E/S, (10).

или Т (n1N2log2n (n1log2n1+n2log2n2))/(2n2S), (11).

где S — число Страуда (5.

Число Страуда Холстед принял равным 18 — число умственных операций в единицу времени.

Потенциальный объем программы является мерой минимально необходимого объема программы с заданным словарем. При этом потенциальный объем не зависит от языка реализации. При переводе программы с одного языка на другой потенциальный объем не меняется, но действительный объем V или увеличивается, или уменьшается в зависимости от языка реализации.

Используя выражение для потенциального объема программы, Холстедом получены следующие метрики:

Число Страуда S определяется как число «страудовских моментов» в секунду. «Страудовский момент» — это время, необходимое человеку для выполнения элементарного различения объектов, подобно различению кадров фильма. Страуд обнаружил, что человек способен различать от 5 до 20 объектов в секунду.

Уровень программы L1 характеризует эффективность реализации алгоритма относительно затрат памяти. Только для наиболее сжатой формы реализации алгоритма (V=V*) уровень программы имеет значение 1. Всем другим вариантам реализации соответствуют значения L<1.

Интеллектуальное содержание характеризует меру «сказанного» в программе, или ее «информативность». Интеллектуальное содержание (уровень) программы сильно коррелирует с потенциальным объемом (LV*) и тоже не зависит от языка реализации.

Работа по программированию (уравнение мысленной работы) характеризует величину умственной работы, связанной с написанием программного кода. Так как сумма квадратов двух величин всегда меньше квадрата их суммы, уравнение работы дает основание для разбиения программы на составные части — модули. Модульность снижает работу по программированию. Исследования возможностей оперативного мышления человека дают основания считать, что наиболее продуктивна ситуация, при которой для получения одного результата используется не более пяти объектов. В прикладном отношении этот результат называют гипотезой о «шести объектах». Для определения количества модулей M в программе Холстед рекомендует использовать выражение

M= n2*/6, (12)

где n2* - общее количество входных и выходных переменных в программе.

Из уравнения работы получено следующее уравнение ошибок в программе

B=LE/E0, (13)

где В — количество ошибок в программе, Е0 — среднее число элементарных отличий между возможными ошибками программирования.

Используя преобразованное уравнение работы Е= (V*)3/2, (14)

значение уровня английского языка (=2,16) в качестве аналога языка программирования и гипотезу о «шести объектах» идеальной по затратам памяти программы (n1=n1*=2, n2=n2*=6), Холстед вывел следующее уравнение для прогноза количества ошибок в программе:

В=Е 2/3 /3000, (15)

Или В=V/3000, (16)

где V — объем программы.

Кроме своего прямого назначения в практическом отношении метрики длины программы (3) и длины реализации (2) можно использовать для выявления несовершенств программирования. Если расчеты длины программы и длины реализации отличаются более чем на десять процентов, то это свидетельствует о возможном наличии в программе следующих шести классов несовершенств:

• 1. Наличие последовательности дополняющих друг друга операторов к одному и тому же операнду, например, А+C-А.
• 2. Наличие неоднозначных операндов, например, A=D и A=С.
• 3. Наличие синонимичных операндов, например, А=В и Т=В.
• 4. Наличие общих подвыражений, например (А+В)С+D (А+В).
• 5. Ненужное присваивание, например С=А+В, если переменная С используется в программе только один раз.
• 6. Наличие выражений, которые не представлены в свернутом виде как произведение множителей, например XX+2XY+YY не представлено как (X+Y)(X+Y).
• 7. Длину реализации N (2) можно использовать для прогноза числа фактических машинных команд P с помощью выражения

(17)

или более грубо, с помощью неравенства

2P N 4P. (18)

Уравнение работы (9) можно использовать для оценки экономической эффективности использования того или иного языка программирования. Относительное сокращение работы по программированию в зависимости от уровня языка используют как показатель эффективности внедрения языка программирования в производственную практику.

Уровень программы 0L1 можно использовать для оценки сложности вариантов реализации заданного алгоритма D (чем меньше затрат памяти, тем сложнее вариант программы):

(19)

Отметим, что уровень программы играет двойственную роль в оценке трудности или легкости ее понимания. Специалист, который хорошо знает язык программирования, поймет программу тем быстрее, чем меньше ее объем, то есть выше уровень. Но для человека, менее разбирающегося в программировании, требуется больший объем и меньший уровень. Установлено, что для любого алгоритма, описанного разными языками, с увеличением объема программы V уровень программы L уменьшается в той же пропорции. Поэтому произведение уровня программы на объем является постоянной величиной, равной потенциальному объему реализации данного алгоритма.

L V = V^* = const. (20)

Вместе с тем, если язык не меняется, а меняется только алгоритм, то для любого языка произведение потенциального объема на уровень программы остается постоянной величиной, равной уровню языка [14]

L V = = const. (21)