Rapide Language Tutorial

The Language Trail

Purpose of the Rapide system of languages and tools

   The Rapide system is aimed at quickly specify, model and test complex distributed, concurrent systems. A classic academic example of them is  the dining philosophers problem. This problem exhibits some of the complexities that the Rapide system aims to solve. The philosophers all act concurrently and do not share access to a common state. Furthermore, the philosophers only interact with the table through a set of actions between a philosopher and the table. This is a simple example that does not require accessing more advanced Rapide features, which will be discusesd later, and we only use the example to show how to construct a Rapide architecture description.

Architecture Construction

    In computer systems, software architecture has been addressed in a number of ways as  illustrated in: Three Concepts of System Architecture.

    Briefly, an architecture is a decomposition of a system into its components and the interconnections among them. A component of an architecture is a part that can be considered a black box at a particular level of detail. An interface is the published way a component in a system interacts with other components in the system.

Traditional components and interfaces

   In traditional languages, interfaces are composed from functions, operations/message, signals, and there is a number of different concepts "Sw components".

    Libraries have been around for a long time, since the linpack library for linear algebra written in FORTRAN, all C standard libraries etc.
    In more structured languages the library concept was offered support in the "package" structure, like the one found in ADA, which incorporates data types and functions as part of the interface definition. In C or early C++ these packages are not present but programmers and Sw engineers have used the language preprocessor and file system to create "header files" and through programming discipline this has helped to mimic the package behavior. In the most recent widely used languages (C++ and Java) the concept of package as a set of classes, types and functions has been incorporated through the "package' in Java and through "namespaces" in C++.

    All these mechanisms have in common is that they provide good support for describing the "offered" interface by the Sw module but offer very little if any support to specify the required interface. In languages with explicit package definitions, the clause "import", "use" or "with" offers some information on other required packages, and in disciplined C use, the #include preprocessor directives, also give a hint of what is needed. In no case a explicit "requires" clause with enough granularity (i.e. function level) is provided. In OO languages, the basic unit of abstraction is the class, and as such it is the main place to specify the offered interface, but again, there are no languages that offer the ability to specify the required interfaces.

     As far as specifying the dynamic behavior of interfaces, common languages offer very little support, most of them rely on a synchronous semantics of function invocations, and offer no support to specify other types of behavior. Other languages like SDL or ADA offer their own concurrency semantics (CSP, rendez-vous) but offer no support either to specify alternative mechanisms. So far, no common languages are able to specify behavior in their interfaces without providing an implementation of the module.

The Rapide approach

     Rapide implements an interface connection architecture model as described in Three Concepts of System Architecture. It provides tools to express both the functionality offered by each interface,  the required functionality from other modules/interfaces, and the connections between interfaces. Rapide also allows for expressing the requirements/constraints an interface behavior has to exhibit.

    The main elements that define a Rapide interface  are:

• Actions & Functions :   These are the primitives the interface uses (provides or requires) to interact with the environment.
• Actions are defined by a name and a set of typed parameters. They represent a "one-way" message to be sent or received by the interface. Actions are asynchronous from the point of view of sender and receiver.
• Functions represent a typed request/reply pair with synchronous interaction between the involved interfaces.
Actions and functions may be grouped in Services  which, while not adding or changing the semantics of the interface, it makes defining interfaces more convenient and reusable by introducing a more refined level of granularity.
 
• Behavior: An interface behavior can be expressed in three ways, either attaching an implementation module to the interface, defining an architecture that implements the interface, or describing its behavior by means of reactive rules that specify the reaction of the interface to events offered to it.
    Interfaces are assembled into an architecture by using connections . Connections as opposed to other languages are not passive elements, Rapide allows connection behavior to be specified in terms of the relationships that the events going into a connection and the ones coming out have. Connections in Rapide do not connect interfaces, they connect events to events, possibly qualified with an interface name. Connections can also be used to connect patterns of events to other events or patterns of event.
    The semantics of a connection in Rapide is such that when the triggering event is present (expressed in the left hand side of the connections), the connection triggers and produces the event specified in the right hand side of the connection.
    Three types of connections are supported by Rapide: Basic connections (A to B), pipe connections (A => B), and agent connections (A ||> B)
