論文の概要: Functional Program Synthesis with Higher-Order Functions and Recursion Schemes
- arxiv url: http://arxiv.org/abs/2511.23354v1
- Date: Fri, 28 Nov 2025 17:02:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-12-01 19:47:55.990598
- Title: Functional Program Synthesis with Higher-Order Functions and Recursion Schemes
- Title（参考訳）: 高次関数と再帰スキームを用いた関数型プログラム合成
- Authors: Matheus Campos Fernandes,
- Abstract要約: 本文は,HOTGPとOrigamiという,純粋,型付き,関数型プログラムを合成する2つの新しいGPアルゴリズムを提示する。
HotGPは、強い型と機能文法、Haskellコード、高階関数、$$functions、パラメトリック多型をサポートする。
折り紙(おりがみ)は、再帰を探索することでループや再帰を効果的に処理するアルゴリズムである。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: プログラム合成は、一連のインプット・アウトプット・サンプルのような一連の仕様に従ってコンピュータプログラムを生成するプロセスである。
検索空間がすべての有効なプログラムの集合である検索問題としてモデル化することができる。
探索空間は広大なため、残酷な力は通常実現不可能であり、遺伝的プログラミングのような探索ヒューリスティックな手法も誘導なしではナビゲートすることが困難である。
本文は,HOTGPとOrigamiという,純粋,型付き,関数型プログラムを合成する2つの新しいGPアルゴリズムを提示する。
HOTGPは強型と機能文法を使用し、Haskellコードを合成し、高階関数、$λ$-functions、パラメトリック多型をサポートする。
実験の結果,HOTGPは最先端技術と競合していることがわかった。
さらに、再帰スキームを探索することで、ループと再帰を効果的に扱うという課題に対処するアルゴリズムである。
折り紙の最初の実装は、複数の再帰スキームやデータ構造における解を合成することができ、文学における他のGP手法やLLMと競合する。
最新の折り紙は、探索空間探索を改善するために、AC/DCと呼ばれる新しい手順を採用している。
それは、すべての問題で成功率を上げることによって、以前のバージョンよりも大幅に改善される。
文献における同様の手法と比較すると、すべてのベンチマークで100\%$、$\geq 75\%$、$\geq 25\%$といった成功率で解決された問題の最も多い数である。
ベンチマーク問題の18 %$では、PSB2のあらゆる問題でそれを達成するための最初の既知のアプローチとして、100 %$の成功率に達する唯一の方法である。
また、LPMと競合する性能を示し、全てのGP手法の中でコパイロットに対して最高勝利率を達成した。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Learning to Reason via Program Generation, Emulation, and Search [33.11955431589091]
言語モデル(LM)によるプログラム合成は、多くの推論能力を解放した。
すべての推論タスクは、コードとして容易に表現できるわけではない。例えば、常識的推論、道徳的意思決定、皮肉な理解を含むタスクである。
我々は,プログラム合成スキルをこのようなタスクに拡張するために,コード生成とエミュレートされた実行(CoGEX)を提案する。
論文 参考訳（メタデータ） (2024-05-25T19:40:50Z) - Origami: (un)folding the abstraction of recursion schemes for program
synthesis [0.0]
遺伝的プログラミングは入力仕様を満たす正しいプログラムを探索する。
特定の課題はループと再帰を扱う方法であり、終わらないプログラムを避けることである。
再帰スキーマは、データ生産と消費の組み合わせを一般化する。
論文 参考訳（メタデータ） (2024-02-21T14:17:45Z) - Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。
我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。
EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
論文 参考訳（メタデータ） (2023-10-23T18:26:00Z) - ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis [54.18659323181771]
プログラム合成において望ましいいくつかの異なる構成一般化形式を特徴付ける。
本稿では,ExeDecを提案する。ExeDecは,実行サブゴールを予測し,各ステップでプログラム実行によって段階的に通知される問題を解くための,新しい分解ベースの戦略である。
論文 参考訳（メタデータ） (2023-07-26T01:07:52Z) - HOTGP -- Higher-Order Typed Genetic Programming [0.0]
HOTGPは純粋、型付き、機能プログラムを合成する新しい遺伝的アルゴリズムである。
この文法はHaskellの標準ベースライブラリに基づいている。
論文 参考訳（メタデータ） (2023-04-06T16:23:34Z) - Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。
最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。
提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
論文 参考訳（メタデータ） (2022-06-14T08:14:14Z) - Searching for More Efficient Dynamic Programs [61.79535031840558]
本稿では,プログラム変換の集合,変換プログラムの効率を評価するための単純な指標,およびこの指標を改善するための探索手順について述べる。
実際に、自動検索は初期プログラムの大幅な改善を見出すことができることを示す。
論文 参考訳（メタデータ） (2021-09-14T20:52:55Z) - The Kikuchi Hierarchy and Tensor PCA [50.840260149979265]
テンソルPCA(主成分分析)問題に対して,ランタイムの増大を伴うアルゴリズムの階層化を提案する。
我々の階層は、SOS(sum-of-squares)階層に似ているが、代わりに統計物理学や関連するアルゴリズムにインスパイアされている。
論文 参考訳（メタデータ） (2019-04-08T06:26:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。