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

38th acm sigplan conference on programming language design and implementation (PLDI)

作者： Feng, Yu Martins, Ruben Van Geffen, Jacob Dillig, Isil Chaudhuri, Swarat Univ Texas Austin Austin TX 78712 USA Rice Univ Houston TX 77251 USA

ISBN: (纸本)9781450349888

this paper presents a novel component-based synthesis algorithm that marries the power of type-directed search with lightweight SMT-based deduction and partial evaluation. Given a set of components together with their over-approximate first-order specifications, our method first generates a program sketch over a subset of the components and checks its feasibility using an SMT solver. Since a program sketch typically represents many concrete programs, the use of SMT-based deduction greatly increases the scalability of the algorithm. Once a feasible program sketch is found, our algorithm completes the sketch in a bottom-up fashion, using partial evaluation to further increase the power of deduction for rejecting partially-filled program sketches. We apply the proposed synthesis methodology for automating a large class of data preparation tasks that commonly arise in data science. We have evaluated our synthesis algorithm on dozens of data wrangling and consolidation tasks obtained from on-line forums, and we show that our approach can automatically solve a large class of problems encountered by R users.

关键词： Program synthesis programming by example data preparation Component-based synthesis SMT-based deduction

来源：评论

学校读者我要写书评

暂无评论

Defining the Undefinedness of C 15

Defining the Undefinedness of C

引用

36th acm sigplan conference on programming language design and implementation

作者： Hathhorn, Chris Ellison, Chucky Rosu, Grigore Univ Missouri Columbia MO 65211 USA Univ Illinois Urbana IL 61801 USA

ISBN: (纸本)9781450334686

We present a "negative" semantics of the C11 language-a semantics that does not just give meaning to correct programs, but also rejects undefined programs. We investigate undefined behavior in C and discuss the techniques and special considerations needed for formally specifying it. We have used these techniques to modify and extend a semantics of C into one that captures undefined behavior. the amount of semantic infrastructure and effort required to achieve this was unexpectedly high, in the end nearly doubling the size of the original semantics. From our semantics, we have automatically extracted an undefinedness checker, which we evaluate against other popular analysis tools, using our own test suite in addition to a third-party test suite. Our checker is capable of detecting examples of all 77 categories of core language undefinedness appearing in the C11 standard, more than any other tool we considered. Based on this evaluation, we argue that our work is the most comprehensive and complete semantic treatment of undefined behavior in C, and thus of the C language itself.

关键词： Undefined behavior programming language semantics C11 K Framework

来源：评论

学校读者我要写书评

暂无评论

An Applied Quantum Hoare Logic 2019

An Applied Quantum Hoare Logic

引用

40th acm sigplan conference on programming language design and implementation (PLDI) part of acm's Federated Computing Research conference (FCRC)

作者： Zhou, Li Yu, Nengkun Ying, Mingsheng Tsinghua Univ Dept Comp Sci & Technol Beijing Peoples R China Univ Technol Sydney CQSI FEIT Sydney NSW Australia Chinese Acad Sci Inst Software Beijing Peoples R China Tsinghua Univ Beijing Peoples R China

ISBN: (纸本)9781450367127

We derive a variant of quantum Hoare logic (QHL), called applied quantum Hoare logic (aQHL for short), by: (1) restricting QHL to a special class of preconditions and postconditions, namely projections, which can significantly simplify verification of quantum programs and are much more convenient when used in debugging and testing;and (2) adding several rules for reasoning about robustness of quantum programs, i.e. error bounds of outputs. the effectiveness of aQHL is shown by its applications to verify two sophisticated quantum algorithms: HHL (Harrow-Hassidim-Lloyd) for solving systems of linear equations and qPCA (quantum Principal Component Analysis).

关键词： Quantum computation programming languages Hoare logic projections robustness

来源：评论

学校读者我要写书评

暂无评论

Interactive Parser Synthesis by Example 15

Interactive Parser Synthesis by Example

引用

36th acm sigplan conference on programming language design and implementation

作者： Leung, Alan Sarracino, John Lerner, Sorin Univ Calif San Diego San Diego CA 92103 USA

ISBN: (纸本)9781450334686

Despite decades of research on parsing, the construction of parsers remains a painstaking, manual process prone to subtle bugs and pitfalls. We present a programming-by-example framework called Parsify that is able to synthesize a parser from input/output examples. the user does not write a single line of code. To achieve this, Parsify provides: (a) an iterative algorithm for synthesizing and refining a grammar one example at a time, (b) an interface that provides immediate visual feedback in response to changes in the grammar being refined, and (c) a graphical mechanism for specifying example parse trees using only textual selections. We empirically demonstrate the viability of our approach by using Parsify to construct parsers for source code drawn from Verilog, SQL, Apache, and Tiger.

关键词： Algorithms Human Factors languages Parsing programming by Example Program Synthesis

来源：评论

学校读者我要写书评

暂无评论

Program Synthesis from Polymorphic Refinement Types 16

Program Synthesis from Polymorphic Refinement Types

引用

37th acm sigplan conference on programming language design and implementation

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

ISBN: (纸本)9781450342612

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

来源：评论

学校读者我要写书评

暂无评论

Experience Report: seL4 Formally Verifying a High-Performance Microkernel

Experience Report: seL4 Formally Verifying a High-Performanc...

引用

14th acm sigplan International conference on Functional programming

作者： Klein, Gerwin Derrin, Philip Elphinstone, Kevin NICTA University of NSW Australia NICTA Australia

ISBN: (纸本)9781605583327

