Algorithmic Modelling Reference Model

Syntax of and Processing Related to the Behaviour and Composition of Algorithmic Models

Final Community Group Specification 18 April 2013

this version:

latest version:

Russell Potter

Table of Contents

1 Introduction
2 Namespaces
3 Common Attributes
4 The Algorithmic Reference Model
4.1 Type Hierarchy
4.2 Component Compositing
4.3 Partitioning
4.4 Imperative Execution
4.5 Object Group Stereotyping
4.6 Inter-process Synchronisation
4.7 Message Timing and Sequencing

1 Introduction

A "model" refers to an abstract description of the composition and relative dynamic behaviour of the sub-parts of some system

This specification describes an XML representation of such a model, to be used as reference for more specific model types


model element
XML element appearing in a model document whose name-space matches that of the namespace defined in this specification
non-model element
element appearing from a namespace other than that defined in this specification

The presence of each of non-model elements appearing, verbatim, in a model document causes the creation, at run-time, of a corresponding "artefact", situated within the implementation's run-time environment, each of which are then transformed, in some way, due to the presence of one of more (possibly nested) model elements

While these run-time artefacts are, generally, some type of XML Information Item, data in other formats may also be referenced through the use of a special attribute named "opaque", whose value contains an IRI which will, when resolved, yield the opaque data

2 Name-spaces

The name-space of this specification, used as the default name-space in the examples below and using the prefix "model" in an XPath context [XPATH], is "http://www.w3.org/ns/model" .

The other name-spaces used in this specification are given in the following table

xshttp://www.w3.org/2001/XMLSchemaXML Schemas
schttp://www.w3.org/2005/07/scxmlState Chart
xmlhttp://www.w3.org/XML/1998/namespaceused to specify element IDs (via "xml:id" [XML11 ])

3 Common Attributes

There are several attributes common to all model elements

Related elements may possess a "constraint" attribute constraining the element's relationships to other elements, as expressed by an XPath expression evaluating to a non-zero value when the constraint holds

Those elements best classified as part of a finite state machine may contain attributes from the State Chart [STATECHART ] name-space having a local name reflecting equivalence between the roles a Chart element of that local name plays in the State Chart semantics, and the role the element containing that attribute plays in the state machine in which that element participates

The value of such an attribute consists of a comma-separated list of name-value pairs, in each name and value represents those of that State Chart attribute.

The receipt or sending of a message to or from, respectively, an element may be specified to trigger the execution of some process by the appearance, on the element, of the "receives" and "sends" attributes, whose value is the ID of a process when, when executed, is, to be passed a single parameter containing a reference to the sent or received message

Any element may also contain a "type" attribute whose value contains a reference to the element of the XML Schema [SCHEMAS ] type of that element

The example below illustrates a use of these common attributes: the "len" attribute of the "parent" element (which itself acts as a state within a state machine), has a type identified in the XML Schema element, located elsewhere in the document having the ID "type", constrained to be equal to the number of "child" elements (the first of which acts as a transition to the second within that state machine). The parent element executes the processes having IDs "http://www.example.com#c" and http://www.example.com#d", respectively, on receipt of and when sending a message

<parent sc:state=type="#type" sends="http://www.example.com#c"

    <child xml:id="child">
    <child sc:transition="target=#child">

4 The Algorithmic Reference Model

The model itself consists of any nested combination of the following, beneath a top-level "model" element (each of the items below will be further discussed when introduced below)

This model is designed to act as a reference over which more specific types of models may be layered (possibly with some type-specific modifications)

4.1 Type Hierarchy

The type system established by XML Schemas [SCHEMAS ] is augmented in two ways: by the specification of namespaces and the addition of methods (that is, behaviourattached to an artefact).

A namespace root is created by the appearance of a "namespace" element, and names are added to such namespaces by the appearance of a "name" attribute on an element, the value of which specifies the name itself, and the value of the "within" attribute of which specifies either the name-space (for "top-level" names) or name (other than "top-level" names) within which the name exists

Methods are created by appearance of a "to" attribute on an element, the value of which specifies the ID of the element to which the method is attached, and a "content" attribute, the value of which specifies the ID of the "process" element constituting the content of the method (both these attributes must be present on the element for the method to attach)

The following example specifies a namespace, within which the names "abc" and "xyz" exist, and the attachment of a method consisting of a process having ID "z" to an element with ID "c"

<namespace xml:id="a" />

<b name="abc" within="#a" />
<c name="xyz" within="#a" />

<d to="#c" content="#z" />

4.2 Component Compositing

This aspect of the model refers to the definition of objects that may be composably called on each other at run-time

This is specified through the use of one or more attributes of two possible types

The first, the "provides" attributes, specifies, in the attribute's value, the XML Schemas element of the type representing an interface the run-time object that element represents provides

The value of the second, the "requires" attribute, contains the ID of the XML Schemas type of a component that an implementation must determine to be present in the component run-time system, so the run-time object may make calls to other run-time objects providing that interface

The following example illustrates the use of component compositing, declaring an element providing two components having the XML Schemas IRIs of "http://www.example.com#x" and "http://www.example.com#y", and another requiring an XML Schemas IRI of "http://www.example.com#a"

<a provides="http://www.example.com#x"
            provides="http://www.example.com#y" />
<b provides="http://www.example.com#y"
            requires="http://www.example.com#a" /> 


4.3 Partitioning

The (possibly nested) "partition" element isolates run-time artefacts generated by declarations in the sub-tree of the element from artefacts outside the sub-tree

The following example demonstrates three partitioned elements having tags "a", "b" and "c" isolated from a second partition containing both an element with tag "d" and a sub-partiton containing elements with tags "e" and "f", respectively

    <a />
    <b />
    <c />
    <d />
        <e />
        <f />

