Basic Concepts


Introduction

Motivation describes the motivation for our project. There, we recognise that there are many different views of systems structure, expressed in many different languages, and that these different views need to be related together. However, our experiences, over fifty years, tells us that the languages get in the way of this "relating together". They make rigid distinctions between things that are not fundamentally different, e.g. programs and data, procedures and interfaces, types and instances, processes and transactions, etc. Worse still, the strong distinctions made by each language are inconsistent with the strong distinctions made by other languages. We therefore want to get away from these distinctions and start from an extremely simple semantics.

We have developed a very simple modelling style that matches our motivation and enables us to relate together the many interacting views of system structure that were referred to above. The primitive semantics of this modelling style has just one type of object - a system, and one type of relationship connecting such objects - a role of a system as a component in another system. We show that this modelling style can cope with the full range of mathematical and business problems, and can be related to other modelling styles.

The basic concepts for our modelling style are described in this document; the reader should not need to read and study the mathematics, embedded in this document, unless she or he wishes to; the text and diagrams should provide sufficient introduction to subsequent documents, Human-Interface that describes the human view of, and interface to our style, and Programming Manual that gradually develops our style through a series of examples.


Graphs of Systems - S and C

Our modelling style is based on a view that all systems (human, mechanical, electronic, natural, etc.) exist in an infinite graph S of systems, with each system built from component systems, with each component of a system having a role (or multiple roles) within that system, and with roles being identified by systems. The systems may be ones that exist now, in the past, or in the future, or ones that might exist. S is thus defined by a set of triples with each triple including a containing system, a contained system, and a system that identifies a role:-

      S = {≺s, c, r≻ • (s, c ∈ S) ∧ (R ⊂ S) ∧ (r ∈ R) ∧ (∃ id ∈ R • (≺s, s, id≻, ≺c, c, id≻, ≺id, id, id≻ ∈ S) ) }

where S is the set of all systems and R is the set of all identifiers of roles. Note that we have made a conscious decision to include the world of identifiers within the world of systems - making identifiers first class citizens. This means that the mechanisms we use for building and manipulating systems can also be used for building and manipulating identifiers (including programs). It allows us to keep faith with our main principle that there should only be one type of object - the system. This approach is quite different from most modelling and programming styles where the worlds of systems and identifiers (including programs) are kept apart.

