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: مكتبة موحدة لتوليف البرامج
  • المؤلفون: تيلمان هينيريخس، روبن جاردوس ريد، جاب دي جونج، بارت سوينكلز، باميلا ووخنر، نيكولاي فيلات، تودور ماجوريسكو، عيسى هانو، سيباستيجان دومانسيك (جامعة تقنية ديلفت)
  • التصنيف: cs.PL (لغات البرمجة)، cs.AI (الذكاء الاصطناعي)، cs.SE (هندسة البرمجيات)
  • تاريخ النشر: مجلة أبحاث التعلم الآلي 10 (2025) 1-48، مُقدّمة 10/25
  • رابط الورقة: https://arxiv.org/abs/2510.09726

الملخص

توليف البرامج — توليد الأكواد تلقائياً بناءً على مواصفات معينة — يعتبر من أساسيات مهام الذكاء الاصطناعي وحلم العديد من المبرمجين. على الرغم من تطوير عدد من أدوات توليف البرامج الذكية للتعامل مع فضاء البرامج المتنامي بشكل أسي، فإن إعادة استخدام وإعادة دمج الطرق الموجودة يعتبر مرهقاً وتستغرق وقتاً طويلاً. تقترح هذه الورقة Herb.jl، مكتبة موحدة لتوليف البرامج مكتوبة بلغة البرمجة جوليا لحل هذه المشاكل. نظراً لأن الطرق الموجودة تعتمد على لبنات بناء متشابهة، يهدف المؤلفون إلى تعديل خوارزميات التوليف الأساسية إلى مكونات فرعية قابلة للتواصل وقابلة للتوسع بالكامل، مما يسمح بإعادة تطبيق مباشرة لهذه الوحدات.

الخلفية البحثية والدافع

المشاكل الأساسية

يواجه مجال توليف البرامج أربع مشاكل رئيسية:

  1. الخصوصية بالمجال: تُصمم تطبيقات المولفات عادة للغات معينة، مما يصعب التكيف مع قواعد بناء جديدة
  2. عدم كفاية التعديل: لا يمكن إعادة استخدام لبنات البناء المتطابقة بسهولة، مما يتطلب من الباحثين إعادة تطبيق الأفكار ذاتها
  3. صعوبة المقارنة: غالباً ما تتحول مقارنة الطرق إلى مقارنة جودة التطبيق بسبب الاختلافات الهندسية
  4. صعوبة إعادة استخدام المعايير: غالباً ما تكون اختيارات قواعد بناء المعايير ضمنية، مما يؤثر على المقارنة العادلة

الدافع البحثي

على الرغم من أن طرق توليف البرامج الموجودة تظهر أداءً ممتازاً في مجالاتها، إلا أنها تعاني من القيود التالية:

  • التطبيقات متخصصة جداً وتفتقر إلى التخطيط لإعادة الاستخدام
  • تفتقر إلى التصميم المعدّل عبر فروع توليف البرامج المختلفة
  • الافتراضات والتحسينات الضمنية تجعل مقارنة الطرق صعبة
  • تعريف قواعد بناء المعايير غير موحد

المساهمات الأساسية

  1. اقتراح Herb.jl: مكتبة موحدة جديدة لتوليف البرامج مكتوبة بلغة جوليا
  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

تفاصيل التطبيق التقني

  • استخدام ميزة الإرسال المتعدد في جوليا لتطبيق التعديل
  • الاستفادة من قدرات البرمجة الفوقية في جوليا للتعامل مع عمليات AST
  • اعتماد بنية الشجرة الموحدة لتحسين استخدام الذاكرة ونشر القيود

نتائج التجربة

عرض تأثير التعديل

