We have developed and implemented a framework that can be used to construct concise high-level specifications of program analysis techniques. Use of such a framework in a system such as the Synthesizer Generator allow...
详细信息
We have developed and implemented a framework that can be used to construct concise high-level specifications of program analysis techniques. Use of such a framework in a system such as the Synthesizer Generator allows program analysis techniques to be incorporated into program development environments without a need to supply implementation details. This aids in rapid development of new program analysis techniques as well as techniques that share common features but are customized for specific applications. The choice of a denotational framework to express these specifications allows formal proofs of correctness to be established for each of these analysis techniques. The facilities provided by the framework result in clear and concise specifications that aid in the understanding of the corresponding analysis techniques.
Dynamically-typed object-oriented languages please programmers, but their lack of static type information penalizes performance. Our new implementation techniques extract static type information from declaration-free ...
详细信息
Dynamically-typed object-oriented languages please programmers, but their lack of static type information penalizes performance. Our new implementation techniques extract static type information from declaration-free programs. Our system compliles several copies of a given procedure, each customized for one receiver type, so that the type of the receiver is bound at compile time. The compiler predicts types that are statically unknown but likely, and inserts run-time type tests to verify its predictions. It splits calls, compiling a copy on each control path, optimized to the specific types on that path. Coupling these new techniques with compile-time message lookup, aggressive procedure inlining, and traditional optimizations has doubled the performance of dynamically-typed object-oriented languages.
The proceedings contain 49 papers. The topics discussed include: the Howitzer improvement program: lessons learned;requirements analysis for large Ada programs: lessons learned on CCPDS-R;Ada implementation of an x wi...
ISBN:
(纸本)0897913299
The proceedings contain 49 papers. The topics discussed include: the Howitzer improvement program: lessons learned;requirements analysis for large Ada programs: lessons learned on CCPDS-R;Ada implementation of an x window system server;the software lifecycle with Ada: a command and control application;software design documentation approach for a DOD-STD-2167A Ada project;experiences in preparing a DOD-STD-21 WA software design document for an Ada project;environment for operational software engineering in Ada;workstation/APSE productivity study results;and design issues and team support: experiences of an Ada tool vendor.
Optimizing and parallelizing compilers for procedural languages rely on various forms of program dependence graphs (pdgs) to express the essential control and data dependences among atomic program operations. In this ...
详细信息
Optimizing and parallelizing compilers for procedural languages rely on various forms of program dependence graphs (pdgs) to express the essential control and data dependences among atomic program operations. In this paper, we provide a semantic justification for this practice by deriving two different forms of program dependence graph - the output pdg and the def-order pdg - and their semantic definitions from non-strict generalizations of the denotational semantics of the programminglanguage. In the process, we demonstrate that both the output pdg and the def-order pdg (with minor technical modifications) are conventional data-flow programs. In addition, we show that the semantics of the def-order pdg dominates the semantics of the output pdg and that both of these semantics dominate - rather than preserve - the semantics of sequential execution.
The E-algorithm, a method for generating tests for general logic circuits modeled using a hardware description language is presented. The proposed E-algorithm generates tests for control, operation, and data faults in...
详细信息
The E-algorithm, a method for generating tests for general logic circuits modeled using a hardware description language is presented. The proposed E-algorithm generates tests for control, operation, and data faults in sequential and combinational logic modeled at the functional level. A symbolic variable notation is introduced to permit systematic fault propagation through control structures. A fault model based on faulting structures in a graph derived from the hardware description language model, and a test generation algorithm that generates tests for the modeled faults have been developed and implemented. The E-algorithm has the ability to propagate fault syndromes through high-level control structures as well as data operations. Results of the implementation are given for a set of test cases, and the application of the algorithm to a semicustom ASIC (application-specific integrated circuit) is discussed. Preliminary results show high fault coverages and reasonable performance.
Our concern is how to determine data dependences between program constructs in programminglanguages with pointer variables. We are particularly interested in computing data dependences for languages that manipulate h...
详细信息
Our concern is how to determine data dependences between program constructs in programminglanguages with pointer variables. We are particularly interested in computing data dependences for languages that manipulate heap-allocated storage, such as Lisp and Pascal. We have defined a family of algorithms that compute safe approximations to the flow, output, and anti-dependences of a program written in such a language. Our algorithms account for destructive updates to fields of a structure and thus are not limited to the cases where all structures are trees or acyclic graphs;they are applicable to programs that build cyclic structures. For structured programming constructs, the technique can be extended to distinguish between loop-carried and loop-independent dependences, as well as to determine lower bounds on minimum distances for loop-carried dependences.
We present a new static analysis method for first-class continuations that uses an effect system to classify the control domain behavior of expressions in a typed polymorphic language. We introduce two new control eff...
详细信息
We present a new static analysis method for first-class continuations that uses an effect system to classify the control domain behavior of expressions in a typed polymorphic language. We introduce two new control effects, goto and comefrom, that describe the control flow properties of expressions. An expression that does not have a goto effect is said to be continuation following because it will always call its passed return continuation. An expression that does not have a comefrom effect is said to be continuation discarding because it will never preserve its return continuation for later use. Unobservable control effects can be masked by the effect system. Control effect soundness theorems guarantee that the effects computed statically by the effect system are a conservative approximation of the dynamic behavior of an expression.
Mul-T is a parallel Lisp system, based on Multilisp's future construct, that has been developed to run on an Encore Multimax multiprocessor. Mul-T is an extended version of the Yale T system and uses the T system&...
详细信息
Mul-T is a parallel Lisp system, based on Multilisp's future construct, that has been developed to run on an Encore Multimax multiprocessor. Mul-T is an extended version of the Yale T system and uses the T system's ORBIT compiler to achieve 'production quality' performance on stock hardware - about 100 times faster than Multilisp. Mul-T shows that futures can be implemented cheaply enough to be useful in a production-quality system. Mul-T is fully operational, including a user interface that supports managing groups of parallel tasks.
The disadvantages of traditional two-phase parsing (a scanner phase preprocessing input for a parser phase) are discussed. We present metalanguage enhancements for context-free grammars that allow the syntax of progra...
ISBN:
(纸本)9780897913065
The disadvantages of traditional two-phase parsing (a scanner phase preprocessing input for a parser phase) are discussed. We present metalanguage enhancements for context-free grammars that allow the syntax of programminglanguages to be completely described in a single grammar. The enhancements consist of two new grammar rules, the exclusion rule, and the adjacency-restriction rule. We also present parser construction techniques for building parsers from these enhanced grammars, that eliminate the need for a scanner phase.
An LR-based parser generator for arbitrary context-free grammars is described, which generates parsers by need and processes grammar modifications by updating already existing parsers. We motivate the need for these t...
ISBN:
(纸本)9780897913065
An LR-based parser generator for arbitrary context-free grammars is described, which generates parsers by need and processes grammar modifications by updating already existing parsers. We motivate the need for these techniques in the context of interactive language definition environments, present all required algorithms, and give measurements comparing their performance with that of conventional techniques.
暂无评论