Adding support for `include` and `slot` to graph safety

This is a log of thoughts and issues I encounter trying to implement that (see google/breadboard-ai#38):

Currently the safety check is over the graph just after it is loaded. include and hence slot nodes are ignored.

Just evaluating the included graphs in isolation isn't going to work, as the safety constraints interact with the parent graph. For instance imagine a loop in the main graph (like in a React agent, see google/labs-prototypes#52), which means the graph's input node's constraint are in part tied to the output node's constraints.

(1) One version that could work: Just incrementally evaluating the graph at each step. Abort when a contradiction is encountered. This is tempting, but not a great long term solution:

Runtime errors that could be foreseen
If there was another way upstream could have been laid out to avoid the safety issue, now it's too late As long as we write graphs by hand and thoroughly test them, this isn't too bad. But for automated graph creation, it would be really nice to give "compile time" errors that the graph generator can fix by rearranging the graph.

(2) The next best option is re-evaluate the graph whenever an include or slot node is encountered, after adding the new graph to the prior full graph. This still means a runtime error, but it's a little more eager and consistently triggering. A complications we run into: ID namespaces are per graph, and so there could be name collisions. This requires changes to the current code, but shouldn't be difficult.

(3) We could then improve on that by trying to eagerly include all graphs before execution, basically recursively looking for all include and slot nodes and just loading these graphs. We have to be cautious about infinite loops, but otherwise this should work. Problems with this:

Load and parse each graph twice? Rearrange board's implementation of include and slot to do that front loaded as well?
Doesn't work, with dynamic selection of graphs, e.g. to support google/breadboard-ai#48

(4) The most elegant solution to address the second concern (dynamic graphs) would be to effectively implement parametric polymorphism for graphs: That is, infer from where graph sits in the graph, including what graphs are being slotted in, what constraints it must have, then ensure that any code producing graphs that should be included only outputs valid types. This would support any number of complex scenarios, including most recursion cases and where constraints come indirectly via the slotted graphs.

As part of ensuring that only valid graphs can be added, the system would either have to convince itself for static inputs or perform a runtime test at the right point. Examples:

When loading graphs, perform the check. But also, provide a tool that allows for offline verification of all dependencies. The advantage over failing at runtime is that such tests could become part of a build system.
When selecting among many graphs, like e.g. google/breadboard-ai#48 suggests, make it a filtering criteria for retrieval. A very general solution here might be possible with some offline calculations ahead of time.
When generating graphs, perform a check at runtime. But this isn't just about includes, this is the bigger idea of giving the generator safety feedback to iterate on before executing such a graph.
- A new twist though is that feedback might be more nuanced, e.g. conveying that executing this graph will lower the trust for all subsequent steps and encouraging the generator to come up with a better solution.

My sense is to start with (2) and then go straight to (4), which subsumes the best of (3) as subsequent steps. Instead of implementing (1), I'm tempted to just implement fuse instead to get React agents working (see google/labs-prototypes#52).

breadboard-ai / breadboard

Adding support for `include` and `slot` to graph safety #42