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

Combining the Top-Down Propagation and Bottom-Up Enumeration for Inductive Program Synthesis

PROCEEDINGS OF THE ACM ON programming LANGUAGES-PACMPL 2021年第POPL期5卷 1–28页

作者： Lee, Woosuk Hanyang Univ Coll Comp Seoul South Korea

We present an effective method for scalable and general-purpose inductive program synthesis. There have been two main approaches for inductive synthesis: enumerative search, which repeatedly enumerates possible candidate programs, and the top-down propagation (TDP), which recursively decomposes a given large synthesis problem into smaller subproblems. Enumerative search is generally applicable but limited in scalability, and the TDP is efficient but only works for special grammars or applications. In this paper, we synergistically combine the two approaches. We generate small program subexpressions via enumerative search and put them together into the desired program by using the TDP. Enumerative search enables to bring the power of TDP into arbitrary grammars, and the TDP helps to overcome the limited scalability of enumerative search. We apply our approach to a standard formulation, syntax-guided synthesis (SyGuS), thereby supporting a broad class of inductive synthesis problems. We have implemented our approach in a tool called Duet and evaluate it on SyGuS benchmark problems from various domains. We show that Duet achieves significant performance gains over existing general-purpose as well as domain-specific synthesizers.

关键词： programming by example Syntax-guided Synthesis

来源：评论

学校读者我要写书评

暂无评论

Mobius: Synthesizing Relational Queries with Recursive and Invented Predicates

引用

PROCEEDINGS OF THE ACM ON programming LANGUAGES-PACMPL 2023年第OOPSLA期7卷 1394–1417页

作者： Thakkar, Aalok Sands, Nathaniel Petrou, George Alur, Rajeev Naik, Mayur Raghothaman, Mukund Univ Penn Philadelphia PA 19104 USA Univ Southern Calif Los Angeles CA USA

Synthesizing relational queries from data is challenging in the presence of recursion and invented predicates. We propose a fully automated approach to synthesize such queries. Our approach comprises of two steps: it first synthesizes a non-recursive query consistent with the given data, and then identifies recursion schemes in it and thereby generalizes to arbitrary data. This generalization is achieved by an iterative predicate unification procedure which exploits the notion of data provenance to accelerate convergence. In each iteration of the procedure, a constraint solver proposes a candidate query, and a query evaluator checks if the proposed program is consistent with the given data. The data provenance for a failed query allows us to construct additional constraints for the constraint solver and refine the search. We have implemented our approach in a tool named MOBIUS. On a suite of 21 challenging recursive query synthesis tasks, MOBIUS outperforms three state-of-the-art baselines GENSYNTH, ILASP, and POPPER, both in terms of runtime and accuracy. We also demonstrate that the synthesized queries generalize well to unseen data.

关键词： programming by example example-guided synthesis recursive program synthesis

来源：评论

学校读者我要写书评

暂无评论

Repairing Regular Expressions for Extraction

引用

PROCEEDINGS OF THE ACM ON programming LANGUAGES-PACMPL 2023年第PLDI期7卷 1633-1656页

作者： Chida, Nariyoshi Terauchi, Tachio Waseda Univ NTT Social Informat Labs Tokyo Japan Waseda Univ Tokyo Japan

While synthesizing and repairing regular expressions (regexes) based on programming-by-examples (PBE) methods have seen rapid progress in recent years, all existing works only support synthesizing or repairing regexes for membership testing, and the support for extraction is still an open problem. This paper fills the void by proposing the first PBE-based method for synthesizing and repairing regexes for extraction. Our work supports regexes that have real-world extensions such as backreferences and lookarounds. The extensions significantly affect the PBE-based synthesis and repair problem. In fact, we show that there are unsolvable instances of the problem if the synthesized regexes are not allowed to use the extensions, i.e., there is no regex without the extensions that correctly classify the given set of examples, whereas every problem instance is solvable if the extensions are allowed. This is in stark contrast to the case for the membership where every instance is guaranteed to have a solution expressible by a pure regex without the extensions. The main contribution of the paper is an algorithm to solve the PBE-based synthesis and repair problem for extraction. Our algorithm builds on existing methods for synthesizing and repairing regexes for membership testing, i.e., the enumerative search algorithms with SMT constraint solving. However, significant extensions are needed because the SMT constraints in the previous works are based on a non-deterministic semantics of regexes. Non-deterministic semantics is sound for membership but not for extraction, because which substrings are extracted depends on the deterministic behavior of actual regex engines. To address the issue, we propose a new SMT constraint generation method that respects the deterministic behavior of regex engines. For this, we first define a novel formal semantics of an actual regex engine as a deterministic big-step operational semantics, and use it as a basis to design the new SMT constraint g

