Balisage Paper: Multitasking algorithms in XForms

Getting Started with XForms

The XForms solutions presented in this paper can be executed directly in current web browsers using a library called XSLTForms. This library relies on the current web browser's XSLT engine to convert the XForms markup into XHTML and JavaScript run-time objects that implement the user interface controls and interaction behaviors specified by XForms 1.1 and XPath 1.0. The XSLTForms library need only be uncompressed into the same web application archive or local directory as an XHTML file, and then the following processing instruction must be placed at the beginning of the XHTML file to enable use of XForms within it:

<?xml-stylesheet href="xsltforms/xsltforms.xsl" type="text/xsl"?>

After processing instructions, such as the one above for XSLTForms, the root html element of the XHTML file would typically be used to declare globally required Namespaces such as for XHTML and XML Events. The XForms markup appears in the html element's two child elements: head and body. The XHTML head element contains the XForms model element, which serves as the parent of the data instance elements and XForms action elements that contain data processing scripts. The XForms model is often written with two attributes: an id, which makes it possible to target the model with XML events that invoke action scripts, and the xmlns attribute to place the model and its descendants (instances, actions, etc.) into the XForms namespace, as follows:

<model id="M" xmlns="http://www.w3.org/2002/xforms">
   ... <!-- Instances, Actions, etc. -->
</model>

The XHTML body element contains the XForms user interface controls that enable the user to interact with the data in the instance elements and dispatch events that invoke the action scripts in the model.

Data Representation

Each instance element in the XForms model can represent one XML data document, as a separate XML document from the containing XHTML document. Multiple instances are differentiated by id attribute values that give each instance a unique name within the containing XHTML document. Throughout all features of XForms, the nodes of XML data are referenced with XPath, and XForms adds to its XPath processor a function instance() which receives the identifier of the desired instance and returns the root element node of the instance's XML data document.

Each instance element's XML document can be expressed as inline content within the instance, or it can be obtained as the XHTML document loads from a URL in the instance element's src attribute. Both options are shown in this XForms code:

<instance id="ORIGDATA" src="./Sort_Data_10.xml"/>

<instance id="DATA">
   <data xmlns="">
      <items>
         <item>
            <num>5</num>
            <name>Alice</name>
            <phone>333-1111</phone>
         </item>
         ... 
      </items>
   </data>
</instance>

The namespace declaration xmlns="" is applied to the data so that XPath expressions can refer to elements of the data without namespace qualification.

In the Data Processing Algorithms section, a sort algorithm puts the item elements above into a numeric or lexicographic order using either the num or name subelement content as the key. The instances above can contain many item elements, perhaps by virtue of declaration or perhaps due to a looping action script that generates large lists of items with keys that are differentiated by suffixes that are randomly generated with the random() function that XForms adds to its XPath processor.

Data instances can also be used to create intermediate variables that help manage interactive processes. As an example, here is an instance fragment showing the data needed to help manage a windowing mechanism for scrolling through large lists of item elements:

<instance id="VARS">
    <vars xmlns="">
        ...
        <window>
            <start>1</start>
            <size>20</size>
            <end>20</end>
        </window>		
    </vars>
</instance>

The user interface mechanisms for using and changing these windowing variables appear in section “User Interface Controls”.

In addition to data instances, an XForms model can also contain bindings that express purely declarative calculations. As an example, below is an XForms bind element that dynamically calculates the window end value based on the window start and size:

<bind nodeset="instance('VARS')/window/end" 
      calculate="../start + ../size - 1"/>

Due to this declarative calculation, the end value is automatically updated any time the window start or size is changed, such as with the imperative code associated with a user interface control shown in section “User Interface Controls”.

One notable aspect of the XPath expression within the nodeset attribute is that the element name vars is omitted. It is not needed because the instance() function returns the root element node of the identified instance, and that root element is vars in this case. This being said, XPath has some mechanisms that enable authors to specify the root element if desired. For example, the above nodeset expression could also be written as instance('VARS')/self::vars/window/end or as instance('VARS')/../vars/window/end).

