Chart examples

From PublicWiki
Jump to: navigation, search

Here we can attempt to provide example charts for various cases that we would like to be able to handle. The use and interpretation of notation is lax for we do not yet have all the ideas we need.


Sorting can be described with the chart:

(unknownArray : sortedArray) sorter;

While the sorter node can be described in several different ways. Bubblesort might be implemented with nothing more than above, while quicksort might be made as:

(unknownArray : sortedArray) [ (unknownArray : forBubble, unknownArray) pivoter {state};
                               (forBubble :  sortedArray) bubbleSorter; ]

Where a pivoter node is declared to maintain a state variable and takes as input unsorted arrays to be split about a pivot and sorted until all subsections have been broken into small enough sizes. The array is then passed to a chart that implements Bubble Sorting where it can be sorted quickly and returned. This is relying upon a state variable to know when the array has been adequately sorted by quicksort such that bubblesort can quickly finish the sorting as well as splitting its output between itself and the bubbleSorted node. Thie would also be making use of 'emit' style rather than 'return' as it would be more natural for the pivoter to 'emit' two unknownArrays each time it is computed.

Mergesort might be described as:

(unknownArray : sortedArray) [ (unknownArray : toMerge, unknownArray) breaker;
                               (toMerge :  toMerge, sortedArray) merger {state, accum}; ]

Here the breaker node cuts arrays to be sorted in half recursively until they are of unit length and are passed to the merger node. The merger node takes two inputs (it holds one in its state variable accum), merges them and outputs them on the toMerge channel unless it knows by its state variable that it has finished merging the array.

Both of these examples make use of state variables. Neither one needs them but they make clear what would otherwise be computed in the nodes. The merger node could maintain two input channels which the breaker could somehow multiplex over. The state variables in general seemed to make clear what I was trying to program. Coding these was somewhat tricky in that traditional methods rely on stacks implicitly but they are somewhat hidden here. This also is relying on linearity in the processing of the data.