A general class of program analyses are a combination of context-free and regular language reachability. We define regularly annotated set constraints, a constraint formalism that captures this class. Our results exte...
详细信息
ISBN:
(纸本)9781595936332
A general class of program analyses are a combination of context-free and regular language reachability. We define regularly annotated set constraints, a constraint formalism that captures this class. Our results extend the class of reachability problems expressible naturally in a single constraint formalism, including such diverse applications as interprocedural dataflow analysis, precise type-based flow analysis, and pushdown model checking.
Two important problems of object-oriented reuse are the propagation of design and implementation specifics of the base software to the inheritors, and the protection of the inheritors against changes in the base softw...
详细信息
Two important problems of object-oriented reuse are the propagation of design and implementation specifics of the base software to the inheritors, and the protection of the inheritors against changes in the base software. In this paper, we argue that the simple inheritance rules of existing object-oriented languages are not sufficient for properly dealing with these problems. In the proposal presented in this paper, programmers are enabled to make metalevel declarations of the internal protocols and dependencies of their classes. Additionally, changes of the base module are automatically monitored to filter out information about the alterations that may invalidate already existing inheritors. Based on these informations, the subclassing semantics is adjusted such that the maintenance of the base module properties and the protection of the inheritor is ensured during their integration. In this way, language support is provided for keeping the behavior of reusable software consistent during its evolution.
This paper presents an algorithm for synthesizing recursive functions that process algebraic datatypes. It is founded on proof-theoretic techniques that exploit both type information and input-output examples to prune...
详细信息
ISBN:
(纸本)9781450334686
This paper presents an algorithm for synthesizing recursive functions that process algebraic datatypes. It is founded on proof-theoretic techniques that exploit both type information and input-output examples to prune the search space. The algorithm uses refinement trees, a data structure that succinctly represents constraints on the shape of generated code. We evaluate the algorithm by using a prototype implementation to synthesize more than 40 benchmarks and several non-trivial larger examples. Our results demonstrate that the approach meets or outperforms the state-of-the-art for this domain, in terms of synthesis time or attainable size of the generated programs.
Contemporary compiler systems such as GCC,. NET, and LLVM incorporate profile-guided optimizations (PGOs) on low-level intermediate code and basic blocks, with impressive results over purely static heuristics. Recent ...
详细信息
ISBN:
(纸本)9781450334686
Contemporary compiler systems such as GCC,. NET, and LLVM incorporate profile-guided optimizations (PGOs) on low-level intermediate code and basic blocks, with impressive results over purely static heuristics. Recent work shows that profile information is also useful for performing source-to-source optimizations via meta-programming. For example, using profiling information to inform decisions about data structures and algorithms can potentially lead to asymptotic improvements in performance. We present a design for profile-guided meta-programming in a general-purpose meta-programming system. Our design is parametric over the particular profiler and meta-programming system. We implement this design in two different meta-programming systems-the syntactic extensions systems of Chez Scheme and Racket- and provide several profile-guided meta-programs as usability case studies.
This paper presents the techniques used for the compilation of the data-flow, synchronous language SIGNAL. The key feature of the compiler is that it performs formal calculus on systems of boolean equations. The origi...
详细信息
We develop Propane/AT, a system to synthesize provablycorrect BGP (border gateway protocol) configurations for large, evolving networks from high-level specifications of topology, routing policy, and fault-tolerance r...
详细信息
ISBN:
(纸本)9781450349888
We develop Propane/AT, a system to synthesize provablycorrect BGP (border gateway protocol) configurations for large, evolving networks from high-level specifications of topology, routing policy, and fault-tolerance requirements. Propane/AT is based on new abstractions for capturing parameterized network topologies and their evolution, and algorithms to analyze the impact of topology and routing policy on fault tolerance. Our algorithms operate entirely on abstract topologies. We prove that the properties established by our analyses hold for every concrete instantiation of the given abstract topology. Propane/AT also guarantees that only incremental changes to existing device configurations are required when the network evolves to add or remove devices and links. Our experiments with real-world topologies and policies show that our abstractions and algorithms are effective, and that, for large networks, Propane/AT synthesizes configurations two orders of magnitude faster than systems that operate on concrete topologies.
This paper describes the development of the programminglanguage Erlang during the period 1985-1997. Erlang is a concurrent programminglanguagedesigned for programming large-scale distributed soft real-time control ...
详细信息
This paper describes the development of the programminglanguage Erlang during the period 1985-1997. Erlang is a concurrent programminglanguagedesigned for programming large-scale distributed soft real-time control applications. The design of Erlang was heavily influenced by ideas from the logic and functional programming communities. Other sources of inspiration came from languages such as Chill and Ada which are used in industry for programming control systems.
This paper presents and evaluates techniques to improve the execution performance of MATLAB. Previous efforts concentrated on source to source translation and batch compilation;MaJIC provides an interactive frontend t...
详细信息
ISBN:
(纸本)9781581134636
This paper presents and evaluates techniques to improve the execution performance of MATLAB. Previous efforts concentrated on source to source translation and batch compilation;MaJIC provides an interactive frontend that looks like MATLAB and compiles/optimizes code behind the scenes in real time, employing a combination of just-in-time and speculative ahead-of-time compilation. Performance results show that the proper mixture of these two techniques can yield near-zero response time as well as performance gains previously achieved only by batch compilers.
There is an increasing interest in extensible languages, (domain-specific) language extensions, and mechanisms for their specification and implementation. One challenge is to develop tools that allow non-expert progra...
详细信息
ISBN:
(纸本)9781605583921
There is an increasing interest in extensible languages, (domain-specific) language extensions, and mechanisms for their specification and implementation. One challenge is to develop tools that allow non-expert programmers to add an eclectic set of language extensions to a host language. We describe mechanisms for composing and analyzing concrete syntax specifications of a host language and extensions to it. These specifications consist of context-free grammars with each terminal symbol mapped to a regular expression, from which a slightly-modified LR parser and context-aware scanner are generated. Traditionally, conflicts are detected when a parser is generated from the composed grammar, but this comes too late since it is the non-expert programmer directing the composition of independently developed extensions with the host language. The primary contribution of this paper is a modular analysis that is performed independently by each extension designer on her extension ( composed alone with the host language). If each extension passes this modular analysis, then the language composed later by the programmer will compile with no conflicts or lexical ambiguities. Thus, extension writers can verify that their extension will safely compose with others and, if not, fix the specification so that it will. This is possible due to the context-aware scanner's lexical disambiguation and a set of reasonable restrictions limiting the constructs that can be introduced by an extension. The restrictions ensure that the parse table states can be partitioned so that each state can be attributed to the host language or a single extension.
The proceedings contains 35 papers from the proceedings of the 2004 acmsigplanconference on programminglanguagedesign and implementation (PLDI'04). Topics discussed include: effective stream-based and executio...
详细信息
The proceedings contains 35 papers from the proceedings of the 2004 acmsigplanconference on programminglanguagedesign and implementation (PLDI'04). Topics discussed include: effective stream-based and execution-based data prefetching;enhancing data cache reliability by the addition of a small fully-associative replication cache;inter-reference gap distribution replacement: an improved replacement algorithm for set-associative caches;parallel algorithms for mining frequent structural motifs in scientific data;and impact of far-field interactions on performance of multipole-based preconditioners for sparse linear systems.
暂无评论