In developing object-oriented (OO) software, the first important thing is to identify objects and define the model of communicating relationships between objects. While designing objects the authors again have to anal...
详细信息
In developing object-oriented (OO) software, the first important thing is to identify objects and define the model of communicating relationships between objects. While designing objects the authors again have to analyse by what relations the subobjects are connected together. So it is of utmost importance to study the relationships between objects in OO system for finding out object analysing criteria. But up to now it still is a very confusing respect on the naming, definitions and the usage of relations among objects. This paper is for the purpose of discarding the confusion. To this end, a 3-dimensional relation model (3DRM) is suggested. In the 3DRM framework, a series of relations among objects are discussed, and a clear relation hierarchy is performed. Therefore the foundation is established for further study of the OO software development methodology (OOM).
Given a term-rewriting system R, a term t is ground-reducible by R if every ground instance tsigma of it is R-reducible. A pair (t, s) of terms is ground-co--reducible by R if every ground instance (tsigma, ssigma] of...
详细信息
Given a term-rewriting system R, a term t is ground-reducible by R if every ground instance tsigma of it is R-reducible. A pair (t, s) of terms is ground-co--reducible by R if every ground instance (tsigma, ssigma] of it for which tsigma and ssigma are distinct is R-reducible, Ground (co-)reducibility has been proved to be the fundamental tool for mechanizing inductive proofs, together with the Knuth-Bendix completion procedure presented by Jouannaud and Kounalis (1986, 1989). Jouannaud and Kounalis (1986. 1989) also presented an algorithm for testing ground reducibility which is tractable in practical cases but restricted to left-linear term-rewriting systems. The solution of the ground (co-)reducibility problem, for the general case, turned out to be surprisingly complicated. Decidability of ground reducibility for arbitrary term-rewriting systems has been first proved by Plaisted (1985) and independently by Kapur et al. (1987). However, the algorithms of Plaisted and Kapur et al. amount to intractable computation, even in very simple cases. We present here a new algorithm for the general case which outperforms the algorithms of Plaisted and Kapur et al. and even our previous algorithm in case of left-linear term-rewriting systems. We then show how to adapt it to check for ground co-reducibility.
A recent interesting paper by Melton et al. [1] discussed finding measures which preserve intuitive orderings on software documents. Informally, if less-than-or-equal-to is such an ordering, then they argue that a mea...
详细信息
A recent interesting paper by Melton et al. [1] discussed finding measures which preserve intuitive orderings on software documents. Informally, if less-than-or-equal-to is such an ordering, then they argue that a measure M is a real-valued function defined on documents such that M(F) less-than-or-equal-to M(F) whenever F less-than-or-equal-to F'. However, in measurement theory, this is only a necessary condition for a measure M. The representation condition for measurement additionally requires the converse;that F less-than-or-equal-to F' whenever M(F) less-than-or-equal-to M(F). Using the measurement theory definition of a measure, we show that Melton et al.'s examples, like McCabe's cyclomatic complexity [2], are not measures of the proposed intuitive document ordering after all. However, by dropping the restriction to real-valued functions, we show that it is possible to define a measure which characterises Melton et al.'s order relation;this provides a considerable strengthening of the results in Reference 1. More generally, we show that there is no single real-valued measure which can characterise any intuitive notion of 'complexity' of programs. The power of measurement theory is further illustrated in a critical analysis of some recent work by Weyuker 131 et al. on axioms for software complexity measures.
Ming-Hua Zhang (1988) has proposed a new specification method for data types based on second-order logic. Now we show that errors and exceptions are included directly in the specifications from the beginning. In our a...
详细信息
Ming-Hua Zhang (1988) has proposed a new specification method for data types based on second-order logic. Now we show that errors and exceptions are included directly in the specifications from the beginning. In our approach errors are not objects but indicate that some formulas are false. Unlike errors, exceptions are special objects. The error, error propagation, error recovery and exception can all be precisely defined and the fundamental results about them can be deduced from the specification by predicate calculus.
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.
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.
Concurrency in distributed systems is usually modeled by a nondeterministic interleaving of atomic events. The consequences of this interleaving (or global time) assumption on the specifications and proofs of distribu...
详细信息
Concurrency in distributed systems is usually modeled by a nondeterministic interleaving of atomic events. The consequences of this interleaving (or global time) assumption on the specifications and proofs of distributed programs are examined in this paper. A construction for atomic registers is presented;this construction has the surprising property that it is correct with respect to a specification based on partial orders but is incorrect with respect to a naively derived specification based on global time.
In shared-memory parallel programs that use explicit synchronization, race conditions result when accesses to shared memory are not properly synchronized. Race conditions are often considered to be manifestations of b...
详细信息
In shared-memory parallel programs that use explicit synchronization, race conditions result when accesses to shared memory are not properly synchronized. Race conditions are often considered to be manifestations of bugs, since their presence can cause the program to behave unexpectedly. Unfortunately, there has been little agreement in the literature as to precisely what constitutes a race condition. Two different notions have been implicitly considered: one pertaining to programs intended to be deterministic (which we call general races) and the other to nondeterministic programs containing critical sections (which we call data races). However, the differences between general races and data races have not yet been recognized. This paper examines these differences by characterizing races using a formal model and exploring their properties. We show that two variations of each type of race exist: feasible general races and data races capture the intuitive notions desired for debugging and apparent races capture less accurate notions implicitly assumed by most dynamic race detection methods. We also show that locating feasible races is an NP-hard problem, implying that only the apparent races, which are approximations to feasible races, can be detected in practice. The complexity of dynamically locating apparent races depends on the type of synchronization used by the program. Apparent races can be exhaustively located efficiently only for weak types of synchronization that are incapable of implementing mutual exclusion. This result has important implications since we argue that debugging general races requires exhaustive race detection and is inherently harder than debugging data races (which requires only partial race detection). Programs containing data races can therefore be efficiently debugged by locating certain easily identifiable races. In contrast, programs containing general races require more complex debugging techniques.
We present a new approach to static program analysis that permits each expression in a program to be assigned an execution time estimate. Our approach uses a time system in conjunction with a conventional type system ...
详细信息
We present a new approach to static program analysis that permits each expression in a program to be assigned an execution time estimate. Our approach uses a time system in conjunction with a conventional type system to compute both the type and the time of an expression. The time of an expression is either an integer upper bound on the number of ticks the expression will execute, or the distinguished element long that indicates that the expression contains a loop, and thus may run for an arbitrary length of time. Every function type includes a latent time that is used to communicate its expected execution time from the point of its definition to the points of its use. Unlike previous approaches, a time system works in the presence of first-class functions and separate compilation. In addition, time polymorphism allows the time of a function to depend on the times of any functions that it takes as arguments. Time estimates are useful when compiling programs for multiprocessors in order to balance the overhead of initiating a concurrent computation against the expected execution time of the computation. The correctness of our time system is proven with respect to a dynamic semantics.
A procedure that constructs mechanically the appropriate lemmas for proving assertions about programs with arrays is described. A certain subclass of formulas for which the procedure is guaranteed to terminate and thu...
详细信息
ISBN:
(纸本)0818627352
A procedure that constructs mechanically the appropriate lemmas for proving assertions about programs with arrays is described. A certain subclass of formulas for which the procedure is guaranteed to terminate and thus constitutes a decision procedure is exhibited. This subclass allows for ordering over integers but not for incrementation. A more general subclass that allows for incrementation, but without the termination property, is considered. It is also indicated how to apply the method to a still more general subclass that allows for full arithmetic. These results are extended to the case in which predicates have more than one list argument.
暂无评论