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.
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.
We present a logical and semantic framework for diagnosing wrong computed answers in CFLP(D), a newly proposed generic scheme for lazy Constraint Functional Logic Programming which can be instantiated by any constrain...
详细信息
We present a logical and semantic framework for diagnosing wrong computed answers in CFLP(D), a newly proposed generic scheme for lazy Constraint Functional Logic Programming which can be instantiated by any constraint domain D given as parameter, and supports a powerful combination of functional and constraint logic programming over D. Our approach extends and combines declarative debugging techniques previously developed for less expressive programming paradigms, namely the CLP(D) scheme and lazy functional logic languages. debugging starts with the observation of a wrong computed answer which the user regards as incorrect w.r.t. an intended model that provides a declarative description of the program's semantics. debugging proceeds by exploring an abridged proof tree that provides a purely declarative view of the computation, so that the user does not need to understand the complex underlying operational mechanisms. debugging ends with the detection of a function rule in the program that is incorrect w.r.t. the intended model. We prove the logical correctness of the debugging method for any sound CFLP(D)system whose computed answers are logical consequences of the program, and we describe a practical tool which implements the debugging method for the domain of arithmetic constraints over the real numbers.
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.
debugging has always been a costly part of software development and software maintenance, which makes it important to find methods and tools to support this activity. algorithmic program debugging is an interactive pr...
详细信息
debugging has always been a costly part of software development and software maintenance, which makes it important to find methods and tools to support this activity. algorithmic program debugging is an interactive process where the debugging system acquires knowledge about the intended behavior of the debugged program and uses this knowledge to localize errors semi-automatically. This knowledge is a set of partial specifications collected by the debugging system through a number of questions to the user. Although in theory the specifications about the intended program behavior can be stored in advance, this is still an error-prone task in practice. Thus, knowledge collection during debugging is a necessity. A major drawback of this method is the large number of user interactions during bug localization. An important improvement would be to supply the debugging system with some information which can reduce this number. This is achieved by combining program slicing with algorithmic debugging. Program slicing improves the search method by eliminating many irrelevant questions to the user during bug localization. (C) 1998 Elsevier Science B.V. All rights reserved.
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...
详细信息
A debugging method for attribute grammars based on algorithmic debugging is proposed. This technique was originally proposed for debugging logic programming languages. It presents to the programmer the local computa...
详细信息
A debugging method for attribute grammars based on algorithmic debugging is proposed. This technique was originally proposed for debugging logic programming languages. It presents to the programmer the local computational results of predicates during program execution. Through examination of whether these results agree with the programmer's intention, it systematically narrows the search space in which bugs can exist. It is formally shown how algorithmic debugging can be applied to attribute grammars by introducing an abstract function, and this technique is expanded in order to realize more efficient debugging by utilizing characteristic features of attribute grammar. It is also demonstrated that this technique is applicable to almost all classes of attribute grammars, making correspondence with their attribute evaluators.
This paper proposes a new environment for high-level VLSI design specification validation using ''algorithmic debugging'' and evaluates its benefits on three significant examples (a protocol processor,...
详细信息
This paper proposes a new environment for high-level VLSI design specification validation using ''algorithmic debugging'' and evaluates its benefits on three significant examples (a protocol processor, an 8-bit CPU, and a Prolog processor). A design is specified at a high-level using the structured analysis (SA) method, which is useful for analyzing and understanding the functionality to be realized. The specification written in SA is transformed into a logic programming language and is simulated in it. The errors (which terminate with an incorrect output in the simulation) included in the three large examples are efficiently located by answering junt a few queries from the algorithmic debugger. The number of interactions between the designer and the debugger is reduced by a factor of ten to a hundred compared to conventional simulation based validation methodologies. The correct SA specification can be automatically translated into a Register Transfer Level (RTL) specification suitable for logic synthesis. In this environment, a designer is freed from the tedious task of debugging a RTL specification, and can concentrate on the design itself. This environment promises to be an important step towards efficient high-level VLSI design specification validation.
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.
暂无评论