2025-11-24T09:28:17.353555

Herb.jl: A Unifying Program Synthesis Library

Hinnerichs, Reid, de Jong et al.
Program synthesis -- the automatic generation of code given a specification -- is one of the most fundamental tasks in artificial intelligence (AI) and many programmers' dream. Numerous synthesizers have been developed to tackle program synthesis, manifesting different ideas to approach the exponentially growing program space. While numerous smart program synthesis tools exist, reusing and remixing previously developed methods is tedious and time-consuming. We propose Herb.jl, a unifying program synthesis library written in the Julia programming language, to address these issues. Since current methods rely on similar building blocks, we aim to modularize the underlying synthesis algorithm into communicating and fully extendable sub-compartments, allowing for straightforward reapplication of these modules. To demonstrate the benefits of using Herb.jl, we show three common use cases: 1. how to implement a simple problem and grammar, and how to solve it, 2. how to implement a previously developed synthesizer with just a few lines of code, and 3. how to run a synthesizer against a benchmark.
academic

Herb.jl: एक एकीकृत प्रोग्राम संश्लेषण पुस्तकालय

मूल जानकारी

  • पेपर ID: 2510.09726
  • शीर्षक: Herb.jl: A Unifying Program Synthesis Library
  • लेखक: Tilman Hinnerichs, Reuben Gardos Reid, Jaap de Jong, Bart Swinkels, Pamela Wochner, Nicolae Filat, Tudor Magurescu, Issa Hanou, Sebastijan Dumancic (Technische Universiteit Delft)
  • वर्गीकरण: cs.PL (प्रोग्रामिंग भाषाएं), cs.AI (कृत्रिम बुद्धिमत्ता), cs.SE (सॉफ्टवेयर इंजीनियरिंग)
  • प्रकाशन समय: Journal of Machine Learning Research 10 (2025) 1-48, Submitted 10/25
  • पेपर लिंक: https://arxiv.org/abs/2510.09726

सारांश

प्रोग्राम संश्लेषण — दिए गए विनिर्देश के अनुसार स्वचालित रूप से कोड उत्पन्न करना — कृत्रिम बुद्धिमत्ता में सबसे मौलिक कार्यों में से एक है और कई प्रोग्रामर का सपना है। हालांकि प्रोग्राम स्पेस की घातीय वृद्धि को संभालने के लिए कई बुद्धिमान प्रोग्राम संश्लेषण उपकरण विकसित किए गए हैं, लेकिन पहले से मौजूद विधियों का पुनः उपयोग और पुनः संयोजन कठिन और समय लेने वाला है। यह पेपर Herb.jl प्रस्तुत करता है, जो Julia प्रोग्रामिंग भाषा में लिखी गई एक एकीकृत प्रोग्राम संश्लेषण पुस्तकालय है जो इन समस्याओं को हल करता है। चूंकि मौजूदा विधियां समान निर्माण खंडों पर निर्भर करती हैं, लेखक अंतर्निहित संश्लेषण एल्गोरिदम को मॉड्यूलर, संचार योग्य और पूरी तरह से विस्तारणीय उप-घटकों में विभाजित करने का लक्ष्य रखते हैं, जिससे इन मॉड्यूल का सीधा पुनः अनुप्रयोग संभव हो सके।

अनुसंधान पृष्ठभूमि और प्रेरणा

मूल समस्याएं

प्रोग्राम संश्लेषण क्षेत्र चार प्रमुख समस्याओं का सामना करता है:

  1. डोमेन विशिष्टता: संश्लेषक कार्यान्वयन आमतौर पर विशिष्ट भाषाओं के लिए डिज़ाइन किए जाते हैं, नए सिंटैक्स नियमों के अनुकूल होना कठिन है
  2. अपर्याप्त मॉड्यूलरिटी: समान निर्माण खंडों को आसानी से पुनः उपयोग नहीं किया जा सकता, शोधकर्ताओं को समान विचारों को दोबारा लागू करना पड़ता है
  3. तुलना में कठिनाई: इंजीनियरिंग विकल्पों के अंतर के कारण, विधि तुलना अक्सर कार्यान्वयन गुणवत्ता की तुलना में बदल जाती है
  4. बेंचमार्क पुनः उपयोग में कठिनाई: बेंचमार्क के सिंटैक्स नियम चयन अक्सर निहित होते हैं, जो निष्पक्ष तुलना को प्रभावित करते हैं

अनुसंधान प्रेरणा

