Programming Manual


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 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 Basic Concepts. The human view of, and modelling language interface to, this style is introduced in Human-Interface. Here, in this document, we add some syntactic features to the language in order to make it easier to use.


Graph C

In Basic Concepts, we introduce a graph C (held in an electronic store) that models the structure of systems in the real world; each node, in graph C, represents a system; each line, in C, declares that the contained system at the "bottom" of the line is a component of the containing system at the "top" of the line and that the contained system supports a role within the containing system. Each role is identified by another system, so that each line, in C, is defined by a triple of nodes, its containing system, its contained system and the identifier of its role. A role, within a containing system, can be supported by only one contained system, so a line can be uniquely identified by just a pair of nodes, its containing system and the identifier of its role. Note, that the above does not stop a contained system from supporting more than one role in a containing system, or from supporting roles in more than one containing system.


Minimal Bind Operation

We recognise that some nodes, in the graph C, have "life", enabling the graph to evolve. We identify one basic type of "living" system, the system that supports a bind operation. We can show that all computation can be performed by sequences of this minimal-bind operation. We can provide an interpreter, operating within the electronic store, capable of interpreting sequences of bind operations.

In Basic Concepts we illustrate the minimal-bind operation with the diagram:-

The bind operation takes the component in X, that has role within X identified by u, and makes it the component in Y, which has role within Y identified by v. The successor of this bind (within the sequence of binds being interpreted by our interpreter) is provided by the component of the bind with role (within the bind) identified by c (standing for continuation). The textual labels, 1, 2, 3, 4, X, u, Y, v, t and c, are in the diagram to enable humans to talk about the diagram. In the graph C, within the electronic store, these labels do not exist; they have been replaced by the nodes (systems) and lines (roles) of the graph. It follows that the absence of labels is also true of a program (made up of many bind operations) once it has been input to the electronic store.


Contextual-Bind Operation - Binding Within a Context

Each minimal-bind operation is totally self-contained; it carries, with it, all the information that an interpreter needs in order to interpret it; it requires no external context. This has advantages, but it has one major disadvantage, it is difficult for programs, built from these operations, to be used in different contexts, particularly when the programs or parts of them may be interpreted concurrently. Reuse of programs is a major feature of most programming languages.

In Basic Concepts, we introduced a contextual-bind operation that is free of the problems described in the last paragraph. We have an interpreter, operating within the electronic store, capable of interpreting sequences of contextual-bind operations. We show that all computation can be performed by sequences of this contextual-bind operation. In Human-Interface, we said that a contextual-bind operation can be input at the human interface with the following text:-

       ≺ ≺type≻≺=c≻, ≺2≻≺x.a≻, ≺4≻≺y.e≻, ≺cont≻≺z.i≻, ≻

Here, the =c sign tells the interpreter that this is is a contextual-bind operation. The labels, x, a, y, e, type, cont, etc., are present at the human-interface to enable humans to understand the text; they disappear as the contextual-bind operation is input into C. The notation, x.a, y,e, etc. provide identifiers for paths through C; the notation is defined by saying that ≺a.b.c≻ is shorthand for:-

       ≺ ≺head≻≺a≻, ≺tail≻≺ ≺head≻≺b≻, ≺tail≻≺ ≺head≻≺c≻, ≺tail≻≺NULL≻ ≻ ≻ ≻

Sometimes, path identifiers may be of length one; for instance, we could, in the above, have had ≺2≻≺x≻ rather than ≺2≻≺x.a≻. We feel it is best to make this much clearer, so, in the examples below, we use the notation ≺x.¿≻ for path identifiers of length one and ≺x≻ for role identifiers.

The principle, inherent in the contextual-bind operation, is that the components of the interpreter provide the context for each contextual-bind operation; thus, the systems, X, Y and Z, of the previous section, rather than being direct components of the bind operations, are components of the interpreter, with roles, within the interpreter, identified by x, y and z;

The components, with roles, within the contextual-bind operation, identified by 2 and 4, give the paths, relative to the interpreter, to the start and end of the line to be created in C. The context (e.g. the systems with roles in the interpreter, such as those identified by x, y and z) can be evolved by the contextual-bind operations themselves.

