School of Computing

Algorithmic debugging with cyclic traces of lazy functional programs

Yong Luo and Olaf Chitil

Technical report 9-07, University of Kent, Computing Laboratory, UK, August 2007.

Abstract

We have proved the correctness of algorithmic debugging if the traces are acyclic. For cyclic traces, however, does algorithmic debugging still work? There does not exist a common understanding of how to debug cyclic traces in functional programming communities for a long time. In this paper we give two small examples to demonstrate that it is extremely difficult to find a generic algorithmic debugging scheme for cyclic traces. We conjecturre that it is impossible to have a generic scheme for cyclic traces, because the examples are very small and the choices of reasonable debugging trees are very limited. We also present acyclic traces in which constants are shared unless shared constants result in a cycle. The normal algorithmic debugging scheme works fine for acyclic traces and the proof is very similar to our previous paper.

Download publication 217 kbytes (PDF)

Bibtex Record

@techreport{2645,
author = {Yong Luo and Olaf Chitil},
title = {Algorithmic Debugging with Cyclic Traces of Lazy Functional Programs},
month = {August},
year = {2007},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/2007/2645},
    publication_type = {techreport},
    submission_id = {22707_1203704843},
    type = {Technical report},
    number = {9-07},
    address = {UK},
    institution = {University of Kent, Computing Laboratory},
}

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

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

Last Updated: 21/03/2014