Herb.jl: A Unifying Program Synthesis Library

Basic Information

• Paper ID: 2510.09726
• Title: Herb.jl: A Unifying Program Synthesis Library
• Authors: Tilman Hinnerichs, Reuben Gardos Reid, Jaap de Jong, Bart Swinkels, Pamela Wochner, Nicolae Filat, Tudor Magurescu, Issa Hanou, Sebastijan Dumancic (Technische Universiteit Delft)
• Classification: cs.PL (Programming Languages), cs.AI (Artificial Intelligence), cs.SE (Software Engineering)
• Publication Date: Journal of Machine Learning Research 10 (2025) 1-48, Submitted 10/25
• Paper Link: https://arxiv.org/abs/2510.09726

Abstract

Program synthesis—automatically generating code from given specifications—is one of the most fundamental tasks in artificial intelligence and a long-standing dream for many programmers. While numerous intelligent program synthesis tools have been developed to handle exponentially growing program spaces, reusing and recombining existing methods remains tedious and time-consuming. This paper presents Herb.jl, a unified program synthesis library written in the Julia programming language to address these challenges. Since existing methods rely on similar building blocks, the authors aim to modularize underlying synthesis algorithms into communicable and fully extensible subcomponents, thereby enabling direct reapplication of these modules.

Research Background and Motivation

Core Problems

The program synthesis field faces four primary challenges:

1. Domain Specificity: Synthesizer implementations are typically designed for specific languages and difficult to adapt to new syntactic rules
2. Insufficient Modularity: Identical building blocks cannot be easily reused, requiring researchers to repeatedly implement the same ideas
3. Comparison Difficulty: Method comparisons often degenerate into comparisons of implementation quality due to engineering choices
4. Benchmark Reuse Difficulty: Syntactic rule choices in benchmarks are often implicit, affecting fair comparison

Research Motivation

While existing program synthesis methods excel in their respective domains, they suffer from the following limitations:

• Implementations are overly specialized with no reuse planning
• Lack of modular design across program synthesis branches
• Implicit assumptions and optimizations make method comparison difficult
• Inconsistent definition of benchmark syntactic rules

Core Contributions

1. Proposed Herb.jl: A novel unified program synthesis library written in Julia
2. Demonstrated Modular Implementation: Showed how to easily implement existing synthesizers using Herb.jl
3. Provided Standardized Benchmarks: Re-implemented standard benchmarks in human-readable and extensible formats
4. Summarized Design Principles: Outlined guiding design principles in Herb.jl with reference value for other synthesizer implementations

Methodology Details

Task Definition

Program synthesis problems are defined by two components:

1. Specification: Describes user intent, typically expressed through input-output examples
2. Grammar: Describes the target language, consisting of context-free derivation rules

Architecture Design

Herb.jl adopts a layered modular architecture containing the following core components:

Core Modules

• HerbCore.jl: Defines interfaces for grammars, programs, and constraints
• HerbSpecification.jl: Handles problem specification definition
• HerbGrammar.jl: Defines program syntactic structure
• HerbInterpret.jl: Handles program semantics and evaluation
• HerbConstraints.jl: Constraint formulation and propagation
• HerbSearch.jl: Search methods and enumeration techniques

Specialized Modules

• Herb.jl: Overall wrapper module
• HerbBenchmarks.jl: Collection of standard benchmarks
• Garden.jl: Collection of known synthesizer implementations

Technical Innovations

1. Separation of Syntax and Semantics

Herb.jl explicitly separates syntax and semantics:

• Program enumeration is purely syntax-based, accomplished through abstract syntax tree (AST) updates
• Programs are transformed into executable expressions to check specifications
• Users only need to provide executable expressions without understanding internal mechanisms

2. Unified Tree Structure

Introduces a custom data structure called "unified tree":

• Similar-shaped operations produce similar-shaped programs
• Unified nodes describe operation domains of identical shape, rather than individual operations
• Significantly reduces memory usage and supports efficient constraint application and propagation

3. Enumeration Order Optimization

Program enumeration order is defined through two functions:

• Priority Function: Defines priority values for elements in the priority queue
• Derivation Heuristic: Defines the enumeration order of element domains within the unified tree

Experimental Setup

Use Case Demonstrations

Case 1: Simple Problem Definition and Solving