मौजूदा प्रोग्राम संश्लेषण विधियां, हालांकि अपने-अपने क्षेत्रों में उत्कृष्ट प्रदर्शन करती हैं, निम्नलिखित सीमाओं का सामना करती हैं:

  • कार्यान्वयन अत्यधिक विशेष है, पुनः उपयोग के लिए योजना की कमी है
  • प्रोग्राम संश्लेषण शाखाओं में मॉड्यूलर डिज़ाइन की कमी है
  • निहित धारणाएं और अनुकूलन विधि तुलना को कठिन बनाते हैं
  • बेंचमार्क सिंटैक्स नियम परिभाषा में एकरूपता की कमी है

मूल योगदान

  1. Herb.jl का प्रस्ताव: Julia भाषा में लिखी गई एक नई एकीकृत प्रोग्राम संश्लेषण पुस्तकालय
  2. मॉड्यूलर कार्यान्वयन का प्रदर्शन: Herb.jl का उपयोग करके पहले से मौजूद संश्लेषकों को आसानी से कार्यान्वित करने का तरीका दिखाया गया है
  3. मानकीकृत बेंचमार्क प्रदान करना: मानव-पठनीय और विस्तारणीय प्रारूप में मानक बेंचमार्क को पुनः कार्यान्वित किया गया है
  4. डिज़ाइन सिद्धांतों का सारांश: Herb.jl में मार्गदर्शक डिज़ाइन सिद्धांतों की रूपरेखा दी गई है, जो अन्य संश्लेषक कार्यान्वयन के लिए संदर्भ मूल्य रखते हैं

विधि विवरण

कार्य परिभाषा

प्रोग्राम संश्लेषण समस्या दो घटकों द्वारा परिभाषित की जाती है:

  1. विनिर्देश (Specification): उपयोगकर्ता के इरादे का वर्णन करता है, आमतौर पर इनपुट-आउटपुट उदाहरणों के माध्यम से व्यक्त किया जाता है
  2. व्याकरण (Grammar): लक्ष्य भाषा का वर्णन करता है, संदर्भ-मुक्त व्युत्पत्ति नियमों से बना है

आर्किटेक्चर डिज़ाइन

Herb.jl एक स्तरीय मॉड्यूलर आर्किटेक्चर अपनाता है, जिसमें निम्नलिखित मूल घटक शामिल हैं:

मूल मॉड्यूल

  • HerbCore.jl: व्याकरण, प्रोग्राम और बाधाओं के इंटरफेस को परिभाषित करता है
  • HerbSpecification.jl: समस्या विनिर्देश परिभाषा को संभालता है
  • HerbGrammar.jl: प्रोग्राम सिंटैक्स संरचना को परिभाषित करता है
  • HerbInterpret.jl: प्रोग्राम शब्दार्थ और मूल्यांकन को संभालता है
  • HerbConstraints.jl: बाधा सूत्रीकरण और प्रसार को संभालता है
  • HerbSearch.jl: खोज विधियां और गणना तकनीकें

विशेष मॉड्यूल

  • Herb.jl: समग्र पैकेजिंग मॉड्यूल
  • HerbBenchmarks.jl: मानक बेंचमार्क संग्रह
  • Garden.jl: ज्ञात संश्लेषकों का कार्यान्वयन संग्रह

तकनीकी नवाचार बिंदु

1. व्याकरण और शब्दार्थ का पृथक्करण

Herb.jl व्याकरण और शब्दार्थ को स्पष्ट रूप से अलग करता है:

  • प्रोग्राम गणना विशुद्ध रूप से व्याकरण पर आधारित है, अमूर्त सिंटैक्स ट्री (AST) को अपडेट करके पूरी की जाती है
  • प्रोग्राम को विनिर्देश की जांच के लिए निष्पादन योग्य अभिव्यक्तियों में परिवर्तित किया जाता है
  • उपयोगकर्ताओं को केवल निष्पादन योग्य अभिव्यक्तियां प्रदान करनी होती हैं, आंतरिक तंत्र को समझने की आवश्यकता नहीं है

2. एकीकृत वृक्ष संरचना

एक कस्टम डेटा संरचना "एकीकृत वृक्ष" का परिचय:

  • समान आकार की संक्रियाएं समान आकार के प्रोग्राम उत्पन्न करती हैं
  • एकीकृत नोड्स एकल संक्रिया के बजाय समान आकार की संक्रियाओं के डोमेन का वर्णन करते हैं
  • मेमोरी उपयोग को काफी कम करता है, कुशल बाधा अनुप्रयोग और प्रसार का समर्थन करता है

3. गणना क्रम अनुकूलन

दो कार्यों के माध्यम से प्रोग्राम गणना क्रम को परिभाषित करता है:

  • प्राथमिकता कार्य: प्राथमिकता कतार में तत्वों के प्राथमिकता मान को परिभाषित करता है
  • व्युत्पत्ति अनुमानी: एकीकृत वृक्ष के भीतर तत्व डोमेन के गणना क्रम को परिभाषित करता है

