Program synthesis searches a grammar-defined space for a program that satisfies a user specification. Constraints can significantly reduce this search space. They can either be added manually by the user or derived through conflict analysis, which turns failed candidates into learned constraints. These constraints often retain irrelevant candidate details and accumulate costly redundancy. This thesis extends a conflict-analysis framework with core-guided MUC generalization and constraint-set cleanup. Generalization uses a semantic unsatisfiable core to wildcard irrelevant branches while preserving the candidate root and core nodes, as well as values referenced by core relations. Cleanup minimizes the active constraint set in many ways: by either removing constraints through exact deduplication or subsumption, or by merging constraints through single-differences and cross-relations. We evaluate both extensions on several benchmarks, assessing the reduced search space, constraint set size, runtime, and number of solved problems and used enumerations. At the largest program sizes, generalized MUC reduces enumerations by anywhere between 60 and 99.9%, consistently improving over the previous MUC implementation. Similarly, the strongest cleanup configuration can reduce the mean active constraint population by more than three orders of magnitude. While the new extensions manage to solve slightly more problems, their runtime improvement is negligible. Nonetheless, our extensions show that conflict analysis can learn substantially more general constraints and represent them more compactly. ... Read more

Learning from Demonstration allows robot behaviour to be specified by examples rather than manual programming, but demonstrations are often noisy and provide limited structure for efficient search. Framing the problem as program synthesis allows us to search for programs that follow the demonstrated behaviour, but enumerative synthesis suffers from an enormous search space and inefficient exploration. Recent work shows that large language models (LLMs) can guide synthesis by providing probabilistic priors over program structure, though such methods typically ignore execution traces and structural depth. In this thesis, we propose a synthesis framework that combines LLM-guided probabilistic grammars with trace-based feedback and depth-sensitive costs. We derive a depth-aware probabilistic grammar from LLM-generated programs, guide bottom-up enumeration using the induced costs, and dynamically update rule probabilities based on how closely candidate programs follow demonstrated execution traces. The results show that the effectiveness of LLM guidance and trace-based feedback depends on structural depth: while LLM priors mainly improve reachability in depth-agnostic settings, trace-based updates performs better when depthaware costs are used, and their combination yields the strongest gains in search efficiency. ... Read more

Existing Inductive Program Synthesis (IPS) techniques generate programs from
examples and are restricted to specific task classes to exploit domain knowledge.
To compete with general-purpose LLM-based code generation, a single IPS system
must handle tasks with different types of inputs, outputs, and instructions without
relying on domain-specific knowledge. This thesis introduces task-level adapta-
tion, a framework in which a synthesizer must learn how to search only from the in-
dividual task it is solving rather than from a predefined domain. We focus specific-
ally on search guided by automatically generated properties that capture useful
aspects of a program’s output. We introduce PHALCON to demonstrate the frame-
work’s viability. PHALCON repeatedly samples programs, selects properties that
distinguish incorrect outputs from intended behavior, and uses them to constrain
subsequent sampling. PHALCON outperforms state-of-the-art techniques special-
ized for string and bit-vector transformations, and solves tasks from the challenging
Abstraction and Reasoning Corpus. These results establish task-level adaptation as
a promising foundation for efficient, general program synthesis. ... Read more

Program synthesis is the task of constructing a program that satisfies specified constraints. One popular formulation of program synthesis is example-based synthesis. Here, the synthesizer attempts to find a program in a specified domain that satisfies a set of input-output examples. Enumeration is the most common approach to finding the desired program. However, the exponentially growing search space makes this infeasible. The size of the domain can be largely attributed to its inefficient representation. Often, programs are only syntactically distinguished, meaning programs that behave the same are seen as different. We introduce Context-Sensitive E-Graph Saturation, a novel method that limits the search space to programs that solve at least one of the provided examples. This allows focusing only on programs that behave similarly to the desired one. Crucial is finding contextual equivalences for each example over a generated termset. These equivalences allow generating many solutions for each individual example. A program in the intersection of these programs solves all examples. In experiments on a subset from SyGus SLIA, our method solves the problems that enumeration solves, but not more. These results highlight a trade-off: with a small termset, the discovered equivalences are often too limited to capture the relationships needed to find a universal solution. Conversely, increasing the termset size quickly leads to inefficiency. To address this, we propose a strategy for constructing a more expressive yet small termset, enabling our method to solve a broader range of synthesis problems. ... Read more