XForms Actions Pertinent to Data Processing

XForms actions express scripts of one or more commands that are to be performed in response to an XML event. The XForms action elements most pertinent to XML data manipulation are described below. They may be used individually when a script needs only one command, but when a script must perform multiple XForms actions, they are placed within a single containing element named action. In both cases, a script's root XForms action element includes an attribute to indicate the specific XML event that activates the script. The attribute name is ev:event, where ev is an XML namespace prefix that must be mapped to the XML Events namespace (by a namespace declaration that may appear in the html element). According to the default XML event processing, the markup of the element that bears the ev:event attribute must define the event handler that is activated when the indicated event occurs on the element's parent. In this paper, the parent will be either an XForms model element or an XForms user interface control.

XForms actions can be conditionally executed using the if attribute, and looping is supported using the while and iterate attributes. Each of these attributes contains an XPath expression that operates over the XML data instances in the XForms model. If an if attribute is used, the XForms action script is performed if the XPath expression evaluates to boolean true. When a while attribute is used, the script is repeatedly executed zero or more times while the XPath expression evaluates to true. For an iterate attribute, the XPath expression is expected to indicate a set of XML data instance nodes, and the script is executed once for each of the nodes. Most typically, these attributes are used on a container action element so that they control the conditional or repeated execution of all XForms actions contained within the action element.

The XForms actions most pertinent to moving elements are insert and delete. The delete action has a nodeset attribute containing an XPath expression that indicates the nodes to delete from instance data. The insert action has more attributes that offer various ways of copying instance nodes from one location to another. In this paper, we will cover the two main usage patterns: prepending and appending nodes into a parent element. In both cases, the origin attribute contains an XPath that indicates the source node or nodes to be copied. For prepending nodes, only the context attribute is used to specify an XPath indicating the parent node into which the origin nodes are copied. Due to default behaviors of the other attributes of insert, if the parent node has any child nodes, the new nodes are prepended to its child list. For appending child nodes, the context attribute can still be used to indicate the parent node, but three other attributes are specified. The nodeset attribute specifies an XPath that selects the child nodes, the at attribute is assigned the literal XPath expression "last()", and the position attribute is set to the literal string "after". The overall effect is that the origin nodes are copied after the last child of the parent node. As an example of insert and delete, the following code initializes the item element content in the DATA instance:

<action ev:event="xforms-model-construct-done">
    <delete nodeset="instance('DATA')/items/item"/>
    <insert context="instance('DATA')/items" 
            origin="instance('ORIGDATA')/items/item"/>
</action>

Because the action element above is a child of the XForms model, it is performed in response to the xforms-model-construct-done event that the XForms processor automatically dispatches to the model after the model is initialized and before the user interface controls are created. The delete action removes any item elements that may already be in the DATA instance's items element. Then, the insert action copies the item elements from items element of the ORIGDATA instance to the items element of the DATA instance. This is the pattern for using a template to reinitialize a list, and the opposite pattern can be used to move elements from one location to a new location: first use insert to copy the nodes from an original location to the new location, then use delete to remove them from the original location.

The setvalue action is used to changing the text content of a node of instance data. It has a ref attribute whose XPath expression indicates an XML data instance node whose content value will be changed. The value attribute contains an XPath expression that evaluates to a string that becomes the new text content for the node. As an example, the following code reduces the value of the window start node by the windows size, unless it is already the minimal value:

<setvalue ref="instance('VARS')/window/start" 
          value="choose(. > 1, . - ../size, .)"/>

The ref indicates the start node. For convenience, the value expression is evaluated relative to the node being changed, so the node being changed and its parent can be indicated by the . and .. shorthand notations, respectively. The choose() function that XForms adds to its XPath processor performs conditional logic within an expression. The invocation above first tests whether the start node is greater than 1. If so, then it subtracts the window size from it, and if not, then the start node is given the same value it currently has.

