检索结果-内蒙古大学图书馆

Synthesizing Transformations on Hierarchically Structured Data

acm sigplan NOTICES 2016年第6期51卷 508-521页

作者： Yaghmazadeh, Navid Klinger, Christian Dillig, Isil Chaudhuri, Swarat Univ Texas Austin Austin TX 78712 USA Univ Freiburg Freiburg Germany Rice Univ Houston TX 77251 USA

This paper presents a new approach for synthesizing transformations on tree-structured data, such as Unix directories and XML documents. We consider a general abstraction for such data, called hierarchical data trees (HDTs) and present a novel example-driven synthesis algorithm for HDT transformations. Our central insight is to reduce the problem of synthesizing tree transformers to the synthesis of list transformations that are applied to the paths of the tree. The synthesis problem over lists is solved using a new algorithm that combines SMT solving and decision tree learning. We have implemented our technique in a system called HADES and show that HADES can automatically synthesize a variety of interesting transformations collected from online forums.

关键词： languages Program synthesis programming by example data transformations

来源：评论

学校读者我要写书评

暂无评论

Fabular: Regression Formulas as Probabilistic programming

引用

acm sigplan NOTICES 2016年第1期51卷 271-283页

作者： Borgstrom, Johannes Gordon, Andrew D. Ouyang, Long Russo, Claudio Scibior, Adam Szymczak, Marcin Uppsala Univ S-75105 Uppsala Sweden Microsoft Res Bangalore Karnataka India Univ Edinburgh Edinburgh EH8 9YL Midlothian Scotland Stanford Univ Stanford CA 94305 USA Univ Cambridge Cambridge CB2 1TN England MPI Tubingen Tubingen Germany

Regression formulas are a domain-specific language adopted by several R packages for describing an important and useful class of statistical models: hierarchical linear regressions. Formulas are succinct, expressive, and clearly popular, so are they a useful addition to probabilistic programming languages? And what do they mean? We propose a core calculus of hierarchical linear regression, in which regression coefficients are themselves defined by nested regressions (unlike in R). We explain how our calculus captures the essence of the formula DSL found in R. We describe the design and implementation of Fabular, a version of the Tabular schema-driven probabilistic programming language, enriched with formulas based on our regression calculus. To the best of our knowledge, this is the first formal description of the core ideas of R's formula notation, the first development of a calculus of regression formulas, and the first demonstration of the benefits of composing regression formulas and latent variables in a probabilistic programming language.

关键词： Bayesian inference linear regression probabilistic programming relational data hierarchical models

来源：评论

学校读者我要写书评

暂无评论

Event-Driven Network programming

引用

acm sigplan NOTICES 2016年第6期51卷 369-385页

作者： McClurg, Jedidiah Hojjat, Hossein Foster, Nate Cerny, Pavol CU Boulder Boulder CO 80309 USA Cornell Univ Ithaca NY 14853 USA

Software-defined networking (SDN) programs must simultaneously describe static forwarding behavior and dynamic updates in response to events. Event-driven updates are critical to get right, but difficult to implement correctly due to the high degree of concurrency in networks. Existing SDN platforms offer weak guarantees that can break application invariants, leading to problems such as dropped packets, degraded performance, security violations, etc. This paper introduces event-driven consistent updates that are guaranteed to preserve well-defined behaviors when transitioning between configurations in response to events. We propose network event structures (NESs) to model constraints on updates, such as which events can be enabled simultaneously and causal dependencies between events. We define an extension of the NetKAT language with mutable state, give semantics to stateful programs using NESs, and discuss provably-correct strategies for implementing NESs in SDNs. Finally, we evaluate our approach empirically, demonstrating that it gives well-defined consistency guarantees while avoiding expensive synchronization and packet buffering.

关键词： network update consistent update event structure software-defined networking SDN NetKAT

来源：评论

学校读者我要写书评

暂无评论

Higher-Order and Tuple-Based Massively-Parallel Prefix Sums

引用

acm sigplan NOTICES 2016年第6期51卷 539-552页

作者： Maleki, Sepideh Yang, Annie Burtscher, Martin Texas State Univ Dept Comp Sci San Marcos TX 78666 USA