We see each system in S as existing over all time, but being of little interest most of the time. For instance, Caesar’s last breath (if considered as a system) exists now (though dispersed) and has always existed; it had a useful role in Caesar for a very short time. S just provides the background canvas for our modelling style; at any one time only a sub-graph of S is of real interest (and it will not include Caesar's last breath); this sub-graph gradually evolves with time - moving like a spot-light over the canvas of S.

We maintain an electronic store that models the evolution of the interesting subset C of S; it is defined by:-

      (CS) ∧ (≺id, id, id≻ ∈ C ) ∧ ( (≺s, c, r≻ ∈ C ) ⇒ (≺s, s, id≻, ≺c, c, id≻, ≺r, r, id≻ ∈ C ) )
      ∧ ( (≺s, c1, r≻, ≺s, c2, r≻ ∈ C ) ⇒ (c1 = c2) )
      ∧ ∀c ∈ S ( ∀ s≠c ∈ S ( ∀ r ∈ R (≺s, c, r≻, ≺c, s, r≻ ∉ C ) ) ⇒ (≺c, c, id≻ ∉ C ) )

The last line of this definition insists that every system in C must either have some component system (other than itself) or be a component of some system (other than itself). We could contemplate a stronger definition here – that every system (other than a top system of C) has to be a component system of some system (other than itself).

The second line of the above definition has a number of important implications. It implies, that any system, in C, can have, within it, at most one component system supporting each of its roles. On the other hand, it allows one component system to support more than one role in the same containing system, and it allows a role to be supported by different component systems in different containing systems. Although the containing system and the role are sufficient to identify the line, the line can only exist in C when it has a component system to support its role.


Identifiers

In the above, we use the term identifier for a representation of an object that uniquely distinguishes that object from any other object. It is totally impossible for an object to be globally identifiable, as that would mean any observer, throughout the universe, in any place, at any time, had to agree the association between the object and its identifier; your own name or title cannot make you globally identifiable in that sense. An object can only be identified locally, within some context.

In the definitions of the previous sections, it is a containing system that provides a context, and it is a component system-performimg-a-role-within-the-context that is given an identifier (another system) - and remember that a component system can fulfil more than one role within a containing system, each with a separate identifier.

Thus, throughout this series of documents, systems are never identified globally; they are always identified by their roles within other systems.


Binding

There are some systems in C, modelled in our electronic store, that have "life", in the sense that they can change their component structure.

Our electronic store supports one type of "living" system; this is a system that can perform a bind operation in order to evolve its own component structure. The nature of this evolution is shown in the following diagrams:-

In these diagrams, the bind system (at the top) has four component systems that contribute to its evolution; these component systems are here labelled X, u, Y and v and they have roles identified by systems labelled 1, 2, 3 and 4. The labels b, 1, 2, 3, 4, X, u, Y, and v are in the diagram just for the purposes of this description – they do not exist within our electronic store – in the store are just systems associated with these labels.

Initially system X has a component of its own, with role identified by system u, and Y has a component system, with role identified by system v. After the bind operation, X’s component system, with role identified by system u, has also become Y’s component system, with role identified by system v. The component system of Y, that previously had the role identified by system v, has lost that role; if this component had no other role within Y, then it has ceased to be a component system of Y; if it had no role in any other system and had no component systems of its own, then it has disappeared from C and from the electronic store.

The bind operation shown in the diagram can be defined by:-

      b : Ç × S × R × S × R → Ç
      C2 = b(C1, s1, r1, s2, r2) ⇒
      ∃ c1, c2 ∈ S • (≺s1, c1, r1≻, ≺s2, c2, r2≻ ∈ C1) ∧ (≺s1, c1, r1≻, ≺s2, c1, r2≻ ∈ C2)
         ∧ ( (≺s, c, r≻ ∈ C1) ∧ (≺s, c, r≻ ≠ ≺s2, c2, r2≻) ⇒ (≺s, c, r≻ ∈ C2) )

where Ç is the set of all subsets of S that conform to our earlier definition of C. Note, that this definition implies that C (modelled within the electronic store) potentially contains more than one “top”, i.e. more than one system that is not a component of any other system.

There are special cases of the above bind operation that need to be mentioned and are not covered by the above definition. If, at the start of the operation, Y did not have a component system, with role identified by system v, then the end result is still as shown to the right of the diagram, except that there is no discarded system. If, at the start, X did not have a component system with role identified by system u, then after the bind operation Y has no component with role identified by system v. If there is no system identified by any one of 2, 3 and 4 (i.e. if any one of u, Y and v is missing), then the operation has no effect. If there is no component with role 1 (i.e. no X), then an empty component (i.e. one with no components) is created to take the role in Y identified by system v (i.e. the absence of X is taken to mean that a new component is to be introduced into C from S). If there is no system identified by cont, then after performing the bind operation, the interpreter idles until the cont is given a useful value.

To allow for these special cases we need the concept of a null system (i.e. null ∈ S – we mean this to be the absence of a system (a HOLE) not just an empty system), the addition to the definition of S of:-

      ∀ s, c, r ∈ S (≺null, c, r≻, ≺s, null, r≻, ≺s, c, null≻ ∉ S )

and the extension of the bind definition to be:-

      b : Ç × S × R × S × R → Ç
      C2 = b(C1, s1, r1, s2, r2) ⇒
      ( (≺s, c, r≻ ∈ C1) ∧ ( (s ≠ s2) ∨ (r ≠ r2) ) ⇒ (≺s, c, r≻ ∈ C2) )
      ∧ ( ( (s1, r1, s2, r2 ≠ null) ∧ (∃ ≺s1, c, r1≻ ∈ C1) ⇒ (≺s1, c, r1≻, ≺s2, c, r2≻ ∈ C2) )
         ∨ ( (s1, r1, s2, r2 ≠ null) ∧ ¬(∃ ≺s1, c, r1≻ ∈ C1) ⇒ ¬(∃ ≺s1, c, r1≻ ∈ C2) ∧ ¬(∃ ≺s2, c, r2≻ ∈ C2) )
         ∨ ( (r1 = null) ∨ (s2 = null) ∨ (r2 = null) ⇒ ( C2 = C1) )
         ∨ ( (s1 = null) ∧ (r1, s2, r2 ≠ null) ⇒ ∃ c ∈ S • (≺s2, c, r2≻ ∈ C2) ∧ ( (≺c, s, r≻ ∈ C2 ) ⇒ (s = c) ) )
         )

Note, that this bind operation, defined above, makes the minimal possible transformation of C; it creates one line in C, removing one line if that line had the same role, and creating (or introducing from S) a new component system if no component is provided; it provides our modelling style with a reasonable minimal building-block; any complex transformation of C should be definable as a set of single line transformations.


A Minimal Interpreter

We currently have an interpreter tool that enables our electronic store to model the aliveness referred to in the previous section. We could have others; human beings are good modellers of aliveness. However, here we are describing our existing interpreter

In the above diagram, the bind system had two component systems that we have not, as yet, discussed; the first, with role identified by system t (or rather type), is used to tell the interpreter that a system, with this component, is a bind system; the second, with role identified by system c (or rather cont), provides the next bind system for the interpreter to activate:-

Thus the interpreter interprets a sequence of bind operations chained together by the cont parameter:

This can be defined recursively by:-

      a : Ç × S → Ç
      a(C, s) = a(b(C, 1(C, s), 2(C, s), 3(C, s), 4(C, s) ), cont(C, s) )

where:-

      1: Ç × S → Ç  •  1(C, s) = get(C, s, 1),
      2: Ç × S → Ç  •  2(C, s) = get(C, s, 2),
      3: Ç × S → Ç  •  3(C, s) = get(C, s, 3),
      4: Ç × S → Ç  •  4(C, s) = get(C, s, 4)
      cont: Ç × S → Ç  •  cont(C, s) = get(C, s, cont)
where:-
      get : Ç × S × R → Ç  •  get(C, s1, r) = s2

where s2 is the component of s1 with role r in C.

The binds in the interpreter's sequence can evolve the sequence, by inserting new binds into the sequence; these insertions need to keep just ahead of the interpreter as it interprets the binds in the sequence; this sequence-evolution process is driven by programs (contained within the graph C and modelled within the electronic store); we demonstrate this in the document, Programming Manual.


Concurrency

Our modelling style needs to support concurrency, as concurrency is a fact of life in the real world. This means that we must allow multiple interpreters to operate on our graph C. Hence, in the definition, given in the previous section, the initial part must be replaced with:-

      a : Ç × P(S) → Ç
      a(C, š) = a(b(C, 1(C, s), 2(C, s), 3(C, s), 4(C, s) ), (š\{s})∪{cont(C, s)} )

where

Here, the set š is the set of bind operations that are waiting to be interpreted by the set of interpreters; one interpreter is chosen, randomly, to interpret its bind operation, s; then there is a new set of bind operations, (š\{s})∪{cont(C, s)}, waiting to be interpreted.

We need the ability to add additional interpreters; we provide this by adding an extra parameter (with role identified by contplus i.e. c+) to our bind operation; this allows one interpreter to spawn another interpreter, giving the following effect:-

Here the contplus parameter gives the beginning of a new sequence of bind operations to be interpreted by a new copy of the interpreter. The above definition needs to be augmented to become:-

      a : Ç × P(S) → Ç
      a(C, š) = a(b(C, 1(C, s), 2(C, s), 3(C, s), 4(C, s) ), š/{s})∪{cont(C, s)}∪{contplus(C, s)} )

