On these respective branches, I am worked on two new major components:
A constraint propagation solver
New hole types
I am replacing propagate_constraints with a new constraint Solver struct. The goal is to increase the inference of constraint propagators while reducing the number of propagations needed. Currently constraint solving is integrated in the top down iterator, but the new solver should also be compatible with any type of program iterator. This means that all program iterators should be rewritten to be compatible with the constraint solver. The idea is that iterators must manipulate program trees through the solver’s API so the propagation of the constraints can happen under the hood. For example:
"""
substitute!(solver::Solver, path::Vector{Int}, new_node::AbstractRuleNode)
Substitute the node at the `path`, with a `new_node`
"""
function substitute!(solver::Solver, path::Vector{Int}, new_node::AbstractRuleNode)
#...
end
"""
fill_hole!(solver::Solver, path::Vector{Int}, rule_index::Int)
Fill in the hole located at the `path` with rule `rule_index`.
It is assumed the path points to a hole, otherwise an exception will be thrown.
It is assumed rule_index ∈ hole.domain, otherwise an exception will be thrown.
"""
function fill_hole!(solver::Solver, path::Vector{Int}, rule_index::Int)
#...
end
The Hole struct will be split up into two new concrete hole structs: FixedShapedHole and VariableShapedHole. The main difference between these two structs is that the domain of a fixed shaped hole contains only rules of exactly the same child types (e.g. A -> A + B and A -> A * B have the same childtypes. A -> A + A has different childtypes). The advantage of fixed shaped holes is that child nodes can already be instantiated before the concrete rule of the parent is known. This reduces the amount of trees that need to be stored in memory and can be exploited for stronger inference during constraint propagation.
Large PR involving 4 repositories:
HerbSearch@solverHerbConstraints@solverHerbCore@holes-typesHerbGrammar@holes-types (small changes)On these respective branches, I am worked on two new major components:
A constraint propagation solver
New hole types
I am replacing
propagate_constraintswith a new constraintSolverstruct. The goal is to increase the inference of constraint propagators while reducing the number of propagations needed. Currently constraint solving is integrated in the top down iterator, but the new solver should also be compatible with any type of program iterator. This means that all program iterators should be rewritten to be compatible with the constraint solver. The idea is that iterators must manipulate program trees through the solver’s API so the propagation of the constraints can happen under the hood. For example:Holestruct will be split up into two new concrete hole structs:FixedShapedHoleandVariableShapedHole. The main difference between these two structs is that the domain of a fixed shaped hole contains only rules of exactly the same child types (e.g.A -> A + BandA -> A * Bhave the same childtypes.A -> A + Ahas different childtypes). The advantage of fixed shaped holes is that child nodes can already be instantiated before the concrete rule of the parent is known. This reduces the amount of trees that need to be stored in memory and can be exploited for stronger inference during constraint propagation.