parametrized_dag_factory behaviour

[sylvainbonnot]

Non intuitive behavior

The behaviour of parametrized_dag_factory
is not too intuitive: one gets the following

from meshed import code_to_dag
from meshed.dag import parametrized_dag_factory

@code_to_dag
def dag1():
    a = criss(x,y)
    b = cross(aa, bb)
    c = apple(a, b)


dag_factory1 = parametrized_dag_factory(dag1, 'a')
assert str(Sig(dag_factory1(x=1,y=2))) == '(b)'  # but we DO NOT WANT THAT.
assert str(Sig(dag_factory1(x=1,y=2))) != '(aa, bb)'  # but we DO WANT THAT.

Inconsistent behavior

Also, when a function in the dag has no params, the parametrized_dag is not consistent with the above:

@code_to_dag
def dag2():
    a = criss()
    b = cross(aa, bb)
    c = apple(a, b)

dag_factory2 = parametrized_dag_factory(dag2, 'a')
assert str(Sig(dag_factory2())) == '(a, b)'
# <Sig (a, b)>  # to be consistent with the above, it should be Sig (b)

[thorwhalen]

Great observations and I agree on both:

• Indeed, my intent was that the first be Sig (aa, bb)
• Consistency is crucial. Without any clear argument or narrative supporting it, I'd put forth an hypothetical rule of thumb: (Behavioral) consistency trumps intuitiveness.

This is a first draft of the function, so maybe it's an actual bug that we can resolve. Unfortunately, there's a chance it may be a bit more involved than that.

Maybe it's a bug else where (ancestors? partial?).

Or maybe, and that would suck, it's one of those "can't satisfy all expectations" kind of problem. Example; the non-obvious C3 linearization solution to getting a method-resolution-order (MRO) that would preserve the order of classes as defined by the programmer, while also preserving the monotonicity of the inheritance graph.

Either way, I'm moving this to a discussion so we can figure out what behavior we actually want (we now have two examples of what we do not want.

[thorwhalen]

The first problem comes from a bug (or an "unexpected behavior" -- TBD) of __getitem__.

computation_dag = dag1['a':]
computation_dag.dot_digraph()

We have:

assert str(Sig(computation_dag)) == '(a, b)'

which translates to (b) when a is removed (on purpose -- see if you agree) when doing the partial.

Now, we need to go back to the definition of __getitem__ and see if we agree with this dag1['a':].
It seems like dag1['a':] gets the subdag goind down, from a, picking up b because it needs it to compute apple.
I can see the rationale, but not sure I agree.
If we made that choice, it's probably because that was the behavior that was intuitive for the context we first made __getitem__ for.

So either:

• We revise the definition of __getitem__. We should bare in mind that this might be a bit disruptive, so we should do that only if we really determine that the choice we made in the current one was not a "good" one. One argument against the current behavior being a "good" one is that dag[:a] + dag[a:] != dag.
• We keep the current __getitem__ behavior, but add the ancestors to "complete" the graph we actually want.

[sylvainbonnot]

About the definition of dag[:a] being wrong: any definition of dag[:a] that uses only "ancestors" of a will fail to satisfy dag[:a] + dag[a:] != dag.
A simple dag to keep in mind is [0-> a ->2, 0 ->1], that is:

  graph TD;
      0-->a;
      a-->2;
      0-->1;

Loading

A possible definition that would satisfy dag[:a] + dag[a:] != dag is:

dag[:a] is the subdag made of all the nodes in a together with all the nodes that can be joined to a node in a by at least one undirected path finishing with an edge arriving in a.

Conversely,

dag[a:] is the subdag made of all the nodes in a together with all the nodes that can be joined to a node in a by at least one undirected path starting with an edge exiting a.

[thorwhalen]

So, what we've decided here is that the dag[:a] + dag[a:] != dag requirement makes sense for total orders, it doesn't really have a canonical extension/generalization to partial orders.

Our current definition of DAG.__getitem__ satisfies the equation when the DAG is linear (therefore defining a total order), and that is sufficient for us for now since we don't know if there is a better definition for our context.

[sylvainbonnot]

This issue is linked to two others:

• roll_in_orphaned_dag : a subdag that is fully computed might be "erased" by simply leaving its leaves apparent
• the question of subdag subtraction: ideally one wants to base it on operations that are purely graph-theoretical. A subgraph subtraction is now done in itools_subtraction