One final XForms action that is relevant to data manipulation is the dispatch action, which creates an XML event with the name given by its name attribute and dispatches it to the document element with the XML identifier that matches the value in its targetid attribute. This action enables form authors to convert events that occur on XForms user interface controls into events that occur on the XForms model element, which contains the action scripts that perform data manipulation. The dispatch action has an additional optional attribute called delay that specified a number of milliseconds to wait before dispatching an event. This enables an action sequence to perform processing later, after yielding to allow event loop and user interface processing. This capability can be used to help create a non-blocking loop, as demonstrated in the section on Multitasking Techniques.

User Interface Controls

The group element is an XForms user interface control that acts as a container for other XForms user interface controls. One useful technique is to use a group to declare XForms as the default namespace, as shown below, so that explicit namespace qualification is not required for the group nor for the XForms user interface controls it contains.

<group xmlns="http://www.w3.org/2002/xforms">
    <!-- XForms user interface controls -->
</group>

The trigger element allows a user to activate an XForms action script without directly entering any data, such as via a clickable button user interface control. When a user activates the user interface control, the trigger element automatically receives a DOMActivate event. Therefore, an XForms action within the trigger can run a script in response to the occurrence of the event by declaring itself to be a handler for the DOMActivate. As an example, the trigger element below creates a user interface control that allows a user to scroll to a previous window of item elements if the current window start is above the minimal value:

<trigger>
   <label>Previous</label>
   <setvalue ev:event="DOMActivate"
             ref="instance('VARS')/window/start" value="choose(. > 1, . - ../size, .)"/>
</trigger>

The output control allows users to view data and calculated values. For example, the following output elements show the user what range of items out of the total is being shown by a windowing mechanism:

<output ref="instance('VARS')/window/start"/> to 
<output value="choose(instance('VARS')/window/end &lt; count(instance('DATA')/items/item),
                      instance('VARS')/window/end, count(instance('DATA')/items/item))"/>
<output value="count(instance('DATA')/items/item)">
    <label> of </label>
</output>

The first output element shows how to display the value of a node of instance data using the ref attribute. The second output element uses the value attribute to display the result of evaluating an XPath expression. The third output element shows how to add a label text before the value to be displayed (rather than placing the text inline before the output element).

To show a table of the item elements and enable user editing of the text content of each item's child elements, we will use two XForms user interface controls, the repeat element and the input element. The repeat element is a container element, similar to group, except that its markup content is repeated once for each node in an XPath expression given by its nodeset attribute. In the code below, the nodeset binds the repeat to the range of item elements indicated by the windowing variables. For each item element so indicated, a copy of the input elements within the repeat is created. XForms input elements are user interface controls that allow editing of the data nodes to which they are bound by the XPath expressions in their ref attributes. The expressions in the ref attributes are evaluated relative to the surrounding context nodes, which in this case are the item elements from the nodeset of the repeat. In the code below, the input elements allow a user to edit the content of the num, name, and phone child elements of each item element:

<repeat nodeset="instance('DATA')/items/item[position() >= instance('VARS')/window/start and
                                             position() &lt;= instance('VARS')/window/end]">
    <input ref="num"><label/></input>
    <input ref="name">><label/></input>
    <input ref="phone"><label/></input>
</repeat>

There are a number of additional XForms user interface controls, but they are not directly related to the current topic. Details on them can be found in the XForms specification.

Initiating Data Processing

The first step of data processing is to identify and declare the process control variables. It will be useful to have a variable to store a copy of the unsorted list of items so that the main process of sorting can be expressed as if the process had received the list as a parameter. Variables must also be declared to have a place to grow the sorted list and to keep track of the least key found in each iteration of the sort. The following instance data declaration creates the required process control variables:

<instance id="SVARS">
   <sort xmlns="">
      <items/>
      <sorted/>
      <least/>
   </sort>    
