Summary Debugging is crucial for producing reliable software. One of the effective bug localization techniques is spectral‐based fault localization. It tries to locate a buggy statement by applying an evaluation metric to program spectra and ranking program components on the basis of the score it computes. Here, we propose a restricted class of “hyperbolic” metrics, with a small number of numeric parameters. This class of functions is based on past theoretical and empirical results. We show that optimization methods such as genetic programming and simulated annealing can reliably discover effective metrics over a wide range of data sets of program spectra. We evaluate the performance for both real programs and model programs with single bugs, multiple bugs, “deterministic” bugs, and nondeterministic bugs and find that the proposed class of metrics performs as well as or better than the previous best‐performing metrics over a broad range of data.

Summary Debugging is crucial for producing reliable software. One of the effective bug localization techniques is spectral‐based fault localization (SBFL). It helps to locate a buggy statement by applying an evaluation metric to program spectra and ranking program components on the basis of the score it computes. SBFL is an example of a dynamic analysis – an analysis of computer program that is performed by executing it with sufficient number of test cases. Static analysis, on the other hand, is performed in a non‐runtime environment. We introduce a weighting technique by combining these two kinds of program analysis. Static analysis is performed to categorize program statements into different classes and giving them weights based on the likelihood of being buggy statement. Statements are finally ranked on the basis of the weights computed by statements' categorization (static analysis) and scores computed by SBFL metrics (dynamic analysis). We evaluate the performance of our technique on Siemens test suite and Flex (having seeded bugs seeded by expert developers), Sed (having mixture of real and seeded bugs), and Space (having real bugs). In our evaluation, proposed weighting technique improves the performance of a wide variety of fault localization metrics up to 20% on single bug datasets and up to 42% on multi‐bug datasets. Copyright © 2017 John Wiley & Sons, Ltd.

Summary Adtpp is an open‐source tool that adds support for algebraic data types (ADTs) to the C programming language. ADTs allow more precise description of program types and more robust handling of data structures than are directly supported by C. ADT definitions and other declarations are put in a file that is preprocessed by adtpp to produce a C header (‘.h’) file that can be included in C source files. The generated header file contains C type definitions, macros, and inline functions that support type‐safe construction, deconstruction, and pattern matching of ADT values while avoiding unsafe operations such as casts, and avoiding the risk of errors such as dereferencing NULL pointers and accessing inappropriate fields of unions. Values are represented efficiently, using techniques from the implementation of declarative languages. For many simple data types, the memory representation is identical to a direct implementation in C, with no loss of efficiency. For more complex types, the adtpp representation is more efficient than common C representations while preserving type safety and convenience. As an example, we present a new variation of 234‐trees that is very compact. Adtpp also supports parametric polymorphism such as defining a type ‘list of t’, where t can be any ADT, and generic functions such as length. However, polymorphic code is somewhat more verbose than for typical declarative languages, due to our reliance on the limited type checking available in C. Copyright © 2016 John Wiley & Sons, Ltd.

Allowing cycles in a logic circuit can be advantageous, for example, by reducing the number of gates required to implement a given Boolean function, or a set of functions. However, a cyclic circuit may easily be ill behaved. For instance, it may have some output wire oscillation instead of reaching a steady state. Propositional three-valued logic has long been used in tests for good behavior of cyclic circuits; a symbolic evaluation method known as ternary analysis provides one criterion for good behavior under certain assumptions about wire and gate delay. We revisit ternary analysis and argue for the use of four truth values. The fourth truth value allows for the distinction of undefined and underspecified behavior. Ability to under specify behavior is useful, because, in a quest for smaller circuits, an implementor can capitalize on degrees of freedom offered in the specification. Moreover, a fourth truth value is attractive because, rather than complicating (ternary) circuit analysis, it introduces a pleasant symmetry, in the form of contra-duality, as well as providing a convenient framework for manipulating specifications. We use this symmetry to provide fixed point results that clarify how two-, three-, and four-valued analyses are related, and to explain some observations about ternary analysis.

Abstract We show how logic programs with “delays” can be transformed to programs without delays in a way that preserves information concerning floundering (also known as deadlock). This allows a declarative (model-theoretic), bottom-up or goal-independent approach to be used for analysis and debugging of properties related to floundering. We rely on some previously introduced restrictions on delay primitives and a key observation which allows properties such as groundness to be analysed by approximating the (ground) success set.

