How to train your dragon: on the application of the Metropolis-Hastings algorithm for program synthesis

This paper addresses the problem of Inductive Synthesis by analysing the Metropolis-Hastings stochastic search algorithm. The goal of Inductive Synthesis is to generate programs whose intended behaviour is established through the use of input and output examples. The Metropolis-Hastings algorithm searches the set of all possible programs and...

Genetic Algorithms for Inductive Program Synthesis

VanillaGP is an Inductive Program Synthesis algorithm that takes a Genetic Algorithm (GA) approach by using its 3 components: selection, mutation, and crossover. Many different alternatives exist for these components and although this is not the only application of a GAs on the Program Synthesis domain, it has not been extensively evaluated what...

Improvements in Monte Carlo Tree Search for Inductive Program Synthesis

A recent development in program synthesis is using Monte Carlo Tree Search to traverse the search tree of possible programs in order to efficiently find a program that will successfully transform the given input to the desired output. Previous research has shown promising results as Monte Carlo Tree Search is able to escape local optima that...

Evaluating Souper: A Synthesizing Superoptimizer

Modern compilers exploit syntax \&amp; semantics to optimize input programs.<br/>Often such optimization rules are arduous to get right and the output is not guaranteed to be globally optimal.<br/>Superoptimizers take a different approach to this problem by traversing the program space.<br/>This study focuses on Souper, a synthesizing...

Evolving a Search Procedure for Program Synthesis

In recent months, researchers developed several new search procedures to augment the process of program synthesis. While many of them performed better than their predecessors, the proposed solutions are still far from ideal. One possible way of overcoming the shortcomings of single search methods is employing genetic algorithms, which have been...

Evolving a Domain-Specific Language to Speed Up Program Synthesis

Program synthesis is used in various ways to automate repetitive tasks or to generate software automatically. Search-based program synthesis constitutes searching the space of candidate programs created from a given language. However, this form of program synthesis is very expensive in terms of computing power. By optimising the synthesiser’s...

Genetic Algorithm for Evolving an Objective Function of a Program Synthesizer

Program Synthesis is a challenging problem in Artificial Intelligence. An important element of a program synthesizer is the objective function that guides the combinatorial search for a program that satisfies a given user intent. Given multiple I/O example transformations that correspond to the intended behavior of the program, this function...

Evolving Design Patterns for Program Synthesis

Design pattern provide an abstraction that the pro- gram synthesis algorithm can use in order to find programs easier. However, coming up with them is difficult as they are domain-specific. This paper showcases a novel approach to creating design pat- terns through the means of genetic algorithms. Re- sults are showing that while in the robot...

GENERALIZE: A framework for evolving searching constraints for domain-specific languages in program synthesis

In this paper, we propose a method for eliciting constraints for arbitrary Domain-Specific Languages (DSL) in Program Synthesis search. We argue that we can successfully predict constraints using a form of attribute-based induction. We also provide a novel approach to constraint verification using genetic algorithms to optimize desired results....

Comparative analysis of the Metropolis-Hastings algorithm as applied to the domain of program synthesis

In this research the Metropolis-Hastings algorithmis implemented for the problem of program synthesis and compared with Brute, a best-first search, together with multiple other different search algorithms. The implementation and choices of the Metrolpolis-Hastings algorithm are discussed in detail. The algorithms are tested for three different...

Program Synthesis with A*

Search based synthesis has emerged as a powerful tool in program synthesis, the process of automatically generating implementations for software programs given some form of semantic specification. Search based synthesis involves a search over the space of candidate programs that can be derived from a given grammar. A recently developed new...

Improving Inductive Program Synthesis by using Very Large Neighborhood Search and Variable-Depth Neighborhood Search

Brute, A state-of-the-art inductive program synthesis (IPS) system, introduced a two-phase algorithm; first, complex pro- gram instructions are invented from basic instructions. Sec- ond, a best-first search algorithm finds a sequence of invented instructions to solve an IPS task. This method is limited because invented instructions are always...

Inductive Program Synthesis through using Monte Carlo Tree Search guided by a heuristic-based loss function

Recently, a new and promising Inductive Program Synthesis (IPS) system, Brute, showed the potential of using a heuristic-based loss function. However, Brute also has its limitations and struggles with escaping local optima. The Monte Carlo Tree Search might offer a solution to this problem since it balances between exploitation and exploration....

VanillaGP: Genetic Algorithm for Inductive Program Synthesis

Inductive Program Synthesis is the problem of generating programs from<br/>a set of input-output examples. Since it can be reduced to the search problem in the space of programs, many search algorithms have been successfully<br/>applied to it over the years. This paper proposes, develops, and analyses<br/>a novel algorithm in the family of...

PropR: Property-Based Automatic Program Repair

Automatic program repair (APR) regularly faces the challenge of overfitting patches — patches that pass the test suite, but do not actually address the problems when evaluated manually. Currently, overfit detection requires manual inspection or an oracle making quality control of APR an expensive task. With this work, we want to introduce...