</instance>

The items element is used to take a copy of the unsorted list of item elements from the DATA instance's items element. The sorted element is the one into which each item is transferred when it is determined to have the least key in an iteration of the sort. The least element is used to obtain the least key value during each loop iteration.

To enable a user to initiate execution of a data processing algorithm, user interface trigger elements in the XHTML body can be used. Upon activation, they can dispatch events to the XForms model in the XHTML head to request performance of the desired algorithms. For example, the following markup shows how to initiate execution of the numeric and lexicographic sorting algorithms:

...
<model id="M" xmlns="http://www.w3.org/2002/xforms">
   ...
   <instance id="SVARS">
      ...
   </instance>
   ...
   <action ev:event="sel-sort-num">
      <!-- Processing actions to Sort by Numeric Keys here -->
   </action>
   <action ev:event="sel-sort-name">
      <!-- Processing actions to Sort by String Keys here -->
   </action>
   ...
</model>
...
<trigger>
   <label>Selection Sort by Number</label>
   <dispatch ev:event="DOMActivate" name="sel-sort-num" targetid="M"/>
</trigger>
<trigger>
   <label>Selection Sort by Name</label>
   <dispatch ev:event="DOMActivate" name="sel-sort-name" targetid="M"/>
</trigger>
...

Because the action elements above are children of the XForms model, they are event handlers for the sel-sort-num and sel-sort-name events that are dispatched by the trigger elements above when they are activated by the user. The processing actions performed by these event handlers are discussed in the next two sections.

Sorting by Numeric Keys

The numeric sorting algorithm is performed by the sel-sort-num event handler. The first of the processing actions copies the unsorted items from the DATA instance into the SVARS instance. Then, a while loop is used to generate the sorted list. The final two processing actions replace the DATA instance's unsorted item list with the item elements in the sorted list. The following XForms markup implements the top logical level of data processing:

<action ev:event="sel-sort-num">
    <insert context="instance('SVARS')/items" 
            origin="instance('DATA')/items/item"/>
            
    <action while="instance('SVARS')/items/item">
        <!-- Code to find item(s) with least key and move to sorted list -->
    </action>
    
    <delete nodeset="instance('DATA')/items/item"/>
    <insert context="instance('DATA')/items" 
            origin="instance('SVARS')/sorted/item"/>
    <delete nodeset="instance('SVARS')/sorted/item"/>
</action>

For numerical sorting, we can take advantage of a function min() that XForms adds to its XPath processor. Like the spreadsheet function of the same name, min() returns the least numeric value of the nodes in its nodeset parameter. Once the least value is known, a setvalue action can place it into the least data element so that it can be used to identify the item(s) to move to the sorted list. The insert action in the code below uses an XPath predicate in its origin attribute to obtain all item elements whose num child matches the least key, so if there are duplicate keys, then all matching items will be copied to the sorted list at the same time. The rest of the insert element's attributes target the sorted list with the append insertion pattern. Once the item or items are appended, the matching items are deleted from the unsorted list of items, as follows:

<setvalue ref="instance('SVARS')/least"
          value="min(instance('SVARS')/items/item/num)"/> 
                
<insert context="instance('SVARS')/sorted" 
        nodeset="item" at="last()" position="after" 
        origin="../items/item[num=instance('SVARS')/least]"/>
                	
<delete nodeset="instance('SVARS')/items/item[num=instance('SVARS')/least]"/>

Note that although there is only a single level loop expressed at the XForms action scripting level, the run-time performance is still quadratic (as expected) because the XSLTForms javascript implementation of the min() function contains a loop.

Sorting by String Keys

