[fud2] Implement More Advanced Planners

[jku20]

Problem Statement

This is partially redundant to a comment on #2113 but that's okay. Read that for more information on current implemented planners and more words about this problem in general.

fud2's ops can be viewed as functions from one set of states to another set of states. The hypergraph of #1958 can be viewed as a solution to this new program synthesis problem, where ops have to be composed in a straight-line program (from here on called a "plan") which takes as input a given set of types and returns a new desired set of types, using a given set of ops.

The goal is a function which creates plans, a "planner," which can deal with large numbers of ops possibly, but probably not forming a dense hypergraph.

Current Solutions

• A simple planner based on enumerating all sequences of ops currently exists. This works with the current shape and number of ops, but will not scale much further.

• A simple (non-complete) planner based on e-graphs and implemented via egg.

Proposals

A few people proposed adapting the solution based on e-graphs to Datalog. This needs to be tested. I'm personally a bit skeptical that just putting the current solution based on e-graphs into Datalog will do much better than the current solution implemented with egg. Both solutions, if they are to be complete, require generating a lot of invalid programs. That would need to be stopped.

Of course any other new ideas are welcome.

Implementing Planners

A planner is an implementation of FindPlan. For examples see, enumerative_planner.rs or egg_planner.rs.

Planners should then be added to tests in fud-core/tests/tests.rs and added as a command line option in cli.rs.