Search 250 million research papers

Application of program slicing in algorithmic debugging

Mariam Kamkar · Information and Software Technology · 1998

Cited by 20

Debugging Techniques for Declarative Languages: Profiling, Program Slicing, and Algorithmic Debugging

Josep Francesc, Silva Galiana, Germán Vidal Oriola · 2007

Prologue I enjoy reading books about neutron stars and black holes, and one of my best friends use to say that I am losing my time because I will never see a black hole, and it is stupid to study something that will never influence my live... One hundred years ago people used to read science fiction about the space and, nowadays, hundreds of satellites are rounding the Earth: what is a dream today will be a fact tomorrow. This is the way in which researchers must think, since much of their work is useless today but, possibly, another researcher will make it useful tomorrow. In fact, this is an annoying property of research: sometimes it is blind. When Fleming discovered penicillin after the first world war, he did not know that he was going to save millions of lives, and the scientific community did not realize about the importance of his discovery until the second world war. Most of the results of this thesis has been implemented and applied to a real language, thus producing useful technology; but others simply no. Some results are theoretical results that I have not been able to apply and I simply hope they will become useful in the future.

Cited by 0

An Analysis of the Current Program Slicing and Algorithmic Debugging Based Techniques

Silva Galiana, Josep Francesc · RiuNet (Politechnical University of Valencia) · 2012

This thesis presents a classification of program slicing based techniques. The classification allows us to identify the differences between existing techniques, but it also allows us to predict new slicing techniques. The study identifies and compares the dimensions that influence current techniques.

Cited by 0Open access

Concurrent algorithmic debugging

Yossi Lichtenstein, Ehud Shapiro · ACM SIGPLAN Notices · 1988

Algorithmic Debugging is a theory of debugging that uses queries on the compositional semantics of a program in order to localize bugs. It uses the following principle: if a computation of a program's component gives an incorrect result, while all the subcomputations it invokes compute correct results, then the code of this component is erroneous. Algorithmic Debugging is applied, in this work, to reactive systems, in particular to programs written in Flat Concurrent Prolog (FCP). Debugging reactive systems is known to be more difficult than the debugging of functional systems. A functional system is fully described by the relation between its initial input and final output; this context-freedom is used in debugging. A reactive system continuously responds to external inputs, thus its debugging cannot make use of context-free input/output relations. Given a compositional semantic model for a concurrent programming language, we demonstrate how one can directly apply the ideas of Algorithmic Debugging to obtain a theory of program debugging for the considered language. The conflict between the context-freedom of input/ output relations and the reactive nature of concurrent systems is resolved by using semantic objects which record the reactive nature of the system's components. In functional algorithmic debugging the queries relate to input/output relations; in concurrent algorithmic debugging the queries refer to semantic objects called processes which capture the reactive nature of FCP computations. A diagnosis algorithm for incorrect FCP programs is proposed. The algorithm gets an erroneous computation and using queries isolates an erroneous clause or an incomplete procedure. An FCP implementation of the diagnosis algorithm demonstrates the usefulness as well as the difficulties of Algorithmic Debugging of FCP programs.

Cited by 7Open access

Procedural Refinement by LLM-driven Algorithmic Debugging for ARC-AGI-2

Yu-Ning Qiu, Linfeng Zou, Jiong-Da Wang et al. · ArXiv.org · 2026

In complex code-generation tasks, conversation-based LLM code repair exhibits limited ability to recover from first-pass programming errors, as such code revisions are usually driven by LLMs' "plausible reasoning" rather than a formal, algorithmic debugging procedure. However, a formal foundation for such debugging exists in Udi Shapiro's theory of algorithmic program debugging (APD), which frames program repair as an explicit, stepwise procedural refinement process. In this paper, we propose a neuro-symbolic procedural refinement approach, Abduction-Based Procedural Refinement (ABPR), which couples an LLM with a meta-interpreter that materialises program execution into compact, declarative tree-structured traces, following the principles of APD. We evaluate ABPR on ARC-AGI-2, a benchmark requiring strong abstraction and debugging capabilities, and adopt Prolog as the target language due to its declarative semantics, which are well-suited to algorithmic program debugging. Our experiments show that ABPR paired with Gemini-3-Flash achieves a Pass@2 score of 56.67\% even in a language in which contemporary LLMs typically underperform. These results point towards a more auditable paradigm for program repair by integrating LLMs with classical formal methods.

Cited by 0Open access

Procedural Refinement by LLM-driven Algorithmic Debugging for ARC-AGI-2

