Functional semantics of programs with exceptions

Linguistic mechanisms for exception handling facilitate the production of reliable software and play an important role in fault tolerant computing. This paper describes the functional semantics of a Pascal-like language which supports exception handling and data abstraction. A program with exceptions is considered as having a standard semantics, as well as an exceptional semantics for each exception that may be signaled during its execution. Standard functional semantics methods provide rules to obtain the function representing the standard semantics. In this paper, we provide rules to determine the functions representing the exceptional semantics. We also describe a method for specifying and verifying the correctness of implementation of data types with exceptions.     

Provably correct control flow graphs from Java bytecode programs with exceptions

We present an algorithm for extracting control flow graphs from Java bytecode that captures normal as well as exceptional control flow. We prove its correctness, in the sense that the behaviour of the extracted control flow graph is a sound over-approximation of the behaviour of the original program. This makes control flow graphs suitable for performing various static analyses, such as model checking of temporal safety properties. Analysing exceptional control flow for Java bytecode is difficult because of the stack-based nature of the language. We therefore develop the extraction in two stages. In the first, we abstract away from the complications arising from exceptional flows, and relativize the extraction on an oracle that is able to look into the stack and predict the exceptions that can be raised at each instruction. This idealized algorithm provides a specification for concrete extraction algorithms, which have to provide a suitable implementation for the oracle. We prove correctness of the idealized algorithm by means of behavioural simulation. In the second stage, we develop a concrete extraction algorithm that consists of two phases. In the first phase, the program is transformed into a BIR program, a stack-less intermediate representation of Java bytecode, from which the control flow graph is extracted in the second phase. We use this intermediate format because it provides the information needed to implement the oracle, and since it gives rise to more compact graphs. We show that the behaviour of the control flow graph extracted via the intermediate representation is a sound over-approximation of the behaviour of the graph extracted by the direct, idealized algorithm, and thus of the original program. The concrete extraction algorithm is implemented as the ConFlEx tool. A number of test cases are performed to evaluate the efficiency of the algorithm.     

Logic programs as compact denotations

This paper shows how logic programs can be used to implement the transition functions of denotational abstract interpretation. The logic variables express regularity in the abstract behaviour of commands. The technique has been applied to sign, class and escape analysis for object-oriented programs. We show that the time and space costs using logic programs for these analyses are smaller than those using a ground relational representation. Moreover, we show that, in the case of sign analysis, our technique requires less memory and has an efficiency comparable to that of an implementation based on binary decision diagrams.     

Inheritance systems with exceptions

In this paper, we are interested in the representation and management of multiple inheritance systems with exceptions in both semantic networks and object-oriented languages. Exception management raises different problems, particularly in the presence of contradictions. Three types of contradictions, which constitute the problematics of exception management, may be identified. The different methods used to solve these contradictions are presented; two approaches in particular are underscored: a logic approach and an algebraic approach.     

Multiple inheritance systems with exceptions

This paper discusses some problems that arise in knowledge-based intelligent systems using property inheritance as the principal inference mechanism. A few methods that deal with those problems are presented here. They are divided into three groups: those that are based on different forms of non-monotonic logics, algebraic structures, and connectionist networks. Implementational issues concerning inheritance systems are considered with the special emphasis put on parallel methods of computation.     

Exceptional C or C with exceptions

C does not have exception handling facilities. Errors are handled by examining the value returned by each function and signals (conditions reported to the program) are handled by using library functions. These approaches lead to ad hoc error-handling techniques and can make programs hard to understand. Exceptional C, a superset of C, provides exception handling facilities. Exceptional C integrates the two techniques used by C programmers (i.e., status values and signals) to handle errors into one unified exception handling mechanism. In this paper, I review exception handling models, specify the criteria used for designing the exception handling facilities in Exceptional C, and then describe these facilities. I also illustrate the use of the exception handling facilities with examples.     

Detecting races in Relay Ladder Logic programs

Relay Ladder Logic (RLL) [5] is a programming language widely used for complex embedded control applications such as manufacturing and amusement park rides. The cost of bugs in RLL programs is extremely high, often measured in millions of dollars (for shutting down a factory) or human safety (for rides). In this paper, we describe our experience in applying constraint-based program analysis techniques to analyze production RLL programs. Our approach is an interesting combination of probabilistic testing and program analysis, and we show that our system is able to detect bugs with high probability, up to the approximations made by the conservative program analysis. We demonstrate that our analysis is useful in detecting some flaws in production RLL programs that are difficult to find by other techniques.     

