Skip to main content

Algorithmic debugging for complex lazy functional programs

Faddegon, Maarten Algorithmic debugging for complex lazy functional programs. Doctor of Philosophy (PhD) thesis, University of Kent,. (KAR id:63869)

Language: English
Download (934kB) Preview
[thumbnail of 220thesis.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format


An algorithmic debugger finds defects in programs by systematic search. It relies on the programmer to direct the search by answering a series of yes/no questions about the correctness of specific function applications and their results. Existing algorithmic debuggers for a lazy functional language work well for small simple programs but cannot be used to locate defects in complex programs for two reasons: Firstly, to collect the information required for algorithmic debugging existing debuggers use different but complex implementations. Therefore, these debuggers are hard to maintain and do not support all the latest language features. As a consequence, programs with unsupported language features cannot be debugged. Also inclusion of a library using unsupported languages features can make algorithmic debugging unusable even when the programmer is not interested in debugging the library. Secondly, algorithmic debugging breaks down when the size or number of questions is too great for the programmer to handle. This is a pity, because, even though algorithmic debugging is a promising method for locating defects, many real-world programs are too complex for the method to be usuable. I claim that the techniques in in this thesis make algorithmic debugging useable for a much more complex lazy functional programs. I present a novel method for collecting the information required for algorithmically debugging a lazy functional program. The method is non-invasive, uses program annotations in suspected modules only and has a simple implementation. My method supports all of Haskell, including laziness, higher-order functions and exceptions. Future language extensions can be supported without changes, or with minimal changes, to the implementation of the debugger. With my method the programmer can focus on untrusted code -- lots of trusted libraries are unaffected. This makes traces, and hence the amount of questions that needs to be answered, more manageable. I give a type-generic definition to support custom types defined by the programmer. Furthermore, I propose a method that re-uses properties to answer automatically some of the questions arising during algorithmic debugging, and to replace others by simpler questions. Properties may already be present in the code for testing; the programmer can also encode a specification or reference implementation as a property, or add a new property in response to a statement they are asked to judge.

Item Type: Thesis (Doctor of Philosophy (PhD))
Thesis advisor: Chitil, Olaf
Uncontrolled keywords: tracing debugging lazy-evaluation Haskell property property-based-testing defect defect-localization
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
SWORD Depositor: System Moodle
Depositing User: System Moodle
Date Deposited: 06 Oct 2017 13:33 UTC
Last Modified: 16 Feb 2021 13:49 UTC
Resource URI: (The current URI for this page, for reference purposes)
  • Depositors only (login required):


Downloads per month over past year