We report on our experience using Haskell as an executable specification language in the formal verification of the seL4 microkernel. the verification connects an abstract operational specification in the theorem prover Isabelle/HOL to a C implementation of the microkernel. We describe how this project differs from other efforts, and examine the effect of using Haskell in a large-scale formal verification. the kernel comprises 8,700 lines of C code;the verification more than 150,000 lines of proof script.

关键词： Verification design languages Haskell seL4 microkernel Isabelle/HOL

来源：评论

学校读者我要写书评

暂无评论

Once upon a polymorphic type

Conference Record of the Annual ACM Symposium on Principles ...

引用

conference Record of the Annual acm Symposium on Principles of programming languages 1999年 15-28页

作者： Wansbrough, Keith Jones, Simon Peyton Univ of Cambridge Cambridge United Kingdom

We present a sound type-based `usage analysis' for a realistic lazy functional language. Accurate information on the usage of program subexpressions in a lazy functional language permits a compiler to perform a number of useful optimizations. However, existing analyses are either ad-hoc and approximate, or defined over restricted languages. Our work extends the Once Upon A Type system of Turner, Mossin, and Wadler (FPCA'95). Firstly, we add type polymorphism, an essential feature of typed functional programming languages. Secondly, we include general Haskell-style user-defined algebraic data types. thirdly, we explain and solve the `poisoning problem', which causes the earlier analysis to yield poor results. Interesting design choices turn up in each of these areas. Our analysis is sound with respect to a Launchbury-style operational semantics, and it is straightforward to implement. Good results have been obtained from a prototype implementation, and we are currently integrating the system into the Glasgow Haskell Compiler.

关键词： Computer programming languages

来源：评论

学校读者我要写书评

暂无评论

RaTrace: Simple and Efficient Abstractions for BVH Ray Traversal Algorithms 2017

RaTrace: Simple and Efficient Abstractions for BVH Ray Trave...

引用

16th acm sigplan International conference on Generative programming - Concepts and Experiences (GPCE) co-located with SPLASH conference

作者： Perard-Gayot, Arsene Weier, Martin Membarth, Richard Slusallek, Philipp Leissa, Roland Hack, Sebastian Saarland Univ Comp Graph Lab Saarbrucken Germany Bonn Rhein Sieg Univ Inst Visual Comp St Augustin Germany DFKI Agents & Simulated Real Saarbrucken Germany Saarland Univ Compiler Design Lab Saarbrucken Germany

ISBN: (纸本)9781450355247

In order to achieve the highest possible performance, the ray traversal and intersection routines at the core of every high-performance ray tracer are usually hand-coded, heavily optimized, and implemented separately for each hardware platform-even though they share most of their algorithmic core. the results are implementations that heavily mix algorithmic aspects with hardware and implementation details, making the code non-portable and difficult to change and maintain. In this paper, we present a new approach that offers the ability to define in a functional language a set of conceptual, high-level language abstractions that are optimized away by a special compiler in order to maximize performance. Using this abstraction mechanism we separate a generic ray traversal and intersection algorithm from its low-level aspects that are specific to the target hardware. We demonstrate that our code is not only significantly more flexible, simpler to write, and more concise but also that the compiled results perform as well as state-of-the-art implementations on any of the tested CPU and GPU platforms.

关键词： Computer Graphics Ray Tracing Functional programming Domain-Specific languages

来源：评论

学校读者我要写书评

暂无评论

Composable and compilable macros -: You want it when?

Composable and compilable macros -: You want it <i>when</i>?

引用

7th International conference on Functional programming

作者： Flatt, M Univ Utah Salt Lake City UT 84112 USA

Many macro systems, especially for Lisp and Scheme, allow macro transformers to perform general computation. Moreover, the language for implementing compile-time macro transformers is usually the same as the language for implementing run-time functions. As a side effect of this sharing, implementations tend to allow the mingling of compile-time values and rum-time values, as well as values from separate compilations. Such mingling breaks programming tools that must parse code without executing it. Macro implementors avoid harmful mingling by obeying certain macro-definition protocols and by inserting phase-distinguishing annotations into the code. However, the annotations are fragile, the protocols are not enforced, and programmers can only reason about the result in terms of the compiler's implementation. MzScheme-the language of the PLT Scheme tool suite-addresses the problem through a macro system that separates compilation without sacrificing the expressiveness of macros.

关键词： languages design macros modules language tower

来源：评论

学校读者我要写书评

暂无评论

Stateless Model Checking Concurrent Programs with Maximal Causality Reduction 15

Stateless Model Checking Concurrent Programs with Maximal Ca...

引用

36th acm sigplan conference on programming language design and implementation

作者： Huang, Jeff Texas A&M Univ College Stn TX 77843 USA

ISBN: (纸本)9781450334686

We present maximal causality reduction (MCR), a new technique for stateless model checking. MCR systematically explores the state-space of concurrent programs with a provably minimal number of executions. Each execution corresponds to a distinct maximal causal model extracted from a given execution trace, which captures the largest possible set of causally equivalent executions. Moreover, MCR is embarrassingly parallel by shifting the runtime exploration cost to offline analysis. We have designed and implemented MCR using a constraint-based approach and compared with iterative context bounding (ICB) and dynamic partial order reduction (DPOR) on both benchmarks and real-world programs. MCR reduces the number of executions explored by ICB and ICB+DPOR by orders of magnitude, and significantly improves the scalability, efficiency, and effectiveness of the state-of-the-art for both state-space exploration and bug finding. In our experiments, MCR also revealed several new data races and null pointer dereference errors in frequently studied real-world programs.

关键词： Algorithms design theory Maximal Causality Reduction Model Checking

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：