• Basic connections produce an identity between the event that triggers the connection and the one that results from it. Events A and B are the same.
• Pipe connections produce a causal relationship on successive B events resulting from repeated  connection firings. This causal relationship is independent of any other relationship between the different A events that trigger the connection.
• Agent connections produce a stream of unrelated B events upon repeated firings.
It is important to take a deeper look to the semantics of Pipe and Agent connections. Pipe connections behave as a single thread of control when producing B events, regardless of the concurrency behavior of the triggering A events. An Agent connection behaves as if each B event is generated by a different thread of control, and thus its produced B events are not related to each other. Mind that the thread of control refers to the connection itself and does not imply anything about the concurrency structure of the interface or interfaces that generate the A events. Both Pipe and Agent connections can carry asynchronous actions or synchronous functions, as the synchronicity between interfaces  is not related to the one of the connection.

Event Model and posets:

The main engine behind the power in Rapide is its model of computation based on Partially Ordered Sets of Events (posets). Under this model, a computation is represented as a set of events generated by the execution of the system. Each event represents the occurrence of an activity within a program. At a particular level of detail. Events are generated by communication between two components of the system. Events are generated by actions and functions. Actions generate a single event, while functions generate two events; one corresponding to the function invocation and another to the function return. Events in Rapide are typed, that means that they are characterized by the number, order and type of their arguments.

Events are ordered with respect to two criteria, time and causality. Both these criteria yield partial orders on the event set of a computation.

• Time order is specified with respect to local clocks. In Rapide there is no required global clock. Events are ordered with respect to the clocks that apply to it. Event times can only be compared with times obtained by clocks in its scope. For a complete description of the clock model in Rapide, consult chapter 10 of Executable LRM.
  This fact of multiple clocks and the relationship of events to clocks imply that events that are referred to different, non related clocks are NOT ordered with respect to each other.
• Causal order represents the generator/generated events. Two elements in Rapide may generate dependent events. Interfaces via their behavior, and connections. Two events A and B are dependent if (A precedes B):
• A and B are generated by the same process or
• A process is triggered by A and then generated B or
• A process generated A and then assigns to a variable v, another process reads v  and then generates B or
• A triggers a connection which generates B or
• A precedes C which precedes B (transitive closure).
The following diagram is an example of time and causality dependency:     By introducing this concept of order and causality, Rapide enables the programmer to explicitly visualize and analyze the execution of the system. In a more sophisticated use of this facility, a system behavior may be expressed as constraints on how events can relate to each other, as explained in the section  on constraints .

Structure of the process language:

Events are generated by processes in Rapide, Processes are the unit of sequential execution and also the means of achieving parallelism.

Conventional programming of internally concurrent applications is supported in Rapide with modules. A module implements an interface and consists of a number of independent processes, each of them executing a sequence of statements as any other procedural language. Chapter 9 of the Executable LRM details the construction of modules.

Modules and Processes

A process represents a single thread of control which executes statements sequentially. A module can contain any number of processes. Apart form processes, modules also have an initial and final executable parts (statement lists). Alternatively, a Module can be also implemented with other modules, interfaces and connections.

Conventional programming elements:

       To program modules, Rapide offers a full range of structured programming statements  as described in chapter 9 of  the referenced  Rapide 1.0 Executable LRM.

The available statements are:

• Conditional: Structured if...else construct
• Do:  Generalized looping
• Exit: Allows to exit an enclosing Do statement
• Next: Allows to skip the current execution of a loop.
• Case: Multiple choice branching of control
• Return: Complete the execution of the enclosing function
• Await: Allows to suspend the process while waiting for an event or pattern of events to happen
• Assert: Allows to express properties that need to hold at the execution point where the statement happens. The system will generate an "inconsistent event" in case the assertion is not true.
• Null: Does nothing.
• Functions Call: Invokes the execution of the appropriate function body. Chapter 6 of  Rapide 1.0 Executable LRM.  describes the mechanism of parameter association in function calls.
• Raise: Generates an exception. Section 8.3 of  Rapide 1.0 Executable LRM. describes the exception mechanism in Rapide.

Reactive Statements and Process communication

    Processes communicate by invoking actions or functions on connections, which will eventually be tied to other processes at the other end. To process these calls Rapide provides the await statement  together with the when statement which is a syntactical simplification for a set of common await use cases.

    The await statement suspends the execution of the process that invokes it until a pattern that matches one of its pattern clauses occurs. at that point, and provided the process becomes active, the associated statements to the matched pattern execute and the process continues. This statement includes one or more patterns that may be matched by events. When one of the patterns matches, its associated body of statements (its alternative) executes. If more than one match becomes available simultaneously on an await statement, one of the alternatives is chosen arbitrarily.
An await statement may also contain an else clause. If this clause is not present, the await statement suspends the process that executed it till one of the patterns matches. if and else clause appears, the await statement checks for the existence of a pattern match when executed, and if no such match exists it executes the else body and continues.

    The When statement   is a form of loop (do statement) which repeatedly executes upon matches of its pattern. A when statement waits for a match of its trigger and then executes its body. The when statement may be terminated with an exit statement.

