HerbSearch.jl Documentation

AbstractAddress

Abstract type for addresses. Addresses point to (combinations of) programs in the bank.

AbstractBFSIterator <: TopDownIterator

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

abstract type AbstractCostBasedBottomUpIterator <: BottomUpIterator

Abstract supertype for cost-ordered bottom-up iterators. Concrete implementations are expected to provide at least:

• get_bank(iter)
• get_solver(iter) and get_grammar(get_solver(iter))
• storage for max_cost

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.

struct AccessAddress{M} <: AbstractAddress

Address pointing to a single program in a bank.

Fields

• type

• measure

• index

• depth

• size

• new_shape

Examples

Given the simple grammar g, the following example retrieves the lone initial program (actually a UniformHole representing all terminals in the grammar g) from the bank.

g = @csgrammar begin
        Int = Int + Int
        Int = 1 | 2 | 3
end
iter = SizeBasedBottomUpIterator(g, :Int)
populate_bank!(iter)
acc = AccessAddress(:Int, 1, 1, 1, 1, false)
retrieve(iter, acc)

# output

UniformHole[Bool[0, 1, 1, 1]]

@programiterator BFSASPIterator() <: AbstractBFSIterator

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.

Constraints on uniform trees are enforced in ASP, making use of Clingo. Behavior should otherwise match that of AbstractBFSIterators.

@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.

mutable struct BankEntry{R<:AbstractRuleNode} <: HerbSearch.AbstractBankEntry

Describes a entry in the program bank of a bottom-up iterator. Holds a program and a flag describing whether the entry is new. The flag is used for calculating the new horizon.

For access use get_program(entry) and is_new(entry).

abstract type BottomUpIterator <: ProgramIterator

A type of iterator that maintains a bank of (executable) programs and iteratively explores larger programs by combining the ones in the bank.

Like other ProgramIterators, BottomUpIterators enumerate programs from a context-free grammar starting at Symbol sym with respect to the grammar up to a given depth and a given size.

The central concept behind this interface is an address (AbstractAddress). Addresses are simply pointers into the bank. Since the bank is often a nested container (ex: Dict{Key,Dict{Key,...}}), the addresses usually have multiple components. The first components indexes the top-most level of the bank, the second indexes, the next level, etc. Program combinations can be expressed as a special address (CombineAddress) that contains one or more programs and an operator. For example: combining the programs 1 + x and x * x with the + operator results in the program (1 + x) + (x * x).

The interface for bottom-up iteration is defined as follows.

• get_bank: get the iterator's bank
• populate_bank!: initialize the bank with the terminals from the grammar and return the resulting AccessAddresses
• get_measure_limit: describes the maximum limit with respect to the measure defined.
• combine: combine the existing programs in the bank into new, more complex programs via CombineAddresses
• add_to_bank!: possibly add a program created by the combine step to the bank
• retrieve: retrieve the program from the bank given an AbstractAddress

A generic implementation (SizeBasedBottomUpIterator) is given with a bank that is indexed based on the program size, meaning that each level of the bank has programs represented by the same number of nodes. Because the implementation works using an arbitrary grammar, the bank also must be indexed on the type of the programs to allow the combine step to avoid constructing programs that do not adhere to the grammar.

abstract type BottomUpState

State that helps us keep track where we are while iterating through program space. More precisely, it help to keep track and switch between the program combinations of the same complexity and the next level of complexity.

The following methods must be implemented:

• remaining_combinations: returns an iterable of program combinations that need to be explored

• state_tracker: returns the state tracker for the combine method

• new_combinations!: assign new combinations to the state

• new_state_tracker!: assign new state tracker to the sate

struct CombineAddress{N} <: AbstractAddress

Address pointing to a combination of N programs from a bank to be combined using op.

Fields

• op: The root of the AST for the combined program

• addrs: The addresses to combine to form the new program

Examples

Given the grammar g, the following example retrieves a new program from the bank. The new program is a UniformHole that represents all programs of the form □ + □ where □ is any of the Int terminals in the grammar.

g = @csgrammar begin
        Int = Int + Int
        Int = 1 | 2 | 3
end;
iter = SizeBasedBottomUpIterator(g, :Int);
populate_bank!(iter);
acc = CombineAddress(
        UniformHole([1, 0, 0, 0]),
        [AccessAddress(:Int, 1, 1, 1, 1, false), AccessAddress(:Int, 1, 1, 1, 1, false)]
);
retrieve(iter, acc)

