Functional Program Synthesis with Higher-Order Functions and Recursion Schemes

• URL: http://arxiv.org/abs/2511.23354v1
• Date: Fri, 28 Nov 2025 17:02:01 GMT
• Title: Functional Program Synthesis with Higher-Order Functions and Recursion Schemes
• Authors: Matheus Campos Fernandes,
• Abstract summary: This text presents 2 novel GP algorithms that synthesize pure, typed, and functional programs: HOTGP and Origami.<n>HotGP uses strong types and a functional grammar, Haskell code, with support for higher-order functions, $$functions, and parametric polymorphism.<n>Origami is an algorithm that tackles the challenge of effectively handling loops and recursion by exploring Recursion.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Program synthesis is the process of generating a computer program following a set of specifications, such as a set of input-output examples. It can be modeled as a search problem in which the search space is the set of all valid programs. As the search space is vast, brute force is usually not feasible, and search heuristics, such as genetic programming, also have difficulty navigating it without guidance. This text presents 2 novel GP algorithms that synthesize pure, typed, and functional programs: HOTGP and Origami. HOTGP uses strong types and a functional grammar, synthesizing Haskell code, with support for higher-order functions, $λ$-functions, and parametric polymorphism. Experimental results show that HOTGP is competitive with the state of the art. Additionally, Origami is an algorithm that tackles the challenge of effectively handling loops and recursion by exploring Recursion Schemes, in which the programs are composed of well-defined templates with only a few parts that need to be synthesized. The first implementation of Origami can synthesize solutions in several Recursion Schemes and data structures, being competitive with other GP methods in the literature, as well as LLMs. The latest version of Origami employs a novel procedure, called AC/DC, designed to improve the search-space exploration. It achieves considerable improvement over its previous version by raising success rates on every problem. Compared to similar methods in the literature, it has the highest count of problems solved with success rates of $100\%$, $\geq 75\%$, and $\geq 25\%$ across all benchmarks. In $18\%$ of all benchmark problems, it stands as the only method to reach $100\%$ success rate, being the first known approach to achieve it on any problem in PSB2. It also demonstrates competitive performance to LLMs, achieving the highest overall win-rate against Copilot among all GP methods.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Code Repair with LLMs gives an Exploration-Exploitation Tradeoff [16.80314690163063]
  Iteratively improving and repairing source code with large language models (LLMs) has emerged as a popular way of generating programs that would be too complex to construct in one shot. We show here that refinement exposes an explore-exploit tradeoff: exploit by refining the program that passes the most test cases, or explore by refining a lesser considered program.
  arXiv  Detail & Related papers  (2024-05-26T04:00:30Z)
• Learning to Reason via Program Generation, Emulation, and Search [33.11955431589091]
  Program synthesis with language models (LMs) has unlocked a large set of reasoning abilities. Not all reasoning tasks are easily expressible as code, e.g. tasks involving commonsense reasoning, moral decision-making, and sarcasm understanding. We propose Code Generation and Emulated EXecution (CoGEX) to extend an LM's program synthesis skills to such tasks.
  arXiv  Detail & Related papers  (2024-05-25T19:40:50Z)
• Origami: (un)folding the abstraction of recursion schemes for program synthesis [0.0]
  Genetic Programming searches for a correct program that satisfies the input specification. One particular challenge is how to handle loops and recursion avoiding programs that never terminate. Recursion Schemes generalize the combination of data production and consumption.
  arXiv  Detail & Related papers  (2024-02-21T14:17:45Z)
• Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
  Four formalisms are equivalent to tree-adjoining grammars (TAG), linear indexed grammars (LIG), pushdown-adjoining automata (PAA) and embedded pushdown automata (EPDA) We design new algorithms for computing their stringsum derivations (the weight of all automatons of a string) and allsums (the weight of all derivations) For EPDA, our algorithm is both more space-efficient and time-efficient than the algorithm of Alonso et al. (2001) by factors of $mathcalO(|Gamma|2)$ and $
  arXiv  Detail & Related papers  (2023-10-23T18:26:00Z)
• ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis [54.18659323181771]
  We characterize several different forms of compositional generalization that are desirable in program synthesis. We propose ExeDec, a novel decomposition-based strategy that predicts execution subgoals to solve problems step-by-step informed by program execution at each step.
  arXiv  Detail & Related papers  (2023-07-26T01:07:52Z)
• HOTGP -- Higher-Order Typed Genetic Programming [0.0]
  HOTGP is a new genetic algorithm that synthesizes pure, typed, and functional programs. The grammar is based on Haskell's standard base library.
  arXiv  Detail & Related papers  (2023-04-06T16:23:34Z)
• Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
  This paper develops a class of low-complexity device scheduling algorithms for over-the-air learning via the method of federated learning. Compared to the state-of-the-art proposed scheme, the proposed scheme poses a drastically lower efficiency system. The efficiency of the proposed scheme is confirmed via experiments on the CIFAR dataset.
  arXiv  Detail & Related papers  (2022-06-14T08:14:14Z)
• Searching for More Efficient Dynamic Programs [61.79535031840558]
  We describe a set of program transformations, a simple metric for assessing the efficiency of a transformed program, and a search procedure to improve this metric. We show that in practice, automated search can find substantial improvements to the initial program.
  arXiv  Detail & Related papers  (2021-09-14T20:52:55Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Performance Analysis of Meta-heuristic Algorithms for a Quadratic Assignment Problem [6.555180412600522]
  A quadratic assignment problem (QAP) is an optimization problem that belongs to the class of NP-hard ones. Heuristics and meta-heuristics algorithm are prevalent solution methods for this problem. This paper is one of comparative studies to apply different metaheuristic algorithms for solving the QAP.
  arXiv  Detail & Related papers  (2020-07-29T15:02:07Z)
• The Kikuchi Hierarchy and Tensor PCA [50.840260149979265]
  For the tensor PCA (principal component analysis) problem, we propose a new hierarchy of increasingly powerful algorithms with increasing runtime.<n>Our hierarchy is analogous to the sum-of-squares (SOS) hierarchy but is instead inspired by statistical physics and related algorithms.
  arXiv  Detail & Related papers  (2019-04-08T06:26:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.