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

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference Article in proceeding › 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 λ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 λ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
Subtitle of host publication	25th International Symposium, PADL 2023, Proceedings
Editors	Michael Hanus, Daniela Inclezan
Publisher	Springer, Cham
Pages	20-36
Number of pages	17
Edition	1
ISBN (Electronic)	978-3-031-24841-2
ISBN (Print)	9783031248405
DOIs	https://doi.org/10.1007/978-3-031-24841-2_2
Publication status	Published - Jan 2023
Event	25th International Symposium on Practical Aspects of Declarative Languages, PADL 2023 - Boston, United States Duration: 16 Jan 2023 → 17 Jan 2023 https://popl23.sigplan.org/home/PADL-2023

Publication series

Series	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13880 LNCS
ISSN	0302-9743

Symposium

Symposium	25th International Symposium on Practical Aspects of Declarative Languages, PADL 2023
Country/Territory	United States
City	Boston
Period	16/01/23 → 17/01/23
Internet address	https://popl23.sigplan.org/home/PADL-2023

Keywords

Constraint propagation
Functional programming
Input-Output examples
Program synthesis

Access to Document

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

Cite this

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

@inproceedings{daaed2e26d8c47e593536f48c22d1c11,

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 λ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 λ2 and MYTH. SCRYBE is able to synthesize most of the combined benchmark tasks.",

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

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.; 25th International Symposium on Practical Aspects of Declarative Languages, PADL 2023 ; Conference date: 16-01-2023 Through 17-01-2023",

year = "2023",

month = jan,

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

language = "English",

isbn = "9783031248405",

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

publisher = "Springer, Cham",

pages = "20--36",

editor = "Michael Hanus and Daniela Inclezan",

booktitle = "Practical Aspects of Declarative Languages",

edition = "1",

url = "https://popl23.sigplan.org/home/PADL-2023",

}

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. 1 edn, Springer, Cham, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13880 LNCS, pp. 20-36, 25th International Symposium on Practical Aspects of Declarative Languages, PADL 2023, Boston, Massachusetts, United States, 16/01/23. 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. ed. / Michael Hanus; Daniela Inclezan. 1. ed. Springer, Cham, 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 Article in proceeding › Academic › peer-review

TY - GEN

T1 - Program Synthesis Using Example Propagation

AU - Mulleners, Niek

AU - Jeuring, Johan

AU - Heeren, Bastiaan

PY - 2023/1

Y1 - 2023/1

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 λ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 λ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 λ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 λ2 and MYTH. SCRYBE is able to synthesize most of the combined benchmark tasks.

KW - Constraint propagation

KW - Functional programming

KW - Input-Output examples

KW - Program synthesis

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

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

M3 - Conference Article in proceeding

AN - SCOPUS:85148688187

SN - 9783031248405

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

A2 - Hanus, Michael

A2 - Inclezan, Daniela

PB - Springer, Cham

T2 - 25th International Symposium on Practical Aspects of Declarative Languages, PADL 2023

Y2 - 16 January 2023 through 17 January 2023

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. 1 ed. Springer, Cham. 2023. p. 20-36. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 13880 LNCS). doi: 10.1007/978-3-031-24841-2_2

Program Synthesis Using Example Propagation

Abstract

Publication series

Symposium

Keywords

Access to Document

Fingerprint

Cite this