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

2nd Genetic and Evolutionary Computation Conference (GECCO)

作者： Tenenbaum, Joshua MIT 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9781450383509

None of today's AI systems or approaches comes anywhere close to capturing the common sense of a toddler, or even a 3-month old infant. I will talk about some of the challenges facing conventional machine learning paradigms, such as end-to-end unsupervised learning in deep networks and deep reinforcement learning, and discuss some initial, small steps we have taken with an alternative cognitively-inspired AI approach. This requires us to develop a different engineering toolset, based on probabilistic programs, game-style simulation programs as general-purpose startup software (or "the game engine in the head"), and learning as programming (or "the child as hacker").

关键词： Artificial intelligence probabilistic programs simulation engines inductive program synthesis

来源：评论

学校读者我要写书评

暂无评论

On the Difficulty of Benchmarking inductive program synthesis Methods 17

On the Difficulty of Benchmarking Inductive Program Synthesi...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Pantridge, Edward Helmuth, Thomas McPhee, Nicholas Freitag Spector, Lee MassMutual Financial Grp Amherst MA 01111 USA Washington & Lee Univ Lexington VA 24450 USA Univ Minnesota Morris MN 56267 USA Hampshire Coll Amherst MA 01002 USA

ISBN: (纸本)9781450349390

A variety of inductive program synthesis (IPS) techniques have recently been developed, emerging from different areas of computer science. However, these techniques have not been adequately compared on general program synthesis problems. In this paper we compare several methods on problems requiring solution programs to handle various data types, control structures, and numbers of outputs. The problem set also spans levels of abstraction;some would ordinarily be approached using machine code or assembly language, while others would ordinarily be approached using high-level languages. The presented comparisons are focused on the possibility of success;that is, on whether the system can produce a program that passes all tests, for all training and unseen testing inputs. The compared systems are Flash Fill, MagicHaskeller, TerpreT, and two forms of genetic programming. The two genetic programming methods chosen were PushGP and Grammar Guided Genetic programming. The results suggest that PushGP and, to an extent, TerpreT and Grammar Guided Genetic programming are more capable of finding solutions than the others, albeit at a higher computational cost. A more salient observation is the difficulty of comparing these methods due to drastically different intended applications, despite the common goal of program synthesis.

关键词： Genetic programming Machine Learning inductive program synthesis Benchmarking

来源：评论

学校读者我要写书评

暂无评论

FlashMeta: A Framework for inductive program synthesis 2015

FlashMeta: A Framework for Inductive Program Synthesis

引用

ACM SIGPLAN International Conference on Object-Oriented programming, Systems, Languages, and Applications (OOPSLA)

作者： Polozov, Oleksandr Gulwani, Sumit Univ Washington Seattle WA 98195 USA Microsoft Res Redmond WA USA

ISBN: (纸本)9781450336895

inductive synthesis, or programming-by-examples (PBE) is gaining prominence with disruptive applications for automating repetitive tasks in end-user programming. However, designing, developing, and maintaining an effective industrial-quality inductive synthesizer is an intellectual and engineering challenge, requiring 1-2 man-years of effort. Our novel observation is that many PBE algorithms are a natural fall-out of one generic meta-algorithm and the domain-specific properties of the operators in the underlying domain-specific language (DSL). The meta-algorithm propagates example-based constraints on an expression to its subexpressions by leveraging associated witness functions, which essentially capture the inverse semantics of the underlying operator. This observation enables a novel program synthesis methodology called data-driven domain-specific deduction (D-4), where domain-specific insight, provided by the DSL designer, is separated from the synthesis algorithm. Our FlashMeta framework implements this methodology, allowing synthesizer developers to generate an efficient synthesizer from the mere DSL definition (if properties of the DSL operators have been modeled). In our case studies, we found that 10+ existing industrial-quality mass-market applications based on PBE can be cast as instances of D-4. Our evaluation includes reimplementation of some prior works, which in FlashMeta become more efficient, maintainable, and extensible. As a result, FlashMeta-based PBE tools are deployed in several industrial products, including Microsoft PowerShell 3.0 for Windows 10, Azure Operational Management Suite, and Microsoft Cortana digital assistant.

关键词： Algorithms Languages inductive program synthesis programming by examples frameworks domain-specific languages deductive inference search-based synthesis

来源：评论

学校读者我要写书评

暂无评论

FlashMeta: A Framework for inductive program synthesis

引用

ACM SIGPLAN NOTICES 2015年第10期50卷 107-126页

作者： Polozov, Oleksandr Gulwani, Sumit Univ Washington Seattle WA 98195 USA Microsoft Res Redmond WA USA

关键词： Algorithms Languages inductive program synthesis programming by examples frameworks domain-specific languages deductive inference search-based synthesis

