Algorithmic Modelling Reference Model

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

Final Community Group Specification 9 November 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 Transformative Formulae
4.6 Object Group Stereotyping
4.7 Synchronisation
4.8 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 ])
mhttp://www.w3.org/1998/Math/MathML/ used to specify the [MathML ] content of transformative functions
xlinkhttp://www.w3.org/1999/xlink used in hyper-linking

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

Elements corresponding to an element within an XMI [XMI] model contain an attribute named "xmi", the value of which specifies the URL 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), and corresponds to an XMI element having the URL "http://www.example.com#xmi". 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, behaviour attached 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-partition 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 by 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 Transformative Formulae

Transformative formulae are mathematical functions producing an output as a transformation of some or all of a defined set of a defined set of named inputs

The content of this function may be either specified using a hyper-link or using an in-line content mark-up representation of a MathML formula

Formulas may be nested and, where the nesting occurs inside the argument of an outer formula, this indicates the outer argument's value is derived from that produced by the nested formula, whether present as a hyper-link or in-line

A formula is specified using an element having a tag named "formula", the first child of which is an element a tag named "args", the children of which each represent a formula argument, as an elements having a tag named "arg", the value of the "name" attribute of each indicates the argument's name

Each of these argument names create an implicit Bound Variable having that name, for use in referencing such variables within the formula

The following example illustrates a formula producing an addition of its arguments, the first of which is derived from the formula located at "http://www.example.com/fmla" and the second a as formula produced from a subtraction of the first argument from the second

        <arg name="x"> 
             xlink:href="http://www.example.com/fmla" />
        <arg name="y"> 
                    <arg name="a" /> 
                    <arg name="b" /> 
                    <m:minus />

4.6 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.7 Synchronisation

This aspect of the model refers to the capability of a model element to wait until signalled by an element identified by the element's "wait_on" attribute, and to notify an element identified in the element's "notify" attribute.

The following example illustrates two elements, the first of which waits for 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.8 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/
XML Linking Language (XLink) Version 1.1. 6 Mey 2011. W3C Recommendation. URL: http://www.w3.org/TR/xlink11/
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/
XML Schema MOF 2 XML Mapping. 8 October 2011. Object Management Group Specification. URL: http://www.omg.org/spec/XMI/2.4.1/PDF
Stephen Buswell; David Carlisle et al Mathematical Markup Language (MathML) Version 3.0 . 21 October 2010. W3C Recommendation. URL: http://www.w3.org/TR/MathML3/
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/