where

      contplus: Ç × S → Ç  •  contplus(C, s) = get(C, s, contplus)

normally {contplus(C, s)} is an empty set; it only has content when a new copy of the interpreter is invoked.


Semaphores

Interpreters, that are operating concurrently, need some way of locking and unlocking the parts of graph C that they need to change; at a minimal level this implies use of Dijkstra's P (lock) and V (unlock) operations; each of these operations needs to be indivisible, so ideally needs to be implemented with a single, indivisible, bind operation.

For each semaphore there is an interpreter that interprets a sequence of binds for the semaphore (the nature of this sequence is described below), and there is a set of (user) interpreters that are interpreting sequences of bind operations that include P and V operations.

In its initial state, a P (lock) operation has its cont parameter set to null; this means that the interpreter (that is interpreting the P bind operation) idles after it has performed the bind operation and remains idle until the cont parameter is reset; the bind operation, itself, tells the interpreter of the semaphore what value should be given to the cont parameter when the lock request has been accepted.

When the interpreter of the semaphore has satisfied the lock (P) request, it idles, i.e. its current cont parameter remains null; it is the V (unlock) operation that resets this cont parameter and so reawakens the interpreter of the semaphore from its idle state.

Thus the P and V operations can each be supported with one bind operation each.

The semaphore interpreter needs a more complex sequence of binds; it cycles round the users of the semaphore interpreting the same sequence of binds for each of them; the sequence starts by testing whether or not the user has requested a lock (P) (i.e. it sees if the bind operation for the lock has provided a value for its own cont parameter); if not, it proceeds to the next user. If a value has been provided for the cont parameter, it clears the stored value, puts the value into the user's cont parameter, and then idles itself; later, the unlock (V) reawakens it, by setting its cont parameter; it then cycles round the users again.

