A Contrast Between Language Level Measures

476

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. SE-3, NO. 6, NOVEMBER 1977

Short Notes A Contrast Between Language Level Measures

L

R. R. OLDEHOEFT Abstraet-Software science techniques have been used to provide a framework for evaluation of problem solving systems. In that effort, two methods for calculating the level of a language (L and L) were used, it was suspected that L, while adequate in that application, might be inferior to L. By using a set of hypothetical languagesj each with different intrinsic data structures and operators, it is shown here that when an inappropriate language is applied to some problems, L may reflect an inaccurately large value for language level, and can sometimes be made to yield an arbitrary value. Since L is often as easily applied as L, and does not exhibit this anomalous behavior, it is suggested that its general use is to be preferred. Index Terms- Language level, problem solving systems, software science. INTRODUCTION "Software science" refers to recent work of which the goal

is to develop measures for describing characteristics of algorithms, programs, and programming languages [1] -[4]. These measures are based on the assumption that a program consists entirely of operators and operands; all measures are computed from the variety and frequency of occurrence of operators and operands. For reference purposes, some of the measures are restated here. Given an algorithm expressed in a language, let =71- the number of distinct operators used, N, = the total number of operators used, 772 = the number of distinct operands used, and N2 = the total number of operands used. The volume of the algorithm expressed in the language is

V=(NI +N2) 10g2

(77k

The minimum volume for language is given by V*

=

(2

+n2)

log2

(2

given algorithm expressed in

=

SEQUENTIAL ARRAY OPERATIONS In this section array operations are examined which can be characterized by a constant number of references to each array element. The most simple is the array assignment A --B where A and B are m by n arrays. Since there are two parameters (A and B) to the problem, the minimum volume for this operation

is

= (4) log2 (4).

In language A the algorithm is written as above: any

+r2)

where 12* is the number of input-output parameters of the algorithm. Then language level is defined as the ratio of the two volume formulas:

L

(2/n1) (n2/N2).

These two measures both produce values in (0,1] for any language and any algorithm. They have been used interchangeably since their values have generally been near each other. Measures L and L have been used to compare languages in a three-dimensional "complexity space" the basis of which is the inherent operators, control structures, and data structures found in the languages [ 5] . Subsequently it has been observed that anomalies may occur when using L to compare different languages with respect to the same problem. In this report two anomalies are exemplified and discussed. In the following assume the existence of three programming languages which differ in their inherent data (and accompanying operator) complexities: A has arrays and intrinsic array operators (like APL); measures of L are expected to be relatively high for some problems. B also has arrays, but array operations must be explicitly coded by referencing individual elements (e.g., Algol 60); smaller values from L and L are anticipated than when using language A. C has no array structures (e.g., array-less Fortran); problems involving them must use scalar variables; language level measures should be even lower than in language B.

V*

+ 72). a

=

V*/ V.

It is experimentally established in [3] that L V = V* is independent of the programming language used to express an algorithm. This means that X2*, the number of input-output parameters, is a property of the algorithm and not of its implementation. An approximation to L is used when the minimum volume V* is not available (e.g., in the analysis of English prose): Manuscript received November 18, 1976; revised May 1977. The author is with the Department of Mathematics, Arizona State University, Tempe, AZ 85 281.

A v-B; The operator and operand counts

Operator Count

; 1

1

are as

follows:

7?l = 2 N1= 2

Operand A B .72 = 2 1 1 N2 =2 Count LA denotes the level of A using L, and LA is the level using L. LA = ((4) 10g2 (4))/((4) log2 (4)) = 1.

LA = (2/2) (2/2) = 1.

Both measures indicate that A is a language with the highest

possible level for this problem. Using language B one would write for i -- 1 to m do 1 to n do for

477

SHORT NOTES

mum volume is

A[i,j]