Abstract The semantics of logic programs was originally described in terms of two-valued logic. Soon, however, it was realised that three-valued logic had some natural advantages, as it provides distinct values not only for truth and falsehood but also for “undefined”. The three-valued semantics proposed by Fitting (Fitting, M. 1985. A Kripke–Kleene semantics for logic programs.Journal of Logic Programming 2, 4, 295–312) and Kunen (Kunen, K. 1987. Negation in logic programming.Journal of Logic Programming 4, 4, 289–308) are closely related to what is computed by a logic program, the third truth value being associated with non-termination. A different three-valued semantics, proposed by Naish, shared much with those of Fitting and Kunen but incorporated allowances for programmer intent, the third truth value being associated with underspecification. Naish used an (apparently) novel “arrow” operator to relate the intended meaning of left and right sides of predicate definitions. In this paper we suggest that the additional truth values of Fitting/Kunen and Naish are best viewed as duals. We use Belnap's four-valued logic (Belnap, N. D. 1977. A useful four-valued logic. InModern Uses of Multiple-Valued Logic, J. M. Dunn and G. Epstein, Eds. D. Reidel, Dordrecht, Netherlands, 8–37), also used elsewhere by Fitting, to unify the two three-valued approaches. The truth values are arranged in a bilattice, which supports the classical ordering on truth values as well as the “information ordering”. We note that the “arrow” operator of Naish (and our four-valued extension) is essentially the information ordering, whereas the classical arrow denotes the truth ordering. This allows us to shed new light on many aspects of logic programming, including program analysis, type and mode systems, declarative debugging and the relationships between specifications and programs, and successive execution states of a program.

This article presents an improved approach to assist diagnosis of failures in software (fault localisation) by ranking program statements or blocks in accordance with to how likely they are to be buggy. We present a very simple single-bug program to model the problem. By examining different possible execution paths through this model program over a number of test cases, the effectiveness of different proposed spectral ranking methods can be evaluated in idealised conditions. The results are remarkably consistent to those arrived at empirically using the Siemens test suite and Space benchmarks. The model also helps identify groups of metrics that are equivalent for ranking. Due to the simplicity of the model, an optimal ranking method can be devised. This new method out-performs previously proposed methods for the model program, the Siemens test suite and Space. It also helps provide insight into other ranking methods.

This paper investigates the relationship between the use of predicate-based and statement-based program spectra for bug localization. Branch and path spectra are also considered. Although statement and predicate spectra can be based on the same raw data, the way the data is aggregated results in different information being lost. We propose a simple and cheap modification to the statement-based approach which retains strictly more information. This allows us to compare statement and predicate ''metrics'' (functions used to rank the statements, predicates or paths). We show that improved bug localization performance is possible using single-bug models and benchmarks.

This paper presents an approach of bug localization using a frequency weighting function. In an existing approach, only binary information of execution count from test executions is used. Information of each program statement being executed and not executed by a particular test is used; indicated by 1 and 0 respectively. In our proposed approach, frequency execution count of each program statement executed by a respective test is used. We evaluate several well-known spectra metrics using our proposed approach and the existing approach (using binary information of execution count) on two test suites; Siemens Test Suite and Unix datasets. We show that the bug localization performance is improved by using our proposed approach. We conduct statistical test and show that the improved bug localization performance using our approach (using frequency execution count) is statistically significant than using the existing approach (using binary information of execution count).

Software faults can be diagnosed using program spectra. The program spectra considered here provide information about which statements are executed in each one of a set of test cases. This information is used to compute a value for each statement which indicates how likely it is to be buggy, and the statements are ranked according to these values. We present two improvements to this method. First, we associate varying weights with failed test cases --- test cases which execute fewer statements are given more weight and have more influence on the ranking. This generally improves diagnosis accuracy, with little additional cost. Second, the ranking is computed incrementally. After the top-ranked statement is identified, the weights are adjusted in order to compute the rest of the ranking. This further improves accuracy. The cost is more significant, but not prohibitive.