来源：评论

学校读者我要写书评

暂无评论

Decomposition-based synthesis for Applying Divide-and-Conquer-like Algorithmic Paradigms

引用

ACM TRANSACTIONS ON programMING LANGUAGES AND SYSTEMS 2024年第2期46卷 1-59页

作者： Ji, Ruyi Zhao, Yuwei Xiong, Yingfei Wang, Di Zhang, Lu Hu, Zhenjiang Peking Univ Sch Comp Sci Dept Comp Sci & Technol Minist EducKey Lab High Confidence Software Tech Beijing Peoples R China

Algorithmic paradigms such as divide-and-conquer (D&C) are proposed to guide developers in designing efficient algorithms, but it can still be difficult to apply algorithmic paradigms to practical tasks. To ease the usage of paradigms, many research efforts have been devoted to the automatic application of algorithmic paradigms. However, most existing approaches to this problem rely on syntax-based program transformations and thus put significant restrictions on the original program. In this article, we study the automatic application of D&C and several similar paradigms, denoted as D&C-like algorithmic paradigms, and aim to remove the restrictions from syntax-based transformations. To achieve this goal, we propose an efficient synthesizer, named AutoLifter, which does not depend on syntax-based transformations. Specifically, the main challenge of applying algorithmic paradigms is from the large scale of the synthesized programs, and AutoLifter addresses this challenge by applying two novel decomposition methods that do not depend on the syntax of the input program, component elimination and variable elimination, to soundly divide the whole problem into simpler subtasks, each synthesizing a sub-program of the final program and being tractable with existing synthesizers. We evaluate AutoLifter on 96 programming tasks related to six different algorithmic paradigms. AutoLifter solves 82/96 tasks with an average time cost of 20.17 s, significantly outperforming existing approaches.

关键词： inductive program synthesis algorithm synthesis decomposition methods for program synthesis tasks

来源：评论

学校读者我要写书评

暂无评论

inductive synthesis of inductive Heap Predicates

引用

PROCEEDINGS OF THE ACM ON programMING LANGUAGES-PACMPL 2025年第OOPSLA1期9卷 169-195页

作者： Yang, Ziyi Sergey, Ilya Natl Univ Singapore Singapore Singapore

We present an approach to automatically synthesise recursive predicates in Separation Logic (SL) from concrete data structure instances using inductive Logic programming (ILP) techniques. The main challenges to make such synthesis effective are (1) making it work without negative examples that are required in ILP but are difficult to construct for heap-based structures in an automated fashion, and (2) to be capable of summarising not just the shape of a heap (e.g., it is a linked list), but also the properties of the data it stores (e.g., it is a sorted linked list). We tackle these challenges with a new predicate learning algorithm. The key contributions of our work are (a) the formulation of ILP-based learning only using positive examples and (b) an algorithm that synthesises property-rich SL predicates from concrete memory graphs based on the positive-only learning. We show that our framework can efficiently and correctly synthesise SL predicates for structures that were beyond the reach of the state-of-the-art tools, including those featuring non-trivial payload constraints (e.g., binary search trees) and nested recursion (e.g., n-ary trees). We further extend the usability of our approach by a memory graph generator that produces positive heap examples from programs. Finally, we show how our approach facilitates deductive verification and synthesis of correct-by-construction code.

关键词： inductive program synthesis answer set programming Separation Logic

来源：评论

学校读者我要写书评

暂无评论

Superfusion: Eliminating Intermediate Data Structures via inductive synthesis

引用

PROCEEDINGS OF THE ACM ON programMING LANGUAGES-PACMPL 2024年第PLDI期8卷 939-964页

作者： Ji, Ruyi Zhao, Yuwei Polikarpova, Nadia Xiong, Yingfei Hu, Zhenjiang Peking Univ Sch Comp Sci Beijing Peoples R China Univ Calif San Diego San Diego CA 92103 USA Minist Educ Key Lab High Confidence Software Technol Beijing Peoples R China

Intermediate data structures are a common cause of inefficiency in functional programming. Fusion attempts to eliminate intermediate data structures by combining adjacent data traversals into one;existing fusion techniques, however, are based on predefined rewrite rules and hence are limited in expressiveness. In this work we explore a different approach to eliminating intermediate data structures, based on inductive program synthesis. We dub this approach superfusion (by analogy with superoptimization, which uses inductive synthesis for program optimization). Starting from a reference program annotated with data structures to be eliminated, superfusion first generates a sketch where program fragments operating on those data structures are replaced with holes;it then fills the holes with constant-time expressions such that the resulting program is equivalent to the reference. The main technical challenge here is scalability because optimized programs are often complex, making the search space intractably large for naive enumeration. To address this challenge, our key insight is to first synthesize a ghost function that describes the relationship between the original intermediate data structure and its compressed version;this function, although not used in the final program, serves to decompose the joint sketch filling problem into independent simpler problems for each hole. We implement superfusion in a tool called SuFu and evaluate it on a dataset of 290 tasks collected from prior work on deductive fusion and program restructuring. The results show that SuFu solves 264 out of 290 tasks, exceeding the capabilities of rewriting-based fusion systems and achieving comparable performance with specialized approaches to program restructuring on their respective domains.

