Some of the basic results in the theory of logic programming, e.g. the mgu lemma, lifting lemma and completeness theorem, have been incorrectly stated in standard texts. We explain how these errors arise and how they ...
详细信息
Some of the basic results in the theory of logic programming, e.g. the mgu lemma, lifting lemma and completeness theorem, have been incorrectly stated in standard texts. We explain how these errors arise and how they may be avoided by suitable ''standardising apart'' of the program clauses used. We also discuss the significance of standardising apart for other purposes, e.g. soundness, obtaining most general answer.
Program analyses are often presented as one of two brands: forwards or backwards. In this paper we explore the significance of the direction of analysis, and show how arbitrary abstract interpretations may be reversed.
Program analyses are often presented as one of two brands: forwards or backwards. In this paper we explore the significance of the direction of analysis, and show how arbitrary abstract interpretations may be reversed.
The categorical semantics of (an abstract version of) the general term graph rewriting language DACTL is investigated. The operational semantics is reformulated in order to reveal its universal properties. The technic...
详细信息
The categorical semantics of (an abstract version of) the general term graph rewriting language DACTL is investigated. The operational semantics is reformulated in order to reveal its universal properties. The technical dissonance between the matchings of left-hand sides of rules to redexes, and the properties of rewrite rules themselves, is taken as the impetus for expressing the core of the model as a Grothendieck opfibration of a category of general rewrites over a base of general rewrite rules. Garbage collection is examined in this framework in order to reconcile the treatment with earlier approaches. It is shown that term rewriting has particularly good garbage-theoretic properties that do not generalise to all cases of graph rewriting and that this has been a stumbling block for aspects of some earlier models for graph rewriting.
It is shown that regular relations, which arise in a number of areas of programming theory, can be characterised in a variety of ways as pullbacks in Jet;and up to isomorphism, as bicartesian squares in Jet.
It is shown that regular relations, which arise in a number of areas of programming theory, can be characterised in a variety of ways as pullbacks in Jet;and up to isomorphism, as bicartesian squares in Jet.
Path dissolution is an inferencing mechanism that generalizes the method of analytic tableaux. We present several results demonstrating that tableau deductions can be substantially speeded up with applications of diss...
详细信息
Path dissolution is an inferencing mechanism that generalizes the method of analytic tableaux. We present several results demonstrating that tableau deductions can be substantially speeded up with applications of dissolution technology. We also consider the class of formulas on which the method of analytic tableaux was first shown to be intractable and prove that, with the application of the ordinary distributive law, standard tableau methods admit linear time proofs for this class.
Much of the earlier development of abstract interpretation, and its application to imperative programming languages, has concerned techniques for finding fixed points in large (often infinite) lattices. The standard a...
详细信息
Much of the earlier development of abstract interpretation, and its application to imperative programming languages, has concerned techniques for finding fixed points in large (often infinite) lattices. The standard approach in the abstract interpretation of functional languages has been to work with small, finite lattices and this supposedly circumvents the need for such techniques. However, practical experience has shown that, in the presence of higher-order functions, the lattices soon become too large (although still finite) for the fixed point finding problem to be tractable. This paper develops some approximation techniques which were first proposed by Hunt and shows how these techniques relate to the earlier use of widening and narrowing operations by the Cousots.
The implementation of syntax-driven static semantic analysis of languages presenting recursive forward references in their definition requires the handling of a syntax tree. When dealing with languages for which the s...
详细信息
The implementation of syntax-driven static semantic analysis of languages presenting recursive forward references in their definition requires the handling of a syntax tree. When dealing with languages for which the syntax tree approach is very heavy to implement, a source code reorganisation operation may solve the problem more conveniently. This applies to the ISO specification language LOTOS [1, 2], which is ta ken as the main concern in the paper. The implementation is described of a static semantic analyser for LOTOS based on the above approach, by means of a C program, and all the main issues are addressed. It is shown that the source code reorganisation operation applied to LOTOS specifications does not alter the semantics of the original source specification. Examples and measures of performance collected by testing the tool on some significant case studies in the literature are also given.
We investigate here the question of finding the minimal requirements for the registers used by n processes that solve the critical-section problem. For two processes, we show that there cannot be a solution to the cri...
详细信息
We investigate here the question of finding the minimal requirements for the registers used by n processes that solve the critical-section problem. For two processes, we show that there cannot be a solution to the critical-section problem if the two registers used are regular and of size 2 and 3. For n processes, this result generalizes to show the impossibility of a solution with regular registers if the total size of the registers is 3n - 1. This is the best result for n = 2 since there are solutions (presented here) in which regular registers of total size 6 are used. The impossibility proof depends on a careful analysis of infinite protocol automata, and therefore a detailed definition of such automata and their semantics is developed first.
This paper describes the transformation of lambda-terms from continuation-passing style (CPS) to direct style. This transformation is the left inverse of Plotkin's left-to-right call-by-value CPS encoding for the ...
详细信息
This paper describes the transformation of lambda-terms from continuation-passing style (CPS) to direct style. This transformation is the left inverse of Plotkin's left-to-right call-by-value CPS encoding for the pure lambda-calculus. Not all lambda-terms are CPS terms, and not all CPS terms encode a left-to-right call-by-value evaluation. These CPS terms are characterized here;they can be mapped back to direct style. In addition, the two transformations-to continuation-passing style and to direct style-are factored using a language where all intermediate values are named and their computation is sequentialized. The issue of proper tail-recursion is also addressed.
Program composition and compositional proof systems have proved themselves important for simplifying the design and the verification of programs. The paper presents a version of the jigsaw program composition operator...
详细信息
Program composition and compositional proof systems have proved themselves important for simplifying the design and the verification of programs. The paper presents a version of the jigsaw program composition operator previously defined in [Fix et al. (1991, 1992)]. Here, the jigsaw operator is defined as the unification of its components by their most general unifier. The jigsaw operator generalizes and unifies the traditional sequential and parallel program composition operators and the newly proposed union and superposition operators. We consider a family of frameworks each consisting of a programming language, a specification language and a compositional syntax-directed proof system. We present syntactic rules to augment any given framework in the family with the jigsaw operator. The augmented framework is syntax-directed and compositional. Moreover, it is sound and complete with respect to the given framework.
暂无评论