There are many advantages to voting schemes in which voters rank all candidates in order, rather than just choosing their favorite. However, these schemes inherently suffer from a coercion problem when there are many candidates, because a coercer can demand a certain permutation from a voter and then check whether that permutation appears during tallying. Recently developed cryptographic voting protocols allow anyone to audit an election (universal verifiability), but existing systems are either not applicable to ranked voting at all, or reveal enough information about the ballots to make voter coercion possible. We solve this problem for the popular single transferable vote (STV) ranked voting system, by constructing an algorithm for the verifiable tallying of encrypted votes. Our construction improves upon existing work because it extends to multiple-seat STV and reveals less information than other schemes. The protocol is based on verifiable shuffling of homomorphic encryptions, a well-studied primitive in the voting arena. Our protocol is efficient enough to be practical, even for a large election.

This paper describes a simpler way for programmers to reason about the correctness of their code. The study of semantics of logic programs has shown strong links between the model theoretic semantics (truth and falsity of atoms in the programmer's interpretation of a program), procedural semantics (for example, SLD resolution) and fixpoint semantics (which is useful for program analysis and alternative execution mechanisms). Most of this work assumes that intended interpretations are two-valued: a ground atom is true (and should succeed according to the procedural semantics) or false (and should not succeed). In reality, intended interpretations are less precise. Programmers consider that some atoms “should not occur” or are “ill-typed” or “inadmissible”. Programmers don't know and don't care whether such atoms succeed. In this paper we propose a three-valued semantics for (essentially) pure Prolog programs with (ground) negation as failure which reflects this. The semantics of Fitting is similar but only associates the third truth value with non-termination. We provide tools to reason about correctness of programs without the need for unnatural precision or undue restrictions on programming style. As well as theoretical results, we provide a programmer-oriented synopsis. This work has come out of work on declarative debugging, where it has been recognised that inadmissible calls are important.

Non-strict purely functional languages pose many challenges to the designers of debugging tools. Declarative debugging has long been considered a suitable candidate for the task due to its abstraction over the evaluation order of the program, although the provision of practical implementations has been lagging. In this paper we discuss the solutions used in our declarative debugger for Haskell to tackle the problems of printing values, memory usage and I/O. The debugger is based on program transformation, although much leverage is gained by interfacing with the runtime environment of the language implementation through a foreign function interface.

We have developed a framework for pedagogically-oriented animations, designed to help students learn new algorithms. Recursive sorting and searching algorithms pose a particular challenge, as it can be difficult to find visual representations that help students develop a mental model of how the recursion proceeds. Relatively complex representations, such as thumbnail sketches or explicitly showing the function stack along with the data structure are appropriate for some algorithms, while simpler representations suffice for others. We have found it useful to classify recursive algorithms according to the way they navigate through a data structure and manipulate data items within it, sometimes with further subdivision according to the kind of recursion. Within each category there are common strategies for visual representation. While there may be no single, general way to represent recursive algorithms, classification is a useful guide to picking an appropriate strategy when animating recursive algorithms.

Computational logic systems can offer an attractive environment for developing Internet applications. They share many of the important characteristics of popular network programming tools, including dynamic memory management, well-behaved structure and pointer manipulation, robustness, and compilation to architecture-independent bytecode. However, in addition, computational logic systems offer some unique features such as very powerful symbolic processing capabilities, constraint solving, dynamic databases, search facilities, grammars, sophisticated meta-programming, and well understood semantics. Such features can often make it very easy to code simple applications. This special issue concerned with applications is the third of its kind in a journal sponsored by the Association for Logic Programming. The first appeared in 1990, and showed the potential for logic programming to be extended. The second issue highlighted some papers from the Practical Applications of Prolog conference that had been held. This third time, the applications are concerned with the Internet and reflect the profound impact that the Internet has had on the computing landscape.

Computer animation is an excellent medium for capturing the dynamic nature of data structure manipulations, and can be used to advantage in the teaching of algorithms and data structures. A major educational issue is the necessity of providing a means for the student to manage the complexity of the material. We have addressed this issue in a multimedia teaching tool called "Algorithms in Action" by allowing students to view an algorithm at varying levels of detail. Starting with a high level pseudocode description of the algorithm, with accompanying high level animation and textual explanation, students can expand sections of the pseudocode to expose more detail. Animation and explanation are controlled in a coordinated fashion, becoming correspondingly more detailed as the pseudocode is expanded. The tool also supports dofferem , pdes. corresponding to different stages in the learning process. Student feedback suggests that the availability of multiple levels detail and the facility for the user to control the level of detail being viewed is an effective way to manage content complexity.