To generate events, a Rapide module can invoke functions and actions on a connection or, if no connection is given, the self module is assumed.

Module as Processor

    A way to consider a module is  as a processor entity that provides variables (storage) and processing capacity to processes. In this view, modules can be of two types, parallel and serial, corresponding to the conventional interpretation of single and multiprocessor systems.

    Parallel modules provide a concurrent execution environment to its processes with no synchronization other than the explicitly programmed in the processes themselves. Furthermore, no assumption can be made on the relative speed of each process.

    Serial modules provide a "one-at-a-time" execution to its process. The semantics is non-preemtive. This means that once a process is running, it will run forever or until it yields control. Yielding control may occur in a number of ways.

• Explicit invocation of a pause or delay timing clause.
• An await or when statement
• The completion or termination of a function call
As described in section 7.6 of Rapide 1.0 Executable LRM, the states a process can be in are: Ready, Active or Suspended. A process is active when it is running, Ready when it is not running and is not waiting for any external event, and Suspended when the process needs an external event or timer expiration to continue execution.

Reactive Statements: Rules.

    Apart from programming processes with lists of statements, Rapide offers a rule-based approach to describe interface and module behavior. Rules  are pieces of code that execute when certain preconditions are matched. The execution of a rule may result in some events being generated.
    Rules appear in await and when statements, in interface behavior and in connection specifications. The basic structure is the same   containing a placeholder declaration block where identifiers to hold values associated to events are declared, an event pattern to be matched and a body to execute upon triggering. The scope of the placeholders declared covers both the pattern and the body so that values appearing in the matched events can be used in the rule body.

The most common case for using these rules is in defining interface behavior without the need for a module implementation;  in which the body of the rule will modify the interface state variables and generate other events.

A special case of a reactive rule is the expression of a connection. A connection can be seen as a rule, that when triggered by an incoming event (or pattern of events) will output another set of events (possibly the same, if it is a basic connection). Due to this ability to specify connections as reactive rules, the connection topology can be much more flexible than a one-to-one connection scheme would allow.

Rules consume events when they fire. A particular rule in a module will not fire twice using the same event, although the same event may be used by different modules, if it is visible from more than one module.

Patterns:

One of the most powerful features of Rapide is its pattern language defined over the poset an execution generates.

Matching single events

A basic pattern is used to match a single event . This pattern establishes an event to be matched with some extra information to restrict the kind of events that will match it and to associate values to place holders. As an example, consider:
(?D : dollar) Deposit(D is ?D, A is Savings)

This pattern matches an event whose name is Deposit, with type event(D: Dollar, A: Account) and binds the value appearing as the first argument to the placeholder ?D.

A basic pattern of the form exp@(<parameters>)  will be matched by an event that satisfies the expression, and has the same number and location of parameters as specified in the pattern. As a particular case the expression "@" will be matched by any event. A complete description of basic patterns is found in section 1.3 of the Rapide 1.0 Pattern LRM.

Composing two patterns

Patterns (basic and otherwise) can be composed into a "compound pattern". The connectives to compose them are binary, and as such they compose exactly two simpler patterns into a more elaborated one. For exposition purposes uniquely, the connectives can be classified as:
• Logical compositions:    and, or, disjoint and (~), and union.
• Causal compositions:    follows (->), immediate follows (|>), independence (||).
    Logical compositions correspond to the familiar logical expressions in other languages with some extensions, but basically are ways to state combinations of patterns and when a match is produced:
• A and B will match whenever there there is a subcomputation that matches patterns A and B simultaneously. A subcomputation is a subset of the original computation poset, in both events and their partial order relationship.
• A or B will match if a subcomputation matches A or it matches B.
• A ~ B will match if two disjoint computations (that is they do not share any events) will match A and B, one subcomputation each.
• A union B will match a subcomputation if there are subsets of it that match separately A and B. There is no need for the whole subcomputation to match both A and B (as in the and connective) nor that the matching subcomputations be disjoint (as in the ~ connective).
    The causal compositions draw on the ability of Rapide to express causality as a partial order of events. In this partial order you can express:
• A -> B : Pattern A precedes B, that is, all events of A precede all events of B
• A |> B : Pattern A immediately precedes B. Similar to the previous one, but more restrictive by not allowing transitive dependency to match this pattern, i.e., A->C->B is not a match for A |>B.
• A || B : Patterns A and B are independent, that is no event of A is dependent upon any event in B and vice versa.