Lexicographic sorting by name is performed by the sel-sort-name event handler. The same first processing action is needed to copy the unsorted items from the DATA instance, the same while loop is needed to generate the sorted list, and the same final two processing actions are needed to replace the unsorted items with the item elements in the sorted list. However, for string sorting, the inner comparison loop to find the least key value must be explicitly expressed with XForms actions because there is no string equivalent of the min() function. XForms does add to its XPath processor a compare() function that performs lexicographic comparison of the values of two nodes given as parameters. In the body of the outer while loop, a first setvalue action can initialize the least value, and then the expressed inner loop can iterate through the unsorted list of items and, for each node, if its name is lexicographically less than the least value, then an inner loop setvalue action can update the least value with the string value of the iteration node's name element, as follows:

<action ev:event="sel-sort-name">
    ...            
    <action while="instance('SVARS')/items/item">
        <setvalue ref="instance('SVARS')/least"
                  value="../items/item[1]/name"/>
                	          
        <action iterate="instance('SVARS')/items/item">
            <setvalue if="compare(./name, ../../least) < 0"
                      ref="../../least" value="context()/name"/>
        </action>
        ...
    </action>
    ...
</action>

Note that the context() function that XForms adds to its XPath processor must be used to obtain the iteration node because the value attribute is normally evaluated relative to the result of the ref attribute. Also, note that the compare() function is used instead of the XPath less-than operator because the latter duck types the values being compared. For example, in a list of movie titles, the XPath less-than operator would place "300" before "1984" and after "42" whereas lexicographic comparison would make both decisions differently.

As with the numeric sort, the lexicographic sort also has quadratic performance, but the numeric sort is about 20% faster because the inner loop is pushed down one level of abstraction (into the JavaScript implementation). As Figure 1 shows, these algorithms take several seconds to execute as the number of items approaches the mid-hundreds, during which time no other algorithms can execute and the main thread of user interaction is blocked.

Figure 1: Performance of the Lexicographic Selection Sort

The solid orange curve shows the empirical performance of the lexicographic sort as the number of items N ranges from 400 to 1000. Time values in seconds are based on using a 2.9GHz CPU and a current Firefox web browser. The behavior of the sort is characterized mathematically by Gaussian summation. The blue dashed curve shows a Gaussian summation that is multiplied by a constant C that makes it intersect with the empirical performance curve at N=400 items. The quadratic performance of the sort is illustrated by similarity in the shapes of these curves as the number of items increases from 400 to 1000.

Coordination

Starting a non-blocking process begins the same way as for a blocking process, with a trigger or other means of dispatching the initiating event to the XForms model. The handler for the model event is implemented differently, though, because it must start up a non-blocking process on a task list and request its first time slice. We begin by adding a few more process control variables that will help control task execution, along with a separate data instance to keep a list of running tasks:

<instance id="SVARS">
    <sort xmlns="" key="" state="play" priority="4">
        ...
    </sort>
</instance>
        
<instance id="TASKS">
    <list xmlns=""/>
</instance>

The list element in the TASKS instance will receive, as a child element, a copy of the sort element (i.e. a set of process control variables) for each sort algorithm while it is running. Now that sorting by num and by name will both be able to run at the same time, the key attribute will indicate which sort algorithm a sort element represents. The state attribute will help control execution of a sort algorithm. Valid states are play (start or continue running), pause, and stop (interrupted or completed). The priority attribute will be used to specify the number of milliseconds to wait before allocating another time slice to a sort algorithm.

Starting up a non-blocking algorithm involves first pushing a copy of its process control variables into the TASKS list and making that copy distinguishable from other sets of process control variables. In the case of sorting, this involves setting the key attribute appropriately. Then, as with the blocking sort algorithms, we take a copy of the unsorted items from the DATA instance. Of course, we skip these initial steps if the user activates the sorting trigger when the sort is already in progress. One reason the user may do this is to continue a sort that has been paused, so if that is the case, then in lieu of those initial steps, we change the state back to play. Here's how to start up (or continue) numeric sorting:

