An official website of the United States government
Programming-by-example (PBE) is a synthesis paradigm that allows users to generate functions by simply providing input-output examples. While a promising interaction paradigm, synthesis is still too slow for realtime interaction and more widespread adoption. Existing approaches to PBE synthesis have used automated reasoning tools, such as SMT solvers, as well as works applying machine learning techniques. At its core, the automated reasoning approach relies on highly domain specific knowledge of programming languages. On the other hand, the machine learning approaches utilize the fact that when working with program code, it is possible to generate arbitrarily large training datasets. In this work, we propose a system for using machine learning in tandem with automated reasoning techniques to solve Syntax Guided Synthesis (SyGuS) style PBE problems. By preprocessing SyGuS PBE problems with a neural network, we can use a data driven approach to reduce the size of the search space, then allow automated reasoning-based solvers to more quickly find a solution analytically. Our system is able to run atop existing SyGuS PBE synthesis tools, decreasing the runtime of the winner of the 2019 SyGuS Competition for the PBE Strings track by 47.65% to outperform all of the competing tools.
more »
« less
Programming-by-example for audio: synthesizing digital signal processing programs
Programming by example allows users to create programs without coding, by simply specifying input and output pairs.We introduce the problem of digital signal processing programming by example (DSP-PBE), where users specify input and output wave files, and a tool automatically synthesizes a program that transforms the input to the output. This program can then be applied to new wave files, giving users a new way to interact with music and program code. We formally define the problem of DSP-PBE, and provide a first implementation of a solution that can handle synthesis over commutative filters.
more »
« less
- PAR ID:
- 10113566
- Date Published:
- Journal Name:
- FARM 2018 Proceedings of the 6th ACM SIGPLAN International Workshop on Functional Art, Music, Modeling, and Design
- Page Range / eLocation ID:
- 18 to 25
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
One vision for program synthesis, and specifically for programming by example (PBE), is an interactive programmer's assistant, integrated into the development environment. To make program synthesis practical for interactive use, prior work on Small-Step Live PBE has proposed to limit the scope of synthesis to small code snippets, and enable the users to provide local specifications for those snippets. This paradigm, however, does not work well in the presence of loops. We present LooPy, a synthesizer integrated into a live programming environment, which extends Small-Step Live PBE to work inside loops and scales it up to synthesize larger code snippets, while remaining fast enough for interactive use. To allow users to effectively provide examples at various loop iterations, even when the loop body is incomplete, LooPy makes use of live execution , a technique that leverages the programmer as an oracle to step over incomplete parts of the loop. To enable synthesis of loop bodies at interactive speeds, LooPy introduces Intermediate State Graph , a new data structure, which compactly represents a large space of code snippets composed of multiple assignment statements and conditionals. We evaluate LooPy empirically using benchmarks from competitive programming and previous synthesizers, and show that it can solve a wide variety of synthesis tasks at interactive speeds. We also perform a small qualitative user study which shows that LooPy's block-level specifications are easy for programmers to provide.more » « less
-
Block-based programming environments, such as Scratch and Snap!, engage users to create programming artifacts such as games and stories, and share them in an online community. Many Snap! users start programming by reusing and modifying an example project, but encounter many barriers when searching and identifying the relevant parts of the program to learn and reuse. We present Pinpoint, a system that helps Snap! programmers understand and reuse an existing program by isolating the code responsible for specific events during program execution. Specifically, a user can record an execution of the program (including user inputs and graphical output), replay the output, and select a specific time interval where the event of interest occurred, to view code that is relevant to this event. We conducted a small-scale user study to compare users’ program comprehension experience with and without Pinpoint, and found suggestive evidence that Pinpoint helps users understand and reuse a complex program more efficiently.more » « less
-
Many computational tasks can be naturally expressed as a composition of a DNN followed by a program written in a traditional programming language or an API call to an LLM. We call such composites "neural programs" and focus on the problem of learning the DNN parameters when the training data consist of end-to-end input-output labels for the composite. When the program is written in a differentiable logic programming language, techniques from neurosymbolic learning are applicable, but in general, the learning for neural programs requires estimating the gradients of black-box components. We present an algorithm for learning neural programs, called ISED, that only relies on input-output samples of black-box components. For evaluation, we introduce new benchmarks that involve calls to modern LLMs such as GPT-4 and also consider benchmarks from the neurosymbolic learning literature. Our evaluation shows that for the latter benchmarks, ISED has comparable performance to state-of-the-art neurosymbolic frameworks. For the former, we use adaptations of prior work on gradient approximations of black-box components as a baseline, and show that ISED achieves comparable accuracy but in a more data- and sample-efficient manner.more » « less
-
This archive contains COAWST model input, grids and initial conditions, and output used to produce the results in a submitted manuscript. The files are:</p> model_input.zip: input files for simulations presented in this paper ocean_rip_current.in: ROMS ocean model input file swan_rip_current.in: SWAN wave model input file (example with Hs=1m) coupling_rip_current.in: model coupling file rip_current.h: model header file model_grids_forcing.zip: bathymetry and initial condition files hbeach_grid_isbathy_2m.nc: ROMS bathymetry input file hbeach_grid_isbathy_2m.bot: SWAN bathymetry input file hbeach_grid_isbathy_2m.grd: SWAN grid input file hbeach_init_isbathy_14_18_17.nc: Initial temperature, cool surf zone dT=-1C case hbeach_init_isbathy_14_18_19.nc: Initial temperature, warm surf zone dT=+1C case hbeach_init_isbathy_14_18_16.nc: Initial temperature, cool surf zone dT=-2C case hbeach_init_isbathy_14_18_20.nc: Initial temperature, warm surf zone dT=+2C case hbeach_init_isbathy_14_18_17p5.nc: Initial temperature, cool surf zone dT=-0.5C case hbeach_init_isbathy_14_18_18p5.nc: Initial temperature, warm surf zone dT=+0.5C case</p> model_output files: model output used to produce the figures netcdf files, zipped variables included: x_rho (cross-shore coordinate, m) y_rho (alongshore coordinate, m) z_rho (vertical coordinate, m) ocean_time (time since initialization, s, output every 5 mins) h (bathymetry, m) temp (temperature, Celsius) dye_02 (surfzone-released dye) Hwave (wave height, m) Dissip_break (wave dissipation W/m2) ubar (cross-shore depth-average velocity, m/s, interpolated to rho-points) Case_141817.nc: cool surf zone dT=-1C Hs=1m Case_141819.nc: warm surf zone dT=+1C Hs=1m Case_141816.nc: cool surf zone dT=-2C Hs=1m Case_141820.nc: warm surf zone dT=-2C Hs=1m Case_141817p5.nc: cool surf zone dT=-0.5C Hs=1m Case_141818p5.nc: warm surf zone dT=+0.5C Hs=1m Case_141817_Hp5.nc: cool surf zone dT=-1C Hs=0.5m Case_141819_Hp5.nc: warm surf zone dT=+1C Hs=0.5m Case_141817_Hp75.nc: cool surf zone dT=-1C Hs=0.75m Case_141819_Hp75.nc: warm surf zone dT=+1C Hs=0.75m</p> COAWST is an open source code and can be download at https://coawstmodel-trac.sourcerepo.com/coawstmodel_COAWST/. Descriptions of the input and output files can be found in the manual distributed with the model code and in the glossary at the end of the ocean.in file.</p> Corresponding author: Melissa Moulton, mmoulton@uw.edu</p>more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Conference Paper:
- https://doi.org/10.1145/3242903.3242906
