Derivations with Holes for Concept-Based Program Synthesis

João Costa Seco, Jonathan Aldrich, Luís Carvalho, Bernardo Toninho, Carla Ferreira

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Citations (Scopus)

Abstract

Program synthesis has the potential to democratize programming by enabling non-programmers to write software. But conventional approaches to synthesis may fail if given insufficient information - a common occurrence when asking non-experts to describe the application they want to write. This paper introduces a new concept-based program synthesis mechanism that can cope with incomplete knowledge, targeting low-code model-driven languages. Concepts are modelled in an ontology that represents user intent including basic actions (e.g. show, filter, and create) along with their associated data as well as basic user interface structures like screens or pages. Our synthesis framework consists of a system of derivation rules that supports deferred premises, which need not be immediately satisfied during synthesis. A derivation in which some deferred premises are missing will thus contain holes; semantically, it represents a proof that is conditional on the developer filling the holes with additional facts from the ontology. We translate derivations with holes to standard first-order logic derivations, where the holes are transformed into assumptions. We illustrate the feasibility and effectiveness of our framework with a proof-of-concept implementation and a set of illustrative examples.

Original languageEnglish
Title of host publicationOnward! 2022
Subtitle of host publicationProceedings of the 2022 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software
EditorsChristophe Scholliers, Jeremy Singer
Place of PublicationNew York
PublisherACM - Association for Computing Machinery
Pages63-79
Number of pages17
ISBN (Print)978-1-4503-9909-8
DOIs
Publication statusPublished - Nov 2022
Event2022 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software, Onward! 2022. - Auckland, New Zealand
Duration: 8 Dec 202210 Dec 2022

Conference

Conference2022 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software, Onward! 2022.
Country/TerritoryNew Zealand
CityAuckland
Period8/12/2210/12/22

Keywords

  • automated programming
  • incomplete knowledge
  • low-code
  • program synthesis
  • user intent

Fingerprint

Dive into the research topics of 'Derivations with Holes for Concept-Based Program Synthesis'. Together they form a unique fingerprint.

Cite this