Yu-Ning Qiu, Linfeng Zou, Jiong-Da Wang et al. · arXiv (Cornell University) · 2026

In complex code-generation tasks, conversation-based LLM code repair exhibits limited ability to recover from first-pass programming errors, as such code revisions are usually driven by LLMs' "plausible reasoning" rather than a formal, algorithmic debugging procedure. However, a formal foundation for such debugging exists in Udi Shapiro's theory of algorithmic program debugging (APD), which frames program repair as an explicit, stepwise procedural refinement process. In this paper, we propose a neuro-symbolic procedural refinement approach, Abduction-Based Procedural Refinement (ABPR), which couples an LLM with a meta-interpreter that materialises program execution into compact, declarative tree-structured traces, following the principles of APD. We evaluate ABPR on ARC-AGI-2, a benchmark requiring strong abstraction and debugging capabilities, and adopt Prolog as the target language due to its declarative semantics, which are well-suited to algorithmic program debugging. Our experiments show that ABPR paired with Gemini-3-Flash achieves a Pass@2 score of 56.67\% even in a language in which contemporary LLMs typically underperform. These results point towards a more auditable paradigm for program repair by integrating LLMs with classical formal methods.

Cited by 0Open access

Algorithmic debugging of real-world haskell programs: deriving dependencies from the cost centre stack

Maarten Faddegon, Olaf Chitil · 2015

Existing algorithmic debuggers for Haskell require a transformation of all modules in a program, even libraries that the user does not want to debug and which may use language features not supported by the debugger. This is a pity, because a promising approach to debugging is therefore not applicable to many real-world programs. We use the cost centre stack from the Glasgow Haskell Compiler profiling environment together with runtime value observations as provided by the Haskell Object Observation Debugger (HOOD) to collect enough information for algorithmic debugging. Program annotations are in suspected modules only. With this technique algorithmic debugging is applicable to a much larger set of Haskell programs. This demonstrates that for functional languages in general a simple stack trace extension is useful to support tasks such as profiling and debugging.

Cited by 8

Proving the Correctness of Algorithmic Debugging for Functional Programs

Yong Luo, Olaf Chitil · Intellect Books · 2005

This paper formally presents a model of tracing for functional programs based on a small-step operational semantics. The model records the computation of a functional program in a graph which can be utilised for various purposes such as algorithmic debugging. The main contribution of this paper is to prove the correctness of algorithmic debugging for functional programs based on the model. Although algorithmic debugging for functional programs is implemented in several tracers such as Hat, the correctness has not been formally proved before. The difficulty of the proof is to find a suitable induction principle and a more general induction hypothesis.

Cited by 7Open access

Proving the Correctness of Algorithmic Debugging for Functional Programs

Olaf Chitil, Yong Luo · 2008

This paper formally presents a model of tracing for functional programs based on a small-step operational semantics. The model records the computation of a functional program in a graph which can be utilised for various purposes such as algorithmic debugging. The main contribution of this paper is to prove the correctness of algorithmic debugging for functional programs based on the model. Although algorithmic debugging for functional programs is implemented in several tracers such as Hat, the correctness has not been formally proved before. The difficulty of the proof is to find a suitable induction principle and a more general induction hypothesis. 1

Cited by 0

Keywords: Algorithmic Debugging, Strategies

Universidad Politécnica, De Valencia, Author(s) Josep Silva · 2006

During the algorithmic debugging process, an oracle (typically the user) is prompted with equations and asked about their correctness; he answers “YES ” when the result is correct, or “NO ” when the result is wrong. Some algorithmic debuggers also accept the answer “I don’t know ” when the user cannot give an answer (maybe because the question is too complicated). After every question, some nodes of the ET leave the suspicious area which contains those nodes that can be buggy. When there is only one node in the suspicious area, the process finishes reporting this node as buggy. It should be clear that algorithmic debugging finds one bug at a time. In order to find different bugs, the process should be restarted once for each different bug. Example 1. Consider the buggy program in Figure 1 (a). This program sums a list of integers ([1,2]) and computes the square of the result with three different methods. If the three methods compute the same result the program returns T rue, if not, it returns F alse. Here, one of the three methods—the one adding the partial sums of its input number—contains a bug. From this program, an algorithmic debugger can automatically generate the ET of Figure 1 (c) (for the time being, the reader can ignore the distinction between different shapes and white and dark nodes) which, in turn, can be used to produce a debugging session as depicted in Figure 1 (b). During the debugging session, the system asks the programmer about the correctness of some ET nodes w.r.t. the intended semantics. At the end of the debugging session, the algorithmic debugger determines that the bug of the program was located in function “sum2 ” (node 26). The definition of function “sum2 ” should be: “sum2 x = div (x ∗ (decr x)) 2”. 2

