Discussion on graph shape

[purpleidea]

We left off here...

if we want to write an optimization which notices that a sub-graph is no longer changing

What was the advantage of doing that rather than just not generating a subgraph via Txn to begin with for the nodes that won't ever need it? IOW, what is the downside of just generating those function graphs to be the same shape as they currently are in git master? (For the non-lambda functions of course.)

It might also be necessary for expressions to be able to express that they will never create a sub-graph

We can add a field to function Info to say whether or not they will need Txn or not. I don't mind manually labelling each function. It's actually easy, the default can be false, and then we have a single function that needs labelling as true so far (iter.map).

[gelisam]

What was the advantage of doing that rather than just not generating a subgraph via Txn to begin with

My suggestion is to write a more general optimization, one which will work both for static expressions and for dynamic expressions which stop changing mid-way through the execution. Let's detect when a sub-graph stops changing, and then let's rewrite the nodes around it so that it looks as if that sub-graph was always part of the original graph. I think this optimization fits better with the existing optimization when Stream() indicates that it will no longer send values downstream.

[gelisam]

It's actually easy

Because the functions themselves are the easy part, they are the base case! The more interesting part of the analysis is to look at an expression which returns a function, and to determine whether it is constant or not.

[gelisam]

You were right, I have changed my mind about this: let's generate the optimized sub-graph right away rather than rewrite the graph at runtime!

The reason I changed my mind is because I now see that if we do, then we can use the same static analysis for this feature and for the "send a function to a resource" feature. This static analysis determines if a given function or expression is "timeless", meaning that it doesn't do shenanigans like sending more than one value downstream or waiting until it receives multiple inputs before sending that single output.

There are several variants to this question:

1. For a Func, we want to know that if the Func receives one record of input values, then it will emit one output value.
2. For a FuncValue, we want to know that if the input Funcs emit a single value, then the output Func will emit a single value.
3. For an Expr, we want to know that the Func returned by Expr.Graph() will only ever output a single value. This implies that the Func itself is timeless, and so are its inputs, and so on transitively up to the Funcs with in-degree zero.

Note that it is possible for a timeless Expr to produce a non-timeless FuncValue! For example, Shell is a timeless constant expression which produces a single FuncValue, but that FuncValue is not timeless. And for higher-order functions like Map, an expression calling Map on a constant list and a constant function might be timeless, meaning that it emits a single list and then stops. But what if this list contains FuncValues? This list might contain a mix of timeless and not timeless FuncValues!

I think we should add an Expr.TimelessValue() Value-or-nil method. The caller may choose to use the non-nil value instead of calling Expr.Graph(). ExprCall would be such a caller, and it would generate a simpler graph with no secret channel when it receives a non-nil value for the function expression. Eventually every Expr.Graph() implementation could call it on their inputs in order to implement the constant folding optimization proposed in #672.

The Value returned by Expr.TimelessValue() can be any number of things, such as an int, a string, a list, a FuncValue, or a list of FuncValues. I think we should add a FuncValue.ApplyTimeless(Values[]) Value-or-nil method which indicates whether each FuncValue is timeless or not, and if so performs the calculation. And in order to answer this question, the FuncValue will either need to call Expr.TimelessValue() (if the FuncValue wraps a lambda) or Func.ApplyTimeless(Values[]) Value-or-nil (if the FuncValue wraps a built-in).

Expr.Graph() takes a Scope mapping the top-level names to Exprs and an environment mapping the lambda-bound names to Funcs. Expr.TimelessValue() would need to receive similar arguments. In the case in which the Expr is the body of a timeless lambda function which itself returns a non-timeless lambda function, the lambda-bound names which occur outside of the returned lambda must be timeless, while those which occur inside don't have to be. Therefore, the Scope and the environment still have to map to Exprs and Funcs, so that they are general enough for the non-timeless case. The FuncValue will thus need to wrap the Values it receives in ConstFunc, add them to the environment, and call Expr.TimelessValue() on the body, who will unwrap those values using Func.ApplyTimeless().

Sounds like a plan?

[purpleidea]

doesn't do shenanigans like sending more than one value downstream or waiting until it receives multiple inputs before sending that single output

I'm not sure if those specific shenanigans matter, do they?

But what if this list contains FuncValues? This list might contain a mix of timeless and not timeless FuncValues!

