Difference between revisions of "Nodal reduction"

From Organic Design wiki
(The Nodal Reduction Algorithm: clean up)
m (Consumption)
 
(30 intermediate revisions by 5 users not shown)
Line 1: Line 1:
[[Category:Glossary]][[Category:Nodal Concepts]]
+
{{legacy}}
{{stub}}
+
== Control flow ==
__NOTOC__
+
[[w:control flow|Control flow]] refers to the order in which the individual statements in a program are [[execution|executed]]. Within a programming language, a ''control flow statement'' is an instruction that when executed can cause a change in the subsequent control flow to differ from the natural sequential order in which the instructions are listed. Discussion of control flow is almost always restricted to a single [[w:Thread (computer science)|thread of execution]], as it depends upon a definite sequence in which instructions are executed one at a time.
<table class=document-code><tr><td>[[+Nodal Reduction/Summary]]</table>
 
  
=== The Nodal Reduction Algorithm ===
+
The kinds of control flow statements available differ by language, but can be roughly categorized by their effect:
The reduction algorithm divides available execution up into ''[[Quantum|quanta]]'' which are like "atoms" of change in that they're kind of indivisible. They have no definite rules about the amount of time they can take to execute, but should be generally ''infinitesimal'' ([[w:Linearizability|linearizable]]) compared to the macro scale. Any looping or iteration-based functionality should be implemented in terms of reducable structure (process). Top level nodal reduction is implemented as an infinite execute-quantum loop within the context of the [[nodeROOT|root node]] of the local [[Nodal Space]]. The currently running nodal reduction algorithm is defined in [[nodeSpace.c]] and sites upon a [[list space]] defined in [[listSpace.c]]. The afore mentioned infinite execute-quanta loop is in [[peerd.c]].
+
*continuation at a different statement (jump),
 +
*executing a set of statements only if some condition is met (choice),
 +
*executing a set of statements repeatedly (loop; equivalent to jumping to an earlier point in the code),
 +
*executing a set of distant statements, after which the flow of control returns ([[w:subroutine|subroutine]]),
 +
*stopping the program, preventing any further execution (halt).
 +
In the [[nodal model]], the subroutine and loop aspects of control flow are defined in the nodal structure of the [[node space]] which is a tree of [[loop]]s. Conditions and jumps are handled within the nodal functions by manipulation of the nodes which compose the loops in the noda space.
  
 +
== Quanta ==
 +
The reduction algorithm divides available [[execution]] up into ''[[Quantum|quanta]]'' which are like "atoms" of change, in that they are essentially indivisible, so most of the [[w:control flow|control flow]] aspect of a program is handled by nodal reduction. They have no definite rules about the amount of time they can take to execute, but should be generally ''infinitesimal'' ([[w:Linearizability|linearisable]]) compared to the macro scale. Any looping or iteration-based functionality should be implemented in terms of reducable structure (process). Top-level nodal reduction is implemented as an infinite execute-quantum loop within the context of the [[root|root node]] of the local [[Nodal Space]]. The currently running nodal reduction algorithm is defined in [[nodeSpace.c]] and sits upon a [[list space]] defined in [[listSpace.c]]. The afore mentioned infinite execute-quanta loop is in [[peerd.c]]. Some logic or algorithmics has to be O(1) and so is required within a function rather than as reducible structure.
  
;Associations
+
[[Image:Communications example.png]]
Each [[node]] has both [[association|associative content]] and a possible local state (which in [[nodeSpace.c]] is accessible via a list of pointers using the node-index in the nodes [[nodeDATA]] association as an index into an array of pointers). The ''associations'' are in the form of ''nodeRef:nodeRef'' pairs similar in concept to the ''key:value'' pairs of [[Wikipedia:Asscoiative array|associative arrays]], and the non-nodal data is in a form specific to the local [[Wikipedia:Runtime|runtime]] environment (if there is no state, it will be returned as the local environments representation of ''null'').
 
  
 +
== Associations ==
 +
Each [[node]] has both [[association|associative content]] and a possible local state (which in [[nodeSpace.c]] is accessible via a list of pointers using the node-index in the nodes ''data'' association as an index into an array of pointers). The ''associations'' are in the form of ''nodeRef:nodeRef'' pairs similar in concept to the ''key:value'' pairs of [[Wikipedia:Associative array|associative arrays]], and the non-nodal data is in a form specific to the local [[Wikipedia:Runtime|runtime]] environment (if there is no state, it will be returned as the local environments representation of ''null'').
  