关键词： Regular Expression programming by example Program Repair

来源：评论

学校读者我要写书评

暂无评论

Empowering Children To Rapidly Author Games and Animations Without Writing Code 16

Empowering Children To Rapidly Author Games and Animations W...

引用

15th International ACM Conference on Interaction Design and Children (IDC)

作者： Banerjee, Rahul Yip, Jason Lee, Kung Jin Popovic, Zoran Univ Washington Ctr Game Sci Comp Sci & Engn Seattle WA 98195 USA Univ Washington Informat Sch Seattle WA 98195 USA

ISBN: (纸本)9781450343138

Prior research has established that long-term interests in programming are often shaped by formative computing experiences, especially those involving programming and graphics. Existing authoring environments for children (ages 9-14) to make 2D games and animations require them to: (a) create programs, (b) customize templates, or (c) combine rewrite rules with programs. One way to support early experiences in computing for a more diverse set of learners is to simplify such authoring systems, by removing text heavy code and minimizing cognitive load, which can allow separation of coding concepts from writing code. In this paper, we describe an exploratory system we are designing to test this idea, called BlockStudio. Using a programming by example paradigm, children manipulate colored blocks on the screen to specify desired behavior via concrete changes. Based on these inputs, our system synthesizes generalized rules based on color. We give a brief overview of our current prototype, then share insights gleaned from two intergenerational co-design sessions with children and discuss implications for designers of similar systems.

关键词： Authoring games interactive content programming by example rule-based system user interface

来源：评论

学校读者我要写书评

暂无评论

End-User programming Architecture for Physical Movement Assessment: An Interactive Machine Learning Approach 11th

End-User Programming Architecture for Physical Movement Asse...

引用

11th International Conference on Digital Human Modeling and Applications in Health, Safety, Ergonomics and Risk Management (DHM) Held as Part of the 22nd International Conference on Human-Computer Interaction (HCII)

作者： Palomares-Pecho, Jessica M. Silva-Calpa, Greis Francy M. Sierra-Franco, Cesar A. Raposo, Alberto Barbosa Pontifical Catholic Univ Rio de Janeiro PUC Rio Dept Informat BR-22451900 Gavea RJ Brazil Pontifical Catholic Univ Rio de Janeiro PUC Rio Tecgraf Inst BR-22451900 Gavea RJ Brazil

ISBN: (纸本)9783030499037;9783030499044

In this article, we propose an end-user adaptive architecture for movement assessment from RGB videos. Our method allows physiotherapists to add customized exercises for patients from only a few video training examples. The main idea is to take leverage of Deep learning-based pose estimation frameworks to track in real-time the key-body joints from the image data. Our system mimics the traditional physical rehabilitation process, where the therapist guides patients through demonstrative examples, and the patients repeat these examples while the physiotherapist monitors their movements. We evaluate our proposed method on four physiotherapeutic exercises for shoulder strengthening. Results indicate that our approach contributes both to reduce physiotherapist time needed to train the system, and to automatically assess the patients' movements without direct monitoring from the physiotherapist.

关键词： Interactive Machine learning OpenPose programming by example Rehabilitation Human activity recognition

来源：评论

学校读者我要写书评

暂无评论

Synthesizing Regular Expressions from examples for Introductory Automata Assignments 2016

Synthesizing Regular Expressions from Examples for Introduct...

引用

15th ACM International Conference on Generative programming - Concepts and Experiences (GPCE)

作者： Lee, Mina So, Sunbeom Oh, Hakjoo Korea Univ Seoul South Korea

ISBN: (纸本)9781450344463

We present a method for synthesizing regular expressions for introductory automata assignments. Given a set of positive and negative examples, the method automatically synthesizes the simplest possible regular expression that accepts all the positive examples while rejecting all the negative examples. The key novelty is the search-based synthesis algorithm that leverages ideas from over- and under-approximations to effectively prune out a large search space. We have implemented our technique in a tool and evaluated it with non-trivial benchmark problems that students often struggle with. The results show that our system can synthesize desired regular expressions in 6.7 seconds on the average, so that it can be interactively used by students to enhance their understanding of regular expressions.