I think the simplest thing might be the easiest thing... Any function we statically label at design time can never be allowed to be part of the static graph generation. IOW, iter.map cannot. strings.toupper can. and so on... If we have some edge case where technically a function could have been part of the static graph but isn't this one time, that's okay, because that situation is rare. Right?

I think we should add an Expr.TimelessValue() Value-or-nil method. The caller may choose to use the non-nil value instead of calling Expr.Graph(). ExprCall would be such a caller, and it would generate a simpler graph with no secret channel when it receives a non-nil value for the function expression. Eventually every Expr.Graph() implementation could call it on their inputs in order to implement the constant folding optimization proposed in #672.

I didn't 100% understand this part, but it might be best to discuss in person today.

I'm excited! Cheers

[gelisam]

I'm not sure if those specific shenanigans matter, do they?

Currently, Shell($str) is compiled to a ConstFunc with emits a FuncValue representing the Shell built-in, which is sent to an ApplyFunc, which calls FuncValue.Call(), which creates a sub-graph containing ShellFunc. ApplyFunc creates secret channels and is prepared to replace the sub-graph if the ConstFunc ever emits a new FuncValue.

The optimization is to instead compile this directly to a ShellFunc. You are right that it doesn't matter whether ShellFunc does some shenanigans or not; what matters is whether the ConstFunc does. This is why I am careful to distinguish between whether a Expr is timeless and whether the FuncValue it produces is timeless.

[gelisam]

If we have some edge case where technically a function could have been part of the static graph but isn't this one time, that's okay, because that situation is rare. Right?

Indeed, when writing a static analysis, we usually need to be conservative and to only optimize the programs which we can guarantee are safe to optimize, and then some more complex programs won't be optimized even though in theory they could be. The reason we have to be conservative is because at compile time, we don't have all the values yet, so we have to pessimistically assume that the values we get at runtime are those which would break the optimization.

In this case, however, we are lucky because the static analysis is determining which expressions are constant. And those are precisely the expressions for which we do have the value at compile-time, so we don't have to compromise!

[purpleidea]

optimize the programs which we can guarantee are safe to optimize, and then some more complex programs won't be optimized even though in theory

Sounds good to me =D

I've updated git master with some of the easy things I could already merge, and I've rebased my feat/graph-shape with the changes I said I would make... I put lots of XXX in places where you should look at things. Cheers!

[gelisam]

I have now pushed answers to those XXXs to gelisam/graph-shape.

[purpleidea]

Okay, I took your branch, and did the following:

1. Add a new patch in master with the missing Graph() method. Rebased everything on top of that.
2. Added some fixes to make it compile.
3. Add a XXX: COMPLETELY GUESSING, PROBABLY WRONG commit at the end.

This last commit is probably completely wrong, but it was the only way I could make the types work. I'm not sure how I would take a full.FuncValue and turn it into a CallableFunc any other way. Maybe you can shed light here and I can do the plumbing if need be.

Lastly, and just for reference, instead of CheckParamScope, we can actually use the Apply method which is basically a catch-all iterator. I will leave this in as-is for now, but I will patch that at the end once things work. Just mentioning it for future reference in case you need to collect something.

Cheers!

[gelisam]

This last commit is probably completely wrong, but it was the only way I could make the types work. I'm not sure how I would take a full.FuncValue and turn it into a CallableFunc any other way.

The commit is indeed wrong. CallableFunc is for Funcs, there is no reason to use it here.

The idea is that we want a FuncValue to know whether it is holding a types.FuncValue (which I now realize is what we call a "timeless" FuncValue), and if so, we should be able to call that types.FuncValue on a list of Values and receive a Value. I have pushed a commit which shows the basic idea, but it does not compile yet. I had to move Call from a method of full.FuncValue to a top-level function in order to avoid yet another import loop.

The next step is to go through all the remaining places where a full.FuncValue is created, and either rename V to Timeful, or use Timeless if possible. The more places where this is possible, the more the optimization is going to be able to create static graphs.

In particular, it would be important to find a way for the many builtins which happen to be timeless, like addition, to use Timeless. I think this will probably require a change to the way builtins are registered, because I think the current implementation associates a name with a Func, and once we have a Func it is difficult to go back to a types.FuncValue.