प्रायोगिक सेटअप

उपयोग केस प्रदर्शन

केस 1: सरल समस्या परिभाषा और समाधान

# इनपुट-आउटपुट विनिर्देश परिभाषित करें
problem = Problem([
    IOExample(Dict(:x => 0), 1),
    IOExample(Dict(:x => 1), 3),
    IOExample(Dict(:x => 2), 5),
    IOExample(Dict(:x => 3), 7)
])

# व्याकरण परिभाषित करें
grammar = @cfgrammar begin
    Int = 1 | 2 | x
    Int = Int + Int
    Int = Int * Int
end

# खोज निष्पादित करें
iterator = BFSIterator(grammar, :Int, max_depth=5)
solution, flag = synth(problem, iterator)

केस 2: Probe एल्गोरिदम का कार्यान्वयन

कुछ पंक्तियों के कोड में Probe संश्लेषक को पुनः कार्यान्वित करने का तरीका दिखाया गया है:

  • सबसे संभावित प्राथमिकता खोज पुनरावृत्तिकार (MLFSIterator) को कार्यान्वित करें
  • संभाव्यता गणना कार्य को परिभाषित करें
  • Probe लूप तर्क को कार्यान्वित करें

केस 3: बेंचमार्क चलाना

using HerbBenchmarks
pairs = get_all_problem_grammar_pairs(PBE_SLIA_Track_2019)

solved_problems = 0
for (problem, grammar) in pairs
    solution = probe(grammar, :Start, problem; max_depth=5)
    if !isnothing(solution)
        solved_problems += 1
    end
end

तकनीकी कार्यान्वयन विवरण

  • मॉड्यूलरिटी को कार्यान्वित करने के लिए Julia की बहु-प्रेषण विशेषता का उपयोग करें
  • AST संचालन को संभालने के लिए Julia की मेटाप्रोग्रामिंग क्षमता का उपयोग करें
  • मेमोरी उपयोग और बाधा प्रसार को अनुकूलित करने के लिए एकीकृत वृक्ष संरचना अपनाएं

प्रायोगिक परिणाम

मॉड्यूलरिटी प्रभाव प्रदर्शन

पेपर तीन उपयोग केसों के माध्यम से Herb.jl की प्रभावशीलता को सत्यापित करता है:

  1. सरल समस्या समाधान: कुछ पंक्तियों के कोड में बुनियादी प्रोग्राम संश्लेषण समस्या को परिभाषित और हल किया जा सकता है
  2. पहले से मौजूद एल्गोरिदम पुनः कार्यान्वयन: Probe एल्गोरिदम का पुनः कार्यान्वयन कोड संक्षिप्त और कुशल है
  3. बेंचमार्क एकीकरण: मानक बेंचमार्क पर संश्लेषक को आसानी से चलाया जा सकता है और प्रदर्शन मेट्रिक्स एकत्र किए जा सकते हैं

व्यावहारिकता सत्यापन

  • कोड सरलता: मूल कार्यान्वयन की तुलना में कोड की मात्रा में काफी कमी
  • मॉड्यूल परस्पर विनिमयता: खोज रणनीति, बाधा प्रकार आदि घटकों को आसानी से बदला जा सकता है
  • विस्तारणीयता: नए सिंटैक्स नियम, खोज विधियां और बाधा प्रकार जोड़ने का समर्थन करता है

संबंधित कार्य

प्रोग्राम संश्लेषण क्षेत्र की वर्तमान स्थिति

  • गणना खोज विधियां: स्वयं-शीर्ष-से-नीचे और स्वयं-नीचे-से-ऊपर खोज रणनीतियां शामिल हैं
  • बाधा-संचालित संश्लेषण: खोज स्पेस को सीमित करने के लिए बाधाओं का उपयोग करता है
  • अनुमानी-निर्देशित: खोज प्रक्रिया को निर्देशित करने के लिए डोमेन ज्ञान का उपयोग करता है
  • तंत्रिका-प्रतीकात्मक विधियां: मशीन लर्निंग और प्रतीकात्मक तर्क को जोड़ता है

Herb.jl की स्थिति

मौजूदा उपकरणों की तुलना में, Herb.jl के लाभ हैं:

  • क्रॉस-डोमेन एकीकृत ढांचे डिज़ाइन
  • मॉड्यूलर और पुनः उपयोग योग्य घटक आर्किटेक्चर
  • मानकीकृत बेंचमार्क प्लेटफॉर्म
  • Julia भाषा द्वारा लाए गए प्रदर्शन और अभिव्यक्ति क्षमता लाभ

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

