How to represent a while loop

[samwaseda]

In semantikon, I managed to parse a function without if, for and while to create a workflow (cf. this file). The dict-representation is based on this one. Now, I would like to extend it to if, for and while. For this, let's take a look at the following workflow:

def add(x, y):
    return x + y

def my_workflow(x, y):
    while x < 0:
        x = add(x, y)
        y = add(x, y)
    return y

(Note: This function has no particular meaning, except for having a while loop)

According to the AST syntax, this while loop has two components: test and body. As the names already sort of suggest, test is the part after while, i.e. x < 0 and body is the indented part after while. In principle, the body can be considered as a workflow itself, knowing that it's a cyclic graph and therefore should not be put in the same way as a normal workflow, and the whole while loop can be wrapped as a nested node. In this case, my_workflow can therefore be considered to be a workflow containing one step:

def my_workflow(x, y):
    y = injected_while_loop(x, y)
    return y

From the technical point of view, we still have to make sure that the inputs and the outputs are correctly identified. In this case the inputs are x and y, and the output is y. I think that's easily achievable. The bigger question is how to represent it. An obvious choice is to represent it just like a normal node and mark it with an additional tag, such as "type", i.e. the one above could be represented as:

{
    'inputs': {'x': {}, 'y': {}},
    'outputs': {'result': {}},
    'nodes': {
        'injected_while_loop_0': {
            'type': 'while',
            'test': 'x < 0',
            'inputs': {'x': {}, 'y': {}},
            'outputs': {'result': {}},
            'nodes': {
                'inputs': {'x': {}, 'y': {}},
                'outputs': {'result': {}},
                'nodes': {
                    'add_0': {
                        'function': <function __main__.add(x, y)>,
                        'inputs': {'x': {}, 'y': {}},
                        'outputs': {'output': {}}
                    },
                    'add_1': {
                        'function': <function __main__.add(x, y)>,
                        'inputs': {'x': {}, 'y': {}},
                        'outputs': {'output': {}}
                },
            'data_edges': [
                ['inputs.x', 'add_0.inputs.x'],
                ['inputs.x', 'add_1.inputs.x'],
                ['inputs.y', 'add_0.inputs.y'],
                ['inputs.y', 'add_1.inputs.y'],
                ['add_1.outputs.output', 'outputs.y']
            ],
            'label': 'injected_while_loop'
        },
    'data_edges': [
        ['inputs.x', 'injected_while_loop_0.inputs.x'],
        ['inputs.y', 'injected_while_loop_0.inputs.y'],
        ['injected_while_loop_0.outputs.output', 'outputs.result']
    ],
    'label': 'my_workflow'
}

And while writing this, I started feeling more and more that this is the right way to go. Anyway suggestions are welcome.

[liamhuber]

I would suggest to transition the 'test' to also be a node, with the restriction that it must return a single boolean. Naively I hope you can then also include the test node as a source/target in the edges, but I'm just on mobile and didn't actually dig through your workflow dict in detail.

Mostly what I have in mind here is to try to set up a system where we aren't simply execing raw code stored in the workflow file, ever, in any realization of the workflow. Maybe I've misunderstood how the test would be parsed though.

[liamhuber]

Is there a typo here? "injected_while_loop_0" doesn't have inputs and outputs fields directly, but has inputs and outputs nested inside its own "nodes" field -- should the io and inter-child edges of "injected_while_loop_0" live alongside not inside its owned nodes?

EDIT:
I mean this:

    'injected_while_loop_0': {
        'type': 'while',
        'test': 'x < 0',
        'inputs': {'x': {}, 'y': {}},
        'outputs': {'result': {}},
        'nodes': {
            'add_0': {
                'function': <function __main__.add(x, y)>,
                'inputs': {'x': {}, 'y': {}},
                'outputs': {'output': {}}
            },
            'add_1': {
                'function': <function __main__.add(x, y)>,
                'inputs': {'x': {}, 'y': {}},
                'outputs': {'output': {}}
        },
        'data_edges': [
            ['inputs.x', 'add_0.inputs.x'],
            ['inputs.x', 'add_1.inputs.x'],
            ['inputs.y', 'add_0.inputs.y'],
            ['inputs.y', 'add_1.inputs.y'],
            ['add_1.outputs.output', 'outputs.y']
        ],
        'label': 'injected_while_loop'

[liamhuber]

Now, I would like to extend it to if, for and while.

I've been thinking about this for a while, and the one that really gives me pause is if. For for and while, we only get the full graph retrospectively, because it depends on actual runtime data; but the IO for those nodes can still be defined fully prospectively, and thus it can be safely used in other recipes. For if, it is the actual return value that is (naively) unavailable prospectively. This means that unless we come up with something really clever, or place some extra restrictions on if returns, we can't use it in other recipes. (E.g. maybe it always returns both branches but one might have exclusively NotData returns, but then we need to be additionally clever and careful on how that impacts the downstream execution (well, maybe it downstream stuff registers as not ready, which is not so hard but I will still lump it under "careful") -- at any rate, there is some extra subtlety.)

[samwaseda]

Is there a typo here? "injected_while_loop_0" doesn't have inputs and outputs fields directly, but has inputs and outputs nested inside its own "nodes" field -- should the io and inter-child edges of "injected_while_loop_0" live alongside not inside its owned nodes?

Good job! Yes it was a typo

[samwaseda]

I would suggest to transition the 'test' to also be a node, with the restriction that it must return a single boolean.

yeah I was thinking in the same direction as well. Since this part usually does not involve any database entry or job submission, I thought it can also be just a line of code in the representation, but I can also accept to consider anything that has inputs, outputs and an execution plan.

[samwaseda]

I've been thinking about this for a while, and the one that really gives me pause is if. For for and while, we only get the full graph retrospectively, because it depends on actual runtime data; but the IO for those nodes can still be defined fully prospectively, and thus it can be safely used in other recipes. For if, it is the actual return value that is (naively) unavailable prospectively. This means that unless we come up with something really clever, or place some extra restrictions on if returns, we can't use it in other recipes. (E.g. maybe it always returns both branches but one might have exclusively NotData returns, but then we need to be additionally clever and careful on how that impacts the downstream execution (well, maybe it downstream stuff registers as not ready, which is not so hard but I will still lump it under "careful") -- at any rate, there is some extra subtlety.)

I don't think it's too much to ask not to put return inside the if clause, i.e. instead of

def f(x):
    if x < 0:
        return x
    else:
        return -x

we ask the user to write:

def f(x):
    if x < 0:
        result = x
    else:
        result = -x
    return result

This way, I would naively claim what has to be done is basically the same as in while and for

[jan-janssen]

Taking your code:

def add(x, y):
    return x + y

def my_workflow(x, y):
    while x < 0:
        x = add(x, y)
        y = add(x, y)
    return y

Running it through: print(ast.dump(ast.parse(while_str), indent=4)) I get:

Module(
    body=[
        FunctionDef(
            name='add',
            args=arguments(
                posonlyargs=[],
                args=[
                    arg(arg='x'),
                    arg(arg='y')],
                kwonlyargs=[],
                kw_defaults=[],
                defaults=[]),
            body=[
                Return(
                    value=BinOp(
                        left=Name(id='x', ctx=Load()),
                        op=Add(),
                        right=Name(id='y', ctx=Load())))],
            decorator_list=[],
            type_params=[]),
        FunctionDef(
            name='my_workflow',
            args=arguments(
                posonlyargs=[],
                args=[
                    arg(arg='x'),
                    arg(arg='y')],
                kwonlyargs=[],
                kw_defaults=[],
                defaults=[]),
            body=[
                While(
                    test=Compare(
                        left=Name(id='x', ctx=Load()),
                        ops=[
                            Lt()],
                        comparators=[
                            Constant(value=0)]),
                    body=[
                        Assign(
                            targets=[
                                Name(id='x', ctx=Store())],
                            value=Call(
                                func=Name(id='add', ctx=Load()),
                                args=[
                                    Name(id='x', ctx=Load()),
                                    Name(id='y', ctx=Load())],
                                keywords=[])),
                        Assign(
                            targets=[
                                Name(id='y', ctx=Store())],
                            value=Call(
                                func=Name(id='add', ctx=Load()),
                                args=[
                                    Name(id='x', ctx=Load()),
                                    Name(id='y', ctx=Load())],
                                keywords=[]))],
                    orelse=[]),
                Return(
                    value=Name(id='y', ctx=Load()))],
            decorator_list=[],
            type_params=[])],
    type_ignores=[])

I wonder, what is the most direct mapping from the output of ast to a graph based representation with nodes and edges?

[samwaseda]

@jan-janssen I have already written most of the algorithm, but for me the question is not so much about how to relate AST to our dict representation, because following the definition of @liamhuber's and mine, there should be a unique representation. So while it's true we want to have a well written parser, as long as the parser exports the dict as we gave it above, we shouldn't need to worry about how it does it.

[liamhuber]

def f(x):
    if x < 0:
        return "something"
    else:
        return 42, np.linspace(0, 1, 10)

I think we wind up needing to impose special constraints to prevent this type of thing

[Tara-Lakshmipathy]

@samwaseda, @liamhuber Quick question, in this representation:

    'injected_while_loop_0': {
        'type': 'while',
        'test': 'x < 0',
        'inputs': {'x': {}, 'y': {}},
        'outputs': {'result': {}},
        'nodes': {
            'add_0': {
                'function': <function __main__.add(x, y)>,
                'inputs': {'x': {}, 'y': {}},
                'outputs': {'output': {}}
            },
            'add_1': {
                'function': <function __main__.add(x, y)>,
                'inputs': {'x': {}, 'y': {}},
                'outputs': {'output': {}}
        },
        'data_edges': [
            ['inputs.x', 'add_0.inputs.x'],
            ['inputs.x', 'add_1.inputs.x'],
            ['inputs.y', 'add_0.inputs.y'],
            ['inputs.y', 'add_1.inputs.y'],
            ['add_1.outputs.output', 'outputs.y']
        ],
        'label': 'injected_while_loop'

How do we see that the output of add_0 and add_1 loop back into the nodes, or am I missing something? Basically, where does it state that the output of add_0 is x and output of add_1 is y, which are reused as inputs to the nodes in the loop?

EDIT: can we have something like this:

        'data_edges': [
            ['inputs.x', 'add_0.inputs.x'],
            ['inputs.x', 'add_1.inputs.x'],
            ['inputs.y', 'add_0.inputs.y'],
            ['inputs.y', 'add_1.inputs.y'],
            ['add_0.outputs.output', 'add_0.inputs.x'],
            ['add_0.outputs.output', 'add_1.inputs.x'],
            ['add_1.outputs.output', 'add_0.inputs.y'],
            ['add_1.outputs.output', 'add_1.inputs.x'],
            ['add_1.outputs.output', 'outputs.result']
        ],

And then should the test part of the representation be:

    'injected_while_loop_0': {
        'type': 'while',
        'inputs': {'x': {}, 'y': {}},
        'outputs': {'result': {}},
        'test': 'inputs.x or add_0.outputs.output < 0',

The above is in case, the input value of x is already greater than 0.

[samwaseda]

@Tara-Lakshmipathy There are actually multiple typos here. I noticed them during the meeting, but I was too lazy to correct them. I guess the correct edges are:

[
    ['inputs.x', 'add_0.inputs.x'],
    ['inputs.y', 'add_0.inputs.y'],
    ['inputs.y', 'add_1.inputs.y'],
    ['add_0.outputs.output', 'add_1.inputs.x'],
    ['add_0.outputs.output', 'outputs.x'],
    ['add_1.outputs.output', 'outputs.y']
]

and as the output labels x and y correspond to the input labels, you know that they are connected. Since it is known that it's a while loop, I don't think we need to add extra edges.

[samwaseda]

Anyway let me come up with the actual implementation first, because I'm relatively sure that I made other typos as well (as @liamhuber had also already pointed out).

[liamhuber]

I think we need to be more careful declaring add_0 as x instead, and then some of the responsibility to rewire things is carried by the type: while. I won't be able to take a swing at syntax details until later this week

[samwaseda]

Let's say now we have the following workflow:

def my_condition(x, y):
    return x + y < 100

def add(x: float = 2.0, y: float = 1) -> float:
    return x + y

def my_workflow(a=10, b=20):
    while my_condition(x, y):
        y = add(x, b)
        x = add(y, b)
    return x

The part for the while loop looks like this (Note: Only the internal while part):

{
 'inputs': {'x': {}, 'y': {}, 'b': {}},
 'outputs': {'x': {}, 'y': {}},
 'test': {
  'function': <function __main__.my_condition(x, y)>,
  'inputs': {'x': {}, 'y': {}},
  'outputs': {}
 },
 'nodes': {'add_0': {'function': <function __main__.add(x: float = 2.0, y: float = 1) -> float>,
   'inputs': {'x': {'dtype': float, 'default': 2.0},
    'y': {'dtype': float, 'default': 1}},
   'outputs': {'output': {'dtype': float}}},
  'add_1': {'function': <function __main__.add(x: float = 2.0, y: float = 1) -> float>,
   'inputs': {'x': {'dtype': float, 'default': 2.0},
    'y': {'dtype': float, 'default': 1}},
   'outputs': {'output': {'dtype': float}}}},
 'data_edges': [
  ['inputs.x', 'add_0.inputs.x'],
  ['inputs.b', 'add_0.inputs.y'],
  ['inputs.b', 'add_1.inputs.y'],
  ['add_0.outputs.output', 'outputs.y'],
  ['inputs.y', 'add_1.inputs.x'],
  ['add_1.outputs.output', 'outputs.x']
 ],
 'label': 'injected_while_loop'}

(It's in my notebook, so you won't find it in the PR yet)

I think so far the representation almost follows what I had promised above, with the change that test has the same structure as an atomic node. Why almost? Because there's not yet the edges between the macro inputs and the test inputs. Now the question is, should I simply append the extra connections: ['inputs.x', 'test.inputs.x'] and ['inputs.y', 'test.inputs.y'] to make:

 'data_edges': [
  ['inputs.x', 'test.inputs.x'],
  ['inputs.y', 'test.inputs.y'],
  ['inputs.x', 'add_0.inputs.x'],
  ['inputs.b', 'add_0.inputs.y'],
  ['inputs.b', 'add_1.inputs.y'],
  ['add_0.outputs.output', 'outputs.y'],
  ['inputs.y', 'add_1.inputs.x'],
  ['add_1.outputs.output', 'outputs.x']
 ],

Since the tests won't have indices, there won't be any duplicate, but I'm wondering if there's a smarter and more importantly, clearer way to represent it.