<action ev:event="sel-sort-num">

    <action if="not(instance('TASKS')/sort[@key='num'])">
        <insert context="instance('TASKS')" origin="instance('SVARS')"/>
        <setvalue ref="instance('TASKS')/sort[@key='']/@key">num</setvalue>
                    
        <insert context="instance('TASKS')/sort[@key='num']/items" 
                origin="instance('DATA')/items/item"/>
    </action>
    
    <setvalue if="instance('TASKS')/sort[@key='num']/@state = 'pause'"
              ref="instance('TASKS')/sort[@key='num']/@state">play</setvalue>
    ...
</action>

Note that in the blocking numeric sort algorithm, XPath subexpressions that referred to instance('SVARS') must be changed to start with instance('TASKS')/sort[@key='num']. The same is true for lexicographic sorting, except for using the value 'name'' for the key attribute.

The processing performed by each time slice of the non-blocking algorithm is encoded in a separate XForms action that is activated by a distinct event. The event name for numeric sorting is sel-sort-num-background-task. The final step of the non-blocking algorithm's initiator action is to dispatch that assigned event to the XForms model to initiate processing in time slices:

<action ev:event="sel-sort-num">
    ...
    <dispatch if="instance('TASKS')/sort[@key='num']/@state = 'play'"
              name="sel-sort-num-background-task" targetid="M"/>
</action>

The processing of each time slice begins with a test to ensure that the algorithm is still in a state of play. If so, then the task performed in each time slice will, in this case, be one iteration of the selection sort outer loop. So, instead of using a while loop that blocks processing until all selection sort iterations are done, an if attribute is used instead to test whether one iteration should be performed. Then, after performing one iteration of the previously defined actions, a non-blocking loop is achieved by using a delayed dispatch action to reinvoke the sel-sort-num-background-task handler after a given number of milliseconds, as follows:

<action ev:event="sel-sort-num-background-task">
    <action if="instance('TASKS')/sort[@key='num']/@state = 'play'">
        <action if="instance('TASKS')/sort[@key='num']/items/item">
    	
            <!-- Same actions to find smallest key and move matching item(s) from unsorted list to end of sorted list -->
            <!-- (except replace subexpression "instance('SVARS')" with "instance('TASKS')/sort[@key='num']" in XPaths) -->
                
            <dispatch name="sel-sort-num-background-task" targetid="M" delay="4"/>
        </action>
        ...
    </action>
    ...
</action>

Once all items have been sorted, the unsorted list of items becomes empty. The blocking algorithm's while loop terminates and then execution proceeds to post-processing code that copies the sorted list back into the DATA instance. The non-blocking algorithm requires the same post-processing, but since it is another possible subtask after an iteration that may not be the last, the post-processing is placed within a conditional test that the unsorted list is empty (an empty nodeset evaluates to boolean false). By virtue of its position in the markup, the post-processing step runs in the same time slice as the last sorting iteration. Once the post-processing logic is performed, the algorithm is changed to the stop state. When this occurs, execution proceeds out of the play state markup, where a final action removes the algorithm's set of process control variables from the TASKS list if the algorithm is in the stop state:

<action ev:event="sel-sort-num-background-task">
    <action if="instance('TASKS')/sort[@key='num']/@state = 'play'">
        ...
        <action if="not(instance('TASKS')/sort[@key='num']/items/item)">
            <!-- Same actions to copy sorted list back to DATA instance, replacing the unsorted list -->
            <!-- (except replace "instance('SVARS')" with "instance('TASKS')/sort[@key='num']" in XPaths) -->
                
            <setvalue ref="instance('TASKS')/sort[@key='num']/@state">stop</setvalue>            
        </action>
    </action>
            
    <delete if="instance('TASKS')/sort[@key='num']/@state = 'stop'"
            nodeset="instance('TASKS')/sort[@key='num']"/>
</action>