;Node names and references
+
== Node names and references ==
All node referencing at runtime is done using [[list space]] indexes not [[naming|names]] as in a normal object-model or [[w:associative array|associative array]]. For [[storage and distribution]] of nodal information, [[identity|GUID]]s are used. List-space references and GUIDs are used internally, but nodes can have context-specific names for external use. The names we use to refer to nodes here in the wiki are taken from the names of the constants to represent them in the [[peerd.c]] scripts.
+
All node referencing at runtime is done using [[list space]] indexes not [[naming|names]] as in a normal object-model or [[w:associative array|associative array]]. For storage and distribution of nodal information, [[identity|GUID]]s are used. List-space references and GUIDs are used internally, but nodes can have context-specific names for external use. The names we use to refer to nodes here in the wiki are taken from the names of the constants to represent them in the [[peerd.c]] scripts.
  
 +
== Tree of loops ==
 +
Using an association called {{right}}, allows the formation of ''[[loop]]s'' of nodes ([[Wikipedia:Linked list|singly-linked-circular lists]]) within the local [[Nodal Space]] (loops also use a {{left}} association too so that nodes can easily be inserted or removed without needing to query other nodes). Combining this with another association called {{down}}'' allows the formation of a ''loop-tree'' starting at the [[root|root node]] (node with index zero). Following the {{down}} association from ''root'' takes us down into another node, which is also part of a loop. Every traversal of a {{down}} takes us from an item in one loop to an item in another loop. The loop may contain zero items, but the idea here is that {{down}}'s always connect items in loops, even though other associations may lead to other nodal structure which may or may not be a loop.
  
;Tree of loops
+
== Loop rotation ==
Using an association called [[nodeNEXT]], allows the formation of ''[[loop]]s'' of nodes ([[Wikipedia:Linked list|singly-linked-circular lists]]) within the local [[Nodal Space]] (loops also use a [[nodePrev|Prev]] association too so that nodes can easily be inserted or removed without needing to query other nodes). Combining this with another association called [[nodeLOOP]]'' allows the formation of a ''loop-tree'' starting at the [[root|root node]] ([[nodeROOT]] node with index zero). Following the [[nodeLOOP]] association from [[nodeROOT]] takes us down into another node, which is also part of a loop. Every traversal of a [[nodeLOOP]] takes us from an item in one loop to an item in another loop. The loop may contain zero items, but the idea here is that [[nodeLOOP]]'s always connect items in loops, even though other associations may lead to other nodal structure which may or may not be a loop.
+
Systems are formed from ongoing, reoccurring patterns which can be described in terms of rotation of the loops in the tree described above. Every time the nodal reduction process follows a {{down}} association it also rotates that loop, so that next time the same {{down}} association is traversed it will lead to the next node. This process is active (change occurs to the structure) but reversable, ie it's cyclic and non-entropic change.
  
 +
== Whiteboard diagram showing rotation in nodal reduction ==
 +
'''NOTE:''' the diagram is rotating the wrong way - it should rotate clockwise so that next's are right and prev's left.
  
;Loop rotation
+
[[Image:Nodalreduction-text.jpg]]
Systems are formed from ongoing, reoccurring patterns which can be described in terms of rotation of the loops in the tree described above. Every time the nodal reduction process follows a [[nodeLOOP]] association it also rotates that loop, so that next time the same [[nodeLOOP]] association is traversed it will lead to the next node. This process is active (change occurs to the structure) but reversable, ie it's cyclic and non-entropic change.
 
 
 
 
 
;Comsumption
 
The actual consumption of a quanta of execution occurs by calling the ''nodeReduce'' function which takes no parameters, but maintains its own persistent state defining the current focal node - just like a ''current working directory''. The reduction function applies its quantum by first rotating the current focal node's loop and following its ''nodeLOOP'' association as described above, then checks if there's any non-nodal data, and if there is and it's a function reference it executes it and exits. If a function was executed, then that quantum is considered consumed and the next quantum is executed starting back at [[nodeROOT]] again. But if the data was not executable, then the ''nodeReduce'' function is called again, but remember that current focal node is now down one level because ''nodeLOOP'' was traversed, so the result is that the quanta of execution has been passed within. If there is no ''nodeLOOP'' association, the quantum is passed back up to [[nodeROOT]] unspent, but in practice this condition should not occur.
 
 
 
