Difference between revisions of "Chart uncertainties"

Revision as of 01:48, 15 December 2005

Head back to Chart_research for some perspective.

Here is a space for our goals, challengs, ideas, restrictions, thoughts, worries, and anything else.

• Streams vs. single arguments?
• How do you preserve state?
• How do you accumulate transparently when a node's execution is split?

Deadlock

Because every necessary resource is known when a chart is first executed, and known in finer detail at the finer scales of recursive charts, deadlock is impossible. A node will not be executed if its needs are not met, and if it exceeds its stated needs it will (in the most likely implementation) be terminated. Failure is possible, deadlock is not.

Circuits do not need to be forbidden for this reason, but there is another: because we don't want nodes to "run" and "stop", as they would have to for a circuit ever to produce a result, we cannot have naive circuits. Circuits the properties and completion conditions of which are precisely known may be permissible. How will we represent this? It comes down to the same problem, I think, but is another approach.

Control Charts

What happens if we use charts, with their current limitations, to describe program flow instead of data flow? If each node executes after its parents and before its children -- and that's the only guarantee -- what do we see? It's intimately related to our larger problem.

To reduce a dataflow chart to a control chart, realize it with nodes that take unary input (no information is exchanged).

Control charts can work with global data, particularly if each node needs a guarantee of state before it runs and gives a guarantee of state after it runs. Now think of a program in a classic language, where not every line really depends on the lines before it, but will still be run in order. What if you marked off the dependencies of lines of code, and structured the program that way? It would be convenient, among other things, for debugging and efficient compilation. It might also offer interesting ways to do conditional expressions.

I think I might study these as a simpler case.

Network Charts

I once listened to a lecture where declaritive overlay networks were being constructed using SQL like query commands. This greatly allows for the simplification of creating overlay networks, or at least reducing the amount of code required per system as so much became abstrated away.

Might a chart be used in some way to describe how nodes interact and are connected?

Ideally we need to find exactly what operations on a Network_chart would be necessary to make this useful. Once we know that, we can apply that knowledge in studying more general computational charts: what operations on a network chart turn it into a computational chart?

Computation Charts

Charts can be used to declare areas of computation and the interactions/dependancies between them. This is the obvious applicaiton of charts, but is significant. It would allow for increased modularity of code, parallelism and diversity in code base. Predominantly the chart abstracts the computation further away from the computer it is being processed on.

See Charts and the Lambda Calculus for more.

Layering

Thus far we have described charts as residing above all other code, no matter how nested the charts themselves are. Could perhaps the charts themselves be used as programming level constructs? Similar to a function or an event handler a programmer could set up inputs or outputs to a chart.

This is, in general, a difficult problem. Consider the following line of arguments:

• Most input systems to the computer require output to trigger. Certainly a node that is considered to be input can be fulfilled with a program that technically performs both input and output, but if we find a way to describe both aspects of this, it will be lovely. [incidentally: a program's output is needed, so its input is needed; its input needs to give an output, so it gives an output. This is a subset of the problems we already have. it's not all too bad.]

• Charts themselves must be loaded into memory. Therefore the solution to the previous point can be applied to the loading of a chart. Simpler methods can be applied, too, ultimately.

• In general, chart meta-programming is acceptable. We need to understand what properties can be known in such a case.

Cycles and Reversibility

It seems that running different programs on the reversal of a chart and applying those results to the forward execution of the same chart will allow the same functionality offered by graph cycles without the potential deadlocks.

That is, you can more accurately explain why you are trading data back and forth, and when those conditions are no longer met, you can pull out. It seems better to me.

This applies strongly to Network Charts and do the issue of metaprogramming ("Layering", above). After all, in both cases it takes output to get an input. The uni-directionality is broken -- but it is only partially broken, not as completely as by cycles. I don't think we need to represent relationships with cycles that are not full cycles.

Incompleteness

As a further question: might we actually gain by making the language selectively Turing incomplete? Obviously the language will be Turing incomplete if there are no deadlocks, because we can decide the halting problem ("every program will halt"). Every program halting is a Good Thing.

This is reality. No computer ever built will be truly Turing complete unless we drop one into the singularity at Universe End. No computer can ever know whether it can run a truly Turing complete program. So our results are much cleaner if we can select precisely what abilities we will lose.

I say, ban: running forever and infinite memory. These don't need to be arbitrarily bounded by the language but the language should guarantee that a bound exists. What do we do to ensure this?

(I recognize that, as each component is implemented separately, any may freeze up. But this is a bug, not a language feature.)

Object Orientation

A chart with some of its inputs set constant represents a simple form of object; more properly, this is a curried function.

A chart with some subset of its internal channels preserved, however, is an object. Pair a chart with constistent memory and an object results. We need a way to determine which data channels need not (or even may not) be overwritten.

Prior work

• Sawzall
• Cilk is simple, solid, and down-to-earth and there is likely to be some work we can draw from it. It gives us one more model for program interaction. It requires POSIX threads and the general form does not allow distributed memory. There is information about a distributed memory version, developed as part of Keith Randall's PhD thesis, at a page deep in the Cilk website.