APPLYING COMPLEXITY-MEASURES TO RULE-BASED PROLOG PROGRAMS

Four measures are developed and empirically tested that attempt to qua ntify the complexity of rule-based Prolog programs in terms of measuri ng the dependency between rules. The measures are lines of code (LOC), number of rules (NR), number of unique predicate nodes (UPN), and McC abe's cyclomatic complexity model, v(G). The UPN and v(G) measures are developed by reducing a Prolog program to its most abstract graphical form and then counting the nodes and arcs represented by the graph. T he four measures are tested in terms of their ability to distinguish b etween a set of 80 professionally developed programs, divided into gro ups of error-prone and error-free programs. Unpaired student's t-tests showed that UPN is a significantly better measure of complexity (rho = 0.002-0.006) than any of the other measures (rho = 0.096-0.609). Fin ally, by plotting the cumulative frequency of errors across the sample , it is possible to observe a threshold point of around 35 +/- 5 UPN, above which Prolog programs contain significantly more errors (rho = 0 .000). (C) 1998 Elsevier Science Inc. All rights reserved.