Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!security!genrad!grkermit!masscomp!clyde!floyd!harpo!seismo!hao!hplabs!sri-unix!broome@brl-bmd
From: broome%brl-bmd@sri-unix.UUCP
Newsgroups: net.ai
Subject: Re:  Expert systems for software debugging?
Message-ID: <15843@sri-arpa.UUCP>
Date: Fri, 20-Jan-84 08:39:38 EST
Article-I.D.: sri-arpa.15843
Posted: Fri Jan 20 08:39:38 1984
Date-Received: Fri, 27-Jan-84 05:46:33 EST
Lines: 23

From:  Paul Broome <broome@brl-bmd>


        Debugging is a black art, not at all algorithmic, but almost totally
        heuristic.  There is a lot of expert knowledge around about how
        to debug faulty programs, but it is rarely written down or
        systemetized.  Usually it seems to reside solely in the minds of
        a few "debugging whizzes".

        Does anyone know of an expert system that assists in software
        debugging? Or any attempts (now or in the past) to produce such
        an expert?

There are some good ideas and a Prolog implementation in Ehud Shapiro's
Algorithmic Program Debugging, which is published as an ACM distinguished
dissertation by MIT Press, 1983.  One of his ideas is "divide-and-query:
a query-optimal diagnosis algorithm," which is essentially a simple binary
bug search.  If the program is incorrect on some input then the program
is divided into two roughly equal subtrees and the computation backtracks
to the midpoint.  If this intermediate result is correct then the
first subtree is ignored and the bug search is repeated on the second
subtree.   If the intermediate result is incorrect then the search
continues instead on the first subtree.