Reference. Program Sketching by Automatically Generating Mocks from Tests

Sketch is a popular program synthesis tool that solves for unknowns in a sketch or partial program. However, while Sketch is powerful, it does not directly support modular synthesis of dependencies, potentially limiting scalability. In this paper, we introduce Sketcham, a new technique that modularizes a regular sketch by automatically generating mocks —functions that approximate the behavior of complete implementations—from the sketch’s test suite. For example, if the function f originally calls g , Sketcham creates a mock 𝑔𝑚 from g ’s tests and augments the sketch with a version of f that calls 𝑔𝑚 . This change allows the unknowns in f and g to be solved separately, enabling modular synthesis with no extra work from the Sketch user. We evaluated Sketcham on ten benchmarks, performing enough runs to show at a 95% confidence level that Sketcham improves median synthesis performance on six of our ten benchmarks by a factor of up to 5× compared to plain Sketch, including one benchmark that times out on Sketch, while exhibiting similar performance on the remaining four. Our results show that Sketcham can achieve modular synthesis by automatically generating mocks from tests.

Cite

Cite as @bragg-2021-program (helia, typst) · \cite{bragg-2021-program} (LaTeX)
BibTeX
bibtex · 1 line
@inbook{bragg-2021-program, title={Program Sketching by Automatically Generating Mocks from Tests}, ISBN={9783030816858}, ISSN={1611-3349}, url={http://dx.doi.org/10.1007/978-3-030-81685-8_38}, DOI={10.1007/978-3-030-81685-8_38}, booktitle={Computer Aided Verification}, publisher={Springer International Publishing}, author={Bragg, Nate F. F. and Foster, Jeffrey S. and Roux, Cody and Solar-Lezama, Armando}, year={2021}, pages={808–831} }
hayagriva YAML (typst)
yaml · 19 lines
bragg-2021-program:
  type: chapter
  title: Program Sketching by Automatically Generating Mocks from Tests
  author:
  - Bragg, Nate F. F.
  - Foster, Jeffrey S.
  - Roux, Cody
  - Solar-Lezama, Armando
  date: 2021
  page-range: 808-831
  url: http://dx.doi.org/10.1007/978-3-030-81685-8_38
  serial-number:
    doi: 10.1007/978-3-030-81685-8_38
    isbn: '9783030816858'
    issn: 1611-3349
  parent:
    type: book
    title: Computer Aided Verification
    publisher: Springer International Publishing
Cites 31 works (0 here)
External (31)
bragg-2021-program reference entries/refs/bragg-2021-program/bragg-2021-program.hel