Iterating Pattern composition

As an extra facility that allows the expression of more complex patterns, Rapide provides an specialized syntax  to describe iterative patterns. This kind of patterns use the binary composition patterns in a repeated way over a single pattern. In this way Rapide can express patterns like: "Any number of different events that match pattern A" as "[* rel ~]A". The cardinality of matches to this pattern can be specified by one of the following:
• * : To express any number of occurrences, including zero.
• + : To express any non zero number of occurrences.
• range n..m : To express an enumeration from n to m. This is often used in conjunction with a placeholder to reuse the value in the affected pattern.
• object expression : which has to evaluate to one or more objects (an iterator type) that will be used in the matching process.

Restricting Patterns

A last refinement to the pattern language is intended to provide a finer grain of control of when a pattern is matched. Rapide uses two ways to achieve this. One is the use of placeholders in patterns so that when a placeholder is used in any two places in the pattern, it forces the pattern to match computations that have the same value at the placeholder locations. Placeholders may be qualified to be "existential" which are matched by any value of the type, and "universal" which forces the match on all the values present in the computation.

The second one is the where clause of a pattern. It is an arbitrary boolean expression, with no side effects, that evaluates to true or false once the placeholders in the pattern have been bound. The pattern will only match if the where clause returns true. The where clause is called a guard, and the affected pattern is said to be guarded.

Matching Strategy

Pattern match occurs only on the poset visible to the module where the pattern is given. The matching process works as if it first constructed a graph with only the events visible to the pattern's enclosing module, related by the transitive causality relationship of the entire poset. The pattern is matched against the resulting poset, that is ignoring the events that aren't visible to the module.

It is also possible to further restrict a pattern's pool of visible events by using the constraint language's filter construct. The constraint checker's matching process will consider ONLY those events that satisfy the filter. The matching process works as if it first constructs a graph with only the events that satisfy the filter, related by the transitive causality relationship of the original graph. The constraint is checked against the resulting graph, that is ignoring the events that don't satisfy the filter. The constraints used to to express the ACID properties of transactions illustrates this strategy.

Advanced  Topics

Generators

Rapide allows its own structural components like interfaces, connections and architectures themselves to be "first class" citizens of its type system. This means that architectures, modules and connections can be created and manipulated at runtime thereby opening the door to expressing "families of behaviors" or "families of architectures."

Rapide treats interfaces, language types and modules as the "values" of those types. To complete the picture, Rapide provides a way of generating such values with module generators .

A module generator declares a function that generates a module each time it is called. The generator takes a set of parameters that are used to initialize the created module. In a similar fashion, architectures can also be generated in a parametric way. As an example, the well known problem of the dining philosophers with a variable number of philosophers can be expressed as a parametrized architecture.

Usage of Patterns in Architecture Descriptions

As it has been hinted in the rules section, connections can be viewed as rules that produce a set of output events when presented with a pattern of events. This capability allows to express in Rapide connection topologies which would not be expressible otherwise.

A simple multicast connection can be expressed by matching a single event by the connection, and generating a number of events when the connection triggers. Alternatively a "fan-in" connection can be expressed easily by having a number of events to be matched before the connection triggers.

In Rapide, the matching connection pattern is not restricted in anyway. It may be anything that can be expressed in the powerful pattern language.

As such, a connection can collect output from an arbitrary number of modules, e.g., via an iteration pattern, or from modules that produce a particular parametrized event, e.g., via placeholders in the pattern matching, or under arbitrary boolean expressions on the event paramagnets, e.g., via guards. Essentially, a connection can inspect the whole computation poset to produce an output event.

Maps and Constraints

    Rapide provide a a sophisticated support to assert what an architecture's computation should be by providing constraints on the topology of the poset produced by a computation. Rapide allows to express assertions of which patterns are forbidden, e.g., event A cannot precede event B, or what patterns are to be enforced in the poset, e.g., there is no A which depends on B or vice versa.

    Constraints draw fully from the flexibility of the pattern matching language adding simply one of two keywords never and match that respectively correspond to forbidden (or required) patterns that the poset has to conform to (understood in the matching scheme described in the pattern section.

    The other construct that Rapide provides to specify how architectures are to behave are maps . A map is essentially a correspondence between two architectures that allows the translation of events back and forth between the two architectures. This allows the system architects to design a reference architecture where constraints are expressed and behavior specified. Then by defining a map, new architectures and their computations can be checked for equivalence with the reference architecture. A map is defined over a range (an architecture type) and defines what events in its range correspond to event patterns in the posets originated by its domain type.