Conditional Evaluation

[mitchmindtree]

Currently gantz expects that a node's expression will always evaluate to one instance of each of its outputs. This is a bit limiting as it means we don't have any way to optionally evaluate branches of a graph based on some value at runtime.

To support conditional evaluation I can think of a couple of approaches:

1. Allowing Nodes to somehow opt-in to having conditional outputs
2. A special-cased node that takes a bool as an input and two conditionally evaluated outputs

I'm leaning towards option 1 as it will likely be common to want to create nodes that conditionally evaluate certain outputs. It also simplifies the idea of allowing for graph nodes themselves to have conditionally evaluated outlets.

Conditional Node Outputs

WIP

[freesig]

Yeh I agree, having a output type that contains the result of the if in the previous node makes sense. Then when we are doing the codegen we know that out put needs to be put in an if like:

let output1 = { // rand true false };
let output2 = { 4 };
if output1 {
 println!("{}", output2);
} else {
 output2;
 let output3 = {5 + output2};
 println!("{}", output3);
}

Which would look like:

[mitchmindtree]

I'm just having a think about the best approach for this in terms of the Node API. Right now, fn expr returns a syn::Expr which is always expected to evaluate to each output. Maybe instead, the return type should be some enum where either an unconditional expr is returned (as is currently the case) or a condition is returned?

I'm finding this a bit tricky to think through in a way that doesn't add a lot more complexity, as even a basic condition has quite a bit more going on than a regular expr. E.g.

The current case:

let (_output0, _output1, _output2) = { node_expr };

Whereas even for a simple conditional node like:

-+--------------
| if then else |
-+------+-------

things get quite a bit more complex, e.g.

if cond_expr {
    let _output_left: () = expr_left;
} else {
    let _output_right: () = expr_right;
}

Here it looks like we need three expressions from the node now,

• the condition expr which in this case happens to be the bool input argument, but what if our input is some other type that we are pattern matching on?
• the then expr and the else expr. In this case the node just happens to output the unit type for each branch as the outputs are placeholders for the branches of evaluation, but in another node each branch could easily be an enum variant we want to retrieve some value from.

[mitchmindtree]

Maybe rather than thinking in terms of conditions it would be easier to come up with a more general solution thinking in terms of pattern matching, as pretty much all conditions and pattern matching can be represented with a match, e.g. the if else node above would be:

match pattern_expr {
    true => {
        let _output_left: () = expr_left;
    }
    false => {
        let _output_right: () = expr_right;
    }
}

This way we could also allow nodes to specifying the pattern associated with each branch. E.g. above true leads to the first branch, false leads to the second.

[mitchmindtree]

Maybe the return type of Node::expr should be something like this:

pub enum Expr {
    /// An unconditional expression, e.g. `l + r`.
    Unconditional(syn::Expr),
    /// An expression that branches based on pattern matching, e.g.
    /// 
    /// match a == b {
    ///     true => { foo(); }
    ///     false => { bar(); }
    /// }
    PatternMatch(PatternMatch),
}

pub struct PatternMatch {
    /// Expression that will be pattern matched on.
    pattern_expr: syn::Expr,
    /// The possible branches of evaluation.
    branches: Vec<Branch>,
}

pub struct Branch {
    /// Pattern that will trigger evaluation of this branch.
    pattern: syn::Pat,
    /// The node's expression to evaluate for this branch.
    expr: syn::Expr,
    /// The outputs that will be evaluated by the expr for this branch.
    outputs: Vec<Output>,
}

Or something along these lines? This way the node can have any number of branches and still evaluate to one or more outputs per branch. Maybe this can be simplified further...

[freesig]

So then this will be expanded into an actual match statement in codegen?
How to we say which downstream nodes belong in which arm though?

as in:

match p.pattern_expr {
 Branch1 => { // some downstream nodes },
 Branch2 => { // some other downstream nodes },
}

[mitchmindtree]

How to we say which downstream nodes belong in which arm though?

By checking the outputs field for that branch - that outputs field contains each of the node outputs which will get evaluated, so we know to only evaluate nodes that are connected from that point.

You're right though, this isn't as easy as I was first thinking - we'll need to do another topographic traversal to determine what we can reach from those outputs.

Alternatively, we could consider each node's expr when creating the initial evaluation steps and rather than returning a Vec of eval steps we could return a tree datastructure. We could then use this tree of steps in the actual code generation function?

[freesig]

I like the idea of returning the tree structure vs the Vec. I'm having a little hard conceptualizing it though. Might make some more drawings.

[freesig]

Actually what we could do is something like:

match p.pattern_expr {
 Branch1 => { eval_stream1() },
 Branch2 => { eval_stream2() },
}

So basically each branch generates another evaluation function.
The only reason this won't work is because we can't pass in the inputs, however this is just the same issue as the state problem. So maybe we should focus on that problem first?

[mitchmindtree]

Nice, I like this idea!

This would add a little more performance overhead though, as we don't know the types of the outputs, we'd have to cast them to &Any or Box<Any> or something like this to be able to pass them into the inner functions, whereas if we just inlined the branches we could avoid this...

This would be really nice though as it would make the generated code a little more modular which might require less work from the compiler each time a branch from the graph is updated.

This issue of not having types available is a tricky tradeoff. I might open an issue for it.

[nebkor]

What if each output always produced a result, but it was wrapped in a type like an Option<NodeOutput<T>>, and non-evaluated outputs were None or some other enum that communicated the provenance or metadata for the value and how it was computed? (I also realize that my example there is assuming exposing the types of the output, but I'm imagining that a programmer using Gantz would be using an idiomatic interface for manipulating the graphs and would appreciate the explicit information being available for inspection, and that person would be available for interactive clarification with the type checker.)

[mitchmindtree]

What if each output always produced a result, but it was wrapped in a type like an Option<NodeOutput>, and non-evaluated outputs were None or some other enum that communicated the provenance or metadata for the value and how it was computed?

@nebkor this sounds interesting, but I'm not sure I fully understand what you mean. Are you suggesting that each node always returns an Option for each output from evaluation of their expression at runtime? Or are you talking about adding extra information about each of the outputs to the Node::expr fn so that we have more information during code generation?

[nebkor]

Always return something like an Option; Some indicates a a value for that output at that instant, while a None means that whatever conditional logic for that output did not get activated. This would mean that clients would need to react appropriately for inputs that come in as None, but maybe that's OK?

For richer metadata, instead of an actual Option, an enum with more than two states, maybe something like:

enum NodeOutput<T> {
  Fresh(T),
  Cached(T),
  Unevaluated,
}

or drop the Unevaluated variant and wrap a Fresh or Cached value in an Option where None means unevaluated.