Prefix sums are an important parallel primitive, especially in massively-parallel programs. This paper discusses two orthogonal generalizations thereof, which we call higher-order and tuple-based prefix sums. Moreover, it describes and evaluates SAM, a GPU-friendly algorithm for computing prefix sums and other scans that directly supports higher orders and tuple values. Its templated CUDA implementation unifies all of these computations in a single 100-statement kernel. SAM is communication-efficient in the sense that it minimizes main-memory accesses. When computing prefix sums of a million or more values, it outperforms Thrust and CUDPP on both a Titan X and a K40 GPU. On the Titan X, SAM reaches memory-copy speeds for large input sizes, which cannot be surpassed. SAM outperforms CUB, the currently fastest conventional prefix sum implementation, by up to a factor of 2.9 on eighth-order prefix sums and by up to a factor of 2.6 on eight-tuple prefix sums.

关键词： Algorithms Performance design Higher-order prefix sums tuple-based prefix sums carry propagation GPU programming

来源：评论

学校读者我要写书评

暂无评论

LLJava: Minimalist structured programming on the Java virtual machine [work-in-progress research paper] 16

LLJava: Minimalist structured programming on the Java virtua...

引用

13th International conference on Principles and Practices of programming on the Java Platform: Virtual Machines, languages, and Tools, PPPJ 2016

作者： Widemann, Baltasar Trancón Y. Lepper, Markus Ilmenau University of Technology Ehrenbergstraße 29 Ilmenau98693 Germany Semantics GmbH Berlin Germany

ISBN: (纸本)9781450341356

There is a wide gap in abstraction level between Java source code and JVM bytecode. Many important software-related tasks, such as specification and implementation of code syn- thesis procedures, code inspection, software understanding and teaching, can benefit from an adequate, intermediate level of abstraction. Available bytecode assembly/disassem- bly tools are ad-hoc and fall short of the requirements regard- ing compositionality and clarity. We report on the design and implementation of the LLJava language that bridges the gap, based on careful analysis of bytecode information and rigorous design. © 2016 Copyright held by the owner/author(s). Publication rights licensed to acm.

关键词： Network security

来源：评论

学校读者我要写书评

暂无评论

Program Synthesis from Polymorphic Refinement Types

引用

acm sigplan NOTICES 2016年第6期51卷 522-538页

作者： Polikarpova, Nadia Kuraj, Ivan Solar-Lezama, Armando MIT CSAIL Cambridge MA USA

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.

关键词： languages Verification Program Synthesis Functional programming Refinement Types Predicate Abstraction

来源：评论

学校读者我要写书评

暂无评论

GreenWeb: language Extensions for Energy-Efficient Mobile Web Computing

引用

acm sigplan NOTICES 2016年第6期51卷 145-160页

作者： Zhu, Yuhao Reddi, Vijay Janapa Univ Texas Austin Dept Elect & Comp Engn Austin TX 78712 USA

Web computing is gradually shifting toward mobile devices, in which the energy budget is severely constrained. As a result, Web developers must be conscious of energy efficiency. However, current Web languages provide developers little control over energy consumption. In this paper, we take a first step toward language-level research to enable energy-efficient Web computing. Our key motivation is that mobile systems can wisely budget energy usage if informed with user quality-of-service (QoS) constraints. To do this, programmers need new abstractions. We propose two language abstractions, QoS type and QoS target, to capture two fundamental aspects of user QoS experience. We then present Green Web, a set of language extensions that empower developers to easily express the QoS abstractions as program annotations. As a proof of concept, we develop a GreenWeb runtime, which intelligently determines how to deliver specified user QoS expectation while minimizing energy consumption. Overall, GreenWeb shows significant energy savings (29.2% similar to 66.0%) over Android's default Interactive governor with few QoS violations. Our work demonstrates a promising first step toward language innovations for energy-efficient Web computing.

关键词： Energy-efficiency Web Mobile computing

来源：评论

学校读者我要写书评

暂无评论

A Distributed OpenCL Framework using Redundant Computation and Data Replication

引用

acm sigplan NOTICES 2016年第6期51卷 553-569页