We could produce bind diagrams to illustrate the above; however, we think it will prove more comprehensible, if we revisit this topic again early in the document Programming Manual after we have introduced the human-interface in Human-Interface.

As has been shown in the past, more sophisticated concurrency mechanisms can be built from these very basic P and V operations.

The contents of this section have assumed that the interpretation of each bind operation is indivisible, i.e. interpretations of different bind operations do not overlap; this implies multi-tasking of the interpreters described above rather than true analogue concurrency; it further implies a lower level interpreter (within C or outside it) that synchronises the different higher level interpreters; this in turn implies a lower level semaphore system to enable synchronisation amongst the lower level interpreters; this is discussed further in a later section.


Duality of C

Up to this point, in this document, the sections have described the effect of sequences of bind operations being interpreted by a set of concurrently operating interpreters; the effect has been defined in terms of an abstract entity C. This entity, C, could be seen as a representation facing in two directions; in one direction (upwards) is the real world; in the other direction (downwards) are the computer systems holding our model of the real world; it represents each of them.

In theory we can observe the effect (upwards) of the sequences of bind operations in C, by merely looking around us and seeing the evolution of the real world; for instance, we can observe a sequence of appointments (bindings) to the cabinet (of the British government) and then relate it to the sequence of bind operations in C.

Alternatively, we can define the effect (downwards) of the sequences of bind operations by defining how they are implemented by our interpreters. Three language views are involved in the operation of each interpreter; the first language is the language used to code the bind operations that are being interpreted; the second language is the language into which the interpreter maps the bind operations; the third language is the language used to write the program of the interpreter. For instance the first language should be our language, as described in our Programming Manual, the second could be a relational language suitable for describing the set of tuples represented by the mathematics, provided above, and the third language could be C#. In theory, all three languages could be our language, as described in our Programming Manual; this simply says that our modelling of the real world is part of the real world and so can be modelled with the rest of the real world.

We now investigate what is required in the implementation orientated (downwards) direction.


Persistence

Our model of C is potentially very large and may operate across many computers. At the top (nearer the human-interface), our model of C, held in our electronic store, appears uniform, with no hint that the electronic store is fragmented across many machines. The electronic store also appears persistent, with C existing and evolving over all time. Thus the human-interface just sees C residing in a uniform persistent electronic store.