关键词： Regular expression program synthesis programming by example

来源：评论

学校读者我要写书评

暂无评论

Component-Based Synthesis of Table Consolidation and Transformation Tasks from examples 2017

Component-Based Synthesis of Table Consolidation and Transfo...

引用

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

来源：评论

学校读者我要写书评

暂无评论

Attaching UI Enhancements to Websites with End Users 09

Attaching UI Enhancements to Websites with End Users

引用

27th Annual CHI Conference on Human Factors in Computing Systems

作者： Toomim, Michael Drucker, Steven M. Dontcheva, Mira Rahimi, Ali Thomson, Blake Landay, James A. Univ Washington DUB Grp Seattle WA 98195 USA

ISBN: (纸本)9781605582467

We present reform, a step toward write-once apply-anywhere user interface enhancements. The reform system envisions roles for both programmers and end users in enhancing existing websites to support new goals. First, a programmer authors a traditional masbup or browser extension, but they do not write a web scraper. Instead they use reform, which allows novice end users to attach the enhancement to their favorite sites with a scraping by-example interface. reform makes enhancements easier to program while also carrying the benefit that end users can apply the enhancements to any number of new websites. We present reform's architecture, user interface, interactive by-example extraction algorithm for novices, and evaluation, along with five example reform enabled enhancements.

关键词： web data extraction mashups programming by example end-user programming

来源：评论

学校读者我要写书评

暂无评论

Repairing Regex-Dependent String Functions 24

Repairing Regex-Dependent String Functions

引用

39th ACM/IEEE International Conference on Automated Software Engineering (ASE)

作者： Chida, Nariyoshi Terauchi, Tachio NTT Social Informat Labs Tokyo Japan Waseda Univ Tokyo Japan

ISBN: (数字)9798400712487

ISBN: (纸本)9798400712487

Regex-dependent string functions are string functions that take regular expressions (regexes) as parameters and are popular means of manipulating strings. They are frequently used for, e.g., string transformation and substring search. Despite the importance, writing these functions is far from easy. To rectify this situation, recent research made significant progress by proposing automated methods for synthesizing regexes based on programming by examples (PBE). However, there still is a gap between these methods and the goal of synthesizing regex-dependent string functions. First, the existing methods focus on whole-string matching, whereas most regex-dependent string functions adopt substring matching. Second, the existing methods focus only on the regex, but many commonly used regex-dependent string functions, such as replace and replaceAll, also take as parameter a replacement to specify how the substrings matched to the regex will be replaced. This paper fills the gap by presenting the first PBE-based method for repairing regex-dependent string functions. Like the recent methods for regex synthesis, our algorithm builds on enumerative search with pruning and SMT constraint solving, but with extensions to support substring matching and replacement. The main challenge is the large search space. We address the challenge by novel ideas such as incorporation of origin information in examples to identify the locations of substrings to be matched, a new substring-context-aware pruning technique, and a novel use of SMT constraints to insert captures that can be referred from the replacement. Additionally, we identify a novel necessary and sufficient condition that can be used to detect and filter unrepairable instances. We implemented our algorithm as a prototype tool called R2-DS and evaluated it on real-world benchmarks. Results show that our algorithm efficiently repairs the bugs in the real world and finds high-quality repairs.

关键词： Regular Expression programming by example Program Repair

来源：评论

学校读者我要写书评

暂无评论

Categories and Completeness of Visual programming and Direct Manipulation 20

Categories and Completeness of Visual Programming and Direct...

引用

Working Conference on Advanced Visual Interfaces (AVI)

作者： McGuffin, Michael J. Fuhrman, Christopher P. Ecole Technol Super Montreal PQ Canada

ISBN: (纸本)9781450375351

Recent innovations in visual programming and the use of direct manipulation for programming have demonstrated promise, but also raise questions about how far these approaches can be generalized. To clarify these issues, we present a categorization of systems for visual programming, programming-by-example, and similar systems. By examining each category, we elucidate the advantages, limitations, and ways to extend systems in each category. Our work makes it easier for researchers and designers to understand how visual programming languages (VPLs) and similar systems relate to each other, and how to extend them. We also indicate directions for future research.

关键词： visual programming languages direct manipulation programming by example output-directed programming taxonomy programming by demonstration

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：