作者： Kim, Junghyun Jo, Gangwon Jung, Jaehoon Kim, Jungwon Lee, Jaejin Seoul Natl Univ Ctr Manycore Programming Dept Comp Sci & Engn Seoul 08826 South Korea

Applications written solely in OpenCL or CUDA cannot execute on a cluster as a whole. Most previous approaches that extend these programming models to clusters are based on a common idea: designating a centralized host node and coordinating the other nodes with the host for computation. However, the centralized host node is a serious performance bottleneck when the number of nodes is large. In this paper, we propose a scalable and distributed OpenCL framework called SnuCL-D for large-scale clusters. SnuCL-D's remote device virtualization provides an OpenCL application with an illusion that all compute devices in a cluster are confined in a single node. To reduce the amount of control-message and data communication between nodes, SnuCL-D replicates the OpenCL host program execution and data in each node. We also propose a new OpenCL host API function and a queueing optimization technique that significantly reduce the overhead incurred by the previous centralized approaches. To show the effectiveness of SnuCL-D, we evaluate SnuCL-D with a microbenchmark and eleven benchmark applications on a large-scale CPU cluster and a medium-scale GPU cluster.

关键词： OpenCL clusters heterogeneous computing programming models runtime systems redundant computation data replication

来源：评论

学校读者我要写书评

暂无评论

Disjoint Intersection Types

引用

acm sigplan NOTICES 2016年第9期51卷 364-377页

作者： Oliveira, Bruno C. d. S. Shi, Zhiyuan Alpuim, Joao Univ Hong Kong Hong Kong Hong Kong Peoples R China

Dunfield showed that a simply typed core calculus with intersection types and a merge operator is able to capture various programming language features. While his calculus is type-safe, it is not coherent: different derivations for the same expression can elaborate to expressions that evaluate to different values. The lack of coherence is an important disadvantage for adoption of his core calculus in implementations of programming languages, as the semantics of the programming language becomes implementation-dependent. This paper presents lambda(i) : a coherent and type-safe calculus with a form of intersection types and a merge operator. Coherence is achieved by ensuring that intersection types are disjoint and programs are sufficiently annotated to avoid type ambiguity. We propose a definition of disjointness where two types A and B are disjoint only if certain set of types are common supertypes of A and B. We investigate three different variants of lambda(i), with three variants of disjointness. In the simplest variant, which does not allow inverted perpendicular types, two types are disjoint if they do not share any common supertypes at all. The other two variants introduce inverted perpendicular types and refine the notion of disjointness to allow two types to be disjoint when the only the set of common supertypes are top-like. The difference between the two variants with inverted perpendicular types is on the definition of top-like types, which has an impact on which types are allowed on intersections. We present a type system that prevents intersection types that are not disjoint, as well as an algorithmic specifications to determine whether two types are disjoint for all three variants.

关键词： Intersection Types Type System design languages Theory

来源：评论

学校读者我要写书评

暂无评论

Occurrence Typing Modulo Theories

引用

acm sigplan NOTICES 2016年第6期51卷 296-309页

作者： Kent, Andrew M. Kempe, David Tobin-Hochstadt, Sam Indiana Univ Bloomington IN 47405 USA

We present a new type system combining occurrence typing- a technique previously used to type check programs in dynamically-typed languages such as Racket, Clojure, and JavaScript-with dependent refinement types. We demonstrate that the addition of refinement types allows the integration of arbitrary solver-backed reasoning about logical propositions from external theories. By building on occurrence typing, we can add our enriched type system as a natural extension of Typed Racket, reusing its core while increasing its expressiveness. The result is a well-tested type system with a conservative, decidable core in which types may depend on a small but extensible set of program terms. In addition to describing our design, we present the following: a formal model and proof of correctness;a strategy for integrating new theories, with specific examples including linear arithmetic and bitvectors;and an evaluation in the context of the full Typed Racket implementation. Specifically, we take safe vector operations as a case study, examining all vector accesses in a 56,000 line corpus of Typed Racket programs. Our system is able to prove that 50% of these are safe with no new annotations, and with a few annotations and modifications we capture more than 70%.

关键词： languages design Verification Refinement types occurrence typing Racket

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：