Logic programs with abstract constraint atoms: The role of computations

We provide a new perspective on the semantics of logic programs with arbitrary abstract constraints. To this end, we introduce several notions of computation. We use the results of computations to specify answer sets of programs with constraints. We present the rationale behind the classes of computations we consider, and discuss the relationships among them. We also discuss the relationships among the corresponding concepts of answer sets. One of those concepts has several compelling characterizations and properties, and we propose it as the correct generalization of the answer-set semantics to the case of programs with arbitrary constraints. We show that several other notions of an answer set proposed in the literature for programs with constraints can be obtained within our framework as the results of appropriately selected classes of computations.     

Logic programs with stable model semantics as a constraint programming paradigm

Logic programming with the stable model semantics is put forward as a novel constraint programming paradigm. This paradigm is interesting because it bring advantages of logic programming based knowledge representation techniques to constraint programming and because implementation methods for the stable model semantics for ground (variable‐free) programs have advanced significantly in recent years. For a program with variables these methods need a grounding procedure for generating a variable‐free program. As a practical approach to handling the grounding problem a subclass of logic programs, domain restricted programs, is proposed. This subclass enables efficient grounding procedures and serves as a basis for integrating built‐in predicates and functions often needed in applications. It is shown that the novel paradigm embeds classical logical satisfiability and standard (finite domain) constraint satisfaction problems but seems to provide a more expressive framework from a knowledge representation point of view. The first steps towards a programming methodology for the new paradigm are taken by presenting solutions to standard constraint satisfaction problems, combinatorial graph problems and planning problems. An efficient implementation of the paradigm based on domain restricted programs has been developed. This is an extension of a previous implementation of the stable model semantics, the Smodels system, and is publicly available. It contains, e.g., built‐in integer arithmetic integrated to stable model computation. The implementation is described briefly and some test results illustrating the current level of performance are reported. This revised version was published online in June 2006 with corrections to the Cover Date.     

Exploiting exceptions

A novel compiler optimization for loops is presented. The optimization uses exceptions to eliminate redundant tests that are performed when code is interpretively executed, as is the case with Java bytecode executed on the Java Virtual Machine. An analysis technique based on abstract interpretation is used to discover when the optimization is applicable. Copyright © 2001 John Wiley & Sons, Ltd.     

Semantics of looping programs in Propositional Dynamic Logic

Standard and nonstandard models of Propositional Dynamic Logic differ in their interpretation of loops. In Standard models, a loop is interpreted as the Kleene closure of the interpretation of its loop body; in nonstandard (Loop Invariant) models, a loop is interpreted as a program which preserves invariant assertions over the loop body.In this paper we show that both interpretations are adequate to represent loops in PDL. We demonstrate this in two ways: First we note that Standard and Loop Invariant models are distinct but not distinguishable within PDL. Second, we show that the class of Loop Invariant models is complete with respect to the Segerberg axiomatization of PDL. Since completeness of the class of Loop Invariant models implies completeness of the class of Standard models, Standard models are also complete with respect to this axiomatization.The research reported here was supported in part by NSF Grants MCS77-02474 and MCS80-05387. Most of the results in this paper were announced in A Completeness Technique forD-axiomatizable Semantics presented at the 11th Annual ACM Symposium on the Theory of Computing in May, 1979.     

Safe locking for multi-threaded Java with exceptions

There are many mechanisms for concurrency control in high-level programming languages. In Java, the original mechanism for concurrency control, based on synchronized blocks, is lexically scoped. For more flexible control, Java 5 introduced non-lexical lock primitives on re-entrant locks.These operators may lead to run-time errors and unwanted behavior; e.g., taking a lock without releasing it, which could lead to a deadlock, or trying to release a lock without owning it. This paper develops a static type and effect system to prevent the mentioned lock errors for a formal, object-oriented calculus which supports non-lexical lock handling and exceptions.Based on an operational semantics, we prove soundness of the effect type analysis. Challenges in the design of the effect type system are dynamic creation of threads, objects, and especially of locks, aliasing of lock references, passing of lock references between threads, and reentrant locks as found in Java. Furthermore, the exception handling mechanism complicates the control-flow and thus the analysis.     

