Getting Started

You can either paste this code into the Julia REPL or into a separate file, e.g. get_started.jl. If using a separate file you can execute using julia get_started.jl or julia --project=. get_started.jl depending on whether you installed Herb.jl globally or in a project.

To begin, we need to import Herb.

begin
    import Pkg
    Pkg.activate(Base.current_project())
    Pkg.instantiate()
end

using Herb

To define a program synthesis problem, we need a grammar and specification.

The grammar defines the space of programs, in the form of syntax trees.
The specification describes the behavior of the desired program.

Having defined a problem, we use HerbSearch to find syntax trees that match the specification. These trees can be executed using HerbInterpret.

The Grammar

We will start by creating a grammar using the @csgrammar macro, included in HerbGrammar. Here, we describe a simple integer arithmetic example grammar that consisting of a only one type, Number. We define a single input variable x, and the values 1,2, of that type. Then, we allow the addition and multiplication of Numbers.

grammar = @csgrammar begin
    Number = |(1:2)
    Number = x
    Number = Number + Number
    Number = Number * Number
end

1: Number = 1
2: Number = 2
3: Number = x
4: Number = Number + Number
5: Number = Number * Number

Note

The symbol x in the grammar corresponds to a variable in the arithmetic expression. It can have any name in the grammar, as long as the name does not collide with already defined symbols in julia, such as +.

The Specification

HerbSpecification defines different forms for the specification. In this guide, the specification is a collection of examples, constructed for input-output pairs. Inputs are provided as a Dict, where the keys are symbols of the input variables (in this example, x), and the values are the input variables corresponding values. The outputs of the program are simply the expected return values for the given inputs. The specification is then defined as a list of IOExamples.

specification = [IOExample(Dict(:x => x), 2x+1) for x ∈ 1:5]

5-element Vector{IOExample{Int64, Int64}}:
 IOExample{Int64, Int64}(Dict(:x => 1), 3)
 IOExample{Int64, Int64}(Dict(:x => 2), 5)
 IOExample{Int64, Int64}(Dict(:x => 3), 7)
 IOExample{Int64, Int64}(Dict(:x => 4), 9)
 IOExample{Int64, Int64}(Dict(:x => 5), 11)

The specification is used to construct a problem instance.

problem = Problem(specification)

Problem{Vector{IOExample{Int64, Int64}}}("", IOExample{Int64, Int64}[IOExample{Int64, Int64}(Dict(:x => 1), 3), IOExample{Int64, Int64}(Dict(:x => 2), 5), IOExample{Int64, Int64}(Dict(:x => 3), 7), IOExample{Int64, Int64}(Dict(:x => 4), 9), IOExample{Int64, Int64}(Dict(:x => 5), 11)])

Searching for Programs

Having defined the grammar and problem, let us search for a solution with HerbSearch.

Note

For the search to be able produce programs that use the examples' inputs, we need to ensure that there is a rule where the right-hand side matches the symbol used in the input of the IOExamples. For an example IOExample(Dict(:x => 1), 2), there must be some rule Number = x – the x's must match, otherwise the input value will never be used in any of the programs. If you have multiple input arguments, like IOExample(Dict(:x => 1, :name => "Alice"), "1. Alice"), then you need two rules, such as Number = x and String = name, to construct programs that use both inputs.

To do so, we will iterate the space of all possible program trees in a breadth-first manner using a BFSIterator. We define it to start with a program tree that have a :Number node in the root, dictating the output of the problem is of type Number defined in the grammar. We also bound the search by setting the maximum depth of the program tree to 5.

program_tree_iterator = BFSIterator(grammar, :Number, max_depth=5)

BFSIterator(GenericSolver(1: Number = 1
2: Number = 2
3: Number = x
4: Number = Number + Number
5: Number = Number * Number
, SolverState(Hole[Bool[1, 1, 1, 1, 1]], Set{AbstractLocalConstraint}(), true), DataStructures.PriorityQueue{AbstractLocalConstraint, Int64, Base.Order.ForwardOrdering}(), nothing, false, 9223372036854775807, 5))

The problem, along with the program tree iterator, can then be handed to the synth function to run the search. The search will continue until it finds a program that satisfies all the examples in the specification, or until the iterator is exhausted. When it terminates, it returns the program that satisfies the most examples, along with a flag that indicates whether the program satisfies all the examples or not.

solution, flag = synth(problem, program_tree_iterator)

(4{4{1,3},3}, optimal_program)

Using the Synthesized Program

Eventually, we want to test our solution on some other inputs. To that end, we transform the solution from a syntax tree back to a readable and exicutable format using rulenode2expr.

begin
    program = rulenode2expr(solution, grammar)
    println(program)
end

To set up an environment that correctly binds values to the variables in the program, we provide the execute_on_input function. It takes in three arguments:

A SymbolTable, which is nothing more than a dictionary mapping symbols from the grammar to symbols in the Julia expression. This can be created using the grammar2symboltable function.
The program to execute. Note: This is not the solution from the search, but the Julia expression built from the solution and the grammar.
Values for all the variables in the grammar.

begin
    output = execute_on_input(grammar2symboltable(grammar), program, Dict(:x => 6)) 
    println(output)
end

If you run the completed code it will output both the generated Julia expression and the result from assigning value.

Just like that we tackled (almost) all modules of Herb.jl.

Where to go from here?

See our other tutorials!

The full code example

using Herb

# define our very simple context-free grammar
# Can add and multiply over the input variable x and the integers 1,2.
grammar = @csgrammar begin
    Number = |(1:2)
    Number = x
    Number = Number + Number
    Number = Number * Number
end

# define the synthesis problem specification as input-output examples, in this case using the function 2x+1
problem = Problem([IOExample(Dict(:x => x), 2x+1) for x ∈ 1:5])

# define a breadth-first iterator over program trees with root node :Number and max depth 5
iterator = BFSIterator(grammar, :Number, max_depth=5)

# run the synthesis, returning the best solution and a flag indicating whether all examples were satisfied
solution, flag = synth(problem, iterator)

# convert the solution from a syntax tree to a Julia expression, and print it
program = rulenode2expr(solution, grammar)
println(program)

# execute the program on the input x=6, and print the output
output = execute_on_input(grammar2symboltable(grammar), program, Dict(:x => 6)) 
println(output)