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: একটি একীভূত প্রোগ্রাম সংশ্লেষণ লাইব্রেরি

মৌলিক তথ্য

  • পেপার আইডি: 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, জমা দেওয়া 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)

সামগ্রিক মূল্যায়ন: এটি একটি উচ্চ মানের সিস্টেম পেপার যা প্রোগ্রাম সংশ্লেষণ ক্ষেত্রে জরুরিভাবে প্রয়োজনীয় একীভূত ফ্রেমওয়ার্ক প্রস্তাব করে। যদিও পরীক্ষামূলক মূল্যায়নের ক্ষেত্রে উন্নতির অবকাশ রয়েছে, তবে এর প্রযুক্তিগত অবদান এবং ব্যবহারিক মূল্য উভয়ই অত্যন্ত উল্লেখযোগ্য এবং এটি এই ক্ষেত্রের একটি গুরুত্বপূর্ণ অবকাঠামো হয়ে উঠার সম্ভাবনা রয়েছে।