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.

using Herb

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

First, a grammar can be constructed using the @csgrammar macro included in HerbGrammar.

Here, we describe a simple integer arithmetic example, that can add and multiply an input variable x or the integers 1,2, using

g = @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

Second, the problem specification can be provided using e.g. input/output examples using HerbSpecification. Inputs are provided as a Dict assigning values to variables, and outputs as arbitrary values. The problem itself is then a list of IOExamples using

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

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)])

The problem is given now, let us search for a solution with HerbSearch. For now, we will just use the default parameters searching for a satisfying program over the grammar, given the problem and a starting symbol using

iterator = BFSIterator(g, :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))

solution, flag = synth(problem, iterator)

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

There are various ways to adapt the search technique to your needs. Please have a look at the synth documentation.

Eventually, we want to test our solution on some other inputs using HerbInterpret. We transform our grammar g to a Julia expression with grammar2symboltable(g), add our solution and the input, assigning the value 6 to the variable x.

program = rulenode2expr(solution, g)

:((1 + x) + x)

output = execute_on_input(grammar2symboltable(g), program, Dict(:x => 6))  # should yield 2*6+1

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 an input variable x or the integers 1,2.
g = @csgrammar begin
    Number = |(1:2)
    Number = x
    Number = Number + Number
    Number = Number * Number
end

problem = Problem([IOExample(Dict(:x => x), 2x+1) for x ∈ 1:5])
iterator = BFSIterator(g, :Number, max_depth=5)

solution, flag = synth(problem, iterator)
program = rulenode2expr(solution, g)
println(program)

output = execute_on_input(grammar2symboltable(g), program, Dict(:x => 6)) 
println(output)