Cited by 0

[12] Korel B., PELAS- Program Error Locating Assistant System, IEEE Transactions on Software Engineering,

David C. Luckham, D. Bryan, W. Mann et al. · 2007

Specification of Software, Journal of the ACM, vol.31, #3, July 1984, pp.600-627. [16] D.Rosenblum, Specifying Concurrent Systems with TSL, IEEE Software, May 1991, pp.52-61. [17] R.Seviora, Knowledge-Based Program Debugging Systems, IEEE Software, vol.4, #3, May 1987, pp.2032 [18] N.Shahmehri,Generalized Algorithmic Debugging. Ph.D. Thesis No 260, Dept. of Computer and Information Science, Linköping University, S-581 83 Linköping, Sweden. [19] E.Shapiro. Algorithmic Program Debugging. MIT Press, May 1982. [20] Winograd: Aleph: a system specification language. 1988, Stanford University, CSLI. Example of the session with the FORMAN/PASCAL assertion checker prototype . 8 Some formalism for describing similar rules remains to be developed in the framework of FORMAN. One of our goals is to formalize, for instance, debugging strategies presented in [17], [12]. 4.3 Principles of Implementation The main step in the implementation of computations over traces is the target program instrum...

Cited by 0

Debugging and Testing of Prolog Programs

Gabriella Kokai, Laszlo Harmath, Tibor Gyimothy et al. · 2007

. In this paper the IDTS (Integrated Debugging, Testing and Slicing), method is presented for the algorithmic debugging and functional testing of Prolog programs. This method integrates Shapiro's Interactive Diagnosis Algorithm with the Category-Partition Testing Method and a slicing technique. Shapiro's original method demands a lot of user interactions during the debugging process. The IDTS method can avoid irrelevant questions to the user by categorizing input parameters, and match them against test cases and test database. In addition, a slicing method is used to compute which parts of the program are relevant for the search. The IDTS method has since been used in a large ECG classifier program and in an interactive learner. 1 1 Introduction In this paper we present a method, called IDTS (Integrated Debugging, Testing and Slicing) for the algorithmic debugging and functional testing of Prolog programs. This method not only integrates Shapiro's Interactive Diagnosis Alg...

Cited by 0

Lightweight computation tree tracing for lazy functional languages

Maarten Faddegon, Olaf Chitil · ACM SIGPLAN Notices · 2016

A computation tree of a program execution describes computations of functions and their dependencies. A computation tree describes how a program works and is at the heart of algorithmic debugging. To generate a computation tree, existing algorithmic debuggers either use a complex implementation or yield a less informative approximation. We present a method for lazy functional languages that requires only a simple tracing library to generate a detailed computation tree. With our algorithmic debugger a programmer can debug any Haskell program by only importing our library and annotating suspected functions.

Cited by 0

Algorithmic program diagnosis

Ehud Shapiro · 1982

The notion of program correctness with respect to an interpretation is defined for a class of programming languages. Under this definition, if a program terminates with an incorrect output then it contains an incorrect procedure. Algorithms for detecting incorrect procedures are developed. These algorithms formalize what experienced programmers may know already.A logic program implementation of these algorithms is described. Its performance suggests that the algorithms can be the backbone of debugging aids that go far beyond what is offered by current programming environments.Applications of algorithmic debugging to automatic program construction are explored.

Cited by 99

A Transformational Approach to Debugging Lazy Functional Programs

Jan Sparud · 1996

We describe a debugger for the lazy functional language Haskell. The basic idea is to transform a Haskell program into a program that evaluates to the same result as the original program but also produces an evaluation dependence tree describing how the result was obtained. If an error is detected while running the program, the programmer can browse the evaluation dependence tree, or use algorithmic debugging, in order to try to find the erroneous definition. The method is compared to other ways of debugging lazy functional programs. Some ideas for improvements are also presented.

Cited by 9

Optimization Techniques for Algorithmic Debugging

David Insa Cabrera · 2016

