Paper Info
Title
A family of multi-concept program synthesisers in Alloy.
Abstract
Program synthesis aims to mechanise the task of programming from the user intent (using pre and post condition, examples and sketches). There are many approaches (or concepts) in program synthesis that are usually implemented in isolation: deductive, syntax-based, inductive, etc. In this paper, we present a characterisation of program synthesis as model finding, using Alloy*. Such a characterisation unifies several of these concepts in a single model. Through model finding, we obtain a general framework for rapid development of a program synthesiser accommodating denotational semantics based synthesis, simultaneous deductive and inductive synthesis, software reuse, syntactic ingredients (the Alloy* scope of entities), and a new one: a soft sketch(a set of commands that must appear in the synthesised program but in no particular order of execution). Our family of synthesisers produce general purpose programs in the Java language. As the Alloy* synthesiser requires several rounds of user assistance to set scope, sketches, etc., particularly for complex problems, we integrated the model finder to a genetic algorithm module, where candidate solutions and user inputs are generated and mutated automatically. We carried out empirical evaluations on program synthesis successfully. As results, we verified that: (i) we can synthesise thirteen programs (Maj5, Maj8, IntSQRT, Max4, Modu, Fact, Fib, aMax, aDouble, aSum, eCount, aBubSort, aSelSort); (ii) inductive synthesis was faster than deductive synthesis; (iii) synthesis with reuse was faster; and (iv) Genetic Algorithm is better than user trial and error approach. (C) 2020 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2021
10.1016/j.scico.2020.102536
SCIENCE OF COMPUTER PROGRAMMING
Keywords
DocType
Volume
Program synthesis,Alloy*,SAT solving,Genetic Algorithm
Journal
201
ISSN
Citations 
PageRank 
0167-6423
0
0.34
References 
Authors
0
3
Name
Order
Citations
PageRank
Alexandre Correia100.34
Juliano Iyoda2619.21
Alexandre Cabral Mota319918.27