Bottom up iterator

[ReubenJ]

Just to trigger CI for now...

[codecov]

Codecov Report

Attention: Patch coverage is 93.22034% with 16 lines in your changes missing coverage. Please review.

Project coverage is 32.59%. Comparing base (1876d08) to head (5ed48ef).
Report is 25 commits behind head on master.

Files with missing lines	Patch %	Lines
src/stochastic_iterator.jl	0.00%	12 Missing ⚠️
src/top_down_iterator.jl	0.00%	3 Missing ⚠️
src/bottom_up_iterators/bottom_up_iterator.jl	97.36%	1 Missing ⚠️

Additional details and impacted files

@@             Coverage Diff             @@
##           master     #107       +/-   ##
===========================================
- Coverage   67.35%   32.59%   -34.76%     
===========================================
  Files          21       24        +3     
  Lines         729      908      +179     
===========================================
- Hits          491      296      -195     
- Misses        238      612      +374     

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

[sebdumancic]

non-urgent thing to think about: should we leave bank and data as Any, or should we introduce some subtyping? I assume the bank will always be either a Dict so that programs are ordered over their type, or some kind of priority as in Brute. If we figure out more precise type, the code might be faster.

[TudorMagirescu]

I have decided to introduce two new abstract types: BUDepthBank and BUDepthData that the concrete iterators will need to extend. Please let me know what you think about this.

[sebdumancic]

does it make sense to make the bank type Dict{Symbol, Dict{Int,Vector{RuleNode}}}? so that you can also index it over depth for easier fetching?

[THinnerichs]

@TudorMagirescu:
Could you merge the uniform iterator branch into this one and check what changes we should keep? Then I can give a full review of both including some hints for the design patterns we discussed during the Hackathon.

[sebdumancic]

I have been going over our struggles to define a clean interface for the bottom-up search. The situation with two iterators is quite clunky, and avoiding the inner iterator overloads the memory. We have to make it easy for people to implement various versions rather quickly.
Here is my proposal that (hopefully?) avoids our previous struggles.

Here is a proposal for a generic bottom-up iterator (the capitalized functions are the interface):

bank <- INITIALISE_BANK(iter)
POPULATE!(iter, bank, grammar)
to_combine, cont <- COMBINE(iter, bank, grammar, nothing)

while cont != nothing
     for prog in construct(to_combine)
          # prog is a uniform tree
          return prog
          address <- NEW_ADDRESS([parent addresses])
          ADD!(iter, prog, bank, address)
          to_combine, cont <- COMBINE(iter, bank, grammar, cont)
     end
end

The interface functions do the following:

• INITIALISE_BANK: create the empty data structure for the bank
• POPULATE!: populates the bank with the initial programs
• COMBINE: returns the addresses (in the bank) of the programs to combine next and an arbitrary state to keep track of combinations so far. Returning the addresses instead of programs allows flexibility and customizability without overwhelming the memory. If the state is nothing, then the iteration stops. The generic combine function takes the addresses and constructs a program combining the programs indicated by those addresses (this is not a functionality that a user needs to implement).
• NEW_ADDRESS: computes the address (in the bank) of a newly constructed program, from the parents' addresses
• ADD!: adds a program into the bank at the given address

This interface would allow us to implement many versions of bottom-up search easily:

• standard depth-indexed bottom-up:
  • the bank is a dict where the depth is the key and values are the programs with that depth
  • the COMBINE function combines the biggest entry in the bank with all the others
• size-indexed bottom-up:
  • the bank is a dict with keys being the size of programs and the values are programs of that size
  • the COMBINE function combines the programs of the biggest size with all the others
• Brute (execution-based distance)
  • the bank is a priority queue with the priority function being the distance to the desired output
  • the COMBINE function takes the best program from the queue and combines it with single-step refinements
• cost-based search:
  • the bank is either a priority queue ordered by cost or a dict where the costs are the keys
  • the COMBINEfunction
• Eco/Heap/Bee search
  • the bank is a nested dictionary with cost tuples
  • the COMBINEfunctions gradually increases the cost
• beam search
  • the bank is a priority queue (of fixed size) ordered by how good programs are (for whatever metric) and a collection of simple programs
  • the COMBINE function extends each program in a queue with simple extensions

Optimisations are also easy to do:

• observational equivalence: do it within the ADD! functions and store the previous executions in the bank
• bank cleanup: also do it in the ADD! function?
• want to store some additional information: extend the bank to contain that information, and use it in theCOMBINE! function, maintain the information within the ADD! function

Issue: how to handle returning individual programs when manipulating uniform trees within the iterator