تتحقق الورقة من فعالية Herb.jl من خلال ثلاث حالات استخدام:

  1. حل المشاكل البسيطة: يمكن تعريف وحل مشاكل توليف البرامج الأساسية بسهولة في عدة أسطر من الأكواس
  2. إعادة تطبيق الخوارزميات الموجودة: إعادة تطبيق خوارزمية Probe بأكواد موجزة وفعالة
  3. دمج المعايير: تشغيل المولفات بسهولة على المعايير القياسية وجمع مقاييس الأداء

التحقق من الفائدة العملية

  • بساطة الأكواد: انخفاض كبير في حجم الأكواد مقارنة بالتطبيقات الأصلية
  • قابلية تبديل الوحدات: يمكن بسهولة استبدال استراتيجيات البحث وأنواع القيود وغيرها من المكونات
  • قابلية التوسع: دعم إضافة قواعس جديدة وطرق بحث وأنواع قيود جديدة

الأعمال ذات الصلة

الحالة الحالية لمجال توليف البرامج

  • طرق البحث بالتعداد: تتضمن استراتيجيات البحث من الأعلى إلى الأسفل ومن الأسفل إلى الأعلى
  • توليف مدفوع بالقيود: استخدام القيود لتقليل فضاء البحث
  • البحث الموجه بالإرشادات: استخدام المعرفة بالمجال لتوجيه عملية البحث
  • الطرق العصبية الرمزية: دمج التعلم الآلي والاستدلال الرمزي

موضع Herb.jl

مقارنة بالأدوات الموجودة، تتمتع Herb.jl بالمزايا التالية:

  • تصميم إطار عمل موحد عبر المجالات
  • عمارة مكونات معدّلة وقابلة لإعادة الاستخدام
  • منصة معايير موحدة
  • مزايا الأداء والتعبيرية التي توفرها لغة جوليا

الخلاصة والنقاش

الاستنتاجات الرئيسية

نجحت Herb.jl في حل أربع مشاكل رئيسية في مجال توليف البرامج:

  1. توفير إطار عمل عام خالٍ من المجال
  2. تطبيق تصميم مكونات معدّل بدرجة عالية
  3. إنشاء بنية أساسية للمقارنة العادلة
  4. توحيد تعريف واستخدام المعايير

القيود

  • كإطار عمل ناشئ، لا تزال النظم البيئية قيد الإنشاء
  • يتطلب من المستخدمين تعلم لغة جوليا ومبادئ تصميم Herb.jl
  • قد تحتفظ بعض المولفات المتخصصة المحسّنة بشكل كبير بمزايا الأداء في مجالات معينة

الاتجاهات المستقبلية

  • الاستمرار في إضافة مكونات معدّلة جديدة لدعم طرق توليف أكثر
  • توسيع مجموعة المعايير لتغطية مجالات تطبيق أكثر
  • التعاون مع مجتمع التعلم الآلي لدمج طرق عصبية رمزية أكثر

التقييم المتعمق

المزايا

  1. إطار عمل موحد مبتكر: يوفر لأول مرة مكتبة توليف برامج معدّلة حقاً
  2. تصميم تقني ممتاز: تصاميم مثل بنية الشجرة الموحدة وفصل القواعس والدلالات ذكية
  3. قيمة عملية عالية: يقلل بشكل كبير من عتبة الدخول لأبحاث توليف البرامج
  4. توثيق شامل: يوفر حالات استخدام واضحة وأدلة تطبيق

أوجه القصور

  1. تقييم محدود: يفتقر إلى مقارنات أداء مفصلة مع الأدوات الموجودة
  2. الاعتماد على النظام البيئي: يعتمد النجاح على قبول مجتمع جوليا
  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)

التقييم الشامل: هذه ورقة عالية الجودة في مجال الأنظمة، تقترح إطار عمل موحد يحتاجه مجال توليف البرامج بشدة. على الرغم من وجود مجال للتحسين في جوانب التقييم التجريبي، فإن مساهماتها التقنية وقيمتها العملية بارزة جداً، وقد تصبح بنية أساسية مهمة في هذا المجال.