Domain analysis typically results in the construction of a domain-specific repository. Such a repository imposes artificial boundaries on the sharing of similar assets between related domains. A lattice-based approach...
详细信息
ISBN:
(纸本)0818628308
Domain analysis typically results in the construction of a domain-specific repository. Such a repository imposes artificial boundaries on the sharing of similar assets between related domains. A lattice-based approach to repository modeling can preserve a reuser's domain specific view of the repository, while avoiding replication of commonly used assets and supporting a more general perspective on domain interrelationships.
In an attempt to devise a general notion of model for spatial logic, we have been led to consider transition systems with an additional so-called spatial structure on the states, with both the tran- sition and the spa...
详细信息
Rules are used as a programming paradigm in several application domains, including active databases, planning, expert systems, and billing. For example, active databases have rules that execute upon the occurrence of ...
详细信息
Rules are used as a programming paradigm in several application domains, including active databases, planning, expert systems, and billing. For example, active databases have rules that execute upon the occurrence of particular events if specified condition predicates are satisfied. It is often the case that multiple rules are fireable when a particular event occurs. We propose a declarative mechanism to control the interaction and execution of multiple rules. The mechanism is based upon logical meta-rules that can express various types of relationships between rules. The meta-rules allow us to reason statically about the rule behavior. We can determine, in polynomial time, if a rule will never execute, whether two rules can ever be executed together, and whether a rule system is guaranteed to have a unique execution set for all possible rules that become fireable. In this paper, we illustrate our techniques using rules in an active database. A system based upon the meta-rules and the static analysis presented here has been found to be of value in a billing application at AT&T to control interactions between discount plans, and is presently being implemented within the application.
The theory of programming with pattern-matching function definitions has been studied mainly in the framework of first-order rewrite systems. We present a typed functional calculus that emphasizes the strong connectio...
详细信息
ISBN:
(纸本)0818631422
The theory of programming with pattern-matching function definitions has been studied mainly in the framework of first-order rewrite systems. We present a typed functional calculus that emphasizes the strong connection between the structure of whole pattern definitions and their types. In this calculus typechecking guarantees the absence of runtime errors caused by nonexhaustive pattern-matching definitions. Its operational semantics is deterministic in a natural way, without the imposition of ad-hoc solutions such as clause order or `best fit'. In the spirit of the Curry-Howard isomorphism, we design the calculus as a computational interpretation of the Gentzen sequent proofs for the intuitionistic propositional logic. We prove the basic properties connecting typing and evaluation: subject reduction and strong normalization. We believe that this calculus offers a rational reconstruction of the pattern-matching features found in successful functional languages.
We present a minimal extension of the Hindley/Milner system to allow for overloading of identifiers. Our approach relies on a combination of the HM(X) type system framework with Constraint Handling Rules (CHRs). CHRs ...
详细信息
ISBN:
(纸本)9781581134872
We present a minimal extension of the Hindley/Milner system to allow for overloading of identifiers. Our approach relies on a combination of the HM(X) type system framework with Constraint Handling Rules (CHRs). CHRs are a declarative language for writing incremental constraint solvers. CHRs allow us to precisely describe the relationships among overloaded identifiers. Under some sufficient conditions on the CHRs we achieve decidable type inference and the semantic meaning of programs is unambiguous. Our approach allows us to combine open and closed world overloading. We also show how to deal with overlapping definitions.
Visual notations are pervasive in circuit design, control systems, and increasingly in mainstream programming environments. Yet many of the foundational advances in programming language theory are taking place in the ...
详细信息
Grammar-based programs analyses are static analysis techniques that have traditionally been seen as quite different from abstract-interpretation-based analyses, due to their apparent non-iterative nature. There are de...
详细信息
ISBN:
(纸本)9780897917193
Grammar-based programs analyses are static analysis techniques that have traditionally been seen as quite different from abstract-interpretation-based analyses, due to their apparent non-iterative nature. There are decidable kinds of analysis that cannot be computed using abstract interpretation (even with widening and narrowing). An example of this is the set-based analysis considered in this work. It is shown that grammar and set-constraint-based program analyses are similar abstract interpretations with iterative fixpoint computation using either a widening or a finitary grammar/set-constraints transformer or even a finite domain for each particular program.
A new method for polymorphic type interference for the dynamically typed language Scheme is described. The method which infers both types and explicit run-time type operations (coercions) for a given program can be us...
详细信息
A new method for polymorphic type interference for the dynamically typed language Scheme is described. The method which infers both types and explicit run-time type operations (coercions) for a given program can be used to statically debug Scheme programs and to give a high-level translation to ML, in essence providing an 'embedding' of Scheme into ML. Finally, an introduction to the type theoretic framework of polymorphic dynamic typing is given, the phases of the type interference process are described, and some examples of the resulting Scheme-to-ML translator are presented.
Applications of iteration space slicing to communication optimizations in parallel executions of programs such as stencil computations and book-cyclic Gaussian elimination with partial pivoting are examined. The key s...
详细信息
ISBN:
(纸本)9780897919029
Applications of iteration space slicing to communication optimizations in parallel executions of programs such as stencil computations and book-cyclic Gaussian elimination with partial pivoting are examined. The key step in calculating an iteration space slice is to calculate the transitive closure of the data dependence graph of the program;the transitive dependences then are applied to the iterations of interest to produce the slice.
This paper describes a framework for modeling macroscopic program behavior and applies it to optimizing prescient instruction prefetch - a novel technique that uses helper threads to improve single-threaded applicatio...
详细信息
ISBN:
(纸本)1581136641
This paper describes a framework for modeling macroscopic program behavior and applies it to optimizing prescient instruction prefetch - a novel technique that uses helper threads to improve single-threaded application performance by performing judicious and timely instruction prefetch. A helper thread is initiated when the main thread encounters a spawn point, and prefetches instructions starting at a distant target point. The target identifies a code region tending to incur I-cache misses that the main thread is likely to execute soon, even though intervening control flow may be unpredictable. The optimization of spawn-target pair selections is formulated by modeling program behavior as a Markov chain based on profile statistics. Execution paths are considered stochastic outcomes, and aspects of program behavior are summarized via path expression mappings. Mappings for computing reaching, and posteriori probability;path length mean, and variance;and expected path footprint are presented. These are used with Tarjan's fast path algorithm to efficiently estimate the benefit of spawn-target pair selections. Using this framework we propose a spawn-target pair selection algorithm for prescient instruction prefetch. This algorithm has been implemented, and evaluated for the Itanium® Processor Family architecture. A limit study finds 4.8% to 17% speedups on an in-order simultaneous multithreading processor with eight contexts, over nextline and streaming I-prefetch for a set of benchmarks with high I-cache miss rates. The framework in this paper is potentially applicable to other thread speculation techniques. Copyright 2003 ACM.
暂无评论