The contextual-bind operation must support the default options that are supported by the minimal bind operations; if there is no X, i.e. no component system of the interpreter with the role that is identified by x, then a new system is created to provide the end of path y.e; if there is no system at the end of the path, identified by x.a, then, after the bind operation, there will be no system at the end of the path, identified by y.e; if any of x, a, y, e, z or i are null then nothing happens.

In the remainder of this document, we show how more complex 'live' operations can be built from contextual-bind operations. Where possible we code these complex operations in reusable code.


Programs

We stated, above, that our interpreter interprets a sequence of bind operations that is held in the electronic store. Each bind operation is linked to its successor in the sequence of bind operations, so the bind operations, in the sequence, may be located in many different parts of the electronic store. In addition, bind operations, in the sequence, may change later content and ordering of the sequence. Thus, the human may input, at the human-interface, programs that define complex operations, and ensure that the programs are acquired as part of the interpreter's sequence. Below we give simple examples of these programs as they are input at the human-interface.


Case Invocation Operation

Our first example of a complex operation is the case-invocation operation; this operation closely matches our modelling style, as it just requires the selection of a component, with one role (the key's value), from a set of components, with many different roles. The set of components is provided by a case system; this could be given role 'case' in the interpreter's context, and input, at the human-interface, with text such as:-

      ≺case≻
      ≺
          ≺complex-type≻≺casec≻,
          ≺key1≻≺program for first option≻,
          ...,
          ≺keyn≻≺program for nth option≻
      ≻

The text ≺complex-type≻≺casec≻ is just there to tell humans that this is a case system; it is of no interest to the interpreter; indeed, its reification, in C, is totally ignored by the interpreter. The rest of the text provides programs for the various options.

A case-invocation operation could then be input at the human-interface with the text:-

      ≺
          ≺complex-type≻≺case-invocationc≻, ≺options≻≺case≻, ≺key≻≺choice≻,
          ≺type≻≺=c≻, ≺2≻≺current.continue≻, ≺4≻≺continuation.¿≻, ≺cont≻≺case.choice≻, ≺continue≻≺rest_of_program≻
      ≻

The second line of this text provides a template for the case-invocation operation; the third line provides its implementation as a sequence of contextual-bind operations (though the sequence, here, is just of length one, comprising one contextual-bind operation). The text ≺complex-type≻≺case-invocationc≻ is just there to tell humans that this is a case-invocation operation; it is of no interest to the interpreter. The system, with label 'case', identifies the role, within the interpreter, of the case system (see above) that contains a program for each option that it supports. The program that is to be interpreted for this call of the case-invocation operation, is the one with role 'choice' within this case system.

Note, that, in the above, the system, with role identified by 'continue', is a program, whilst the system, with role identified by 'cont', is a path identifier (with the system at the end of the path being a program); in later examples, in order to avoid confusion about continuations, we continue to use this convention, with 'cont' for the roles of path identifiers and 'continue' for the roles of actual programs; this convention is not built into our language.

The third line, of the above text, relies on a number of definitions that we provide in Human-Interface:-

Hence, the effect, of the third line of the text, is to make the interpreter interpret the appropriate program within the case system's repertoire. This program must use, as its continuation program, the value of the interpreter's continuation role (this is set in the third line of the above code).

An if-then-else system is just a special instance of the case system; it supports just two options. An if-then-else-invocation operation is just a special instance of the case-invocation operation; it requires a key that is one of the boolean values, TRUE or FALSE.

Note, that the code for the case-invocation operation is only reusable if its options and key parameters remain unchanged; so for an if-then-else-invocation operation we would need one version of this code for a choice of TRUE and one for a choice of FALSE; later we provide a version of the code that works for both TRUE and FALSE.


P and V Operations

In Basic Concepts we introduced semaphores; we also sketched our provisions of the P and V operations; we are now in a position to define them properly; the P and V operations can be represented at the human-interface by the following:-

      ≺
          ≺complex-type≻≺Pc≻, ≺semaphore≻≺intsem1≻, ≺user≻≺user1≻,
          ≺type≻≺=c≻, ≺2≻≺current.continue≻, ≺4≻≺semaphoreset.intsem1.userset.user1.continuation≻, ≺cont≻≺empty.¿≻, ≺continue≻≺rest_of_program-1≻
      ≻

and

      ≺
          ≺complex-type≻≺Vc≻, ≺semaphore≻≺intsem1≻,
          ≺type≻≺=c≻, ≺2≻≺semaphoreset.intsem1.continuation≻, ≺4≻≺semaphoreset.intsem1.current≻, ≺cont≻≺current.continue≻, ≺continue≻≺rest_of_program-2≻
      ≻

The above assumes that:-

Note, that the code for the P and V operations needs to be duplicated for each semaphore used by a particular user interpreter; later we will show how this restriction could be removed.

Later, in this document, we provide the code for the semaphore, itself, that ensures that these P and V operations perform correctly.


Test for Null System

Earlier, we used the conventional head/tail chain structure for the system (in the electronic store) that provides the path identifier a.b.c and later we use similar structures in a number of examples. We clearly need to be able to test for the 'bottom' nodes of such structures; this means that we need a test that determines whether or not a particular role (e.g. the role 'tail'), within a containing system, is being used or not; that is to say, whether or not it has a contained (component) system associated with it. The following code does this for the role 'target' in the interpreter:-

      ≺
          ≺complex-type≻≺testnullc≻, ≺test≻≺target≻, ≺continue1≻≺contin1≻, ≺continue2≻≺contin2≻,
          ≺type≻≺=c≻, ≺2≻≺current.continue1≻, ≺4≻≺continuation.¿≻, ≺cont≻≺current.continue≻,
          ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺target.¿≻, ≺4≻≺current.continue.4.head≻, ≺cont≻≺current.continue≻,
                                   ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺current.continue2≻, ≺4≻≺HOLE.¿≻, ≺cont≻≺current.continue≻, ≺continue2≻≺contin2≻,
                                                            ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺target.¿≻, ≺4≻≺current.continue.2.head≻, ≺cont≻≺current.continue≻,
                                                                                      ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺HOLE.¿≻, ≺4≻≺continuation.¿≻, ≺cont≻≺continuation.¿≻ ≻
      ≻ ≻ ≻ ≻

This code works because the bind operation on the fifth line does nothing if its parameter 4 is null, and the bind operation on the seventh line does nothing if its parameter 2 is null. If the target of the test is null then those two parameters are indeed null, and so the continuation of the test remains as continuation1; otherwise the seventh line is changed and the continuation is then continuation2.

This code is not reusable, as it contains self-modifying code; a version of this code needs to be duplicated for each interpreter and held, with role, identified by testnull, as a component of the interpreter; it is invoked as a component of the interpreter; rather than as a component of the invoking and potentially reusable code; later we show how this is done.

Note that, in the above, 'target' is a label for a role identifier. We could have make the code more general, by deciding that 'target' should be a label for a path identifier rather than for a role identifier; to do this we simply need to leave the .¿ off the end of each occurrence of 'target' (as suggested in Human-Interface), giving:-

      ≺
          ≺complex-type≻≺testnullc≻, ≺test≻≺target≻, ≺continue1≻≺contin1≻, ≺continue2≻≺contin2≻,
          ≺type≻≺=c≻, ≺2≻≺current.continue1≻, ≺4≻≺continuation.¿≻, ≺cont≻≺current.continue≻,
          ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺target≻, ≺4≻≺current.continue.4.head≻, ≺cont≻≺current.continue≻,
                                   ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺current.continue2≻, ≺4≻≺HOLE.¿≻, ≺cont≻≺current.continue≻, ≺continue2≻≺contin2≻,
                                                            ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺target≻, ≺4≻≺current.continue.2.head≻, ≺cont≻≺current.continue≻,
                                                                                      ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺HOLE.¿≻, ≺4≻≺continuation.¿≻, ≺cont≻≺continuation.¿≻ ≻
      ≻ ≻ ≻ ≻


Push

Now, consider a push operation that puts a new link on the front of a chain, such as:-

This operation can be provided with the following code:-

      ≺
          ≺complex-type≻≺pushc≻, ≺chaintop≻≺top≻, ≺pushed≻≺psd≻, ≺contn≻≺continuation≻,
          ≺type≻≺=c≻, ≺2≻≺NULL≻, ≺4≻≺temp.¿≻, ≺cont≻≺current.continue≻,
          ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺top≻, ≺4≻≺temp.tail≻, ≺cont≻≺current.continue≻,
                                   ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺psd≻, ≺4≻≺temp.head≻, ≺cont≻≺current.continue≻,
                                                            ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺temp.¿≻, ≺4≻≺top≻, ≺cont≻≺continuation.¿≻ ≻
      ≻ ≻ ≻

Here, the chaintop and pushed parameters provide paths to (not roles for) the stack that is to be pushed and the element that is to be pushed onto it (this use of paths was catered for in Human-Interface). There is no component system with the path identifier 'null' in the interpreter, so the third line, above, creates a new and empty system with the role 'temp' in the interpreter.


Reusability

Three levels of reusability are exhibited in the last four sections:-

However, the first two levels are not a major concern; we can provide reusable code for the Test Null, Case and the P/V operations, if such code is needed.

For the Case operation we can take the key parameter out of the case-invocation code and put it in the case system; the code for the case-invocation operation should then be:-

      ≺
          ≺complex-type≻≺case-invocationcr≻, ≺options≻≺case≻,
          ≺type≻≺=c≻, ≺2≻≺current.continue≻, ≺4≻≺continuation.¿≻, ≺cont≻≺case.chooser≻, ≺continue≻≺rest_of_program≻
      ≻

The system, with path identifier, 'case.chooser', relative to the interpreter, then needs the following code:-

      ≺
          ≺complex-type≻≺case-chooserc≻,
          ≺type≻≺=c≻, ≺2≻≺case.key≻, ≺4≻≺current.cont.tail.head≻, ≺cont≻≺case.HOLE≻
      ≻

For Test Null, we could have the following reusable code:-

      ≺
          ≺complex-type≻≺testnullcd≻, ≺test≻≺target≻, ≺continue1≻≺contin1≻, ≺continue2≻≺contin2≻,
          ≺type≻≺=c≻, ≺2≻≺current.¿≻, ≺4≻≺invoker.¿≻, ≺cont≻≺current.continue≻,
          ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺target≻, ≺4≻≺nulltester.test≻, ≺cont≻≺nulltester.¿≻ ≻
      ≻

that invokes the following un-reusable code, with role, 'nulltester', relative to the interpreter:-

      ≺
          ≺complex-type≻≺nulltesterc≻, ≺test≻≺targetted≻,
          ≺type≻≺=c≻, ≺2≻≺invoker.continue1≻, ≺4≻≺continuation.¿≻, ≺cont≻≺current.continue≻,
          ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺nulltester.test≻, ≺4≻≺current.continue.4.head≻, ≺cont≻≺current.continue≻,
                                   ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺invoker.continue2≻, ≺4≻≺HOLE.¿≻, ≺cont≻≺current.continue≻,
                                                            ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺nulltester.test≻, ≺4≻≺current.continue.2.head≻, ≺cont≻≺current.continue≻,
                                                                                      ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺HOLE.¿≻, ≺4≻≺continuation.¿≻, ≺cont≻≺continuation.¿≻ ≻
      ≻ ≻ ≻ ≻

The code for P and V operations is pretty much satisfactory as it is, as we would expect the code to be operating on a particular semaphore. However, if we wanted the code to be able to work on different semaphores, we could adopt a solution similar to either Case or Test Null.


Context

Textual labels, such as 'type', 'x' and 'a', in:-

       ≺ ≺type≻≺=c≻, ≺2≻≺x.a≻, ≺4≻≺y.e≻, ≺cont≻≺z.i≻, ≻

disappear as the systems (that are represented by the text) are input to graph C (in our electronic store) - this happens, because labelled role and path identifiers, such as ≺type≻≺ and ≺x.a≻, are reified as text-less systems in C - remember that, in Basic Concepts, we took a conscious decision to make our identifiers first class citizens, thus merging the worlds of systems and identifiers, and so merging the software support required by these worlds.

Admittedly, making role and path identifiers into first class citizens can make some of our code difficult to decipher. However, we have already illustrated some advantages; we were able to change some of the identifiers in the Test Null code; and, as the worlds of systems and identifiers are supported by the same software, we have gained enhanced generality as well as reduced programming effort (for us at least). There are more advantages to be gained; in later examples, we make much more sophisticated use, of our extra freedom, by creating and evolving path identifiers; we could go further and add programs to some identifiers, making them 'live' systems; we have yet to explore where that might lead.

We have, just, used the term 'first class citizen'. In a sense, this terminology has no meaning in our modelling style; we only have one type of object, a system, so everything that we model is a first class citizen.

As we said above, the reifications of ≺type≻≺ and ≺x.a≻ that provide our role and path identifiers generalise the concept of identifiers, as found in most programming languages. It is, therefore, sensible to look at the capabilities of high level language identifiers, such as i, j, k, fred, etc, to see if we have managed to capture all of their capabilities. In fact, some of the capabilities are not captured in the way that we would expect, but are provided in different ways.

Our interpreter works within a context that is provided by the sub-graph of C, which 'hangs off' the interpreter's own node in C. Role and path identifiers enable the interpreter to 'find' systems, within its context, as it interprets its sequence of bind operations. The bind operation's parameters provide path identifiers that tell the interpreter where to find the systems involved in the binding. We can have many interpreters operating in parallel with each other, with each having its own context.

One startling omission, from the above, is the nesting of contexts that is found in many high level languages; this allows the 'meaning' of identifiers to be overridden as a program moves down the nesting. One way of getting round this deficiency is to extensively use our concurrency capabilities, spawning many 'small' processes, each with its own interpreter. Alternatively we can model the block structure within the context of an interpreter; however, currently bind operations would have to explicitly navigate this structure; there would be no implicit override mechanism. Clearly another approach would be to build knowledge of block structuring into the interpreter.


Graph Transformations

Our minimal-bind operation performs the minimum transformation on the graph C; it changes just one line in the graph. Earlier sections have shown that we can build more complex graph-transformations out of this minimal transformation. Hence, we can view the language we introduced in Human-Interface as a language for building graph-transformations; the ability to build ever more complex graph-transformations is at the heart of our modelling style. In the following sections we continue to develop this ability.


Push, Pop and Append

We have already defined the Push operation:-

      ≺
          ≺complex-type≻≺pushc≻, ≺chaintop≻≺top≻, ≺pushed≻≺psd≻, ≺contn≻≺continuation≻,
          ≺type≻≺=c≻, ≺2≻≺NULL≻, ≺4≻≺temp.¿≻, ≺cont≻≺current.continue≻,
          ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺top≻, ≺4≻≺temp.tail≻, ≺cont≻≺current.continue≻,
                                   ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺psd≻, ≺4≻≺temp.head≻, ≺cont≻≺current.continue≻,
                                                            ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺temp.¿≻, ≺4≻≺top≻, ≺cont≻≺continuation.¿≻ ≻
      ≻ ≻ ≻

We can now add the Pop and Append operations:-

      ≺
          ≺complex-type≻≺popc≻, ≺chaintop≻≺top≻, ≺popped≻≺ppd≻, ≺contn≻≺continuation≻,
          ≺type≻≺=c≻, ≺2≻≺top.head≻, ≺4≻≺ppd≻, ≺cont≻≺current.continue≻,
          ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺top.tail≻, ≺4≻≺top≻, ≺cont≻≺current.continue≻,
                                   ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺top.id≻, ≺4≻≺top≻, ≺cont≻≺continuation.¿≻ ≻
      ≻ ≻

and:-

      ≺
          ≺complex-type≻≺appendc≻, ≺chainbottom≻≺bottom≻, ≺put≻≺pt≻, ≺contn≻≺continuation≻,
          ≺type≻≺=c≻, ≺2≻≺pt≻, ≺4≻≺bottom.head≻, ≺cont≻≺current.continue≻,
          ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺NULL≻, ≺4≻≺bottom.tail≻, ≺cont≻≺current.continue≻,
                                   ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺bottom.tail≻, ≺4≻≺bottom≻, ≺cont≻≺continuation.¿≻ ≻
      ≻ ≻

The fifth line of the Pop code probably needs some explanation; it is only needed if the role 'top' has no system associated with it; that is to say, if 'top' is the role of nothing within the interpreter. In the graph C each system is a component of itself with role id. Our definition of the bind operation said that, if the path identified by its parameter 2 had no system at its end, then an empty system should be created to go at the end of the path identified by its parameter 4. Because of the last two sentences, we know that the fifth line ensures that an empty stack always has, at its head, an empty system rather than a null system.

We have already said that 'top' and 'psd', in the Push code, are labels for path identifiers. We are also assuming that 'top', 'ppd', 'bottom' and 'pt' in the Pop and Append code are labels for path identifiers; this means that the code 'top.head', 'top.tail', 'top.id', 'bottom.head' and 'bottom.tail' all represent concatenation of path identifiers, as described in Human-Interface.


Stacks and Queues

We are now in a position to provide stacks and queues (very similar to cases).

      ≺
          ≺complex-type≻≺stackc≻, ≺stacktop≻≺top≻, ≺pushed≻≺psd≻, ≺popped≻≺ppd≻, ≺contn≻≺continuation≻,
          ≺push≻≺ ≺complex-type≻≺pushc≻, ≺chaintop≻≺top≻, ≺pushed≻≺psd≻, ≺contn≻≺continuation≻ ≻,
          ≺pop≻≺ ≺complex-type≻≺popc≻, ≺chaintop≻≺top≻, ≺popped≻≺ppd≻, ≺contn≻≺continuation≻ ≻
      ≻

and:-

      ≺
          ≺complex-type≻≺queuec≻, ≺queuestart≻≺top≻, ≺queueend≻≺bottom≻, ≺gotten≻≺ppd≻ ≺putted≻≺ppd≻, ≺contn≻≺continuation≻,
          ≺get≻≺ ≺complex-type≻≺popc≻, ≺chaintop≻≺top≻, ≺popped≻≺ppd≻, ≺contn≻≺continuation≻ ≻,
          ≺put≻≺ ≺complex-type≻≺appendc≻, ≺chainbottom≻≺bottom≻, ≺put≻≺pt≻, ≺contn≻≺continuation≻ ≻
      ≻

Then, if a program needed to push onto the stack, it would include code, such as the following:-

      ≺
          ≺complex-type≻≺push-invocationc≻, ≺stack≻≺stck≻, ≺pushed≻≺pshd≻,
          ≺type≻≺=c≻, ≺2≻≺pshd≻, ≺4≻≺psd≻, ≺cont≻≺current.continue≻,
          ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺current.continue≻, ≺4≻≺continuation.¿≻, ≺cont≻≺stck.push≻, ≺continue≻≺rest_of_program≻ ≻
      ≻

and similarly for popping, putting and getting.


Copy List

Given the results of the earlier sections, copying a list (held as a head/tail chain) is fairly easy:-

      ≺copylist
          ≺complex-type≻≺copy-listc≻, ≺source≻≺src≻, ≺destination≻≺dest≻, ≺continue2≻≺contin≻,
          ≺type≻≺=c≻, ≺2≻≺src.head≻, ≺4≻≺dest.head≻, ≺cont≻≺current.continue≻,
          ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺src.tail≻, ≺4≻≺src≻, ≺cont≻≺current.continue≻,
                                   ≺continue≻≺ ≺complex-type≻≺testnullc≻, ≺test≻≺src≻, ≺continue2≻≺contin≻,
                                                            ≺continue1≻≺ ≺type≻≺=c≻, ≺2≻≺NULL≻, ≺4≻≺dest.tail≻, ≺cont≻≺current.continue≻,
                                                                                       ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺dest.tail≻, ≺4≻≺dest≻, ≺cont≻≺current.continue≻, ≺continue≻≺copylist≻ ≻
      ≻ ≻ ≻ ≻

A typical step in this program is shown by:-

We expained the purpose of the third line above when we considered the pop operation; it makes sure that the destination can never be a null system. The parameter, source, initially points at (i.e. gives a path identifier for) the list to be copied; the copy-list program then uses this parameter to work its way down the list until it eventually reaches the null tail at the end. The parameter, destination, initially points at (i.e. gives a path identifier for) an empty list (not a null list); the copy-list program uses this parameter to work its way down the copied list until the list is fully copied. Note, that when the copy-list program finishes its task, the parameters, source and destination, do not point at (i.e are not path identifiers for) the original list and its copy, but point at the ends of the lists. It is assumed that any program invoking the copy-list program keeps pointers to the starts of these lists.

The end of the above code might seem somewhat convoluted; this is because it is trying to ensure that the end of the chain has a no system with role 'tail'; then we can always use the Test Null operation to find the end of a chain.


Reverse List

Reversing a list is slightly more complicated; we can use:-

      ≺reverselist
          ≺complex-type≻≺reverse-listc≻, ≺source≻≺src≻, ≺destination≻≺dest≻, ≺continue2≻≺contin≻,
          ≺type≻≺=c≻, ≺2≻≺null≻, ≺4≻≺temp.¿≻, ≺cont≻≺current.continue≻,
          ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺dest≻, ≺4≻≺temp.tail≻, ≺cont≻≺current.continue≻,
                                   ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺src.head≻, ≺4≻≺temp.head≻, ≺cont≻≺current.continue≻,
                                                            ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺temp.¿≻, ≺4≻≺dest≻, ≺cont≻≺current.continue≻,
                                                                                     ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺src.tail≻, ≺4≻≺src≻, ≺cont≻≺current.continue≻,
                                                                                                              ≺continue≻≺ ≺complex-type≻≺testnullc≻, ≺test≻≺src≻, ≺continue1≻≺reverselist≻, ≺continue2≻≺contin≻ ≻
      ≻ ≻ ≻ ≻ ≻

A typical step in this program is shown by:-

The parameter, source, initially points to (i.e. gives a path identifier for) the list to be reversed; the reverse-list program then uses this parameter to work its way down the list until it eventually reaches the null tail at the end. Each step in the reverse-list program creates an empty system to be pointed at by the parameter, destination, and then gives it appropriate systems for its head and tail roles. Note, that when the reverse-list program finishes its task, the parameter, source, does not point at (i.e is not a path identifier for) the original list, but points at the end of the list; the parameter, destination, does point at the reversed list. It is assumed that any program invoking the reverse-list program has kept a pointer to the start of the source list. The destination parameter should initially point at a null system, i.e. there should initially be no system at the end of the path identified by dest.


Semaphore

We are now in a position to give the code for the semaphore that we promised when we provided the P and V code. Remember that the P and V code is:-

      ≺
          ≺complex-type≻≺Pc≻, ≺semaphore≻≺intsem1≻, ≺user≻≺user1≻,
          ≺type≻≺=c≻, ≺2≻≺current.continue≻, ≺4≻≺semaphoreset.intsem1.userset.user1.continuation≻, ≺cont≻≺empty.¿≻, ≺continue≻≺rest_of_program-1≻
      ≻

and

      ≺
          ≺complex-type≻≺Vc≻, ≺semaphore≻≺intsem1≻,
          ≺type≻≺=c≻, ≺2≻≺semaphoreset.intsem1.continuation≻, ≺4≻≺semaphoreset.intsem1.current≻, ≺cont≻≺current.continue≻, ≺continue≻≺rest_of_program-2≻
      ≻

In Basic Concepts we said that the interpreter for the semaphore cycles round the users of the semaphore, interpreting the same sequence of bind operations for each of them; the sequence starts by testing whether or not the user has requested a lock (with a P operation) - i.e. it sees if the bind operation for the lock has provided a continuation program so that it can be restarted; if not, it proceeds to the next user. If a continuation program has been provided for the user, it clears the stored value of this continuation, and gives the value to the user's 'current' role, and then idles itself; later, the unlock (V) reawakens it, by giving a value to the semaphore's 'current' role; it then cycles round the users again. This requires the role, in the semaphore's interpreter, that is identified by 'sema4', to be given a system with the following code:-

      ≺
          ≺complex-type≻≺semaphorec≻, ≺user≻≺user1record≻,
          ≺type≻≺=c≻, ≺2≻≺sema4.user.continuation≻, ≺4≻≺temp.¿≻, ≺cont≻≺current.continue≻,
          ≺continue≻≺ ≺complex-type≻≺testnullc≻, ≺test≻≺temp.¿≻,
                                  ≺continue1≻≺ ≺type≻≺=c≻, ≺2≻≺sema4.user.next≻, ≺4≻≺sema4.user≻, ≺cont≻≺current.continue≻, ≺continue≻≺sema4.¿≻ ≻,
                                  ≺continue2≻≺ ≺type≻≺=c≻, ≺2≻≺empty.¿≻, ≺4≻≺sema4.user.continuation≻, ≺cont≻≺current.continue≻,
                                                             ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺temp.¿≻, ≺4≻≺sema4.user.interpreter.current≻, ≺cont≻≺current.continue≻,
                                                                                      ≺continue≻≺ ≺type≻≺=c≻, ≺2≻≺sema4.continue.continue1≻, ≺4≻≺continuation.¿≻, ≺cont≻≺empty.¿≻ ≻
      ≻ ≻ ≻ ≻

The above assumes that, in the system with role identified by 'userset' within the semaphore's interpreter, there is a component system (e.g. user1record) for each user of the semaphore, and that this system has:-