School of Computing

One right does make a wrong

Thomas Davie and Olaf Chitil

In Pre-Proceedings of the Seventh Symposium on Trends in Functional Programming, TFP 2006, pages 182-196, April 2006.

Abstract

Algorithmic debugging is a semi-automatic method for locating bugs in programs. An algorithmic debugger asks a user a series of questions about the intended behaviour of the program. Here we present two new methods that reduces the number of questions a user must answer to locate a bug.

First, we describe a heuristic based on comparing computations of the same program with different inputs. Besides a computation that exhibits some erroneous behaviour, we use information from computations that produce correct results. The heuristic uses program slices to identify areas of code that are likely to be correct.

Secondly, we describe a method of compressing the search tree that guides the questions of an algorithmic debugger. This compression is particularly successful when used in combination with our heuristic.

Both heuristic and tree-compression are applicable to algorithmic debugging in general. We have implemented it for locating bugs in Haskell programs.

Download publication 438 kbytes (PDF)

Bibtex Record

@inproceedings{2472,
author = { Thomas Davie and Olaf Chitil},
title = {One Right Does Make a Wrong},
month = {April},
year = {2006},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/2006/2472},
    publication_type = {inproceedings},
    submission_id = {8026_1170268601},
    booktitle = {Pre-Proceedings of the Seventh Symposium on Trends in Functional Programming, TFP 2006},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014