HerbSearch.jl Documentation

AbstractBFSIterator <: TopDownIterator

This is the supertype for all breadth-first search iterators. It inherits all stop-criteria and traversal mechanisms from TopDownIterator.

AbstractDFSIterator <: TopDownIterator

This is the supertype for all depth-first search iterators. It inherits all stop-criteria and from TopDownIterator, but the traversal mechanism is implemented to perform a depth-first search.

AbstractMHSearchIterator <: StochasticSearchIterator

This is the supertype for all Metropolis Hastings (MH) search iterators. It inherits all behaviour from StochasticSearchIterator.

AbstractSASearchIterator <: StochasticSearchIterator

This is the supertype for all SA search iterators.

AbstractVLSNSearchIterator <: StochasticSearchIterator

This is the supertype for all VLSN search iterators.

@programiterator BFSIterator() <: TopDownIterator

Creates a breadth-first search iterator for traversing given a grammar, starting from the given symbol. The iterator returns trees in the grammar in increasing order of size.

@programiterator DFSIterator() <: AbstractDFSIterator

Creates a depth-first search iterator for traversing a given a grammar, starting from a given symbol. The iterator returns trees in the grammar in decreasing order of size.

@enum ExpandFailureReason limit_reached=1 already_complete=2

Representation of the different reasons why expanding a partial tree failed. Currently, there are two possible causes of the expansion failing:

• limit_reached: The depth limit or the size limit of the partial tree would be violated by the expansion
• already_complete: There is no hole left in the tree, so nothing can be expanded.

GeneticSearchIterator{FitnessFunction,CrossOverFunction,MutationFunction,SelectParentsFunction,EvaluationFunction} <: ProgramIterator

Defines an ProgramIterator using genetic search.

Consists of:

• examples::Vector{<:IOExample}: a collection of examples defining the specification

• evaluation_function::EvaluationFunction: interpreter to evaluate the individual programs

• population_size::Int64: number of inviduals in the population

• mutation_probability::Float64: probability of mutation for each individual

• maximum_initial_population_depth::Int64: maximum depth of trees when population is initialized

end

MHSearchIterator(examples::AbstractArray{<:IOExample}, cost_function::Function, evaluation_function::Function=HerbInterpret.execute_on_input)

The MHSearchIterator generates programs using the Metropolis-Hastings algorithm. The search behaviour has the following characteristics:

• It uses random_fill_propose for the propose function.
• The accept function isprobabilistic`.
• The temperature of the algorithm remains constant over time, ensuring a stable acceptance probability.

Arguments

• examples::AbstractArray{<:IOExample}: An array of input-output examples used to guide the search.
• cost_function::Function: A function to evaluate the cost of the proposed programs.
• evaluation_function::Function=HerbInterpret.execute_on_input: A function that evaluates the generated program generated and produces an output. Defaults to HerbInterpret.execute_on_input.

Returns

An iterator to generate programs according to the Metropolis Hastings algorithm.

@programiterator MLFSIterator() <: TopDownIterator

Iterator that enumerates expressions in the grammar in decreasing order of probability (Only use this iterator with probabilistic grammars). Inherits all stop-criteria from TopDownIterator.

abstract type ProgramIterator

Generic iterator for all possible search strategies. All iterators are expected to have the following fields:

• grammar::ContextSensitiveGrammar: the grammar to search over
• sym::Symbol: defines the start symbol from which the search should be started
• max_depth::Int: maximum depth of program trees
• max_size::Int: maximum number of AbstractRuleNodes of program trees
• max_time::Int: maximum time the iterator may take
• max_enumerations::Int: maximum number of enumerations

@programiterator RandomIterator() <: TopDownIterator

Iterates trees in the grammar in a random order.

SASearchIterator(spec, cost_function, initial_temperature=1, temperature_decreasing_factor = 0.99, evaluation_function::Function=HerbInterpret.execute_on_input)

Returns an enumerator that runs according to the Simulated Annealing Search algorithm.

• spec : array of examples
• cost_function : cost function to evaluate the programs proposed
• initial_temperature : the starting temperature of the algorithm
• temperature_decreasing_factor : the decreasing factor of the temperature of the time
• evaluation_function : evaluation function that evaluates the program generated and produces an output

The propose function is random_fill_propose (the same as for Metropolis Hastings). The accept function is probabilistic but takes into account the tempeerature too.

 abstract type StochasticSearchIterator <: ProgramIterator

A unified abstract type for the stochastic search algorithms Metropolis Hastings, Very Large Scale Neighbourhood and Simulated Annealing. Iterators are customisable by overloading the followign functions:

• neighbourhood
• propose
• temperature
• accept.

Fields

• examples::Vector{IOExample} example used to check the program
• cost_function::Function. Returns the cost of the current program. It receives a list of tuples for (expected, found) and gives back a cost.
• initial_temperature::Real = 1
• evaluation_function::Function that evaluates the julia expressions

An iterator over all possible expressions of a grammar up to maxdepth with start symbol sym. Also inherits all stop criteria like `maxdepthfromProgramIterator`.

@enum SynthResult optimal_program=1 suboptimal_program=2

Representation of the possible results of the synth procedure. At the moment there are two possible outcomes:

• optimal_program: The synthesized program satisfies the entire program specification.
• suboptimal_program: The synthesized program does not satisfy the entire program specification, but got the best score from the evaluator.

mutable struct TopDownIterator <: ProgramIterator

Enumerates a context-free grammar starting at Symbol sym with respect to the grammar up to a given depth and a given size. The exploration is done using the given priority function for derivations, and the expand function for discovered nodes. Concrete iterators may overload the following methods:

• priority_function
• derivation_heuristic
• hole_heuristic

mutable struct UniformIterator

Inner iterator that enumerates all candidate programs of a uniform tree.

• solver: the uniform solver.
• outeriter: outer iterator that is responsible for producing uniform trees. This field is used to dispatch on the derivation_heuristic.
• unvisited_branches: for each search-node from the root to the current search-node, a list of unviisted branches.
• nsolutions: number of solutions found so far.

UniformIterator(solver::UniformSolver, outeriter::ProgramIterator)

Constructs a new UniformIterator that traverses solutions of the UniformSolver and is an inner iterator of an outer ProgramIterator.

VLSNSearchIterator(spec, cost_function, enumeration_depth = 2, evaluation_function::Function=HerbInterpret.execute_on_input) = StochasticSearchIterator(

Returns an iterator that runs according to the Very Large Scale Neighbourhood Search algorithm.

• spec : array of examples
• cost_function : cost function to evaluate the proposed programs
• vlsn_neighbourhood_depth : the enumeration depth to search for a best program at a time
• evaluation_function : evaluation function that evaluates the program generated and produces an output

The propose function consists of all possible programs of the given enumeration_depth. The accept function accepts the program with the lowest cost according to the cost_function. The temperature value of the algorithm remains constant over time.

@programiterator

Canonical way of creating a program iterator. The macro automatically declares the expected fields listed in the ProgramIterator documentation. Syntax accepted by the macro is as follows (anything enclosed in square brackets is optional): @programiterator [mutable] <IteratorName>( <arg₁>, ..., <argₙ> ) [<: <SupertypeIterator>] Note that the macro emits an assertion that the SupertypeIterator is a subtype of ProgramIterator which otherwise throws an ArgumentError. If no supertype is given, the new iterator extends ProgramIterator directly. Each <argᵢ> may be (almost) any expression valid in a struct declaration, and they must be comma separated. One known exception is that an inner constructor must always be given using the extended function <name>(...) ... end syntax. The mutable keyword determines whether the declared struct is mutable.

function Base.collect(iter::TopDownIterator)

Return an array of all programs in the TopDownIterator.

Base.iterate(iter::GeneticSearchIterator, current_state::GeneticIteratorState)

Iterates the search space using a genetic algorithm. Takes the iterator and the current state to mutate and crossover random inviduals. Returns the best program-so-far and the state of the iterator.

Base.iterate(iter::GeneticSearchIterator)

Iterates the search space using a genetic algorithm. First generates a population sampling random programs. Returns the best program-so-far, and the state of the iterator.

Base.iterate(iter::StochasticSearchIterator, current_state::IteratorState)

The algorithm that constructs the iterator of StochasticSearchIterator. It has the following structure:

1. get a random node location -> location,dict = neighbourhood(current_program)
2. call propose on the current program getting a list of full programs
3. iterate through all the proposals and check if the proposed program is "better" than the previous one
4. "accept" the new program by calling the accept
5. return the new next_program

Base.iterate(iter::TopDownIterator, pq::DataStructures.PriorityQueue)

Describes the iteration for a given TopDownIterator and a PriorityQueue over the grammar without enqueueing new items to the priority queue. Recursively returns the result for the priority queue.

Base.iterate(iter::TopDownIterator)

Describes the iteration for a given TopDownIterator over the grammar. The iteration constructs a PriorityQueue first and then prunes it propagating the active constraints. Recursively returns the result for the priority queue.

Base.length(iter::ProgramIterator)

Counts and returns the number of possible programs without storing all the programs. !!! warning: modifies and exhausts the iterator

Base.length(iter::UniformIterator)

Counts and returns the number of programs without storing all the programs. !!! warning: modifies and exhausts the iterator

rand(::Type{RuleNode}, grammar::AbstractGrammar, max_depth::Int=10)

Generates a random RuleNode of arbitrary type and maximum depth max_depth.

rand(::Type{RuleNode}, grammar::AbstractGrammar, typ::Symbol, max_depth::Int=10)

Generates a random RuleNode of return type typ and maximum depth max_depth.

rand(::Type{RuleNode}, grammar::AbstractGrammar, typ::Symbol, dmap::AbstractVector{Int}, max_depth::Int=10)

Generates a random RuleNode, i.e. an expression tree, of root type typ and maximum depth max_depth guided by a depth map dmap if possible.

_calculate_cost(program::RuleNode, cost_function::Function, spec::AbstractVector{IOExample}, grammar::AbstractGrammar, evaluation_function::Function)

Returns the cost of the program using the examples and the cost_function. It first convert the program to an expression and evaluates it on all the examples.

_find_next_complete_tree(solver::Solver, pq::PriorityQueue, iter::TopDownIterator)::Union{Tuple{RuleNode, Tuple{Vector{AbstractRuleNode}, PriorityQueue}}, Nothing}

Takes a priority queue and returns the smallest AST from the grammar it can obtain from the queue or by (repeatedly) expanding trees that are in the queue. Returns nothing if there are no trees left within the depth limit.

accept(::StochasticSearchIterator, current_cost::Real, next_cost::Real, temperature::Real)

Based on the current program and possible cost and temperature a program is accepted or not. Usually we would always want to accept better programs but we might get stuck if we do so. That is why some implementations of the accept function accept with a probability costs that are worse. cost means how different are the outcomes of the program compared to the correct outcomes. The lower the cost the better the program performs on the examples. The cost is provided by the cost_function

best_accept(current_cost::Real, next_cost::Real, temperature::Real)

Returns true if the cost of the proposed program is smaller than the cost of the current program. Otherwise, returns false.

Arguments

• current_cost::Real: the cost of the current program.
• next_cost::Real: the cost of the proposed program.
• temperature::Real: the temperature; not used.

calculate_cost(iter::T, program::Union{RuleNode, StateHole}) where T <: StochasticSearchIterator

Wrapper around _calculate_cost.

const_temperature(current_temperature::Real)

Returns the temperature unchanged. This function is used by Metropolis Hastings and Very Large Neighbourhood Search algorithms.

Arguments

• current_temperature::Real: the current temperature of the search.

constructNeighbourhood(current_program::RuleNode, grammar::AbstractGrammar)

The neighbourhood node location is chosen at random. The dictionary is nothing.

Arguments

• current_program::RuleNode: the current program.
• grammar::AbstractGrammar: the grammar.

constructNeighbourhoodRuleSubset(current_program::RuleNode, grammar::AbstractGrammar)

The neighbourhood node location is chosen at random. The dictionary is contains one entry with key "rule_subset" and value of type Vector{Any} being a random subset of grammar rules.

Arguments

• current_program::RuleNode: the current program.
• grammar::AbstractGrammar: the grammar.

cross_over(::GeneticSearchIterator, parent_1::RuleNode, parent_2::RuleNode)

Combines the program from two parent individuals to create one or more offspring individuals.

crossover_swap_children_1(parent_1::RuleNode, parent_2::RuleNode)

Performs a random crossover of two parents of type RuleNode. The subprograms are swapped and only one altered parent program is returned.

crossover_swap_children_2(parent_1::RuleNode, parent_2::RuleNode)

Performs a random crossover of two parents of type RuleNode. The subprograms are swapped and both altered parent programs are returned.

decreasing_temperature(percentage::Real)

Returns a function that produces a temperature decreased by percentage%. This function is used by the Simmulated Annealing algorithm.

Arguments

• percentage::Real: the percentage to decrease the temperature by.

default_fitness(program, results)

Defines the default fitness function taking the program and its results. Results are a vector of tuples, where each tuple is in the form Tuple{expected_output, actual_output}. As we are looking for individuals with the highest fitness function, the error is inverted.

derivation_heuristic(iter::MLFSIterator, domain::Vector{Int})

Defines derivation_heuristic for the iterator type MLFSIterator. Sorts the indices within a domain, that is grammar rules, by decreasing log_probabilities.

This will invert the enumeration order if probabilities are equal.

function derivation_heuristic(::RandomIterator, indices::Vector{Int})

Randomly shuffles the rules.

function derivation_heuristic(::TopDownIterator, indices::Vector{Int})

Returns a sorted sublist of the indices, based on which rules are most promising to fill a hole. The underlying solver can change the order within a Hole's domain. We sort the domain to make the enumeration order explicit and more predictable.

enumerate_neighbours_propose(enumeration_depth::Int64)

The return function is a function that produces a list with all the subprograms with depth at most enumeration_depth.

evaluate(problem::Problem{Vector{IOExample}}, expr::Any, tab::SymbolTable; allow_evaluation_errors::Bool=false)

Evaluate the expression on the examples.

Optional parameters:

- `shortcircuit` - Whether to stop evaluating after finding single example fails, to speed up the [synth](@ref) procedure. If true, the returned score is an underapproximation of the actual score.
- `allow_evaluation_errors` - Whether the search should continue if an exception is thrown in the evaluation or throw the error

Returns a score in the interval [0, 1]

extract_name_from_argument(ex)

Extracts the name of a field declaration, otherwise throws an ArgumentError. A field declaration is either a simple field name with possible a type attached to it or a keyword argument.

Example

x::Int -> x hello -> hello x = 4 -> x x::Int = 3 -> x

fitness(::GeneticSearchIterator, program, results)

Assigns a numerical value (fitness score) to each individual based on how closely it meets the desired objective.

Returns a vector of disjoint branches to expand the search tree at its current state. Example:

# pseudo code
Hole(domain=[2, 4, 5], children=[
    Hole(domain=[1, 6]), 
    Hole(domain=[1, 6])
])

If we split on the first hole, this function will create three branches.

• (firsthole, 2)
• (firsthole, 4)
• (firsthole, 5)

get_best_program(population::Array{RuleNode}, iter::GeneticSearchIterator)::RuleNode

Returns the best program within the population with respect to the fitness function.

heuristic_leftmost(node::AbstractRuleNode, max_depth::Int)::Union{ExpandFailureReason, HoleReference}

Defines a heuristic over holes, where the left-most hole always gets considered first. Returns a HoleReference once a hole is found. This is the default option for enumerators.

heuristic_random(node::AbstractRuleNode, max_depth::Int)::Union{ExpandFailureReason, HoleReference}

Defines a heuristic over holes, where random holes get chosen randomly using random exploration. Returns a HoleReference once a hole is found.

heuristic_rightmost(node::AbstractRuleNode, max_depth::Int)::Union{ExpandFailureReason, HoleReference}

Defines a heuristic over holes, where the right-most hole always gets considered first. Returns a HoleReference once a hole is found.

heuristic_smallest_domain(node::AbstractRuleNode, max_depth::Int)::Union{ExpandFailureReason, HoleReference}

Defines a heuristic over all available holes in the unfinished AST, by considering the size of their respective domains. A domain here describes the number of possible derivations with respect to the constraints. Returns a HoleReference once a hole is found.

hole_heuristic(::TopDownIterator, node::AbstractRuleNode, max_depth::Int)::Union{ExpandFailureReason, HoleReference}

Defines a heuristic over variable shaped holes. Returns a HoleReference once a hole is found.

is_field_decl(ex)

Check if extractname(ex) returns a name.

is_kwdeg(ex)

Checks if a field declaration is a keyword argument or not. This is called when filtering if the user arguments to the program iteartor are keyword arguments or not.

mean_squared_error(results::AbstractVector{Tuple{<:Number,<:Number}})

Returns the mean squared error of results.

Arguments

• results<:AbstractVector{<:Tuple{Number,Number}}: the vector of tuples, where each tuple is in the form Tuple{expected_output, actual_output}.

misclassification(results::AbstractVector{Tuple{<:Number,<:Number}})

Returns the amount of misclassified examples, i.e. how many tuples with non-matching entries are there in results.

Arguments

• results<:AbstractVector{<:Tuple{Number,Number}}: the vector of tuples, where each tuple is in the form Tuple{expected_output, actual_output}.

mutate!(::GeneticSearchIterator, program::RuleNode, grammar::AbstractGrammar, max_depth::Int = 2)

Mutates the program of an invididual.

mutate_random!(program::RuleNode, grammar::AbstractGrammar, max_depth::Int64 = 2)

Mutates the given program by inserting a randomly generated sub-program at a random location.

neighbourhood(iter::StochasticSearchIterator, current_program::RuleNode)

Returns a node location from the neighbourhood of the current program.

next_solution!(iter::UniformIterator)::Union{RuleNode, StateHole, Nothing}

Searches for the next unvisited solution. Returns nothing if all solutions have been found already.

priority_function(::AbstractDFSIterator, g::AbstractGrammar, tree::AbstractRuleNode, parent_value::Union{Real, Tuple{Vararg{Real}}}, isrequeued::Bool)

Assigns priority such that the search tree is traversed like in a DFS manner.

priority_function(::MLFSIterator, grammar::AbstractGrammar, current_program::AbstractRuleNode, parent_value::Union{Real, Tuple{Vararg{Real}}}, isrequeued::Bool)

Calculates the priority function of the MLFSIterator. The priority value of a tree is then the maxrulenodelog_probability within the represented uniform tree. The value is negated as lower priority values are popped earlier.

priority_function(::RandomIterator, g::AbstractGrammar, tree::AbstractRuleNode, parent_value::Union{Real, Tuple{Vararg{Real}}}, isrequeued::Bool)

Assigns a random priority to each state.

priority_function(::TopDownIterator, g::AbstractGrammar, tree::AbstractRuleNode, parent_value::Union{Real, Tuple{Vararg{Real}}}, isrequeued::Bool)

Assigns a priority value to a tree that needs to be considered later in the search. Trees with the lowest priority value are considered first.

• ``: The first argument is a dispatch argument and is only used to dispatch to the correct priority function
• g: The grammar used for enumeration
• tree: The tree that is about to be stored in the priority queue
• parent_value: The priority value of the parent SolverState
• isrequeued: The same tree shape will be requeued. The next time this tree shape is considered, the UniformSolver will produce the next complete program deriving from this shape.

probabilistic_accept(current_cost::Real, next_cost::Real, temperature::Real)

Probabilistically decides whether to accept the new program (next) based on the ratio of costs (smaller is better) between the previous and new program. Returns True if the new program is accepted, False otherwise.

Arguments

• current_cost::Real: the cost of the current program.
• next_cost::Real: the cost of the proposed program.
• temperature::Real: the temperature; not used.

probabilistic_accept_with_temperature(current_cost::Real, next_cost::Real, temperature::Real)

Returns true if the cost of the proposed program is smaller than the cost of the current program. Otherwise, returns true with the probability equal to:

\[1 / (1 + exp(delta / temperature))\]

In any other case, returns false.

Arguments

• current_cost::Real: the cost of the current program.
• next_cost::Real: the cost of the proposed program.
• temperature::Real: the temperature of the search.

probabilistic_accept_with_temperature_fraction(current_cost::Real, program_to_consider_cost::Real, temperature::Real)

Probabilistically decides whether to accept the new program (next) based on the ratio of costs (smaller is better) between the previous and new program multiplied by the temperature. Returns True if the new program is accepted, False otherwise.

Arguments

• current_cost::Real: the cost of the current program.
• next_cost::Real: the cost of the proposed program.
• temperature::Real: the current temperature

processkwarg!(keywords::Vector{Expr}, ex::Union{Expr, Symbol})

Checks if ex has a default value specified, if so it returns only the field declaration, and pushes ex to keywords. Otherwise it returns ex

propose(iter::StochasticSearchIterator, path::Vector{Int}, dict::Union{Nothing,Dict{String,Any}})

Proposes a list of programs to fill in the location provided by path and the dict.

random_fill_propose(solver::Solver, path::Vector{Int}, dict::Union{Nothing,Dict{String,Any}}, nr_random=5)

Returns a list with only one proposed, completely random, subprogram.

Arguments

• solver::solver: solver
• path::Vector{Int}: path to the location to be filled.
• dict::Dict{String, Any}: the dictionary with additional arguments; not used.
• nr_random=1 : the number of random subprograms to be generated.

select_chromosome(population::Array{RuleNode}, fitness_array::Array{<:Real})::RuleNode

Selects a chromosome (individual) from the population based on a fitness array. The function uses a fitness-proportionate selection strategy, often referred to as "roulette wheel" selection. Assumes fitness_array to be normalized already.

select_fitness_proportional_parents(population::Array{RuleNode}, fitness_array::Array{<:Real})::Tuple{RuleNode,RuleNode}

Selects two parent chromosomes (individuals) from a population based on fitness-proportionate selection. The selected parents can be used for genetic crossover in the next steps of the algorithm.

select_parents(::GeneticSearchIterator, population::Array{RuleNode}, fitness_array::Array{<:Real})

Selects two parents for the crossover.

function set_stateholes!(iter::UniformIterator, node::Union{StateHole, RuleNode})::Vector{StateHole}

Does a dfs to retrieve all unfilled state holes in the program tree and stores them in the stateholes vector.

synth(problem::Problem, iterator::ProgramIterator; shortcircuit::Bool=true, allow_evaluation_errors::Bool=false, mod::Module=Main)::Union{Tuple{RuleNode, SynthResult}, Nothing}

Synthesize a program that satisfies the maximum number of examples in the problem. - problem - The problem definition with IO examples - iterator - The iterator that will be used - shortcircuit - Whether to stop evaluating after finding a single example that fails, to speed up the synth procedure. If true, the returned score is an underapproximation of the actual score. - allowevaluationerrors - Whether the search should crash if an exception is thrown in the evaluation - maxtime - Maximum time that the iterator will run - maxenumerations - Maximum number of iterations that the iterator will run - mod - A module containing definitions for the functions in the grammar that do not exist in Main

Returns a tuple of the rulenode representing the solution program and a synthresult that indicates if that program is optimal. synth uses evaluate which returns a score in the interval [0, 1] and checks whether that score reaches 1. If not it will return the best program so far, with the proper flag

temperature(::StochasticSearchIterator, current_temperature::Real)

Returns the new temperature based on the current temperature. A higher temperature means that the algorithm will explore more.

validate_iterator(iter)

Validates the parameters of the iterator

sample(root::RuleNode, typ::Symbol, grammar::AbstractGrammar,
                      maxdepth::Int=typemax(Int))

Uniformly selects a random node of the given return type typ limited by maxdepth.

sample(root::RuleNode, typ::Symbol, grammar::AbstractGrammar, maxdepth::Int=typemax(Int))

Uniformly samples a random node from the tree limited to maxdepth.

sample(::Type{NodeLoc}, root::RuleNode, maxdepth::Int=typemax(Int))

Uniformly selects a random node in the tree no deeper than maxdepth using reservoir sampling. Returns a NodeLoc that specifies the location using its parent so that the subtree can be replaced.

StatsBase.sample(::Type{NodeLoc}, root::RuleNode, typ::Symbol, grammar::AbstractGrammar, maxdepth::Int=typemax(Int))

Uniformly selects a random node in the tree of a given type, specified using its parent such that the subtree can be replaced. Returns a NodeLoc.