Now that an algorithm can be executed without blocking the main thread of user interaction, a user can continue to enter data into input elements, view data shown by output elements, and activate trigger elements. Although this is the intended effect in general, users should be restricted from changing content within the DATA instance's items element because the changes will be overwritten with the sort algorithm's results. For trigger elements that let a user insert or delete an item, XForms already offers the if attribute, so insertion and deletion into the items element can be made conditional upon the TASKS list containing no sort elements. To help restrict editing content within existing item elements, XForms provides a readonly property for every node of instance data, and the value of each node's readonly property value can be declaratively controlled by an XPath expression that tests whether there are any sort elements in the TASKS list. User interface controls bound to read-only nodes allow users to view but not edit the bound node's content value. Moreover, nodes default to read-only if they have a read-only ancestor. Hence, only the items element in the DATA instance must be declared to have a readonly value of true to restrict the user from editing the num, name, and phone text content within all item elements. In the following markup, the readonly property changes between true and false whenever the TASKS list changes between containing and not containing a sort element:

<bind nodeset="instance('DATA')/items"
      readonly="instance('TASKS')/sort"/>

The execution of a non-blocking algorithm can be paused at any time by programmatically taking it out of the play state without putting it in the stop state. Furthermore, the algorithm doesn't block user interface interactions, so the form author can give the user direct control of this capability. The following markup puts the algorithm into the pause state upon a user's activation of an XForms trigger in the user interface:

<group ref="instance('TASKS')/sort[@key='num']">
    ...
    <trigger>
        <label>Pause</label>
        <setvalue ev:event="DOMActivate" if="@state = 'play'" ref="@state">pause</setvalue>
    </trigger>
    ...
</group>

In the next time slice, the background task event handler action performs no operations since all code in the handler is executed on the condition of being in the play or stop states. This includes the fact that no further time slices are allocated since no further delayed dispatch actions are performed. As mentioned above, the event handler for the sel-sort-num event can be used not only to start the sorting algorithm but also to continue it if it is in the pause state. In that case, the handler does not create a new set of process control variables, but it changes the state back to play and then requests a time slice.

A non-blocking algorithm can also be programmatically stopped at any time before completion by changing it to the stop state. Of course, if the algorithm is paused, then a time slice must also be requested to ensure that the stopping logic executes. Since we must test the pause state before changing to the stop state, we request the extra time slice with a delayed action so that it runs only after the last action changes to the stop state^[3], as follows:

<group ref="instance('TASKS')/sort[@key='num']">
    ...
    <trigger>
        <label>Stop</label>
        <action ev:event="DOMActivate">
            <dispatch if="@state = 'pause'" name="sel-sort-num-background-task" targetid="M" delay="1"/>
            <setvalue ref="@state">stop</setvalue>
        </action>
    </trigger>
    ...
</group>

Progress

Since the user interface remains active during the execution of a non-blocking algorithm, it is also possible to calculate and report the algorithm's progress. The progress can be calculated and stored in an additional process control variable. For the selection sort, a few additional attributes are also needed to help with calculating progress, as follows:

<instance id="SVARS">
    <sort xmlns="" ...>
        ...
        <progress unsortedCount="" unsortedGauss="" totalCount="" totalGauss=""/>
    </sort>
</instance>

The unsortedCount and totalCount attributes represent the number of items still to be sorted and the total number of items being sorted. These can be calculated using declarative calculate expressions as follows:

<bind nodeset="instance('TASKS')/sort/progress/@unsortedCount" 
      calculate="count(../../items/item)"/>
        
<bind nodeset="instance('TASKS')/sort/progress/@totalCount" 
      calculate="../@unsortedCount + count(../../sorted/item)"/>

These values are important for tracking the progress of each sort, but using their direct ratio to help calculate progress would be inaccurate because selection sort processing is quadratic, not linear. Specifically, the number of steps, i.e. the work, needed to process n items is given by the Gaussian summation formula: (n+1)*n/2.