# output

UniformHole[Bool[1, 0, 0, 0]]{UniformHole[Bool[0, 1, 1, 1]],UniformHole[Bool[0, 1, 1, 1]]}

ConstraintStyle

Abstract type representing the family of constraint styles present in Herb.

There are currently two styles, namely:

• HerbStyle: The default, this corresponds to iterators that enforce constraints using the propagation implemented in HerbConstraints.
• ASPStyle: Corresponds to iterators that enforce constraints using ASP via Clingo.

See constraint_style.

CostBasedBottomUpIterator

A bottom-up iterator which enumerates program by increasing cost.

The bank is ordered by measures, i.e., the cost, just like the shape-based BUS but of type Float64. In contrast to the shape-based BUS implementations, each BankEntry holds a single program, not a shape. While is worse for propagating constraints, this is significantly faster for checking observational equivalence.

In CostBasedBottomUpIterator, we assume the costs to be compositional, i.e., the cost of a program is the sum of the costs of the sub-rules. This also holds when constructing a new program as the combination of existing programs in the bank.

CostBasedBottomUpIterator implements and propagates observational equivalence by default. To enable provide a program_to_outputs function, which takes a RuleNode and returns a concrete program. To check for observational equivalence, the outputs are hashed, compared to the bank of seen outputs, and added if not seen before.

CostBasedBottomUpIterator keeps an enumeration window, similar to BottomUpIterator.

@programiterator DFSASPIterator() <: AbstractDFSIterator

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

Constraints on uniform trees are enforced in ASP, making use of Clingo. Behavior should otherwise match that of AbstractDFSIterators.

@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.

 DepthBasedBottomUpIterator

A bottom-up iterator with a bank indexed by the size of a program.

ExpandFailureReason

Abstract type representing the different reasons why expanding a partial tree failed.

Currently, there are two possible causes of the expansion failing:

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

mutable struct GenericBUState <: BottomUpState

Generic bottom-up search state. Tracks the current state of the search procedure.

Fields

• combinations: A vector of program combinations to construct new programs from

• combine_stage_tracker: The state that the combine function can manipulate.

• current_uniform_iterator: The current uniform iterator that the bottom-up search is iterating through

• starting_node: The starting node of the search

• last_horizon: The last horizon that was considered. Gives a lower bound on solutions to enumerate.

• new_horizon: The current horizon, enumerating only programs with measure strictly smaller than the new horizon.

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.

struct MeasureHashedBank{M,T,O<:AbstractVector{<:T},R<:AbstractRuleNode}