Herb.jl प्रोग्राम संश्लेषण क्षेत्र की चार प्रमुख समस्याओं को सफलतापूर्वक हल करता है:

  1. डोमेन-अज्ञेय सामान्य ढांचा प्रदान करता है
  2. उच्च स्तर की मॉड्यूलर घटक डिज़ाइन को कार्यान्वित करता है
  3. निष्पक्ष तुलना के लिए आधारभूत संरचना स्थापित करता है
  4. बेंचमार्क परिभाषा और उपयोग को मानकीकृत करता है

सीमाएं

  • एक नई ढांचे के रूप में, पारिस्थितिकी तंत्र अभी भी निर्माणाधीन है
  • उपयोगकर्ताओं को Julia भाषा और Herb.jl के डिज़ाइन दर्शन को सीखने की आवश्यकता है
  • कुछ अत्यधिक अनुकूलित विशेष संश्लेषक विशिष्ट डोमेन में अभी भी प्रदर्शन लाभ रख सकते हैं

भविष्य की दिशा

  • नई मॉड्यूलर घटकों को जोड़ना जारी रखें ताकि अधिक संश्लेषण विधियों का समर्थन किया जा सके
  • बेंचमार्क संग्रह को विस्तारित करें ताकि अधिक अनुप्रयोग क्षेत्रों को कवर किया जा सके
  • मशीन लर्निंग समुदाय के साथ सहयोग करें, अधिक तंत्रिका-प्रतीकात्मक विधियों को एकीकृत करें

गहन मूल्यांकन

शक्तियां

  1. नवाचारी एकीकृत ढांचा: पहली बार सच में मॉड्यूलर प्रोग्राम संश्लेषण पुस्तकालय प्रदान करता है
  2. उत्कृष्ट तकनीकी डिज़ाइन: एकीकृत वृक्ष संरचना और व्याकरण-शब्दार्थ पृथक्करण जैसे डिज़ाइन चतुर हैं
  3. उच्च व्यावहारिक मूल्य: प्रोग्राम संश्लेषण अनुसंधान के लिए प्रवेश बाधा को काफी कम करता है
  4. संपूर्ण दस्तावेज़: स्पष्ट उपयोग केस और कार्यान्वयन मार्गदर्शन प्रदान करता है

कमियां

  1. सीमित मूल्यांकन: मौजूदा उपकरणों के साथ विस्तृत प्रदर्शन तुलना की कमी है
  2. पारिस्थितिकी तंत्र निर्भरता: सफलता Julia समुदाय की स्वीकृति पर निर्भर करती है
  3. सीखने की वक्र: उपयोगकर्ताओं को नई प्रोग्रामिंग प्रतिमान और उपकरण में महारत हासिल करने की आवश्यकता है

प्रभाव

  • शैक्षणिक योगदान: प्रोग्राम संश्लेषण अनुसंधान के लिए मानकीकृत प्लेटफॉर्म प्रदान करता है
  • व्यावहारिक मूल्य: अनुसंधान दक्षता और कोड पुनः उपयोग को काफी हद तक सुधारता है
  • पुनरुत्पादनीयता: एकीकृत बेंचमार्क प्लेटफॉर्म परिणामों के पुनरुत्पादन में सहायता करता है

लागू परिदृश्य

  • प्रोग्राम संश्लेषण एल्गोरिदम के प्रोटोटाइप विकास और परीक्षण
  • विभिन्न संश्लेषण विधियों की निष्पक्ष तुलना और मूल्यांकन
  • प्रोग्राम संश्लेषण अवधारणाओं की शिक्षा और सीखना
  • क्रॉस-डोमेन प्रोग्राम संश्लेषण अनुप्रयोगों का तेजी से तैनाती

संदर्भ

पेपर प्रोग्राम संश्लेषण क्षेत्र के महत्वपूर्ण कार्यों का हवाला देता है, जिनमें शामिल हैं:

  • SyGuS प्रतियोगिता बेंचमार्क (Padhi et al., 2019)
  • Probe एल्गोरिदम (Barke et al., 2020)
  • FrAngel संश्लेषक (Shi et al., 2019)
  • Neo संश्लेषक (Feng et al., 2018)
  • प्रोग्राम संश्लेषण सर्वेक्षण (Gulwani et al., 2017)

समग्र मूल्यांकन: यह एक उच्च-गुणवत्ता वाला प्रणाली पेपर है जो प्रोग्राम संश्लेषण क्षेत्र में तत्काल आवश्यकता वाली एकीकृत ढांचा प्रस्तुत करता है। हालांकि प्रायोगिक मूल्यांकन के पहलू में सुधार की गुंजाइश है, लेकिन इसके तकनीकी योगदान और व्यावहारिक मूल्य दोनों ही बहुत उत्कृष्ट हैं, और यह इस क्षेत्र का एक महत्वपूर्ण आधारभूत संरचना बनने की संभावना रखता है।