Talk:Chart uncertainties

?? How do you accumulate transparently when a node's execution is split? ??

Yeah, weird wording. It's been sitting there a while, so I'm not as sure anymore, but: when you have a program expressed as nicely as in Sawzall, how, in general, do you accumulate the responses to an earlier node for passing to a later one, without problems? This is certainly a matter of inserting another node, I suppose...

Which seems equivalent to the problem of maintaining state as well as the recursion question (which I already wrote some on). I currently am of the belief that a node must be let free to only output on some of its channels. It cannot output on any channel not mentioned in the chart, but is free to output on any of its described channels. This comes one step closer to multiple 'emit' calls compared to a single return but this does seem to solve the state/recursion problem.

As per your specific question of an accumulator node:

(goose, accum : accum, geese) accumulator

Where accumulator takes in a 'goose' and an accumulated pile of geese and can output a set of 'geese' or feedback into itself with the 'accum' channel. The problem here is initializing the 'accum' channel which cannot be done without some other node intervening. The data node could pass along an initializing state, but without it having some method to accumulate state it would always send an initializing state with its data. This is wrong.

This problem could be stated such as needing the ability to accumulate state to be able to accumulate data. How do we accumulate state? Clearly not in the same way that we accumulate data as we have not solved that problem yet. Either some node must initialize all states at the start of the chart, each node must specify some default initial input, or a way must be specified for nodes to run with partial inputs. The third feels most powerful and dangerous given that our current setup allows for nodes inputs to be filled from multiple nodes.

...

Five points; point 5 is the truly important one.

1) In general complicated problems will need either state or code generation. Statefulness is the Turing approach; code generation is the Church approach. Your summary is apt.

The catch is that we want a solution that gives us a solution for the halting problem. The solution doesn't have to be very nice, but it should have this property: if any component is hard to test for halting, it should be as shallow in the structure as possible. We want loops and recursion and code generation to exist above the level of the thing looping, recursing, or generating.

If we know a module will halt, and it's in a structure that will halt, then the whole thing will halt. It's an easy proof and the only one we need.

2) Partial in/out. If there is demand only for a subset of a chart's output the chart might run with a fraction of its input. I think that this requires that the branches ultimately be parallel, as in:

(i1, i2 : o1, o2) [ (i1:o1) a; (i2:o2) b ]

In general, a node needs all of its interfaces fulfilled unless the node can be expanded as a chart and proved to have parallel branches. Whether having an interface fulfilled means that data is available on the interface is questionable.

Take the example of a merge node, designed to give as output any item on any of its input channels. It evidently does not need every input at once. Then again, merge might be an exception.

Take the further example of user input to a game, where processing in the game doesn't pause because no input is available -- but the fact that there is no key pressed is, itself, input. Is it best to represent that as a "no input" signal, or as an unfulfilled interface?

3) State should be admitted to. The need for state should percolate up a structure. One way or another a node should admit that it will be stateful (and on what scale will it be?).

4) We can do control flow charts and dataflow charts, but what about memory charts? What about 'resource' charts in general -- where the actual 'execution' is the making available of a resource to a program (and the various inverse executions are analyses, as always)? So I can dump 512 MB into the top of the chart, with 0 MB coming out the bottom, and let it assign the resource as it goes.

Mind that I'm not proposing this as a general extension to our current chart theory, just as another possibility to think about. But if we can find a way to tie it all together...

5) State and code generation can do each others' jobs (code generation being a sort of state). We already have a gode generation mechanism: the chartrunner.

Remember, from the perspective of the system as a whole, the chartrunner makes the charts and then executes them; even if it runs code to load a chart from disk, that code, from the system's perspective, has created the chart.

It seems like we can implement state and code generation on the chartrunner scale, then. Remember that all input to a program is first available to the chartrunner, after all.

We have something like:

(i, programname:o) chartrunner=[(programname:programcode) database; (i,programcode:o) interpreter]

Where programname is the name of the program, or whatever it is that the chartrunner needs to find the interpreter and run the program. After all, the chartrunner is itself an interpreter, and its programs (which are charts) are themselves loaded the same way that programs are loaded for other interpreters.

So what, then, if we indicate on the level of the chartrunner code the fact that we're looping? What if we syphon off one of the inputs to the program and use it to decide, before the program is ever run, how many times we'll run it?

I think if we explore this type of metaprogramming the notation will get messy for a while and then clean itself up as we understand better what we're doing. And I think this kind of metaprogramming will answer our questions and offer the type of expressive power I've been looking for.