Chart research
This page is for the development of the chart notation and its computational models. Fork it as it grows. Keep an overview of each topic here. This is research so schizophrenia is ok: just make it clear that the voice is changing.
Other Topics
- The Chartrunner interprets charts and realizes them
- Chart_examples is a repository for possible example charts
- Chart_uncertainties is a place for our hopes and dreams (nightmares welcome!)
- Network charts represent networks of computers, each distinctly represented by a chart. We need to find the simplest way to allow this (simple as measured in the elements needed to describe it, as distinct from other problems we have already solved).
- At Charts and the Lambda Calculus we consider the relationship between chart theory and the applicative/functional languages.
- DataflowBibliography ... time to pay for that ACM membership, it seems.
- Chart_cStyle Sketches of a related c-style language
Overview
A chart is an acyclic directed graph. Programs can be run on its nodes and communicate as described by its edges. The state of a program is not a single point that follows a directed graph with decision making at the vertices; rather, execution occurs at a vertex when all of its inputs are fulfilled, so (in our standard model) every vertex executes as the course of the program proceeds.
Dataflow can be represented with charts, but charts are meant to be a more general notation: they are not at all an architectural model (as dataflow tends to be). Charts are a general computational model. They are probably not equivalent to the pi calculus.
Notation
The current chart notation lists local names for a node's inputs and outputs.
(in1, in2 : out1, out2) node1
A set of nodes, placed in square brackets, represents a chart. A chart can realize a node, so the following could be used where the above is called for:
(in1, in2 : out1, out2) [ (in1 : chan1) node_a (in2 : chan2) node_b (chan1, chan2 : out1, chan3) node_c (chan3 : out2) node_d ]
The following rules explain this:
- All names are strictly local. The block's channels in and out are the only external names; likewise, each node has access only to the names given to it in its input/output.
- Every pipe must be connected at both ends. Each end may be connected only once: so each pipe will connect exactly two nodes.
- Each pipe must be first used as a node's output (or as the input to the block) and only then as a node's input (or as the output of the block).
- Typing is not performed at chart level. The assumption is made that both ends of a pipe communicate in the same format, in the same units, and with the same mechanism. For more, see Chartrunner.
Here is a nested example:
(in1 : out1, out2)
[ (in1 : chan1, chan2) node_a
(chan1 : chan3) [ (chan1 : int1) node_b1
(int1 : chan3) node_b2 ]
(chan2, chan3 : out1, out2) node_c
]
There are two questions on beautiful notation: how do we locally rename channels and how do we allow multiple pipes to what (to the node) appears as one input? Should we? ("probably")
External Links
The Flow-Based Programming Wiki This work has a different focus, but it is obvious what our initial abstractions (charts) do for us that they do not have. Our basis is more solid and will get us further faster. (I have purchased the associated book and should have it within a week.)
Distributed systems & deadlocks
The Cilk Project Massive parallelism as a faithful extension of c.