The progress of an algorithm is the difference between the total work and the ratio of the remaining work and total work. For the selection sort, the number of remaining work steps and total work steps can be calculated by applying the Gaussian summation formula to the values of the unsortedCount and totalCount attributes. These calculated values are stored in the unsortedGauss and totalGauss attributes. Then, the value of the progress element can be declaratively calculated as follows:

<bind nodeset="instance('TASKS')/sort/progress/@unsortedGauss" 
      calculate="(../@unsortedCount div 2) * (../@unsortedCount + 1)"/>
        
<bind nodeset="instance('TASKS')/sort/progress/@totalGauss" 
      calculate="(../@totalCount div 2) * (../@totalCount + 1)"/>

<bind nodeset="instance('TASKS')/sort/progress"
      calculate="concat(round(100 * (1 - @unsortedGauss div @totalGauss)), '%')"/>

The declarative calculations above automatically bind to the process control variables of all sort algorithms as their representative sort elements are added to the TASKS list. Then, they are automatically updated as implicit additions to the processing of each time slice. Thus, the sort algorithm is transformed into a hybrid declarative/imperative algorithm. Furthermore, since the algorithm is non-blocking, declarative user interface bindings can automatically show the updated progress of each time slice using the following markup:

<group ref="instance('TASKS')/sort[@key='num']">
    ...
    <output ref="progress"> 
        <label> Progress: </label>
    </output>
</group>

When examining the progress updates on larger data sets, there can be a small lag in updating near the beginning, and the processing seems to slow down more perceptibly toward the end. These effects occur because of the simplicity of the method used to divide the processing across time slices. Each time slice performs one and only one iteration of the sort's inner loop regardless of how much or little time that may take. In very early iterations on large data sets, the inner loop may slightly block processing enough to perceive. The lag near the end is more noticeable because there is so little work being done per time slice that the idle wait time between time slices becomes a bottleneck to completion. A more balanced approach to assigning work to time slices could help to smooth out the processing. Solving the early stage lag would come at a cost of designing unnatural breaking points in the algorithm processing, whereas smoothing out and optimizing the later processing seems both more pertinent and also easier to solve with natural breaking points in the algorithm processing.

Priority

Any non-blocking XForms action script can be given a higher or lower execution priority using a minor variation of the delayed dispatch action. In the markup for the non-blocking processes above, the request for each new time slice was hard-coded to be delayed by 4 milliseconds using the delay attribute. Instead, the delay can be controlled with a process control variable in instance data, such as the priority attribute of the sort element. For a number of its elements, XForms added child elements to match certain attributes so that the child element could use a value attribute's XPath expression to dynamically obtain the value rather than using a hard-coded attribute value. For the dispatch action, the value attribute of a delay child element can be used to obtain the delay from the priority attribute in instance data as follows:

<dispatch name="sel-sort-num-background-task" targetid="M">
    <delay value="instance('TASKS')/sort[@key='num']/@priority"/>
</dispatch>

Increasing or decreasing the execution priority is then as simple as using the setvalue action to change the priority attribute value, after which the subsequent time slices will use the new value to set the length of delay for the successor time slice. The priority can be increased and decreased throughout the execution of the algorithm. In the following markup, trigger elements give the end-user direct control of the execution priority:

<group ref="instance('TASKS')/sort[@key='num']">
    ...
    <trigger>
        <label>Decrease priority</label>
        <setvalue ev:event="DOMActivate" ref="@priority" value=". * 2"/>
    </trigger>
    <trigger>
        <label>Increase priority</label>
        <setvalue ev:event="DOMActivate" ref="@priority" value="choose(. > 1, . div 2, .)"/>
    </trigger>
    ...
</group>

In this markup, the execution priority level is decreased by doubling the number of milliseconds of delay, and it is increased by halving the number of milliseconds, down to the minimum of a 1 millisecond delay. It is instructive to run^[2] both sort algorithms simultaneously, and then decrease the priority level of the first sort and increase the priority level of the second sort so that it finishes first.