Program synthesis is often seen as the holy grail of computer science. A user only needs to provide program specifications and a computer will automatically generate the desired program. This often involves searching for the desired program in the program space, which is like searching for a needle in a haystack. Luckily, there is room for improvement here. Many programs in the program space are redundant and should never be considered. To filter out these redundant programs, we propagated grammar constraints during search using a novel built-in constraint solver. Only programs that satisfy these constraints will be considered as candidates for synthesis. To measure the effectiveness of the solver, we have enumerated several program spaces with and without constraints. Although the amount of filtering largely depends on the concrete grammar and constraints, the results show that constraints can often eliminate $99\%$ of the program space. Accounting for the overhead of propagation, this comes down to a 50-fold improvement in runtime. ... Read more

Program synthesis is the task of generating a program that satisfies some specification. An important aspect of program synthesis is the method of specification. There are various ways in which a desired program can be specified, such as I/O examples, traces, and natural language. This research paper aims to explore a novel method of specifying a desired program in program synthesis -- rewards. This concept is explored by adjusting the Probe program synthesiser to solve the dense navigation environments in MineRL. In order to avoid local maxima, it is necessary to increase the amount of exploration. To that end, different ways of increasing exploration were tested by changing the parameters of Probe. By increasing the amount of exploration, it is possible to solve more environments, or solve them faster. But increasing exploration could also have the opposite effect, depending on the environment. ... Read more

Program synthesis has been extensively used for automating code-related tasks, but it has yet to be applied in the realm of reward-based games. FrAngel is a component-based program synthesizer that addresses the aspects of exploration and exploitation, both important for the performance of a program synthesizer. However, its specific implementation makes it hard to study and extend. We first implement a generalized version of FrAngel that takes arbitrary grammars and program generators, while also generalizing most of its features by redesign. We then use it to introduce a novel approach to formulating a reward-based problem into an inductive specification. We integrate this algorithm within MineRL, an AI framework for playing Minecraft. Lastly, we lay the groundwork for using program synthesis for Minecraft by investigating the ways of tuning the algorithm to generate complex subprograms. By changing the configuration parameters, as well as slightly changing the algorithm’s implementation, we managed to observe a significant increase in the complexity of fragments and generated programs. These modifications are a stepping stone towards using program synthesis to solve complex game tasks. ... Read more

Program synthesis is the task to construct a program that provably satisfies a given high-level specification. There are various ways in which a specification can be described. This research focuses on adapting the Probe synthesizer, traditionally reliant on input-output examples, to utilize reward-based synthesis. The generalization of Probe allows for flexibility in using various search algorithms, selection and updating algorithms, enhancing its applicability to a general case. By modifying the Probe algorithm to learn from rewards, we explore how exploiting existing programs as partial solutions impacts synthesis performance. Different ways of exploitation were tested, specifically, how much the probabilities change, and how a starting probabilities can affect the synthesis. Exploitation of programs could lead to faster synthesis but it could also lead to no solutions depending on the world environment. ... Read more

Program synthesis remains largely unexplored in the context of playing games, where exploration and exploitation are crucial for solving tasks within complex environments. FrAngel is a program synthesis algorithm that addresses both of these aspects with its fragments used for the generation of new candidate programs. We introduce a generalised version of the FrAngel program synthesis algorithm that accepts an arbitrary iterator and grammar, enabling flexible modifications. We then formulate Program by Example (PBE) program synthesis from rewards and apply this framework to Minecraft's navigation task, where dense rewards guide the algorithm's exploration. Then, we use the generalised version of the algorithm to conduct experiments in the context of exploration of the algorithm. The experiments show the importance of exploration as a step required for the exploitation and finding the wanted solution to the task while also revealing that sometimes more exploration does not necessarily mean reaching the solution faster. ... Read more

