Divide and Conquer, per-example synthesis

[THinnerichs]

Here in HerbSearch: a divide-and-conquer pattern

support two cases:

• find a solution program for every example (the first one suffices), and combine them into a single program
• find all solution programs for every example, select the smallest subset, and combine into a single program

The parameters of the procedure:

• problem: global specification
• iterator: iterator to run on local specification
• divide: divides global specification into a collection of local ones
  • takes in a problem
  • output a collection of problems (Vector?)
• decide: decides whether to keep a program as a solution to a specification/example
  • takes in a problem::AbstractProblem, a program::RuleNode, a mapping from local examples/specification to a set of solutions (discovered so far)
  • returns a Boolean stating whether the program should be kept as a solution to the problem
  • if we only care about finding a single solution (the first one) for an example, then this function should check if we already have it
• conquer: takes in examples/specification and a corresponding set of solutions, and produces a global program

sub_problems = divide(problem)

#keep track of 
probs_to_sols: Dict{Problem, Vector{RuleNode}} = {}

for prog in iter
    for prob in sb_problems
        keep_program = decide(prob, prog, probs_to_sols)
        
        if keep_program:
               add program to probs_to_sols under prob
    end
end

final_program = conquer(probs_to_sols)

The general loop should be in HerbSearch. (, with default implementations?)
In HerbGarden an example of splitting per-example, and combining as a decision tree (à la EUSolver)

[ReubenJ]

Possible optimization: only run a single iterator to search over programs, the evaluator then calculates the success per-program

[ReubenJ]

In discussing with @pwochner, we came across a good point to clarify: with this formulation, we're not running many searches per example or group of examples. We're just running one search and deciding whether to keep examples based on which (group of) problem(s) they solve.

Edit: which is exactly what I suggested above. Oops!