A bank that groups programs by a measure of type M` (e.g., depth, size, etc.) by hashing them.

abstract type ProgramIterator

Abstract iterator type for all search strategies.

See @programiterator for details on constructing iterators or defining new strategies.

@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.

 SizeBasedBottomUpIterator

A bottom-up iterator with a bank indexed by the size of a program.

 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 UniformASPIterator

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

• solver: the ASP 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 unvisited branches.
• nsolutions: number of solutions found so far.

UniformASPIterator(solver::ASPSolver, outeriter::ProgramIterator)

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

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 unvisited 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

Create a new type T<:ProgramIterator that includes the common fields of ProgramIterators and some useful constructors.

Fields

• solver
• start_symbol
• initial_node
• grammar
• max_depth
• max_size

Syntax accepted by the macro is as follows (anything enclosed in square brackets is optional):

@programiterator [mutable] <IteratorName>(
<arg₁>,
...,
<argₙ>
) [<: <SupertypeIterator>]

The mutable keyword determines whether the declared struct is mutable. SupertypeIterator must be an abstract type <:ProgramIterator. 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.

Example

julia> abstract type SomeIteratorFamily<:ProgramIterator end

julia> @programiterator mutable SomeCustomIterator(a_param::Int) <: SomeIteratorFamily;

function Base.collect(iter::BottomUpIterator)

Return an array of all programs in the BottomUpIterator.

function Base.collect(iter::TopDownIterator)

Return an array of all programs in the TopDownIterator.

iterate(
    iter::BottomUpIterator,
    state::GenericBUState
) -> Union{Nothing, Tuple{AbstractRuleNode, Union{Nothing, GenericBUState}}}

The second call to iterate uses get_next_program to retrive the next program from the GenericBUState and - if it is nothing, then it returns nothing; we stop - if it is indexed by `` then it has the program that is already in the bank; just return AccessAddress - if it is indexed by CombineAddress then it - it calls construct_program to construct the program - call the add_to_bank! function to add it to the bank - if it is added to the bank, then it return the program and the new state - if it is not added to the bank, e.g., because of observational equivalence, then it calls itself again with the new state

iterate(
    iter::BottomUpIterator
) -> Union{Nothing, Tuple{AbstractRuleNode, Union{Nothing, GenericBUState}}}

Initial call of the bottom-up iterator.

Populate the bank with initial programs.

Return the first program and a state-tracking GenericBUState containing the remaining initial programs and the initialstate for the combine function

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.

Base.length(iter::UniformASPIterator)

Counts and returns the number of 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, 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.

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

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

size(a::AccessAddress) -> Int64

HerbConstraints.get_grammar(pi::ProgramIterator)

HerbConstraints.get_max_depth(pi::ProgramIterator)

Get the maximum depth of the programs that the program iterator will return.

HerbConstraints.get_max_size(pi::ProgramIterator)

Get the maximum size of the programs that the program iterator will return.

HerbConstraints.get_starting_symbol(pi::ProgramIterator)

Get the starting symbol of the iterator.

Example

Given an iterator that is initialized with :Int as the starting symbol, the root of each of the programs returned from the iterator will have the same type, and this will match the symbol returned by get_starting_symbol.

julia> g = @csgrammar begin
           Int = length(List)
           Int = Int + Int
           List = x
       end;

julia> it = BFSIterator(g, :Int; max_depth=4);

julia> programs = rulenode2expr.((freeze_state(p) for p in it), (g,))
5-element Vector{Expr}:
 :(length(x))
 :(length(x) + length(x))
 :(length(x) + (length(x) + length(x)))
 :((length(x) + length(x)) + length(x))
 :((length(x) + length(x)) + (length(x) + length(x)))

julia> get_starting_symbol(it)
:Int

Note that all of the programs will return an Int, matching the type returned by get_starting_symbol(it).

depth(a::AccessAddress) -> Int64

_calc_measure(
    _::DepthBasedBottomUpIterator,
    combination::Tuple{Vararg{AccessAddress}}
) -> Any

Calculates the measure given a combination of children. Does not take the parent cost into account.

_calc_measure(
    iter::HerbSearch.AbstractCostBasedBottomUpIterator,
    children::Tuple
) -> Any

Given the children of a node, returns the accumulated cost of the children, i.e., the sum of their respective costs.

_calc_measure(
    _::SizeBasedBottomUpIterator,
    combination::Tuple{Vararg{AccessAddress}}
) -> Any

Calculates the measure given a combination of children. Does not take the parent cost into account.

_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.

_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

_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.

_hash_outputs_to_u64vec(outs_any::Vector) -> Vector{UInt64}

Hashes a vector of outputs. Hashes to UInt64 by default.

_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.

_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

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

add_to_bank!(
    _::BottomUpIterator,
    _::AccessAddress,
    _::AbstractRuleNode
) -> Bool

Always return true. Adding an AccessAddress to the bank only happens in the first iteration with terminals.

add_to_bank!(
    iter::BottomUpIterator,
    program_combination::CombineAddress,
    program::AbstractRuleNode
) -> Bool

Add the program (the result of combining program_combination) to the bank of the iter.

Return true if the program is added to the bank, and false otherwise.

For example, to implement an iterator with observational equivalence, the function might return false if the program is observationally equivalent to another program already in the bank.

add_to_bank!(
    iter::HerbSearch.AbstractCostBasedBottomUpIterator,
    addr::CombineAddress,
    prog::AbstractRuleNode
) -> Bool

Add the program (the result of combining program_combination) to the bank of the iter.

Return true if the program is added to the bank, and false otherwise.

This add_to_bank! checks for observational equivalence.

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.

calc_measure(
    iter::HerbSearch.AbstractCostBasedBottomUpIterator,
    rn::AbstractRuleNode
) -> Any

Calculates the cost of a CombineAddress given a concrete program in form of a RuleNode.

calc_measure(
    iter::HerbSearch.AbstractCostBasedBottomUpIterator,
    a::CombineAddress
) -> Any

Calculates the cost of a CombineAddress, which refers to a concrete program.

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

Wrapper around _calculate_cost.

combine(
    iter::BottomUpIterator,
    state::GenericBUState
) -> Tuple{DataStructures.PriorityQueue{AbstractAddress, Number}, GenericBUState}

Combine the programs currently in iter's bank to create a new set of programs. Constructs all tuples of combinations of programs joined by an operator. To ensure that we only consider new programs, the tuple of existing programs has to contain at least one new program. New programs are represented by CombineAddresses, i.e., operators over a tuple of existing programs, represented with AccessAddress.

Combine also calculates the new enumeration window, i.e. sets lasthorizon to newhorizon and calculates newhorizon via `computenewhorizon. Enqueues ALL found combinations intostate.combinations` that are bigger than lasthorizon, but will NOT prune solutions that exceed the current window, i.e., new_horizon.

combine(
    iter::HerbSearch.AbstractCostBasedBottomUpIterator,
    state::GenericBUState
) -> Tuple{DataStructures.PriorityQueue{AbstractAddress, Number}, GenericBUState}

Combine the programs currently in iter's bank to create a new set of programs. Constructs all tuples of combinations of programs joined by an operator. To ensure that we only consider new programs, the tuple of existing programs has to contain at least one new program. New programs are represented by CombineAddresses, i.e., operators over a tuple of existing programs, represented with AccessAddress.

Combine also calculates the new enumeration window, i.e. sets lasthorizon to newhorizon and calculates newhorizon via `computenewhorizon. Enqueues ALL found combinations intostate.combinations` that are bigger than lasthorizon, but will NOT prune solutions that exceed the current window, i.e., new_horizon.

compute_new_horizon(iter::BottomUpIterator) -> Any

Compute the new horizon using the current contents of the bank. The newhorizon is an exclusive upper bound on the window we currently try to enumerate, with the inclusive lower bound being the lasthorizon. Both are stored in the BottomUpState.

Definition:

• Consider all non-terminal shapes (operators).
• For each shape, form the cheapest child tuple that uses

at least one new child (as marked by the bank’s is_new flags) and all other children at their cheapest existing measures (per return type).

• The next horizon is the minimum, over those shapes, of

1 + _calc_measure(children_tuple).

_calc_measure(children_tuple) is the sum of the children measures for SizeBasedBottomUpIterator and the maximum of the children measures for DepthBasedBottomUpIterator.

Notes:

• “Newness” is derived from the bank’s is_new flags on entries, not from horizons.
• This function does not mutate the bank or the state (other than reading state).

compute_new_horizon(
    iter::HerbSearch.AbstractCostBasedBottomUpIterator
) -> Any

Compute the new horizon using the current contents of the bank. The newhorizon is an exclusive upper bound on the window we currently try to enumerate, with the inclusive lower bound being the lasthorizon. Both are stored in the BottomUpState.

Definition:

• Consider all non-terminal shapes (operators).
• For each shape, form the cheapest child tuple that uses

at least one new child (as marked by the bank’s is_new flags) and all other children at their cheapest existing measures (per return type).

• The next horizon is the minimum, over those shapes, of

operator_cost + _calc_measure(children_tuple).

Note that this differs from compute_new_horizon(iter::BottomUpIterator), as operate over singular programs, not shapes.

Notes:

• “Newness” is derived from the bank’s is_new flags on entries, not from horizons.
• This function does not mutate the bank or the state (other than reading state).

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.

constraint_style(it)

Get the constraint style of an iterator.

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.

convert_to_rulenode(tree::AbstractRuleNode)::AbstractRuleNode

Converts an AST and replaces each hole with a filled domain (one rule is true) to a RuleNode

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]

update_rule_indices!(iter::UniformASPIterator,tree::Union{RuleNode,UniformHole,StateHole}, mapping::Dict{Int64,Int64}, current_index::Int64)

Iterates through the tree, and updates the domains of UniformHoles according to the updates given in mapping (nodeindex => ruleindex). Use current_index to traverse through the tree and update the correct nodes.

fitness(::GeneticSearchIterator, program, results)

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

generate_branches(iter::UniformASPIterator)::Vector{Branch}

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)

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_bank(iter::BottomUpIterator) -> Any

Get the problem bank from the BottomUpIterator, iter.

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

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

get_entries(mhb::MeasureHashedBank, measure, type)

Retrieve all bank entries in bank mhb with a certain type and measure.

get_index(a::AccessAddress) -> Int64

Get the index of address a.

get_measure(a::AccessAddress) -> Any

Get the measure (depth, size, etc. depending on the bank) of address a.

Sets the maximum value of a measure for program enumeration. For example, if the limit is 5 (using depth as the measure), all programs up to depth 5 are included.

get_measure_limit(
    iter::HerbSearch.AbstractCostBasedBottomUpIterator
) -> Any

Returns maximum cost, which is set at init. If not defined, the maximum cost is set to Inf.

Sets the maximum value of a measure for program enumeration. For example, if the limit is 5 (using depth as the measure), all programs up to depth 5 are included.

get_measures(mhb::MeasureHashedBank)

Retrieve the measures present in the bank mhb with a certain type.

get_next_program(
    iter::BottomUpIterator,
    state::GenericBUState
) -> Union{Tuple{Nothing, Nothing}, Tuple{AbstractAddress, Union{Nothing, GenericBUState}}}

Return the next program to explore and the updated BottomUpState.

• If there are still remaining programs from the current bottom-up iteration to explore (state.combinations), it pops the next one if in the current horizon window.
  • If last_horizon == new_horizon, exhaust the PQ at that value before advancing.
• Otherwise, it calls the combine function again, and processes the first returned program.

programs(mhb::MeasureHashedBank, measure, type)

Retrieve the programs in bank mhb with a certain type and measure.

get_return_type(a::AccessAddress) -> Symbol

Get the type of address a.

get_rule_cost(
    iter::HerbSearch.AbstractCostBasedBottomUpIterator,
    rule_idx::Int64
) -> Any

Given an iter and the rule index, returns the current cost of that index, by getting the respective element of current_costs.

get_solver(pi::ProgramIterator)

Get the program iterator solver.

get_types(mhb::MeasureHashedBank, measure)

Retrieve the types of programs in bank mhb.

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.

init_combine_structure(
    _::BottomUpIterator
) -> Dict{Any, Any}

Return the initial state for the first combine call.

is_observationally_equivalent(
    iter::HerbSearch.AbstractCostBasedBottomUpIterator,
    program::RuleNode,
    rettype::Symbol
) -> Bool

Checks a program for observational equivalence by evaluating the program, hashing the outputs and checking them against the set of seen outputs.

Returns true, if the program was seen already. Returns false, if the program was not seen yet. Adds the output signature to the set of seen outputs in that case.

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}.

measure_type(iter::BottomUpIterator) -> Any

Return the measure type M used by the bank of the iterator.

measure_type(
    _::HerbSearch.MeasureHashedBank{M, R<:AbstractRuleNode}
) -> Any

Return the measure type M used by this MeasureHashedBank{M,R}.

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.

new_address(
    iter::BottomUpIterator,
    program_combination::CombineAddress,
    program_type::Symbol,
    idx
) -> AccessAddress

Create an AccessAddress derived from the program_combination CombineAddress and program_type.

next_solution!(iter::UniformASPIterator)

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

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

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

populate_bank!(
    iter::BottomUpIterator
) -> Vector{AccessAddress}

Fill the bank with the initial, smallest programs, likely just the terminals in most cases. Return the AbstractAddresses to the newly-added programs.

populate_bank!(
    iter::HerbSearch.AbstractCostBasedBottomUpIterator
) -> Vector{AccessAddress}

Fill the bank with the concrete programs in the grammar, i.e., the terminals. Returns the AccessAddresses of the newly-added programs.

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

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.

retrieve(
    iter::BottomUpIterator,
    address::AccessAddress
) -> AbstractRuleNode

Retrieve a program located at address from the iter's bank.

retrieve(
    iter::BottomUpIterator,
    address::CombineAddress
) -> RuleNode

Construct a program using the CombineAddress address and the iter's bank and return it.

retrieve(
    iter::HerbSearch.AbstractCostBasedBottomUpIterator,
    a::CombineAddress
) -> RuleNode

Retrieve a program using a CombineAddress. Overwrites the parent function, as AbstractCostBasedBottomUpIterator operates over concrete trees, not uniform trees.

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::UniformASPIterator, 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.

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

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.

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

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

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(::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.