The interpreters of this top level of model know that the electronic store is fragmented into sub-stores that are held on different machines; they use hyper-links to give them the sub-stores that hold systems as well as the systems themselves. The organisation of the electronic store into sub-stores, and hence the hyper-links, can be modelled within C, so the implementations of the interpreters can also be modelled within C. These interpreters rely on lower (nearer the hardware) level interpreters confined to their own sub-stores; it is these interpreters that ensure the persistence of the store.


Deep-Bind

Earlier in this note we defined our minimal bind operation:-

We can note two things about this bind operation; firstly, its parameters are provided as direct components of the bind operation; secondly, these parameters provide all the information required for the bind operation, i.e. it is totally self-contained and requires no external context; the deep-bind operation relaxes the first of these constraints; the contextual-bind (discussed in the next section) relaxes both constraints.

The deep-bind operation:-

differs from the minimal bind operations in having path identifiers rather than role identifiers for its second and fourth parameters; these path identifiers define paths down from the systems X and Y to the systems that need to be linked by a new line in C; this removes the need for the long sequence of minimal binds, that would have to wend their way down through the structures of X and Y, before the required change could be made. Note, that we have used the traditional head/tail structures for the component structures of path identifiers; there is nothing sacrosant (built in) about this structure; we could have used some other structure.


Contextual-Bind

The contextual bind operation:-

differs from the minimal bind operations by dispensing with the need for the first and third parameters. For this variant of the bind operation, the systems X and Y (required by the minimal bind operation) are now components, with roles identified by x and y, within the interpreter itself; thus, the contextual bind operation is defined relative to a context held with the interpreter; the parameters, with roles identified by 2, 4 and cont in the contextual bind operation, define paths relative to the interpreter rather than relative to X, Y and the bind operation.

The defaults for this operation are consistent with those given for the minimal bind operation; if parameter 2 or parameter 4 is a null system then nothing happens; if parameter cont is a null system then the interpreter idles waiting for it to be set; if any link in either of parameters 2, 4 and cont except the last link in parameter 4 (ie any of x, a, y, z and j in the above diagram) is the role of a null system then an empty system is created to replace the null system.

The great virtue of the contextual-bind operation is that sequences of contextual-bind operations can be reused within different contexts; this gives us reusable programs; this is particularly important when we need multiple interpreters interpreting the same program.

We could go further than this and have the second and fourth parameters (or parts of them) held in the context provided by the interpreter; this would be necessary if these needed to vary according to the context in which a program is interpreted.


Implementation

We now need to sketch, how the ideas of this document might be implemented. Although we could and do (in Implementation) model an implementation within C, it should be more comprehensible if we first describe an implementation using a high level language, such as C#.

We already have an implementation in C# for a single interpreter. In this implementation, each system is modelled by a C# object of a class called 'system'; the state of this object is a set of tuples; each tuple contains two C# objects of class 'system', that model a component system and the role identifier of that component system within the containing system. The class 'system' has 'get' and 'put' methods that can be used to explore and evolve the states of its objects; it has a 'bind' method that orchestrates bind operations.

Extending this implementation to multiple interpreters operating on one processor is comparitively easy; the interpreters must be implemented in separate C# threads; the interpreters must support P and V bind operations and include an interpreter for each semaphore as described, above, in this document.

When one interpreter spawns another (prompted by a contplus parameter, as described above), the new interpreter needs to be added as an additional C# thread, using the same C# program as the spawning interpreter. If the spawned interpreter is an alien (that appears to be operating within C, but actually is outside of it) then the new thread must be given a C# program appropriate to the alien.

The above just requires one C# program, on one computer. Extending this implementation to multiple computers is more tricky, as it requires communication and coordination between multiple C# programs on multiple computers; a system, modelled on one computer, may have some components, modelled on other computers; some of its roles may be identified by systems, that are modelled on other computers; hence, the tuples in the state of each system, in one C# program, may need to reference C# objects. in other C# programs; the get and put procedures may need to manipulate these remote C# objects, using gateway C# methods at the inter-computer interfaces.

All of this is explored further in Implementation.