4.4 Imperative Execution

The term "imperative Processing", as specified in the "process" element, refers to a set of "imperative statements" transforming, at run-time, a stream of artefacts arriving on the designated the "input stream" of that process (as specified by the element the ID of which forms the value of the "in" attribute), then output to the element referenced in the value of the "out" attribute

The actual content of the process consists of the result of either resolving the reference to an XProc step [XPROC] forming the value of the element's "step" attribute, or of resolving a reference to the State Chart [STATECHART ] Executable Content forming the value of the element's "script" attribute

The following example demonstrates a process the content of which is formed from an XProc step located at "http://www.example.com#step" taking, as input, the output of a process the content of which is formed from the State Chart executable content located at "http://www.example.com#sc"

<process xml:id="proc1"
            step="http://www.example.com#step" />
<process in=#proc1"
            script="http://www.example.com#sc" />

4.5 Object Group Stereotyping

A "stereotype" creates a "template" instantiated, at run-time, by a group of objects, each fulfilling named "roles" within that stereotype

The template for the stereotype itself is established by the appearance of a "stereotype" element containing one or more "role" sub-elements, each containing a "name" attribute, the value of which names the role, and a "matches" attribute, the value of which contains an XPath expression constraining the location and/or nature of the role within the stereotype

This XPath expression, the context node of which is set to the element in on which the "stereotype" attribute is located, is augmented with a "model:role" function returning the node bound to the role, within the stereotype having the name passed in the function's first argument

The following example illustrates a "family" stereotype, whose "mother" role is constrained to be a female whose children include the "son" or "daughter" role in the stereotype, whose "father" role to a male constrained in the same manner, whose "son" role is constrained to be a male whose father or mother has the "father" or "mother" role in the stereotype and whose "daughter" role as a female constrained in the same manner, instantiated by two elements denoting a mother and father, and two denoting a son and daughter

<stereotype xml:id="family">

    <role name="father" matches="person[@gender='male']
          and (person/@mother is model:role('mother')
          or person/@father is model:role("father'))" />

    <role name="mother" matches="person[@gender='female']
          and (person/@mother is model:role('mother') or
          person@/@father is model:role("'father'))" /> 

    <role name="son" matches="person[@gender='male']
          and (person/child[model:role('son')] or
          person/child[model:role('daughter')])" />

    <role name="daughter" matches="person[@gender='female']
          and (person/child[model:role('son')] or
          person/child[model:role('daughter')])" />

<group stereotype="#family">

    <person xml:id="john" gender="male"
                             role="father" >
             <person xml:id="emily"
                           mother="#jenny" />

                <person xml:id="tom"
                       mother="#jenny" /"&;gt
        <person xml:id="jenny" gender="female"
                                  role="mother" />
                <person xml:id="emily"
                        mother="#jenny" />
                <person xml:id="tom"
                       mother="#jenny" />

4.6 Inter-process Synchronisation

This aspect of the model refers to the capability of a process to wait to start until signalled by the process identified by the content of the element's "wait_on" attribute, and to notify when completed the process identified by the content of the element's "notify" attribute.

The following example illustrates two elements, the first of which waits got the second to complete which, itself, notifies the first on completion

<a wait_on="#a" xml:id="b" />
<b notify="#b" xml:id="a" />

4.7 Message Timing and Sequencing

The timing of messages between objects and the relative order of these messages is specified through use of the "messaging" element

Within this element are located a "path" element, the children of which identify the path of the messages, followed by a set of "message" elements, each identifying a message along that path

The children of the "path" element collectively identify the path of run-time objects, within the model, for which messaging is specified, while each "message" sub-element represents a single message along that path, to be referenced by certain timing- and sequencing-related attributes of the remaining elements

The "starts" attribute of such an element references the message creating, when received, the run-time object corresponding to the element on which the attribute appears, while the value of the "ends" attribute destroys the analogous object

The value of the "delay" attribute specifies the delay, in seconds, between the sending of the message and the creation or destruction of the object

The value of the "after" attribute references the message that must may only be sent after the run-time object has received the message referenced in the value of the "ctx" attribute, while the value of the "before" attribute references the message that may only be sent before the analogous message has been received

Similarly, the value of the "delay" attribute specifies the delay, in seconds, between the the receipt of the message and the message before or after it must be received

The following example demonstrates a path of three elements the first of which must creates start the second, the first of which may only be sent after the second, with a delay of 4 seconds

        <a xml:id="a" />
        <b xml:id="b" />
        <c xml:id="c" />
    <message xml:id="x" />
    <message xml:id="y" />
    <a starts="#y" />
    <b after="#x" ctx="#y" delay="4" />


David C. Fallside; Priscilla Walmsley XML Schema Part 0: Primer Second Edition. 28 October 2004. W3C Recommendation. URL: http://www.w3.org/TR/xmlschema-0/
Jim Barnett; Rahul Akolkar; RJ Auburn et al State Chart XML (SCXML): State Machine Notation for Control Abstraction. 6 December 2012. W3C Working Draft. URL: http://www.w3.org/TR/scxml/
Norman Walsh; Alex Milowski; Henry S. Thompson An XML Pipeline Language. 11 May 2010. W3C Recommendation. URL: http://www.w3.org/TR/xproc/
James Clark; Steve DeRose XML Path Language (XPath) Version 1.0. 16 November 1999. W3C Recommendation. URL: http://www.w3.org/TR/xpath/
Tim Bray; Jean Paoli; C. M. Sperberg-McQueen; Eve Maler Extensible Markup Language (XML) 1.1 (Second Edition). 16 August 2006. W3C Recommendation. URL: http://www.w3.org/TR/xml11/