Program synthesis involves finding a program that meets the user intent, typically provided as input/output examples or formal mathematical specifications. This paper explores a novel specification in program synthesis - learning from rewards.
We explore existing synthesizers, Probe and FrAngel, to solve navigation tasks inside the popular Minecraft game. The problem formulation is inspired by reinforcement learning but was adapted to program synthesis. Similar to reinforcement learning, balancing exploration and exploitation is essential for solving the task efficiently. Excessive exploration can prevent finding the correct program because the feedback from the environment is not used. On the other hand, excessive exploitation is not ideal, as seemingly promising programs might not lead to the actual solution. This work compares different trade-offs between exploration and exploitation of Probe and FrAngel when applied to Minecraft environments. ... Read more

How convenient would it be to have an AI that relieves us programmers from the burden of coding? Program synthesis is a technique that achieves exactly that: it automatically generates simple programs that meet a given set of examples or adhere to a provided specification. This is often done by enumerating all programs in the search space and returning the first program that satisfies the requirements. However, these algorithms frequently enumerate redundant programs because of symmetries in the search space. We propose a new constraint discovery system that is able to detect these symmetries in a language and systematically generate symmetry-breaking constraints for them. To test these constraints, we implemented a novel, re-usable framework for program synthesis called Herb.jl. The generated constraints are shown to cut down search spaces to less than 25% of the original size and reduce the enumeration time by a factor of 3. Furthermore, this approach is extended to automatically discover semantic specifications without needing an expert. The effectiveness of these specifications is evaluated with an existing specification-based synthesizer, which shows that adding these specifications is an effective way to cut the synthesis time in half for domains where expert-defined specifications are not available. Together, these approaches demonstrate the effectiveness of extracting additional information from a language and applying it during enumeration. ... Read more

This paper presents a comparative study of multiple algorithms that can be used to automatically search for high-performing pipelines on machine learning problems. These algorithms, namely Very Large-Scale Neighbourhood search (VLSN), Breadth-first search, Metropolis-Hastings, Monte-Carlo tree search (MCTS), enumerative A* search, and Genetic Programming, are evaluated on three datasets. The performance of VLSN is consistently acceptable for this task, but the best performance is given by MCTS. Interestingly the results show that limiting the solution space to pipelines containing only a classifier operator does not significantly decrease performance. Three possible explanations for this are that the datasets used are too simple, the use of default hyperparameters makes preprocessing and feature selection operators useless, or the evaluation of pipelines on a limited training set makes the search procedure ineffective. This research contributes to the field of AutoML by shedding light on algorithm performance and providing insights for future improvements. ... Read more

Machine learning pipelines encompass various sequential steps involved in tasks such as data extraction, preprocessing, model training, and deployment. Manual construction of these pipelines demands expert knowledge and can be time-consuming. To address this challenge, program synthesis offers an automated approach to generate computer programs based on high-level specifications or examples. By leveraging program synthesis, the development of machine learning solutions can be expedited, leading to broader adaptability. A key element of program synthesis is the objective function, which guides the combinatorial search for a program that satisfies user-defined requirements. This study examines the performance of the Monte Carlo Tree Search (MCTS) algorithm in the realm of generating machine learning pipelines through program synthesis. The research investigates the method's efficacy, explores its findings in terms of accuracy, cost, variance, and execution time, and draws conclusions regarding the algorithm's potential and limitations. By analyzing the MCTS algorithm's performance, this research contributes to the advancement of automated machine learning pipeline generation and highlights the benefits and considerations associated with using program synthesis techniques. ... Read more

This paper investigates the performance of the A* algorithm in the field of automated machine learning using program synthesis. We designed a context-free grammar to create machine learning pipelines and came up with a cost function for A*. Two different experiments were done, the first one to tune the parameters of our algorithm and the second one to compare the efficiency of A* with other search algorithms. The results indicate that for the selected datasets, A* did not have better performance, but rather had similar results with the other search algorithms. Nevertheless, more research in this field is needed to find concrete results. ... Read more