Existing algorithmic debugging methods which can locate faults under the guidance of a system have a number of shortcomings. For example, some cannot be applied to imperative languages with side effects;some can locat...
详细信息
Existing algorithmic debugging methods which can locate faults under the guidance of a system have a number of shortcomings. For example, some cannot be applied to imperative languages with side effects;some can locate a faulty function but cannot locate a faulty statement;and some cannot detect faults related to missing statements. This paper presents an algorithmic critical slice-based fault-locating method for imperative languages. Program faults are first classified into two categories: wrong-value faults and missing-assignment faults. The critical slice with respect to a variable-value error is a set of statements such that (1) a wrong-value fault contained in any instruction in the critical slice may have caused that variable-value error, and (2) a wrong-value fault contained in any instruction outside the critical slice could never have caused that variable-value error. The paper also classifies errors found during program testing into three categories: wron g-output errors, missing-output errors, and infinite-loop errors with no output. It finally shows that it is possible to algorithmically locate any fault, including missing statements, for each type of error.
Attribute grammars provide a formal means to specify the semantics of context free grammars. In this work, we propose a method to debug attribute grammars by applying algorithmic debugging to the paradigm of attribute...
详细信息
Attribute grammars provide a formal means to specify the semantics of context free grammars. In this work, we propose a method to debug attribute grammars by applying algorithmic debugging to the paradigm of attribute grammars. The technique of algorithmic debugging uses the data flow of a program to debug it rather than stepping through its source code thereby making it suitable for declarative platforms like attribute grammars. In a debugging session, dependencies between attributes are obtained and used to construct an execution tree which is then traversed by the debugger based on interactions with the user. The debugger asks the user questions about the validity of a node in the execution tree and about the search space to be explored. Based on the user's response to the questions the debugger identifies the incorrect equation in a production definition. Further, we also propose a means to improve the debugging process by using a guided heuristic based mechanism which helps in reducing the number of questions to the user regarding the search space to be explored next.
While Computational Logic plays an important role in several areas of Computer Science (CS), most educational software developed for teaching logic is not suitable to be used directly in large portions of the CS educa...
详细信息
While Computational Logic plays an important role in several areas of Computer Science (CS), most educational software developed for teaching logic is not suitable to be used directly in large portions of the CS education domain where the application of logical notions is usually required. In this paper we describe an innovative methodology based on a logic teaching tool on semantic tableaux that has been developed to help students to use logic as a formal proof technique in other advanced topics of CS, such as the verification of algorithms, the algorithmic debugging of programs, and the derivation of algorithms from logical specifications, which are foundations of good development of software. We present the results of the evaluation of this tool by means of several educational experiences during the academic year 2009/2010. From these results we conclude that the use of the tool in current CS teaching can help our students to understand more advanced CS concepts and clarify the formal process involved in the design and analysis of correct and efficient imperative programs.
algorithmic debugging is a semi-automatic debugging technique that allows the programmer to precisely identify the location of bugs without the need to inspect the source code. The technique has been successfully adap...
详细信息
ISBN:
(纸本)9783642247682
algorithmic debugging is a semi-automatic debugging technique that allows the programmer to precisely identify the location of bugs without the need to inspect the source code. The technique has been successfully adapted to all paradigms and mature implementations have been released for languages such as Haskell, Prolog or Java. During three decades, the algorithm introduced by Shapiro and later improved by Hirunkitti has been thought optimal. In this paper we first show that this algorithm is not optimal, and moreover, in some situations it is unable to find all possible solutions, thus it is incomplete. Then, we present a new version of the algorithm that is proven optimal, and we introduce some equations that allow the algorithm to identify all optimal solutions.
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 comput...
详细信息
ISBN:
(纸本)9781450342612
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.
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 comput...
详细信息
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.
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 ...
详细信息
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.
This paper proposes an algorithm for checking incorrectness of a rule in equivalent transformation programs. Incorrect rules in programs can be detected without having to execute the program by applying the proposed a...
详细信息
This paper proposes an algorithm for checking incorrectness of a rule in equivalent transformation programs. Incorrect rules in programs can be detected without having to execute the program by applying the proposed algorithm to each rule one by one. Incorrectness of a rule can be shown by this algorithm without having to consider interrelations with other rules. Programmers can know if a rule needs to be corrected prior to trying to solve large-scale problems. This leads to a remarkable cost reduction in the construction of correct programs.
Up to now, it has been a difficult task to locate faults in programs when failures have occurred in test runs. In doing so, a programmer first makes a guess about the possible cause of failure, and then verifies his g...
详细信息
暂无评论