Halstead’s Software Metrics
According to Halstead’s “A computer program is an implementation of an algorithm considered to be a collection of tokens which can be classified as either operators or operand.”
Token Count
In these metrics, a computer program is considered to be a collection of tokens, which may be classified as either operators or operands. All software science metrics can be defined in terms of these basic symbols. These symbols are called as a token.
The basic measures are
n1 = count of unique operators.
n2 = count of unique operands.
N1 = count of total occurrences of operators.
N2 = count of total occurrence of operands.
In terms of the total tokens used, the size of the program can be expressed as N = N1 + N2.
Halstead metrics are:
Program Volume (V)
The unit of measurement of volume is the standard unit for size “bits.” It is the actual size of a program if a uniform binary encoding for the vocabulary is used.
V=N*log2n
Program Level (L)
The value of L ranges between zero and one, with L=1 representing a program written at the highest possible level (i.e., with minimum size).
L=V*/V
Program Difficulty
The difficulty level or error-proneness (D) of the program is proportional to the number of the unique operator in the program.
D= (n1/2) * (N2/n2)
Programming Effort (E)
The unit of measurement of E is elementary mental discriminations.
E=V/L=D*V
Estimated Program Length
According to Halstead, The first Hypothesis of software science is that the length of a well-structured program is a function only of the number of unique operators and operands.
N=N1+N2
And estimated program length is denoted by N^
N^ = n1log2n1 + n2log2n2
The following alternate expressions have been published to estimate program length:
- NJ = log2 (n1!) + log2 (n2!)
- NB = n1 * log2n2 + n2 * log2n1
- NC = n1 * sqrt(n1) + n2 * sqrt(n2)
- NS = (n * log2n) / 2
Potential Minimum Volume
The potential minimum volume V* is defined as the volume of the most short program in which a problem can be coded.
V* = (2 + n2*) * log2 (2 + n2*)
Here, n2* is the count of unique input and output parameters
Size of Vocabulary (n)
The size of the vocabulary of a program, which consists of the number of unique tokens used to build a program, is defined as:
n=n1+n2
where
n=vocabulary of a program
n1=number of unique operators
n2=number of unique operands
Language Level – Shows the algorithm implementation program language level. The same algorithm demands additional effort if it is written in a low-level program language. For example, it is easier to program in Pascal than in Assembler.
L’ = V / D / D
lambda = L * V* = L2 * V
Language levels
| Language | Language level λ | Variance σ |
|---|---|---|
| PL/1 | 1.53 | 0.92 |
| ALGOL | 1.21 | 0.74 |
| FORTRAN | 1.14 | 0.81 |
| CDC Assembly | 0.88 | 0.42 |
| PASCAL | 2.54 | – |
| APL | 2.42 | – |
| C | 0.857 | 0.445 |
Counting rules for C language
- Comments are not considered.
- The identifier and function declarations are not considered
- All the variables and constants are considered operands.
- Global variables used in different modules of the same program are counted as multiple occurrences of the same variable.
- Local variables with the same name in different functions are counted as unique operands.
- Functions calls are considered as operators.
- All looping statements e.g., do {…} while ( ), while ( ) {…}, for ( ) {…}, all control statements e.g., if ( ) {…}, if ( ) {…} else {…}, etc. are considered as operators.
- In control construct switch ( ) {case:…}, switch as well as all the case statements are considered as operators.
- The reserve words like return, default, continue, break, sizeof, etc., are considered as operators.
- All the brackets, commas, and terminators are considered as operators.
- GOTO is counted as an operator, and the label is counted as an operand.
- The unary and binary occurrence of “+” and “-” are dealt with separately. Similarly “*” (multiplication operator) are dealt separately.
- In the array variables such as “array-name [index]” “array-name” and “index” are considered as operands and [ ] is considered an operator.
- In the structure variables such as “struct-name, member-name” or “struct-name -> member-name,” struct-name, member-name are considered as operands and ‘.’, ‘->’ are taken as operators. Some names of member elements in different structure variables are counted as unique operands.
- All the hash directive is ignored.
Example: Consider the sorting program as shown in fig: List out the operators and operands and also calculate the value of software science measure like n, N, V, E, λ ,etc.
Solution: The list of operators and operands is given in the table
| Operators | Occurrences | Operands | Occurrences |
|---|---|---|---|
| int | 4 | SORT | 1 |
| () | 5 | x | 7 |
| , | 4 | n | 3 |
| [] | 7 | i | 8 |
| if | 2 | j | 7 |
| < | 2 | save | 3 |
| ; | 11 | im1 | 3 |
| for | 2 | 2 | 2 |
| = | 6 | 1 | 3 |
| – | 1 | 0 | 1 |
| <= | 2 | – | – |
| ++ | 2 | – | – |
| return | 2 | – | – |
| {} | 3 | – | – |
| n1=14 | N1=53 | n2=10 | N2=38 |
Here N1=53 and N2=38. The program length N=N1+N2=53+38=91
Vocabulary of the program n=n1+n2=14+10=24
Volume V= N * log2N=91 x log2 24=417 bits.
The estimate program length N of the program
= 14 log214+10 log2)10
= 14 * 3.81+10 * 3.32
= 53.34+33.2=86.45
Conceptually unique input and output parameters are represented by n2*.
n2*=3 {x: array holding the integer to be sorted. This is used as both input and output}
{N: the size of the array to be sorted}
The Potential Volume V*=5log25=11.6
Since L=V*/V
We may use another formula
V^=V x L^= 417 x 0.038=15.67
E^=V/L^=D^ x V 
Therefore, 10974 elementary mental discrimination is required to construct the program.
This is probably a reasonable time to produce the program, which is very simple.