# Define input-output specification
problem = Problem([
    IOExample(Dict(:x => 0), 1),
    IOExample(Dict(:x => 1), 3),
    IOExample(Dict(:x => 2), 5),
    IOExample(Dict(:x => 3), 7)
])

# Define grammar
grammar = @cfgrammar begin
    Int = 1 | 2 | x
    Int = Int + Int
    Int = Int * Int
end

# Execute search
iterator = BFSIterator(grammar, :Int, max_depth=5)
solution, flag = synth(problem, iterator)

Case 2: Implementing the Probe Algorithm

Demonstrates how to re-implement the Probe synthesizer in a few lines of code:

• Implement most-likely-first search iterator (MLFSIterator)
• Define probability calculation functions
• Implement Probe loop logic

Case 3: Benchmark Execution

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

Technical Implementation Details

• Utilizes Julia's multiple dispatch feature for modularity
• Leverages Julia's metaprogramming capabilities for AST manipulation
• Employs unified tree structure to optimize memory usage and constraint propagation

Experimental Results

Modularity Effectiveness Demonstration

The paper validates Herb.jl's effectiveness through three use cases:

1. Simple Problem Solving: Define and solve basic program synthesis problems with just a few lines of code
2. Re-implementation of Existing Algorithms: Probe algorithm re-implementation is concise and efficient
3. Benchmark Integration: Easily run synthesizers on standard benchmarks and collect performance metrics

Practical Validation

• Code Conciseness: Significantly reduced code volume compared to original implementations
• Module Interchangeability: Easily substitute search strategies, constraint types, and other components
• Extensibility: Supports adding new syntactic rules, search methods, and constraint types

Related Work

Current State of Program Synthesis

• Enumeration Search Methods: Including top-down and bottom-up search strategies
• Constraint-Driven Synthesis: Utilizing constraints to limit search space
• Heuristic-Guided Search: Using domain knowledge to guide the search process
• Neuro-Symbolic Methods: Combining machine learning and symbolic reasoning

Herb.jl's Positioning

Herb.jl's advantages over existing tools include:

• Cross-domain unified framework design
• Modular and reusable component architecture
• Standardized benchmark platform
• Performance and expressiveness advantages from Julia language

Conclusions and Discussion

Main Conclusions

Herb.jl successfully addresses four key problems in the program synthesis field:

1. Provides a domain-agnostic general framework
2. Implements highly modular component design
3. Establishes infrastructure for fair comparison
4. Standardizes benchmark definition and usage

Limitations

• As an emerging framework, the ecosystem is still under development
• Requires users to learn Julia language and Herb.jl's design philosophy
• Certain highly optimized domain-specific synthesizers may still have performance advantages in specific domains

Future Directions

• Continuously add new modular components to support more synthesis methods
• Expand benchmark collections to cover more application domains
• Collaborate with the machine learning community to integrate more neuro-symbolic methods

In-Depth Evaluation

Strengths

1. Innovative Unified Framework: First to provide a truly modular program synthesis library
2. Excellent Technical Design: Clever designs such as unified tree structure and syntax-semantics separation
3. High Practical Value: Significantly lowers the barrier to entry for program synthesis research
4. Comprehensive Documentation: Provides clear usage examples and implementation guides

Weaknesses

1. Limited Evaluation: Lacks detailed performance comparisons with existing tools
2. Ecosystem Dependency: Success depends on Julia community acceptance
3. Learning Curve: Requires users to master new programming paradigms and tools

Impact

• Academic Contribution: Provides a standardized platform for program synthesis research
• Practical Value: Significantly improves research efficiency and code reusability
• Reproducibility: Unified benchmark platform facilitates result reproduction

Applicable Scenarios

• Prototype development and testing of program synthesis algorithms
• Fair comparison and evaluation of different synthesis methods
• Teaching and learning program synthesis concepts
• Rapid deployment of cross-domain program synthesis applications

References

The paper cites important works in the program synthesis field, including:

• SyGuS competition benchmarks (Padhi et al., 2019)
• Probe algorithm (Barke et al., 2020)
• FrAngel synthesizer (Shi et al., 2019)
• Neo synthesizer (Feng et al., 2018)
• Program synthesis survey (Gulwani et al., 2017)

Overall Assessment: This is a high-quality systems paper that proposes a much-needed unified framework for the program synthesis field. While there is room for improvement in experimental evaluation, its technical contributions and practical value are outstanding and have the potential to become important infrastructure in the field.