Here is the ''nodeReduce'' function from [[nodeSpace.c]] which is part of the currently running [[peerd.c]] nodal implementation.
 
<table class=document-code><tr><td>[[+NR.c|]]</table>
 
  
 +
== Consumption ==
 +
The actual consumption of a quanta of execution occurs by calling the ''reduce'' function which takes no parameters, but maintains its own persistent state defining the current focal node - just like a ''current working directory''. The reduction function applies its quantum by first rotating the current focal node's loop and following its ''loop'' association as described above, then checks if there's any non-nodal data, and if there is and it's a function reference it executes it and exits. If a function was executed, then that quantum is considered consumed and the next quantum is executed starting back at ''root'' again. But if the data was not executable, then the ''reduce'' function is called again, but remember that current focal node is now down one level because ''loop'' was traversed, so the result is that the quanta of execution has been passed within. If there is no ''loop'' association, the quantum is passed back up to ''root'' unspent, but in practice this condition should not occur.
 +
{{:NR.c}}
  
;Division
+
== Division ==
 
As the nodal reduction process rotate the loops in the tree, all of the nodes in loops will periodically get execution focus. The period is longer depending on the depth of the loop, since each node is effectively dividing its share of [[Quantum|quanta]] between its currently active child [[Process|processes]]. This method of division is called [[multiplexing]], see also [[w:time division multiplexing|Wikipedia's article]].
 
As the nodal reduction process rotate the loops in the tree, all of the nodes in loops will periodically get execution focus. The period is longer depending on the depth of the loop, since each node is effectively dividing its share of [[Quantum|quanta]] between its currently active child [[Process|processes]]. This method of division is called [[multiplexing]], see also [[w:time division multiplexing|Wikipedia's article]].
  
=== Function execution & parameters ===
+
[[Image:Wickerbasket-text.jpg]]
<s>Currently the model is that an executing function binding can interact with the local global environment using either the languages own hash-table syntax as in [[nodal-wikid.pl]], or using specific functions as in [[peer-nodal.as]].</s> Only the functional method is used now as in [[nodeSpace.c]].
 
  
It seemed preferable to remove the concept of interfaces in order to give direct nodal access to the code, but wait states can occur in reads if they have to instantiate due to first-read which means that the function could easily take non-infinitesimal time to execute.
+
== Nodal network ==
 
+
''Storage and distribution'' is a nodal organisation which extends reduction out to form a single harmonic ''global reduction space'' called the [[nodal network]]. Large organisations involving the process and resources of many individual nodal peers are also formed from and loops, but they rotate on larger cycles which are the globally known harmonics of [[spectrum]].
If we take a more UML/DOM-like approach we instead can nodally describe not only the OO and program flow control aspects, but also the function interfaces (names and entry/exit parameter lists). This means that the retrieval of the nodal information required to execute the function is being executed through nodal reduction.
+
[[Category:Nodal Concepts|Reduction]]
 
+
__NOTOC__
The function itself executes after all information is present, and does not ever interact directly with the outside environment, so no nodal access syntax or functions are required.
 
 
 
=== See also ===
 
*[[nodeSpace.c]] implements nodal reduction from the [[List Space]] level.
 
*[[Root]] ''- the nodal content of the root node''
 
 
 
=== Whiteboard diagams ===
 
'''''NOTE:''' the diagram is rotating the wrong way - it should rotate clockwise so that next's are right and prev's left.''
 
 
 
[[Image:Nodalreduction-text.jpg]]
 
 
 
[[Image:Wickerbasket-text.jpg]]
 

Latest revision as of 00:32, 26 May 2016

Legacy.svg Legacy: This article describes a concept that has been superseded in the course of ongoing development on the Organic Design wiki. Please do not develop this any further or base work on this concept, now this page is for historic record only.

Control flow

Control flow refers to the order in which the individual statements in a program are executed. Within a programming language, a control flow statement is an instruction that when executed can cause a change in the subsequent control flow to differ from the natural sequential order in which the instructions are listed. Discussion of control flow is almost always restricted to a single thread of execution, as it depends upon a definite sequence in which instructions are executed one at a time.

The kinds of control flow statements available differ by language, but can be roughly categorized by their effect:

  • continuation at a different statement (jump),
  • executing a set of statements only if some condition is met (choice),
  • executing a set of statements repeatedly (loop; equivalent to jumping to an earlier point in the code),
  • executing a set of distant statements, after which the flow of control returns (subroutine),
  • stopping the program, preventing any further execution (halt).

In the nodal model, the subroutine and loop aspects of control flow are defined in the nodal structure of the node space which is a tree of loops. Conditions and jumps are handled within the nodal functions by manipulation of the nodes which compose the loops in the noda space.

Quanta

The reduction algorithm divides available execution up into quanta which are like "atoms" of change, in that they are essentially indivisible, so most of the control flow aspect of a program is handled by nodal reduction. They have no definite rules about the amount of time they can take to execute, but should be generally infinitesimal (linearisable) compared to the macro scale. Any looping or iteration-based functionality should be implemented in terms of reducable structure (process). Top-level nodal reduction is implemented as an infinite execute-quantum loop within the context of the root node of the local Nodal Space. The currently running nodal reduction algorithm is defined in nodeSpace.c and sits upon a list space defined in listSpace.c. The afore mentioned infinite execute-quanta loop is in peerd.c. Some logic or algorithmics has to be O(1) and so is required within a function rather than as reducible structure.

Communications example.png

Associations

Each node has both associative content and a possible local state (which in nodeSpace.c is accessible via a list of pointers using the node-index in the nodes data association as an index into an array of pointers). The associations are in the form of nodeRef:nodeRef pairs similar in concept to the key:value pairs of associative arrays, and the non-nodal data is in a form specific to the local runtime environment (if there is no state, it will be returned as the local environments representation of null).

Node names and references

All node referencing at runtime is done using list space indexes not names as in a normal object-model or associative array. For storage and distribution of nodal information, GUIDs are used. List-space references and GUIDs are used internally, but nodes can have context-specific names for external use. The names we use to refer to nodes here in the wiki are taken from the names of the constants to represent them in the peerd.c scripts.

Tree of loops

Using an association called Right, allows the formation of loops of nodes (singly-linked-circular lists) within the local Nodal Space (loops also use a Left association too so that nodes can easily be inserted or removed without needing to query other nodes). Combining this with another association called Down allows the formation of a loop-tree starting at the root node (node with index zero). Following the Down association from root takes us down into another node, which is also part of a loop. Every traversal of a Down takes us from an item in one loop to an item in another loop. The loop may contain zero items, but the idea here is that Down's always connect items in loops, even though other associations may lead to other nodal structure which may or may not be a loop.

Loop rotation

Systems are formed from ongoing, reoccurring patterns which can be described in terms of rotation of the loops in the tree described above. Every time the nodal reduction process follows a Down association it also rotates that loop, so that next time the same Down association is traversed it will lead to the next node. This process is active (change occurs to the structure) but reversable, ie it's cyclic and non-entropic change.

Whiteboard diagram showing rotation in nodal reduction

NOTE: the diagram is rotating the wrong way - it should rotate clockwise so that next's are right and prev's left.

Nodalreduction-text.jpg

Consumption

The actual consumption of a quanta of execution occurs by calling the reduce function which takes no parameters, but maintains its own persistent state defining the current focal node - just like a current working directory. The reduction function applies its quantum by first rotating the current focal node's loop and following its loop association as described above, then checks if there's any non-nodal data, and if there is and it's a function reference it executes it and exits. If a function was executed, then that quantum is considered consumed and the next quantum is executed starting back at root again. But if the data was not executable, then the reduce function is called again, but remember that current focal node is now down one level because loop was traversed, so the result is that the quanta of execution has been passed within. If there is no loop association, the quantum is passed back up to root unspent, but in practice this condition should not occur.

// Moves "this" to node's focus if exists then rotates loop and executes/reduces the focus item
void nodeReduce() {
    if(this = nodeLoopRotate(parent = this)) {        // Move "this" to the focus in the node's loop and rotate
        nodeSetValue(this, nodePARENT, parent);       // Update the parent association
        if(code = *nodeState(this, nodeCODE)) code(); // nodeCODE value is a pointer-index, execute as function-reference if non-zero
    }
}

Division

As the nodal reduction process rotate the loops in the tree, all of the nodes in loops will periodically get execution focus. The period is longer depending on the depth of the loop, since each node is effectively dividing its share of quanta between its currently active child processes. This method of division is called multiplexing, see also Wikipedia's article.

Wickerbasket-text.jpg

Nodal network

Storage and distribution is a nodal organisation which extends reduction out to form a single harmonic global reduction space called the nodal network. Large organisations involving the process and resources of many individual nodal peers are also formed from and loops, but they rotate on larger cycles which are the globally known harmonics of spectrum.