We said, in our introduction document, that we were interested, in the organisational structure, of systems, and the way, that such structures may evolve. Here, in this document, we describe the notations, that we use to describe such structures, and to describe their evolution. We focus, mainly, on two well-known, long-established, notations, Venn-Diagrams (1880s) and the untyped Lambda-notation (1930s). We show that a Venn-like diagram is effective, at describing a component structure of a system, while the Lambda-notation can describe (as a function) the transition, from one component structure to another. Here, and in the series of examples, listed in the documents section of our introduction document, we will establish an effective synergy, between the two notations.
In our earlier work, we used the POSD notation, to represent the structure of systems. However, by discarding the touching feature of POSD, we can turn POSD diagrams, into Venn-like diagrams. Despite moving to Venn-like diagrams, we still want to retain two key motivations, behind our original POSD notation. Firstly, in developing POSD, we recognised, that a necessary condition, for two systems to interact (so that one, or both, can change the other), is that there exists a third system, that supports the interaction. This third system must, either be a component, shared, by the two systems, or be a connecting system, interacting, with both systems. Secondly, we wanted to avoid the introduction, of lines, into our diagrams. Many notations use boxes, to represent systems, and lines, to represent the interactions, between the systems. Such notations rob their users, of much design flexibility (the wire syndrome, of hardware engineers), by giving the false impression, that lines represent primitive concepts, and thus have simple implementations.
We prefer to consider systems and interactions, as dual concepts - with interactions needing support, by systems, and systems being needed, to support interactions. In our work, on POSD, we used the term ‘shared behaviour’, to emphasise the importance, of interactions and their supporting, connecting, systems. We wanted to emphasise that these connecting systems could, potentially, be as complex, as the systems that they connect. The connecting systems, or shared behaviours, needed synergising, with the systems that they connect.
In the above, we gave a necessary condition, for two systems to interact. To make this condition sufficient, as well as necessary, the connecting system must support an end-to-end interaction, between the two systems, so that the interaction, at one end of the connecting system, triggers the interaction, at the other end.
Whenever we represent systems, we encounter a scoping problem. For instance, when we talk of the system, John-Lewis, we may mean John-Lewis’s set of shops and its headquarters, we may include John-Lewis’s supply and distribution chains and/or its employees, or we may mean John-Lewis, as a financial entity, that is of concern to the City. These are best thought of as different, though closely related, systems, with different, but overlapping, sets of components.
In using our notation, we take an extremely broad view, of systems, effectively including any entity, that has an evolving set, of components.
The Venn-like-diagram:
represents the unions and intersections, of systems, just as a Venn-diagram represents the unions and intersections, of sets. Each box represents the set of components, of a system.
We need to use the phrase, Venn-like diagram, for our diagram, as its difference, from a Venn-diagram, of sets, is significant. A component box, in a Venn-diagram, always represents a subset, of the objects, represented by the containing box. In a Venn-like diagram, a component box may represent a part, or subsystem, of the system that is represented, by the containing box. This means that the component box represents the states, of the subsystem, and these are substates (not states) of the system. This gives the key difference, between Venn-diagrams and our Venn-like diagrams.
Despite the difference explained, in the previous paragraph, we believe that it is possible to consider Venn-like diagrams, as actual Venn-diagrams. To do this, we would need to identify minimal components, like atoms or packets of energy, from which all systems, shown in our examples, are built. Then all boxes, in our diagrams, including the top-most box, represent sets of states, of these minimal components. We can characterise this, as a bottom-up view, of structure, whereas the previous paragraph gave a top-down view. We will stick, with the top-down view, and live with the difference, identified in the previous paragraph.
A weakness, of Venn-diagrams, is that they become geometrically impossible to draw (within two or even three dimensions) if they contain too many interconnections. We avoid this problem, in our examples, by using a series of our Venn-like diagrams, with each diagram representing a small design step, from the previous one, and thus gradually working, down the structure (such as the one shown above) taking the design, to increasing levels of detail.
We can also represent the information, in the Venn-like-diagram, with a directed graph, where the system, represented by the bottom node, of each line in the graph, is a component subsystem of the system, represented by the top node. This is the view, that we developed, in our introduction document. This description is not, as obvious, as it sounds. We can interpret the phrase ‚component system’ in one of two ways. It could imply a component system, entirely contained, within its container system. Alternatively, we could allow it to be partially (or entirely) contained within its container system. However, this would leave us unsure, whether Dd was a component of Bb, or Bb a component of Dd. Hence, in our examples, we must adopt, the first, tight, definition, so that the following are seen, as equivalent:
To ensure the equivalence, of the two diagrams, we had to introduce a number, of additional component systems, that were anonymous in the Venn-like-diagram. For instance, the components, ?z and ?x, are the parts of system Dd, that lie within Bb and Cc, while ?y lies outside Bb and Cc, but still within Dd.
In our examples, we will frequently encounter systems, that have a set of components that are similar. If we try to include, in a diagram, all the members of the set, with all their interactions, we will hit the well-known, geometrical, problem, referred to in the previous section. We will avoid this problem, by treating the complete set as one system, in the diagram that first introduces the set. Then, later diagrams, can consider typical members of the set and their interactions, without exceeding the geometrical limits. This implies, that our notation must have a way of representing sets. The following diagram illustrates how we do this:
There are a number of features, that we need to emphasise in this notation:
curly brackets { } mean, that this notation represents a set, of components the contents, of each pair of brackets, represents a typical member, of the set members, of the set, are distinguished, by the superscripts, p, q, qp, etc a superscript after the bracket, e.g. }p, indicates the superscript varying inside the brackets note, that the superscript, p, does not vary within the brackets in {Hhqp}q later diagram must indicate which components, Hhqp, lie within each component Ggp
In the introduction, above, we mentioned the Lambda-notation, as a useful way, of representing the dynamics of systems, the change in component structures of the systems.
The Lambda-notation allows one to define anonymous functions. Symbols, λ (lambda), and • (dot), are used, in all function definitions. Thus, λx•x defines the identity function. Brackets, (), are used in all applications, of a function. Thus, (λx•x 5) applies the identity function to 5, and so returns 5, i.e., (λx•x 5) = 5. An application, of the plus-2 function, to the value 5, gives (λx•(2+x) 5) = 2+5 = 7. Note, that the identity function can be applied to any value, but the plus-2 function can only be applied, to numbers, unless it is given a very complex definition. Functions, defined in the Lambda-notation, take functions, as their arguments, and return functions as their results. Thus (λy•λx•(y+x) 2) = λx•(2+x). We could explain this example further, by providing Lambda representations of 2 and + (remember that all arguments and results, of functions, are functions, even if the functions still lack definitions).
Functions, expressed in the Lambda-notation, may only take one argument, so if we want a function of two (or more) arguments, we must provide it in curried format. For instance, a curried version, of the add function, is λx•λy•(x+y). If this is applied to an argument 3, λx•λy•(x+y) 3, it returns an plus-3 function, λy•(3+y). Applications of the add function to both 3 and 5 gives (λx•λy•(x+y) 3) 5 = (λy•(3+y) 5) = 3+5 = 8. We could explain this example further, by providing Lambda representations (as functions) of 3, 5, 8 and +.
The key building block of this process is the βreduction, which can be represented by:
(λx•M N) → M[x→N]where M[x→N] means M, with any free x, within it (i.e., not bound, within it, by another λx), replaced with an N.
Thus, the following defines the Lambda calculus, in Lambda-notation and in Venn-like-diagram:
We can represent the evaluation, of the identity function, with Venn-like diagrams, or directed-graphs:
Now consider the function Q=Ω(fa(I)), where Ω is the self-application function, λx•(x x), I is the identity function, λy•y, and fa is the function, λx•x (x a), and remember, that (y z) means the function y applied to z. The paper, "Sharing in the Evaluation of Lambda Expressions", by Jean Jacques Levy, represents the structure of Q, with the following directed graphs, and their textual equivalents. The right-hand graph gives the full detail:
We have attached superscripts to the brackets, to show how the diagrams and text represent the same system. Evaluation systems, for Lambda-Calculus, might evaluate (or evolve, or execute) the above expressions, with either, of the following sequences:
Q = (Ω (fa I)) → (Ω (I a)) → (Ω a) → (a a) Q = (Ω (fa I)) → ((fa I) (fa I)) → ((I a) (I a)) → (a a)Each step, in these sequences, comprises one or more β-reductions. The first can be referred to as an inner reduction, because it evaluates a subexpression first, whereas the second evaluates the outer expression first (best seen in the graphs). These two sequences of evaluations are represented diagrammatically, by:
Further evaluation steps could evaluate (a a), but only if we knew, the function represented, by a.
The lower sequence (outer evaluation) shows a rather naive view, of the evaluation process. The first and second steps, in the process, imply duplicate evaluations of branches, of the tree. In fact, more sophisticated evaluation processes recognize these shared components, so that this second sequence is better represented, by:
For the third graph, in this sequence:
the textual representation could be:
Now let us summarise the various ways of describing the above system:
Some approaches, to the evaluation of Lambda expressions, go further than the above. They entirely dispense, with names, for the components in the graphs, e.g., Q, Ω and fa, and instead they use positions, in the graph, to identify shared components. Now compare this, with our examples, in the first section, e.g.:
In theory, each box, in this last Venn-like diagram, could be given a program, in the Lambda-notation, which represents its operation. The box might represent a very complex system, so its Lambda representation might be very very complex, with many alternative threads of activity. and using Lambda calculus capabilities (e.g., concurrency), beyond those described above. Some of the complexity, might be beyond our understanding, and so un-expressible, in Lambda-notation. However, we can express part of it, and that is what we will do, in our examples. Hence, the notation we used, in our first section, is the same as the notation used, in this section, for the Lambda-calculus. It has shown, how we may synergise the Venn-like-notation and the Lambda notation, in our examples.
All the examples, listed in the documents section of our introduction document, will be represented, with Venn-like diagrams and their equivalent directed-graphs. When we need to represent change, in these examples, we will use relatively simple Lambda-expressions, involving composition and application of simple functions. Here, in the following sections, we will use the detailed Lambda-notation, to develop the implementations, of these functions.
We have demonstrated, in earlier sections, that we can always represent our Venn-like diagrams, as directed-graphs. Hence, we can mirror the evolution, of systems, with the evolution, of their directed-graphs, as represented in the Lambda-notation. Before that, we need lambda-notation representations, of some simpler functions.
We will start, with the definition of a pair, and a function to operate on the pair:
f( {x,y} ) = f( pair(x,y) ) = λx•λy•λf•( (f x) y )this lambda function creates a pair {x, y}, which can be operated on, by a function f. If this lambda function is applied to the numbers 3 and 4: λx•(λy•λf•( (f x) y ) 4) 3 it creates a pair f({3,4}) = λf•( (f 3) 4 ), which is a curried function f, applied to 3 and then to 4.
We will need the functions, first and second, to augment the pair function:
first( {x,y} ) → (first x) y = x second( {x,y} ) → (second x) y = yIf, in the definition of a pair, f is taken as the function, first, we get ( (first 3) 4 ) = 3, and, if it is taken as the function, second, we get ( (second 3) 4) = 4.
Now, define a particular pair:
b = booleans = {TRUE,FALSE}.Then:
TRUE → first(b) = (λx•( λy•x ) ) {TRUE,FALSE} = TRUE FALSE → second(b) = (λx•(λy•y) ) {TRUE,FALSE} = FALSE null → null = λp•p (λx•λy•FALSE)We can, similarly, define a function that creates a triple, which can be operated on, by a function f:
f( {x,y,z} ) → f( triple(x,y,z) ) = λx•λy•λz•λf•( ( (f x) y ) z)and this would create the need, for a function, third:
third( {x,y,z} ) → third({x,y,z}) = λx•( λy•( λz•z {x,y,z} ) = z
Now, we will proceed, to more ambitious functions - for binary-trees and directed-graphs.
An ancestry-tree is a good example, of a binary-tree. Each node, in the ancestry-tree has, stemming from it, two sub-trees giving the ancestors, of the node’s father, on the left, and, of the node’s mother, on the right. If two of the ancestors are cousins, then the binary-tree becomes a binary directed-graph, though, usually (but not for the Hapsburgs) the first few levels still form a binary-tree. Even, when it is a directed-graph, it remains binary, because each node has just two parents.
If needed, the nodes, in a binary-tree, can be given unique identifiers. This can be done, by associating a 1, with the left-hand branches of trees, and a 0, with the right-hand branches. Then, the first level node can be given identifier 1, the second level identifiers 11, and 10, the third level identifiers 111, 110, 101 and 100, the fourth level identifiers 1111, 1110, 1101, 1100, 1011, 1010, 1001 and 1000, and so on. These identifiers are all unique binary-numbers. We can use these, or their decimal equivalents, as unique identifiers, for the nodes:
The Lambda-notation, for the above tree, is comparatively simple. We can express it with:
btree(n*) = (λn•(bt n) n*) where: (bt n) = bt(n) = triple( n, bt(2n+1), bt(2n) ) and where triple is the function defined in the last section.
Remember, that we said earlier that, in Lambda expressions, all arguments and results, of functions, are functions, even if the functions still lack definitions. Hence, in the above expressions, n, n*, 2n, and 2n+1, represent functions. These functions could view these expressions as character strings ‘n’, ‘n*’, ‘2n’, and ‘2n+1’, so allowing functions, such as concatenation, to be applied to them. Alternatively, they could view the expressions as nodes, in the directed graphs, shown above, so allowing us to build these graphs.
How about a more complex function, like triple( 10, bt(101), bt(100) ). This could be viewed as generating the string structure ‘10{ bt(101), bt(100) }’ or ‘10{ 101{1011,1010}, 100{1001,1000} }’. Alternatively, it could be seen as generating the structure:
Remember, that, in the above, λn• represents the formal declaration, of a function. We used stars, e.g. n*, to represent actual declarations. Remember, also that bt(n) = (bt n), as bt(n) and (bt n), are just alternative notations, for the same thing.
However, the Lambda-notation, that we provided above, for our directed-graph, has a problem. It has no end condition, so it generates a tree, with an infinite number, of levels and nodes, or rather, it takes an infinite time, to generate the tree. We can remove this deficiency, with:
btree(n*) = (λn•(bt n) n*) where: (bt n) = bt(n) = triple( n, bt(2n+1), bt(2n) ) if n<15 or: btree(n*) = null if n>14The above diagram and the Lambda-definitions are for an ancestry-tree. We can produce a similar diagram, for the traditional family-tree. In this tree, we need to take the left-hand (horizontal) branch, as giving siblings, and the right-hand (vertical) branch, as giving descendants:
Clearly, a binary-identifier, if found in both diagrams, need not represent the same person. In addition, this tree need not extend fully in either direction, so e.g. nodes 8 and 11 may not exist. The Lambda notation, for this family-tree, is the same, as that, for the ancestry-tree:
btree(n*) = (λn•(bt n) n*) where: (bt n) = bt(n) = triple( n, bt(2n+1), bt(2n)We noted, above, that cousins may marry, thus giving us directed-graphs, rather than trees. For instance, we might have the following family-graph:
Each binary-identifier identifies the position, of its node, in the total graph. This identifier is not useful, if we want to implement a function, that changes the node‘s position. Then we need the nodes, to have names. As it happens, the above is the graph, that shows the descents, of Charles 2 of Spain, from Philip 1 of Spain (the effects, of the incestuous relationships, in that graph, eventually gave us the War of Spanish Succession). The graph, with names instead of identifiers, is:
but we will need shorter names, so we will use the following:
We do not want, to impose the concept, of marriage, on our directed-graph notation, as it restricts the number, of parent nodes, to two, so we will replace the above with.
Note, that these directed-graphs could be viewed (starting from the bottom), as ancestry graphs, or (starting from the top), as family-graphs.
These two versions are logically identical, but the right-hand one is better, because it clearly shows the sibling and descendent dimensions. It also shows that each parent, in a marriage, must have its own sibling dimension, for its children. There are no examples, in the above, of a person having multiple marriages (like Henry 8), so the diagram could be much more complex. However, a family directed-graph is not as complex, as a general directed graph, as each person has only two parents, and therefore sits in only two sibling-sequences. In general, it could sit in any number of them. However, the right-hand diagram, above, will be adequate, for the discussion, in this section.
Above, we represented one node of a binary tree. The equivalent, for one node of the directed-graph, displayed above, could be:
dgraph(CSE) = (λn•(dg n) CSE) where: dg(CSE) = triple( CSE, dg(P2S), dg(F1E) )
Now, let us consider part, of this graph, in more detail:
Then, this fragment (of the full graph) can be represented by:
dgraph = (λn•(dg(n)) AA) where: dg(AA) = triple( AA, dg(MB1), null ) dg(MB1) = triple( MB1, dg(MA), dg(WSB) ) dg(MA) = triple( MA, null, dg(F2E) ) dg(WSB) = triple( WSB, dg(MB2), null ) dg(F2E) = triple( F2E, dg(F3E), null ) dg(MB2) = triple( MB2, dg(F3E), null ) dg(F3E) = triple( F3E, null, null )
Let us consider the functions used, in the example, in the last section, of our Kissing-Hands document. First, consider the upv function (i.e. the up-vertical function), that achieves the following transformation:
a{ b{ z{w}, x }, y }For the directed graph, of the last section, this gives:a{ b{x}, z{w}, y } triple(b, dg(z), dg(y) )
MB1{ MA{ P4S{C2S}, MAS{C2S} }, F2E }We also need the inverse, of the upv function. We can call this downv (i.e. the down-vertical function). This requires:
a{ b{x}, z{w}, y }We will need a function, to move a component horizontally, between two nodes. This could be:a{ b{ z{w}, x }, y } triple(b, dg(x), triple( z, dg(c), dg(y) ) )
a{ b{ z{v}, x }, y{w}, u }In the last few sections, we have rather forgotten our earlier emphasis on Venn-like diagrams. However, our digital-graphs can easily be re-expressed as Venn-like diagrams. For instance:a{ b{x}, y{ z{v}, w }, u } triple(b, dg(z), dg(y) )
is re-expressed as:
Where ↓MA means the tree under MA (not quite the same as dg(MA)).
In the Venn-like diagrams, above, we have always used rectangles to represent systems, and, as far as our notation is concerned, that is fine. However, for other purposes, we might use shape or colour, to emphasise different facets of our design. For instance, we often talk, of cycles within our design, for instance the energy cycle, within each human (or other) cell:
with the energy carried, by the chemical, ATP:
At other times, we may want, to emphasise the different levels of design, in a model. For instance, we may model a human level system, involving people and technology. Within this model, we may show software systems, used by the humans. We could go further, and show the hardware, used by the humans and software. Colouring of the levels is a good way of distinguishing the levels, as shown below
In earlier work, prior to POSD, we used diagrams like:
And these were referred to, as bone diagrams, for obvious reasons. They provide another way, of showing the relationship, between different levels of abstraction, in a design.
We will now use the notations, described in this document, in the series of examples, listed in the document section, of our introduction document. END