FRIwE: fuzzy rule identification with exceptions

In this paper, the FRIwE method is proposed to identify fuzzy models from examples. Such a method has been developed trying to achieve a double goal:accuracy and interpretability. In order to do that, maximal structure fuzzy rules are firstly obtained based on a method proposed by Castro et al. In a second stage, the conflicts generated by the maximal rules are solved, thus increasing the model accuracy. The resolution of conflicts are carried out by including exceptions in the rules. This strategy has been identified by psychologists with the learning mechanism employed by the human being, thus improving the model interpretability. Besides, in order to improve the interpretability even more, several methods are presented based on reducing and merging rules and exceptions in the model. The exhaustive use of the training examples gives the method a special suitability for problems with small training sets or high dimensionality. Finally, the method is applied to an example in order to analyze the achievement of the goals.     

Towards a Declarative Semantics of Inheritance with Exceptions

This paper presents a declarative semantics of compositional inheritance in an object-oriented logic programming framework with explicit exceptions,based on the iterated least fixpoint semantics to normal logic programs.Taking logic objects with exceptions as a kind of non-monotonic theory,the nonmonotonicity of inheritance is achieved,which is of importance for modeling incoplete knowledge and requirement specifications in both artificial intelligence and software engineering.     

A Dynamic Logic for deductive verification of multi-threaded programs

We present MODL, a Dynamic Logic and a deductive verification calculus for a core Java-like language that includes multi-threading. The calculus is based on symbolic execution. Even though we currently do not handle non-atomic loops, employing the technique of symmetry reduction allows us to verify systems without limits on state space or thread number. We have instantiated our logic for (restricted) multi-threaded Java programs and implemented the verification calculus within the KeY system. We demonstrate our approach by verifying a central method of the StringBuffer class from the Java standard library in the presence of unbounded concurrency.     

强弱例外下的交互时态逻辑

非单调推理是众多人工智能应用系统都可能面对的问题,多Agent系统也不例外。在前期关于Agent BDI逻辑、多Agent合作逻辑、多Agent合作问题求解过程建模等研究工作的基础上,借鉴Baral等人开发非单调线性时态逻辑N-LTL的技术,利用强弱例外对多Agent合作逻辑的开创性工作交互时态逻辑(ATL)进行拓展,建立非单调交互时态逻辑NATL,给出其语法和语义。是对ATL进行非单调拓展的首次有益尝试。可以考虑以之为理论工具对多Agent思维状态及其动态修正机制进行妥善刻画。     

Introducing possibilistic logic in ILP for dealing with exceptions

In this paper we propose a new formalization of the inductive logic programming (ILP) problem for a better handling of exceptions. It is now encoded in first-order possibilistic logic. This allows us to handle exceptions by means of prioritized rules, thus taking lessons from non-monotonic reasoning. Indeed, in classical first-order logic, the exceptions of the rules that constitute a hypothesis accumulate and classifying an example in two different classes, even if one is the right one, is not correct. The possibilistic formalization provides a sound encoding of non-monotonic reasoning that copes with rules with exceptions and prevents an example to be classified in more than one class. The benefits of our approach with respect to the use of first-order decision lists are pointed out. The possibilistic logic view of ILP problem leads to an optimization problem at the algorithmic level. An algorithm based on simulated annealing that in one turn computes the set of rules together with their priority levels is proposed. The reported experiments show that the algorithm is competitive to standard ILP approaches on benchmark examples.     

A pipelined interface for high floating-point performance with precise exceptions

Two options are presented that were considered for a pipelined interface between a central processing unit (CPU) and a floating-point coprocessor (FPU), along with the CPU recovery mechanisms that provide precise floating-point exceptions for each option. The first option supports parallel execution of both floating-point and integer instructions, while the second option pipelines only the execution of floating-point instructions. The use of the second option in National Semiconductor's 32532/32580 processor cluster because it offers high performance with significantly lower complexity. The 32532 microprocessor features a pipelined slave protocol that hides the CPU-FPU communication overhead for most floating-point instructions by pipelining their execution. A simple recovery mechanism implemented within the CPU maintains the precision of floating-point exceptions. As a result, the 32532 microprocessor supports very high floating point performance without sacrificing software compatibility with previous Series 32000 CPU-FPU clusters.<>