In this paper we study the constrained equivalence of programs with effects. In particular, we present a formal system for deriving such equivalences. The formal system we present defines a single-conclusion consequen...
详细信息
In this paper we study the constrained equivalence of programs with effects. In particular, we present a formal system for deriving such equivalences. The formal system we present defines a single-conclusion consequence relation between finite sets of constraints and assertions. Although the formal system is computationally adequate, even for expressions containing recursively defined functions, it is inadequate for proving properties of recursively defined functions. We show how to enrich the formal system by addition of induction principles. To illustrate the use of the formal system, we give three nontrivial examples of constrained equivalence assertions of well-known list-processing programs. We also establish several metatheoretic properties of constrained equivalence and the formal system, including soundness, completeness, and a comparison of the equivalence relations on various fragments.
Lower, upper, sandwich, mixed. and convex power domains are isomorphic to domains of second-order predicates mapping predicates on the ground domain to logical values in a semiring. The various power domains differ in...
详细信息
Lower, upper, sandwich, mixed. and convex power domains are isomorphic to domains of second-order predicates mapping predicates on the ground domain to logical values in a semiring. The various power domains differ in the nature of the underlying semiring logic and in logical constraints on the second-order predicates.
This paper demonstrates completeness of a termination-rule for iterative programs with strongly fair nondeterminism, even when there are countably infinite options for the nondeterminism. This means that whenever a pr...
详细信息
This paper demonstrates completeness of a termination-rule for iterative programs with strongly fair nondeterminism, even when there are countably infinite options for the nondeterminism. This means that whenever a program is guaranteed to terminate under the assumption of strong fairness, then this termination can be proved via the strongly fair termination rule. A variant of the rule is also shown to be complete for extremely fair nondeterminism, as introduced by Pnueli (1983) and developed by Francez (1986).
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.
Trace semantics is extended to allow conditional commutativity among operations. Conditional commutativity is obtained by identifying the context (the set of global states) in which operations are commutative using sp...
详细信息
Trace semantics is extended to allow conditional commutativity among operations. Conditional commutativity is obtained by identifying the context (the set of global states) in which operations are commutative using special predicates. These predicates allow collapsing execution histories. into equivalence classes of conditional traces. Using this approach, it is possible that the execution of two operations will be dependent in one context and independent in another. The predicates allow defining a family of possible semantic definitions for each language, where each is an extension of previous standard definitions. Examples are shown when such a semantics is desired. As an example of an application, a proof method for total correctness is introduced.
An algebraic programming system (APS) integrates four main paradigms of computations: procedural, functional, algebraic (rewriting rules) and logical. All of them may be used in different combinations at different lev...
详细信息
An algebraic programming system (APS) integrates four main paradigms of computations: procedural, functional, algebraic (rewriting rules) and logical. All of them may be used in different combinations at different levels of implementation. Formal models used in the developing computational techniques for APS are presented and discussed. These include data structures, algebraic modules, rewriting and computing, canonical forms, tools for building strategies and data types.
The growth of manufacturing control software from simple NC and PLC-based systems to concurrent networked systems incorporating PCs, PLCs, CNCs, and enterprise databases has created new challenges to the design, imple...
详细信息
The growth of manufacturing control software from simple NC and PLC-based systems to concurrent networked systems incorporating PCs, PLCs, CNCs, and enterprise databases has created new challenges to the design, implementation, and maintenance of safe and dependable manufacturing systems. Key milestones in this evolution, and the prospects for the use of formal verification methods in achieving enhanced dependability of future manufacturing software, are examined in this paper and presentation. (c) 2006 Elsevier Ltd. All rights reserved.
A system of hierarchical, fully recursive types in a truly imperative language allows program fragments written for small types to be reused for all larger types. To exploit this property to enable type-safe hierarchi...
详细信息
A system of hierarchical, fully recursive types in a truly imperative language allows program fragments written for small types to be reused for all larger types. To exploit this property to enable type-safe hierarchical procedures, it is necessary to impose a static requirement on procedure calls. We introduce an example language and prove the existence of a sound requirement which preserves static correctness while allowing hierarchical procedures. This requirement is further shown to be optimal, in the sense that it imposes as few restrictions as possible. This establishes the theoretical basis for a general type hierarchy with static type checking, which enables first-order polymorphism combined with multiple inheritance and specialization in a language with assignments. We extend the results to include opaque types. An opaque version of a type is different from the original but has the same values and the same order relations to other types. The opaque types allow a more flexible polymorphism and provide the usual pragmatic advantages of distinguishing between intended and unintended type equalities. Opaque types can be viewed as a compromise between synonym types and abstract types.
We study a typing scheme derived from a semantic situation where a single category possesses several closed structures, corresponding to different varieties of function type. In this scheme typing contexts are trees b...
详细信息
We study a typing scheme derived from a semantic situation where a single category possesses several closed structures, corresponding to different varieties of function type. In this scheme typing contexts are trees built from two (or more) binary combining operations, or in short, bunches. Bunched typing and its logical counterpart, bunched implications, have arisen in joint work of the author and David Pym. The present paper gives a basic account of the type system, and then focusses on concrete models that illustrate how it may be understood in terms of resource access and sharing. The most basic system has two context-combining operations, and the structural rules of Weakening and Contraction are allowed for one but not the other. This system includes a multiplicative, or substructural, function type --> alongside the usual (additive) function type -->;it is dubbed the alphalambda-calculus after its binders, alpha for the additive binder and lambda for the multiplicative, or lambdainear, binder. We show that the features of this system are, in a sense, complementary to calculi based on linear logic;it is incompatible with an interpretation where a multiplicative function uses its argument once, but perfectly compatible with a reading based on sharing of resources. This sharing interpretation is derived from syntactic control of interference, a type-theoretic method of controlling sharing of storage, and we show how bunch-based management of Contraction can be used to provide a more flexible type system for interference control.
暂无评论