Path: utzoo!utgpu!water!watmath!clyde!rutgers!ukma!psuvm.bitnet!uh2
From: UH2@PSUVM.BITNET (Lee Sailer)
Newsgroups: comp.software-eng
Subject: Re: Software Complexity Measures Will Never Be Accurate
Message-ID: <30176UH2@PSUVM>
Date: 19 Jan 88 14:50:11 GMT
References: <5874@sol.ARPA>
Organization: Penn Sate Erie--School of Business
Lines: 34

In article <5874@sol.ARPA>, crowl@cs.rochester.edu (Lawrence Crowl) says:
>
>Algorithmic measures of algorithmic complexity will never be accurate.  The
     
Never say "never".  8-)
     
>problem is that a larger set of assumptions, or programmer state, allows
>smaller programs.  Since algorithms are unlikely to be able to capture the set
>of assumptions in a piece of code, the measures must rely on program size,
>operator relationships, etc.
     
This is a good point.  In *today's* programming languages, there are too many
pieces of required knowledge that are not coded, so complexity measures
based on the code alone will be of limited accuracy.
     
This bring to my mind two developments in CS theory.
     
PROGRAM CORRECTNESS PROOFS:  All the work on this seems to require the
addition of "assertions" to the code, that is, logical statements of
all the assumptions that must hold before, after, and even during the
execution of a piece of program.  (See Gries, the Science of Programming)
     
SPECIFICATION LANGUAGES:  The ideal spec. lang. would lead to the user
making explicit all of the *unstated* assumptions about the process.
Furthermore, research is moving towards specification which can be executed
directly, omitting the coding step altogether.
     
I conclude then that complexity measures should at least have both the code
and the specifications as input.  Complexity could be perceived as
sort of a ratio of actual code complexity to specification complexity.
     
Disclaimer:  I am interested in these ideas, but unread.  If this sounds
to you like something that someone has written, please send me the reference.