Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | 이우석 | - |
dc.date.accessioned | 2023-05-11T11:45:47Z | - |
dc.date.available | 2023-05-11T11:45:47Z | - |
dc.date.issued | 2023-01 | - |
dc.identifier.citation | PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL, v. 7, NO. POPL, | - |
dc.identifier.issn | 2475-1421;2475-1421 | - |
dc.identifier.uri | https://dl.acm.org/doi/10.1145/3571263 | en_US |
dc.identifier.uri | https://repository.hanyang.ac.kr/handle/20.500.11754/179539 | - |
dc.description.abstract | We present a novel approach to synthesizing recursive functional programs from input-output examples. Synthesizing a recursive function is challenging because recursive subexpressions should be constructed while the target function has not been fully defined yet. We address this challenge by using a new technique we call block-based pruning. A block refers to a recursion- and conditional-free expression (i.e., straight-line code) that yields an output from a particular input. We first synthesize as many blocks as possible for each input-output example, and then we explore the space of recursive programs, pruning candidates that are inconsistent with the blocks. Our method is based on an efficient version space learning, thereby effectively dealing with a possibly enormous number of blocks. In addition, we present a method that uses sampled input-output behaviors of library functions to enable a goal-directed search for a recursive program using the library. We have implemented our approach in a system called Trio and evaluated it on synthesis tasks from prior work and on new tasks. Our experiments show that Trio outperforms prior work by synthesizing a solution to 98% of the benchmarks in our benchmark suite. | - |
dc.description.sponsorship | We thank the reviewers for insightful comments. This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. 2020R1C1C1014518, 2021R1A5A1021944) and Institute for Information & Communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. 2021-0-00758, 2022-0-00995). | - |
dc.language | en | - |
dc.publisher | ASSOC COMPUTING MACHINERY | - |
dc.subject | Programming by Example | - |
dc.subject | Recursive Functional Programs | - |
dc.subject | Synthesis | - |
dc.title | Inductive Synthesis of Structurally Recursive Functional Programs from Non-recursive Expressions | - |
dc.type | Article | - |
dc.relation.no | POPL | - |
dc.relation.volume | 7 | - |
dc.identifier.doi | 10.1145/3571263 | - |
dc.relation.journal | PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL | - |
dc.contributor.googleauthor | Lee, Woosuk | - |
dc.contributor.googleauthor | Cho, Hangyeol | - |
dc.sector.campus | E | - |
dc.sector.daehak | 소프트웨어융합대학 | - |
dc.sector.department | 컴퓨터학부 | - |
dc.identifier.pid | woosuk | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.