Program Synthesis Using Example Propagation

Niek Mulleners; Johan Jeuring; Bastiaan Heeren

doi:10.1007/978-3-031-24841-2_2

Program Synthesis Using Example Propagation

Niek Mulleners, Johan Jeuring, Bastiaan Heeren

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

We present Scrybe, an example-based synthesis tool for a statically-typed functional programming language, which combines top-down deductive reasoning in the style of $$\lambda ^2$$ with Smyth-style live bidirectional evaluation. During synthesis, example constraints are propagated through sketches to prune and guide the search. This enables Scrybe to make more effective use of functions provided in the context. To evaluate our tool, it is run on the combined, largely disjoint, benchmarks of $$\lambda ^2$$ and Myth. Scrybe is able to synthesize most of the combined benchmark tasks.

Original language	English
Title of host publication	Practical Aspects of Declarative Languages - 25th International Symposium, PADL 2023, Proceedings
Subtitle of host publication	25th International Symposium, PADL 2023, Boston, MA, USA, January 16–17, 2023, Proceedings
Editors	Michael Hanus, Daniela Inclezan
Place of Publication	Cham
Publisher	Springer
Pages	20-36
Number of pages	17
Edition	1
ISBN (Electronic)	978-3-031-24841-2
ISBN (Print)	978-3-031-24841-2, 978-3-031-24840-5
DOIs	https://doi.org/10.1007/978-3-031-24841-2_2
Publication status	Published - 8 Jan 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13880 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Keywords

Program synthesis
Constraint propagation
Input-Output examples
Functional programming

Access to Document

10.1007/978-3-031-24841-2_2

978-3-031-24841-2_2Final published version, 482 KBLicence: Taverne

Cite this

Mulleners, N., Jeuring, J., & Heeren, B. (2023). Program Synthesis Using Example Propagation. In M. Hanus, & D. Inclezan (Eds.), Practical Aspects of Declarative Languages - 25th International Symposium, PADL 2023, Proceedings: 25th International Symposium, PADL 2023, Boston, MA, USA, January 16–17, 2023, Proceedings (1 ed., pp. 20-36). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13880 LNCS). Springer. https://doi.org/10.1007/978-3-031-24841-2_2

Mulleners, Niek ; Jeuring, Johan ; Heeren, Bastiaan. / Program Synthesis Using Example Propagation. Practical Aspects of Declarative Languages - 25th International Symposium, PADL 2023, Proceedings: 25th International Symposium, PADL 2023, Boston, MA, USA, January 16–17, 2023, Proceedings. editor / Michael Hanus ; Daniela Inclezan. 1. ed. Cham : Springer, 2023. pp. 20-36 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1d8e0b7f0f1849949679838c4f993439,

title = "Program Synthesis Using Example Propagation",

abstract = "We present Scrybe, an example-based synthesis tool for a statically-typed functional programming language, which combines top-down deductive reasoning in the style of $$\lambda ^2$$ with Smyth-style live bidirectional evaluation. During synthesis, example constraints are propagated through sketches to prune and guide the search. This enables Scrybe to make more effective use of functions provided in the context. To evaluate our tool, it is run on the combined, largely disjoint, benchmarks of $$\lambda ^2$$ and Myth. Scrybe is able to synthesize most of the combined benchmark tasks.",

keywords = "Program synthesis, Constraint propagation, Input-Output examples, Functional programming",

author = "Niek Mulleners and Johan Jeuring and Bastiaan Heeren",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.",

year = "2023",

month = jan,

day = "8",

doi = "10.1007/978-3-031-24841-2_2",

language = "English",

isbn = "978-3-031-24841-2",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "20--36",

editor = "Michael Hanus and Daniela Inclezan",

booktitle = "Practical Aspects of Declarative Languages - 25th International Symposium, PADL 2023, Proceedings",

address = "Germany",

edition = "1",

}

Mulleners, N , Jeuring, J & Heeren, B 2023, Program Synthesis Using Example Propagation. in M Hanus & D Inclezan (eds), Practical Aspects of Declarative Languages - 25th International Symposium, PADL 2023, Proceedings: 25th International Symposium, PADL 2023, Boston, MA, USA, January 16–17, 2023, Proceedings. 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13880 LNCS, Springer, Cham, pp. 20-36. https://doi.org/10.1007/978-3-031-24841-2_2

Program Synthesis Using Example Propagation. / Mulleners, Niek ; Jeuring, Johan ; Heeren, Bastiaan.
Practical Aspects of Declarative Languages - 25th International Symposium, PADL 2023, Proceedings: 25th International Symposium, PADL 2023, Boston, MA, USA, January 16–17, 2023, Proceedings. ed. / Michael Hanus; Daniela Inclezan. 1. ed. Cham: Springer, 2023. p. 20-36 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13880 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Program Synthesis Using Example Propagation

AU - Mulleners, Niek

AU - Jeuring, Johan

AU - Heeren, Bastiaan

PY - 2023/1/8

Y1 - 2023/1/8

N2 - We present Scrybe, an example-based synthesis tool for a statically-typed functional programming language, which combines top-down deductive reasoning in the style of $$\lambda ^2$$ with Smyth-style live bidirectional evaluation. During synthesis, example constraints are propagated through sketches to prune and guide the search. This enables Scrybe to make more effective use of functions provided in the context. To evaluate our tool, it is run on the combined, largely disjoint, benchmarks of $$\lambda ^2$$ and Myth. Scrybe is able to synthesize most of the combined benchmark tasks.

AB - We present Scrybe, an example-based synthesis tool for a statically-typed functional programming language, which combines top-down deductive reasoning in the style of $$\lambda ^2$$ with Smyth-style live bidirectional evaluation. During synthesis, example constraints are propagated through sketches to prune and guide the search. This enables Scrybe to make more effective use of functions provided in the context. To evaluate our tool, it is run on the combined, largely disjoint, benchmarks of $$\lambda ^2$$ and Myth. Scrybe is able to synthesize most of the combined benchmark tasks.

KW - Program synthesis

KW - Constraint propagation

KW - Input-Output examples

KW - Functional programming

UR - http://www.scopus.com/inward/record.url?scp=85148688187&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-24841-2_2

DO - 10.1007/978-3-031-24841-2_2

M3 - Conference contribution

SN - 978-3-031-24841-2

SN - 978-3-031-24840-5

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 20

EP - 36

BT - Practical Aspects of Declarative Languages - 25th International Symposium, PADL 2023, Proceedings

A2 - Hanus, Michael

A2 - Inclezan, Daniela

PB - Springer

CY - Cham

ER -

Mulleners N , Jeuring J , Heeren B. Program Synthesis Using Example Propagation. In Hanus M, Inclezan D, editors, Practical Aspects of Declarative Languages - 25th International Symposium, PADL 2023, Proceedings: 25th International Symposium, PADL 2023, Boston, MA, USA, January 16–17, 2023, Proceedings. 1 ed. Cham: Springer. 2023. p. 20-36. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-24841-2_2

Program Synthesis Using Example Propagation

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this