We describe PSKETCH, a program synthesizer that helps programmers implement concurrent data structures. The system is based on the concept of sketching, a form of synthesis that allows programmers to express their ins...
详细信息
We describe PSKETCH, a program synthesizer that helps programmers implement concurrent data structures. The system is based on the concept of sketching, a form of synthesis that allows programmers to express their insight about an implementation as a partial program: a sketch. The synthesizer automatically completes the sketch to produce an implementation that matches a given correctness criteria. PSKETCH is based on a new counterexample-guided inductive synthesis algorithm (CEGIS) that generalizes the original sketch synthesis algorithm from [ 20] to cope efficiently with concurrent programs. The new algorithm produces a correct implementation by iteratively generating candidate implementations, running them through a verifier, and if they fail, learning from the counterexample traces to produce a better candidate;converging to a solution in a handful of iterations. PSKETCH also extends SKETCH with higher-level sketching constructs that allow the programmer to express her insight as a "soup" of ingredients from which complicated code fragments must be assembled. Such sketches can be viewed as syntactic descriptions of huge spaces of candidate programs ( over 1 0 8 candidates for some sketches we resolved). We have used the PSKETCH system to implement several classes of concurrent data structures, including lock-free queues and concurrent sets with fine-grained locking. We have also sketched some other concurrent objects including a sense-reversing barrier and a protocol for the dining philosophers problem;all these sketches resolved in under an hour.
Computer experiments are part of the daily business for many researchers within the area of computational intelligence. However, there is no standard for either human or computer readable documentation of computer exp...
详细信息
ISBN:
(纸本)9781450311786
Computer experiments are part of the daily business for many researchers within the area of computational intelligence. However, there is no standard for either human or computer readable documentation of computer experiments. Such a standard could considerably improve the collaboration between experimental researchers, given it is intuitive to use. In response to this deficiency the Intelligent Param eter Utilization Tool (InPUT ) is introduced. InPUT offers a general and programminglanguage independent format for the definition of parameters and their ranges. It provides services to simplify the implementation of algorithms and can be used as a substitute for input mechanisms of existing frameworks. InPUT reduces code-complexity and increases the reusability of algorithm designs as well as the reproducibility of experiments. InPUT is available as open-source for Java and this will soon also be extended to C++, two of the predominant languages of choice for the development of evolutionary algorithms.
We present a method for synthesizing recursive functions that provably satisfy a given specification in the form of a polymorphic refinement type. We observe that such specifications are particularly suitable for prog...
详细信息
We present a method for synthesizing recursive functions that provably satisfy a given specification in the form of a polymorphic refinement type. We observe that such specifications are particularly suitable for program synthesis for two reasons. First, they offer a unique combination of expressive power and decidability, which enables automatic verification-and hence synthesis-of nontrivial programs. Second, a type-based specification for a program can often be effectively decomposed into independent specifications for its components, causing the synthesizer to consider fewer component combinations and leading to a combinatorial reduction in the size of the search space. At the core of our synthesis procedure is a newalgorithm for refinement type checking, which supports specification decomposition. We have evaluated our prototype implementation on a large set of synthesis problems and found that it exceeds the state of the art in terms of both scalability and usability. The tool was able to synthesize more complex programs than those reported in prior work (several sorting algorithms and operations on balanced search trees), as well as most of the benchmarks tackled by existing synthesizers, often starting from a more concise and intuitive user input.
Architecture description languages deal with the description, analysis and reuse of software architectures. This paper describes DAOP-ADL, a component- and aspect-based language to specify the architecture of an appli...
详细信息
Concurrent garbage collection is highly attractive for real-time systems, because offloading the collection effort from the executing threads allows faster response, allowing for extremely short deadlines at the micro...
详细信息
Concurrent garbage collection is highly attractive for real-time systems, because offloading the collection effort from the executing threads allows faster response, allowing for extremely short deadlines at the microseconds level. Concurrent collectors also offer much better scalability over incremental collectors. The main problem with concurrent real-time collectors is their complexity. The first concurrent real-time garbage collector that can support fine synchronization, STOPLESS, has recently been presented by Pizlo et al. In this paper, we propose two additional ( and different) algorithms for concurrent real-time garbage collection: CLOVER and CHICKEN. Both collectors obtain reduced complexity over the first collector STOPLESS, but need to trade a benefit for it. We study the algorithmic strengths and weaknesses of CLOVER and CHICKEN and compare them to STOPLESS. Finally, we have implemented all three collectors on the Bartok compiler and runtime for C# and we present measurements to compare their efficiency and responsiveness.
Refactorings are behaviour-preserving program transformations, typically for improving the structure of existing code. A few of these transformations have been mechanised in interactive development environments. Many ...
详细信息
ISBN:
(纸本)1595933751
Refactorings are behaviour-preserving program transformations, typically for improving the structure of existing code. A few of these transformations have been mechanised in interactive development environments. Many more refactorings have been proposed, and it would be desirable for programmers to script their own refactorings. Implementing such source-to-source transformations, however, is quite complex: even the most sophisticated development environments contain significant bugs in their refactoring tools. We present a domain-specific language for refactoring, named JunGL. It manipulates a graph representation of the program: all information about the program, including ASTs for its compilation units, variable binding, control flow and so on is represented in a uniform graph format. The language is a hybrid of a functional language (in the style of ML) and a logic query language (akin to Datalog). JunGL furthermore has a notion of demand-driven evaluation for constructing computed information in the graph, such as control flow edges. Borrowing from earlier work on the specification of compiler optimisations, JunGL uses socalled 'path queries' to express dataflow properties. We motivate the design of JunGL via a number of nontrivial refactorings, and describe its implementation on the .NET platform. Copyright 2006 acm.
In the context of sequential computers, it is common practice to exploit temporal locality of reference through devices such as caches and virtual memory. In the context of multiprocessors, we believe that it is equal...
详细信息
In the context of sequential computers, it is common practice to exploit temporal locality of reference through devices such as caches and virtual memory. In the context of multiprocessors, we believe that it is equally important to exploit spatial locality of reference. We are developing a system which, given a sequential program and its domain decomposition, performs process decomposition so as to enhance spatial locality of reference. We describe an application of this method - generating code from shared-memory programs for the (distributed memory) Intel iPSC/2.
In this paper, we present a technique for summarizing the data accesses in a given region and show how this summary can be used to detect and enhance task parallelism in a program. For the sake of simplicity, we restr...
详细信息
In this paper, we present a technique for summarizing the data accesses in a given region and show how this summary can be used to detect and enhance task parallelism in a program. For the sake of simplicity, we restrict our discussion to Fortran programs that consist of a sequence of perfectly-nested loops in which all subroutine calls are expanded inline. However, the techniques presented here can easily be extended to the general case of programs with imperfectly nested loops and subroutine calls.
Cedar is the name for both a language and an environment in use in the Computer Science Laboratory at Xerox PARC since 1980. The Cedar language is a superset of Mesa, the major additions being garbage collection and r...
详细信息
Cedar is the name for both a language and an environment in use in the Computer Science Laboratory at Xerox PARC since 1980. The Cedar language is a superset of Mesa, the major additions being garbage collection and runtime types. Neither the language nor the environment was originally intended to be portable, and for many years ran only on D-machines at PARC and a few other locations in Xerox. We recently re-implemented the language to make it portable across many different architectures. We present a brief description of the Cedar language, our portability strategy for the compiler and runtime, our manner of making connections to other languages and the Unix operating system, and some measures of the performance of our 'Portable Cedar'.
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.
暂无评论