关键词： inductive program synthesis program Optimization Fusion

来源：评论

学校读者我要写书评

暂无评论

Facilitating Function Application in Code Building Genetic programming

Facilitating Function Application in Code Building Genetic P...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Helmuth, Thomas Fedoroff, Jayden Pantridge, Edward Spector, Lee Hamilton Coll Clinton NY 13323 USA Spindle Hlth Boston MA USA UMass Amherst Amherst Coll Amherst MA USA

ISBN: (纸本)9798400704949

Code Building Genetic programming (CBGP) is a method for general inductive program synthesis that uses a genetic algorithm and a formal type system to evolve linear genomes that are compiled into type-safe programs in a host language. Prior work showed that CBGP can evolve programs that use arbitrary abstractions from existing codebases along with higher-order functions and polymorphism. In tests on benchmark problems, however, the problem solving capabilities of CBGP have been mixed. One hypothesized explanation for weak performance on some problems is that many functions encountered during the compilation process are typically not applied. Here we propose two modifications to the compilation algorithm, both of which make it more likely that functions will be applied when composing programs. The first modification changes how frequently CBGP attempts to perform function application, while the second allows the construction of function applications to backtrack. While both modifications increase solution rates on benchmark problems, the backtracking modification shows more promise with a modest increase in computational cost and no additional configuration requirements. We argue that this modification should be considered the new standard compilation algorithm for CBGP systems.

关键词： automatic programming genetic programming inductive program synthesis function application

来源：评论

学校读者我要写书评

暂无评论

Solving Novel program synthesis Problems with Genetic programming using Parametric Polymorphism 23

Solving Novel Program Synthesis Problems with Genetic Progra...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Pantridge, Edward Helmuth, Thomas Swoop Cambridge MA 02140 USA Hamilton Coll Clinton NY USA

ISBN: (纸本)9798400701191

Contemporary genetic programming (GP) systems for general program synthesis have been primarily concerned with evolving programs that can manipulate values from a standard set of primitive data types and simple indexed data structures. In contrast, human programmers do not limit themselves to a small finite set of data types and use polymorphism to express an unbounded number of types including nested data structures, product types, and generic functions. Code-building Genetic programming (CBGP) is a recently introduced method that compiles type-safe programs from linear genomes using stack-based compilation and a formal type system. Although prior work with CBGP has shown initial demonstrations of polymorphism inside evolved programs, we have provided a deeper exploration of these capabilities through the evolution of programs which make use of generic data types such as key-value maps, tuples, and sets, as well as higher order functions and functions with polymorphic type signatures. In our experiments, CBGP is able to solve problems with all of these properties, where every other GP system that we know of has restrictions that make it unable to even consider problems with these properties. This demonstration provides a significant step towards fully aligning the expressiveness of GP to real world programming.

关键词： automatic programming genetic programming inductive program synthesis polymorphism

来源：评论

学校读者我要写书评

暂无评论

HOTGP- Higher-Order Typed Genetic programming 23

HOTGP- Higher-Order Typed Genetic Programming

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Fernandes, Matheus Campos de Franca, Fabricio Olivetti Francesquini, Emilio Fed Univ ABC UFABC Santo Andre SP Brazil

ISBN: (纸本)9798400701191

program synthesis is the process of generating a computer program following a set of specifications, which can be a high-level description of the problem and/or a set of input-output examples. The synthesis can be modeled as a search problem in which the search space is the set of all the programs valid under a grammar. As the search space is vast, brute force is usually not viable and search heuristics, such as genetic programming, also have difficulty navigating it without any guidance. In this paper we present HOTGP, a new genetic programming algorithm that synthesizes pure, typed, and functional programs. HOTGP leverages the knowledge provided by the rich data-types associated with the specification and the built-in grammar to constrain the search space and improve the performance of the synthesis. The grammar is based on Haskell's standard base library (the synthesized code can be directly compiled using any standard Haskell compiler) and includes support for higher-order functions,..-functions, and parametric polymorphism. Experimental results show that, when compared to 6 stateof-the-art algorithms using a standard set of benchmarks, HOTGP is competitive and capable of synthesizing the correct programs more frequently than any other of the evaluated algorithms.

关键词： inductive program synthesis Genetic programming Functional programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：