Nowadays, undetected programming bugs produce a waste of billions of dollars per year to private and public companies and institutions.In spite of this, no significant advances in the debugging area that help developers along the software development process have been achieved yet.In fact, the same debugging techniques that were used 20 years ago are still being used now.Along the time, some alternatives have appeared, but there still is a long way for them to be useful enough to get into the software development process.One of them is algorithmic debugging, which abstracts the information the user has to investigate to debug the program, allowing them to focus on what is happening instead of how it is happening.This abstraction comes at a price: the granularity level of the bugs that can be detected allows for isolating wrongly implemented functions, but which part of them contains the bug cannot be found out yet.This thesis focusses on improving algorithmic debugging in many aspects.Concretely, the main aims of this thesis are to reduce the time the user needs to detect a programming bug as well as to provide the user with more detailed information about where the bug is located.To achieve these goals, some techniques have been developed to start the debugging sessions as soon as possible, to reduce the number of questions the user is going to be asked, and to augment the granularity level of those bugs that algorithmic debugging can detect, allowing the debugger in this way to keep looking for bugs even inside functions.As a result of this thesis, three completely new techniques have been defined, an already existent technique has been improved, and two new algorithmic debugging search strategies have been defined that improve the already existent ones.Besides these theoretical results, a fully functional algorithmic debugger has been implemented that contains and supports all these techniques and strategies.This debugger is written in Java, and it debugs Java code.The election of this language is justified because it is currently one of the most widely extended and used languages.Also because it contains an interesting combination of unsolved challenges for algorithmic debugging.To further increase its usability, the debugger has been later adapted as an Eclipse plugin, so it could be used by a wider number of users.These two debuggers are publicly available, so any interested person can access them and continue with the research if they wish so.Chapter 2 Debugging TechniquesIn this chapter we introduce some other debugging techniques related to Algorithmic Debugging.Some of them have been used in some techniques of this thesis, such as Trace Debugging or Omniscient Debugging, whereas other are included due to their close relation to Algorithmic Debugging, such as Abstract Diagnosis, Abstract Debugging, or Delta Debugging.

Cited by 0Open access

AUTOMATIC DETECTION OF INCORRECT RULES IN EQUIVALENT TRANSFORMATION PROGRAMS

Shinya Miyajima, Kiyoshi Akama, Yuya Wakamatsu · 2009

A method of detecting bugs automatically in equivalent transformation (ET) programs is proposed. For this purpose, theories for finding contradictions within given ET programs are constructed. By applying the proposed method, a part of a program which includes incorrectness is detected. Moreover the proposed method does not use oracles. Keywords: Equivalent transformation model, Algorithmic debugging, Program correct- ness

Cited by 1

Tracing and Debugging Lazy Functional Computations

Jan Sparud · 1999

Functional programming languages have many advantages over the conventional alternative of procedural languages. For example, program construction is more rapid, more modular and less error-prone. Programs themselves are more concise. Moreover, lazy functional languages are declarative and allow the programmer to write programs where operational issues such as the evaluation order are left implicit. However, programs do not always work first time. When they fail, programmers cannot always see the reason immediately, and they need tools to help them find it. In traditional, procedural programming languages, fault-tracing or debugging can be based on studying sequences of events. But in a lazy functional language, the sequence of events is not so easily presented, nor is it what the programmer really needs. This thesis presents several approaches to tracing and debugging lazy functional programs. In the first part, a method based on algorithmic debugging is presented. An algorithmic...

Cited by 8

Keynote Speeches

Franz Wotawa, Zheng Hu · 2023

In this talk, I discuss automated fault localization in spreadsheets, considering various techniques originating from automated and algorithmic program debugging, like model-based debugging, spectrum-based fault localization, and smell detection using machine learning. I will provide an overview of the current state of work and the experimental results obtained. In addition, I will focus on the most recent research work where we investigated the usability of debugging. In particular, we carried out user studies identifying challenges regarding tool overreliance and the optimal presentation of results to users. We found out that textual feedback from debugging tools is better perceived when compared with other means of presentation. The provided results might also be of interest to other researchers working on software engineering tools and, in particular, debugging support functionality.

Cited by 0Open access

Keynote Speeches

Franz Wotawa, Zheng Hu · 2023

In this talk, I discuss automated fault localization in spreadsheets, considering various techniques originating from automated and algorithmic program debugging, like model-based debugging, spectrum-based fault localization, and smell detection using machine learning. I will provide an overview of the current state of work and the experimental results obtained. In addition, I will focus on the most recent research work where we investigated the usability of debugging. In particular, we carried out user studies identifying challenges regarding tool overreliance and the optimal presentation of results to users. We found out that textual feedback from debugging tools is better perceived when compared with other means of presentation. The provided results might also be of interest to other researchers working on software engineering tools and, in particular, debugging support functionality.

Cited by 0Open access