home *** CD-ROM | disk | FTP | other *** search
/ Programmer's ROM - The Computer Language Library / programmersrom.iso / ada / metric / halstead.doc < prev    next >
Encoding:
Text File  |  1988-05-03  |  34.1 KB  |  1,027 lines

  1. ::::::::::::::
  2. halstead.cnt
  3. ::::::::::::::
  4. [NOSC.RELEASES.V0302.HALSTEAD.SOURCE]IHSUBTYPE.DAT                      6    11
  5. [NOSC.RELEASES.V0302.HALSTEAD.SOURCE]IHSERIES_.DAT                      6    11
  6. [NOSC.RELEASES.V0302.HALSTEAD.SOURCE]IHAGG_NAM.DAT                      6    11
  7. [NOSC.RELEASES.V0302.HALSTEAD.SOURCE]IHCASE_AL.DAT                      6    11
  8. [NOSC.RELEASES.V0302.HALSTEAD.SOURCE]IHHANDLER.DAT                      6    11
  9. [NOSC.RELEASES.V0302.HALSTEAD.SOURCE]IHBLOCK_S.DAT                      6    11
  10. [NOSC.RELEASES.V0302.HALSTEAD.SOURCE]IHINNER_R.DAT                      6    11
  11. [NOSC.RELEASES.V0302.HALSTEAD.SOURCE]IHVARIABL.DAT                      8    12
  12. [NOSC.RELEASES.V0302.HALSTEAD.SOURCE]IHTYPE_DE.DAT                      8    12
  13. [NOSC.RELEASES.V0302.HALSTEAD.SOURCE]IHGENERIC.DAT                      6    11
  14. [NOSC.RELEASES.V0302.HALSTEAD.SOURCE]IHTASK_DE.DAT                      6    11
  15. [NOSC.RELEASES.V0302.HALSTEAD.SOURCE]HALSTEAD.ADA                      70   252
  16. [NOSC.RELEASES.V0302.HALSTEAD.TEST]SCANNERS.SPC                        15   245
  17. [NOSC.RELEASES.V0302.HALSTEAD.TEST]SCANNERS.BDY                        85   283
  18. ::::::::::::::
  19. halstead.mem
  20. ::::::::::::::
  21.                         The Halstead Tool
  22. COMMAND FORMAT
  23. -- Halstead : Computes HALSTEAD's software science formulas for Ada
  24. --            program units 
  25. -- Version 3.01-1.01
  26. subtype STRING_TYPE is STRING;
  27. type    STRING_LIST is array (POSITIVE range <>) of STRING_TYPE;
  28. procedure HALSTEAD(
  29.     UNITS     : in STRING_LIST;
  30.     OUTPUT    : in STRING := "";
  31.     LIBRARY   : in STRING := "_AIELIB";
  32.     );
  33. -- UNITS    : Names of the Ada compilation units
  34. -- OUTPUT   : Name of the report file (defaults to standard output)
  35. -- LIBRARY  : Name of the program library
  36. PARAMETERS
  37. UNITS      This parameter is a list of string values, each of which is
  38.            the name of a unit which is to be analyzed.  This parameter
  39.            is required and the list must have at least one value.  A
  40.            subunit may be specified using a qualified name, as in
  41.            ("PARENT.SUBUNIT"), which would analyze the subunit called
  42.            SUBUNIT of the compilation unit PARENT.
  43.      
  44. OUTPUT     This is the name of the output file.  It is optional and if it
  45.            is not used, output will be directed to standard output.
  46.      
  47. LIBRARY    This parameter is a string which is the program library
  48.            containing the compilation units to be analyzed.  This
  49.            This parameter is optional and defaults to "_AIELIB"
  50.            (WARNING: in the current release, this parameter is ignored)
  51.      As an example assume that there  exists  a  program  library
  52. called  [.AIELIB]  and  that  it  is the current directory.  Also
  53. assume that in the program library  there  exists  a  compilation
  54. unit  which  is a procedure called MAIN.  The objective is to run
  55. the HALSTEAD tool on the unit MAIN.  The following command can be
  56. used:
  57.      $ HALSTEAD(UNITS => ("MAIN"));
  58. This will compute the Halstead metrics on the unit MAIN and write
  59. The Halstead Tool                                          Page 2
  60. the report to the default output file.
  61.      Note that an implicit specification is  constructed  by  the
  62. Byron/AIE  compiler  front end for any compilation unit that does
  63. not have an explicit specification.  The HALSTEAD tool  does  not
  64. distinguish   these   implicit   specifications   from   explicit
  65. specifications.  In  the  above  example,  the  metrics  will  be
  66. computed  for both the specification and body of MAIN, regardless
  67. of whether or not a source file containing  a  specification  for
  68. MAIN was compiled into the library.
  69. DESCRIPTION
  70.      The Halstead tool uses the number of operands and  operators
  71. in  the  program  to  compute the expected length of the program.
  72. Each symbol in the program is classified  as  an  operand  or  an
  73. operator.   Operators are mathematical functions such as +, -, *,
  74. and /, as well as parenthesis and subprogram calls.  Operands are
  75. constants  and  variables.   From  the  number  of  operands  and
  76. operators, Halstead makes predictions about the program  such  as
  77. intelligence   content,  number  of  expected  bugs,  programming
  78. effort, and the level at  which  the  program  is  written.   See
  79. [Els].
  80.      The metrics are computed on a compilation unit  by  breaking
  81. it  down  into  its fundamental units.  These are the basic units
  82. out of which Ada programs  are  built.   These  are  subprograms,
  83. packages,  and  tasks.   The  metrics are computed in a lexically
  84. nested fashion.  For example inside a package body which contains
  85. subprogram  bodies  in it each of the subprograms has the metrics
  86. computed for it.
  87. PREPARATION
  88.      HALSTEAD computes the metrics for an ADA  program  by  using
  89. the  source  program's  DIANA  representation.   Therefore  it is
  90. necessary to have the source program's DIANA in  an  ADA  program
  91. library  before  running HALSTEAD.  This can be accomplished in a
  92. number of steps.
  93.      1. First it is necessary to create an ADA program library which will
  94.         contain the DIANA representations of the source program which
  95.         HALSTEAD will analyze.  This is accomplished by the command:
  96.      
  97.         AIEPLIB
  98.      
  99.      
  100.         This command creates a directory called [._AIELIB] in the directory it
  101.         is executed from.
  102.      
  103.      2. Following this it is necessary to successfully run the source
  104. The Halstead Tool                                          Page 3
  105.         program through ADASEM, which is semantics phase of the ADA
  106.         compiler. This generates the DIANA representation for the source
  107.         program. In order to run the semantics phase execute the command:
  108.         ADASEM SOURCE.ADA
  109. RESTRICTIONS
  110.      It  is  important  to  note  that   Halstead   places   some
  111. restrictions  on  the program whose estimates are being computed.
  112. It must be a "pure" program.  Halstead defines a pure program  to
  113. be one that does not contain any of the following constructions.
  114.      
  115.       1. No complementary operators.
  116.      
  117.          There cannot be successive applications of two comple-
  118.          mentary operations to the same operand. For example:
  119.      
  120.          z - t + t -> r
  121.      
  122.      
  123.       2. There cannot be ambigous operands.
  124.      
  125.          A given operand cannot refer to different objects at
  126.          different times in the program.  For instance in the
  127.          following example r represents first a sum and then a
  128.          product.
  129.      
  130.      
  131.          p + q -> r   r * r -> r
  132.      
  133.          Should be written as:
  134.      
  135.          p + q -> t   t * t -> r
  136.      
  137.      
  138.       3. There cannot be synonomous operands.
  139.      
  140.          Two different names for the same object.  There can only
  141.          exist one name for one object.
  142.      
  143.      
  144.          p + q -> t1  p + q -> t2  t1 * t2 -> r
  145.      
  146.          Should be written as:
  147.      
  148.          p + q -> t1  t1 * t1 -> r
  149.      
  150.      
  151.       4. Common subexpressions cannot exist.
  152.      
  153.          Any expression which is used more than once must be
  154. The Halstead Tool                                          Page 4
  155.          assigned to a variable.
  156.      
  157.          (p + q) * (p + q) -> r
  158.      
  159.          Should be written as:
  160.      
  161.          (p + q) -> t1  t1 ** 2 -> r
  162.      
  163.      
  164.       5. No unwarranted assignments.
  165.      
  166.          If an assignment is made and the value used only once
  167.          the assignment is unnecessary.
  168.      
  169.          p + q -> t1   t1 ** 2 -> r
  170.      
  171.          Should be written as:
  172.      
  173.          (p + q) ** 2 -> r
  174.      
  175.      
  176.       6. Expressions should be factored.
  177.      
  178.          p*p + 2*p*q + q*q
  179.      
  180.          Should be written as:
  181.      
  182.          (p + q) ** 2
  183.      
  184. METRICS COMPUTED
  185.      Halstead begins by defining the following symbols:
  186.      
  187. 1.  NUMBER OF UNIQUE OPERATORS
  188.      
  189.     n1
  190.      
  191.      
  192. 2.  NUMBER OF UNIQUE OPERANDS
  193.      
  194.     n2
  195.      
  196.      
  197. 3.  THE VOCABULARY
  198.      
  199.     n = n1 + n2
  200.      
  201.      
  202. 4.  TOTAL NUMBER OF OPERATORS
  203.      
  204.     N1
  205.      
  206. The Halstead Tool                                          Page 5
  207.      
  208. 5.  TOTAL NUMBER OF OPERANDS
  209.      
  210.      
  211.     N2
  212.      
  213.      
  214. 6.  LENGTH OF PROGRAM
  215.      
  216.     N = N1 + N2
  217.      
  218.      
  219. 7.  ESTIMATED PROGRAM LENGTH:
  220.      
  221.     N^ = n1*log2(n1) + n2*log2(n2)
  222.      
  223.     Where n1 and n2 are the number of distinct operators and
  224.     operands.  N^ is an estimator for program length.  
  225.      
  226. 8.  PROGRAM VOLUME:
  227.      
  228.     V = N * log2(n)
  229.      
  230.     This is the size of the program in bits.  Where N is program
  231.     length and n is the vocabulary.  This is because we need
  232.     log2(n) bits for each symbol and there are N symbols.
  233.      
  234.      
  235. 9.  POTENTIAL VOLUME
  236.      
  237.     V* = (2 + n2*) * log2(2 + n2*)
  238.      
  239.     This represents the size of the algorithm if it existed as a
  240.     built-in function or a subprogram.  It is the most compact
  241.     form of the algorithm.  The 2 is the minimum number of opera-
  242.     tors the procedure name and a grouping symbol needed to per-
  243.     form the function. The n2* represents the minimum number of
  244.     operands needed if the algorithm existed as a built-in func-
  245.     tion.  The n2* can be viewed as the minimum number of
  246.     input/output parameters for the algorithm if it existed as a
  247.     builtin function.
  248.      
  249.      
  250. 10. PROGRAM LEVEL
  251.      
  252.     L = (V* / V)
  253.      
  254.     This measures the level at which the program was written.
  255.     The the closer the volume V is to the potential volume V* the
  256.     higher the level.
  257.      
  258.      
  259. 11. PROGRAM LEVEL APPROXOMATION
  260.      
  261.     L^ = (n1* / n1) * (n2 * N2)
  262. The Halstead Tool                                          Page 6
  263.      
  264.     This is an approximation for program level.
  265.      
  266.      
  267. 12. INTELLIGENCE CONTENT
  268.      
  269.     I = L^ * V
  270.      
  271.     This is the amount of information contained in a program.
  272.      
  273.      
  274. 13. PROGRAMMING EFFORT
  275.      
  276.     E = ( V / L )
  277.      
  278.     The effort of programming increases as the volume of the pro-
  279.     gram increases and decreases as the level increases.  This
  280.     means the larger a program the more difficult the effort and
  281.     the higher the level of implemenation the the easier the
  282.     effort.  This effort also can be viewed as the number of ele-
  283.     mentary discriminations necessary to complete a program.
  284.     [Fitz Lov]
  285.      
  286.      
  287. 14. PROGRAMMING TIME
  288.      
  289.     T^ = E / S = (V ** 2) / (S * V*)
  290.      
  291.     The amount of time required to implement an algorithm is
  292.     directly proportional to the programing effort E divided by a
  293.     constant S.  S is the speed of the programmer, or the number
  294.     of mental discriminations per second.  Halstead calculated S
  295.     equaled 18.  This relates to the work of Stroud, a psycholo-
  296.     gist,  who estimates S between 5 and 20. [Str], [Hal]
  297.      
  298.      
  299. 15. LANGUAGE LEVEL
  300.      
  301.     lambda = L * V*
  302.      
  303.     lambda = L**2 * V
  304.      
  305.     This measure enables us to rank languages in terms of their
  306.     expressive power.  The higher the measure the higher the
  307.     levle of the langusage.  For example Pascal has a lambda
  308.     greater than the lambda for Fortran.
  309.      
  310.      
  311. 16. NUMBER OF DELIVERED ERRORS
  312.      
  313.      
  314.     B = (E ** 2/3) / E0
  315.      
  316.     B^ = (E ** 2/3) / 3000
  317.      
  318. The Halstead Tool                                          Page 7
  319.     B^ = V / 3000
  320.      
  321.     E0 is the mean number of elementary discriminations between
  322.     errors. E0 has been estimated to be 3000.
  323.      
  324.      
  325. 17. Modularization
  326.      
  327.     n log2 (n/2) = M((n-n*)/M + n*) log2 (( (n-n*) / M ) /2)
  328.      
  329.     M is the number of modules the program should be divided
  330.     into.
  331.       
  332. OUTPUT FORMAT
  333.      The output format will be organized by Ada  units  contained
  334. in  compilation  unit  specified.   The metrics computed for each
  335. nested unit will  be  displayed  in  reverse  linear  elaboration
  336. order.   This  means  the  most deeply nested units will have the
  337. metrics computed for them appear first in the report.  The output
  338. format  below  has  each  column representing a different metric.
  339. The  numbers  heading  each  column  correspond  to  the  metrics
  340. described  above.   An  example  output  for library unit appears
  341. below.
  342.      The following is a sample input and output from HALSTEAD:
  343. SAMPLE INPUT:
  344. ----------------------------------------------------------------
  345. package SCANNERS is
  346.     .
  347.     .
  348.     .
  349. procedure scan_Delimited(       --| Scan string delimited by a single character
  350.     Scanner: in out scanner_Type;
  351.     S: in string
  352.     )
  353. is
  354.     quote: character;
  355. begin
  356.     Scanner.First := Scanner.Index;
  357.     if Scanner.Index <= Scanner.Max_Index then
  358.         quote := S(Scanner.Index);
  359.         Scanner.Index := Scanner.Index + 1;
  360.         Scanner.First := Scanner.Index;
  361.         while Scanner.Index <= Scanner.Max_Index 
  362.               and then S(Scanner.Index) /= quote
  363.         loop
  364.           Scanner.Index := Scanner.Index + 1;
  365. The Halstead Tool                                          Page 8
  366.         end loop;
  367.     end if;
  368.     Scanner.Length := Scanner.Index - Scanner.First;
  369.     Scanner.Last := Scanner.Index - 1;
  370.     if Scanner.Index <= Scanner.Max_Index
  371.     and then S(Scanner.Index) = quote then      -- Null string?
  372.         Scanner.Index := Scanner.Index + 1;
  373.     end if;
  374. end scan_Delimited;
  375. ----------------------------------------------------------------
  376. SAMPLE OUTPUT:
  377.  PROCEDURE BODY OF SCANNERS.SCAN_DELIMITED AT LINE         205
  378. UNIQUE OPERATORS                 17     UNIQUE OPERANDS                11
  379. TOTAL OPERATORS                  60     TOTAL OPERANDS                 61
  380. VOCABULARY                       28
  381. PROGRAM LENGTH                  121     ESTIMATED LENGTH              107.54
  382. PROGRAM VOLUME                  579.68  POTENTIAL VOLUME               15.50
  383. PROGRAM LEVEL                      .03  ESTIMATED LEVEL                78.94
  384. INTELLIGENCE CONTENT          45760.71  PROGRAMMING EFFORT          21674.78
  385. PROGRAMMING TIME               4334.96  LANGUAGE LEVEL                   .41
  386. DELIVERED ERRORS                  4.17  ESTIMATED ERRORS                 .19
  387. REFERENCES
  388.      
  389.      
  390. [Els]   Elshoff, James, L., "Measuring Commercial PL/1 Programs
  391.         Using Halstead's Criteria", SIGPLAN Notices, May 76, pp38-46
  392.      
  393. [Fitz Lov]   Fitzsimmons, A., Love, T. "A Review and Evaluation of
  394.         Software Science", Computing Surveys, Vol. 10, No. 1, March 
  395.         1978, pp3-18
  396.      
  397. [Hal]   Halstead, M. H., Elements of Software Science, Elsevier North
  398.         Holland, Inc., Operating and Proramming Systems Series, New 
  399.         York, 1977
  400.      
  401. [Str]   Stroud, John, M., The Fine Structure of Psychological Time,
  402.         "Annals of New York Academy of Sciences", 1966, pp623-631
  403. The Halstead Tool                                          Page 9
  404. APPENDIX A:  INSTALLATION AND MODIFICATION
  405. Note: This version of HALSTEAD ignores the LIBRARY parameter.  The
  406. directory containing the AIE program library must be your default
  407. directory when you run HALSTEAD.  This is a limitation of the AIE
  408. Program Library Manager which should be corrected at some time in the
  409. future.
  410. To use the HALSTEAD tool you must:
  411.  1. Be a "HIF User".  See the Byron/AIE Programmers Reference Manual
  412.     for details.  This requires that certain logical symbols be defined
  413.     and that you have run the ADDUSER tool to make yourself known to
  414.     the HIF database.
  415.  2. Define a symbol HALSTEAD so that VMS knows what executable to run
  416.     when you type the HALSTEAD command.  For example:
  417.       $ HALSTEAD :== $USER1:[NOSC.TOOLS]HALSTEAD.EXE
  418.      NOTE: The full path name of the executable is required in the 
  419.      definition of the symbol.   The pathname given here is just an
  420.      example and will be different on your system.
  421.  3. Create a Byron/AIE program library and use the Byron/AIE compiler
  422.     front end to analyze source code into it.  The AIEPLIB and AIECOMP
  423.     commands are used respectively.
  424.  4. Enter a command with appropriate parameters.  For example,
  425.       $ HALSTEAD(("MYPROG", "TEST.OUT"));
  426.     Entering the command with no parameters gives a brief description
  427.     of how to use the tool.
  428. To build the HALSTEAD tool:
  429.  1. Compile all the abstractions into a program library (see READ.ME in
  430.     abstractions directory for details).  
  431.  2. Compile everything named in the HALSTEAD.CO file into the program library
  432.     containing the abstractions or a sublibrary whose parent library contains 
  433.     all the abstractions.  HALSTEAD.CO lists file names in a correct 
  434.     compilation order.
  435.  3. Link HALSTEAD with the program library where everything was compiled.
  436.     To do this using the DEC Ada compiler type:
  437.     $ ACS LINK HALSTEAD
  438. Files contained in the HALSTEAD.SOURCE directory:
  439. BLOCKU.SPC      BLOCKU.BDY      COMLIN.SPC
  440. The Halstead Tool                                         Page 10
  441. COMLIN.BDY      DEFS.SPC        COUNTYPE.SPC    COUNT.SPC
  442. COUNT.BDY       COUNTYPE.BDY    DEFS.BDY        HDB.SPC
  443. HDB.BDY         SCTYPESP.SPC    SCNAMEEX.SPC
  444. SCCONSTRA.SPC   IHSUBTYPE.DAT   OBJ.SPC OBJ.BDY
  445. IHSERIES.DAT    IHAGGNAM.DAT    SCCHOICE.SPC
  446. SCAGGCOM.SPC    SCAGGCOM.BDY    IHCASEAL.DAT
  447. IHHANDLER.DAT   SCSTM.SPC       SCITEM.SPC
  448. SCALTERNA.SPC   SCALTERNA.BDY   IHBLOCKS.DAT
  449. SRCUTIL.SPC     SCBLOCKS.SPC    SCBLOCKS.BDY
  450. IHINNERR.DAT    SCCHOICE.BDY    SCCOMPUN.SPC
  451. SCCOMPUN.BDY    SCGENERAL.SPC   SCCONSTRA.BDY
  452. IHVARIABL.DAT   IHTYPEDE.DAT    IDUTILS.SPC
  453. IDUTILS.BDY     SCDEFID.SPC     SCDEFID.BDY
  454. SCGENERAL.BDY   IHGENERIC.DAT   SCGENERIC.SPC
  455. SCGENERIC.BDY   SCHEADER.SPC    SCHEADER.BDY
  456. SCVARIANT.SPC   SCINNERR.SPC    SCINNERR.BDY
  457. IHTASKDE.DAT    SCPKGDEF.SPC    SCOBJECT.SPC
  458. SCSUBPDE.SPC    SCITEM.BDY      SCITERATI.SPC
  459. SCITERATI.BDY   SCNAMEEX.BDY    SCOBJECT.BDY
  460. SCPKGDEF.BDY    SCSTM.BDY       SCSUBPDE.BDY
  461. SCTYPESP.BDY    SCVARIANT.BDY   SRCUTIL.BDY
  462. HALSTEAD.ADA
  463. To change the assignemnt of a token as either an operator, operand, or
  464. neither, see COUNT.BDY.  To change the computation of any of the HALSTEAD
  465. measures, see HDB.BDY.  The file HALSTEAD.ADA contains the driver program.  
  466. To test the HALSTEAD tool, create an AIE program library using AIEPLIB,
  467. compile [.TEST]SCANNERS.SPC and [.TEST]SCANNERS.BDY into the AIE program
  468. library using AIECOMP, make that library your default directory, and run
  469. HALSTEAD, as follows:
  470.     $ AIEPLIB [.DEMOLIB]
  471.     $ AIECOMP SCANNERS.SPC [.DEMOLIB]
  472.     $ AIECOMP SCANNERS.BDY [.DEMOLIB]
  473.     $ SET DEFAULT [.DEMOLIB]
  474.     $ HALSTEAD(("SCANNERS"), "SCANNERS.OUT");
  475. Then, verify that the file SCANNERS.OUT is the same as that shipped with
  476. this release.
  477. ::::::::::::::
  478. halstead.rno
  479. ::::::::::::::
  480. .RM 65        ! right margin makes page ~65 chars and almost centered
  481. .PS ,65        ! lines page numbers up with right margin
  482. .STHL ,,,0,,,,,    ! turns off section numbering
  483. .KEEP        ! Keep blank lines in literal text
  484. .T The Halstead Tool
  485.  
  486. .C
  487. The Halstead Tool
  488. .HL Command Format
  489. .LT
  490.  
  491. -- Halstead : Computes HALSTEAD's software science formulas for Ada
  492. --            program units 
  493. -- Version 3.01-1.01
  494.  
  495.  
  496. subtype STRING_TYPE is STRING;
  497. type    STRING_LIST is array (POSITIVE range <>) of STRING_TYPE;
  498.  
  499. procedure HALSTEAD(
  500.     UNITS     : in STRING_LIST;
  501.     OUTPUT    : in STRING := "";
  502.     LIBRARY   : in STRING := "_AIELIB";
  503.     );
  504.  
  505. -- UNITS    : Names of the Ada compilation units
  506. -- OUTPUT   : Name of the report file (defaults to standard output)
  507. -- LIBRARY  : Name of the program library
  508.  
  509. .EL
  510.  
  511. .HL PARAMETERS
  512. .LT
  513. UNITS      This parameter is a list of string values, each of which is
  514.            the name of a unit which is to be analyzed.  This parameter
  515.            is required and the list must have at least one value.  A
  516.            subunit may be specified using a qualified name, as in
  517.            ("PARENT.SUBUNIT"), which would analyze the subunit called
  518.            SUBUNIT of the compilation unit PARENT.
  519.      
  520. OUTPUT     This is the name of the output file.  It is optional and if it
  521.            is not used, output will be directed to standard output.
  522.      
  523. LIBRARY    This parameter is a string which is the program library
  524.            containing the compilation units to be analyzed.  This
  525.            This parameter is optional and defaults to "_AIELIB"
  526.        (WARNING: in the current release, this parameter is ignored)
  527. .EL
  528. .P     
  529. As an example assume that there exists a program library called
  530. [._AIELIB] and that it is the current directory.  Also assume that in
  531. the program library there exists a compilation unit which is a procedure
  532. called MAIN.  The objective is to run the HALSTEAD tool on the unit
  533. MAIN.  The following command can be used:
  534. .lt     
  535.  
  536.      $ HALSTEAD(UNITS => ("MAIN"));
  537.  
  538. .el     
  539. This will compute the Halstead metrics on the unit MAIN and write
  540. the report to the default output file.
  541. .p     
  542. Note that an implicit specification is constructed by the Byron/AIE
  543. compiler front end for any compilation unit that does not have an
  544. explicit specification.  The HALSTEAD tool does not distinguish these
  545. implicit specifications from explicit specifications.  In the above
  546. example, the metrics will be computed for both the specification and
  547. body of MAIN, regardless of whether or not a source file containing a
  548. specification for MAIN was compiled into the library.
  549.  
  550. .HL DESCRIPTION
  551. .p     
  552. The Halstead tool uses the number of operands and operators in the
  553. program to compute the expected length of the program.  Each symbol in
  554. the program is classified as an operand or an operator.  Operators are
  555. mathematical functions such as +, -, *, and /, as well as parenthesis
  556. and subprogram calls.  Operands are constants and variables.  From the
  557. number of operands and operators, Halstead makes predictions about the
  558. program such as intelligence content, number of expected bugs,
  559. programming effort, and the level at which the program is written.  See
  560. [Els].
  561. .p     
  562. The metrics are computed on a compilation unit by breaking it down into
  563. its fundamental units. These are the basic units out of which Ada
  564. programs are built.  These are subprograms, packages, and tasks.  The
  565. metrics are computed in a lexically nested fashion.  For example inside
  566. a package body which contains subprogram bodies in it each of the
  567. subprograms has the metrics computed for it.
  568. .hl PREPARATION
  569. .p     
  570. HALSTEAD computes the metrics for an ADA program by using the
  571. source program's DIANA representation.  Therefore it is necessary
  572. to have the source program's DIANA in an ADA program library
  573. before running HALSTEAD.  This can be accomplished in a number of
  574. steps.
  575. .lt     
  576.  
  577.      1. First it is necessary to create an ADA program library which will
  578.         contain the DIANA representations of the source program which
  579.         HALSTEAD will analyze.  This is accomplished by the command:
  580.      
  581.         AIEPLIB
  582.      
  583.      
  584.         This command creates a directory called [._AIELIB] in the directory it
  585.         is executed from.
  586.      
  587.      2. Following this it is necessary to successfully run the source
  588.         program through ADASEM, which is semantics phase of the ADA
  589.         compiler. This generates the DIANA representation for the source
  590.         program. In order to run the semantics phase execute the command:
  591.  
  592.         ADASEM SOURCE.ADA
  593.  
  594. .el
  595.  
  596. .HL RESTRICTIONS
  597. .p     
  598. It is important to note that Halstead places some restrictions on
  599. the program whose estimates are being computed.  It must be a
  600. "pure" program.  Halstead defines a pure program to be one that
  601. does not contain any of the following constructions.
  602. .LT     
  603.      
  604.       1. No complementary operators.
  605.      
  606.          There cannot be successive applications of two comple-
  607.          mentary operations to the same operand. For example:
  608.      
  609.          z - t + t -> r
  610.      
  611.      
  612.       2. There cannot be ambigous operands.
  613.      
  614.          A given operand cannot refer to different objects at
  615.          different times in the program.  For instance in the
  616.          following example r represents first a sum and then a
  617.          product.
  618.      
  619.      
  620.          p + q -> r   r * r -> r
  621.      
  622.          Should be written as:
  623.      
  624.          p + q -> t   t * t -> r
  625.      
  626.      
  627.       3. There cannot be synonomous operands.
  628.      
  629.          Two different names for the same object.  There can only
  630.          exist one name for one object.
  631.      
  632.      
  633.          p + q -> t1  p + q -> t2  t1 * t2 -> r
  634.      
  635.          Should be written as:
  636.      
  637.          p + q -> t1  t1 * t1 -> r
  638.      
  639.      
  640.       4. Common subexpressions cannot exist.
  641.      
  642.          Any expression which is used more than once must be
  643.          assigned to a variable.
  644.      
  645.          (p + q) * (p + q) -> r
  646.      
  647.          Should be written as:
  648.      
  649.          (p + q) -> t1  t1 ** 2 -> r
  650.      
  651.      
  652.       5. No unwarranted assignments.
  653.      
  654.          If an assignment is made and the value used only once
  655.          the assignment is unnecessary.
  656.      
  657.          p + q -> t1   t1 ** 2 -> r
  658.      
  659.          Should be written as:
  660.      
  661.          (p + q) ** 2 -> r
  662.      
  663.      
  664.       6. Expressions should be factored.
  665.      
  666.          p*p + 2*p*q + q*q
  667.      
  668.          Should be written as:
  669.      
  670.          (p + q) ** 2
  671.      
  672. .el     
  673. .hl METRICS COMPUTED     
  674. .p     
  675. Halstead begins by defining the following symbols:
  676. .lt     
  677.      
  678. 1.  NUMBER OF UNIQUE OPERATORS
  679.      
  680.     n1
  681.      
  682.      
  683. 2.  NUMBER OF UNIQUE OPERANDS
  684.      
  685.     n2
  686.      
  687.      
  688. 3.  THE VOCABULARY
  689.      
  690.     n = n1 + n2
  691.      
  692.      
  693. 4.  TOTAL NUMBER OF OPERATORS
  694.      
  695.     N1
  696.      
  697.      
  698. 5.  TOTAL NUMBER OF OPERANDS
  699.      
  700.      
  701.     N2
  702.      
  703.      
  704. 6.  LENGTH OF PROGRAM
  705.      
  706.     N = N1 + N2
  707.      
  708.      
  709. 7.  ESTIMATED PROGRAM LENGTH:
  710.      
  711.     N^ = n1*log2(n1) + n2*log2(n2)
  712.      
  713.     Where n1 and n2 are the number of distinct operators and
  714.     operands.  N^ is an estimator for program length.  
  715.      
  716. 8.  PROGRAM VOLUME:
  717.      
  718.     V = N * log2(n)
  719.      
  720.     This is the size of the program in bits.  Where N is program
  721.     length and n is the vocabulary.  This is because we need
  722.     log2(n) bits for each symbol and there are N symbols.
  723.      
  724.      
  725. 9.  POTENTIAL VOLUME
  726.      
  727.     V* = (2 + n2*) * log2(2 + n2*)
  728.      
  729.     This represents the size of the algorithm if it existed as a
  730.     built-in function or a subprogram.  It is the most compact
  731.     form of the algorithm.  The 2 is the minimum number of opera-
  732.     tors the procedure name and a grouping symbol needed to per-
  733.     form the function. The n2* represents the minimum number of
  734.     operands needed if the algorithm existed as a built-in func-
  735.     tion.  The n2* can be viewed as the minimum number of
  736.     input/output parameters for the algorithm if it existed as a
  737.     builtin function.
  738.      
  739.      
  740. 10. PROGRAM LEVEL
  741.      
  742.     L = (V* / V)
  743.      
  744.     This measures the level at which the program was written.
  745.     The the closer the volume V is to the potential volume V* the
  746.     higher the level.
  747.      
  748.      
  749. 11. PROGRAM LEVEL APPROXOMATION
  750.      
  751.     L^ = (n1* / n1) * (n2 * N2)
  752.      
  753.     This is an approximation for program level.
  754.      
  755.      
  756. 12. INTELLIGENCE CONTENT
  757.      
  758.     I = L^ * V
  759.      
  760.     This is the amount of information contained in a program.
  761.      
  762.      
  763. 13. PROGRAMMING EFFORT
  764.      
  765.     E = ( V / L )
  766.      
  767.     The effort of programming increases as the volume of the pro-
  768.     gram increases and decreases as the level increases.  This
  769.     means the larger a program the more difficult the effort and
  770.     the higher the level of implemenation the the easier the
  771.     effort.  This effort also can be viewed as the number of ele-
  772.     mentary discriminations necessary to complete a program.
  773.     [Fitz Lov]
  774.      
  775.      
  776. 14. PROGRAMMING TIME
  777.      
  778.     T^ = E / S = (V ** 2) / (S * V*)
  779.      
  780.     The amount of time required to implement an algorithm is
  781.     directly proportional to the programing effort E divided by a
  782.     constant S.  S is the speed of the programmer, or the number
  783.     of mental discriminations per second.  Halstead calculated S
  784.     equaled 18.  This relates to the work of Stroud, a psycholo-
  785.     gist,  who estimates S between 5 and 20. [Str], [Hal]
  786.      
  787.      
  788. 15. LANGUAGE LEVEL
  789.      
  790.     lambda = L * V*
  791.      
  792.     lambda = L**2 * V
  793.      
  794.     This measure enables us to rank languages in terms of their
  795.     expressive power.  The higher the measure the higher the
  796.     levle of the langusage.  For example Pascal has a lambda
  797.     greater than the lambda for Fortran.
  798.      
  799.      
  800. 16. NUMBER OF DELIVERED ERRORS
  801.      
  802.      
  803.     B = (E ** 2/3) / E0
  804.      
  805.     B^ = (E ** 2/3) / 3000
  806.      
  807.     B^ = V / 3000
  808.      
  809.     E0 is the mean number of elementary discriminations between
  810.     errors. E0 has been estimated to be 3000.
  811.      
  812.      
  813. 17. Modularization
  814.      
  815.     n log2 (n/2) = M((n-n*)/M + n*) log2 (( (n-n*) / M ) /2)
  816.      
  817.     M is the number of modules the program should be divided
  818.     into.
  819.       
  820. .el
  821. .HL OUTPUT FORMAT
  822. .p     
  823. The output format will be organized by Ada units contained in
  824. compilation unit specified.  The metrics computed for each nested
  825. unit will be displayed in reverse linear elaboration order.  This
  826. means the most deeply nested units will have the metrics computed
  827. for them appear first in the report.  The output format below has
  828. each column representing a different metric.  The numbers heading
  829. each column correspond to the metrics described above. An example
  830. output for library unit appears below.
  831. .P
  832. The following is a sample input and output from HALSTEAD:
  833. .LT
  834. SAMPLE INPUT:
  835.  
  836. ----------------------------------------------------------------
  837. package SCANNERS is
  838.  
  839.     .
  840.     .
  841.     .
  842.  
  843. procedure scan_Delimited(    --| Scan string delimited by a single character
  844.     Scanner: in out scanner_Type;
  845.     S: in string
  846.     )
  847. is
  848.     quote: character;
  849.  
  850. begin
  851.     Scanner.First := Scanner.Index;
  852.     if Scanner.Index <= Scanner.Max_Index then
  853.     quote := S(Scanner.Index);
  854.     Scanner.Index := Scanner.Index + 1;
  855.     Scanner.First := Scanner.Index;
  856.     while Scanner.Index <= Scanner.Max_Index 
  857.           and then S(Scanner.Index) /= quote
  858.     loop
  859.       Scanner.Index := Scanner.Index + 1;
  860.     end loop;
  861.     end if;
  862.     Scanner.Length := Scanner.Index - Scanner.First;
  863.     Scanner.Last := Scanner.Index - 1;
  864.     if Scanner.Index <= Scanner.Max_Index
  865.     and then S(Scanner.Index) = quote then    -- Null string?
  866.     Scanner.Index := Scanner.Index + 1;
  867.     end if;
  868.  
  869. end scan_Delimited;
  870.  
  871. ----------------------------------------------------------------
  872.  
  873.  
  874. SAMPLE OUTPUT:
  875.  
  876.  
  877.  PROCEDURE BODY OF SCANNERS.SCAN_DELIMITED AT LINE         205
  878.  
  879. UNIQUE OPERATORS                 17     UNIQUE OPERANDS                11
  880. TOTAL OPERATORS                  60     TOTAL OPERANDS                 61
  881. VOCABULARY                       28
  882. PROGRAM LENGTH                  121     ESTIMATED LENGTH              107.54
  883. PROGRAM VOLUME                  579.68  POTENTIAL VOLUME               15.50
  884. PROGRAM LEVEL                      .03  ESTIMATED LEVEL                78.94
  885. INTELLIGENCE CONTENT          45760.71  PROGRAMMING EFFORT          21674.78
  886. PROGRAMMING TIME               4334.96  LANGUAGE LEVEL                   .41
  887. DELIVERED ERRORS                  4.17  ESTIMATED ERRORS                 .19
  888.  
  889. .EL
  890.  
  891. .HL REFERENCES
  892. .LT     
  893.      
  894.      
  895. [Els]    Elshoff, James, L., "Measuring Commercial PL/1 Programs
  896.     Using Halstead's Criteria", SIGPLAN Notices, May 76, pp38-46
  897.      
  898. [Fitz Lov]   Fitzsimmons, A., Love, T. "A Review and Evaluation of
  899.     Software Science", Computing Surveys, Vol. 10, No. 1, March 
  900.     1978, pp3-18
  901.      
  902. [Hal]    Halstead, M. H., Elements of Software Science, Elsevier North
  903.     Holland, Inc., Operating and Proramming Systems Series, New 
  904.     York, 1977
  905.      
  906. [Str]    Stroud, John, M., The Fine Structure of Psychological Time,
  907.     "Annals of New York Academy of Sciences", 1966, pp623-631
  908. .el     
  909.     
  910. .PG
  911. .HL Appendix A: Installation and Modification
  912.  
  913. .NF
  914. .RM 80
  915. .REQUIRE "[-]read.me"
  916. ::::::::::::::
  917. release.nts
  918. ::::::::::::::
  919. 28-Feb-85    Initial release.  Does not support named program libraries.
  920.         The LIBRARY parameter on the command line is ignored.
  921.  
  922.